OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 // | 4 // |
5 // Decoder for strings encoded using the HPACK Huffman Code (see | 5 // Decoder for strings encoded using the HPACK Huffman Code (see |
6 // https://httpwg.github.io/specs/rfc7541.html#huffman.code). | 6 // https://httpwg.github.io/specs/rfc7541.html#huffman.code). |
7 // | 7 // |
8 // This implementation is inspired by the One-Shift algorithm described in | 8 // This implementation is inspired by the One-Shift algorithm described in |
9 // "On the Implementation of Minimum Redundancy Prefix Codes", by Alistair | 9 // "On the Implementation of Minimum Redundancy Prefix Codes", by Alistair |
10 // Moffat and Andrew Turpin, 1997. | 10 // Moffat and Andrew Turpin, 1997. |
(...skipping 286 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
297 return static_cast<char>(kCanonicalToSymbol[canonical]); | 297 return static_cast<char>(kCanonicalToSymbol[canonical]); |
298 } | 298 } |
299 | 299 |
300 // TODO(jamessynge): Maybe further refactorings, including just passing in a | 300 // TODO(jamessynge): Maybe further refactorings, including just passing in a |
301 // StringPiece instead of an HpackInputStream, thus avoiding the PeekBits calls, | 301 // StringPiece instead of an HpackInputStream, thus avoiding the PeekBits calls, |
302 // and also allowing us to separate the code into portions dealing with long | 302 // and also allowing us to separate the code into portions dealing with long |
303 // strings, and a later portion dealing with the last few bytes of strings. | 303 // strings, and a later portion dealing with the last few bytes of strings. |
304 // TODO(jamessynge): Determine if that is worth it by adding some counters to | 304 // TODO(jamessynge): Determine if that is worth it by adding some counters to |
305 // measure the distribution of string sizes seen in practice. | 305 // measure the distribution of string sizes seen in practice. |
306 bool HpackHuffmanDecoder::DecodeString(HpackInputStream* in, | 306 bool HpackHuffmanDecoder::DecodeString(HpackInputStream* in, |
307 size_t out_capacity, | |
308 std::string* out) { | 307 std::string* out) { |
309 out->clear(); | 308 out->clear(); |
310 | 309 |
311 // Load |bits| with the leading bits of the input stream, left justified | 310 // Load |bits| with the leading bits of the input stream, left justified |
312 // (i.e. the bits of the first byte are the high-order bits of |bits|, | 311 // (i.e. the bits of the first byte are the high-order bits of |bits|, |
313 // and the bits of the fourth byte are the low-order bits of |bits|). | 312 // and the bits of the fourth byte are the low-order bits of |bits|). |
314 // |peeked_success| if there are more bits in |*in| (i.e. the encoding | 313 // |peeked_success| if there are more bits in |*in| (i.e. the encoding |
315 // of the string to be decoded is more than 4 bytes). | 314 // of the string to be decoded is more than 4 bytes). |
316 | 315 |
317 auto bits_available_and_bits = in->InitializePeekBits(); | 316 auto bits_available_and_bits = in->InitializePeekBits(); |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
362 << " HasMoreData: " << in->HasMoreData(); | 361 << " HasMoreData: " << in->HasMoreData(); |
363 return !in->HasMoreData(); | 362 return !in->HasMoreData(); |
364 } | 363 } |
365 // We're dealing with a long code. It *might* be useful to add a special | 364 // We're dealing with a long code. It *might* be useful to add a special |
366 // method to HpackInputStream for getting more than "at most 8" bits | 365 // method to HpackInputStream for getting more than "at most 8" bits |
367 // at a time. | 366 // at a time. |
368 do { | 367 do { |
369 peeked_success = in->PeekBits(&bits_available, &bits); | 368 peeked_success = in->PeekBits(&bits_available, &bits); |
370 } while (peeked_success && bits_available < 32); | 369 } while (peeked_success && bits_available < 32); |
371 } else { | 370 } else { |
372 if (out->size() == out_capacity) { | |
373 // This code would cause us to overflow |out_capacity|. | |
374 // TODO(jamessynge) Avoid this case by pre-allocating out based on | |
375 // scaling up the encoded size by 8/5 (shortest codes are 5 bits). | |
376 DLOG(WARNING) << "Output size too large: " << out_capacity; | |
377 return false; | |
378 } | |
379 | |
380 // Convert from the prefix code of length |code_length| to the | 371 // Convert from the prefix code of length |code_length| to the |
381 // canonical symbol (i.e. where the input symbols (bytes) are ordered by | 372 // canonical symbol (i.e. where the input symbols (bytes) are ordered by |
382 // increasing code length and then by their increasing uint8 value). | 373 // increasing code length and then by their increasing uint8 value). |
383 HuffmanWord canonical = DecodeToCanonical(code_length, bits); | 374 HuffmanWord canonical = DecodeToCanonical(code_length, bits); |
384 | 375 |
385 bits = bits << code_length; | 376 bits = bits << code_length; |
386 bits_available -= code_length; | 377 bits_available -= code_length; |
387 in->ConsumeBits(code_length); | 378 in->ConsumeBits(code_length); |
388 | 379 |
389 if (canonical < 256) { | 380 if (canonical < 256) { |
(...skipping 11 matching lines...) Expand all Loading... |
401 // Get some more bits for decoding (up to 8). |peeked_success| is true | 392 // Get some more bits for decoding (up to 8). |peeked_success| is true |
402 // if we got any bits. | 393 // if we got any bits. |
403 peeked_success = in->PeekBits(&bits_available, &bits); | 394 peeked_success = in->PeekBits(&bits_available, &bits); |
404 } | 395 } |
405 DLOG_IF(WARNING, (VLOG_IS_ON(1) && bits_available < 32 && !peeked_success)) | 396 DLOG_IF(WARNING, (VLOG_IS_ON(1) && bits_available < 32 && !peeked_success)) |
406 << "no more peeking possible"; | 397 << "no more peeking possible"; |
407 } | 398 } |
408 } | 399 } |
409 | 400 |
410 } // namespace net | 401 } // namespace net |
OLD | NEW |