enc_huffman_tree.cc (9858B)
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_tree.h" 7 8 #include <algorithm> 9 #include <limits> 10 #include <vector> 11 12 #include "lib/jxl/base/status.h" 13 14 namespace jxl { 15 16 void SetDepth(const HuffmanTree& p, HuffmanTree* pool, uint8_t* depth, 17 uint8_t level) { 18 if (p.index_left >= 0) { 19 ++level; 20 SetDepth(pool[p.index_left], pool, depth, level); 21 SetDepth(pool[p.index_right_or_value], pool, depth, level); 22 } else { 23 depth[p.index_right_or_value] = level; 24 } 25 } 26 27 // Sort the root nodes, least popular first. 28 static JXL_INLINE bool Compare(const HuffmanTree& v0, const HuffmanTree& v1) { 29 return v0.total_count < v1.total_count; 30 } 31 32 // This function will create a Huffman tree. 33 // 34 // The catch here is that the tree cannot be arbitrarily deep. 35 // Brotli specifies a maximum depth of 15 bits for "code trees" 36 // and 7 bits for "code length code trees." 37 // 38 // count_limit is the value that is to be faked as the minimum value 39 // and this minimum value is raised until the tree matches the 40 // maximum length requirement. 41 // 42 // This algorithm is not of excellent performance for very long data blocks, 43 // especially when population counts are longer than 2**tree_limit, but 44 // we are not planning to use this with extremely long blocks. 45 // 46 // See http://en.wikipedia.org/wiki/Huffman_coding 47 void CreateHuffmanTree(const uint32_t* data, const size_t length, 48 const int tree_limit, uint8_t* depth) { 49 // For block sizes below 64 kB, we never need to do a second iteration 50 // of this loop. Probably all of our block sizes will be smaller than 51 // that, so this loop is mostly of academic interest. If we actually 52 // would need this, we would be better off with the Katajainen algorithm. 53 for (uint32_t count_limit = 1;; count_limit *= 2) { 54 std::vector<HuffmanTree> tree; 55 tree.reserve(2 * length + 1); 56 57 for (size_t i = length; i != 0;) { 58 --i; 59 if (data[i]) { 60 const uint32_t count = std::max(data[i], count_limit - 1); 61 tree.emplace_back(count, -1, static_cast<int16_t>(i)); 62 } 63 } 64 65 const size_t n = tree.size(); 66 if (n == 1) { 67 // Fake value; will be fixed on upper level. 68 depth[tree[0].index_right_or_value] = 1; 69 break; 70 } 71 72 std::stable_sort(tree.begin(), tree.end(), Compare); 73 74 // The nodes are: 75 // [0, n): the sorted leaf nodes that we start with. 76 // [n]: we add a sentinel here. 77 // [n + 1, 2n): new parent nodes are added here, starting from 78 // (n+1). These are naturally in ascending order. 79 // [2n]: we add a sentinel at the end as well. 80 // There will be (2n+1) elements at the end. 81 const HuffmanTree sentinel(std::numeric_limits<uint32_t>::max(), -1, -1); 82 tree.push_back(sentinel); 83 tree.push_back(sentinel); 84 85 size_t i = 0; // Points to the next leaf node. 86 size_t j = n + 1; // Points to the next non-leaf node. 87 for (size_t k = n - 1; k != 0; --k) { 88 size_t left; 89 size_t right; 90 if (tree[i].total_count <= tree[j].total_count) { 91 left = i; 92 ++i; 93 } else { 94 left = j; 95 ++j; 96 } 97 if (tree[i].total_count <= tree[j].total_count) { 98 right = i; 99 ++i; 100 } else { 101 right = j; 102 ++j; 103 } 104 105 // The sentinel node becomes the parent node. 106 size_t j_end = tree.size() - 1; 107 tree[j_end].total_count = 108 tree[left].total_count + tree[right].total_count; 109 tree[j_end].index_left = static_cast<int16_t>(left); 110 tree[j_end].index_right_or_value = static_cast<int16_t>(right); 111 112 // Add back the last sentinel node. 113 tree.push_back(sentinel); 114 } 115 JXL_DASSERT(tree.size() == 2 * n + 1); 116 SetDepth(tree[2 * n - 1], tree.data(), depth, 0); 117 118 // We need to pack the Huffman tree in tree_limit bits. 119 // If this was not successful, add fake entities to the lowest values 120 // and retry. 121 if (*std::max_element(&depth[0], &depth[length]) <= tree_limit) { 122 break; 123 } 124 } 125 } 126 127 void Reverse(uint8_t* v, size_t start, size_t end) { 128 --end; 129 while (start < end) { 130 uint8_t tmp = v[start]; 131 v[start] = v[end]; 132 v[end] = tmp; 133 ++start; 134 --end; 135 } 136 } 137 138 void WriteHuffmanTreeRepetitions(const uint8_t previous_value, 139 const uint8_t value, size_t repetitions, 140 size_t* tree_size, uint8_t* tree, 141 uint8_t* extra_bits_data) { 142 JXL_DASSERT(repetitions > 0); 143 if (previous_value != value) { 144 tree[*tree_size] = value; 145 extra_bits_data[*tree_size] = 0; 146 ++(*tree_size); 147 --repetitions; 148 } 149 if (repetitions == 7) { 150 tree[*tree_size] = value; 151 extra_bits_data[*tree_size] = 0; 152 ++(*tree_size); 153 --repetitions; 154 } 155 if (repetitions < 3) { 156 for (size_t i = 0; i < repetitions; ++i) { 157 tree[*tree_size] = value; 158 extra_bits_data[*tree_size] = 0; 159 ++(*tree_size); 160 } 161 } else { 162 repetitions -= 3; 163 size_t start = *tree_size; 164 while (true) { 165 tree[*tree_size] = 16; 166 extra_bits_data[*tree_size] = repetitions & 0x3; 167 ++(*tree_size); 168 repetitions >>= 2; 169 if (repetitions == 0) { 170 break; 171 } 172 --repetitions; 173 } 174 Reverse(tree, start, *tree_size); 175 Reverse(extra_bits_data, start, *tree_size); 176 } 177 } 178 179 void WriteHuffmanTreeRepetitionsZeros(size_t repetitions, size_t* tree_size, 180 uint8_t* tree, uint8_t* extra_bits_data) { 181 if (repetitions == 11) { 182 tree[*tree_size] = 0; 183 extra_bits_data[*tree_size] = 0; 184 ++(*tree_size); 185 --repetitions; 186 } 187 if (repetitions < 3) { 188 for (size_t i = 0; i < repetitions; ++i) { 189 tree[*tree_size] = 0; 190 extra_bits_data[*tree_size] = 0; 191 ++(*tree_size); 192 } 193 } else { 194 repetitions -= 3; 195 size_t start = *tree_size; 196 while (true) { 197 tree[*tree_size] = 17; 198 extra_bits_data[*tree_size] = repetitions & 0x7; 199 ++(*tree_size); 200 repetitions >>= 3; 201 if (repetitions == 0) { 202 break; 203 } 204 --repetitions; 205 } 206 Reverse(tree, start, *tree_size); 207 Reverse(extra_bits_data, start, *tree_size); 208 } 209 } 210 211 static void DecideOverRleUse(const uint8_t* depth, const size_t length, 212 bool* use_rle_for_non_zero, 213 bool* use_rle_for_zero) { 214 size_t total_reps_zero = 0; 215 size_t total_reps_non_zero = 0; 216 size_t count_reps_zero = 1; 217 size_t count_reps_non_zero = 1; 218 for (size_t i = 0; i < length;) { 219 const uint8_t value = depth[i]; 220 size_t reps = 1; 221 for (size_t k = i + 1; k < length && depth[k] == value; ++k) { 222 ++reps; 223 } 224 if (reps >= 3 && value == 0) { 225 total_reps_zero += reps; 226 ++count_reps_zero; 227 } 228 if (reps >= 4 && value != 0) { 229 total_reps_non_zero += reps; 230 ++count_reps_non_zero; 231 } 232 i += reps; 233 } 234 *use_rle_for_non_zero = total_reps_non_zero > count_reps_non_zero * 2; 235 *use_rle_for_zero = total_reps_zero > count_reps_zero * 2; 236 } 237 238 void WriteHuffmanTree(const uint8_t* depth, size_t length, size_t* tree_size, 239 uint8_t* tree, uint8_t* extra_bits_data) { 240 uint8_t previous_value = 8; 241 242 // Throw away trailing zeros. 243 size_t new_length = length; 244 for (size_t i = 0; i < length; ++i) { 245 if (depth[length - i - 1] == 0) { 246 --new_length; 247 } else { 248 break; 249 } 250 } 251 252 // First gather statistics on if it is a good idea to do rle. 253 bool use_rle_for_non_zero = false; 254 bool use_rle_for_zero = false; 255 if (length > 50) { 256 // Find rle coding for longer codes. 257 // Shorter codes seem not to benefit from rle. 258 DecideOverRleUse(depth, new_length, &use_rle_for_non_zero, 259 &use_rle_for_zero); 260 } 261 262 // Actual rle coding. 263 for (size_t i = 0; i < new_length;) { 264 const uint8_t value = depth[i]; 265 size_t reps = 1; 266 if ((value != 0 && use_rle_for_non_zero) || 267 (value == 0 && use_rle_for_zero)) { 268 for (size_t k = i + 1; k < new_length && depth[k] == value; ++k) { 269 ++reps; 270 } 271 } 272 if (value == 0) { 273 WriteHuffmanTreeRepetitionsZeros(reps, tree_size, tree, extra_bits_data); 274 } else { 275 WriteHuffmanTreeRepetitions(previous_value, value, reps, tree_size, tree, 276 extra_bits_data); 277 previous_value = value; 278 } 279 i += reps; 280 } 281 } 282 283 namespace { 284 285 uint16_t ReverseBits(int num_bits, uint16_t bits) { 286 static const size_t kLut[16] = {// Pre-reversed 4-bit values. 287 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 288 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf}; 289 size_t retval = kLut[bits & 0xf]; 290 for (int i = 4; i < num_bits; i += 4) { 291 retval <<= 4; 292 bits = static_cast<uint16_t>(bits >> 4); 293 retval |= kLut[bits & 0xf]; 294 } 295 retval >>= (-num_bits & 0x3); 296 return static_cast<uint16_t>(retval); 297 } 298 299 } // namespace 300 301 void ConvertBitDepthsToSymbols(const uint8_t* depth, size_t len, 302 uint16_t* bits) { 303 // In Brotli, all bit depths are [1..15] 304 // 0 bit depth means that the symbol does not exist. 305 const int kMaxBits = 16; // 0..15 are values for bits 306 uint16_t bl_count[kMaxBits] = {0}; 307 { 308 for (size_t i = 0; i < len; ++i) { 309 ++bl_count[depth[i]]; 310 } 311 bl_count[0] = 0; 312 } 313 uint16_t next_code[kMaxBits]; 314 next_code[0] = 0; 315 { 316 int code = 0; 317 for (size_t i = 1; i < kMaxBits; ++i) { 318 code = (code + bl_count[i - 1]) << 1; 319 next_code[i] = static_cast<uint16_t>(code); 320 } 321 } 322 for (size_t i = 0; i < len; ++i) { 323 if (depth[i]) { 324 bits[i] = ReverseBits(depth[i], next_code[depth[i]]++); 325 } 326 } 327 } 328 329 } // namespace jxl