1/* Copyright 2013 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5*/ 6 7/* Utilities for building Huffman decoding tables. */ 8 9#ifndef BROTLI_DEC_HUFFMAN_H_ 10#define BROTLI_DEC_HUFFMAN_H_ 11 12#include "../common/platform.h" 13#include <brotli/types.h> 14 15#if defined(__cplusplus) || defined(c_plusplus) 16extern "C" { 17#endif 18 19#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15 20 21/* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */ 22#define BROTLI_HUFFMAN_MAX_SIZE_26 396 23/* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */ 24#define BROTLI_HUFFMAN_MAX_SIZE_258 632 25/* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */ 26#define BROTLI_HUFFMAN_MAX_SIZE_272 646 27 28#define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5 29 30#if ((defined(BROTLI_TARGET_ARMV7) || defined(BROTLI_TARGET_ARMV8_32)) && \ 31 BROTLI_GNUC_HAS_ATTRIBUTE(aligned, 2, 7, 0)) 32#define BROTLI_HUFFMAN_CODE_FAST_LOAD 33#endif 34 35#if !defined(BROTLI_HUFFMAN_CODE_FAST_LOAD) 36/* Do not create this struct directly - use the ConstructHuffmanCode 37 * constructor below! */ 38typedef struct { 39 uint8_t bits; /* number of bits used for this symbol */ 40 uint16_t value; /* symbol value or table offset */ 41} HuffmanCode; 42 43static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits, 44 const uint16_t value) { 45 HuffmanCode h; 46 h.bits = bits; 47 h.value = value; 48 return h; 49} 50 51/* Please use the following macros to optimize HuffmanCode accesses in hot 52 * paths. 53 * 54 * For example, assuming |table| contains a HuffmanCode pointer: 55 * 56 * BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); 57 * BROTLI_HC_ADJUST_TABLE_INDEX(table, index_into_table); 58 * *bits = BROTLI_HC_GET_BITS(table); 59 * *value = BROTLI_HC_GET_VALUE(table); 60 * BROTLI_HC_ADJUST_TABLE_INDEX(table, offset); 61 * *bits2 = BROTLI_HC_GET_BITS(table); 62 * *value2 = BROTLI_HC_GET_VALUE(table); 63 * 64 */ 65 66#define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H) 67#define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V) 68 69/* These must be given a HuffmanCode pointer! */ 70#define BROTLI_HC_FAST_LOAD_BITS(H) (H->bits) 71#define BROTLI_HC_FAST_LOAD_VALUE(H) (H->value) 72 73#else /* BROTLI_HUFFMAN_CODE_FAST_LOAD */ 74 75typedef BROTLI_ALIGNED(4) uint32_t HuffmanCode; 76 77static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits, 78 const uint16_t value) { 79 return (HuffmanCode) ((value & 0xFFFF) << 16) | (bits & 0xFF); 80} 81 82#define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H) uint32_t __fastload_##H = (*H) 83#define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V); __fastload_##H = (*H) 84 85/* These must be given a HuffmanCode pointer! */ 86#define BROTLI_HC_FAST_LOAD_BITS(H) ((__fastload_##H) & 0xFF) 87#define BROTLI_HC_FAST_LOAD_VALUE(H) ((__fastload_##H) >> 16) 88#endif /* BROTLI_HUFFMAN_CODE_FAST_LOAD */ 89 90/* Builds Huffman lookup table assuming code lengths are in symbol order. */ 91BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table, 92 const uint8_t* const code_lengths, uint16_t* count); 93 94/* Builds Huffman lookup table assuming code lengths are in symbol order. 95 Returns size of resulting table. */ 96BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, 97 int root_bits, const uint16_t* const symbol_lists, uint16_t* count); 98 99/* Builds a simple Huffman table. The |num_symbols| parameter is to be 100 interpreted as follows: 0 means 1 symbol, 1 means 2 symbols, 101 2 means 3 symbols, 3 means 4 symbols with lengths [2, 2, 2, 2], 102 4 means 4 symbols with lengths [1, 2, 3, 3]. */ 103BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, 104 int root_bits, uint16_t* symbols, uint32_t num_symbols); 105 106/* Contains a collection of Huffman trees with the same alphabet size. */ 107/* alphabet_size_limit is needed due to simple codes, since 108 log2(alphabet_size_max) could be greater than log2(alphabet_size_limit). */ 109typedef struct { 110 HuffmanCode** htrees; 111 HuffmanCode* codes; 112 uint16_t alphabet_size_max; 113 uint16_t alphabet_size_limit; 114 uint16_t num_htrees; 115} HuffmanTreeGroup; 116 117#if defined(__cplusplus) || defined(c_plusplus) 118} /* extern "C" */ 119#endif 120 121#endif /* BROTLI_DEC_HUFFMAN_H_ */ 122