aboutsummaryrefslogtreecommitdiff
path: root/c/dec/huffman.c
diff options
context:
space:
mode:
authorTao Bao <tbao@google.com>2018-09-11 03:21:35 +0000
committerTao Bao <tbao@google.com>2018-09-10 20:25:06 -0700
commitc4af2b09ada22257ff12967537264627a3936822 (patch)
treebbbd0739556711089201e0448c444e8cf8bc547f /c/dec/huffman.c
parent885730d69b5f844f1c59f6de809495726290ae22 (diff)
downloadbrotli-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.c72
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;