godot/thirdparty/libwebp/src/utils/huffman_utils.c

// 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 ([email protected])

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "src/utils/huffman_utils.h"
#include "src/utils/utils.h"
#include "src/webp/format_constants.h"

// Huffman data read via DecodeImageStream is represented in two (red and green)
// bytes.
#define MAX_HTREE_GROUPS …

HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) { … }

void VP8LHtreeGroupsFree(HTreeGroup* const 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) { … }

// 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) { … }

// 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) { … }

// sorted[code_lengths_size] is a pre-allocated array for sorting symbols
// by code length.
static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
                             const int code_lengths[], int code_lengths_size,
                             uint16_t sorted[]) { … }

// Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits).
// More commonly, the value is around ~280.
#define MAX_CODE_LENGTHS_SIZE …
// Cut-off value for switching between heap and stack allocation.
#define SORTED_SIZE_CUTOFF …
int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
                          const int code_lengths[], int code_lengths_size) { … }

int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) { … }

void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) { … }