summaryrefslogtreecommitdiff
path: root/drivers/webp/utils/huffman.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/webp/utils/huffman.c')
-rw-r--r--drivers/webp/utils/huffman.c205
1 files changed, 0 insertions, 205 deletions
diff --git a/drivers/webp/utils/huffman.c b/drivers/webp/utils/huffman.c
deleted file mode 100644
index 7c9d83db9a..0000000000
--- a/drivers/webp/utils/huffman.c
+++ /dev/null
@@ -1,205 +0,0 @@
-// 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 "webp/format_constants.h"
-#include "./utils.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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-17 19:11:01 +0000