/******************************************************************** * * * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE. * * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * * * * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2009 * * by the Xiph.Org Foundation and contributors http://www.xiph.org/ * * * ******************************************************************** function: last mod: $Id$ ********************************************************************/ #include <stdlib.h> #include <string.h> #include <ogg/ogg.h> #include "huffdec.h" #include "decint.h" /*Instead of storing every branching in the tree, subtrees can be collapsed into one node, with a table of size 1<<nbits pointing directly to its descedents nbits levels down. This allows more than one bit to be read at a time, and avoids following all the intermediate branches with next to no increased code complexity once the collapsed tree has been built. We do _not_ require that a subtree be complete to be collapsed, but instead store duplicate pointers in the table, and record the actual depth of the node below its parent. This tells us the number of bits to advance the stream after reaching it. This turns out to be equivalent to the method described in \cite{Hash95}, without the requirement that codewords be sorted by length. If the codewords were sorted by length (so-called ``canonical-codes''), they could be decoded much faster via either Lindell and Moffat's approach or Hashemian's Condensed Huffman Code approach, the latter of which has an extremely small memory footprint. We can't use Choueka et al.'s finite state machine approach, which is extremely fast, because we can't allow multiple symbols to be output at a time; the codebook can and does change between symbols. It also has very large memory requirements, which impairs cache coherency. We store the tree packed in an array of 16-bit integers (words). Each node consists of a single word, followed consecutively by two or more indices of its children. Let n be the value of this first word. This is the number of bits that need to be read to traverse the node, and must be positive. 1<<n entries follow in the array, each an index to a child node. If the child is positive, then it is the index of another internal node in the table. If the child is negative or zero, then it is a leaf node. These are stored directly in the child pointer to save space, since they only require a single word. If a leaf node would have been encountered before reading n bits, then it is duplicated the necessary number of times in this table. Leaf nodes pack both a token value and their actual depth in the tree. The token in the leaf node is (-leaf&255). The number of bits that need to be consumed to reach the leaf, starting from the current node, is (-leaf>>8). @ARTICLE{Hash95, author="Reza Hashemian", title="Memory Efficient and High-Speed Search {Huffman} Coding", journal="{IEEE} Transactions on Communications", volume=43, number=10, pages="2576--2581", month=Oct, year=1995 }*/ /*The map from external spec-defined tokens to internal tokens. This is constructed so that any extra bits read with the original token value can be masked off the least significant bits of its internal token index. In addition, all of the tokens which require additional extra bits are placed at the start of the list, and grouped by type. OC_DCT_REPEAT_RUN3_TOKEN is placed first, as it is an extra-special case, so giving it index 0 may simplify comparisons on some architectures. These requirements require some substantial reordering.*/ static const unsigned char OC_DCT_TOKEN_MAP[TH_NDCT_TOKENS]= …; /*The log base 2 of number of internal tokens associated with each of the spec tokens (i.e., how many of the extra bits are folded into the token value). Increasing the maximum value beyond 3 will enlarge the amount of stack required for tree construction.*/ static const unsigned char OC_DCT_TOKEN_MAP_LOG_NENTRIES[TH_NDCT_TOKENS]= …; /*The size a lookup table is allowed to grow to relative to the number of unique nodes it contains. E.g., if OC_HUFF_SLUSH is 4, then at most 75% of the space in the tree is wasted (1/4 of the space must be used). Larger numbers can decode tokens with fewer read operations, while smaller numbers may save more space. With a sample file: 32233473 read calls are required when no tree collapsing is done (100.0%). 19269269 read calls are required when OC_HUFF_SLUSH is 1 (59.8%). 11144969 read calls are required when OC_HUFF_SLUSH is 2 (34.6%). 10538563 read calls are required when OC_HUFF_SLUSH is 4 (32.7%). 10192578 read calls are required when OC_HUFF_SLUSH is 8 (31.6%). Since a value of 2 gets us the vast majority of the speed-up with only a small amount of wasted memory, this is what we use. This value must be less than 128, or you could create a tree with more than 32767 entries, which would overflow the 16-bit words used to index it.*/ #define OC_HUFF_SLUSH … /*The root of the tree is on the fast path, and a larger value here is more beneficial than elsewhere in the tree. 7 appears to give the best performance, trading off between increased use of the single-read fast path and cache footprint for the tables, though obviously this will depend on your cache size. Using 7 here, the VP3 tables are about twice as large compared to using 2.*/ #define OC_ROOT_HUFF_SLUSH … /*Unpacks a Huffman codebook. _opb: The buffer to unpack from. _tokens: Stores a list of internal tokens, in the order they were found in the codebook, and the lengths of their corresponding codewords. This is enough to completely define the codebook, while minimizing stack usage and avoiding temporary allocations (for platforms where free() is a no-op). Return: The number of internal tokens in the codebook, or a negative value on error.*/ int oc_huff_tree_unpack(oc_pack_buf *_opb,unsigned char _tokens[256][2]){ … } /*Count how many tokens would be required to fill a subtree at depth _depth. _tokens: A list of internal tokens, in the order they are found in the codebook, and the lengths of their corresponding codewords. _depth: The depth of the desired node in the corresponding tree structure. Return: The number of tokens that belong to that subtree.*/ static int oc_huff_subtree_tokens(unsigned char _tokens[][2],int _depth){ … } /*Compute the number of bits to use for a collapsed tree node at the given depth. _tokens: A list of internal tokens, in the order they are found in the codebook, and the lengths of their corresponding codewords. _ntokens: The number of tokens corresponding to this tree node. _depth: The depth of this tree node. Return: The number of bits to use for a collapsed tree node rooted here. This is always at least one, even if this was a leaf node.*/ static int oc_huff_tree_collapse_depth(unsigned char _tokens[][2], int _ntokens,int _depth){ … } /*Determines the size in words of a Huffman tree node that represents a subtree of depth _nbits. _nbits: The depth of the subtree. This must be greater than zero. Return: The number of words required to store the node.*/ static size_t oc_huff_node_size(int _nbits){ … } /*Produces a collapsed-tree representation of the given token list. _tree: The storage for the collapsed Huffman tree. This may be NULL to compute the required storage size instead of constructing the tree. _tokens: A list of internal tokens, in the order they are found in the codebook, and the lengths of their corresponding codewords. _ntokens: The number of tokens corresponding to this tree node. Return: The number of words required to store the tree.*/ static size_t oc_huff_tree_collapse(ogg_int16_t *_tree, unsigned char _tokens[][2],int _ntokens){ … } /*Unpacks a set of Huffman trees, and reduces them to a collapsed representation. _opb: The buffer to unpack the trees from. _nodes: The table to fill with the Huffman trees. Return: 0 on success, or a negative value on error. The caller is responsible for cleaning up any partially initialized _nodes on failure.*/ int oc_huff_trees_unpack(oc_pack_buf *_opb, ogg_int16_t *_nodes[TH_NHUFFMAN_TABLES]){ … } /*Determines the size in words of a Huffman subtree. _tree: The complete Huffman tree. _node: The index of the root of the desired subtree. Return: The number of words required to store the tree.*/ static size_t oc_huff_tree_size(const ogg_int16_t *_tree,int _node){ … } /*Makes a copy of the given set of Huffman trees. _dst: The array to store the copy in. _src: The array of trees to copy.*/ int oc_huff_trees_copy(ogg_int16_t *_dst[TH_NHUFFMAN_TABLES], const ogg_int16_t *const _src[TH_NHUFFMAN_TABLES]){ … } /*Frees the memory used by a set of Huffman trees. _nodes: The array of trees to free.*/ void oc_huff_trees_clear(ogg_int16_t *_nodes[TH_NHUFFMAN_TABLES]){ … } /*Unpacks a single token using the given Huffman tree. _opb: The buffer to unpack the token from. _node: The tree to unpack the token with. Return: The token value.*/ int oc_huff_token_decode_c(oc_pack_buf *_opb,const ogg_int16_t *_tree){ … }
Codebase Browser
godot