Coverage Report

Created: 2024-07-27 06:27

/src/libwebp/src/utils/huffman_utils.c
Line
Count
Source (jump to first uncovered line)
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 "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
0
HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
26
0
  HTreeGroup* const htree_groups =
27
0
      (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups));
28
0
  if (htree_groups == NULL) {
29
0
    return NULL;
30
0
  }
31
0
  assert(num_htree_groups <= MAX_HTREE_GROUPS);
32
0
  return htree_groups;
33
0
}
34
35
0
void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) {
36
0
  if (htree_groups != NULL) {
37
0
    WebPSafeFree(htree_groups);
38
0
  }
39
0
}
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
0
static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) {
44
0
  uint32_t step = 1 << (len - 1);
45
0
  while (key & step) {
46
0
    step >>= 1;
47
0
  }
48
0
  return step ? (key & (step - 1)) + step : key;
49
0
}
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
0
                                       HuffmanCode code) {
56
0
  assert(end % step == 0);
57
0
  do {
58
0
    end -= step;
59
0
    table[end] = code;
60
0
  } while (end > 0);
61
0
}
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
0
                                        int len, int root_bits) {
68
0
  int left = 1 << (len - root_bits);
69
0
  while (len < MAX_ALLOWED_CODE_LENGTH) {
70
0
    left -= count[len];
71
0
    if (left <= 0) break;
72
0
    ++len;
73
0
    left <<= 1;
74
0
  }
75
0
  return len - root_bits;
76
0
}
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
0
                             uint16_t sorted[]) {
83
0
  HuffmanCode* table = root_table;  // next available space in table
84
0
  int total_size = 1 << root_bits;  // total size root table + 2nd level table
85
0
  int len;                          // current code length
86
0
  int symbol;                       // symbol index in original or sorted table
87
  // number of codes of each length:
88
0
  int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
89
  // offsets in sorted table for each length:
90
0
  int offset[MAX_ALLOWED_CODE_LENGTH + 1];
91
92
0
  assert(code_lengths_size != 0);
93
0
  assert(code_lengths != NULL);
94
0
  assert((root_table != NULL && sorted != NULL) ||
95
0
         (root_table == NULL && sorted == NULL));
96
0
  assert(root_bits > 0);
97
98
  // Build histogram of code lengths.
99
0
  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
100
0
    if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
101
0
      return 0;
102
0
    }
103
0
    ++count[code_lengths[symbol]];
104
0
  }
105
106
  // Error, all code lengths are zeros.
107
0
  if (count[0] == code_lengths_size) {
108
0
    return 0;
109
0
  }
110
111
  // Generate offsets into sorted symbol table by code length.
112
0
  offset[1] = 0;
113
0
  for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
114
0
    if (count[len] > (1 << len)) {
115
0
      return 0;
116
0
    }
117
0
    offset[len + 1] = offset[len] + count[len];
118
0
  }
119
120
  // Sort symbols by length, by symbol order within each length.
121
0
  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
122
0
    const int symbol_code_length = code_lengths[symbol];
123
0
    if (code_lengths[symbol] > 0) {
124
0
      if (sorted != NULL) {
125
0
        if(offset[symbol_code_length] >= code_lengths_size) {
126
0
            return 0;
127
0
        }
128
0
        sorted[offset[symbol_code_length]++] = symbol;
129
0
      } else {
130
0
        offset[symbol_code_length]++;
131
0
      }
132
0
    }
133
0
  }
134
135
  // Special case code with only one value.
136
0
  if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
137
0
    if (sorted != NULL) {
138
0
      HuffmanCode code;
139
0
      code.bits = 0;
140
0
      code.value = (uint16_t)sorted[0];
141
0
      ReplicateValue(table, 1, total_size, code);
142
0
    }
143
0
    return total_size;
144
0
  }
145
146
0
  {
147
0
    int step;              // step size to replicate values in current table
148
0
    uint32_t low = 0xffffffffu;        // low bits for current root entry
149
0
    uint32_t mask = total_size - 1;    // mask for low bits
150
0
    uint32_t key = 0;      // reversed prefix code
151
0
    int num_nodes = 1;     // number of Huffman tree nodes
152
0
    int num_open = 1;      // number of open branches in current tree level
153
0
    int table_bits = root_bits;        // key length of current table
154
0
    int table_size = 1 << table_bits;  // size of current table
155
0
    symbol = 0;
156
    // Fill in root table.
157
0
    for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
158
0
      num_open <<= 1;
159
0
      num_nodes += num_open;
160
0
      num_open -= count[len];
161
0
      if (num_open < 0) {
162
0
        return 0;
163
0
      }
164
0
      if (root_table == NULL) continue;
165
0
      for (; count[len] > 0; --count[len]) {
166
0
        HuffmanCode code;
167
0
        code.bits = (uint8_t)len;
168
0
        code.value = (uint16_t)sorted[symbol++];
169
0
        ReplicateValue(&table[key], step, table_size, code);
170
0
        key = GetNextKey(key, len);
171
0
      }
172
0
    }
173
174
    // Fill in 2nd level tables and add pointers to root table.
175
0
    for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
176
0
         ++len, step <<= 1) {
177
0
      num_open <<= 1;
178
0
      num_nodes += num_open;
179
0
      num_open -= count[len];
180
0
      if (num_open < 0) {
181
0
        return 0;
182
0
      }
183
0
      for (; count[len] > 0; --count[len]) {
184
0
        HuffmanCode code;
185
0
        if ((key & mask) != low) {
186
0
          if (root_table != NULL) table += table_size;
187
0
          table_bits = NextTableBitSize(count, len, root_bits);
188
0
          table_size = 1 << table_bits;
189
0
          total_size += table_size;
190
0
          low = key & mask;
191
0
          if (root_table != NULL) {
192
0
            root_table[low].bits = (uint8_t)(table_bits + root_bits);
193
0
            root_table[low].value = (uint16_t)((table - root_table) - low);
194
0
          }
195
0
        }
196
0
        if (root_table != NULL) {
197
0
          code.bits = (uint8_t)(len - root_bits);
198
0
          code.value = (uint16_t)sorted[symbol++];
199
0
          ReplicateValue(&table[key >> root_bits], step, table_size, code);
200
0
        }
201
0
        key = GetNextKey(key, len);
202
0
      }
203
0
    }
204
205
    // Check if tree is full.
206
0
    if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
207
0
      return 0;
208
0
    }
209
0
  }
210
211
0
  return total_size;
212
0
}
213
214
// Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits).
215
// More commonly, the value is around ~280.
216
#define MAX_CODE_LENGTHS_SIZE \
217
  ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES)
218
// Cut-off value for switching between heap and stack allocation.
219
0
#define SORTED_SIZE_CUTOFF 512
220
int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
221
0
                          const int code_lengths[], int code_lengths_size) {
222
0
  const int total_size =
223
0
      BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
224
0
  assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
225
0
  if (total_size == 0 || root_table == NULL) return total_size;
226
227
0
  if (root_table->curr_segment->curr_table + total_size >=
228
0
      root_table->curr_segment->start + root_table->curr_segment->size) {
229
    // If 'root_table' does not have enough memory, allocate a new segment.
230
    // The available part of root_table->curr_segment is left unused because we
231
    // need a contiguous buffer.
232
0
    const int segment_size = root_table->curr_segment->size;
233
0
    struct HuffmanTablesSegment* next =
234
0
        (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next));
235
0
    if (next == NULL) return 0;
236
    // Fill the new segment.
237
    // We need at least 'total_size' but if that value is small, it is better to
238
    // allocate a big chunk to prevent more allocations later. 'segment_size' is
239
    // therefore chosen (any other arbitrary value could be chosen).
240
0
    next->size = total_size > segment_size ? total_size : segment_size;
241
0
    next->start =
242
0
        (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start));
243
0
    if (next->start == NULL) {
244
0
      WebPSafeFree(next);
245
0
      return 0;
246
0
    }
247
0
    next->curr_table = next->start;
248
0
    next->next = NULL;
249
    // Point to the new segment.
250
0
    root_table->curr_segment->next = next;
251
0
    root_table->curr_segment = next;
252
0
  }
253
0
  if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
254
    // use local stack-allocated array.
255
0
    uint16_t sorted[SORTED_SIZE_CUTOFF];
256
0
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
257
0
                      code_lengths, code_lengths_size, sorted);
258
0
  } else {  // rare case. Use heap allocation.
259
0
    uint16_t* const sorted =
260
0
        (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
261
0
    if (sorted == NULL) return 0;
262
0
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
263
0
                      code_lengths, code_lengths_size, sorted);
264
0
    WebPSafeFree(sorted);
265
0
  }
266
0
  return total_size;
267
0
}
268
269
0
int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) {
270
  // Have 'segment' point to the first segment for now, 'root'.
271
0
  HuffmanTablesSegment* const root = &huffman_tables->root;
272
0
  huffman_tables->curr_segment = root;
273
0
  root->next = NULL;
274
  // Allocate root.
275
0
  root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start));
276
0
  if (root->start == NULL) return 0;
277
0
  root->curr_table = root->start;
278
0
  root->size = size;
279
0
  return 1;
280
0
}
281
282
0
void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) {
283
0
  HuffmanTablesSegment *current, *next;
284
0
  if (huffman_tables == NULL) return;
285
  // Free the root node.
286
0
  current = &huffman_tables->root;
287
0
  next = current->next;
288
0
  WebPSafeFree(current->start);
289
0
  current->start = NULL;
290
0
  current->next = NULL;
291
0
  current = next;
292
  // Free the following nodes.
293
0
  while (current != NULL) {
294
0
    next = current->next;
295
0
    WebPSafeFree(current->start);
296
0
    WebPSafeFree(current);
297
0
    current = next;
298
0
  }
299
0
}