| 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 |