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