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