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/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 
VP8LHtreeGroupsNew(int num_htree_groups)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 
VP8LHtreeGroupsFree(HTreeGroup * const htree_groups)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.
GetNextKey(uint32_t key,int len)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.
ReplicateValue(HuffmanCode * table,int step,int end,HuffmanCode code)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
NextTableBitSize(const int * const count,int len,int root_bits)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 
VP8LBuildHuffmanTable(HuffmanCode * const root_table,int root_bits,const int code_lengths[],int code_lengths_size)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