reader.h 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_CBOR_READER_H_
  5. #define COMPONENTS_CBOR_READER_H_
  6. #include <stddef.h>
  7. #include <map>
  8. #include "base/containers/span.h"
  9. #include "base/memory/raw_ptr.h"
  10. #include "components/cbor/cbor_export.h"
  11. #include "components/cbor/values.h"
  12. #include "third_party/abseil-cpp/absl/types/optional.h"
  13. // Concise Binary Object Representation (CBOR) decoder as defined by
  14. // https://tools.ietf.org/html/rfc7049. This decoder only accepts canonical CBOR
  15. // as defined by section 3.9.
  16. //
  17. // This implementation supports the following major types:
  18. // - 0: Unsigned integers, up to 64-bit values*.
  19. // - 1: Signed integers, up to 64-bit values*.
  20. // - 2: Byte strings.
  21. // - 3: UTF-8 strings.
  22. // - 4: Definite-length arrays.
  23. // - 5: Definite-length maps.
  24. // - 7: Simple values.
  25. //
  26. // * Note: For simplicity, this implementation represents both signed and
  27. // unsigned integers with signed int64_t. This reduces the effective range
  28. // of unsigned integers.
  29. //
  30. // Requirements for canonical CBOR representation:
  31. // - Duplicate keys in maps are not allowed.
  32. // - Keys for maps must be sorted first by length and then by byte-wise
  33. // lexical order, as defined in Section 3.9.
  34. //
  35. // Known limitations and interpretations of the RFC (and the reasons):
  36. // - Does not support indefinite-length data streams or semantic tags (major
  37. // type 6). (Simplicity; security)
  38. // - Does not support the floating point and BREAK stop code value types in
  39. // major type 7. (Simplicity)
  40. // - Does not support non-character codepoints in major type 3. (Security)
  41. // - Treats incomplete CBOR data items as syntax errors. (Security)
  42. // - Treats trailing data bytes as errors. (Security)
  43. // - Treats unknown additional information formats as syntax errors.
  44. // (Simplicity; security)
  45. // - Limits CBOR value inputs to at most 16 layers of nesting. Callers can
  46. // enforce more shallow nesting by setting |max_nesting_level|. (Efficiency;
  47. // security)
  48. // - Only supports CBOR maps with integer or string type keys, due to the
  49. // cost of serialization when sorting map keys. (Efficiency; simplicity)
  50. // - Does not support simple values that are unassigned/reserved as per RFC
  51. // 7049, and treats them as errors. (Security)
  52. namespace cbor {
  53. class CBOR_EXPORT Reader {
  54. public:
  55. enum class DecoderError {
  56. CBOR_NO_ERROR = 0,
  57. UNSUPPORTED_MAJOR_TYPE,
  58. UNKNOWN_ADDITIONAL_INFO,
  59. INCOMPLETE_CBOR_DATA,
  60. INCORRECT_MAP_KEY_TYPE,
  61. TOO_MUCH_NESTING,
  62. INVALID_UTF8,
  63. EXTRANEOUS_DATA,
  64. OUT_OF_ORDER_KEY,
  65. NON_MINIMAL_CBOR_ENCODING,
  66. UNSUPPORTED_SIMPLE_VALUE,
  67. UNSUPPORTED_FLOATING_POINT_VALUE,
  68. OUT_OF_RANGE_INTEGER_VALUE,
  69. DUPLICATE_KEY,
  70. UNKNOWN_ERROR,
  71. };
  72. // CBOR nested depth sufficient for most use cases.
  73. static const int kCBORMaxDepth = 16;
  74. // Config contains configuration for a CBOR parsing operation.
  75. struct CBOR_EXPORT Config {
  76. Config();
  77. Config(const Config&) = delete;
  78. Config& operator=(const Config&) = delete;
  79. ~Config();
  80. // Used to report the number of bytes of input consumed. This suppresses the
  81. // |EXTRANEOUS_DATA| error case. May be nullptr.
  82. raw_ptr<size_t> num_bytes_consumed = nullptr;
  83. // Used to report the specific error in the case that parsing fails. May be
  84. // nullptr;
  85. raw_ptr<DecoderError, DanglingUntriaged> error_code_out = nullptr;
  86. // Controls the maximum depth of CBOR nesting that will be permitted. This
  87. // exists to control stack consumption during parsing.
  88. int max_nesting_level = kCBORMaxDepth;
  89. // Causes strings that are not valid UTF-8 to be accepted and suppresses the
  90. // |INVALID_UTF8| error, unless such strings are map keys. Invalid strings
  91. // will result in Values of type |INVALID_UTF8| rather than |STRING|. Users
  92. // of this feature should ensure that every invalid string is accounted for
  93. // in the resulting structure.
  94. //
  95. // (Map keys are not allowed to be invalid because it was not necessary for
  96. // the motivating case and because it adds complexity to handle the ordering
  97. // correctly.)
  98. bool allow_invalid_utf8 = false;
  99. // Causes an input to be accepted even if it contains one or more maps with
  100. // keys that are not in the canonical ordering as defined in Section 3.9,
  101. // and suppresses the OUT_OF_ORDER_KEY error. The original ordering of keys
  102. // will _not_ be preserved, but instead, in the returned cbor::Value, all
  103. // maps are re-sorted so that their keys are in canonical order. By
  104. // definition, enabling this option may result in loss of information (i.e.
  105. // the original key ordering).
  106. //
  107. // Enabling this option will still not allow duplicate keys, in case of
  108. // which the DUPLICATE_KEY error will be emitted.
  109. bool allow_and_canonicalize_out_of_order_keys = false;
  110. };
  111. Reader(const Reader&) = delete;
  112. Reader& operator=(const Reader&) = delete;
  113. ~Reader();
  114. // Reads and parses |input_data| into a Value. Returns an empty Optional
  115. // if the input violates any one of the syntax requirements (including unknown
  116. // additional info and incomplete CBOR data).
  117. //
  118. // The caller can optionally provide |error_code_out| to obtain additional
  119. // information about decoding failures.
  120. //
  121. // If the caller provides it, |max_nesting_level| cannot exceed
  122. // |kCBORMaxDepth|.
  123. //
  124. // Returns an empty Optional if not all the data was consumed, and sets
  125. // |error_code_out| to EXTRANEOUS_DATA in this case.
  126. static absl::optional<Value> Read(base::span<const uint8_t> input_data,
  127. DecoderError* error_code_out = nullptr,
  128. int max_nesting_level = kCBORMaxDepth);
  129. // A version of |Read|, above, that takes a |Config| structure to allow
  130. // additional controls.
  131. static absl::optional<Value> Read(base::span<const uint8_t> input_data,
  132. const Config& config);
  133. // A version of |Read| that takes some fields of |Config| as parameters to
  134. // avoid having to construct a |Config| object explicitly.
  135. static absl::optional<Value> Read(base::span<const uint8_t> input_data,
  136. size_t* num_bytes_consumed,
  137. DecoderError* error_code_out = nullptr,
  138. int max_nesting_level = kCBORMaxDepth);
  139. // Translates errors to human-readable error messages.
  140. static const char* ErrorCodeToString(DecoderError error_code);
  141. private:
  142. explicit Reader(base::span<const uint8_t> data);
  143. // Encapsulates information extracted from the header of a CBOR data item,
  144. // which consists of the initial byte, and a variable-length-encoded integer
  145. // (if any).
  146. struct DataItemHeader {
  147. // The major type decoded from the initial byte.
  148. Value::Type type;
  149. // The raw 5-bit additional information from the initial byte.
  150. uint8_t additional_info;
  151. // The integer |value| decoded from the |additional_info| and the
  152. // variable-length-encoded integer, if any.
  153. uint64_t value;
  154. };
  155. absl::optional<DataItemHeader> DecodeDataItemHeader();
  156. absl::optional<Value> DecodeCompleteDataItem(const Config& config,
  157. int max_nesting_level);
  158. absl::optional<Value> DecodeValueToNegative(uint64_t value);
  159. absl::optional<Value> DecodeValueToUnsigned(uint64_t value);
  160. absl::optional<Value> DecodeToSimpleValue(const DataItemHeader& header);
  161. absl::optional<uint64_t> ReadVariadicLengthInteger(uint8_t additional_info);
  162. absl::optional<Value> ReadByteStringContent(const DataItemHeader& header);
  163. absl::optional<Value> ReadStringContent(const DataItemHeader& header,
  164. const Config& config);
  165. absl::optional<Value> ReadArrayContent(const DataItemHeader& header,
  166. const Config& config,
  167. int max_nesting_level);
  168. absl::optional<Value> ReadMapContent(const DataItemHeader& header,
  169. const Config& config,
  170. int max_nesting_level);
  171. absl::optional<uint8_t> ReadByte();
  172. absl::optional<base::span<const uint8_t>> ReadBytes(uint64_t num_bytes);
  173. bool IsKeyInOrder(const Value& new_key,
  174. const std::map<Value, Value, Value::Less>& map);
  175. // Check if `new_key` is a duplicate of a key that already exists in the
  176. // `map`.
  177. bool IsDuplicateKey(const Value& new_key,
  178. const std::map<Value, Value, Value::Less>& map);
  179. bool IsEncodingMinimal(uint8_t additional_bytes, uint64_t uint_data);
  180. DecoderError GetErrorCode() { return error_code_; }
  181. size_t num_bytes_remaining() const { return rest_.size(); }
  182. base::span<const uint8_t> rest_;
  183. DecoderError error_code_;
  184. };
  185. } // namespace cbor
  186. #endif // COMPONENTS_CBOR_READER_H_