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 #include "net/tools/huffman_trie/trie/trie_bit_buffer.h"
6
7 #include <bit>
8 #include <cstdint>
9 #include <ostream>
10
11 #include "base/check.h"
12 #include "net/tools/huffman_trie/bit_writer.h"
13
14 namespace net::huffman_trie {
15
16 TrieBitBuffer::TrieBitBuffer() = default;
17
18 TrieBitBuffer::~TrieBitBuffer() = default;
19
WriteBit(uint8_t bit)20 void TrieBitBuffer::WriteBit(uint8_t bit) {
21 current_byte_ |= bit << (7 - used_);
22 used_++;
23
24 if (used_ == 8) {
25 Flush();
26 }
27 }
28
WriteBits(uint32_t bits,uint8_t number_of_bits)29 void TrieBitBuffer::WriteBits(uint32_t bits, uint8_t number_of_bits) {
30 DCHECK(number_of_bits <= 32);
31 for (uint8_t i = 1; i <= number_of_bits; i++) {
32 uint8_t bit = 1 & (bits >> (number_of_bits - i));
33 WriteBit(bit);
34 }
35 }
36
WritePosition(uint32_t position,int32_t * last_position)37 void TrieBitBuffer::WritePosition(uint32_t position, int32_t* last_position) {
38 // NOTE: If either of these values are changed, the corresponding values in
39 // net::extras::PreloadDecoder::Decode must also be changed.
40 constexpr uint8_t kShortOffsetMaxLength = 7;
41 constexpr uint8_t kLongOffsetLengthLength = 4;
42 // The maximum number of lengths in the long form is
43 // 2^kLongOffsetLengthLength, which added to kShortOffsetMaxLength gives the
44 // maximum bit length for |position|.
45 constexpr uint8_t kMaxBitLength =
46 kShortOffsetMaxLength + (1 << kLongOffsetLengthLength);
47
48 if (*last_position != -1) {
49 int32_t delta = position - *last_position;
50 DCHECK(delta > 0) << "delta position is not positive.";
51
52 uint8_t number_of_bits = std::bit_width<uint32_t>(delta);
53 DCHECK(number_of_bits <= kMaxBitLength)
54 << "positive position delta too large.";
55
56 if (number_of_bits <= kShortOffsetMaxLength) {
57 WriteBits(0, 1);
58 WriteBits(delta, kShortOffsetMaxLength);
59 } else {
60 WriteBits(1, 1);
61 // The smallest length written when using the long offset form is one
62 // more than kShortOffsetMaxLength, and it is written as 0.
63 WriteBits(number_of_bits - kShortOffsetMaxLength - 1,
64 kLongOffsetLengthLength);
65 WriteBits(delta, number_of_bits);
66 }
67
68 *last_position = position;
69 return;
70 }
71
72 if (used_ != 0) {
73 Flush();
74 }
75
76 AppendPositionElement(position);
77
78 *last_position = position;
79 }
80
WriteChar(uint8_t byte,const HuffmanRepresentationTable & table,HuffmanBuilder * huffman_builder)81 void TrieBitBuffer::WriteChar(uint8_t byte,
82 const HuffmanRepresentationTable& table,
83 HuffmanBuilder* huffman_builder) {
84 HuffmanRepresentationTable::const_iterator item;
85 item = table.find(byte);
86 DCHECK(item != table.end());
87 if (huffman_builder) {
88 huffman_builder->RecordUsage(byte);
89 }
90 WriteBits(item->second.bits, item->second.number_of_bits);
91 }
92
WriteSize(size_t size)93 void TrieBitBuffer::WriteSize(size_t size) {
94 switch (size) {
95 case 0:
96 WriteBits(0b00, 2);
97 break;
98 case 1:
99 WriteBits(0b100, 3);
100 break;
101 case 2:
102 WriteBits(0b101, 3);
103 break;
104 case 3:
105 WriteBits(0b110, 3);
106 break;
107 default: {
108 WriteBit(size % 2);
109 for (size_t len = (size + 1) / 2; len > 0; --len) {
110 WriteBit(1);
111 }
112 WriteBit(0);
113 }
114 }
115 }
116
AppendBitsElement(uint8_t bits,uint8_t number_of_bits)117 void TrieBitBuffer::AppendBitsElement(uint8_t bits, uint8_t number_of_bits) {
118 BitsOrPosition element;
119 element.bits = current_byte_;
120 element.number_of_bits = used_;
121 elements_.push_back(element);
122 }
123
AppendPositionElement(uint32_t position)124 void TrieBitBuffer::AppendPositionElement(uint32_t position) {
125 BitsOrPosition element;
126 element.position = position;
127 element.number_of_bits = 0;
128 elements_.push_back(element);
129 }
130
WriteToBitWriter(BitWriter * writer)131 uint32_t TrieBitBuffer::WriteToBitWriter(BitWriter* writer) {
132 Flush();
133
134 uint32_t old_position = writer->position();
135 for (auto const& element : elements_) {
136 if (element.number_of_bits) {
137 writer->WriteBits(element.bits >> (8 - element.number_of_bits),
138 element.number_of_bits);
139 } else {
140 uint32_t current = old_position;
141 uint32_t target = element.position;
142 DCHECK(target < current) << "Reference is not backwards";
143 uint32_t delta = current - target;
144 uint8_t delta_number_of_bits = std::bit_width(delta);
145 DCHECK(delta_number_of_bits < 32) << "Delta too large";
146 writer->WriteBits(delta_number_of_bits, 5);
147 writer->WriteBits(delta, delta_number_of_bits);
148 }
149 }
150 return old_position;
151 }
152
Flush()153 void TrieBitBuffer::Flush() {
154 if (used_) {
155 AppendBitsElement(current_byte_, used_);
156
157 used_ = 0;
158 current_byte_ = 0;
159 }
160 }
161
162 } // namespace net::huffman_trie
163