Coverage Report

Created: 2024-09-08 07:14

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