1 // Copyright 2016 The Chromium Authors 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 NET_TOOLS_HUFFMAN_TRIE_TRIE_TRIE_BIT_BUFFER_H_ 6 #define NET_TOOLS_HUFFMAN_TRIE_TRIE_TRIE_BIT_BUFFER_H_ 7 8 #include <stdint.h> 9 10 #include <vector> 11 12 #include "net/tools/huffman_trie/huffman/huffman_builder.h" 13 14 namespace net::huffman_trie { 15 16 class BitWriter; 17 18 // TrieBitBuffer acts as a buffer for TrieWriter. It can be used to write bits, 19 // characters, and positions. The characters are stored as their 20 // HuffmanRepresentation. Positions are references to other locations in the 21 // trie. 22 class TrieBitBuffer { 23 public: 24 TrieBitBuffer(); 25 26 TrieBitBuffer(const TrieBitBuffer&) = delete; 27 TrieBitBuffer& operator=(const TrieBitBuffer&) = delete; 28 29 ~TrieBitBuffer(); 30 31 // Writes |bit| to the buffer. 32 void WriteBit(uint8_t bit); 33 34 // Writes the |number_of_bits| least-significant bits from |bits| to the 35 // buffer. 36 void WriteBits(uint32_t bits, uint8_t number_of_bits); 37 38 // Write a position to the buffer. Actually writes the difference between 39 // |position| and |*last_position|. |*last_position| will be updated to equal 40 // the input |position|. 41 void WritePosition(uint32_t position, int32_t* last_position); 42 43 // Writes the character in |byte| to the buffer using its Huffman 44 // representation in |table|. Optionally tracks usage of the character in 45 // |*huffman_builder|. 46 void WriteChar(uint8_t byte, 47 const HuffmanRepresentationTable& table, 48 HuffmanBuilder* huffman_builder); 49 50 // Writes a size_t |size| in a format that provides a compact representation 51 // for small values. This function's inverse is PreloadDecoder::DecodeSize. 52 void WriteSize(size_t size); 53 54 // Writes the entire buffer to |*writer|. Returns the position |*writer| was 55 // at before the buffer was written to it. 56 uint32_t WriteToBitWriter(BitWriter* writer); 57 58 // Appends the buffered bits in |current_byte_| to |elements_|. No padding 59 // will occur. 60 void Flush(); 61 62 private: 63 // Represents either the |number_of_bits| least-significant bits in |bits| or 64 // a position (offset) in the trie. 65 struct BitsOrPosition { 66 uint8_t bits; 67 uint8_t number_of_bits; 68 uint32_t position; 69 }; 70 71 // Append a new element to |elements_|. 72 void AppendBitsElement(uint8_t bits, uint8_t number_of_bits); 73 void AppendPositionElement(uint32_t position); 74 75 // Buffers bits until they fill a whole byte. 76 uint8_t current_byte_ = 0; 77 78 // The number of bits currently in |current_byte_|. 79 uint32_t used_ = 0; 80 81 std::vector<BitsOrPosition> elements_; 82 }; 83 84 } // namespace net::huffman_trie 85 86 #endif // NET_TOOLS_HUFFMAN_TRIE_TRIE_TRIE_BIT_BUFFER_H_ 87