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 (at) google.com) 13 14 #include <assert.h> 15 #include <stdlib.h> 16 #include <string.h> 17 #include "src/utils/huffman_utils.h" 18 #include "src/utils/utils.h" 19 #include "src/webp/format_constants.h" 20 21 // Huffman data read via DecodeImageStream is represented in two (red and green) 22 // bytes. 23 #define MAX_HTREE_GROUPS 0x10000 24 25 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) { 26 HTreeGroup* const htree_groups = 27 (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups)); 28 if (htree_groups == NULL) { 29 return NULL; 30 } 31 assert(num_htree_groups <= MAX_HTREE_GROUPS); 32 return htree_groups; 33 } 34 35 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) { 36 if (htree_groups != NULL) { 37 WebPSafeFree(htree_groups); 38 } 39 } 40 41 // Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the 42 // bit-wise reversal of the len least significant bits of key. 43 static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) { 44 uint32_t step = 1 << (len - 1); 45 while (key & step) { 46 step >>= 1; 47 } 48 return step ? (key & (step - 1)) + step : key; 49 } 50 51 // Stores code in table[0], table[step], table[2*step], ..., table[end]. 52 // Assumes that end is an integer multiple of step. 53 static WEBP_INLINE void ReplicateValue(HuffmanCode* table, 54 int step, int end, 55 HuffmanCode code) { 56 assert(end % step == 0); 57 do { 58 end -= step; 59 table[end] = code; 60 } while (end > 0); 61 } 62 63 // Returns the table width of the next 2nd level table. count is the histogram 64 // of bit lengths for the remaining symbols, len is the code length of the next 65 // processed symbol 66 static WEBP_INLINE int NextTableBitSize(const int* const count, 67 int len, int root_bits) { 68 int left = 1 << (len - root_bits); 69 while (len < MAX_ALLOWED_CODE_LENGTH) { 70 left -= count[len]; 71 if (left <= 0) break; 72 ++len; 73 left <<= 1; 74 } 75 return len - root_bits; 76 } 77 78 // sorted[code_lengths_size] is a pre-allocated array for sorting symbols 79 // by code length. 80 static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits, 81 const int code_lengths[], int code_lengths_size, 82 uint16_t sorted[]) { 83 HuffmanCode* table = root_table; // next available space in table 84 int total_size = 1 << root_bits; // total size root table + 2nd level table 85 int len; // current code length 86 int symbol; // symbol index in original or sorted table 87 // number of codes of each length: 88 int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 89 // offsets in sorted table for each length: 90 int offset[MAX_ALLOWED_CODE_LENGTH + 1]; 91 92 assert(code_lengths_size != 0); 93 assert(code_lengths != NULL); 94 assert(root_table != NULL); 95 assert(root_bits > 0); 96 97 // Build histogram of code lengths. 98 for (symbol = 0; symbol < code_lengths_size; ++symbol) { 99 if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) { 100 return 0; 101 } 102 ++count[code_lengths[symbol]]; 103 } 104 105 // Error, all code lengths are zeros. 106 if (count[0] == code_lengths_size) { 107 return 0; 108 } 109 110 // Generate offsets into sorted symbol table by code length. 111 offset[1] = 0; 112 for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) { 113 if (count[len] > (1 << len)) { 114 return 0; 115 } 116 offset[len + 1] = offset[len] + count[len]; 117 } 118 119 // Sort symbols by length, by symbol order within each length. 120 for (symbol = 0; symbol < code_lengths_size; ++symbol) { 121 const int symbol_code_length = code_lengths[symbol]; 122 if (code_lengths[symbol] > 0) { 123 sorted[offset[symbol_code_length]++] = symbol; 124 } 125 } 126 127 // Special case code with only one value. 128 if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) { 129 HuffmanCode code; 130 code.bits = 0; 131 code.value = (uint16_t)sorted[0]; 132 ReplicateValue(table, 1, total_size, code); 133 return total_size; 134 } 135 136 { 137 int step; // step size to replicate values in current table 138 uint32_t low = -1; // low bits for current root entry 139 uint32_t mask = total_size - 1; // mask for low bits 140 uint32_t key = 0; // reversed prefix code 141 int num_nodes = 1; // number of Huffman tree nodes 142 int num_open = 1; // number of open branches in current tree level 143 int table_bits = root_bits; // key length of current table 144 int table_size = 1 << table_bits; // size of current table 145 symbol = 0; 146 // Fill in root table. 147 for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) { 148 num_open <<= 1; 149 num_nodes += num_open; 150 num_open -= count[len]; 151 if (num_open < 0) { 152 return 0; 153 } 154 for (; count[len] > 0; --count[len]) { 155 HuffmanCode code; 156 code.bits = (uint8_t)len; 157 code.value = (uint16_t)sorted[symbol++]; 158 ReplicateValue(&table[key], step, table_size, code); 159 key = GetNextKey(key, len); 160 } 161 } 162 163 // Fill in 2nd level tables and add pointers to root table. 164 for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH; 165 ++len, step <<= 1) { 166 num_open <<= 1; 167 num_nodes += num_open; 168 num_open -= count[len]; 169 if (num_open < 0) { 170 return 0; 171 } 172 for (; count[len] > 0; --count[len]) { 173 HuffmanCode code; 174 if ((key & mask) != low) { 175 table += table_size; 176 table_bits = NextTableBitSize(count, len, root_bits); 177 table_size = 1 << table_bits; 178 total_size += table_size; 179 low = key & mask; 180 root_table[low].bits = (uint8_t)(table_bits + root_bits); 181 root_table[low].value = (uint16_t)((table - root_table) - low); 182 } 183 code.bits = (uint8_t)(len - root_bits); 184 code.value = (uint16_t)sorted[symbol++]; 185 ReplicateValue(&table[key >> root_bits], step, table_size, code); 186 key = GetNextKey(key, len); 187 } 188 } 189 190 // Check if tree is full. 191 if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) { 192 return 0; 193 } 194 } 195 196 return total_size; 197 } 198 199 // Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits). 200 // More commonly, the value is around ~280. 201 #define MAX_CODE_LENGTHS_SIZE \ 202 ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES) 203 // Cut-off value for switching between heap and stack allocation. 204 #define SORTED_SIZE_CUTOFF 512 205 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, 206 const int code_lengths[], int code_lengths_size) { 207 int total_size; 208 assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE); 209 if (code_lengths_size <= SORTED_SIZE_CUTOFF) { 210 // use local stack-allocated array. 211 uint16_t sorted[SORTED_SIZE_CUTOFF]; 212 total_size = BuildHuffmanTable(root_table, root_bits, 213 code_lengths, code_lengths_size, sorted); 214 } else { // rare case. Use heap allocation. 215 uint16_t* const sorted = 216 (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted)); 217 if (sorted == NULL) return 0; 218 total_size = BuildHuffmanTable(root_table, root_bits, 219 code_lengths, code_lengths_size, sorted); 220 WebPSafeFree(sorted); 221 } 222 return total_size; 223 } 224
