huffman_table.cc (5302B)
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/huffman_table.h" 7 8 #include <cstring> /* for memcpy */ 9 #include <vector> 10 11 #include "lib/jxl/ans_params.h" 12 #include "lib/jxl/dec_huffman.h" 13 14 namespace jxl { 15 16 /* Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the 17 bit-wise reversal of the len least significant bits of key. */ 18 static inline int GetNextKey(int key, int len) { 19 int step = 1u << (len - 1); 20 while (key & step) { 21 step >>= 1; 22 } 23 return (key & (step - 1)) + step; 24 } 25 26 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */ 27 /* Assumes that end is an integer multiple of step */ 28 static inline void ReplicateValue(HuffmanCode* table, int step, int end, 29 HuffmanCode code) { 30 do { 31 end -= step; 32 table[end] = code; 33 } while (end > 0); 34 } 35 36 /* Returns the table width of the next 2nd level table. count is the histogram 37 of bit lengths for the remaining symbols, len is the code length of the next 38 processed symbol */ 39 static inline size_t NextTableBitSize(const uint16_t* const count, size_t len, 40 int root_bits) { 41 size_t left = 1u << (len - root_bits); 42 while (len < PREFIX_MAX_BITS) { 43 if (left <= count[len]) break; 44 left -= count[len]; 45 ++len; 46 left <<= 1; 47 } 48 return len - root_bits; 49 } 50 51 uint32_t BuildHuffmanTable(HuffmanCode* root_table, int root_bits, 52 const uint8_t* const code_lengths, 53 size_t code_lengths_size, uint16_t* count) { 54 HuffmanCode code; /* current table entry */ 55 HuffmanCode* table; /* next available space in table */ 56 size_t len; /* current code length */ 57 size_t symbol; /* symbol index in original or sorted table */ 58 int key; /* reversed prefix code */ 59 int step; /* step size to replicate values in current table */ 60 int low; /* low bits for current root entry */ 61 int mask; /* mask for low bits */ 62 size_t table_bits; /* key length of current table */ 63 int table_size; /* size of current table */ 64 int total_size; /* sum of root table size and 2nd level table sizes */ 65 /* offsets in sorted table for each length */ 66 uint16_t offset[PREFIX_MAX_BITS + 1]; 67 size_t max_length = 1; 68 69 if (code_lengths_size > 1u << PREFIX_MAX_BITS) return 0; 70 71 /* symbols sorted by code length */ 72 std::vector<uint16_t> sorted_storage(code_lengths_size); 73 uint16_t* sorted = sorted_storage.data(); 74 75 /* generate offsets into sorted symbol table by code length */ 76 { 77 uint16_t sum = 0; 78 for (len = 1; len <= PREFIX_MAX_BITS; len++) { 79 offset[len] = sum; 80 if (count[len]) { 81 sum = static_cast<uint16_t>(sum + count[len]); 82 max_length = len; 83 } 84 } 85 } 86 87 /* sort symbols by length, by symbol order within each length */ 88 for (symbol = 0; symbol < code_lengths_size; symbol++) { 89 if (code_lengths[symbol] != 0) { 90 sorted[offset[code_lengths[symbol]]++] = symbol; 91 } 92 } 93 94 table = root_table; 95 table_bits = root_bits; 96 table_size = 1u << table_bits; 97 total_size = table_size; 98 99 /* special case code with only one value */ 100 if (offset[PREFIX_MAX_BITS] == 1) { 101 code.bits = 0; 102 code.value = static_cast<uint16_t>(sorted[0]); 103 for (key = 0; key < total_size; ++key) { 104 table[key] = code; 105 } 106 return total_size; 107 } 108 109 /* fill in root table */ 110 /* let's reduce the table size to a smaller size if possible, and */ 111 /* create the repetitions by memcpy if possible in the coming loop */ 112 if (table_bits > max_length) { 113 table_bits = max_length; 114 table_size = 1u << table_bits; 115 } 116 key = 0; 117 symbol = 0; 118 code.bits = 1; 119 step = 2; 120 do { 121 for (; count[code.bits] != 0; --count[code.bits]) { 122 code.value = static_cast<uint16_t>(sorted[symbol++]); 123 ReplicateValue(&table[key], step, table_size, code); 124 key = GetNextKey(key, code.bits); 125 } 126 step <<= 1; 127 } while (++code.bits <= table_bits); 128 129 /* if root_bits != table_bits we only created one fraction of the */ 130 /* table, and we need to replicate it now. */ 131 while (total_size != table_size) { 132 memcpy(&table[table_size], &table[0], table_size * sizeof(table[0])); 133 table_size <<= 1; 134 } 135 136 /* fill in 2nd level tables and add pointers to root table */ 137 mask = total_size - 1; 138 low = -1; 139 for (len = root_bits + 1, step = 2; len <= max_length; ++len, step <<= 1) { 140 for (; count[len] != 0; --count[len]) { 141 if ((key & mask) != low) { 142 table += table_size; 143 table_bits = NextTableBitSize(count, len, root_bits); 144 table_size = 1u << table_bits; 145 total_size += table_size; 146 low = key & mask; 147 root_table[low].bits = static_cast<uint8_t>(table_bits + root_bits); 148 root_table[low].value = 149 static_cast<uint16_t>((table - root_table) - low); 150 } 151 code.bits = static_cast<uint8_t>(len - root_bits); 152 code.value = static_cast<uint16_t>(sorted[symbol++]); 153 ReplicateValue(&table[key >> root_bits], step, table_size, code); 154 key = GetNextKey(key, len); 155 } 156 } 157 158 return total_size; 159 } 160 161 } // namespace jxl