enc_huffman.cc (6995B)
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/enc_huffman.h" 7 8 #include <algorithm> 9 #include <memory> 10 11 #include "lib/jxl/enc_huffman_tree.h" 12 13 namespace jxl { 14 15 namespace { 16 17 constexpr int kCodeLengthCodes = 18; 18 19 void StoreHuffmanTreeOfHuffmanTreeToBitMask(const int num_codes, 20 const uint8_t* code_length_bitdepth, 21 BitWriter* writer) { 22 static const uint8_t kStorageOrder[kCodeLengthCodes] = { 23 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 24 // The bit lengths of the Huffman code over the code length alphabet 25 // are compressed with the following static Huffman code: 26 // Symbol Code 27 // ------ ---- 28 // 0 00 29 // 1 1110 30 // 2 110 31 // 3 01 32 // 4 10 33 // 5 1111 34 static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = {0, 7, 3, 35 2, 1, 15}; 36 static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = {2, 4, 3, 37 2, 2, 4}; 38 39 // Throw away trailing zeros: 40 size_t codes_to_store = kCodeLengthCodes; 41 if (num_codes > 1) { 42 for (; codes_to_store > 0; --codes_to_store) { 43 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { 44 break; 45 } 46 } 47 } 48 size_t skip_some = 0; // skips none. 49 if (code_length_bitdepth[kStorageOrder[0]] == 0 && 50 code_length_bitdepth[kStorageOrder[1]] == 0) { 51 skip_some = 2; // skips two. 52 if (code_length_bitdepth[kStorageOrder[2]] == 0) { 53 skip_some = 3; // skips three. 54 } 55 } 56 writer->Write(2, skip_some); 57 for (size_t i = skip_some; i < codes_to_store; ++i) { 58 size_t l = code_length_bitdepth[kStorageOrder[i]]; 59 writer->Write(kHuffmanBitLengthHuffmanCodeBitLengths[l], 60 kHuffmanBitLengthHuffmanCodeSymbols[l]); 61 } 62 } 63 64 void StoreHuffmanTreeToBitMask(const size_t huffman_tree_size, 65 const uint8_t* huffman_tree, 66 const uint8_t* huffman_tree_extra_bits, 67 const uint8_t* code_length_bitdepth, 68 const uint16_t* code_length_bitdepth_symbols, 69 BitWriter* writer) { 70 for (size_t i = 0; i < huffman_tree_size; ++i) { 71 size_t ix = huffman_tree[i]; 72 writer->Write(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix]); 73 JXL_ASSERT(ix <= 17); 74 // Extra bits 75 switch (ix) { 76 case 16: 77 writer->Write(2, huffman_tree_extra_bits[i]); 78 break; 79 case 17: 80 writer->Write(3, huffman_tree_extra_bits[i]); 81 break; 82 default: 83 // no-op 84 break; 85 } 86 } 87 } 88 89 void StoreSimpleHuffmanTree(const uint8_t* depths, size_t symbols[4], 90 size_t num_symbols, size_t max_bits, 91 BitWriter* writer) { 92 // value of 1 indicates a simple Huffman code 93 writer->Write(2, 1); 94 writer->Write(2, num_symbols - 1); // NSYM - 1 95 96 // Sort 97 for (size_t i = 0; i < num_symbols; i++) { 98 for (size_t j = i + 1; j < num_symbols; j++) { 99 if (depths[symbols[j]] < depths[symbols[i]]) { 100 std::swap(symbols[j], symbols[i]); 101 } 102 } 103 } 104 105 if (num_symbols == 2) { 106 writer->Write(max_bits, symbols[0]); 107 writer->Write(max_bits, symbols[1]); 108 } else if (num_symbols == 3) { 109 writer->Write(max_bits, symbols[0]); 110 writer->Write(max_bits, symbols[1]); 111 writer->Write(max_bits, symbols[2]); 112 } else { 113 writer->Write(max_bits, symbols[0]); 114 writer->Write(max_bits, symbols[1]); 115 writer->Write(max_bits, symbols[2]); 116 writer->Write(max_bits, symbols[3]); 117 // tree-select 118 writer->Write(1, depths[symbols[0]] == 1 ? 1 : 0); 119 } 120 } 121 122 // num = alphabet size 123 // depths = symbol depths 124 void StoreHuffmanTree(const uint8_t* depths, size_t num, BitWriter* writer) { 125 // Write the Huffman tree into the compact representation. 126 std::unique_ptr<uint8_t[]> arena(new uint8_t[2 * num]); 127 uint8_t* huffman_tree = arena.get(); 128 uint8_t* huffman_tree_extra_bits = arena.get() + num; 129 size_t huffman_tree_size = 0; 130 WriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree, 131 huffman_tree_extra_bits); 132 133 // Calculate the statistics of the Huffman tree in the compact representation. 134 uint32_t huffman_tree_histogram[kCodeLengthCodes] = {0}; 135 for (size_t i = 0; i < huffman_tree_size; ++i) { 136 ++huffman_tree_histogram[huffman_tree[i]]; 137 } 138 139 int num_codes = 0; 140 int code = 0; 141 for (int i = 0; i < kCodeLengthCodes; ++i) { 142 if (huffman_tree_histogram[i]) { 143 if (num_codes == 0) { 144 code = i; 145 num_codes = 1; 146 } else if (num_codes == 1) { 147 num_codes = 2; 148 break; 149 } 150 } 151 } 152 153 // Calculate another Huffman tree to use for compressing both the 154 // earlier Huffman tree with. 155 uint8_t code_length_bitdepth[kCodeLengthCodes] = {0}; 156 uint16_t code_length_bitdepth_symbols[kCodeLengthCodes] = {0}; 157 CreateHuffmanTree(&huffman_tree_histogram[0], kCodeLengthCodes, 5, 158 &code_length_bitdepth[0]); 159 ConvertBitDepthsToSymbols(code_length_bitdepth, kCodeLengthCodes, 160 &code_length_bitdepth_symbols[0]); 161 162 // Now, we have all the data, let's start storing it 163 StoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth, 164 writer); 165 166 if (num_codes == 1) { 167 code_length_bitdepth[code] = 0; 168 } 169 170 // Store the real huffman tree now. 171 StoreHuffmanTreeToBitMask(huffman_tree_size, huffman_tree, 172 huffman_tree_extra_bits, &code_length_bitdepth[0], 173 code_length_bitdepth_symbols, writer); 174 } 175 176 } // namespace 177 178 void BuildAndStoreHuffmanTree(const uint32_t* histogram, const size_t length, 179 uint8_t* depth, uint16_t* bits, 180 BitWriter* writer) { 181 size_t count = 0; 182 size_t s4[4] = {0}; 183 for (size_t i = 0; i < length; i++) { 184 if (histogram[i]) { 185 if (count < 4) { 186 s4[count] = i; 187 } else if (count > 4) { 188 break; 189 } 190 count++; 191 } 192 } 193 194 size_t max_bits_counter = length - 1; 195 size_t max_bits = 0; 196 while (max_bits_counter) { 197 max_bits_counter >>= 1; 198 ++max_bits; 199 } 200 201 if (count <= 1) { 202 // Output symbol bits and depths are initialized with 0, nothing to do. 203 writer->Write(4, 1); 204 writer->Write(max_bits, s4[0]); 205 return; 206 } 207 208 CreateHuffmanTree(histogram, length, 15, depth); 209 ConvertBitDepthsToSymbols(depth, length, bits); 210 211 if (count <= 4) { 212 StoreSimpleHuffmanTree(depth, s4, count, max_bits, writer); 213 } else { 214 StoreHuffmanTree(depth, length, writer); 215 } 216 } 217 218 } // namespace jxl