dec_huffman.cc (7615B)
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/dec_huffman.h" 7 8 #include <jxl/types.h> 9 #include <string.h> /* for memset */ 10 11 #include <vector> 12 13 #include "lib/jxl/ans_params.h" 14 #include "lib/jxl/base/bits.h" 15 #include "lib/jxl/huffman_table.h" 16 17 namespace jxl { 18 19 static const int kCodeLengthCodes = 18; 20 static const uint8_t kCodeLengthCodeOrder[kCodeLengthCodes] = { 21 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, 22 }; 23 static const uint8_t kDefaultCodeLength = 8; 24 static const uint8_t kCodeLengthRepeatCode = 16; 25 26 JXL_BOOL ReadHuffmanCodeLengths(const uint8_t* code_length_code_lengths, 27 int num_symbols, uint8_t* code_lengths, 28 BitReader* br) { 29 int symbol = 0; 30 uint8_t prev_code_len = kDefaultCodeLength; 31 int repeat = 0; 32 uint8_t repeat_code_len = 0; 33 int space = 32768; 34 HuffmanCode table[32]; 35 36 uint16_t counts[16] = {0}; 37 for (int i = 0; i < kCodeLengthCodes; ++i) { 38 ++counts[code_length_code_lengths[i]]; 39 } 40 if (!BuildHuffmanTable(table, 5, code_length_code_lengths, kCodeLengthCodes, 41 &counts[0])) { 42 return JXL_FALSE; 43 } 44 45 while (symbol < num_symbols && space > 0) { 46 const HuffmanCode* p = table; 47 uint8_t code_len; 48 br->Refill(); 49 p += br->PeekFixedBits<5>(); 50 br->Consume(p->bits); 51 code_len = static_cast<uint8_t>(p->value); 52 if (code_len < kCodeLengthRepeatCode) { 53 repeat = 0; 54 code_lengths[symbol++] = code_len; 55 if (code_len != 0) { 56 prev_code_len = code_len; 57 space -= 32768u >> code_len; 58 } 59 } else { 60 const int extra_bits = code_len - 14; 61 int old_repeat; 62 int repeat_delta; 63 uint8_t new_len = 0; 64 if (code_len == kCodeLengthRepeatCode) { 65 new_len = prev_code_len; 66 } 67 if (repeat_code_len != new_len) { 68 repeat = 0; 69 repeat_code_len = new_len; 70 } 71 old_repeat = repeat; 72 if (repeat > 0) { 73 repeat -= 2; 74 repeat <<= extra_bits; 75 } 76 repeat += static_cast<int>(br->ReadBits(extra_bits) + 3); 77 repeat_delta = repeat - old_repeat; 78 if (symbol + repeat_delta > num_symbols) { 79 return 0; 80 } 81 memset(&code_lengths[symbol], repeat_code_len, 82 static_cast<size_t>(repeat_delta)); 83 symbol += repeat_delta; 84 if (repeat_code_len != 0) { 85 space -= repeat_delta << (15 - repeat_code_len); 86 } 87 } 88 } 89 if (space != 0) { 90 return JXL_FALSE; 91 } 92 memset(&code_lengths[symbol], 0, static_cast<size_t>(num_symbols - symbol)); 93 return JXL_TRUE; 94 } 95 96 static JXL_INLINE bool ReadSimpleCode(size_t alphabet_size, BitReader* br, 97 HuffmanCode* table) { 98 size_t max_bits = 99 (alphabet_size > 1u) ? FloorLog2Nonzero(alphabet_size - 1u) + 1 : 0; 100 101 size_t num_symbols = br->ReadFixedBits<2>() + 1; 102 103 uint16_t symbols[4] = {0}; 104 for (size_t i = 0; i < num_symbols; ++i) { 105 uint16_t symbol = br->ReadBits(max_bits); 106 if (symbol >= alphabet_size) { 107 return false; 108 } 109 symbols[i] = symbol; 110 } 111 112 for (size_t i = 0; i < num_symbols - 1; ++i) { 113 for (size_t j = i + 1; j < num_symbols; ++j) { 114 if (symbols[i] == symbols[j]) return false; 115 } 116 } 117 118 // 4 symbols have to option to encode. 119 if (num_symbols == 4) num_symbols += br->ReadFixedBits<1>(); 120 121 const auto swap_symbols = [&symbols](size_t i, size_t j) { 122 uint16_t t = symbols[j]; 123 symbols[j] = symbols[i]; 124 symbols[i] = t; 125 }; 126 127 size_t table_size = 1; 128 switch (num_symbols) { 129 case 1: 130 table[0] = {0, symbols[0]}; 131 break; 132 case 2: 133 if (symbols[0] > symbols[1]) swap_symbols(0, 1); 134 table[0] = {1, symbols[0]}; 135 table[1] = {1, symbols[1]}; 136 table_size = 2; 137 break; 138 case 3: 139 if (symbols[1] > symbols[2]) swap_symbols(1, 2); 140 table[0] = {1, symbols[0]}; 141 table[2] = {1, symbols[0]}; 142 table[1] = {2, symbols[1]}; 143 table[3] = {2, symbols[2]}; 144 table_size = 4; 145 break; 146 case 4: { 147 for (size_t i = 0; i < 3; ++i) { 148 for (size_t j = i + 1; j < 4; ++j) { 149 if (symbols[i] > symbols[j]) swap_symbols(i, j); 150 } 151 } 152 table[0] = {2, symbols[0]}; 153 table[2] = {2, symbols[1]}; 154 table[1] = {2, symbols[2]}; 155 table[3] = {2, symbols[3]}; 156 table_size = 4; 157 break; 158 } 159 case 5: { 160 if (symbols[2] > symbols[3]) swap_symbols(2, 3); 161 table[0] = {1, symbols[0]}; 162 table[1] = {2, symbols[1]}; 163 table[2] = {1, symbols[0]}; 164 table[3] = {3, symbols[2]}; 165 table[4] = {1, symbols[0]}; 166 table[5] = {2, symbols[1]}; 167 table[6] = {1, symbols[0]}; 168 table[7] = {3, symbols[3]}; 169 table_size = 8; 170 break; 171 } 172 default: { 173 // Unreachable. 174 return false; 175 } 176 } 177 178 const uint32_t goal_size = 1u << kHuffmanTableBits; 179 while (table_size != goal_size) { 180 memcpy(&table[table_size], &table[0], 181 static_cast<size_t>(table_size) * sizeof(table[0])); 182 table_size <<= 1; 183 } 184 185 return true; 186 } 187 188 bool HuffmanDecodingData::ReadFromBitStream(size_t alphabet_size, 189 BitReader* br) { 190 if (alphabet_size > (1 << PREFIX_MAX_BITS)) return false; 191 192 /* simple_code_or_skip is used as follows: 193 1 for simple code; 194 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ 195 uint32_t simple_code_or_skip = br->ReadFixedBits<2>(); 196 if (simple_code_or_skip == 1u) { 197 table_.resize(1u << kHuffmanTableBits); 198 return ReadSimpleCode(alphabet_size, br, table_.data()); 199 } 200 201 std::vector<uint8_t> code_lengths(alphabet_size, 0); 202 uint8_t code_length_code_lengths[kCodeLengthCodes] = {0}; 203 int space = 32; 204 int num_codes = 0; 205 /* Static Huffman code for the code length code lengths */ 206 static const HuffmanCode huff[16] = { 207 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1}, 208 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5}, 209 }; 210 for (size_t i = simple_code_or_skip; i < kCodeLengthCodes && space > 0; ++i) { 211 const int code_len_idx = kCodeLengthCodeOrder[i]; 212 const HuffmanCode* p = huff; 213 uint8_t v; 214 br->Refill(); 215 p += br->PeekFixedBits<4>(); 216 br->Consume(p->bits); 217 v = static_cast<uint8_t>(p->value); 218 code_length_code_lengths[code_len_idx] = v; 219 if (v != 0) { 220 space -= (32u >> v); 221 ++num_codes; 222 } 223 } 224 bool ok = 225 (num_codes == 1 || space == 0) && 226 FROM_JXL_BOOL(ReadHuffmanCodeLengths( 227 code_length_code_lengths, alphabet_size, code_lengths.data(), br)); 228 229 if (!ok) return false; 230 uint16_t counts[16] = {0}; 231 for (size_t i = 0; i < alphabet_size; ++i) { 232 ++counts[code_lengths[i]]; 233 } 234 table_.resize(alphabet_size + 376); 235 uint32_t table_size = 236 BuildHuffmanTable(table_.data(), kHuffmanTableBits, code_lengths.data(), 237 alphabet_size, &counts[0]); 238 table_.resize(table_size); 239 return (table_size > 0); 240 } 241 242 // Decodes the next Huffman coded symbol from the bit-stream. 243 uint16_t HuffmanDecodingData::ReadSymbol(BitReader* br) const { 244 size_t n_bits; 245 const HuffmanCode* table = table_.data(); 246 table += br->PeekBits(kHuffmanTableBits); 247 n_bits = table->bits; 248 if (n_bits > kHuffmanTableBits) { 249 br->Consume(kHuffmanTableBits); 250 n_bits -= kHuffmanTableBits; 251 table += table->value; 252 table += br->PeekBits(n_bits); 253 } 254 br->Consume(table->bits); 255 return table->value; 256 } 257 258 } // namespace jxl