diff options
Diffstat (limited to 'media/libtheora/lib/huffdec.c')
| -rw-r--r-- | media/libtheora/lib/huffdec.c | 515 |
1 files changed, 515 insertions, 0 deletions
diff --git a/media/libtheora/lib/huffdec.c b/media/libtheora/lib/huffdec.c new file mode 100644 index 0000000000..5a83c5f150 --- /dev/null +++ b/media/libtheora/lib/huffdec.c @@ -0,0 +1,515 @@ +/******************************************************************** + * * + * 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]={ + /*OC_DCT_EOB1_TOKEN (0 extra bits)*/ + 15, + /*OC_DCT_EOB2_TOKEN (0 extra bits)*/ + 16, + /*OC_DCT_EOB3_TOKEN (0 extra bits)*/ + 17, + /*OC_DCT_REPEAT_RUN0_TOKEN (2 extra bits)*/ + 88, + /*OC_DCT_REPEAT_RUN1_TOKEN (3 extra bits)*/ + 80, + /*OC_DCT_REPEAT_RUN2_TOKEN (4 extra bits)*/ + 1, + /*OC_DCT_REPEAT_RUN3_TOKEN (12 extra bits)*/ + 0, + /*OC_DCT_SHORT_ZRL_TOKEN (3 extra bits)*/ + 48, + /*OC_DCT_ZRL_TOKEN (6 extra bits)*/ + 14, + /*OC_ONE_TOKEN (0 extra bits)*/ + 56, + /*OC_MINUS_ONE_TOKEN (0 extra bits)*/ + 57, + /*OC_TWO_TOKEN (0 extra bits)*/ + 58, + /*OC_MINUS_TWO_TOKEN (0 extra bits)*/ + 59, + /*OC_DCT_VAL_CAT2 (1 extra bit)*/ + 60, + 62, + 64, + 66, + /*OC_DCT_VAL_CAT3 (2 extra bits)*/ + 68, + /*OC_DCT_VAL_CAT4 (3 extra bits)*/ + 72, + /*OC_DCT_VAL_CAT5 (4 extra bits)*/ + 2, + /*OC_DCT_VAL_CAT6 (5 extra bits)*/ + 4, + /*OC_DCT_VAL_CAT7 (6 extra bits)*/ + 6, + /*OC_DCT_VAL_CAT8 (10 extra bits)*/ + 8, + /*OC_DCT_RUN_CAT1A (1 extra bit)*/ + 18, + 20, + 22, + 24, + 26, + /*OC_DCT_RUN_CAT1B (3 extra bits)*/ + 32, + /*OC_DCT_RUN_CAT1C (4 extra bits)*/ + 12, + /*OC_DCT_RUN_CAT2A (2 extra bits)*/ + 28, + /*OC_DCT_RUN_CAT2B (3 extra bits)*/ + 40 +}; + +/*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]={ + 0,0,0,2,3,0,0,3,0,0,0,0,0,1,1,1,1,2,3,1,1,1,2,1,1,1,1,1,3,1,2,3 +}; + + +/*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 (2) +/*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 (7) + + + +/*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]){ + ogg_uint32_t code; + int len; + int ntokens; + int nleaves; + code=0; + len=ntokens=nleaves=0; + for(;;){ + long bits; + bits=oc_pack_read1(_opb); + /*Only process nodes so long as there's more bits in the buffer.*/ + if(oc_pack_bytes_left(_opb)<0)return TH_EBADHEADER; + /*Read an internal node:*/ + if(!bits){ + len++; + /*Don't allow codewords longer than 32 bits.*/ + if(len>32)return TH_EBADHEADER; + } + /*Read a leaf node:*/ + else{ + ogg_uint32_t code_bit; + int neb; + int nentries; + int token; + /*Don't allow more than 32 spec-tokens per codebook.*/ + if(++nleaves>32)return TH_EBADHEADER; + bits=oc_pack_read(_opb,OC_NDCT_TOKEN_BITS); + neb=OC_DCT_TOKEN_MAP_LOG_NENTRIES[bits]; + token=OC_DCT_TOKEN_MAP[bits]; + nentries=1<<neb; + while(nentries-->0){ + _tokens[ntokens][0]=(unsigned char)token++; + _tokens[ntokens][1]=(unsigned char)(len+neb); + ntokens++; + } + code_bit=0x80000000U>>len-1; + while(len>0&&(code&code_bit)){ + code^=code_bit; + code_bit<<=1; + len--; + } + if(len<=0)break; + code|=code_bit; + } + } + return ntokens; +} + +/*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){ + ogg_uint32_t code; + int ti; + code=0; + ti=0; + do{ + if(_tokens[ti][1]-_depth<32)code+=0x80000000U>>_tokens[ti++][1]-_depth; + else{ + /*Because of the expanded internal tokens, we can have codewords as long + as 35 bits. + A single recursion here is enough to advance past them.*/ + code++; + ti+=oc_huff_subtree_tokens(_tokens+ti,_depth+31); + } + } + while(code<0x80000000U); + return ti; +} + +/*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){ + int got_leaves; + int loccupancy; + int occupancy; + int slush; + int nbits; + int best_nbits; + slush=_depth>0?OC_HUFF_SLUSH:OC_ROOT_HUFF_SLUSH; + /*It's legal to have a tree with just a single node, which requires no bits + to decode and always returns the same token. + However, no encoder actually does this (yet). + To avoid a special case in oc_huff_token_decode(), we force the number of + lookahead bits to be at least one. + This will produce a tree that looks ahead one bit and then advances the + stream zero bits.*/ + nbits=1; + occupancy=2; + got_leaves=1; + do{ + int ti; + if(got_leaves)best_nbits=nbits; + nbits++; + got_leaves=0; + loccupancy=occupancy; + for(occupancy=ti=0;ti<_ntokens;occupancy++){ + if(_tokens[ti][1]<_depth+nbits)ti++; + else if(_tokens[ti][1]==_depth+nbits){ + got_leaves=1; + ti++; + } + else ti+=oc_huff_subtree_tokens(_tokens+ti,_depth+nbits); + } + } + while(occupancy>loccupancy&&occupancy*slush>=1<<nbits); + return best_nbits; +} + +/*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){ + return 1+(1<<_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){ + ogg_int16_t node[34]; + unsigned char depth[34]; + unsigned char last[34]; + size_t ntree; + int ti; + int l; + depth[0]=0; + last[0]=(unsigned char)(_ntokens-1); + ntree=0; + ti=0; + l=0; + do{ + int nbits; + nbits=oc_huff_tree_collapse_depth(_tokens+ti,last[l]+1-ti,depth[l]); + node[l]=(ogg_int16_t)ntree; + ntree+=oc_huff_node_size(nbits); + if(_tree!=NULL)_tree[node[l]++]=(ogg_int16_t)nbits; + do{ + while(ti<=last[l]&&_tokens[ti][1]<=depth[l]+nbits){ + if(_tree!=NULL){ + ogg_int16_t leaf; + int nentries; + nentries=1<<depth[l]+nbits-_tokens[ti][1]; + leaf=(ogg_int16_t)-(_tokens[ti][1]-depth[l]<<8|_tokens[ti][0]); + while(nentries-->0)_tree[node[l]++]=leaf; + } + ti++; + } + if(ti<=last[l]){ + /*We need to recurse*/ + depth[l+1]=(unsigned char)(depth[l]+nbits); + if(_tree!=NULL)_tree[node[l]++]=(ogg_int16_t)ntree; + l++; + last[l]= + (unsigned char)(ti+oc_huff_subtree_tokens(_tokens+ti,depth[l])-1); + break; + } + /*Pop back up a level of recursion.*/ + else if(l-->0)nbits=depth[l+1]-depth[l]; + } + while(l>=0); + } + while(l>=0); + return ntree; +} + +/*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]){ + int i; + for(i=0;i<TH_NHUFFMAN_TABLES;i++){ + unsigned char tokens[256][2]; + int ntokens; + ogg_int16_t *tree; + size_t size; + /*Unpack the full tree into a temporary buffer.*/ + ntokens=oc_huff_tree_unpack(_opb,tokens); + if(ntokens<0)return ntokens; + /*Figure out how big the collapsed tree will be and allocate space for it.*/ + size=oc_huff_tree_collapse(NULL,tokens,ntokens); + /*This should never happen; if it does it means you set OC_HUFF_SLUSH or + OC_ROOT_HUFF_SLUSH too large.*/ + if(size>32767)return TH_EIMPL; + tree=(ogg_int16_t *)_ogg_malloc(size*sizeof(*tree)); + if(tree==NULL)return TH_EFAULT; + /*Construct the collapsed the tree.*/ + oc_huff_tree_collapse(tree,tokens,ntokens); + _nodes[i]=tree; + } + return 0; +} + +/*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){ + size_t size; + int nchildren; + int n; + int i; + n=_tree[_node]; + size=oc_huff_node_size(n); + nchildren=1<<n; + i=0; + do{ + int child; + child=_tree[_node+i+1]; + if(child<=0)i+=1<<n-(-child>>8); + else{ + size+=oc_huff_tree_size(_tree,child); + i++; + } + } + while(i<nchildren); + return size; +} + +/*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]){ + int total; + int i; + total=0; + for(i=0;i<TH_NHUFFMAN_TABLES;i++){ + size_t size; + size=oc_huff_tree_size(_src[i],0); + total+=size; + _dst[i]=(ogg_int16_t *)_ogg_malloc(size*sizeof(*_dst[i])); + if(_dst[i]==NULL){ + while(i-->0)_ogg_free(_dst[i]); + return TH_EFAULT; + } + memcpy(_dst[i],_src[i],size*sizeof(*_dst[i])); + } + return 0; +} + +/*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]){ + int i; + for(i=0;i<TH_NHUFFMAN_TABLES;i++)_ogg_free(_nodes[i]); +} + + +/*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){ + const unsigned char *ptr; + const unsigned char *stop; + oc_pb_window window; + int available; + long bits; + int node; + int n; + ptr=_opb->ptr; + window=_opb->window; + stop=_opb->stop; + available=_opb->bits; + node=0; + for(;;){ + n=_tree[node]; + if(n>available){ + unsigned shift; + shift=OC_PB_WINDOW_SIZE-available; + do{ + /*We don't bother setting eof because we won't check for it after we've + started decoding DCT tokens.*/ + if(ptr>=stop){ + shift=(unsigned)-OC_LOTS_OF_BITS; + break; + } + shift-=8; + window|=(oc_pb_window)*ptr++<<shift; + } + while(shift>=8); + /*Note: We never request more than 24 bits, so there's no need to fill in + the last partial byte here.*/ + available=OC_PB_WINDOW_SIZE-shift; + } + bits=window>>OC_PB_WINDOW_SIZE-n; + node=_tree[node+1+bits]; + if(node<=0)break; + window<<=n; + available-=n; + } + node=-node; + n=node>>8; + window<<=n; + available-=n; + _opb->ptr=ptr; + _opb->window=window; + _opb->bits=available; + return node&255; +} |