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