| 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 |