15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2011 Google Inc. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 3eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// Use of this source code is governed by a BSD-style license 4eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// that can be found in the COPYING file in the root of the source 5eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// tree. An additional intellectual property rights grant can be found 6eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// in the file PATENTS. All contributing project authors may 7eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// be found in the AUTHORS file in the root of the source tree. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Jyrki Alakuijala (jyrki@google.com) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Entropy encoding (Huffman) for webp lossless 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef WEBP_UTILS_HUFFMAN_ENCODE_H_ 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define WEBP_UTILS_HUFFMAN_ENCODE_H_ 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../webp/types.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#ifdef __cplusplus 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)extern "C" { 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Struct for holding the tree header in coded form. 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t code; // value (0..15) or escape code (16,17,18) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t extra_bits; // extra bits for escape codes 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} HuffmanTreeToken; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Struct to represent the tree codes (depth and bits array). 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct { 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_symbols; // Number of symbols. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t* code_lengths; // Code lengths of the symbols. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint16_t* codes; // Symbol Codes. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} HuffmanTreeCode; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Struct to represent the Huffman tree. 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// TODO(vikasa): Add comment for the fields of the Struct. 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)typedef struct { 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) uint32_t total_count_; 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int value_; 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int pool_index_left_; // Index for the left sub-tree. 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) int pool_index_right_; // Index for the right sub-tree. 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} HuffmanTree; 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Turn the Huffman tree into a token sequence. 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the number of tokens used. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree, 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HuffmanTreeToken* tokens, int max_tokens); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Create an optimized tree, and tokenize it. 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 'buf_rle' and 'huff_tree' are pre-allocated and the 'tree' is the constructed 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// huffman code tree. 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit, 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) uint8_t* const buf_rle, HuffmanTree* const huff_tree, 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) HuffmanTreeCode* const tree); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#ifdef __cplusplus 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // WEBP_UTILS_HUFFMAN_ENCODE_H_ 62