1 // Copyright 2012 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 // Utilities for building and looking up Huffman trees. 11 // 12 // Author: Urvang Joshi (urvang@google.com) 13 14 #ifndef WEBP_UTILS_HUFFMAN_UTILS_H_ 15 #define WEBP_UTILS_HUFFMAN_UTILS_H_ 16 17 #include <assert.h> 18 #include "src/webp/format_constants.h" 19 #include "src/webp/types.h" 20 21 #ifdef __cplusplus 22 extern "C" { 23 #endif 24 25 #define HUFFMAN_TABLE_BITS 8 26 #define HUFFMAN_TABLE_MASK ((1 << HUFFMAN_TABLE_BITS) - 1) 27 28 #define LENGTHS_TABLE_BITS 7 29 #define LENGTHS_TABLE_MASK ((1 << LENGTHS_TABLE_BITS) - 1) 30 31 32 // Huffman lookup table entry 33 typedef struct { 34 uint8_t bits; // number of bits used for this symbol 35 uint16_t value; // symbol value or table offset 36 } HuffmanCode; 37 38 // long version for holding 32b values 39 typedef struct { 40 int bits; // number of bits used for this symbol, 41 // or an impossible value if not a literal code. 42 uint32_t value; // 32b packed ARGB value if literal, 43 // or non-literal symbol otherwise 44 } HuffmanCode32; 45 46 // Contiguous memory segment of HuffmanCodes. 47 typedef struct HuffmanTablesSegment { 48 HuffmanCode* start; 49 // Pointer to where we are writing into the segment. Starts at 'start' and 50 // cannot go beyond 'start' + 'size'. 51 HuffmanCode* curr_table; 52 // Pointer to the next segment in the chain. 53 struct HuffmanTablesSegment* next; 54 int size; 55 } HuffmanTablesSegment; 56 57 // Chained memory segments of HuffmanCodes. 58 typedef struct HuffmanTables { 59 HuffmanTablesSegment root; 60 // Currently processed segment. At first, this is 'root'. 61 HuffmanTablesSegment* curr_segment; 62 } HuffmanTables; 63 64 // Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on 65 // memory allocation error, 1 otherwise. 66 int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables); 67 void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables); 68 69 #define HUFFMAN_PACKED_BITS 6 70 #define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) 71 72 // Huffman table group. 73 // Includes special handling for the following cases: 74 // - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) 75 // - is_trivial_code: only 1 code (no bit is read from bitstream) 76 // - use_packed_table: few enough literal symbols, so all the bit codes 77 // can fit into a small look-up table packed_table[] 78 // The common literal base, if applicable, is stored in 'literal_arb'. 79 typedef struct HTreeGroup HTreeGroup; 80 struct HTreeGroup { 81 HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; 82 int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha 83 // Symbols are trivial (have a single code). 84 uint32_t literal_arb; // If is_trivial_literal is true, this is the 85 // ARGB value of the pixel, with Green channel 86 // being set to zero. 87 int is_trivial_code; // true if is_trivial_literal with only one code 88 int use_packed_table; // use packed table below for short literal code 89 // table mapping input bits to a packed values, or escape case to literal code 90 HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; 91 }; 92 93 // Creates the instance of HTreeGroup with specified number of tree-groups. 94 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); 95 96 // Releases the memory allocated for HTreeGroup. 97 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); 98 99 // Builds Huffman lookup table assuming code lengths are in symbol order. 100 // The 'code_lengths' is pre-allocated temporary memory buffer used for creating 101 // the huffman table. 102 // Returns built table size or 0 in case of error (invalid tree or 103 // memory error). 104 int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits, 105 const int code_lengths[], int code_lengths_size); 106 107 #ifdef __cplusplus 108 } // extern "C" 109 #endif 110 111 #endif // WEBP_UTILS_HUFFMAN_UTILS_H_ 112