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 ([email protected]) 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 WEBP_NODISCARD int VP8LHuffmanTablesAllocate(int size, 67 HuffmanTables* huffman_tables); 68 void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables); 69 70 #define HUFFMAN_PACKED_BITS 6 71 #define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) 72 73 // Huffman table group. 74 // Includes special handling for the following cases: 75 // - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) 76 // - is_trivial_code: only 1 code (no bit is read from bitstream) 77 // - use_packed_table: few enough literal symbols, so all the bit codes 78 // can fit into a small look-up table packed_table[] 79 // The common literal base, if applicable, is stored in 'literal_arb'. 80 typedef struct HTreeGroup HTreeGroup; 81 struct HTreeGroup { 82 HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; 83 int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha 84 // Symbols are trivial (have a single code). 85 uint32_t literal_arb; // If is_trivial_literal is true, this is the 86 // ARGB value of the pixel, with Green channel 87 // being set to zero. 88 int is_trivial_code; // true if is_trivial_literal with only one code 89 int use_packed_table; // use packed table below for short literal code 90 // table mapping input bits to a packed values, or escape case to literal code 91 HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; 92 }; 93 94 // Creates the instance of HTreeGroup with specified number of tree-groups. 95 WEBP_NODISCARD HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); 96 97 // Releases the memory allocated for HTreeGroup. 98 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); 99 100 // Builds Huffman lookup table assuming code lengths are in symbol order. 101 // The 'code_lengths' is pre-allocated temporary memory buffer used for creating 102 // the huffman table. 103 // Returns built table size or 0 in case of error (invalid tree or 104 // memory error). 105 WEBP_NODISCARD int VP8LBuildHuffmanTable(HuffmanTables* const root_table, 106 int root_bits, 107 const int code_lengths[], 108 int code_lengths_size); 109 110 #ifdef __cplusplus 111 } // extern "C" 112 #endif 113 114 #endif // WEBP_UTILS_HUFFMAN_UTILS_H_ 115