// Copyright 2012 Google Inc. All Rights Reserved.
//
// Use of this source code is governed by a BSD-style license
// that can be found in the COPYING file in the root of the source
// tree. An additional intellectual property rights grant can be found
// in the file PATENTS. All contributing project authors may
// be found in the AUTHORS file in the root of the source tree.
// -----------------------------------------------------------------------------
//
// Utilities for building and looking up Huffman trees.
//
// Author: Urvang Joshi (urvang@google.com)
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "./huffman.h"
#include "../utils/utils.h"
#include "../webp/format_constants.h"
// Huffman data read via DecodeImageStream is represented in two (red and green)
// bytes.
#define MAX_HTREE_GROUPS 0x10000
HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
HTreeGroup* const htree_groups =
(HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups));
if (htree_groups == NULL) {
return NULL;
}
assert(num_htree_groups <= MAX_HTREE_GROUPS);
return htree_groups;
}
void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) {
if (htree_groups != NULL) {
WebPSafeFree(htree_groups);
}
}
// Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
// bit-wise reversal of the len least significant bits of key.
static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) {
uint32_t step = 1 << (len - 1);
while (key & step) {
step >>= 1;
}
return (key & (step - 1)) + step;
}
// Stores code in table[0], table[step], table[2*step], ..., table[end].
// Assumes that end is an integer multiple of step.
static WEBP_INLINE void ReplicateValue(HuffmanCode* table,
int step, int end,
HuffmanCode code) {
assert(end % step == 0);
do {
end -= step;
table[end] = code;
} while (end > 0);
}
// Returns the table width of the next 2nd level table. count is the histogram
// of bit lengths for the remaining symbols, len is the code length of the next
// processed symbol
static WEBP_INLINE int NextTableBitSize(const int* const count,
int len, int root_bits) {
int left = 1 << (len - root_bits);
while (len < MAX_ALLOWED_CODE_LENGTH) {
left -= count[len];
if (left <= 0) break;
++len;
left <<= 1;
}
return len - root_bits;
}
int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
const int code_lengths[], int code_lengths_size) {
HuffmanCode* table = root_table; // next available space in table
int total_size = 1 << root_bits; // total size root table + 2nd level table
int* sorted = NULL; // symbols sorted by code length
int len; // current code length
int symbol; // symbol index in original or sorted table
// number of codes of each length:
int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
// offsets in sorted table for each length:
int offset[MAX_ALLOWED_CODE_LENGTH + 1];
assert(code_lengths_size != 0);
assert(code_lengths != NULL);
assert(root_table != NULL);
assert(root_bits > 0);
// Build histogram of code lengths.
for (symbol = 0; symbol < code_lengths_size; ++symbol) {
if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
return 0;
}
++count[code_lengths[symbol]];
}
// Error, all code lengths are zeros.
if (count[0] == code_lengths_size) {
return 0;
}
// Generate offsets into sorted symbol table by code length.
offset[1] = 0;
for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
if (count[len] > (1 << len)) {
return 0;
}
offset[len + 1] = offset[len] + count[len];
}
sorted = (int*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
if (sorted == NULL) {
return 0;
}
// Sort symbols by length, by symbol order within each length.
for (symbol = 0; symbol < code_lengths_size; ++symbol) {
const int symbol_code_length = code_lengths[symbol];
if (code_lengths[symbol] > 0) {
sorted[offset[symbol_code_length]++] = symbol;
}
}
// Special case code with only one value.
if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
HuffmanCode code;
code.bits = 0;
code.value = (uint16_t)sorted[0];
ReplicateValue(table, 1, total_size, code);
WebPSafeFree(sorted);
return total_size;
}
{
int step; // step size to replicate values in current table
uint32_t low = -1; // low bits for current root entry
uint32_t mask = total_size - 1; // mask for low bits
uint32_t key = 0; // reversed prefix code
int num_nodes = 1; // number of Huffman tree nodes
int num_open = 1; // number of open branches in current tree level
int table_bits = root_bits; // key length of current table
int table_size = 1 << table_bits; // size of current table
symbol = 0;
// Fill in root table.
for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
num_open <<= 1;
num_nodes += num_open;
num_open -= count[len];
if (num_open < 0) {
WebPSafeFree(sorted);
return 0;
}
for (; count[len] > 0; --count[len]) {
HuffmanCode code;
code.bits = (uint8_t)len;
code.value = (uint16_t)sorted[symbol++];
ReplicateValue(&table[key], step, table_size, code);
key = GetNextKey(key, len);
}
}
// Fill in 2nd level tables and add pointers to root table.
for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
++len, step <<= 1) {
num_open <<= 1;
num_nodes += num_open;
num_open -= count[len];
if (num_open < 0) {
WebPSafeFree(sorted);
return 0;
}
for (; count[len] > 0; --count[len]) {
HuffmanCode code;
if ((key & mask) != low) {
table += table_size;
table_bits = NextTableBitSize(count, len, root_bits);
table_size = 1 << table_bits;
total_size += table_size;
low = key & mask;
root_table[low].bits = (uint8_t)(table_bits + root_bits);
root_table[low].value = (uint16_t)((table - root_table) - low);
}
code.bits = (uint8_t)(len - root_bits);
code.value = (uint16_t)sorted[symbol++];
ReplicateValue(&table[key >> root_bits], step, table_size, code);
key = GetNextKey(key, len);
}
}
// Check if tree is full.
if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
WebPSafeFree(sorted);
return 0;
}
}
WebPSafeFree(sorted);
return total_size;
}