Coverage Report

Created: 2025-06-13 06:38

/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