MdeModulePkg/Library/BrotliCustomDecompressLib/dec/huffman.c

   1 /* Copyright 2013 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 /* Utilities for building Huffman decoding tables. */
   8
   9 #include "./huffman.h"
  10
  11 //#include <string.h>  /* memcpy, 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 #define BROTLI_REVERSE_BITS_MAX 8
  22
  23 #ifdef BROTLI_RBIT
  24 #define BROTLI_REVERSE_BITS_BASE (32 - BROTLI_REVERSE_BITS_MAX)
  25 #else
  26 #define BROTLI_REVERSE_BITS_BASE 0
  27 static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = {
  28   0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
  29   0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  30   0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
  31   0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  32   0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
  33   0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  34   0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
  35   0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  36   0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
  37   0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  38   0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
  39   0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  40   0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
  41   0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  42   0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
  43   0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  44   0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
  45   0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  46   0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
  47   0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  48   0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
  49   0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  50   0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
  51   0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  52   0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
  53   0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  54   0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
  55   0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  56   0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
  57   0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  58   0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
  59   0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
  60 };
  61 #endif  /* BROTLI_RBIT */
  62
  63 #define BROTLI_REVERSE_BITS_LOWEST \
  64   (1U << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
  65
  66 /* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
  67    where reverse(value, len) is the bit-wise reversal of the len least
  68    significant bits of value. */
  69 static BROTLI_INLINE uint32_t BrotliReverseBits(uint32_t num) {
  70 #ifdef BROTLI_RBIT
  71   return BROTLI_RBIT(num);
  72 #else
  73   return kReverseBits[num];
  74 #endif
  75 }
  76
  77 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
  78 /* Assumes that end is an integer multiple of step */
  79 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
  80                                          int step, int end,
  81                                          HuffmanCode code) {
  82   do {
  83     end -= step;
  84     table[end] = code;
  85   } while (end > 0);
  86 }
  87
  88 /* Returns the table width of the next 2nd level table. count is the histogram
  89    of bit lengths for the remaining symbols, len is the code length of the next
  90    processed symbol */
  91 static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count,
  92                                           int len, int root_bits) {
  93   int left = 1 << (len - root_bits);
  94   while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) {
  95     left -= count[len];
  96     if (left <= 0) break;
  97     ++len;
  98     left <<= 1;
  99   }
 100   return len - root_bits;
 101 }
 102
 103 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
 104                                         const uint8_t* const code_lengths,
 105                                         uint16_t* count) {
 106   HuffmanCode code;   /* current table entry */
 107   int symbol;         /* symbol index in original or sorted table */
 108   uint32_t key;       /* prefix code */
 109   uint32_t key_step;  /* prefix code addend */
 110   int step;           /* step size to replicate values in current table */
 111   int table_size;     /* size of current table */
 112   int sorted[BROTLI_CODE_LENGTH_CODES];  /* symbols sorted by code length */
 113   /* offsets in sorted table for each length */
 114   int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
 115   int bits;
 116   int bits_count;
 117   BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
 118                 BROTLI_REVERSE_BITS_MAX);
 119
 120   /* generate offsets into sorted symbol table by code length */
 121   symbol = -1;
 122   bits = 1;
 123   BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
 124     symbol += count[bits];
 125     offset[bits] = symbol;
 126     bits++;
 127   });
 128   /* Symbols with code length 0 are placed after all other symbols. */
 129   offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
 130
 131   /* sort symbols by length, by symbol order within each length */
 132   symbol = BROTLI_CODE_LENGTH_CODES;
 133   do {
 134     BROTLI_REPEAT(6, {
 135       symbol--;
 136       sorted[offset[code_lengths[symbol]]--] = symbol;
 137     });
 138   } while (symbol != 0);
 139
 140   table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
 141
 142   /* Special case: all symbols but one have 0 code length. */
 143   if (offset[0] == 0) {
 144     code.bits = 0;
 145     code.value = (uint16_t)sorted[0];
 146     for (key = 0; key < (uint32_t)table_size; ++key) {
 147       table[key] = code;
 148     }
 149     return;
 150   }
 151
 152   /* fill in table */
 153   key = 0;
 154   key_step = BROTLI_REVERSE_BITS_LOWEST;
 155   symbol = 0;
 156   bits = 1;
 157   step = 2;
 158   do {
 159     code.bits = (uint8_t)bits;
 160     for (bits_count = count[bits]; bits_count != 0; --bits_count) {
 161       code.value = (uint16_t)sorted[symbol++];
 162       ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
 163       key += key_step;
 164     }
 165     step <<= 1;
 166     key_step >>= 1;
 167   } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
 168 }
 169
 170 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
 171                                  int root_bits,
 172                                  const uint16_t* const symbol_lists,
 173                                  uint16_t* count) {
 174   HuffmanCode code;       /* current table entry */
 175   HuffmanCode* table;     /* next available space in table */
 176   int len;                /* current code length */
 177   int symbol;             /* symbol index in original or sorted table */
 178   uint32_t key;           /* prefix code */
 179   uint32_t key_step;      /* prefix code addend */
 180   uint32_t sub_key;       /* 2nd level table prefix code */
 181   uint32_t sub_key_step;  /* 2nd level table prefix code addend */
 182   int step;               /* step size to replicate values in current table */
 183   int table_bits;         /* key length of current table */
 184   int table_size;         /* size of current table */
 185   int total_size;         /* sum of root table size and 2nd level table sizes */
 186   int max_length = -1;
 187   int bits;
 188   int bits_count;
 189
 190   BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
 191   BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
 192                 BROTLI_REVERSE_BITS_MAX);
 193
 194   while (symbol_lists[max_length] == 0xFFFF) max_length--;
 195   max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
 196
 197   table = root_table;
 198   table_bits = root_bits;
 199   table_size = 1 << table_bits;
 200   total_size = table_size;
 201
 202   /* fill in root table */
 203   /* let's reduce the table size to a smaller size if possible, and */
 204   /* create the repetitions by memcpy if possible in the coming loop */
 205   if (table_bits > max_length) {
 206     table_bits = max_length;
 207     table_size = 1 << table_bits;
 208   }
 209   key = 0;
 210   key_step = BROTLI_REVERSE_BITS_LOWEST;
 211   bits = 1;
 212   step = 2;
 213   do {
 214     code.bits = (uint8_t)bits;
 215     symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
 216     for (bits_count = count[bits]; bits_count != 0; --bits_count) {
 217       symbol = symbol_lists[symbol];
 218       code.value = (uint16_t)symbol;
 219       ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
 220       key += key_step;
 221     }
 222     step <<= 1;
 223     key_step >>= 1;
 224   } while (++bits <= table_bits);
 225
 226   /* if root_bits != table_bits we only created one fraction of the */
 227   /* table, and we need to replicate it now. */
 228   while (total_size != table_size) {
 229     memcpy(&table[table_size], &table[0],
 230            (size_t)table_size * sizeof(table[0]));
 231     table_size <<= 1;
 232   }
 233
 234   /* fill in 2nd level tables and add pointers to root table */
 235   key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
 236   sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1);
 237   sub_key_step = BROTLI_REVERSE_BITS_LOWEST;
 238   for (len = root_bits + 1, step = 2; len <= max_length; ++len) {
 239     symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
 240     for (; count[len] != 0; --count[len]) {
 241       if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) {
 242         table += table_size;
 243         table_bits = NextTableBitSize(count, len, root_bits);
 244         table_size = 1 << table_bits;
 245         total_size += table_size;
 246         sub_key = BrotliReverseBits(key);
 247         key += key_step;
 248         root_table[sub_key].bits = (uint8_t)(table_bits + root_bits);
 249         root_table[sub_key].value =
 250             (uint16_t)(((size_t)(table - root_table)) - sub_key);
 251         sub_key = 0;
 252       }
 253       code.bits = (uint8_t)(len - root_bits);
 254       symbol = symbol_lists[symbol];
 255       code.value = (uint16_t)symbol;
 256       ReplicateValue(
 257           &table[BrotliReverseBits(sub_key)], step, table_size, code);
 258       sub_key += sub_key_step;
 259     }
 260     step <<= 1;
 261     sub_key_step >>= 1;
 262   }
 263   return (uint32_t)total_size;
 264 }
 265
 266 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
 267                                        int root_bits,
 268                                        uint16_t* val,
 269                                        uint32_t num_symbols) {
 270   uint32_t table_size = 1;
 271   const uint32_t goal_size = 1U << root_bits;
 272   switch (num_symbols) {
 273     case 0:
 274       table[0].bits = 0;
 275       table[0].value = val[0];
 276       break;
 277     case 1:
 278       table[0].bits = 1;
 279       table[1].bits = 1;
 280       if (val[1] > val[0]) {
 281         table[0].value = val[0];
 282         table[1].value = val[1];
 283       } else {
 284         table[0].value = val[1];
 285         table[1].value = val[0];
 286       }
 287       table_size = 2;
 288       break;
 289     case 2:
 290       table[0].bits = 1;
 291       table[0].value = val[0];
 292       table[2].bits = 1;
 293       table[2].value = val[0];
 294       if (val[2] > val[1]) {
 295         table[1].value = val[1];
 296         table[3].value = val[2];
 297       } else {
 298         table[1].value = val[2];
 299         table[3].value = val[1];
 300       }
 301       table[1].bits = 2;
 302       table[3].bits = 2;
 303       table_size = 4;
 304       break;
 305     case 3: {
 306       int i, k;
 307       for (i = 0; i < 3; ++i) {
 308         for (k = i + 1; k < 4; ++k) {
 309           if (val[k] < val[i]) {
 310             uint16_t t = val[k];
 311             val[k] = val[i];
 312             val[i] = t;
 313           }
 314         }
 315       }
 316       for (i = 0; i < 4; ++i) {
 317         table[i].bits = 2;
 318       }
 319       table[0].value = val[0];
 320       table[2].value = val[1];
 321       table[1].value = val[2];
 322       table[3].value = val[3];
 323       table_size = 4;
 324       break;
 325     }
 326     case 4: {
 327       int i;
 328       if (val[3] < val[2]) {
 329         uint16_t t = val[3];
 330         val[3] = val[2];
 331         val[2] = t;
 332       }
 333       for (i = 0; i < 7; ++i) {
 334         table[i].value = val[0];
 335         table[i].bits = (uint8_t)(1 + (i & 1));
 336       }
 337       table[1].value = val[1];
 338       table[3].value = val[2];
 339       table[5].value = val[1];
 340       table[7].value = val[3];
 341       table[3].bits = 3;
 342       table[7].bits = 3;
 343       table_size = 8;
 344       break;
 345     }
 346   }
 347   while (table_size != goal_size) {
 348     memcpy(&table[table_size], &table[0],
 349            (size_t)table_size * sizeof(table[0]));
 350     table_size <<= 1;
 351   }
 352   return goal_size;
 353 }
 354
 355 #if defined(__cplusplus) || defined(c_plusplus)
 356 }  /* extern "C" */
 357 #endif