chromium/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 "../common/platform.h"
#include <brotli/types.h>

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

#define BROTLI_REVERSE_BITS_MAX …

#if defined(BROTLI_RBIT)
#define BROTLI_REVERSE_BITS_BASE …
#else
#define BROTLI_REVERSE_BITS_BASE …
static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = …;
#endif  /* BROTLI_RBIT */

#define BROTLI_REVERSE_BITS_LOWEST …

/* 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) { … }

/* 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,
                                         int step, int end,
                                         HuffmanCode code) { … }

/* 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) { … }

void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
                                        const uint8_t* const code_lengths,
                                        uint16_t* count) { … }

uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
                                 int root_bits,
                                 const uint16_t* const symbol_lists,
                                 uint16_t* count) { … }

uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
                                       int root_bits,
                                       uint16_t* val,
                                       uint32_t num_symbols) { … }

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif