Update brotli to v1.0.0-snapshot.

third_party/brotli/dec/huffman.c

 /* Copyright 2013 Google Inc. All Rights Reserved.
 
    Distributed under MIT license.
    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
 */
 
 /* Utilities for building Huffman decoding tables. */
 
 #include "./huffman.h"
 
 #include <string.h>  /* memcpy, memset */
 
+#include "../common/constants.h"
+#include <brotli/types.h>
 #include "./port.h"
-#include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
 #define BROTLI_REVERSE_BITS_MAX 8
 
 #ifdef BROTLI_RBIT
-#define BROTLI_REVERSE_BITS_BASE (32 - BROTLI_REVERSE_BITS_MAX)
+#define BROTLI_REVERSE_BITS_BASE \
+  ((sizeof(reg_t) << 3) - BROTLI_REVERSE_BITS_MAX)
 #else
 #define BROTLI_REVERSE_BITS_BASE 0
 static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = {
   0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
   0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
   0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
   0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
   0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
   0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
   0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
@@ skipping 19 matching lines @@
   0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
   0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
   0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
   0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
   0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
   0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
 };
 #endif  /* BROTLI_RBIT */
 
 #define BROTLI_REVERSE_BITS_LOWEST \
-  (1U << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
+  ((reg_t)1 << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
 
 /* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
    where reverse(value, len) is the bit-wise reversal of the len least
    significant bits of value. */
-static BROTLI_INLINE uint32_t BrotliReverseBits(uint32_t num) {
+static BROTLI_INLINE reg_t BrotliReverseBits(reg_t num) {
 #ifdef BROTLI_RBIT
   return BROTLI_RBIT(num);
 #else
   return kReverseBits[num];
 #endif
 }
 
 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
 /* Assumes that end is an integer multiple of step */
 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
@@ skipping 16 matching lines @@
     if (left <= 0) break;
     ++len;
     left <<= 1;
   }
   return len - root_bits;
 }
 
 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
                                         const uint8_t* const code_lengths,
                                         uint16_t* count) {
-  HuffmanCode code;   /* current table entry */
-  int symbol;         /* symbol index in original or sorted table */
-  uint32_t key;       /* prefix code */
-  uint32_t key_step;  /* prefix code addend */
-  int step;           /* step size to replicate values in current table */
-  int table_size;     /* size of current table */
-  int sorted[18];     /* symbols sorted by code length */
+  HuffmanCode code; /* current table entry */
+  int symbol;       /* symbol index in original or sorted table */
+  reg_t key;        /* prefix code */
+  reg_t key_step;   /* prefix code addend */
+  int step;         /* step size to replicate values in current table */
+  int table_size;   /* size of current table */
+  int sorted[BROTLI_CODE_LENGTH_CODES];  /* symbols sorted by code length */
   /* offsets in sorted table for each length */
   int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
   int bits;
   int bits_count;
   BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
                 BROTLI_REVERSE_BITS_MAX);
 
   /* generate offsets into sorted symbol table by code length */
   symbol = -1;
   bits = 1;
   BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
     symbol += count[bits];
     offset[bits] = symbol;
     bits++;
   });
   /* Symbols with code length 0 are placed after all other symbols. */
-  offset[0] = 17;
+  offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
 
   /* sort symbols by length, by symbol order within each length */
-  symbol = 18;
+  symbol = BROTLI_CODE_LENGTH_CODES;
   do {
     BROTLI_REPEAT(6, {
       symbol--;
       sorted[offset[code_lengths[symbol]]--] = symbol;
     });
   } while (symbol != 0);
 
   table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
 
   /* Special case: all symbols but one have 0 code length. */
   if (offset[0] == 0) {
     code.bits = 0;
     code.value = (uint16_t)sorted[0];
-    for (key = 0; key < (uint32_t)table_size; ++key) {
+    for (key = 0; key < (reg_t)table_size; ++key) {
       table[key] = code;
     }
     return;
   }
 
   /* fill in table */
   key = 0;
   key_step = BROTLI_REVERSE_BITS_LOWEST;
   symbol = 0;
   bits = 1;
   step = 2;
   do {
     code.bits = (uint8_t)bits;
     for (bits_count = count[bits]; bits_count != 0; --bits_count) {
       code.value = (uint16_t)sorted[symbol++];
       ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
       key += key_step;
     }
     step <<= 1;
     key_step >>= 1;
   } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
 }
 
 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
                                  int root_bits,
                                  const uint16_t* const symbol_lists,
                                  uint16_t* count) {
-  HuffmanCode code;       /* current table entry */
-  HuffmanCode* table;     /* next available space in table */
-  int len;                /* current code length */
-  int symbol;             /* symbol index in original or sorted table */
-  uint32_t key;           /* prefix code */
-  uint32_t key_step;      /* prefix code addend */
-  uint32_t sub_key;       /* 2nd level table prefix code */
-  uint32_t sub_key_step;  /* 2nd level table prefix code addend */
-  int step;               /* step size to replicate values in current table */
-  int table_bits;         /* key length of current table */
-  int table_size;         /* size of current table */
-  int total_size;         /* sum of root table size and 2nd level table sizes */
+  HuffmanCode code;    /* current table entry */
+  HuffmanCode* table;  /* next available space in table */
+  int len;             /* current code length */
+  int symbol;          /* symbol index in original or sorted table */
+  reg_t key;           /* prefix code */
+  reg_t key_step;      /* prefix code addend */
+  reg_t sub_key;       /* 2nd level table prefix code */
+  reg_t sub_key_step;  /* 2nd level table prefix code addend */
+  int step;            /* step size to replicate values in current table */
+  int table_bits;      /* key length of current table */
+  int table_size;      /* size of current table */
+  int total_size;      /* sum of root table size and 2nd level table sizes */
   int max_length = -1;
   int bits;
   int bits_count;
 
   BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
   BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
                 BROTLI_REVERSE_BITS_MAX);
 
   while (symbol_lists[max_length] == 0xFFFF) max_length--;
   max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
@@ skipping 152 matching lines @@
     memcpy(&table[table_size], &table[0],
            (size_t)table_size * sizeof(table[0]));
     table_size <<= 1;
   }
   return goal_size;
 }
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }  /* extern "C" */
 #endif