BaseTools/Source/C/BrotliCompress/enc/entropy_encode.c

   1 /* Copyright 2010 Google Inc. All Rights Reserved.
   2
   3    Distributed under MIT license.
   4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   5 */
   6
   7 /* Entropy encoding (Huffman) utilities. */
   8
   9 #include "./entropy_encode.h"
  10
  11 #include <string.h>  /* memset */
  12
  13 #include "../common/constants.h"
  14 #include "../common/types.h"
  15 #include "./port.h"
  16
  17 #if defined(__cplusplus) || defined(c_plusplus)
  18 extern "C" {
  19 #endif
  20
  21 BROTLI_BOOL BrotliSetDepth(
  22     int p0, HuffmanTree* pool, uint8_t* depth, int max_depth) {
  23   int stack[16];
  24   int level = 0;
  25   int p = p0;
  26   assert(max_depth <= 15);
  27   stack[0] = -1;
  28   while (BROTLI_TRUE) {
  29     if (pool[p].index_left_ >= 0) {
  30       level++;
  31       if (level > max_depth) return BROTLI_FALSE;
  32       stack[level] = pool[p].index_right_or_value_;
  33       p = pool[p].index_left_;
  34       continue;
  35     } else {
  36       depth[pool[p].index_right_or_value_] = (uint8_t)level;
  37     }
  38     while (level >= 0 && stack[level] == -1) level--;
  39     if (level < 0) return BROTLI_TRUE;
  40     p = stack[level];
  41     stack[level] = -1;
  42   }
  43 }
  44
  45 /* Sort the root nodes, least popular first. */
  46 static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree(
  47     const HuffmanTree* v0, const HuffmanTree* v1) {
  48   if (v0->total_count_ != v1->total_count_) {
  49     return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_);
  50   }
  51   return TO_BROTLI_BOOL(v0->index_right_or_value_ > v1->index_right_or_value_);
  52 }
  53
  54 /* This function will create a Huffman tree.
  55
  56    The catch here is that the tree cannot be arbitrarily deep.
  57    Brotli specifies a maximum depth of 15 bits for "code trees"
  58    and 7 bits for "code length code trees."
  59
  60    count_limit is the value that is to be faked as the minimum value
  61    and this minimum value is raised until the tree matches the
  62    maximum length requirement.
  63
  64    This algorithm is not of excellent performance for very long data blocks,
  65    especially when population counts are longer than 2**tree_limit, but
  66    we are not planning to use this with extremely long blocks.
  67
  68    See http://en.wikipedia.org/wiki/Huffman_coding */
  69 void BrotliCreateHuffmanTree(const uint32_t *data,
  70                              const size_t length,
  71                              const int tree_limit,
  72                              HuffmanTree* tree,
  73                              uint8_t *depth) {
  74   uint32_t count_limit;
  75   HuffmanTree sentinel;
  76   InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1);
  77   /* For block sizes below 64 kB, we never need to do a second iteration
  78      of this loop. Probably all of our block sizes will be smaller than
  79      that, so this loop is mostly of academic interest. If we actually
  80      would need this, we would be better off with the Katajainen algorithm. */
  81   for (count_limit = 1; ; count_limit *= 2) {
  82     size_t n = 0;
  83     size_t i;
  84     size_t j;
  85     size_t k;
  86     for (i = length; i != 0;) {
  87       --i;
  88       if (data[i]) {
  89         const uint32_t count = BROTLI_MAX(uint32_t, data[i], count_limit);
  90         InitHuffmanTree(&tree[n++], count, -1, (int16_t)i);
  91       }
  92     }
  93
  94     if (n == 1) {
  95       depth[tree[0].index_right_or_value_] = 1;  /* Only one element. */
  96       break;
  97     }
  98
  99     SortHuffmanTreeItems(tree, n, SortHuffmanTree);
 100
 101     /* The nodes are:
 102        [0, n): the sorted leaf nodes that we start with.
 103        [n]: we add a sentinel here.
 104        [n + 1, 2n): new parent nodes are added here, starting from
 105                     (n+1). These are naturally in ascending order.
 106        [2n]: we add a sentinel at the end as well.
 107        There will be (2n+1) elements at the end. */
 108     tree[n] = sentinel;
 109     tree[n + 1] = sentinel;
 110
 111     i = 0;      /* Points to the next leaf node. */
 112     j = n + 1;  /* Points to the next non-leaf node. */
 113     for (k = n - 1; k != 0; --k) {
 114       size_t left, right;
 115       if (tree[i].total_count_ <= tree[j].total_count_) {
 116         left = i;
 117         ++i;
 118       } else {
 119         left = j;
 120         ++j;
 121       }
 122       if (tree[i].total_count_ <= tree[j].total_count_) {
 123         right = i;
 124         ++i;
 125       } else {
 126         right = j;
 127         ++j;
 128       }
 129
 130       {
 131         /* The sentinel node becomes the parent node. */
 132         size_t j_end = 2 * n - k;
 133         tree[j_end].total_count_ =
 134             tree[left].total_count_ + tree[right].total_count_;
 135         tree[j_end].index_left_ = (int16_t)left;
 136         tree[j_end].index_right_or_value_ = (int16_t)right;
 137
 138         /* Add back the last sentinel node. */
 139         tree[j_end + 1] = sentinel;
 140       }
 141     }
 142     if (BrotliSetDepth((int)(2 * n - 1), &tree[0], depth, tree_limit)) {
 143       /* We need to pack the Huffman tree in tree_limit bits. If this was not
 144          successful, add fake entities to the lowest values and retry. */
 145       break;
 146     }
 147   }
 148 }
 149
 150 static void Reverse(uint8_t* v, size_t start, size_t end) {
 151   --end;
 152   while (start < end) {
 153     uint8_t tmp = v[start];
 154     v[start] = v[end];
 155     v[end] = tmp;
 156     ++start;
 157     --end;
 158   }
 159 }
 160
 161 static void BrotliWriteHuffmanTreeRepetitions(
 162     const uint8_t previous_value,
 163     const uint8_t value,
 164     size_t repetitions,
 165     size_t* tree_size,
 166     uint8_t* tree,
 167     uint8_t* extra_bits_data) {
 168   assert(repetitions > 0);
 169   if (previous_value != value) {
 170     tree[*tree_size] = value;
 171     extra_bits_data[*tree_size] = 0;
 172     ++(*tree_size);
 173     --repetitions;
 174   }
 175   if (repetitions == 7) {
 176     tree[*tree_size] = value;
 177     extra_bits_data[*tree_size] = 0;
 178     ++(*tree_size);
 179     --repetitions;
 180   }
 181   if (repetitions < 3) {
 182     size_t i;
 183     for (i = 0; i < repetitions; ++i) {
 184       tree[*tree_size] = value;
 185       extra_bits_data[*tree_size] = 0;
 186       ++(*tree_size);
 187     }
 188   } else {
 189     size_t start = *tree_size;
 190     repetitions -= 3;
 191     while (BROTLI_TRUE) {
 192       tree[*tree_size] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH;
 193       extra_bits_data[*tree_size] = repetitions & 0x3;
 194       ++(*tree_size);
 195       repetitions >>= 2;
 196       if (repetitions == 0) {
 197         break;
 198       }
 199       --repetitions;
 200     }
 201     Reverse(tree, start, *tree_size);
 202     Reverse(extra_bits_data, start, *tree_size);
 203   }
 204 }
 205
 206 static void BrotliWriteHuffmanTreeRepetitionsZeros(
 207     size_t repetitions,
 208     size_t* tree_size,
 209     uint8_t* tree,
 210     uint8_t* extra_bits_data) {
 211   if (repetitions == 11) {
 212     tree[*tree_size] = 0;
 213     extra_bits_data[*tree_size] = 0;
 214     ++(*tree_size);
 215     --repetitions;
 216   }
 217   if (repetitions < 3) {
 218     size_t i;
 219     for (i = 0; i < repetitions; ++i) {
 220       tree[*tree_size] = 0;
 221       extra_bits_data[*tree_size] = 0;
 222       ++(*tree_size);
 223     }
 224   } else {
 225     size_t start = *tree_size;
 226     repetitions -= 3;
 227     while (BROTLI_TRUE) {
 228       tree[*tree_size] = BROTLI_REPEAT_ZERO_CODE_LENGTH;
 229       extra_bits_data[*tree_size] = repetitions & 0x7;
 230       ++(*tree_size);
 231       repetitions >>= 3;
 232       if (repetitions == 0) {
 233         break;
 234       }
 235       --repetitions;
 236     }
 237     Reverse(tree, start, *tree_size);
 238     Reverse(extra_bits_data, start, *tree_size);
 239   }
 240 }
 241
 242 void BrotliOptimizeHuffmanCountsForRle(size_t length, uint32_t* counts,
 243                                        uint8_t* good_for_rle) {
 244   size_t nonzero_count = 0;
 245   size_t stride;
 246   size_t limit;
 247   size_t sum;
 248   const size_t streak_limit = 1240;
 249   /* Let's make the Huffman code more compatible with rle encoding. */
 250   size_t i;
 251   for (i = 0; i < length; i++) {
 252     if (counts[i]) {
 253       ++nonzero_count;
 254     }
 255   }
 256   if (nonzero_count < 16) {
 257     return;
 258   }
 259   while (length != 0 && counts[length - 1] == 0) {
 260     --length;
 261   }
 262   if (length == 0) {
 263     return;  /* All zeros. */
 264   }
 265   /* Now counts[0..length - 1] does not have trailing zeros. */
 266   {
 267     size_t nonzeros = 0;
 268     uint32_t smallest_nonzero = 1 << 30;
 269     for (i = 0; i < length; ++i) {
 270       if (counts[i] != 0) {
 271         ++nonzeros;
 272         if (smallest_nonzero > counts[i]) {
 273           smallest_nonzero = counts[i];
 274         }
 275       }
 276     }
 277     if (nonzeros < 5) {
 278       /* Small histogram will model it well. */
 279       return;
 280     }
 281     if (smallest_nonzero < 4) {
 282       size_t zeros = length - nonzeros;
 283       if (zeros < 6) {
 284         for (i = 1; i < length - 1; ++i) {
 285           if (counts[i - 1] != 0 && counts[i] == 0 && counts[i + 1] != 0) {
 286             counts[i] = 1;
 287           }
 288         }
 289       }
 290     }
 291     if (nonzeros < 28) {
 292       return;
 293     }
 294   }
 295   /* 2) Let's mark all population counts that already can be encoded
 296      with an rle code. */
 297   memset(good_for_rle, 0, length);
 298   {
 299     /* Let's not spoil any of the existing good rle codes.
 300        Mark any seq of 0's that is longer as 5 as a good_for_rle.
 301        Mark any seq of non-0's that is longer as 7 as a good_for_rle. */
 302     uint32_t symbol = counts[0];
 303     size_t step = 0;
 304     for (i = 0; i <= length; ++i) {
 305       if (i == length || counts[i] != symbol) {
 306         if ((symbol == 0 && step >= 5) ||
 307             (symbol != 0 && step >= 7)) {
 308           size_t k;
 309           for (k = 0; k < step; ++k) {
 310             good_for_rle[i - k - 1] = 1;
 311           }
 312         }
 313         step = 1;
 314         if (i != length) {
 315           symbol = counts[i];
 316         }
 317       } else {
 318         ++step;
 319       }
 320     }
 321   }
 322   /* 3) Let's replace those population counts that lead to more rle codes.
 323      Math here is in 24.8 fixed point representation. */
 324   stride = 0;
 325   limit = 256 * (counts[0] + counts[1] + counts[2]) / 3 + 420;
 326   sum = 0;
 327   for (i = 0; i <= length; ++i) {
 328     if (i == length || good_for_rle[i] ||
 329         (i != 0 && good_for_rle[i - 1]) ||
 330         (256 * counts[i] - limit + streak_limit) >= 2 * streak_limit) {
 331       if (stride >= 4 || (stride >= 3 && sum == 0)) {
 332         size_t k;
 333         /* The stride must end, collapse what we have, if we have enough (4). */
 334         size_t count = (sum + stride / 2) / stride;
 335         if (count == 0) {
 336           count = 1;
 337         }
 338         if (sum == 0) {
 339           /* Don't make an all zeros stride to be upgraded to ones. */
 340           count = 0;
 341         }
 342         for (k = 0; k < stride; ++k) {
 343           /* We don't want to change value at counts[i],
 344              that is already belonging to the next stride. Thus - 1. */
 345           counts[i - k - 1] = (uint32_t)count;
 346         }
 347       }
 348       stride = 0;
 349       sum = 0;
 350       if (i < length - 2) {
 351         /* All interesting strides have a count of at least 4, */
 352         /* at least when non-zeros. */
 353         limit = 256 * (counts[i] + counts[i + 1] + counts[i + 2]) / 3 + 420;
 354       } else if (i < length) {
 355         limit = 256 * counts[i];
 356       } else {
 357         limit = 0;
 358       }
 359     }
 360     ++stride;
 361     if (i != length) {
 362       sum += counts[i];
 363       if (stride >= 4) {
 364         limit = (256 * sum + stride / 2) / stride;
 365       }
 366       if (stride == 4) {
 367         limit += 120;
 368       }
 369     }
 370   }
 371 }
 372
 373 static void DecideOverRleUse(const uint8_t* depth, const size_t length,
 374                              BROTLI_BOOL *use_rle_for_non_zero,
 375                              BROTLI_BOOL *use_rle_for_zero) {
 376   size_t total_reps_zero = 0;
 377   size_t total_reps_non_zero = 0;
 378   size_t count_reps_zero = 1;
 379   size_t count_reps_non_zero = 1;
 380   size_t i;
 381   for (i = 0; i < length;) {
 382     const uint8_t value = depth[i];
 383     size_t reps = 1;
 384     size_t k;
 385     for (k = i + 1; k < length && depth[k] == value; ++k) {
 386       ++reps;
 387     }
 388     if (reps >= 3 && value == 0) {
 389       total_reps_zero += reps;
 390       ++count_reps_zero;
 391     }
 392     if (reps >= 4 && value != 0) {
 393       total_reps_non_zero += reps;
 394       ++count_reps_non_zero;
 395     }
 396     i += reps;
 397   }
 398   *use_rle_for_non_zero =
 399       TO_BROTLI_BOOL(total_reps_non_zero > count_reps_non_zero * 2);
 400   *use_rle_for_zero = TO_BROTLI_BOOL(total_reps_zero > count_reps_zero * 2);
 401 }
 402
 403 void BrotliWriteHuffmanTree(const uint8_t* depth,
 404                             size_t length,
 405                             size_t* tree_size,
 406                             uint8_t* tree,
 407                             uint8_t* extra_bits_data) {
 408   uint8_t previous_value = BROTLI_INITIAL_REPEATED_CODE_LENGTH;
 409   size_t i;
 410   BROTLI_BOOL use_rle_for_non_zero = BROTLI_FALSE;
 411   BROTLI_BOOL use_rle_for_zero = BROTLI_FALSE;
 412
 413   /* Throw away trailing zeros. */
 414   size_t new_length = length;
 415   for (i = 0; i < length; ++i) {
 416     if (depth[length - i - 1] == 0) {
 417       --new_length;
 418     } else {
 419       break;
 420     }
 421   }
 422
 423   /* First gather statistics on if it is a good idea to do rle. */
 424   if (length > 50) {
 425     /* Find rle coding for longer codes.
 426        Shorter codes seem not to benefit from rle. */
 427     DecideOverRleUse(depth, new_length,
 428                      &use_rle_for_non_zero, &use_rle_for_zero);
 429   }
 430
 431   /* Actual rle coding. */
 432   for (i = 0; i < new_length;) {
 433     const uint8_t value = depth[i];
 434     size_t reps = 1;
 435     if ((value != 0 && use_rle_for_non_zero) ||
 436         (value == 0 && use_rle_for_zero)) {
 437       size_t k;
 438       for (k = i + 1; k < new_length && depth[k] == value; ++k) {
 439         ++reps;
 440       }
 441     }
 442     if (value == 0) {
 443       BrotliWriteHuffmanTreeRepetitionsZeros(
 444           reps, tree_size, tree, extra_bits_data);
 445     } else {
 446       BrotliWriteHuffmanTreeRepetitions(previous_value,
 447                                         value, reps, tree_size,
 448                                         tree, extra_bits_data);
 449       previous_value = value;
 450     }
 451     i += reps;
 452   }
 453 }
 454
 455 static uint16_t BrotliReverseBits(size_t num_bits, uint16_t bits) {
 456   static const size_t kLut[16] = {  /* Pre-reversed 4-bit values. */
 457     0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
 458     0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
 459   };
 460   size_t retval = kLut[bits & 0xf];
 461   size_t i;
 462   for (i = 4; i < num_bits; i += 4) {
 463     retval <<= 4;
 464     bits = (uint16_t)(bits >> 4);
 465     retval |= kLut[bits & 0xf];
 466   }
 467   retval >>= ((0 - num_bits) & 0x3);
 468   return (uint16_t)retval;
 469 }
 470
 471 /* 0..15 are values for bits */
 472 #define MAX_HUFFMAN_BITS 16
 473
 474 void BrotliConvertBitDepthsToSymbols(const uint8_t *depth,
 475                                      size_t len,
 476                                      uint16_t *bits) {
 477   /* In Brotli, all bit depths are [1..15]
 478      0 bit depth means that the symbol does not exist. */
 479   uint16_t bl_count[MAX_HUFFMAN_BITS] = { 0 };
 480   uint16_t next_code[MAX_HUFFMAN_BITS];
 481   size_t i;
 482   int code = 0;
 483   for (i = 0; i < len; ++i) {
 484     ++bl_count[depth[i]];
 485   }
 486   bl_count[0] = 0;
 487   next_code[0] = 0;
 488   for (i = 1; i < MAX_HUFFMAN_BITS; ++i) {
 489     code = (code + bl_count[i - 1]) << 1;
 490     next_code[i] = (uint16_t)code;
 491   }
 492   for (i = 0; i < len; ++i) {
 493     if (depth[i]) {
 494       bits[i] = BrotliReverseBits(depth[i], next_code[depth[i]]++);
 495     }
 496   }
 497 }
 498
 499 #if defined(__cplusplus) || defined(c_plusplus)
 500 }  /* extern "C" */
 501 #endif