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 |