Update (#826)

 * IMPORTANT: decoder: fix potential overflow when input chunk is >2GiB
 * simplify max Huffman table size calculation
 * eliminate symbol duplicates (static arrays in .h files)
 * minor combing in research/ code

6 files changed, 29 insertions, 45 deletions

diff --git a/c/dec/bit_reader.c b/c/dec/bit_reader.c
index 41cd050..7f7b256 100644
--- a/c/dec/bit_reader.c
+++ b/c/dec/bit_reader.c
@@ -15,6 +15,17 @@
 extern "C" {
 #endif
 
+const uint32_t kBrotliBitMask[33] = {   0x00000000,
+    0x00000001, 0x00000003, 0x00000007, 0x0000000F,
+    0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
+    0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
+    0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
+    0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
+    0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
+    0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
+    0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
+};
+
 void BrotliInitBitReader(BrotliBitReader* const br) {
   br->val_ = 0;
   br->bit_pos_ = sizeof(br->val_) << 3;
diff --git a/c/dec/bit_reader.h b/c/dec/bit_reader.h
index f94a717..22bc060 100644
--- a/c/dec/bit_reader.h
+++ b/c/dec/bit_reader.h
@@ -11,6 +11,7 @@
 
 #include <string.h>  /* memcpy */
 
+#include "../common/constants.h"
 #include "../common/platform.h"
 #include <brotli/types.h>
 
@@ -20,16 +21,7 @@ extern "C" {
 
 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1)
 
-static const uint32_t kBitMask[33] = {  0x00000000,
-    0x00000001, 0x00000003, 0x00000007, 0x0000000F,
-    0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
-    0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
-    0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
-    0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
-    0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
-    0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
-    0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
-};
+BROTLI_INTERNAL extern const uint32_t kBrotliBitMask[33];
 
 static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
   if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
@@ -37,7 +29,7 @@ static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
        "Unsigned Bit Field Extract" UBFX instruction on ARM. */
     return ~((0xFFFFFFFFu) << n);
   } else {
-    return kBitMask[n];
+    return kBrotliBitMask[n];
   }
 }
 
@@ -93,8 +85,11 @@ static BROTLI_INLINE uint32_t BrotliGetAvailableBits(
 }
 
 /* Returns amount of unread bytes the bit reader still has buffered from the
-   BrotliInput, including whole bytes in br->val_. */
+   BrotliInput, including whole bytes in br->val_. Result is capped with
+   maximal ring-buffer size (larger number won't be utilized anyway). */
 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
+  static const size_t kCap = (size_t)1 << BROTLI_LARGE_MAX_WBITS;
+  if (br->avail_in > kCap) return kCap;
   return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
 }
 
diff --git a/c/dec/decode.c b/c/dec/decode.c
index 9cdbb57..ae5a3d3 100644
--- a/c/dec/decode.c
+++ b/c/dec/decode.c
@@ -875,8 +875,8 @@ static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table,
   uint32_t code;
   uint32_t nbits;
   code = ReadSymbol(table, br);
-  nbits = kBlockLengthPrefixCode[code].nbits;  /* nbits == 2..24 */
-  return kBlockLengthPrefixCode[code].offset + BrotliReadBits24(br, nbits);
+  nbits = _kBrotliPrefixCodeRanges[code].nbits;  /* nbits == 2..24 */
+  return _kBrotliPrefixCodeRanges[code].offset + BrotliReadBits24(br, nbits);
 }
 
 /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
@@ -894,13 +894,14 @@ static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength(
   }
   {
     uint32_t bits;
-    uint32_t nbits = kBlockLengthPrefixCode[index].nbits;  /* nbits == 2..24 */
+    uint32_t nbits = _kBrotliPrefixCodeRanges[index].nbits;
+    uint32_t offset = _kBrotliPrefixCodeRanges[index].offset;
     if (!BrotliSafeReadBits(br, nbits, &bits)) {
       s->block_length_index = index;
       s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX;
       return BROTLI_FALSE;
     }
-    *result = kBlockLengthPrefixCode[index].offset + bits;
+    *result = offset + bits;
     s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
     return BROTLI_TRUE;
   }
diff --git a/c/dec/huffman.h b/c/dec/huffman.h
index 2e01447..a8fbc45 100644
--- a/c/dec/huffman.h
+++ b/c/dec/huffman.h
@@ -18,13 +18,6 @@ extern "C" {
 
 #define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15
 
-/* Maximum possible Huffman table size for an alphabet size of (index * 32),
-   max code length 15 and root table bits 8. This table describes table sizes
-   for alphabets containing up to 1152 = 36 * 32 symbols. */
-static const uint16_t kMaxHuffmanTableSize[] = {
-  256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822,
-  854, 886, 920, 952, 984, 1016, 1048, 1080, 1112, 1144, 1176, 1208, 1240, 1272,
-  1304, 1336, 1368, 1400, 1432, 1464, 1496, 1528};
 /* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */
 #define BROTLI_HUFFMAN_MAX_SIZE_26 396
 /* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */
@@ -101,7 +94,7 @@ BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,
 /* Builds Huffman lookup table assuming code lengths are in symbol order.
    Returns size of resulting table. */
 BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
-    int root_bits, const uint16_t* const symbol_lists, uint16_t* count_arg);
+    int root_bits, const uint16_t* const symbol_lists, uint16_t* count);
 
 /* Builds a simple Huffman table. The |num_symbols| parameter is to be
    interpreted as follows: 0 means 1 symbol, 1 means 2 symbols,
diff --git a/c/dec/prefix.h b/c/dec/prefix.h
index 3ea062d..481a2c7 100644
--- a/c/dec/prefix.h
+++ b/c/dec/prefix.h
@@ -13,24 +13,6 @@
 #include "../common/constants.h"
 #include <brotli/types.h>
 
-/* Represents the range of values belonging to a prefix code:
-   [offset, offset + 2^nbits) */
-struct PrefixCodeRange {
-  uint16_t offset;
-  uint8_t nbits;
-};
-
-static const struct PrefixCodeRange
-    kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = {
-  {   1,  2}, {    5,  2}, {  9,   2}, {  13,  2},
-  {  17,  3}, {   25,  3}, {  33,  3}, {  41,  3},
-  {  49,  4}, {   65,  4}, {  81,  4}, {  97,  4},
-  { 113,  5}, {  145,  5}, { 177,  5}, { 209,  5},
-  { 241,  6}, {  305,  6}, { 369,  7}, { 497,  8},
-  { 753,  9}, { 1265, 10}, {2289, 11}, {4337, 12},
-  {8433, 13}, {16625, 24}
-};
-
 typedef struct CmdLutElement {
   uint8_t insert_len_extra_bits;
   uint8_t copy_len_extra_bits;
diff --git a/c/dec/state.c b/c/dec/state.c
index 6cf2476..f847836 100644
--- a/c/dec/state.c
+++ b/c/dec/state.c
@@ -136,9 +136,11 @@ void BrotliDecoderStateCleanup(BrotliDecoderState* s) {
 BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(BrotliDecoderState* s,
     HuffmanTreeGroup* group, uint32_t alphabet_size_max,
     uint32_t alphabet_size_limit, uint32_t ntrees) {
-  /* Pack two allocations into one */
-  const size_t max_table_size =
-      kMaxHuffmanTableSize[(alphabet_size_limit + 31) >> 5];
+  /* 376 = 256 (1-st level table) + 4 + 7 + 15 + 31 + 63 (2-nd level mix-tables)
+     This number is discovered "unlimited" "enough" calculator; it is actually
+     a wee bigger than required in several cases (especially for alphabets with
+     less than 16 symbols). */
+  const size_t max_table_size = alphabet_size_limit + 376;
   const size_t code_size = sizeof(HuffmanCode) * ntrees * max_table_size;
   const size_t htree_size = sizeof(HuffmanCode*) * ntrees;
   /* Pointer alignment is, hopefully, wider than sizeof(HuffmanCode). */