1*b2055c35SXin Li // Copyright 2011 Google Inc. All Rights Reserved. 2*b2055c35SXin Li // 3*b2055c35SXin Li // Use of this source code is governed by a BSD-style license 4*b2055c35SXin Li // that can be found in the COPYING file in the root of the source 5*b2055c35SXin Li // tree. An additional intellectual property rights grant can be found 6*b2055c35SXin Li // in the file PATENTS. All contributing project authors may 7*b2055c35SXin Li // be found in the AUTHORS file in the root of the source tree. 8*b2055c35SXin Li // ----------------------------------------------------------------------------- 9*b2055c35SXin Li // 10*b2055c35SXin Li // Author: Jyrki Alakuijala ([email protected]) 11*b2055c35SXin Li // 12*b2055c35SXin Li // Entropy encoding (Huffman) for webp lossless 13*b2055c35SXin Li 14*b2055c35SXin Li #ifndef WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_ 15*b2055c35SXin Li #define WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_ 16*b2055c35SXin Li 17*b2055c35SXin Li #include "src/webp/types.h" 18*b2055c35SXin Li 19*b2055c35SXin Li #ifdef __cplusplus 20*b2055c35SXin Li extern "C" { 21*b2055c35SXin Li #endif 22*b2055c35SXin Li 23*b2055c35SXin Li // Struct for holding the tree header in coded form. 24*b2055c35SXin Li typedef struct { 25*b2055c35SXin Li uint8_t code; // value (0..15) or escape code (16,17,18) 26*b2055c35SXin Li uint8_t extra_bits; // extra bits for escape codes 27*b2055c35SXin Li } HuffmanTreeToken; 28*b2055c35SXin Li 29*b2055c35SXin Li // Struct to represent the tree codes (depth and bits array). 30*b2055c35SXin Li typedef struct { 31*b2055c35SXin Li int num_symbols; // Number of symbols. 32*b2055c35SXin Li uint8_t* code_lengths; // Code lengths of the symbols. 33*b2055c35SXin Li uint16_t* codes; // Symbol Codes. 34*b2055c35SXin Li } HuffmanTreeCode; 35*b2055c35SXin Li 36*b2055c35SXin Li // Struct to represent the Huffman tree. 37*b2055c35SXin Li typedef struct { 38*b2055c35SXin Li uint32_t total_count_; // Symbol frequency. 39*b2055c35SXin Li int value_; // Symbol value. 40*b2055c35SXin Li int pool_index_left_; // Index for the left sub-tree. 41*b2055c35SXin Li int pool_index_right_; // Index for the right sub-tree. 42*b2055c35SXin Li } HuffmanTree; 43*b2055c35SXin Li 44*b2055c35SXin Li // Turn the Huffman tree into a token sequence. 45*b2055c35SXin Li // Returns the number of tokens used. 46*b2055c35SXin Li int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 47*b2055c35SXin Li HuffmanTreeToken* tokens, int max_tokens); 48*b2055c35SXin Li 49*b2055c35SXin Li // Create an optimized tree, and tokenize it. 50*b2055c35SXin Li // 'buf_rle' and 'huff_tree' are pre-allocated and the 'tree' is the constructed 51*b2055c35SXin Li // huffman code tree. 52*b2055c35SXin Li void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit, 53*b2055c35SXin Li uint8_t* const buf_rle, HuffmanTree* const huff_tree, 54*b2055c35SXin Li HuffmanTreeCode* const huff_code); 55*b2055c35SXin Li 56*b2055c35SXin Li #ifdef __cplusplus 57*b2055c35SXin Li } 58*b2055c35SXin Li #endif 59*b2055c35SXin Li 60*b2055c35SXin Li #endif // WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_ 61