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 #include "quiche/http2/hpack/huffman/hpack_huffman_decoder.h"
6
7 #include <bitset>
8 #include <limits>
9
10 #include "quiche/common/platform/api/quiche_logging.h"
11
12 // Terminology:
13 //
14 // Symbol - a plain text (unencoded) character (uint8), or the End-of-String
15 // (EOS) symbol, 256.
16 //
17 // Code - the sequence of bits used to encode a symbol, varying in length from
18 // 5 bits for the most common symbols (e.g. '0', '1', and 'a'), to
19 // 30 bits for the least common (e.g. the EOS symbol).
20 // For those symbols whose codes have the same length, their code values
21 // are sorted such that the lower symbol value has a lower code value.
22 //
23 // Canonical - a symbol's cardinal value when sorted first by code length, and
24 // then by symbol value. For example, canonical 0 is for ASCII '0'
25 // (uint8 value 0x30), which is the first of the symbols whose code
26 // is 5 bits long, and the last canonical is EOS, which is the last
27 // of the symbols whose code is 30 bits long.
28
29 namespace http2 {
30 namespace {
31
32 // HuffmanCode is used to store the codes associated with symbols (a pattern of
33 // from 5 to 30 bits).
34 typedef uint32_t HuffmanCode;
35
36 // HuffmanCodeBitCount is used to store a count of bits in a code.
37 typedef uint16_t HuffmanCodeBitCount;
38
39 // HuffmanCodeBitSet is used for producing a string version of a code because
40 // std::bitset logs nicely.
41 typedef std::bitset<32> HuffmanCodeBitSet;
42 typedef std::bitset<64> HuffmanAccumulatorBitSet;
43
44 static constexpr HuffmanCodeBitCount kMinCodeBitCount = 5;
45 static constexpr HuffmanCodeBitCount kMaxCodeBitCount = 30;
46 static constexpr HuffmanCodeBitCount kHuffmanCodeBitCount =
47 std::numeric_limits<HuffmanCode>::digits;
48
49 static_assert(std::numeric_limits<HuffmanCode>::digits >= kMaxCodeBitCount,
50 "HuffmanCode isn't big enough.");
51
52 static_assert(std::numeric_limits<HuffmanAccumulator>::digits >=
53 kMaxCodeBitCount,
54 "HuffmanAccumulator isn't big enough.");
55
56 static constexpr HuffmanAccumulatorBitCount kHuffmanAccumulatorBitCount =
57 std::numeric_limits<HuffmanAccumulator>::digits;
58 static constexpr HuffmanAccumulatorBitCount kExtraAccumulatorBitCount =
59 kHuffmanAccumulatorBitCount - kHuffmanCodeBitCount;
60
61 // PrefixInfo holds info about a group of codes that are all of the same length.
62 struct PrefixInfo {
63 // Given the leading bits (32 in this case) of the encoded string, and that
64 // they start with a code of length |code_length|, return the corresponding
65 // canonical for that leading code.
DecodeToCanonicalhttp2::__anon28e9a2420111::PrefixInfo66 uint32_t DecodeToCanonical(HuffmanCode bits) const {
67 // What is the position of the canonical symbol being decoded within
68 // the canonical symbols of |length|?
69 HuffmanCode ordinal_in_length =
70 ((bits - first_code) >> (kHuffmanCodeBitCount - code_length));
71
72 // Combined with |canonical| to produce the position of the canonical symbol
73 // being decoded within all of the canonical symbols.
74 return first_canonical + ordinal_in_length;
75 }
76
77 const HuffmanCode first_code; // First code of this length, left justified in
78 // the field (i.e. the first bit of the code is
79 // the high-order bit).
80 const uint16_t code_length; // Length of the prefix code |base|.
81 const uint16_t first_canonical; // First canonical symbol of this length.
82 };
83
operator <<(std::ostream & out,const PrefixInfo & v)84 inline std::ostream& operator<<(std::ostream& out, const PrefixInfo& v) {
85 return out << "{first_code: " << HuffmanCodeBitSet(v.first_code)
86 << ", code_length: " << v.code_length
87 << ", first_canonical: " << v.first_canonical << "}";
88 }
89
90 // Given |value|, a sequence of the leading bits remaining to be decoded,
91 // figure out which group of canonicals (by code length) that value starts
92 // with. This function was generated.
PrefixToInfo(HuffmanCode value)93 PrefixInfo PrefixToInfo(HuffmanCode value) {
94 if (value < 0b10111000000000000000000000000000) {
95 if (value < 0b01010000000000000000000000000000) {
96 return {0b00000000000000000000000000000000, 5, 0};
97 } else {
98 return {0b01010000000000000000000000000000, 6, 10};
99 }
100 } else {
101 if (value < 0b11111110000000000000000000000000) {
102 if (value < 0b11111000000000000000000000000000) {
103 return {0b10111000000000000000000000000000, 7, 36};
104 } else {
105 return {0b11111000000000000000000000000000, 8, 68};
106 }
107 } else {
108 if (value < 0b11111111110000000000000000000000) {
109 if (value < 0b11111111101000000000000000000000) {
110 if (value < 0b11111111010000000000000000000000) {
111 return {0b11111110000000000000000000000000, 10, 74};
112 } else {
113 return {0b11111111010000000000000000000000, 11, 79};
114 }
115 } else {
116 return {0b11111111101000000000000000000000, 12, 82};
117 }
118 } else {
119 if (value < 0b11111111111111100000000000000000) {
120 if (value < 0b11111111111110000000000000000000) {
121 if (value < 0b11111111111100000000000000000000) {
122 return {0b11111111110000000000000000000000, 13, 84};
123 } else {
124 return {0b11111111111100000000000000000000, 14, 90};
125 }
126 } else {
127 return {0b11111111111110000000000000000000, 15, 92};
128 }
129 } else {
130 if (value < 0b11111111111111110100100000000000) {
131 if (value < 0b11111111111111101110000000000000) {
132 if (value < 0b11111111111111100110000000000000) {
133 return {0b11111111111111100000000000000000, 19, 95};
134 } else {
135 return {0b11111111111111100110000000000000, 20, 98};
136 }
137 } else {
138 return {0b11111111111111101110000000000000, 21, 106};
139 }
140 } else {
141 if (value < 0b11111111111111111110101000000000) {
142 if (value < 0b11111111111111111011000000000000) {
143 return {0b11111111111111110100100000000000, 22, 119};
144 } else {
145 return {0b11111111111111111011000000000000, 23, 145};
146 }
147 } else {
148 if (value < 0b11111111111111111111101111000000) {
149 if (value < 0b11111111111111111111100000000000) {
150 if (value < 0b11111111111111111111011000000000) {
151 return {0b11111111111111111110101000000000, 24, 174};
152 } else {
153 return {0b11111111111111111111011000000000, 25, 186};
154 }
155 } else {
156 return {0b11111111111111111111100000000000, 26, 190};
157 }
158 } else {
159 if (value < 0b11111111111111111111111111110000) {
160 if (value < 0b11111111111111111111111000100000) {
161 return {0b11111111111111111111101111000000, 27, 205};
162 } else {
163 return {0b11111111111111111111111000100000, 28, 224};
164 }
165 } else {
166 return {0b11111111111111111111111111110000, 30, 253};
167 }
168 }
169 }
170 }
171 }
172 }
173 }
174 }
175 }
176
177 // Mapping from canonical symbol (0 to 255) to actual symbol.
178 // clang-format off
179 constexpr unsigned char kCanonicalToSymbol[] = {
180 '0', '1', '2', 'a', 'c', 'e', 'i', 'o',
181 's', 't', 0x20, '%', '-', '.', '/', '3',
182 '4', '5', '6', '7', '8', '9', '=', 'A',
183 '_', 'b', 'd', 'f', 'g', 'h', 'l', 'm',
184 'n', 'p', 'r', 'u', ':', 'B', 'C', 'D',
185 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
186 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
187 'U', 'V', 'W', 'Y', 'j', 'k', 'q', 'v',
188 'w', 'x', 'y', 'z', '&', '*', ',', ';',
189 'X', 'Z', '!', '\"', '(', ')', '?', '\'',
190 '+', '|', '#', '>', 0x00, '$', '@', '[',
191 ']', '~', '^', '}', '<', '`', '{', '\\',
192 0xc3, 0xd0, 0x80, 0x82, 0x83, 0xa2, 0xb8, 0xc2,
193 0xe0, 0xe2, 0x99, 0xa1, 0xa7, 0xac, 0xb0, 0xb1,
194 0xb3, 0xd1, 0xd8, 0xd9, 0xe3, 0xe5, 0xe6, 0x81,
195 0x84, 0x85, 0x86, 0x88, 0x92, 0x9a, 0x9c, 0xa0,
196 0xa3, 0xa4, 0xa9, 0xaa, 0xad, 0xb2, 0xb5, 0xb9,
197 0xba, 0xbb, 0xbd, 0xbe, 0xc4, 0xc6, 0xe4, 0xe8,
198 0xe9, 0x01, 0x87, 0x89, 0x8a, 0x8b, 0x8c, 0x8d,
199 0x8f, 0x93, 0x95, 0x96, 0x97, 0x98, 0x9b, 0x9d,
200 0x9e, 0xa5, 0xa6, 0xa8, 0xae, 0xaf, 0xb4, 0xb6,
201 0xb7, 0xbc, 0xbf, 0xc5, 0xe7, 0xef, 0x09, 0x8e,
202 0x90, 0x91, 0x94, 0x9f, 0xab, 0xce, 0xd7, 0xe1,
203 0xec, 0xed, 0xc7, 0xcf, 0xea, 0xeb, 0xc0, 0xc1,
204 0xc8, 0xc9, 0xca, 0xcd, 0xd2, 0xd5, 0xda, 0xdb,
205 0xee, 0xf0, 0xf2, 0xf3, 0xff, 0xcb, 0xcc, 0xd3,
206 0xd4, 0xd6, 0xdd, 0xde, 0xdf, 0xf1, 0xf4, 0xf5,
207 0xf6, 0xf7, 0xf8, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe,
208 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0b,
209 0x0c, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14,
210 0x15, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d,
211 0x1e, 0x1f, 0x7f, 0xdc, 0xf9, 0x0a, 0x0d, 0x16,
212 };
213 // clang-format on
214
215 constexpr size_t kShortCodeTableSize = 124;
216 struct ShortCodeInfo {
217 uint8_t symbol;
218 uint8_t length;
219 } kShortCodeTable[kShortCodeTableSize] = {
220 {0x30, 5}, // Match: 0b0000000, Symbol: 0
221 {0x30, 5}, // Match: 0b0000001, Symbol: 0
222 {0x30, 5}, // Match: 0b0000010, Symbol: 0
223 {0x30, 5}, // Match: 0b0000011, Symbol: 0
224 {0x31, 5}, // Match: 0b0000100, Symbol: 1
225 {0x31, 5}, // Match: 0b0000101, Symbol: 1
226 {0x31, 5}, // Match: 0b0000110, Symbol: 1
227 {0x31, 5}, // Match: 0b0000111, Symbol: 1
228 {0x32, 5}, // Match: 0b0001000, Symbol: 2
229 {0x32, 5}, // Match: 0b0001001, Symbol: 2
230 {0x32, 5}, // Match: 0b0001010, Symbol: 2
231 {0x32, 5}, // Match: 0b0001011, Symbol: 2
232 {0x61, 5}, // Match: 0b0001100, Symbol: a
233 {0x61, 5}, // Match: 0b0001101, Symbol: a
234 {0x61, 5}, // Match: 0b0001110, Symbol: a
235 {0x61, 5}, // Match: 0b0001111, Symbol: a
236 {0x63, 5}, // Match: 0b0010000, Symbol: c
237 {0x63, 5}, // Match: 0b0010001, Symbol: c
238 {0x63, 5}, // Match: 0b0010010, Symbol: c
239 {0x63, 5}, // Match: 0b0010011, Symbol: c
240 {0x65, 5}, // Match: 0b0010100, Symbol: e
241 {0x65, 5}, // Match: 0b0010101, Symbol: e
242 {0x65, 5}, // Match: 0b0010110, Symbol: e
243 {0x65, 5}, // Match: 0b0010111, Symbol: e
244 {0x69, 5}, // Match: 0b0011000, Symbol: i
245 {0x69, 5}, // Match: 0b0011001, Symbol: i
246 {0x69, 5}, // Match: 0b0011010, Symbol: i
247 {0x69, 5}, // Match: 0b0011011, Symbol: i
248 {0x6f, 5}, // Match: 0b0011100, Symbol: o
249 {0x6f, 5}, // Match: 0b0011101, Symbol: o
250 {0x6f, 5}, // Match: 0b0011110, Symbol: o
251 {0x6f, 5}, // Match: 0b0011111, Symbol: o
252 {0x73, 5}, // Match: 0b0100000, Symbol: s
253 {0x73, 5}, // Match: 0b0100001, Symbol: s
254 {0x73, 5}, // Match: 0b0100010, Symbol: s
255 {0x73, 5}, // Match: 0b0100011, Symbol: s
256 {0x74, 5}, // Match: 0b0100100, Symbol: t
257 {0x74, 5}, // Match: 0b0100101, Symbol: t
258 {0x74, 5}, // Match: 0b0100110, Symbol: t
259 {0x74, 5}, // Match: 0b0100111, Symbol: t
260 {0x20, 6}, // Match: 0b0101000, Symbol: (space)
261 {0x20, 6}, // Match: 0b0101001, Symbol: (space)
262 {0x25, 6}, // Match: 0b0101010, Symbol: %
263 {0x25, 6}, // Match: 0b0101011, Symbol: %
264 {0x2d, 6}, // Match: 0b0101100, Symbol: -
265 {0x2d, 6}, // Match: 0b0101101, Symbol: -
266 {0x2e, 6}, // Match: 0b0101110, Symbol: .
267 {0x2e, 6}, // Match: 0b0101111, Symbol: .
268 {0x2f, 6}, // Match: 0b0110000, Symbol: /
269 {0x2f, 6}, // Match: 0b0110001, Symbol: /
270 {0x33, 6}, // Match: 0b0110010, Symbol: 3
271 {0x33, 6}, // Match: 0b0110011, Symbol: 3
272 {0x34, 6}, // Match: 0b0110100, Symbol: 4
273 {0x34, 6}, // Match: 0b0110101, Symbol: 4
274 {0x35, 6}, // Match: 0b0110110, Symbol: 5
275 {0x35, 6}, // Match: 0b0110111, Symbol: 5
276 {0x36, 6}, // Match: 0b0111000, Symbol: 6
277 {0x36, 6}, // Match: 0b0111001, Symbol: 6
278 {0x37, 6}, // Match: 0b0111010, Symbol: 7
279 {0x37, 6}, // Match: 0b0111011, Symbol: 7
280 {0x38, 6}, // Match: 0b0111100, Symbol: 8
281 {0x38, 6}, // Match: 0b0111101, Symbol: 8
282 {0x39, 6}, // Match: 0b0111110, Symbol: 9
283 {0x39, 6}, // Match: 0b0111111, Symbol: 9
284 {0x3d, 6}, // Match: 0b1000000, Symbol: =
285 {0x3d, 6}, // Match: 0b1000001, Symbol: =
286 {0x41, 6}, // Match: 0b1000010, Symbol: A
287 {0x41, 6}, // Match: 0b1000011, Symbol: A
288 {0x5f, 6}, // Match: 0b1000100, Symbol: _
289 {0x5f, 6}, // Match: 0b1000101, Symbol: _
290 {0x62, 6}, // Match: 0b1000110, Symbol: b
291 {0x62, 6}, // Match: 0b1000111, Symbol: b
292 {0x64, 6}, // Match: 0b1001000, Symbol: d
293 {0x64, 6}, // Match: 0b1001001, Symbol: d
294 {0x66, 6}, // Match: 0b1001010, Symbol: f
295 {0x66, 6}, // Match: 0b1001011, Symbol: f
296 {0x67, 6}, // Match: 0b1001100, Symbol: g
297 {0x67, 6}, // Match: 0b1001101, Symbol: g
298 {0x68, 6}, // Match: 0b1001110, Symbol: h
299 {0x68, 6}, // Match: 0b1001111, Symbol: h
300 {0x6c, 6}, // Match: 0b1010000, Symbol: l
301 {0x6c, 6}, // Match: 0b1010001, Symbol: l
302 {0x6d, 6}, // Match: 0b1010010, Symbol: m
303 {0x6d, 6}, // Match: 0b1010011, Symbol: m
304 {0x6e, 6}, // Match: 0b1010100, Symbol: n
305 {0x6e, 6}, // Match: 0b1010101, Symbol: n
306 {0x70, 6}, // Match: 0b1010110, Symbol: p
307 {0x70, 6}, // Match: 0b1010111, Symbol: p
308 {0x72, 6}, // Match: 0b1011000, Symbol: r
309 {0x72, 6}, // Match: 0b1011001, Symbol: r
310 {0x75, 6}, // Match: 0b1011010, Symbol: u
311 {0x75, 6}, // Match: 0b1011011, Symbol: u
312 {0x3a, 7}, // Match: 0b1011100, Symbol: :
313 {0x42, 7}, // Match: 0b1011101, Symbol: B
314 {0x43, 7}, // Match: 0b1011110, Symbol: C
315 {0x44, 7}, // Match: 0b1011111, Symbol: D
316 {0x45, 7}, // Match: 0b1100000, Symbol: E
317 {0x46, 7}, // Match: 0b1100001, Symbol: F
318 {0x47, 7}, // Match: 0b1100010, Symbol: G
319 {0x48, 7}, // Match: 0b1100011, Symbol: H
320 {0x49, 7}, // Match: 0b1100100, Symbol: I
321 {0x4a, 7}, // Match: 0b1100101, Symbol: J
322 {0x4b, 7}, // Match: 0b1100110, Symbol: K
323 {0x4c, 7}, // Match: 0b1100111, Symbol: L
324 {0x4d, 7}, // Match: 0b1101000, Symbol: M
325 {0x4e, 7}, // Match: 0b1101001, Symbol: N
326 {0x4f, 7}, // Match: 0b1101010, Symbol: O
327 {0x50, 7}, // Match: 0b1101011, Symbol: P
328 {0x51, 7}, // Match: 0b1101100, Symbol: Q
329 {0x52, 7}, // Match: 0b1101101, Symbol: R
330 {0x53, 7}, // Match: 0b1101110, Symbol: S
331 {0x54, 7}, // Match: 0b1101111, Symbol: T
332 {0x55, 7}, // Match: 0b1110000, Symbol: U
333 {0x56, 7}, // Match: 0b1110001, Symbol: V
334 {0x57, 7}, // Match: 0b1110010, Symbol: W
335 {0x59, 7}, // Match: 0b1110011, Symbol: Y
336 {0x6a, 7}, // Match: 0b1110100, Symbol: j
337 {0x6b, 7}, // Match: 0b1110101, Symbol: k
338 {0x71, 7}, // Match: 0b1110110, Symbol: q
339 {0x76, 7}, // Match: 0b1110111, Symbol: v
340 {0x77, 7}, // Match: 0b1111000, Symbol: w
341 {0x78, 7}, // Match: 0b1111001, Symbol: x
342 {0x79, 7}, // Match: 0b1111010, Symbol: y
343 {0x7a, 7}, // Match: 0b1111011, Symbol: z
344 };
345
346 } // namespace
347
HuffmanBitBuffer()348 HuffmanBitBuffer::HuffmanBitBuffer() { Reset(); }
349
Reset()350 void HuffmanBitBuffer::Reset() {
351 accumulator_ = 0;
352 count_ = 0;
353 }
354
AppendBytes(absl::string_view input)355 size_t HuffmanBitBuffer::AppendBytes(absl::string_view input) {
356 HuffmanAccumulatorBitCount free_cnt = free_count();
357 size_t bytes_available = input.size();
358 if (free_cnt < 8 || bytes_available == 0) {
359 return 0;
360 }
361
362 // Top up |accumulator_| until there isn't room for a whole byte.
363 size_t bytes_used = 0;
364 auto* ptr = reinterpret_cast<const uint8_t*>(input.data());
365 do {
366 auto b = static_cast<HuffmanAccumulator>(*ptr++);
367 free_cnt -= 8;
368 accumulator_ |= (b << free_cnt);
369 ++bytes_used;
370 } while (free_cnt >= 8 && bytes_used < bytes_available);
371 count_ += (bytes_used * 8);
372 return bytes_used;
373 }
374
free_count() const375 HuffmanAccumulatorBitCount HuffmanBitBuffer::free_count() const {
376 return kHuffmanAccumulatorBitCount - count_;
377 }
378
ConsumeBits(HuffmanAccumulatorBitCount code_length)379 void HuffmanBitBuffer::ConsumeBits(HuffmanAccumulatorBitCount code_length) {
380 QUICHE_DCHECK_LE(code_length, count_);
381 accumulator_ <<= code_length;
382 count_ -= code_length;
383 }
384
InputProperlyTerminated() const385 bool HuffmanBitBuffer::InputProperlyTerminated() const {
386 auto cnt = count();
387 if (cnt < 8) {
388 if (cnt == 0) {
389 return true;
390 }
391 HuffmanAccumulator expected = ~(~HuffmanAccumulator() >> cnt);
392 // We expect all the bits below the high order |cnt| bits of accumulator_
393 // to be cleared as we perform left shift operations while decoding.
394 QUICHE_DCHECK_EQ(accumulator_ & ~expected, 0u)
395 << "\n expected: " << HuffmanAccumulatorBitSet(expected) << "\n "
396 << *this;
397 return accumulator_ == expected;
398 }
399 return false;
400 }
401
DebugString() const402 std::string HuffmanBitBuffer::DebugString() const {
403 std::stringstream ss;
404 ss << "{accumulator: " << HuffmanAccumulatorBitSet(accumulator_)
405 << "; count: " << count_ << "}";
406 return ss.str();
407 }
408
409 HpackHuffmanDecoder::HpackHuffmanDecoder() = default;
410
411 HpackHuffmanDecoder::~HpackHuffmanDecoder() = default;
412
Decode(absl::string_view input,std::string * output)413 bool HpackHuffmanDecoder::Decode(absl::string_view input, std::string* output) {
414 QUICHE_DVLOG(1) << "HpackHuffmanDecoder::Decode";
415
416 // Fill bit_buffer_ from input.
417 input.remove_prefix(bit_buffer_.AppendBytes(input));
418
419 while (true) {
420 QUICHE_DVLOG(3) << "Enter Decode Loop, bit_buffer_: " << bit_buffer_;
421 if (bit_buffer_.count() >= 7) {
422 // Get high 7 bits of the bit buffer, see if that contains a complete
423 // code of 5, 6 or 7 bits.
424 uint8_t short_code =
425 bit_buffer_.value() >> (kHuffmanAccumulatorBitCount - 7);
426 QUICHE_DCHECK_LT(short_code, 128);
427 if (short_code < kShortCodeTableSize) {
428 ShortCodeInfo info = kShortCodeTable[short_code];
429 bit_buffer_.ConsumeBits(info.length);
430 output->push_back(static_cast<char>(info.symbol));
431 continue;
432 }
433 // The code is more than 7 bits long. Use PrefixToInfo, etc. to decode
434 // longer codes.
435 } else {
436 // We may have (mostly) drained bit_buffer_. If we can top it up, try
437 // using the table decoder above.
438 size_t byte_count = bit_buffer_.AppendBytes(input);
439 if (byte_count > 0) {
440 input.remove_prefix(byte_count);
441 continue;
442 }
443 }
444
445 HuffmanCode code_prefix = bit_buffer_.value() >> kExtraAccumulatorBitCount;
446 QUICHE_DVLOG(3) << "code_prefix: " << HuffmanCodeBitSet(code_prefix);
447
448 PrefixInfo prefix_info = PrefixToInfo(code_prefix);
449 QUICHE_DVLOG(3) << "prefix_info: " << prefix_info;
450 QUICHE_DCHECK_LE(kMinCodeBitCount, prefix_info.code_length);
451 QUICHE_DCHECK_LE(prefix_info.code_length, kMaxCodeBitCount);
452
453 if (prefix_info.code_length <= bit_buffer_.count()) {
454 // We have enough bits for one code.
455 uint32_t canonical = prefix_info.DecodeToCanonical(code_prefix);
456 if (canonical < 256) {
457 // Valid code.
458 char c = kCanonicalToSymbol[canonical];
459 output->push_back(c);
460 bit_buffer_.ConsumeBits(prefix_info.code_length);
461 continue;
462 }
463 // Encoder is not supposed to explicity encode the EOS symbol.
464 QUICHE_DLOG(ERROR) << "EOS explicitly encoded!\n " << bit_buffer_ << "\n "
465 << prefix_info;
466 return false;
467 }
468 // bit_buffer_ doesn't have enough bits in it to decode the next symbol.
469 // Append to it as many bytes as are available AND fit.
470 size_t byte_count = bit_buffer_.AppendBytes(input);
471 if (byte_count == 0) {
472 QUICHE_DCHECK_EQ(input.size(), 0u);
473 return true;
474 }
475 input.remove_prefix(byte_count);
476 }
477 }
478
DebugString() const479 std::string HpackHuffmanDecoder::DebugString() const {
480 return bit_buffer_.DebugString();
481 }
482
483 } // namespace http2
484