OLD | NEW |
(Empty) | |
| 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@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 if (t1->value_ < t2->value_) { |
| 142 return -1; |
| 143 } |
| 144 if (t1->value_ > t2->value_) { |
| 145 return 1; |
| 146 } |
| 147 return 0; |
| 148 } |
| 149 } |
| 150 |
| 151 static void SetBitDepths(const HuffmanTree* const tree, |
| 152 const HuffmanTree* const pool, |
| 153 uint8_t* const bit_depths, int level) { |
| 154 if (tree->pool_index_left_ >= 0) { |
| 155 SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1); |
| 156 SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1); |
| 157 } else { |
| 158 bit_depths[tree->value_] = level; |
| 159 } |
| 160 } |
| 161 |
| 162 // Create an optimal Huffman tree. |
| 163 // |
| 164 // (data,length): population counts. |
| 165 // tree_limit: maximum bit depth (inclusive) of the codes. |
| 166 // bit_depths[]: how many bits are used for the symbol. |
| 167 // |
| 168 // Returns 0 when an error has occurred. |
| 169 // |
| 170 // The catch here is that the tree cannot be arbitrarily deep |
| 171 // |
| 172 // count_limit is the value that is to be faked as the minimum value |
| 173 // and this minimum value is raised until the tree matches the |
| 174 // maximum length requirement. |
| 175 // |
| 176 // This algorithm is not of excellent performance for very long data blocks, |
| 177 // especially when population counts are longer than 2**tree_limit, but |
| 178 // we are not planning to use this with extremely long blocks. |
| 179 // |
| 180 // See http://en.wikipedia.org/wiki/Huffman_coding |
| 181 static int GenerateOptimalTree(const int* const histogram, int histogram_size, |
| 182 int tree_depth_limit, |
| 183 uint8_t* const bit_depths) { |
| 184 int count_min; |
| 185 HuffmanTree* tree_pool; |
| 186 HuffmanTree* tree; |
| 187 int tree_size_orig = 0; |
| 188 int i; |
| 189 |
| 190 for (i = 0; i < histogram_size; ++i) { |
| 191 if (histogram[i] != 0) { |
| 192 ++tree_size_orig; |
| 193 } |
| 194 } |
| 195 |
| 196 // 3 * tree_size is enough to cover all the nodes representing a |
| 197 // population and all the inserted nodes combining two existing nodes. |
| 198 // The tree pool needs 2 * (tree_size_orig - 1) entities, and the |
| 199 // tree needs exactly tree_size_orig entities. |
| 200 tree = (HuffmanTree*)WebPSafeMalloc(3ULL * tree_size_orig, sizeof(*tree)); |
| 201 if (tree == NULL) return 0; |
| 202 tree_pool = tree + tree_size_orig; |
| 203 |
| 204 // For block sizes with less than 64k symbols we never need to do a |
| 205 // second iteration of this loop. |
| 206 // If we actually start running inside this loop a lot, we would perhaps |
| 207 // be better off with the Katajainen algorithm. |
| 208 assert(tree_size_orig <= (1 << (tree_depth_limit - 1))); |
| 209 for (count_min = 1; ; count_min *= 2) { |
| 210 int tree_size = tree_size_orig; |
| 211 // We need to pack the Huffman tree in tree_depth_limit bits. |
| 212 // So, we try by faking histogram entries to be at least 'count_min'. |
| 213 int idx = 0; |
| 214 int j; |
| 215 for (j = 0; j < histogram_size; ++j) { |
| 216 if (histogram[j] != 0) { |
| 217 const int count = |
| 218 (histogram[j] < count_min) ? count_min : histogram[j]; |
| 219 tree[idx].total_count_ = count; |
| 220 tree[idx].value_ = j; |
| 221 tree[idx].pool_index_left_ = -1; |
| 222 tree[idx].pool_index_right_ = -1; |
| 223 ++idx; |
| 224 } |
| 225 } |
| 226 |
| 227 // Build the Huffman tree. |
| 228 qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees); |
| 229 |
| 230 if (tree_size > 1) { // Normal case. |
| 231 int tree_pool_size = 0; |
| 232 while (tree_size > 1) { // Finish when we have only one root. |
| 233 int count; |
| 234 tree_pool[tree_pool_size++] = tree[tree_size - 1]; |
| 235 tree_pool[tree_pool_size++] = tree[tree_size - 2]; |
| 236 count = tree_pool[tree_pool_size - 1].total_count_ + |
| 237 tree_pool[tree_pool_size - 2].total_count_; |
| 238 tree_size -= 2; |
| 239 { |
| 240 // Search for the insertion point. |
| 241 int k; |
| 242 for (k = 0; k < tree_size; ++k) { |
| 243 if (tree[k].total_count_ <= count) { |
| 244 break; |
| 245 } |
| 246 } |
| 247 memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree)); |
| 248 tree[k].total_count_ = count; |
| 249 tree[k].value_ = -1; |
| 250 |
| 251 tree[k].pool_index_left_ = tree_pool_size - 1; |
| 252 tree[k].pool_index_right_ = tree_pool_size - 2; |
| 253 tree_size = tree_size + 1; |
| 254 } |
| 255 } |
| 256 SetBitDepths(&tree[0], tree_pool, bit_depths, 0); |
| 257 } else if (tree_size == 1) { // Trivial case: only one element. |
| 258 bit_depths[tree[0].value_] = 1; |
| 259 } |
| 260 |
| 261 { |
| 262 // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria. |
| 263 int max_depth = bit_depths[0]; |
| 264 for (j = 1; j < histogram_size; ++j) { |
| 265 if (max_depth < bit_depths[j]) { |
| 266 max_depth = bit_depths[j]; |
| 267 } |
| 268 } |
| 269 if (max_depth <= tree_depth_limit) { |
| 270 break; |
| 271 } |
| 272 } |
| 273 } |
| 274 free(tree); |
| 275 return 1; |
| 276 } |
| 277 |
| 278 // ----------------------------------------------------------------------------- |
| 279 // Coding of the Huffman tree values |
| 280 |
| 281 static HuffmanTreeToken* CodeRepeatedValues(int repetitions, |
| 282 HuffmanTreeToken* tokens, |
| 283 int value, int prev_value) { |
| 284 assert(value <= MAX_ALLOWED_CODE_LENGTH); |
| 285 if (value != prev_value) { |
| 286 tokens->code = value; |
| 287 tokens->extra_bits = 0; |
| 288 ++tokens; |
| 289 --repetitions; |
| 290 } |
| 291 while (repetitions >= 1) { |
| 292 if (repetitions < 3) { |
| 293 int i; |
| 294 for (i = 0; i < repetitions; ++i) { |
| 295 tokens->code = value; |
| 296 tokens->extra_bits = 0; |
| 297 ++tokens; |
| 298 } |
| 299 break; |
| 300 } else if (repetitions < 7) { |
| 301 tokens->code = 16; |
| 302 tokens->extra_bits = repetitions - 3; |
| 303 ++tokens; |
| 304 break; |
| 305 } else { |
| 306 tokens->code = 16; |
| 307 tokens->extra_bits = 3; |
| 308 ++tokens; |
| 309 repetitions -= 6; |
| 310 } |
| 311 } |
| 312 return tokens; |
| 313 } |
| 314 |
| 315 static HuffmanTreeToken* CodeRepeatedZeros(int repetitions, |
| 316 HuffmanTreeToken* tokens) { |
| 317 while (repetitions >= 1) { |
| 318 if (repetitions < 3) { |
| 319 int i; |
| 320 for (i = 0; i < repetitions; ++i) { |
| 321 tokens->code = 0; // 0-value |
| 322 tokens->extra_bits = 0; |
| 323 ++tokens; |
| 324 } |
| 325 break; |
| 326 } else if (repetitions < 11) { |
| 327 tokens->code = 17; |
| 328 tokens->extra_bits = repetitions - 3; |
| 329 ++tokens; |
| 330 break; |
| 331 } else if (repetitions < 139) { |
| 332 tokens->code = 18; |
| 333 tokens->extra_bits = repetitions - 11; |
| 334 ++tokens; |
| 335 break; |
| 336 } else { |
| 337 tokens->code = 18; |
| 338 tokens->extra_bits = 0x7f; // 138 repeated 0s |
| 339 ++tokens; |
| 340 repetitions -= 138; |
| 341 } |
| 342 } |
| 343 return tokens; |
| 344 } |
| 345 |
| 346 int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, |
| 347 HuffmanTreeToken* tokens, int max_tokens) { |
| 348 HuffmanTreeToken* const starting_token = tokens; |
| 349 HuffmanTreeToken* const ending_token = tokens + max_tokens; |
| 350 const int depth_size = tree->num_symbols; |
| 351 int prev_value = 8; // 8 is the initial value for rle. |
| 352 int i = 0; |
| 353 assert(tokens != NULL); |
| 354 while (i < depth_size) { |
| 355 const int value = tree->code_lengths[i]; |
| 356 int k = i + 1; |
| 357 int runs; |
| 358 while (k < depth_size && tree->code_lengths[k] == value) ++k; |
| 359 runs = k - i; |
| 360 if (value == 0) { |
| 361 tokens = CodeRepeatedZeros(runs, tokens); |
| 362 } else { |
| 363 tokens = CodeRepeatedValues(runs, tokens, value, prev_value); |
| 364 prev_value = value; |
| 365 } |
| 366 i += runs; |
| 367 assert(tokens <= ending_token); |
| 368 } |
| 369 (void)ending_token; // suppress 'unused variable' warning |
| 370 return (int)(tokens - starting_token); |
| 371 } |
| 372 |
| 373 // ----------------------------------------------------------------------------- |
| 374 |
| 375 // Pre-reversed 4-bit values. |
| 376 static const uint8_t kReversedBits[16] = { |
| 377 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, |
| 378 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf |
| 379 }; |
| 380 |
| 381 static uint32_t ReverseBits(int num_bits, uint32_t bits) { |
| 382 uint32_t retval = 0; |
| 383 int i = 0; |
| 384 while (i < num_bits) { |
| 385 i += 4; |
| 386 retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i); |
| 387 bits >>= 4; |
| 388 } |
| 389 retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits); |
| 390 return retval; |
| 391 } |
| 392 |
| 393 // Get the actual bit values for a tree of bit depths. |
| 394 static void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) { |
| 395 // 0 bit-depth means that the symbol does not exist. |
| 396 int i; |
| 397 int len; |
| 398 uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1]; |
| 399 int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; |
| 400 |
| 401 assert(tree != NULL); |
| 402 len = tree->num_symbols; |
| 403 for (i = 0; i < len; ++i) { |
| 404 const int code_length = tree->code_lengths[i]; |
| 405 assert(code_length <= MAX_ALLOWED_CODE_LENGTH); |
| 406 ++depth_count[code_length]; |
| 407 } |
| 408 depth_count[0] = 0; // ignore unused symbol |
| 409 next_code[0] = 0; |
| 410 { |
| 411 uint32_t code = 0; |
| 412 for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) { |
| 413 code = (code + depth_count[i - 1]) << 1; |
| 414 next_code[i] = code; |
| 415 } |
| 416 } |
| 417 for (i = 0; i < len; ++i) { |
| 418 const int code_length = tree->code_lengths[i]; |
| 419 tree->codes[i] = ReverseBits(code_length, next_code[code_length]++); |
| 420 } |
| 421 } |
| 422 |
| 423 // ----------------------------------------------------------------------------- |
| 424 // Main entry point |
| 425 |
| 426 int VP8LCreateHuffmanTree(int* const histogram, int tree_depth_limit, |
| 427 HuffmanTreeCode* const tree) { |
| 428 const int num_symbols = tree->num_symbols; |
| 429 if (!OptimizeHuffmanForRle(num_symbols, histogram)) { |
| 430 return 0; |
| 431 } |
| 432 if (!GenerateOptimalTree(histogram, num_symbols, |
| 433 tree_depth_limit, tree->code_lengths)) { |
| 434 return 0; |
| 435 } |
| 436 // Create the actual bit codes for the bit lengths. |
| 437 ConvertBitDepthsToSymbols(tree); |
| 438 return 1; |
| 439 } |
OLD | NEW |