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. |
11 // See also https://en.wikipedia.org/wiki/Canonical_Huffman_code for background | 11 // See also https://en.wikipedia.org/wiki/Canonical_Huffman_code for background |
12 // on canonical Huffman codes. | 12 // on canonical Huffman codes. |
13 // | 13 // |
14 // This decoder differs from that in .../spdy/hpack/hpack_huffman_table.cc | 14 // This decoder differs from that in .../spdy/chromium/hpack/hpack_huffman_table
.cc |
15 // as follows: | 15 // as follows: |
16 // 1) It decodes only the code described in RFC7541, where as the older | 16 // 1) It decodes only the code described in RFC7541, where as the older |
17 // implementation supported any canonical Huffman code provided at run | 17 // implementation supported any canonical Huffman code provided at run |
18 // time. | 18 // time. |
19 // 2) It uses a fixed amount of memory allocated at build time; it doesn't | 19 // 2) It uses a fixed amount of memory allocated at build time; it doesn't |
20 // construct a tree of of decoding tables based on an encoding | 20 // construct a tree of of decoding tables based on an encoding |
21 // table provided at run time. | 21 // table provided at run time. |
22 // 3) In benchmarks it runs from 10% to 70% faster, based on the length | 22 // 3) In benchmarks it runs from 10% to 70% faster, based on the length |
23 // of the strings (faster for longer strings). Some of the improvements | 23 // of the strings (faster for longer strings). Some of the improvements |
24 // could be back ported, but others are fundamental to the approach. | 24 // could be back ported, but others are fundamental to the approach. |
25 | 25 |
26 #include "net/spdy/hpack/hpack_huffman_decoder.h" | 26 #include "net/spdy/core/hpack/hpack_huffman_decoder.h" |
27 | 27 |
28 #include <bitset> | 28 #include <bitset> |
29 #include <limits> | 29 #include <limits> |
30 #include <utility> | 30 #include <utility> |
31 | 31 |
32 #include "base/logging.h" | 32 #include "base/logging.h" |
33 #include "net/spdy/hpack/hpack_input_stream.h" | 33 #include "net/spdy/core/hpack/hpack_input_stream.h" |
34 | 34 |
35 namespace net { | 35 namespace net { |
36 namespace { | 36 namespace { |
37 | 37 |
38 typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord; | 38 typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord; |
39 typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength; | 39 typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength; |
40 | 40 |
41 const HuffmanCodeLength kHuffmanWordLength = | 41 const HuffmanCodeLength kHuffmanWordLength = |
42 std::numeric_limits<HuffmanWord>::digits; | 42 std::numeric_limits<HuffmanWord>::digits; |
43 | 43 |
(...skipping 347 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
391 // Get some more bits for decoding (up to 8). |peeked_success| is true | 391 // Get some more bits for decoding (up to 8). |peeked_success| is true |
392 // if we got any bits. | 392 // if we got any bits. |
393 peeked_success = in->PeekBits(&bits_available, &bits); | 393 peeked_success = in->PeekBits(&bits_available, &bits); |
394 } | 394 } |
395 DLOG_IF(WARNING, (VLOG_IS_ON(2) && bits_available < 32 && !peeked_success)) | 395 DLOG_IF(WARNING, (VLOG_IS_ON(2) && bits_available < 32 && !peeked_success)) |
396 << "no more peeking possible"; | 396 << "no more peeking possible"; |
397 } | 397 } |
398 } | 398 } |
399 | 399 |
400 } // namespace net | 400 } // namespace net |
OLD | NEW |