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