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 "./huffman.h" 18 #include "../utils/utils.h" 19 #include "../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 (key & (step - 1)) + step; 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 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, 79 const int code_lengths[], int code_lengths_size) { 80 HuffmanCode* table = root_table; // next available space in table 81 int total_size = 1 << root_bits; // total size root table + 2nd level table 82 int* sorted = NULL; // symbols sorted by code length 83 int len; // current code length 84 int symbol; // symbol index in original or sorted table 85 // number of codes of each length: 86 int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 87 // offsets in sorted table for each length: 88 int offset[MAX_ALLOWED_CODE_LENGTH + 1]; 89 90 assert(code_lengths_size != 0); 91 assert(code_lengths != NULL); 92 assert(root_table != NULL); 93 assert(root_bits > 0); 94 95 // Build histogram of code lengths. 96 for (symbol = 0; symbol < code_lengths_size; ++symbol) { 97 if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) { 98 return 0; 99 } 100 ++count[code_lengths[symbol]]; 101 } 102 103 // Error, all code lengths are zeros. 104 if (count[0] == code_lengths_size) { 105 return 0; 106 } 107 108 // Generate offsets into sorted symbol table by code length. 109 offset[1] = 0; 110 for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) { 111 if (count[len] > (1 << len)) { 112 return 0; 113 } 114 offset[len + 1] = offset[len] + count[len]; 115 } 116 117 sorted = (int*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted)); 118 if (sorted == NULL) { 119 return 0; 120 } 121 122 // Sort symbols by length, by symbol order within each length. 123 for (symbol = 0; symbol < code_lengths_size; ++symbol) { 124 const int symbol_code_length = code_lengths[symbol]; 125 if (code_lengths[symbol] > 0) { 126 sorted[offset[symbol_code_length]++] = symbol; 127 } 128 } 129 130 // Special case code with only one value. 131 if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) { 132 HuffmanCode code; 133 code.bits = 0; 134 code.value = (uint16_t)sorted[0]; 135 ReplicateValue(table, 1, total_size, code); 136 WebPSafeFree(sorted); 137 return total_size; 138 } 139 140 { 141 int step; // step size to replicate values in current table 142 uint32_t low = -1; // low bits for current root entry 143 uint32_t mask = total_size - 1; // mask for low bits 144 uint32_t key = 0; // reversed prefix code 145 int num_nodes = 1; // number of Huffman tree nodes 146 int num_open = 1; // number of open branches in current tree level 147 int table_bits = root_bits; // key length of current table 148 int table_size = 1 << table_bits; // size of current table 149 symbol = 0; 150 // Fill in root table. 151 for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) { 152 num_open <<= 1; 153 num_nodes += num_open; 154 num_open -= count[len]; 155 if (num_open < 0) { 156 WebPSafeFree(sorted); 157 return 0; 158 } 159 for (; count[len] > 0; --count[len]) { 160 HuffmanCode code; 161 code.bits = (uint8_t)len; 162 code.value = (uint16_t)sorted[symbol++]; 163 ReplicateValue(&table[key], step, table_size, code); 164 key = GetNextKey(key, len); 165 } 166 } 167 168 // Fill in 2nd level tables and add pointers to root table. 169 for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH; 170 ++len, step <<= 1) { 171 num_open <<= 1; 172 num_nodes += num_open; 173 num_open -= count[len]; 174 if (num_open < 0) { 175 WebPSafeFree(sorted); 176 return 0; 177 } 178 for (; count[len] > 0; --count[len]) { 179 HuffmanCode code; 180 if ((key & mask) != low) { 181 table += table_size; 182 table_bits = NextTableBitSize(count, len, root_bits); 183 table_size = 1 << table_bits; 184 total_size += table_size; 185 low = key & mask; 186 root_table[low].bits = (uint8_t)(table_bits + root_bits); 187 root_table[low].value = (uint16_t)((table - root_table) - low); 188 } 189 code.bits = (uint8_t)(len - root_bits); 190 code.value = (uint16_t)sorted[symbol++]; 191 ReplicateValue(&table[key >> root_bits], step, table_size, code); 192 key = GetNextKey(key, len); 193 } 194 } 195 196 // Check if tree is full. 197 if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) { 198 WebPSafeFree(sorted); 199 return 0; 200 } 201 } 202 203 WebPSafeFree(sorted); 204 return total_size; 205 } 206
