1 // Copyright 2011 Google Inc. All Rights Reserved. 2 // 3 // This code is licensed under the same terms as WebM: 4 // Software License Agreement: http://www.webmproject.org/license/software/ 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 6 // ----------------------------------------------------------------------------- 7 // 8 // Author: Jyrki Alakuijala (jyrki (at) google.com) 9 // 10 // Entropy encoding (Huffman) for webp lossless. 11 12 #include <assert.h> 13 #include <stdlib.h> 14 #include <string.h> 15 #include "./huffman_encode.h" 16 #include "../utils/utils.h" 17 #include "webp/format_constants.h" 18 19 // ----------------------------------------------------------------------------- 20 // Util function to optimize the symbol map for RLE coding 21 22 // Heuristics for selecting the stride ranges to collapse. 23 static int ValuesShouldBeCollapsedToStrideAverage(int a, int b) { 24 return abs(a - b) < 4; 25 } 26 27 // Change the population counts in a way that the consequent 28 // Hufmann tree compression, especially its RLE-part, give smaller output. 29 static int OptimizeHuffmanForRle(int length, int* const counts) { 30 uint8_t* good_for_rle; 31 // 1) Let's make the Huffman code more compatible with rle encoding. 32 int i; 33 for (; length >= 0; --length) { 34 if (length == 0) { 35 return 1; // All zeros. 36 } 37 if (counts[length - 1] != 0) { 38 // Now counts[0..length - 1] does not have trailing zeros. 39 break; 40 } 41 } 42 // 2) Let's mark all population counts that already can be encoded 43 // with an rle code. 44 good_for_rle = (uint8_t*)calloc(length, 1); 45 if (good_for_rle == NULL) { 46 return 0; 47 } 48 { 49 // Let's not spoil any of the existing good rle codes. 50 // Mark any seq of 0's that is longer as 5 as a good_for_rle. 51 // Mark any seq of non-0's that is longer as 7 as a good_for_rle. 52 int symbol = counts[0]; 53 int stride = 0; 54 for (i = 0; i < length + 1; ++i) { 55 if (i == length || counts[i] != symbol) { 56 if ((symbol == 0 && stride >= 5) || 57 (symbol != 0 && stride >= 7)) { 58 int k; 59 for (k = 0; k < stride; ++k) { 60 good_for_rle[i - k - 1] = 1; 61 } 62 } 63 stride = 1; 64 if (i != length) { 65 symbol = counts[i]; 66 } 67 } else { 68 ++stride; 69 } 70 } 71 } 72 // 3) Let's replace those population counts that lead to more rle codes. 73 { 74 int stride = 0; 75 int limit = counts[0]; 76 int sum = 0; 77 for (i = 0; i < length + 1; ++i) { 78 if (i == length || good_for_rle[i] || 79 (i != 0 && good_for_rle[i - 1]) || 80 !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) { 81 if (stride >= 4 || (stride >= 3 && sum == 0)) { 82 int k; 83 // The stride must end, collapse what we have, if we have enough (4). 84 int count = (sum + stride / 2) / stride; 85 if (count < 1) { 86 count = 1; 87 } 88 if (sum == 0) { 89 // Don't make an all zeros stride to be upgraded to ones. 90 count = 0; 91 } 92 for (k = 0; k < stride; ++k) { 93 // We don't want to change value at counts[i], 94 // that is already belonging to the next stride. Thus - 1. 95 counts[i - k - 1] = count; 96 } 97 } 98 stride = 0; 99 sum = 0; 100 if (i < length - 3) { 101 // All interesting strides have a count of at least 4, 102 // at least when non-zeros. 103 limit = (counts[i] + counts[i + 1] + 104 counts[i + 2] + counts[i + 3] + 2) / 4; 105 } else if (i < length) { 106 limit = counts[i]; 107 } else { 108 limit = 0; 109 } 110 } 111 ++stride; 112 if (i != length) { 113 sum += counts[i]; 114 if (stride >= 4) { 115 limit = (sum + stride / 2) / stride; 116 } 117 } 118 } 119 } 120 free(good_for_rle); 121 return 1; 122 } 123 124 typedef struct { 125 int total_count_; 126 int value_; 127 int pool_index_left_; 128 int pool_index_right_; 129 } HuffmanTree; 130 131 // A comparer function for two Huffman trees: sorts first by 'total count' 132 // (more comes first), and then by 'value' (more comes first). 133 static int CompareHuffmanTrees(const void* ptr1, const void* ptr2) { 134 const HuffmanTree* const t1 = (const HuffmanTree*)ptr1; 135 const HuffmanTree* const t2 = (const HuffmanTree*)ptr2; 136 if (t1->total_count_ > t2->total_count_) { 137 return -1; 138 } else if (t1->total_count_ < t2->total_count_) { 139 return 1; 140 } else { 141 assert(t1->value_ != t2->value_); 142 return (t1->value_ < t2->value_) ? -1 : 1; 143 } 144 } 145 146 static void SetBitDepths(const HuffmanTree* const tree, 147 const HuffmanTree* const pool, 148 uint8_t* const bit_depths, int level) { 149 if (tree->pool_index_left_ >= 0) { 150 SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1); 151 SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1); 152 } else { 153 bit_depths[tree->value_] = level; 154 } 155 } 156 157 // Create an optimal Huffman tree. 158 // 159 // (data,length): population counts. 160 // tree_limit: maximum bit depth (inclusive) of the codes. 161 // bit_depths[]: how many bits are used for the symbol. 162 // 163 // Returns 0 when an error has occurred. 164 // 165 // The catch here is that the tree cannot be arbitrarily deep 166 // 167 // count_limit is the value that is to be faked as the minimum value 168 // and this minimum value is raised until the tree matches the 169 // maximum length requirement. 170 // 171 // This algorithm is not of excellent performance for very long data blocks, 172 // especially when population counts are longer than 2**tree_limit, but 173 // we are not planning to use this with extremely long blocks. 174 // 175 // See http://en.wikipedia.org/wiki/Huffman_coding 176 static int GenerateOptimalTree(const int* const histogram, int histogram_size, 177 int tree_depth_limit, 178 uint8_t* const bit_depths) { 179 int count_min; 180 HuffmanTree* tree_pool; 181 HuffmanTree* tree; 182 int tree_size_orig = 0; 183 int i; 184 185 for (i = 0; i < histogram_size; ++i) { 186 if (histogram[i] != 0) { 187 ++tree_size_orig; 188 } 189 } 190 191 if (tree_size_orig == 0) { // pretty optimal already! 192 return 1; 193 } 194 195 // 3 * tree_size is enough to cover all the nodes representing a 196 // population and all the inserted nodes combining two existing nodes. 197 // The tree pool needs 2 * (tree_size_orig - 1) entities, and the 198 // tree needs exactly tree_size_orig entities. 199 tree = (HuffmanTree*)WebPSafeMalloc(3ULL * tree_size_orig, sizeof(*tree)); 200 if (tree == NULL) return 0; 201 tree_pool = tree + tree_size_orig; 202 203 // For block sizes with less than 64k symbols we never need to do a 204 // second iteration of this loop. 205 // If we actually start running inside this loop a lot, we would perhaps 206 // be better off with the Katajainen algorithm. 207 assert(tree_size_orig <= (1 << (tree_depth_limit - 1))); 208 for (count_min = 1; ; count_min *= 2) { 209 int tree_size = tree_size_orig; 210 // We need to pack the Huffman tree in tree_depth_limit bits. 211 // So, we try by faking histogram entries to be at least 'count_min'. 212 int idx = 0; 213 int j; 214 for (j = 0; j < histogram_size; ++j) { 215 if (histogram[j] != 0) { 216 const int count = 217 (histogram[j] < count_min) ? count_min : histogram[j]; 218 tree[idx].total_count_ = count; 219 tree[idx].value_ = j; 220 tree[idx].pool_index_left_ = -1; 221 tree[idx].pool_index_right_ = -1; 222 ++idx; 223 } 224 } 225 226 // Build the Huffman tree. 227 qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees); 228 229 if (tree_size > 1) { // Normal case. 230 int tree_pool_size = 0; 231 while (tree_size > 1) { // Finish when we have only one root. 232 int count; 233 tree_pool[tree_pool_size++] = tree[tree_size - 1]; 234 tree_pool[tree_pool_size++] = tree[tree_size - 2]; 235 count = tree_pool[tree_pool_size - 1].total_count_ + 236 tree_pool[tree_pool_size - 2].total_count_; 237 tree_size -= 2; 238 { 239 // Search for the insertion point. 240 int k; 241 for (k = 0; k < tree_size; ++k) { 242 if (tree[k].total_count_ <= count) { 243 break; 244 } 245 } 246 memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree)); 247 tree[k].total_count_ = count; 248 tree[k].value_ = -1; 249 250 tree[k].pool_index_left_ = tree_pool_size - 1; 251 tree[k].pool_index_right_ = tree_pool_size - 2; 252 tree_size = tree_size + 1; 253 } 254 } 255 SetBitDepths(&tree[0], tree_pool, bit_depths, 0); 256 } else if (tree_size == 1) { // Trivial case: only one element. 257 bit_depths[tree[0].value_] = 1; 258 } 259 260 { 261 // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria. 262 int max_depth = bit_depths[0]; 263 for (j = 1; j < histogram_size; ++j) { 264 if (max_depth < bit_depths[j]) { 265 max_depth = bit_depths[j]; 266 } 267 } 268 if (max_depth <= tree_depth_limit) { 269 break; 270 } 271 } 272 } 273 free(tree); 274 return 1; 275 } 276 277 // ----------------------------------------------------------------------------- 278 // Coding of the Huffman tree values 279 280 static HuffmanTreeToken* CodeRepeatedValues(int repetitions, 281 HuffmanTreeToken* tokens, 282 int value, int prev_value) { 283 assert(value <= MAX_ALLOWED_CODE_LENGTH); 284 if (value != prev_value) { 285 tokens->code = value; 286 tokens->extra_bits = 0; 287 ++tokens; 288 --repetitions; 289 } 290 while (repetitions >= 1) { 291 if (repetitions < 3) { 292 int i; 293 for (i = 0; i < repetitions; ++i) { 294 tokens->code = value; 295 tokens->extra_bits = 0; 296 ++tokens; 297 } 298 break; 299 } else if (repetitions < 7) { 300 tokens->code = 16; 301 tokens->extra_bits = repetitions - 3; 302 ++tokens; 303 break; 304 } else { 305 tokens->code = 16; 306 tokens->extra_bits = 3; 307 ++tokens; 308 repetitions -= 6; 309 } 310 } 311 return tokens; 312 } 313 314 static HuffmanTreeToken* CodeRepeatedZeros(int repetitions, 315 HuffmanTreeToken* tokens) { 316 while (repetitions >= 1) { 317 if (repetitions < 3) { 318 int i; 319 for (i = 0; i < repetitions; ++i) { 320 tokens->code = 0; // 0-value 321 tokens->extra_bits = 0; 322 ++tokens; 323 } 324 break; 325 } else if (repetitions < 11) { 326 tokens->code = 17; 327 tokens->extra_bits = repetitions - 3; 328 ++tokens; 329 break; 330 } else if (repetitions < 139) { 331 tokens->code = 18; 332 tokens->extra_bits = repetitions - 11; 333 ++tokens; 334 break; 335 } else { 336 tokens->code = 18; 337 tokens->extra_bits = 0x7f; // 138 repeated 0s 338 ++tokens; 339 repetitions -= 138; 340 } 341 } 342 return tokens; 343 } 344 345 int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 346 HuffmanTreeToken* tokens, int max_tokens) { 347 HuffmanTreeToken* const starting_token = tokens; 348 HuffmanTreeToken* const ending_token = tokens + max_tokens; 349 const int depth_size = tree->num_symbols; 350 int prev_value = 8; // 8 is the initial value for rle. 351 int i = 0; 352 assert(tokens != NULL); 353 while (i < depth_size) { 354 const int value = tree->code_lengths[i]; 355 int k = i + 1; 356 int runs; 357 while (k < depth_size && tree->code_lengths[k] == value) ++k; 358 runs = k - i; 359 if (value == 0) { 360 tokens = CodeRepeatedZeros(runs, tokens); 361 } else { 362 tokens = CodeRepeatedValues(runs, tokens, value, prev_value); 363 prev_value = value; 364 } 365 i += runs; 366 assert(tokens <= ending_token); 367 } 368 (void)ending_token; // suppress 'unused variable' warning 369 return (int)(tokens - starting_token); 370 } 371 372 // ----------------------------------------------------------------------------- 373 374 // Pre-reversed 4-bit values. 375 static const uint8_t kReversedBits[16] = { 376 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 377 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf 378 }; 379 380 static uint32_t ReverseBits(int num_bits, uint32_t bits) { 381 uint32_t retval = 0; 382 int i = 0; 383 while (i < num_bits) { 384 i += 4; 385 retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i); 386 bits >>= 4; 387 } 388 retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits); 389 return retval; 390 } 391 392 // Get the actual bit values for a tree of bit depths. 393 static void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) { 394 // 0 bit-depth means that the symbol does not exist. 395 int i; 396 int len; 397 uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1]; 398 int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 399 400 assert(tree != NULL); 401 len = tree->num_symbols; 402 for (i = 0; i < len; ++i) { 403 const int code_length = tree->code_lengths[i]; 404 assert(code_length <= MAX_ALLOWED_CODE_LENGTH); 405 ++depth_count[code_length]; 406 } 407 depth_count[0] = 0; // ignore unused symbol 408 next_code[0] = 0; 409 { 410 uint32_t code = 0; 411 for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) { 412 code = (code + depth_count[i - 1]) << 1; 413 next_code[i] = code; 414 } 415 } 416 for (i = 0; i < len; ++i) { 417 const int code_length = tree->code_lengths[i]; 418 tree->codes[i] = ReverseBits(code_length, next_code[code_length]++); 419 } 420 } 421 422 // ----------------------------------------------------------------------------- 423 // Main entry point 424 425 int VP8LCreateHuffmanTree(int* const histogram, int tree_depth_limit, 426 HuffmanTreeCode* const tree) { 427 const int num_symbols = tree->num_symbols; 428 if (!OptimizeHuffmanForRle(num_symbols, histogram)) { 429 return 0; 430 } 431 if (!GenerateOptimalTree(histogram, num_symbols, 432 tree_depth_limit, tree->code_lengths)) { 433 return 0; 434 } 435 // Create the actual bit codes for the bit lengths. 436 ConvertBitDepthsToSymbols(tree); 437 return 1; 438 } 439