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 #ifndef NET_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ | |
6 #define NET_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ | |
7 | |
8 // HpackStringDecoder decodes strings encoded per the HPACK spec; this does | |
9 // not mean decompressing Huffman encoded strings, just identifying the length, | |
10 // encoding and contents for a listener. | |
11 | |
12 #include <stddef.h> | |
13 | |
14 #include <algorithm> | |
15 #include <string> | |
16 | |
17 #include "base/logging.h" | |
18 #include "base/macros.h" | |
19 #include "net/base/net_export.h" | |
20 #include "net/http2/decoder/decode_buffer.h" | |
21 #include "net/http2/decoder/decode_status.h" | |
22 #include "net/http2/hpack/decoder/hpack_varint_decoder.h" | |
23 | |
24 namespace net { | |
25 | |
26 // Decodes a single string in an HPACK header entry. The high order bit of | |
27 // the first byte of the length is the H (Huffman) bit indicating whether | |
28 // the value is Huffman encoded, and the remainder of the byte is the first | |
29 // 7 bits of an HPACK varint. | |
30 // | |
31 // Call Start() to begin decoding; if it returns kDecodeInProgress, then call | |
32 // Resume() when more input is available, repeating until kDecodeInProgress is | |
33 // not returned. If kDecodeDone or kDecodeError is returned, then Resume() must | |
34 // not be called until Start() has been called to start decoding a new string. | |
35 // | |
36 // There are 3 variants of Start in this class, participants in a performance | |
37 // experiment. Perflab experiments show it is generally fastest to call | |
38 // StartSpecialCaseShort rather than StartOnly (~9% slower) or | |
39 // StartAndDecodeLength (~10% slower). | |
40 class NET_EXPORT_PRIVATE HpackStringDecoder { | |
41 public: | |
42 enum StringDecoderState { | |
43 kStartDecodingLength, | |
44 kDecodingString, | |
45 kResumeDecodingLength, | |
46 }; | |
47 | |
48 // TODO(jamessynge): Get rid of all but one of the Start and Resume methods | |
49 // after all of the HPACK decoder is checked in and has been perf tested. | |
50 template <class Listener> | |
51 DecodeStatus Start(DecodeBuffer* db, Listener* cb) { | |
52 return StartSpecialCaseShort(db, cb); | |
53 } | |
54 | |
55 template <class Listener> | |
56 DecodeStatus StartOnly(DecodeBuffer* db, Listener* cb) { | |
57 state_ = kStartDecodingLength; | |
58 return Resume(db, cb); | |
59 } | |
60 | |
61 template <class Listener> | |
62 DecodeStatus StartAndDecodeLength(DecodeBuffer* db, Listener* cb) { | |
63 DecodeStatus status; | |
64 if (StartDecodingLength(db, cb, &status)) { | |
65 state_ = kDecodingString; | |
66 return DecodeString(db, cb); | |
67 } | |
68 return status; | |
69 } | |
70 | |
71 template <class Listener> | |
72 DecodeStatus StartSpecialCaseShort(DecodeBuffer* db, Listener* cb) { | |
73 // Fast decode path is used if the string is under 127 bytes and the | |
74 // entire length of the string is in the decode buffer. More than 83% of | |
75 // string lengths are encoded in just one byte. | |
76 if (db->HasData() && (*db->cursor() & 0x7f) != 0x7f) { | |
77 // The string is short. | |
78 uint8_t h_and_prefix = db->DecodeUInt8(); | |
79 uint8_t length = h_and_prefix & 0x7f; | |
80 bool huffman_encoded = (h_and_prefix & 0x80) == 0x80; | |
81 cb->OnStringStart(huffman_encoded, length); | |
82 if (length <= db->Remaining()) { | |
83 // Yeah, we've got the whole thing in the decode buffer. | |
84 // Ideally this will be the common case. Note that we don't | |
85 // update any of the member variables in this path. | |
86 cb->OnStringData(db->cursor(), length); | |
87 db->AdvanceCursor(length); | |
88 cb->OnStringEnd(); | |
89 return DecodeStatus::kDecodeDone; | |
90 } | |
91 // Not all in the buffer. | |
92 huffman_encoded_ = huffman_encoded; | |
93 remaining_ = length; | |
94 // Call Resume to decode the string body, which is only partially | |
95 // in the decode buffer (or not at all). | |
96 state_ = kDecodingString; | |
97 return Resume(db, cb); | |
98 } | |
99 // Call Resume to decode the string length, which is either not in | |
100 // the decode buffer, or spans multiple bytes. | |
101 state_ = kStartDecodingLength; | |
102 return Resume(db, cb); | |
103 } | |
104 | |
105 template <class Listener> | |
106 DecodeStatus Resume(DecodeBuffer* db, Listener* cb) { | |
107 DecodeStatus status; | |
108 while (true) { | |
109 switch (state_) { | |
110 case kStartDecodingLength: | |
111 DVLOG(2) << "kStartDecodingLength: db->Remaining=" << db->Remaining(); | |
112 if (!StartDecodingLength(db, cb, &status)) { | |
113 // The length is split across decode buffers. | |
114 return status; | |
115 } | |
116 // We've finished decoding the length, which spanned one or more | |
117 // bytes. Approximately 17% of strings have a length that is greater | |
118 // than 126 bytes, and thus the length is encoded in more than one | |
119 // byte, and so doesn't get the benefit of the optimization in | |
120 // Start() for single byte lengths. But, we still expect that most | |
121 // of such strings will be contained entirely in a single decode | |
122 // buffer, and hence this fall through skips another trip through the | |
123 // switch above and more importantly skips setting the state_ variable | |
124 // again in those cases where we don't need it. | |
125 | |
126 // FALLTHROUGH_INTENDED | |
127 | |
128 case kDecodingString: | |
129 DVLOG(2) << "kDecodingString: db->Remaining=" << db->Remaining() | |
130 << " remaining_=" << remaining_; | |
131 return DecodeString(db, cb); | |
132 | |
133 case kResumeDecodingLength: | |
134 DVLOG(2) << "kResumeDecodingLength: db->Remaining=" | |
135 << db->Remaining(); | |
136 if (!ResumeDecodingLength(db, cb, &status)) { | |
137 return status; | |
138 } | |
139 } | |
140 } | |
141 } | |
142 | |
143 std::string DebugString() const; | |
144 | |
145 private: | |
146 static std::string StateToString(StringDecoderState v); | |
147 | |
148 // Returns true if the length is fully decoded and the listener wants the | |
149 // decoding to continue, false otherwise; status is set to the status from | |
150 // the varint decoder. | |
151 // If the length is not fully decoded, case state_ is set appropriately | |
152 // for the next call to Resume. | |
153 template <class Listener> | |
154 bool StartDecodingLength(DecodeBuffer* db, | |
155 Listener* cb, | |
156 DecodeStatus* status) { | |
157 if (db->Empty()) { | |
158 *status = DecodeStatus::kDecodeInProgress; | |
159 state_ = kStartDecodingLength; | |
160 return false; | |
161 } | |
162 uint8_t h_and_prefix = db->DecodeUInt8(); | |
163 huffman_encoded_ = (h_and_prefix & 0x80) == 0x80; | |
164 *status = length_decoder_.Start(h_and_prefix, 0x7f, db); | |
165 if (*status == DecodeStatus::kDecodeDone) { | |
166 OnStringStart(cb, status); | |
167 return true; | |
168 } | |
169 // Set the state to cover the DecodeStatus::kDecodeInProgress case. | |
170 // Won't be needed if the status is kDecodeError. | |
171 state_ = kResumeDecodingLength; | |
172 return false; | |
173 } | |
174 | |
175 // Returns true if the length is fully decoded and the listener wants the | |
176 // decoding to continue, false otherwise; status is set to the status from | |
177 // the varint decoder; state_ is updated when fully decoded. | |
178 // If the length is not fully decoded, case state_ is set appropriately | |
179 // for the next call to Resume. | |
180 template <class Listener> | |
181 bool ResumeDecodingLength(DecodeBuffer* db, | |
182 Listener* cb, | |
183 DecodeStatus* status) { | |
184 DCHECK_EQ(state_, kResumeDecodingLength); | |
185 *status = length_decoder_.Resume(db); | |
186 if (*status == DecodeStatus::kDecodeDone) { | |
187 state_ = kDecodingString; | |
188 OnStringStart(cb, status); | |
189 return true; | |
190 } | |
191 return false; | |
192 } | |
193 | |
194 // Returns true if the listener wants the decoding to continue, and | |
195 // false otherwise, in which case status set. | |
196 template <class Listener> | |
197 void OnStringStart(Listener* cb, DecodeStatus* status) { | |
198 remaining_ = length_decoder_.value(); | |
199 // Make callback so consumer knows what is coming. | |
200 cb->OnStringStart(huffman_encoded_, remaining_); | |
201 return; | |
202 } | |
203 | |
204 // Passes the available portion of the string to the listener, and signals | |
205 // the end of the string when it is reached. Returns kDecodeDone or | |
206 // kDecodeInProgress as appropriate. | |
207 template <class Listener> | |
208 DecodeStatus DecodeString(DecodeBuffer* db, Listener* cb) { | |
209 size_t len = std::min(remaining_, db->Remaining()); | |
210 if (len > 0) { | |
211 cb->OnStringData(db->cursor(), len); | |
212 db->AdvanceCursor(len); | |
213 remaining_ -= len; | |
214 } | |
215 if (remaining_ == 0) { | |
216 cb->OnStringEnd(); | |
217 return DecodeStatus::kDecodeDone; | |
218 } | |
219 state_ = kDecodingString; | |
220 return DecodeStatus::kDecodeInProgress; | |
221 } | |
222 | |
223 HpackVarintDecoder length_decoder_; | |
224 | |
225 // These fields are initialized just to keep ASAN happy about reading | |
226 // them from DebugString(). | |
227 size_t remaining_ = 0; | |
228 StringDecoderState state_ = kStartDecodingLength; | |
229 bool huffman_encoded_ = false; | |
230 }; | |
231 | |
232 NET_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& out, | |
233 const HpackStringDecoder& v); | |
234 | |
235 } // namespace net | |
236 #endif // NET_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ | |
OLD | NEW |