OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 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 |
| 5 // HpackVarintDecoder decodes HPACK variable length unsigned integers. These |
| 6 // integers are used to identify static or dynamic table index entries, to |
| 7 // specify string lengths, and to update the size limit of the dynamic table. |
| 8 // |
| 9 // The caller will need to validate that the decoded value is in an acceptable |
| 10 // range. |
| 11 // |
| 12 // In order to support naive encoders (i.e. which always output 5 extension |
| 13 // bytes for a uint32 that is >= prefix_mask), the decoder supports an an |
| 14 // encoding with up to 5 extension bytes, and a maximum value of 268,435,582 |
| 15 // (4 "full" extension bytes plus the maximum for a prefix, 127). It could be |
| 16 // modified to support a lower maximum value (by requiring that extensions bytes |
| 17 // be "empty"), or a larger value if valuable for some reason I can't see. |
| 18 // |
| 19 // For details of the encoding, see: |
| 20 // http://httpwg.org/specs/rfc7541.html#integer.representation |
| 21 // |
| 22 // TODO(jamessynge): Consider dropping support for encodings of more than 4 |
| 23 // bytes, including the prefix byte, as in practice we only see at most 3 bytes, |
| 24 // and 4 bytes would cover any desire to support large (but not ridiculously |
| 25 // large) header values. |
| 26 |
| 27 #ifndef NET_HTTP2_HPACK_DECODER_HPACK_VARINT_DECODER_H_ |
| 28 #define NET_HTTP2_HPACK_DECODER_HPACK_VARINT_DECODER_H_ |
| 29 |
| 30 #include <string> |
| 31 |
| 32 #include "base/logging.h" |
| 33 #include "net/base/net_export.h" |
| 34 #include "net/http2/decoder/decode_buffer.h" |
| 35 #include "net/http2/decoder/decode_status.h" |
| 36 |
| 37 namespace net { |
| 38 // Decodes an HPACK variable length unsigned integer, in a resumable fashion |
| 39 // so it can handle running out of input in the DecodeBuffer. Call Start or |
| 40 // StartExtended the first time (when decoding the byte that contains the |
| 41 // prefix), then call Resume later if it is necessary to resume. When done, |
| 42 // call value() to retrieve the decoded value. |
| 43 // |
| 44 // No constructor or destructor. Holds no resources, so destruction isn't |
| 45 // needed. Start and StartExtended handles the initialization of member |
| 46 // variables. This is necessary in order for HpackVarintDecoder to be part |
| 47 // of a union. |
| 48 class NET_EXPORT_PRIVATE HpackVarintDecoder { |
| 49 public: |
| 50 // |prefix_value| is the first byte of the encoded varint. |
| 51 // |prefix_mask| is the mask of the valid bits, i.e. without the top 1 to 4 |
| 52 // high-bits set, as appropriate for the item being decoded; must be a |
| 53 // contiguous sequence of set bits, starting with the low-order bits. |
| 54 DecodeStatus Start(uint8_t prefix_value, |
| 55 uint8_t prefix_mask, |
| 56 DecodeBuffer* db) { |
| 57 DCHECK_LE(15, prefix_mask) << std::hex << prefix_mask; |
| 58 DCHECK_LE(prefix_mask, 127) << std::hex << prefix_mask; |
| 59 // Confirm that |prefix_mask| is a contiguous sequence of bits. |
| 60 DCHECK_EQ(0, (prefix_mask + 1) & prefix_mask) << std::hex << prefix_mask; |
| 61 |
| 62 // Ignore the bits that aren't a part of the prefix of the varint. |
| 63 value_ = prefix_value & prefix_mask; |
| 64 |
| 65 if (value_ < prefix_mask) { |
| 66 MarkDone(); |
| 67 return DecodeStatus::kDecodeDone; |
| 68 } |
| 69 |
| 70 offset_ = 0; |
| 71 return Resume(db); |
| 72 } |
| 73 |
| 74 // The caller has already determined that the encoding requires multiple |
| 75 // bytes, i.e. that the 4 to 7 low-order bits (the number determined by the |
| 76 // prefix length, a value not passed into this function) of the first byte are |
| 77 // are all 1. The caller passes in |prefix_mask|, which is 2^prefix_length-1. |
| 78 DecodeStatus StartExtended(uint8_t prefix_mask, DecodeBuffer* db) { |
| 79 DCHECK_LE(15, prefix_mask) << std::hex << prefix_mask; |
| 80 DCHECK_LE(prefix_mask, 127) << std::hex << prefix_mask; |
| 81 // Confirm that |prefix_mask| is a contiguous sequence of bits. |
| 82 DCHECK_EQ(0, prefix_mask & (prefix_mask + 1)) << std::hex << prefix_mask; |
| 83 |
| 84 value_ = prefix_mask; |
| 85 offset_ = 0; |
| 86 return Resume(db); |
| 87 } |
| 88 |
| 89 // Resume decoding a variable length integer after an earlier |
| 90 // call to Start or StartExtended returned kDecodeInProgress. |
| 91 DecodeStatus Resume(DecodeBuffer* db) { |
| 92 CheckNotDone(); |
| 93 do { |
| 94 if (db->Empty()) { |
| 95 return DecodeStatus::kDecodeInProgress; |
| 96 } |
| 97 uint8_t byte = db->DecodeUInt8(); |
| 98 value_ += (byte & 0x7f) << offset_; |
| 99 if ((byte & 0x80) == 0) { |
| 100 if (offset_ < MaxOffset() || byte == 0) { |
| 101 MarkDone(); |
| 102 return DecodeStatus::kDecodeDone; |
| 103 } |
| 104 break; |
| 105 } |
| 106 offset_ += 7; |
| 107 } while (offset_ <= MaxOffset()); |
| 108 DLOG(WARNING) << "Variable length int encoding is too large or too long. " |
| 109 << DebugString(); |
| 110 MarkDone(); |
| 111 return DecodeStatus::kDecodeError; |
| 112 } |
| 113 |
| 114 uint32_t value() const { |
| 115 CheckDone(); |
| 116 return value_; |
| 117 } |
| 118 |
| 119 // This supports optimizations for the case of a varint with zero extension |
| 120 // bytes, where the handling of the prefix is done by the caller. |
| 121 void set_value(uint32_t v) { |
| 122 MarkDone(); |
| 123 value_ = v; |
| 124 } |
| 125 |
| 126 // All the public methods below are for supporting assertions and tests. |
| 127 |
| 128 std::string DebugString() const; |
| 129 |
| 130 // For benchmarking, these methods ensure the decoder |
| 131 // is NOT inlined into the caller. |
| 132 DecodeStatus StartForTest(uint8_t prefix_value, |
| 133 uint8_t prefix_mask, |
| 134 DecodeBuffer* db); |
| 135 DecodeStatus StartExtendedForTest(uint8_t prefix_mask, DecodeBuffer* db); |
| 136 DecodeStatus ResumeForTest(DecodeBuffer* db); |
| 137 |
| 138 static constexpr uint32_t MaxExtensionBytes() { return 5; } |
| 139 |
| 140 // Returns the highest value with the specified number of extension bytes and |
| 141 // the specified prefix length (bits). |
| 142 static uint64_t constexpr HiValueOfExtensionBytes(uint32_t extension_bytes, |
| 143 uint32_t prefix_length) { |
| 144 return (1 << prefix_length) - 2 + |
| 145 (extension_bytes == 0 ? 0 : (1LLU << (extension_bytes * 7))); |
| 146 } |
| 147 |
| 148 private: |
| 149 // Protection in case Resume is called when it shouldn't be. |
| 150 void MarkDone() { |
| 151 #ifndef NDEBUG |
| 152 // We support up to 5 extension bytes, so offset_ should never be > 28 when |
| 153 // it makes sense to call Resume(). |
| 154 offset_ = MaxOffset() + 7; |
| 155 #endif |
| 156 } |
| 157 void CheckNotDone() const { |
| 158 #ifndef NDEBUG |
| 159 DCHECK_LE(offset_, MaxOffset()); |
| 160 #endif |
| 161 } |
| 162 void CheckDone() const { |
| 163 #ifndef NDEBUG |
| 164 DCHECK_GT(offset_, MaxOffset()); |
| 165 #endif |
| 166 } |
| 167 static constexpr uint32_t MaxOffset() { |
| 168 return 7 * (MaxExtensionBytes() - 1); |
| 169 } |
| 170 |
| 171 // These fields are initialized just to keep ASAN happy about reading |
| 172 // them from DebugString(). |
| 173 uint32_t value_ = 0; |
| 174 uint32_t offset_ = 0; |
| 175 }; |
| 176 |
| 177 std::ostream& operator<<(std::ostream& out, const HpackVarintDecoder& v); |
| 178 |
| 179 } // namespace net |
| 180 |
| 181 #endif // NET_HTTP2_HPACK_DECODER_HPACK_VARINT_DECODER_H_ |
OLD | NEW |