Update brotli from 722f89 (Feb 19, 2016) to 510131 (Apr 22, 2016)

third_party/brotli/dec/decode.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
 */
 
 #include "./decode.h"
 
 #ifdef __ARM_NEON__
 #include <arm_neon.h>
 #endif
 
-#include <stdio.h>  /* printf (debug output) */
 #include <stdlib.h>  /* free, malloc */
 #include <string.h>  /* memcpy, memset */
 
 #include "./bit_reader.h"
 #include "./context.h"
 #include "./dictionary.h"
 #include "./huffman.h"
 #include "./port.h"
 #include "./prefix.h"
+#include "./state.h"
 #include "./transform.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-/* BROTLI_FAILURE macro unwraps to BROTLI_RESULT_ERROR in non-debug build. */
-/* In debug build it dumps file name, line and pretty function name. */
-#if defined(_MSC_VER) || \
-  (!defined(BROTLI_DEBUG) && !defined(BROTLI_DECODE_DEBUG))
-#define BROTLI_FAILURE() BROTLI_RESULT_ERROR
-#else
-#define BROTLI_FAILURE() BrotliFailure(__FILE__, __LINE__, __PRETTY_FUNCTION__)
-static inline BrotliResult BrotliFailure(const char* f, int l, const char* fn) {
-  fprintf(stderr, "ERROR at %s:%d (%s)\n", f, l, fn);
-  fflush(stderr);
-  return BROTLI_RESULT_ERROR;
-}
-#endif
+#define BROTLI_FAILURE() (BROTLI_DUMP(), BROTLI_RESULT_ERROR)
 
-#ifdef BROTLI_DECODE_DEBUG
 #define BROTLI_LOG_UINT(name)                                       \
-  printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name))
+  BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)))
 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx)                     \
-  printf("[%s] %s[%lu] = %lu\n", __func__, #array_name,             \
-         (unsigned long)(idx), (unsigned long)array_name[idx])
-#define BROTLI_LOG(x) printf x
-#else
-#define BROTLI_LOG_UINT(name)
-#define BROTLI_LOG_ARRAY_INDEX(array_name, idx)
-#define BROTLI_LOG(x)
-#endif
+  BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name,        \
+         (unsigned long)(idx), (unsigned long)array_name[idx]))
 
 static const uint32_t kDefaultCodeLength = 8;
 static const uint32_t kCodeLengthRepeatCode = 16;
 static const uint32_t kNumLiteralCodes = 256;
 static const uint32_t kNumInsertAndCopyCodes = 704;
 static const uint32_t kNumBlockLengthCodes = 26;
 static const int kLiteralContextBits = 6;
 static const int kDistanceContextBits = 2;
 
 #define HUFFMAN_TABLE_BITS 8U
@@ skipping 17 matching lines @@
 
 BrotliState* BrotliCreateState(
     brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
   BrotliState* state = 0;
   if (!alloc_func && !free_func) {
     state = (BrotliState*)malloc(sizeof(BrotliState));
   } else if (alloc_func && free_func) {
     state = (BrotliState*)alloc_func(opaque, sizeof(BrotliState));
   }
   if (state == 0) {
-    (void)BROTLI_FAILURE();
+    BROTLI_DUMP();
     return 0;
   }
   BrotliStateInitWithCustomAllocators(state, alloc_func, free_func, opaque);
   return state;
 }
 
 /* Deinitializes and frees BrotliState instance. */
 void BrotliDestroyState(BrotliState* state) {
   if (!state) {
     return;
@@ skipping 266 matching lines @@
                                         BrotliBitReader* br,
                                         uint32_t* result) {
   uint32_t val;
   if (PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
     *result = DecodeSymbol(val, table, br);
     return 1;
   }
   return SafeDecodeSymbol(table, br, result);
 }
 
-
 /* Makes a look-up in first level Huffman table. Peeks 8 bits. */
 static BROTLI_INLINE void PreloadSymbol(int safe,
                                         const HuffmanCode* table,
                                         BrotliBitReader* br,
                                         uint32_t* bits,
                                         uint32_t* value) {
   if (safe) {
     return;
   }
   table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);
@@ skipping 117 matching lines @@
     *repeat_code_len = new_len;
   }
   old_repeat = *repeat;
   if (*repeat > 0) {
     *repeat -= 2;
     *repeat <<= code_len - 14U;
   }
   *repeat += repeat_delta + 3U;
   repeat_delta = *repeat - old_repeat;
   if (*symbol + repeat_delta > alphabet_size) {
-    (void)BROTLI_FAILURE();
+    BROTLI_DUMP();
     *symbol = alphabet_size;
     *space = 0xFFFFF;
     return;
   }
   BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",
               *symbol, *symbol + repeat_delta - 1, *repeat_code_len));
   if (*repeat_code_len != 0) {
     unsigned last = *symbol + repeat_delta;
     int next = next_symbol[*repeat_code_len];
     do {
@@ skipping 351 matching lines @@
     do {
       index--;
       mtf[index + 1] = mtf[index];
     } while (index > 0);
     mtf[0] = value;
   }
   /* Remember amount of elements to be reinitialized. */
   state->mtf_upper_bound = upper_bound;
 }
 
-
 /* Decodes a series of Huffman table using ReadHuffmanCode function. */
 static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
                                            BrotliState* s) {
   if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {
     s->next = group->codes;
     s->htree_index = 0;
     s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;
   }
   while (s->htree_index < group->num_htrees) {
     uint32_t table_size;
@@ skipping 341 matching lines @@
           return result;
         }
         s->pos = 0;
         s->rb_roundtrips++;
         s->max_distance = s->max_backward_distance;
         s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
         break;
       }
     }
   }
-  return BROTLI_FAILURE();
+  BROTLI_DCHECK(0);  /* Unreachable */
 }
 
 int BrotliDecompressedSize(size_t encoded_size,
                            const uint8_t* encoded_buffer,
                            size_t* decoded_size) {
   BrotliState s;
   int next_block_header;
   BrotliStateInit(&s);
   s.br.next_in = encoded_buffer;
   s.br.avail_in = encoded_size;
@@ skipping 18 matching lines @@
 /* Calculates the smallest feasible ring buffer.
 
    If we know the data size is small, do not allocate more ringbuffer
    size than needed to reduce memory usage.
 
    When this method is called, metablock size and flags MUST be decoded.
 */
 static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(BrotliState* s,
     BrotliBitReader* br) {
   int is_last = s->is_last_metablock;
-  s->ringbuffer_size = 1 << s->window_bits;
+  int window_size = 1 << s->window_bits;
+  s->ringbuffer_size = window_size;
 
   if (s->is_uncompressed) {
     int next_block_header =
         BrotliPeekByte(br, (size_t)s->meta_block_remaining_len);
     if (next_block_header != -1) {  /* Peek succeeded */
       if ((next_block_header & 3) == 3) {  /* ISLAST and ISEMPTY */
         is_last = 1;
       }
     }
   }
 
+  /* Limit custom dictionary size to stream window size. */
+  if (s->custom_dict_size >= window_size) {
+    s->custom_dict += s->custom_dict_size - window_size;
+    s->custom_dict_size = window_size;
+  }
+
   /* We need at least 2 bytes of ring buffer size to get the last two
      bytes for context from there */
   if (is_last) {
-    while (s->ringbuffer_size >= s->meta_block_remaining_len * 2 &&
-           s->ringbuffer_size > 32) {
+    int min_size_x2 = (s->meta_block_remaining_len + s->custom_dict_size) * 2;
+    while (s->ringbuffer_size >= min_size_x2 && s->ringbuffer_size > 32) {
       s->ringbuffer_size >>= 1;
     }
   }
 
-  /* But make it fit the custom dictionary if there is one. */
-  while (s->ringbuffer_size < s->custom_dict_size) {
-    s->ringbuffer_size <<= 1;
-  }
-
   s->ringbuffer_mask = s->ringbuffer_size - 1;
 }
 
 /* Reads 1..256 2-bit context modes. */
 static BrotliResult ReadContextModes(BrotliState* s) {
   BrotliBitReader* br = &s->br;
   int i = s->loop_counter;
 
   while (i < (int)s->num_block_types[0]) {
     uint32_t bits;
@@ skipping 902 matching lines @@
 void BrotliSetCustomDictionary(
     size_t size, const uint8_t* dict, BrotliState* s) {
   s->custom_dict = dict;
   s->custom_dict_size = (int)size;
 }
 
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }  /* extern "C" */
 #endif