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