[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / huffman.h

/* Copyright 2013 Google Inc. All Rights Reserved.\r
\r
   Distributed under MIT license.\r
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
*/\r
\r
/* Utilities for building Huffman decoding tables. */\r
\r
#ifndef BROTLI_DEC_HUFFMAN_H_\r
#define BROTLI_DEC_HUFFMAN_H_\r
\r
#include "../common/types.h"\r
#include "./port.h"\r
#include <BrotliDecompressLibInternal.h>\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
extern "C" {\r
#endif\r
\r
#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15\r
\r
/* Maximum possible Huffman table size for an alphabet size of (index * 32),\r
 * max code length 15 and root table bits 8. */\r
static const uint16_t kMaxHuffmanTableSize[] = {\r
  256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822,\r
  854, 886, 920, 952, 984, 1016, 1048, 1080};\r
/* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */\r
#define BROTLI_HUFFMAN_MAX_SIZE_26 396\r
/* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */\r
#define BROTLI_HUFFMAN_MAX_SIZE_258 632\r
/* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */\r
#define BROTLI_HUFFMAN_MAX_SIZE_272 646\r
\r
#define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5\r
\r
typedef struct {\r
  uint8_t bits;    /* number of bits used for this symbol */\r
  uint16_t value;  /* symbol value or table offset */\r
} HuffmanCode;\r
\r
/* Builds Huffman lookup table assuming code lengths are in symbol order. */\r
BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,\r
    const uint8_t* const code_lengths, uint16_t* count);\r
\r
/* Builds Huffman lookup table assuming code lengths are in symbol order. */\r
/* Returns size of resulting table. */\r
BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,\r
    int root_bits, const uint16_t* const symbol_lists, uint16_t* count_arg);\r
\r
/* Builds a simple Huffman table. The num_symbols parameter is to be */\r
/* interpreted as follows: 0 means 1 symbol, 1 means 2 symbols, 2 means 3 */\r
/* symbols, 3 means 4 symbols with lengths 2,2,2,2, 4 means 4 symbols with */\r
/* lengths 1,2,3,3. */\r
BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,\r
    int root_bits, uint16_t* symbols, uint32_t num_symbols);\r
\r
/* Contains a collection of Huffman trees with the same alphabet size. */\r
typedef struct {\r
  HuffmanCode** htrees;\r
  HuffmanCode* codes;\r
  uint16_t alphabet_size;\r
  uint16_t num_htrees;\r
} HuffmanTreeGroup;\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
}  /* extern "C" */\r
#endif\r
\r
#endif  /* BROTLI_DEC_HUFFMAN_H_ */\r
Commit	Line	Data
	1	/* Copyright 2013 Google Inc. All Rights Reserved.\r
	2	\r
	3	Distributed under MIT license.\r
	4	See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
	5	*/\r
	6	\r
	7	/* Utilities for building Huffman decoding tables. */\r
	8	\r
	9	#ifndef BROTLI_DEC_HUFFMAN_H_\r
	10	#define BROTLI_DEC_HUFFMAN_H_\r
	11	\r
	12	#include "../common/types.h"\r
	13	#include "./port.h"\r
	14	#include <BrotliDecompressLibInternal.h>\r
	15	\r
	16	#if defined(__cplusplus) \|\| defined(c_plusplus)\r
	17	extern "C" {\r
	18	#endif\r
	19	\r
	20	#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15\r
	21	\r
	22	/* Maximum possible Huffman table size for an alphabet size of (index * 32),\r
	23	* max code length 15 and root table bits 8. */\r
	24	static const uint16_t kMaxHuffmanTableSize[] = {\r
	25	256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822,\r
	26	854, 886, 920, 952, 984, 1016, 1048, 1080};\r
	27	/* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */\r
	28	#define BROTLI_HUFFMAN_MAX_SIZE_26 396\r
	29	/* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */\r
	30	#define BROTLI_HUFFMAN_MAX_SIZE_258 632\r
	31	/* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */\r
	32	#define BROTLI_HUFFMAN_MAX_SIZE_272 646\r
	33	\r
	34	#define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5\r
	35	\r
	36	typedef struct {\r
	37	uint8_t bits; /* number of bits used for this symbol */\r
	38	uint16_t value; /* symbol value or table offset */\r
	39	} HuffmanCode;\r
	40	\r
	41	/* Builds Huffman lookup table assuming code lengths are in symbol order. */\r
	42	BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,\r
	43	const uint8_t* const code_lengths, uint16_t* count);\r
	44	\r
	45	/* Builds Huffman lookup table assuming code lengths are in symbol order. */\r
	46	/* Returns size of resulting table. */\r
	47	BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,\r
	48	int root_bits, const uint16_t* const symbol_lists, uint16_t* count_arg);\r
	49	\r
	50	/* Builds a simple Huffman table. The num_symbols parameter is to be */\r
	51	/* interpreted as follows: 0 means 1 symbol, 1 means 2 symbols, 2 means 3 */\r
	52	/* symbols, 3 means 4 symbols with lengths 2,2,2,2, 4 means 4 symbols with */\r
	53	/* lengths 1,2,3,3. */\r
	54	BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,\r
	55	int root_bits, uint16_t* symbols, uint32_t num_symbols);\r
	56	\r
	57	/* Contains a collection of Huffman trees with the same alphabet size. */\r
	58	typedef struct {\r
	59	HuffmanCode** htrees;\r
	60	HuffmanCode* codes;\r
	61	uint16_t alphabet_size;\r
	62	uint16_t num_htrees;\r
	63	} HuffmanTreeGroup;\r
	64	\r
	65	#if defined(__cplusplus) \|\| defined(c_plusplus)\r
	66	} /* extern "C" */\r
	67	#endif\r
	68	\r
	69	#endif /* BROTLI_DEC_HUFFMAN_H_ */\r