/src/libjxl/lib/jpegli/huffman.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) the JPEG XL Project Authors. All rights reserved. |
2 | | // |
3 | | // Use of this source code is governed by a BSD-style |
4 | | // license that can be found in the LICENSE file. |
5 | | |
6 | | #include "lib/jpegli/huffman.h" |
7 | | |
8 | | #include <algorithm> |
9 | | #include <cstddef> |
10 | | #include <cstdint> |
11 | | #include <cstring> |
12 | | #include <limits> |
13 | | #include <vector> |
14 | | |
15 | | #include "lib/jpegli/common.h" |
16 | | #include "lib/jpegli/common_internal.h" |
17 | | #include "lib/jpegli/error.h" |
18 | | #include "lib/jxl/base/compiler_specific.h" |
19 | | #include "lib/jxl/base/status.h" |
20 | | |
21 | | namespace jpegli { |
22 | | |
23 | | // Returns the table width of the next 2nd level table, count is the histogram |
24 | | // of bit lengths for the remaining symbols, len is the code length of the next |
25 | | // processed symbol. |
26 | 30.3k | static inline int NextTableBitSize(const int* count, int len) { |
27 | 30.3k | int left = 1 << (len - kJpegHuffmanRootTableBits); |
28 | 67.4k | while (len < static_cast<int>(kJpegHuffmanMaxBitLength)) { |
29 | 62.0k | left -= count[len]; |
30 | 62.0k | if (left <= 0) break; |
31 | 37.0k | ++len; |
32 | 37.0k | left <<= 1; |
33 | 37.0k | } |
34 | 30.3k | return len - kJpegHuffmanRootTableBits; |
35 | 30.3k | } |
36 | | |
37 | | void BuildJpegHuffmanTable(const uint32_t* count, const uint32_t* symbols, |
38 | 10.6k | HuffmanTableEntry* lut) { |
39 | 10.6k | HuffmanTableEntry code; // current table entry |
40 | 10.6k | HuffmanTableEntry* table; // next available space in table |
41 | 10.6k | int len; // current code length |
42 | 10.6k | int idx; // symbol index |
43 | 10.6k | int key; // prefix code |
44 | 10.6k | int reps; // number of replicate key values in current table |
45 | 10.6k | int low; // low bits for current root entry |
46 | 10.6k | int table_bits; // key length of current table |
47 | 10.6k | int table_size; // size of current table |
48 | | |
49 | | // Make a local copy of the input bit length histogram. |
50 | 10.6k | int tmp_count[kJpegHuffmanMaxBitLength + 1] = {0}; |
51 | 10.6k | int total_count = 0; |
52 | 180k | for (len = 1; len <= static_cast<int>(kJpegHuffmanMaxBitLength); ++len) { |
53 | 170k | tmp_count[len] = count[len]; |
54 | 170k | total_count += tmp_count[len]; |
55 | 170k | } |
56 | | |
57 | 10.6k | table = lut; |
58 | 10.6k | table_bits = kJpegHuffmanRootTableBits; |
59 | 10.6k | table_size = 1 << table_bits; |
60 | | |
61 | | // Special case code with only one value. |
62 | 10.6k | if (total_count == 1) { |
63 | 64 | code.bits = 0; |
64 | 64 | code.value = symbols[0]; |
65 | 16.4k | for (key = 0; key < table_size; ++key) { |
66 | 16.3k | table[key] = code; |
67 | 16.3k | } |
68 | 64 | return; |
69 | 64 | } |
70 | | |
71 | | // Fill in root table. |
72 | 10.5k | key = 0; |
73 | 10.5k | idx = 0; |
74 | 95.0k | for (len = 1; len <= kJpegHuffmanRootTableBits; ++len) { |
75 | 225k | for (; tmp_count[len] > 0; --tmp_count[len]) { |
76 | 141k | code.bits = len; |
77 | 141k | code.value = symbols[idx++]; |
78 | 141k | reps = 1 << (kJpegHuffmanRootTableBits - len); |
79 | 2.73M | while (reps--) { |
80 | 2.59M | table[key++] = code; |
81 | 2.59M | } |
82 | 141k | } |
83 | 84.5k | } |
84 | | |
85 | | // Fill in 2nd level tables and add pointers to root table. |
86 | 10.5k | table += table_size; |
87 | 10.5k | table_size = 0; |
88 | 10.5k | low = 0; |
89 | 10.5k | for (len = kJpegHuffmanRootTableBits + 1; |
90 | 95.0k | len <= static_cast<int>(kJpegHuffmanMaxBitLength); ++len) { |
91 | 787k | for (; tmp_count[len] > 0; --tmp_count[len]) { |
92 | | // Start a new sub-table if the previous one is full. |
93 | 703k | if (low >= table_size) { |
94 | 30.3k | table += table_size; |
95 | 30.3k | table_bits = NextTableBitSize(tmp_count, len); |
96 | 30.3k | table_size = 1 << table_bits; |
97 | 30.3k | low = 0; |
98 | 30.3k | lut[key].bits = table_bits + kJpegHuffmanRootTableBits; |
99 | 30.3k | lut[key].value = (table - lut) - key; |
100 | 30.3k | ++key; |
101 | 30.3k | } |
102 | 703k | code.bits = len - kJpegHuffmanRootTableBits; |
103 | 703k | code.value = symbols[idx++]; |
104 | 703k | reps = 1 << (table_bits - code.bits); |
105 | 2.05M | while (reps--) { |
106 | 1.35M | table[low++] = code; |
107 | 1.35M | } |
108 | 703k | } |
109 | 84.5k | } |
110 | 10.5k | } |
111 | | |
112 | | // A node of a Huffman tree. |
113 | | struct HuffmanTree { |
114 | | HuffmanTree(uint32_t count, int16_t left, int16_t right) |
115 | 0 | : total_count(count), index_left(left), index_right_or_value(right) {} |
116 | | uint32_t total_count; |
117 | | int16_t index_left; |
118 | | int16_t index_right_or_value; |
119 | | }; |
120 | | |
121 | | void SetDepth(const HuffmanTree& p, HuffmanTree* pool, uint8_t* depth, |
122 | 0 | uint8_t level) { |
123 | 0 | if (p.index_left >= 0) { |
124 | 0 | ++level; |
125 | 0 | SetDepth(pool[p.index_left], pool, depth, level); |
126 | 0 | SetDepth(pool[p.index_right_or_value], pool, depth, level); |
127 | 0 | } else { |
128 | 0 | depth[p.index_right_or_value] = level; |
129 | 0 | } |
130 | 0 | } |
131 | | |
132 | | // Compare the root nodes, least popular first; indices are in decreasing order |
133 | | // before sorting is applied. |
134 | 0 | static JXL_INLINE bool Compare(const HuffmanTree& v0, const HuffmanTree& v1) { |
135 | 0 | return v0.total_count != v1.total_count |
136 | 0 | ? v0.total_count < v1.total_count |
137 | 0 | : v0.index_right_or_value > v1.index_right_or_value; |
138 | 0 | } |
139 | | |
140 | | // This function will create a Huffman tree. |
141 | | // |
142 | | // The catch here is that the tree cannot be arbitrarily deep. |
143 | | // Brotli specifies a maximum depth of 15 bits for "code trees" |
144 | | // and 7 bits for "code length code trees." |
145 | | // |
146 | | // count_limit is the value that is to be faked as the minimum value |
147 | | // and this minimum value is raised until the tree matches the |
148 | | // maximum length requirement. |
149 | | // |
150 | | // This algorithm is not of excellent performance for very long data blocks, |
151 | | // especially when population counts are longer than 2**tree_limit, but |
152 | | // we are not planning to use this with extremely long blocks. |
153 | | // |
154 | | // See http://en.wikipedia.org/wiki/Huffman_coding |
155 | | void CreateHuffmanTree(const uint32_t* data, const size_t length, |
156 | 0 | const int tree_limit, uint8_t* depth) { |
157 | | // For block sizes below 64 kB, we never need to do a second iteration |
158 | | // of this loop. Probably all of our block sizes will be smaller than |
159 | | // that, so this loop is mostly of academic interest. If we actually |
160 | | // would need this, we would be better off with the Katajainen algorithm. |
161 | 0 | for (uint32_t count_limit = 1;; count_limit *= 2) { |
162 | 0 | std::vector<HuffmanTree> tree; |
163 | 0 | tree.reserve(2 * length + 1); |
164 | |
|
165 | 0 | for (size_t i = length; i != 0;) { |
166 | 0 | --i; |
167 | 0 | if (data[i]) { |
168 | 0 | const uint32_t count = std::max(data[i], count_limit - 1); |
169 | 0 | tree.emplace_back(count, -1, static_cast<int16_t>(i)); |
170 | 0 | } |
171 | 0 | } |
172 | |
|
173 | 0 | const size_t n = tree.size(); |
174 | 0 | if (n == 1) { |
175 | | // Fake value; will be fixed on upper level. |
176 | 0 | depth[tree[0].index_right_or_value] = 1; |
177 | 0 | break; |
178 | 0 | } |
179 | | |
180 | 0 | std::sort(tree.begin(), tree.end(), Compare); |
181 | | |
182 | | // The nodes are: |
183 | | // [0, n): the sorted leaf nodes that we start with. |
184 | | // [n]: we add a sentinel here. |
185 | | // [n + 1, 2n): new parent nodes are added here, starting from |
186 | | // (n+1). These are naturally in ascending order. |
187 | | // [2n]: we add a sentinel at the end as well. |
188 | | // There will be (2n+1) elements at the end. |
189 | 0 | const HuffmanTree sentinel(std::numeric_limits<uint32_t>::max(), -1, -1); |
190 | 0 | tree.push_back(sentinel); |
191 | 0 | tree.push_back(sentinel); |
192 | |
|
193 | 0 | size_t i = 0; // Points to the next leaf node. |
194 | 0 | size_t j = n + 1; // Points to the next non-leaf node. |
195 | 0 | for (size_t k = n - 1; k != 0; --k) { |
196 | 0 | size_t left; |
197 | 0 | size_t right; |
198 | 0 | if (tree[i].total_count <= tree[j].total_count) { |
199 | 0 | left = i; |
200 | 0 | ++i; |
201 | 0 | } else { |
202 | 0 | left = j; |
203 | 0 | ++j; |
204 | 0 | } |
205 | 0 | if (tree[i].total_count <= tree[j].total_count) { |
206 | 0 | right = i; |
207 | 0 | ++i; |
208 | 0 | } else { |
209 | 0 | right = j; |
210 | 0 | ++j; |
211 | 0 | } |
212 | | |
213 | | // The sentinel node becomes the parent node. |
214 | 0 | size_t j_end = tree.size() - 1; |
215 | 0 | tree[j_end].total_count = |
216 | 0 | tree[left].total_count + tree[right].total_count; |
217 | 0 | tree[j_end].index_left = static_cast<int16_t>(left); |
218 | 0 | tree[j_end].index_right_or_value = static_cast<int16_t>(right); |
219 | | |
220 | | // Add back the last sentinel node. |
221 | 0 | tree.push_back(sentinel); |
222 | 0 | } |
223 | 0 | JXL_DASSERT(tree.size() == 2 * n + 1); |
224 | 0 | SetDepth(tree[2 * n - 1], tree.data(), depth, 0); |
225 | | |
226 | | // We need to pack the Huffman tree in tree_limit bits. |
227 | | // If this was not successful, add fake entities to the lowest values |
228 | | // and retry. |
229 | 0 | if (*std::max_element(&depth[0], &depth[length]) <= tree_limit) { |
230 | 0 | break; |
231 | 0 | } |
232 | 0 | } |
233 | 0 | } |
234 | | |
235 | | void ValidateHuffmanTable(j_common_ptr cinfo, const JHUFF_TBL* table, |
236 | 12.9k | bool is_dc) { |
237 | 12.9k | size_t total_symbols = 0; |
238 | 12.9k | size_t total_p = 0; |
239 | 12.9k | size_t max_depth = 0; |
240 | 220k | for (size_t d = 1; d <= kJpegHuffmanMaxBitLength; ++d) { |
241 | 207k | uint8_t count = table->bits[d]; |
242 | 207k | if (count) { |
243 | 145k | total_symbols += count; |
244 | 145k | total_p += (1u << (kJpegHuffmanMaxBitLength - d)) * count; |
245 | 145k | max_depth = d; |
246 | 145k | } |
247 | 207k | } |
248 | 12.9k | total_p += 1u << (kJpegHuffmanMaxBitLength - max_depth); // sentinel symbol |
249 | 12.9k | if (total_symbols == 0) { |
250 | 0 | JPEGLI_ERROR("Empty Huffman table"); |
251 | 0 | } |
252 | 12.9k | if (total_symbols > kJpegHuffmanAlphabetSize) { |
253 | 0 | JPEGLI_ERROR("Too many symbols in Huffman table"); |
254 | 0 | } |
255 | 12.9k | if (total_p != (1u << kJpegHuffmanMaxBitLength)) { |
256 | 0 | JPEGLI_ERROR("Invalid bit length distribution"); |
257 | 0 | } |
258 | 12.9k | uint8_t symbol_seen[kJpegHuffmanAlphabetSize] = {}; |
259 | 1.12M | for (size_t i = 0; i < total_symbols; ++i) { |
260 | 1.10M | uint8_t symbol = table->huffval[i]; |
261 | 1.10M | if (symbol_seen[symbol]) { |
262 | 0 | JPEGLI_ERROR("Duplicate symbol %d in Huffman table", symbol); |
263 | 0 | } |
264 | 1.10M | symbol_seen[symbol] = 1; |
265 | 1.10M | } |
266 | 12.9k | } |
267 | | |
268 | 12.0k | void AddStandardHuffmanTables(j_common_ptr cinfo, bool is_dc) { |
269 | | // Huffman tables from the JPEG standard. |
270 | 12.0k | static constexpr JHUFF_TBL kStandardDCTables[2] = { |
271 | | // DC luma |
272 | 12.0k | {{0, 0, 1, 5, 1, 1, 1, 1, 1, 1}, |
273 | 12.0k | {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, |
274 | 12.0k | FALSE}, |
275 | | // DC chroma |
276 | 12.0k | {{0, 0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1}, |
277 | 12.0k | {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, |
278 | 12.0k | FALSE}}; |
279 | 12.0k | static constexpr JHUFF_TBL kStandardACTables[2] = { |
280 | | // AC luma |
281 | 12.0k | {{0, 0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 125}, |
282 | 12.0k | {0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12, 0x21, 0x31, 0x41, 0x06, |
283 | 12.0k | 0x13, 0x51, 0x61, 0x07, 0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08, |
284 | 12.0k | 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52, 0xd1, 0xf0, 0x24, 0x33, 0x62, 0x72, |
285 | 12.0k | 0x82, 0x09, 0x0a, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28, |
286 | 12.0k | 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44, 0x45, |
287 | 12.0k | 0x46, 0x47, 0x48, 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, |
288 | 12.0k | 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x73, 0x74, 0x75, |
289 | 12.0k | 0x76, 0x77, 0x78, 0x79, 0x7a, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, |
290 | 12.0k | 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3, |
291 | 12.0k | 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, |
292 | 12.0k | 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, |
293 | 12.0k | 0xca, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2, |
294 | 12.0k | 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xf1, 0xf2, 0xf3, 0xf4, |
295 | 12.0k | 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa}, |
296 | 12.0k | FALSE}, |
297 | | // AC chroma |
298 | 12.0k | {{0, 0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 119}, |
299 | 12.0k | {0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21, 0x31, 0x06, 0x12, 0x41, |
300 | 12.0k | 0x51, 0x07, 0x61, 0x71, 0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91, |
301 | 12.0k | 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33, 0x52, 0xf0, 0x15, 0x62, 0x72, 0xd1, |
302 | 12.0k | 0x0a, 0x16, 0x24, 0x34, 0xe1, 0x25, 0xf1, 0x17, 0x18, 0x19, 0x1a, 0x26, |
303 | 12.0k | 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44, |
304 | 12.0k | 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, |
305 | 12.0k | 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x73, 0x74, |
306 | 12.0k | 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, |
307 | 12.0k | 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, |
308 | 12.0k | 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, |
309 | 12.0k | 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, |
310 | 12.0k | 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, |
311 | 12.0k | 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xf2, 0xf3, 0xf4, |
312 | 12.0k | 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa}, |
313 | 12.0k | FALSE}}; |
314 | 12.0k | const JHUFF_TBL* std_tables = is_dc ? kStandardDCTables : kStandardACTables; |
315 | 12.0k | JHUFF_TBL** tables; |
316 | 12.0k | if (cinfo->is_decompressor) { |
317 | 12.0k | j_decompress_ptr cinfo_d = reinterpret_cast<j_decompress_ptr>(cinfo); |
318 | 12.0k | tables = is_dc ? cinfo_d->dc_huff_tbl_ptrs : cinfo_d->ac_huff_tbl_ptrs; |
319 | 12.0k | } else { |
320 | 0 | j_compress_ptr cinfo_c = reinterpret_cast<j_compress_ptr>(cinfo); |
321 | 0 | tables = is_dc ? cinfo_c->dc_huff_tbl_ptrs : cinfo_c->ac_huff_tbl_ptrs; |
322 | 0 | } |
323 | 36.1k | for (int i = 0; i < 2; ++i) { |
324 | 24.0k | if (tables[i] == nullptr) { |
325 | 12.9k | tables[i] = jpegli_alloc_huff_table(cinfo); |
326 | 12.9k | memcpy(tables[i], &std_tables[i], sizeof(JHUFF_TBL)); |
327 | 12.9k | ValidateHuffmanTable(cinfo, tables[i], is_dc); |
328 | 12.9k | } |
329 | 24.0k | } |
330 | 12.0k | } |
331 | | |
332 | | } // namespace jpegli |