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 140 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
151 0xee, 0xf0, 0xf2, 0xf3, 0xff, 0xcb, 0xcc, 0xd3, | 151 0xee, 0xf0, 0xf2, 0xf3, 0xff, 0xcb, 0xcc, 0xd3, |
152 0xd4, 0xd6, 0xdd, 0xde, 0xdf, 0xf1, 0xf4, 0xf5, | 152 0xd4, 0xd6, 0xdd, 0xde, 0xdf, 0xf1, 0xf4, 0xf5, |
153 0xf6, 0xf7, 0xf8, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, | 153 0xf6, 0xf7, 0xf8, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, |
154 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0b, | 154 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0b, |
155 0x0c, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, | 155 0x0c, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, |
156 0x15, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, | 156 0x15, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, |
157 0x1e, 0x1f, 0x7f, 0xdc, 0xf9, 0x0a, 0x0d, 0x16, | 157 0x1e, 0x1f, 0x7f, 0xdc, 0xf9, 0x0a, 0x0d, 0x16, |
158 }; | 158 }; |
159 // clang-format on | 159 // clang-format on |
160 | 160 |
161 #ifndef NDEBUG | 161 #if !defined(NDEBUG) || defined(DCHECK_ALWAYS_ON) |
162 | 162 |
163 // Only used in DLOG. | 163 // Only used in DLOG. |
164 bool IsEOSPrefix(HuffmanWord bits, HuffmanCodeLength bits_available) { | 164 bool IsEOSPrefix(HuffmanWord bits, HuffmanCodeLength bits_available) { |
165 if (bits_available == 0) { | 165 if (bits_available == 0) { |
166 return true; | 166 return true; |
167 } | 167 } |
168 // We expect all the bits below the high order |bits_available| bits | 168 // We expect all the bits below the high order |bits_available| bits |
169 // to be cleared. | 169 // to be cleared. |
170 HuffmanWord expected = HuffmanWord(0xffffffff) << (32 - bits_available); | 170 HuffmanWord expected = HuffmanWord(0xffffffff) << (32 - bits_available); |
171 return bits == expected; | 171 return bits == expected; |
172 } | 172 } |
173 | 173 |
174 #endif // NDEBUG | 174 #endif // NDEBUG && !defined(DCHECK_ALWAYS_ON) |
175 | 175 |
176 } // namespace | 176 } // namespace |
177 | 177 |
178 // TODO(jamessynge): Should we read these magic numbers from | 178 // TODO(jamessynge): Should we read these magic numbers from |
179 // kLengthToFirstLJCode? Would that reduce cache consumption? Slow decoding? | 179 // kLengthToFirstLJCode? Would that reduce cache consumption? Slow decoding? |
180 // TODO(jamessynge): Is this being inlined by the compiler? Should we inline | 180 // TODO(jamessynge): Is this being inlined by the compiler? Should we inline |
181 // into DecodeString the tests for code lengths 5 through 8 (> 99% of codes | 181 // into DecodeString the tests for code lengths 5 through 8 (> 99% of codes |
182 // according to the HPACK spec)? | 182 // according to the HPACK spec)? |
183 HpackHuffmanDecoder::HuffmanCodeLength HpackHuffmanDecoder::CodeLengthOfPrefix( | 183 HpackHuffmanDecoder::HuffmanCodeLength HpackHuffmanDecoder::CodeLengthOfPrefix( |
184 HpackHuffmanDecoder::HuffmanWord value) { | 184 HpackHuffmanDecoder::HuffmanWord value) { |
(...skipping 216 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
401 // Get some more bits for decoding (up to 8). |peeked_success| is true | 401 // Get some more bits for decoding (up to 8). |peeked_success| is true |
402 // if we got any bits. | 402 // if we got any bits. |
403 peeked_success = in->PeekBits(&bits_available, &bits); | 403 peeked_success = in->PeekBits(&bits_available, &bits); |
404 } | 404 } |
405 DLOG_IF(WARNING, (VLOG_IS_ON(1) && bits_available < 32 && !peeked_success)) | 405 DLOG_IF(WARNING, (VLOG_IS_ON(1) && bits_available < 32 && !peeked_success)) |
406 << "no more peeking possible"; | 406 << "no more peeking possible"; |
407 } | 407 } |
408 } | 408 } |
409 | 409 |
410 } // namespace net | 410 } // namespace net |
OLD | NEW |