diff options
author | Tao Bao <tbao@google.com> | 2018-09-11 03:21:35 +0000 |
---|---|---|
committer | Tao Bao <tbao@google.com> | 2018-09-10 20:25:06 -0700 |
commit | c4af2b09ada22257ff12967537264627a3936822 (patch) | |
tree | bbbd0739556711089201e0448c444e8cf8bc547f /c/dec/huffman.c | |
parent | 885730d69b5f844f1c59f6de809495726290ae22 (diff) | |
download | brotli-c4af2b09ada22257ff12967537264627a3936822.tar.gz |
Revert "Merge tag 'v1.0.5' into HEAD"
This reverts commit 885730d69b5f844f1c59f6de809495726290ae22.
Reason for revert: b/114832768 (32-bit
recovery_component_test.UpdaterTest#brotli_new_data on marlin is
broken).
Bug: 114832768
Test: The above test passes w/ the revert.
Change-Id: I9d6ad3ce44069a94bc78020ed28c5aa1a6d10ce8
Diffstat (limited to 'c/dec/huffman.c')
-rw-r--r-- | c/dec/huffman.c | 72 |
1 files changed, 37 insertions, 35 deletions
diff --git a/c/dec/huffman.c b/c/dec/huffman.c index c5eafad..37da2a5 100644 --- a/c/dec/huffman.c +++ b/c/dec/huffman.c @@ -11,8 +11,8 @@ #include <string.h> /* memcpy, memset */ #include "../common/constants.h" -#include "../common/platform.h" #include <brotli/types.h> +#include "./port.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -20,9 +20,9 @@ extern "C" { #define BROTLI_REVERSE_BITS_MAX 8 -#if defined(BROTLI_RBIT) +#ifdef BROTLI_RBIT #define BROTLI_REVERSE_BITS_BASE \ - ((sizeof(brotli_reg_t) << 3) - BROTLI_REVERSE_BITS_MAX) + ((sizeof(reg_t) << 3) - BROTLI_REVERSE_BITS_MAX) #else #define BROTLI_REVERSE_BITS_BASE 0 static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = { @@ -62,13 +62,13 @@ static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = { #endif /* BROTLI_RBIT */ #define BROTLI_REVERSE_BITS_LOWEST \ - ((brotli_reg_t)1 << (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 brotli_reg_t BrotliReverseBits(brotli_reg_t num) { -#if defined(BROTLI_RBIT) +static BROTLI_INLINE reg_t BrotliReverseBits(reg_t num) { +#ifdef BROTLI_RBIT return BROTLI_RBIT(num); #else return kReverseBits[num]; @@ -86,9 +86,9 @@ static BROTLI_INLINE void ReplicateValue(HuffmanCode* table, } while (end > 0); } -/* Returns the table width of the next 2nd level table. |count| is the histogram - of bit lengths for the remaining symbols, |len| is the code length of the - next processed symbol. */ +/* Returns the table width of the next 2nd level table. count is the histogram + of bit lengths for the remaining symbols, len is the code length of the next + processed symbol */ static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count, int len, int root_bits) { int left = 1 << (len - root_bits); @@ -104,12 +104,12 @@ static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count, 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 */ - brotli_reg_t key; /* prefix code */ - brotli_reg_t key_step; /* prefix code addend */ - int step; /* step size to replicate values in current table */ - int table_size; /* size of current table */ + 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]; @@ -118,7 +118,7 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <= BROTLI_REVERSE_BITS_MAX); - /* Generate offsets into sorted symbol table by code length. */ + /* generate offsets into sorted symbol table by code length */ symbol = -1; bits = 1; BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, { @@ -129,7 +129,7 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, /* Symbols with code length 0 are placed after all other symbols. */ offset[0] = BROTLI_CODE_LENGTH_CODES - 1; - /* Sort symbols by length, by symbol order within each length. */ + /* sort symbols by length, by symbol order within each length */ symbol = BROTLI_CODE_LENGTH_CODES; do { BROTLI_REPEAT(6, { @@ -144,13 +144,13 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, if (offset[0] == 0) { code.bits = 0; code.value = (uint16_t)sorted[0]; - for (key = 0; key < (brotli_reg_t)table_size; ++key) { + for (key = 0; key < (reg_t)table_size; ++key) { table[key] = code; } return; } - /* Fill in table. */ + /* fill in table */ key = 0; key_step = BROTLI_REVERSE_BITS_LOWEST; symbol = 0; @@ -172,18 +172,18 @@ 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 */ - brotli_reg_t key; /* prefix code */ - brotli_reg_t key_step; /* prefix code addend */ - brotli_reg_t sub_key; /* 2nd level table prefix code */ - brotli_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 */ + 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; @@ -200,8 +200,9 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, table_size = 1 << table_bits; total_size = table_size; - /* Fill in the root table. Reduce the table size to if possible, - and create the repetitions by memcpy. */ + /* fill in root table */ + /* let's reduce the table size to a smaller size if possible, and */ + /* create the repetitions by memcpy if possible in the coming loop */ if (table_bits > max_length) { table_bits = max_length; table_size = 1 << table_bits; @@ -223,14 +224,15 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, key_step >>= 1; } while (++bits <= table_bits); - /* If root_bits != table_bits then replicate to fill the remaining slots. */ + /* if root_bits != table_bits we only created one fraction of the */ + /* table, and we need to replicate it now. */ while (total_size != table_size) { memcpy(&table[table_size], &table[0], (size_t)table_size * sizeof(table[0])); table_size <<= 1; } - /* Fill in 2nd level tables and add pointers to root table. */ + /* fill in 2nd level tables and add pointers to root table */ key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1); sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1); sub_key_step = BROTLI_REVERSE_BITS_LOWEST; |