diff options
Diffstat (limited to 'src/3rdparty/libwebp/src/utils/huffman.h')
-rw-r--r-- | src/3rdparty/libwebp/src/utils/huffman.h | 110 |
1 files changed, 48 insertions, 62 deletions
diff --git a/src/3rdparty/libwebp/src/utils/huffman.h b/src/3rdparty/libwebp/src/utils/huffman.h index 624bc17..c6dd6aa 100644 --- a/src/3rdparty/libwebp/src/utils/huffman.h +++ b/src/3rdparty/libwebp/src/utils/huffman.h @@ -22,78 +22,64 @@ extern "C" { #endif -// A node of a Huffman tree. -typedef struct { - int symbol_; - int children_; // delta offset to both children (contiguous) or 0 if leaf. -} HuffmanTreeNode; +#define HUFFMAN_TABLE_BITS 8 +#define HUFFMAN_TABLE_MASK ((1 << HUFFMAN_TABLE_BITS) - 1) + +#define LENGTHS_TABLE_BITS 7 +#define LENGTHS_TABLE_MASK ((1 << LENGTHS_TABLE_BITS) - 1) -// Huffman Tree. -#define HUFF_LUT_BITS 7 -#define HUFF_LUT (1U << HUFF_LUT_BITS) -typedef struct HuffmanTree HuffmanTree; -struct HuffmanTree { - // Fast lookup for short bit lengths. - uint8_t lut_bits_[HUFF_LUT]; - int16_t lut_symbol_[HUFF_LUT]; - int16_t lut_jump_[HUFF_LUT]; - // Complete tree for lookups. - HuffmanTreeNode* root_; // all the nodes, starting at root. - int max_nodes_; // max number of nodes - int num_nodes_; // number of currently occupied nodes -}; -// Huffman Tree group. +// Huffman lookup table entry +typedef struct { + uint8_t bits; // number of bits used for this symbol + uint16_t value; // symbol value or table offset +} HuffmanCode; + +// long version for holding 32b values +typedef struct { + int bits; // number of bits used for this symbol, + // or an impossible value if not a literal code. + uint32_t value; // 32b packed ARGB value if literal, + // or non-literal symbol otherwise +} HuffmanCode32; + +#define HUFFMAN_PACKED_BITS 6 +#define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) + +// Huffman table group. +// Includes special handling for the following cases: +// - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) +// - is_trivial_code: only 1 code (no bit is read from bitstream) +// - use_packed_table: few enough literal symbols, so all the bit codes +// can fit into a small look-up table packed_table[] +// The common literal base, if applicable, is stored in 'literal_arb'. typedef struct HTreeGroup HTreeGroup; struct HTreeGroup { - HuffmanTree htrees_[HUFFMAN_CODES_PER_META_CODE]; + HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; + int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha + // Symbols are trivial (have a single code). + uint32_t literal_arb; // If is_trivial_literal is true, this is the + // ARGB value of the pixel, with Green channel + // being set to zero. + int is_trivial_code; // true if is_trivial_literal with only one code + int use_packed_table; // use packed table below for short literal code + // table mapping input bits to a packed values, or escape case to literal code + HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; }; -// Returns true if the given node is not a leaf of the Huffman tree. -static WEBP_INLINE int HuffmanTreeNodeIsNotLeaf( - const HuffmanTreeNode* const node) { - return node->children_; -} - -// Go down one level. Most critical function. 'right_child' must be 0 or 1. -static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( - const HuffmanTreeNode* node, int right_child) { - return node + node->children_ + right_child; -} - -// Releases the nodes of the Huffman tree. -// Note: It does NOT free 'tree' itself. -void VP8LHuffmanTreeFree(HuffmanTree* const tree); - // Creates the instance of HTreeGroup with specified number of tree-groups. HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); // Releases the memory allocated for HTreeGroup. -void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups); - -// Builds Huffman tree assuming code lengths are implicitly in symbol order. -// The 'huff_codes' and 'code_lengths' are pre-allocated temporary memory -// buffers, used for creating the huffman tree. -// Returns false in case of error (invalid tree or memory error). -int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, - const int* const code_lengths, - int* const huff_codes, - int code_lengths_size); - -// Build a Huffman tree with explicitly given lists of code lengths, codes -// and symbols. Verifies that all symbols added are smaller than max_symbol. -// Returns false in case of an invalid symbol, invalid tree or memory error. -int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree, - const int* const code_lengths, - const int* const codes, - const int* const symbols, int max_symbol, - int num_symbols); - -// Utility: converts Huffman code lengths to corresponding Huffman codes. -// 'huff_codes' should be pre-allocated. -// Returns false in case of error (memory allocation, invalid codes). -int VP8LHuffmanCodeLengthsToCodes(const int* const code_lengths, - int code_lengths_size, int* const huff_codes); +void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); + +// Builds Huffman lookup table assuming code lengths are in symbol order. +// The 'code_lengths' is pre-allocated temporary memory buffer used for creating +// the huffman table. +// Returns built table size or 0 in case of error (invalid tree or +// memory error). +int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, + const int code_lengths[], int code_lengths_size); #ifdef __cplusplus } // extern "C" |