1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2011 Google Inc. All Rights Reserved. 2a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 30406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Use of this source code is governed by a BSD-style license 40406ce1417f76f2034833414dcecc9f56253640cVikas Arora// that can be found in the COPYING file in the root of the source 50406ce1417f76f2034833414dcecc9f56253640cVikas Arora// tree. An additional intellectual property rights grant can be found 60406ce1417f76f2034833414dcecc9f56253640cVikas Arora// in the file PATENTS. All contributing project authors may 70406ce1417f76f2034833414dcecc9f56253640cVikas Arora// be found in the AUTHORS file in the root of the source tree. 8a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 9a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 10a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Author: Jyrki Alakuijala (jyrki@google.com) 11a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 12a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Entropy encoding (Huffman) for webp lossless 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#ifndef WEBP_UTILS_HUFFMAN_ENCODE_H_ 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#define WEBP_UTILS_HUFFMAN_ENCODE_H_ 16a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 179e80ee991168a0a6c2a906dd2c17c5e17df4566eJames Zern#include "../webp/types.h" 18a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 198b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifdef __cplusplus 20a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraextern "C" { 21a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#endif 22a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 23a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Struct for holding the tree header in coded form. 24a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroratypedef struct { 25a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t code; // value (0..15) or escape code (16,17,18) 26a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t extra_bits; // extra bits for escape codes 27a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} HuffmanTreeToken; 28a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 29a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Struct to represent the tree codes (depth and bits array). 30a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroratypedef struct { 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int num_symbols; // Number of symbols. 32a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint8_t* code_lengths; // Code lengths of the symbols. 33a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora uint16_t* codes; // Symbol Codes. 34a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} HuffmanTreeCode; 35a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 3633f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// Struct to represent the Huffman tree. 3733f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// TODO(vikasa): Add comment for the fields of the Struct. 3833f74dabbc7920a65ed435d7417987589febdc16Vikas Aroratypedef struct { 3933f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint32_t total_count_; 4033f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int value_; 4133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int pool_index_left_; // Index for the left sub-tree. 4233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora int pool_index_right_; // Index for the right sub-tree. 4333f74dabbc7920a65ed435d7417987589febdc16Vikas Arora} HuffmanTree; 4433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora 45a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Turn the Huffman tree into a token sequence. 46a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Returns the number of tokens used. 47a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Aroraint VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 48a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeToken* tokens, int max_tokens); 49a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 50a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Create an optimized tree, and tokenize it. 5133f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// 'buf_rle' and 'huff_tree' are pre-allocated and the 'tree' is the constructed 5233f74dabbc7920a65ed435d7417987589febdc16Vikas Arora// huffman code tree. 5333f74dabbc7920a65ed435d7417987589febdc16Vikas Aroravoid VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit, 5433f74dabbc7920a65ed435d7417987589febdc16Vikas Arora uint8_t* const buf_rle, HuffmanTree* const huff_tree, 5533f74dabbc7920a65ed435d7417987589febdc16Vikas Arora HuffmanTreeCode* const tree); 56a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 578b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifdef __cplusplus 58a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 59a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#endif 60a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 61a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#endif // WEBP_UTILS_HUFFMAN_ENCODE_H_ 62