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 #ifndef QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_ 6 #define QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_ 7 8 // HpackHuffmanDecoder is an incremental decoder of strings that have been 9 // encoded using the Huffman table defined in the HPACK spec. 10 // By incremental, we mean that the HpackHuffmanDecoder::Decode method does 11 // not require the entire string to be provided, and can instead decode the 12 // string as fragments of it become available (e.g. as HPACK block fragments 13 // are received for decoding by HpackEntryDecoder). 14 15 #include <stddef.h> 16 17 #include <cstdint> 18 #include <iosfwd> 19 #include <string> 20 21 #include "absl/strings/string_view.h" 22 #include "quiche/common/platform/api/quiche_export.h" 23 24 namespace http2 { 25 26 // HuffmanAccumulator is used to store bits during decoding, e.g. next N bits 27 // that have not yet been decoded, but have been extracted from the encoded 28 // string). An advantage of using a uint64 for the accumulator 29 // is that it has room for the bits of the longest code plus the bits of a full 30 // byte; that means that when adding more bits to the accumulator, it can always 31 // be done in whole bytes. For example, if we currently have 26 bits in the 32 // accumulator, and need more to decode the current symbol, we can add a whole 33 // byte to the accumulator, and not have to do juggling with adding 6 bits (to 34 // reach 30), and then keep track of the last two bits we've not been able to 35 // add to the accumulator. 36 typedef uint64_t HuffmanAccumulator; 37 typedef size_t HuffmanAccumulatorBitCount; 38 39 // HuffmanBitBuffer stores the leading edge of bits to be decoded. The high 40 // order bit of accumulator_ is the next bit to be decoded. 41 class QUICHE_EXPORT HuffmanBitBuffer { 42 public: 43 HuffmanBitBuffer(); 44 45 // Prepare for decoding a new Huffman encoded string. 46 void Reset(); 47 48 // Add as many whole bytes to the accumulator (accumulator_) as possible, 49 // returning the number of bytes added. 50 size_t AppendBytes(absl::string_view input); 51 52 // Get the bits of the accumulator. value()53 HuffmanAccumulator value() const { return accumulator_; } 54 55 // Number of bits of the encoded string that are in the accumulator 56 // (accumulator_). count()57 HuffmanAccumulatorBitCount count() const { return count_; } 58 59 // Are there no bits in the accumulator? IsEmpty()60 bool IsEmpty() const { return count_ == 0; } 61 62 // Number of additional bits that can be added to the accumulator. 63 HuffmanAccumulatorBitCount free_count() const; 64 65 // Consume the leading |code_length| bits of the accumulator. 66 void ConsumeBits(HuffmanAccumulatorBitCount code_length); 67 68 // Are the contents valid for the end of a Huffman encoded string? The RFC 69 // states that EOS (end-of-string) symbol must not be explicitly encoded in 70 // the bit stream, but any unused bits in the final byte must be set to the 71 // prefix of the EOS symbol, which is all 1 bits. So there can be at most 7 72 // such bits. 73 // Returns true if the bit buffer is empty, or contains at most 7 bits, all 74 // of them 1. Otherwise returns false. 75 bool InputProperlyTerminated() const; 76 77 std::string DebugString() const; 78 79 private: 80 HuffmanAccumulator accumulator_; 81 HuffmanAccumulatorBitCount count_; 82 }; 83 84 inline std::ostream& operator<<(std::ostream& out, const HuffmanBitBuffer& v) { 85 return out << v.DebugString(); 86 } 87 88 class QUICHE_EXPORT HpackHuffmanDecoder { 89 public: 90 HpackHuffmanDecoder(); 91 ~HpackHuffmanDecoder(); 92 93 // Prepare for decoding a new Huffman encoded string. Reset()94 void Reset() { bit_buffer_.Reset(); } 95 96 // Decode the portion of a HPACK Huffman encoded string that is in |input|, 97 // appending the decoded symbols into |*output|, stopping when more bits are 98 // needed to determine the next symbol, which/ means that the input has been 99 // drained, and also that the bit_buffer_ is empty or that the bits that are 100 // in it are not a whole symbol. 101 // If |input| is the start of a string, the caller must first call Reset. 102 // If |input| includes the end of the encoded string, the caller must call 103 // InputProperlyTerminated after Decode has returned true in order to 104 // determine if the encoded string was properly terminated. 105 // Returns false if something went wrong (e.g. the encoding contains the code 106 // EOS symbol). Otherwise returns true, in which case input has been fully 107 // decoded or buffered; in particular, if the low-order bit of the final byte 108 // of the input is not the last bit of an encoded symbol, then bit_buffer_ 109 // will contain the leading bits of the code for that symbol, but not the 110 // final bits of that code. 111 // Note that output should be empty, but that it is not cleared by Decode(). 112 bool Decode(absl::string_view input, std::string* output); 113 114 // Is what remains in the bit_buffer_ valid at the end of an encoded string? 115 // Call after passing the the final portion of a Huffman string to Decode, 116 // and getting true as the result. InputProperlyTerminated()117 bool InputProperlyTerminated() const { 118 return bit_buffer_.InputProperlyTerminated(); 119 } 120 121 std::string DebugString() const; 122 123 private: 124 HuffmanBitBuffer bit_buffer_; 125 }; 126 127 inline std::ostream& operator<<(std::ostream& out, 128 const HpackHuffmanDecoder& v) { 129 return out << v.DebugString(); 130 } 131 132 } // namespace http2 133 134 #endif // QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_ 135