enc_jpeg_huffman_decode.cc (3229B)
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