third_party/brotli/dec/huffman.c

   1 /* Copyright 2013 Google Inc. All Rights Reserved.
   2
   3    Licensed under the Apache License, Version 2.0 (the "License");
   4    you may not use this file except in compliance with the License.
   5    You may obtain a copy of the License at
   6
   7    http://www.apache.org/licenses/LICENSE-2.0
   8
   9    Unless required by applicable law or agreed to in writing, software
  10    distributed under the License is distributed on an "AS IS" BASIS,
  11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    See the License for the specific language governing permissions and
  13    limitations under the License.
  14
  15    Utilities for building Huffman decoding tables.
  16 */
  17
  18 #include <assert.h>
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <string.h>
  22 #include "./huffman.h"
  23 #include "./safe_malloc.h"
  24
  25 #if defined(__cplusplus) || defined(c_plusplus)
  26 extern "C" {
  27 #endif
  28
  29 #define MAX_LENGTH 15
  30
  31 /* Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
  32    bit-wise reversal of the len least significant bits of key. */
  33 static BROTLI_INLINE int GetNextKey(int key, int len) {
  34   int step = 1 << (len - 1);
  35   while (key & step) {
  36     step >>= 1;
  37   }
  38   return (key & (step - 1)) + step;
  39 }
  40
  41 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
  42 /* Assumes that end is an integer multiple of step */
  43 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
  44                                          int step, int end,
  45                                          HuffmanCode code) {
  46   do {
  47     end -= step;
  48     table[end] = code;
  49   } while (end > 0);
  50 }
  51
  52 /* Returns the table width of the next 2nd level table. count is the histogram
  53    of bit lengths for the remaining symbols, len is the code length of the next
  54    processed symbol */
  55 static BROTLI_INLINE int NextTableBitSize(const int* const count,
  56                                           int len, int root_bits) {
  57   int left = 1 << (len - root_bits);
  58   while (len < MAX_LENGTH) {
  59     left -= count[len];
  60     if (left <= 0) break;
  61     ++len;
  62     left <<= 1;
  63   }
  64   return len - root_bits;
  65 }
  66
  67 int BrotliBuildHuffmanTable(HuffmanCode* root_table,
  68                             int root_bits,
  69                             const uint8_t* const code_lengths,
  70                             int code_lengths_size) {
  71   HuffmanCode code;    /* current table entry */
  72   HuffmanCode* table;  /* next available space in table */
  73   int len;             /* current code length */
  74   int symbol;          /* symbol index in original or sorted table */
  75   int key;             /* reversed prefix code */
  76   int step;            /* step size to replicate values in current table */
  77   int low;             /* low bits for current root entry */
  78   int mask;            /* mask for low bits */
  79   int table_bits;      /* key length of current table */
  80   int table_size;      /* size of current table */
  81   int total_size;      /* sum of root table size and 2nd level table sizes */
  82   int* sorted;         /* symbols sorted by code length */
  83   int count[MAX_LENGTH + 1] = { 0 };  /* number of codes of each length */
  84   int offset[MAX_LENGTH + 1];  /* offsets in sorted table for each length */
  85
  86   sorted = (int*)malloc((size_t)code_lengths_size * sizeof(*sorted));
  87   if (sorted == NULL) {
  88     return 0;
  89   }
  90
  91   /* build histogram of code lengths */
  92   for (symbol = 0; symbol < code_lengths_size; symbol++) {
  93     count[code_lengths[symbol]]++;
  94   }
  95
  96   /* generate offsets into sorted symbol table by code length */
  97   offset[1] = 0;
  98   for (len = 1; len < MAX_LENGTH; len++) {
  99     offset[len + 1] = offset[len] + count[len];
 100   }
 101
 102   /* sort symbols by length, by symbol order within each length */
 103   for (symbol = 0; symbol < code_lengths_size; symbol++) {
 104     if (code_lengths[symbol] != 0) {
 105       sorted[offset[code_lengths[symbol]]++] = symbol;
 106     }
 107   }
 108
 109   table = root_table;
 110   table_bits = root_bits;
 111   table_size = 1 << table_bits;
 112   total_size = table_size;
 113
 114   /* special case code with only one value */
 115   if (offset[MAX_LENGTH] == 1) {
 116     code.bits = 0;
 117     code.value = (uint16_t)sorted[0];
 118     for (key = 0; key < total_size; ++key) {
 119       table[key] = code;
 120     }
 121     free(sorted);
 122     return total_size;
 123   }
 124
 125   /* fill in root table */
 126   key = 0;
 127   symbol = 0;
 128   for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
 129     for (; count[len] > 0; --count[len]) {
 130       code.bits = (uint8_t)(len);
 131       code.value = (uint16_t)sorted[symbol++];
 132       ReplicateValue(&table[key], step, table_size, code);
 133       key = GetNextKey(key, len);
 134     }
 135   }
 136
 137   /* fill in 2nd level tables and add pointers to root table */
 138   mask = total_size - 1;
 139   low = -1;
 140   for (len = root_bits + 1, step = 2; len <= MAX_LENGTH; ++len, step <<= 1) {
 141     for (; count[len] > 0; --count[len]) {
 142       if ((key & mask) != low) {
 143         table += table_size;
 144         table_bits = NextTableBitSize(count, len, root_bits);
 145         table_size = 1 << table_bits;
 146         total_size += table_size;
 147         low = key & mask;
 148         root_table[low].bits = (uint8_t)(table_bits + root_bits);
 149         root_table[low].value = (uint16_t)((table - root_table) - low);
 150       }
 151       code.bits = (uint8_t)(len - root_bits);
 152       code.value = (uint16_t)sorted[symbol++];
 153       ReplicateValue(&table[key >> root_bits], step, table_size, code);
 154       key = GetNextKey(key, len);
 155     }
 156   }
 157
 158   free(sorted);
 159   return total_size;
 160 }
 161
 162 #if defined(__cplusplus) || defined(c_plusplus)
 163 }    /* extern "C" */
 164 #endif