| OLD | NEW |
|---|
| (Empty) |
| 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 #include <assert.h> | |
| 15 #include <stdlib.h> | |
| 16 #include <string.h> | |
| 17 #include "./huffman.h" | |
| 18 #include "./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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2651883004:
libwebp-0.6.0-rc1 (Closed)
