Debian Codegraph @

lib/jxl/jpeg/enc_jpeg_huffman_decode.cc

raw
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/jxl/jpeg/enc_jpeg_huffman_decode.h"
7
8 #include "lib/jxl/jpeg/jpeg_data.h"
9
10 namespace jxl {
11 namespace jpeg {
12
13 // Returns the table width of the next 2nd level table, count is the histogram
14 // of bit lengths for the remaining symbols, len is the code length of the next
15 // processed symbol.
16 static inline int NextTableBitSize(const int* count, int len) {
17 int left = 1 << (len - kJpegHuffmanRootTableBits);
18 while (len < static_cast<int>(kJpegHuffmanMaxBitLength)) {
19 left -= count[len];
20 if (left <= 0) break;
21 ++len;
22 left <<= 1;
23 }
24 return len - kJpegHuffmanRootTableBits;
25 }
26
27 void BuildJpegHuffmanTable(const uint32_t* count, const uint32_t* symbols,
28 HuffmanTableEntry* lut) {
29 HuffmanTableEntry code; // current table entry
30 HuffmanTableEntry* table; // next available space in table
31 int len; // current code length
32 int idx; // symbol index
33 int key; // prefix code
34 int reps; // number of replicate key values in current table
35 int low; // low bits for current root entry
36 int table_bits; // key length of current table
37 int table_size; // size of current table
38
39 // Make a local copy of the input bit length histogram.
40 int tmp_count[kJpegHuffmanMaxBitLength + 1] = {0};
41 int total_count = 0;
42 for (len = 1; len <= static_cast<int>(kJpegHuffmanMaxBitLength); ++len) {
43 tmp_count[len] = count[len];
44 total_count += tmp_count[len];
45 }
46
47 table = lut;
48 table_bits = kJpegHuffmanRootTableBits;
49 table_size = 1 << table_bits;
50
51 // Special case code with only one value.
52 if (total_count == 1) {
53 code.bits = 0;
54 code.value = symbols[0];
55 for (key = 0; key < table_size; ++key) {
56 table[key] = code;
57 }
58 return;
59 }
60
61 // Fill in root table.
62 key = 0;
63 idx = 0;
64 for (len = 1; len <= kJpegHuffmanRootTableBits; ++len) {
65 for (; tmp_count[len] > 0; --tmp_count[len]) {
66 code.bits = len;
67 code.value = symbols[idx++];
68 reps = 1 << (kJpegHuffmanRootTableBits - len);
69 while (reps--) {
70 table[key++] = code;
71 }
72 }
73 }
74
75 // Fill in 2nd level tables and add pointers to root table.
76 table += table_size;
77 table_size = 0;
78 low = 0;
79 for (len = kJpegHuffmanRootTableBits + 1;
80 len <= static_cast<int>(kJpegHuffmanMaxBitLength); ++len) {
81 for (; tmp_count[len] > 0; --tmp_count[len]) {
82 // Start a new sub-table if the previous one is full.
83 if (low >= table_size) {
84 table += table_size;
85 table_bits = NextTableBitSize(tmp_count, len);
86 table_size = 1 << table_bits;
87 low = 0;
88 lut[key].bits = table_bits + kJpegHuffmanRootTableBits;
89 lut[key].value = (table - lut) - key;
90 ++key;
91 }
92 code.bits = len - kJpegHuffmanRootTableBits;
93 code.value = symbols[idx++];
94 reps = 1 << (table_bits - code.bits);
95 while (reps--) {
96 table[low++] = code;
97 }
98 }
99 }
100 }
101
102 } // namespace jpeg
103 } // namespace jxl