diff options
Diffstat (limited to 'thirdparty/libtheora/huffdec.c')
| -rw-r--r-- | thirdparty/libtheora/huffdec.c | 694 |
1 files changed, 360 insertions, 334 deletions
diff --git a/thirdparty/libtheora/huffdec.c b/thirdparty/libtheora/huffdec.c index 8cf27f0341..5a83c5f150 100644 --- a/thirdparty/libtheora/huffdec.c +++ b/thirdparty/libtheora/huffdec.c @@ -11,7 +11,7 @@ ******************************************************************** function: - last mod: $Id: huffdec.c 16503 2009-08-22 18:14:02Z giles $ + last mod: $Id$ ********************************************************************/ @@ -22,14 +22,60 @@ #include "decint.h" -/*The ANSI offsetof macro is broken on some platforms (e.g., older DECs).*/ -#define _ogg_offsetof(_type,_field)\ - ((size_t)((char *)&((_type *)0)->_field-(char *)0)) -/*The number of internal tokens associated with each of the spec tokens.*/ -static const unsigned char OC_DCT_TOKEN_MAP_ENTRIES[TH_NDCT_TOKENS]={ - 1,1,1,4,8,1,1,8,1,1,1,1,1,2,2,2,2,4,8,2,2,2,4,2,2,2,2,2,8,2,4,8 -}; +/*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 @@ -99,391 +145,371 @@ static const unsigned char OC_DCT_TOKEN_MAP[TH_NDCT_TOKENS]={ 40 }; -/*These three functions are really part of the bitpack.c module, but - they are only used here. - Declaring local static versions so they can be inlined saves considerable - function call overhead.*/ - -static oc_pb_window oc_pack_refill(oc_pack_buf *_b,int _bits){ - const unsigned char *ptr; - const unsigned char *stop; - oc_pb_window window; - int available; - window=_b->window; - available=_b->bits; - ptr=_b->ptr; - stop=_b->stop; - /*This version of _refill() doesn't bother setting eof because we won't - check for it after we've started decoding DCT tokens.*/ - if(ptr>=stop)available=OC_LOTS_OF_BITS; - while(available<=OC_PB_WINDOW_SIZE-8){ - available+=8; - window|=(oc_pb_window)*ptr++<<OC_PB_WINDOW_SIZE-available; - if(ptr>=stop)available=OC_LOTS_OF_BITS; - } - _b->ptr=ptr; - if(_bits>available)window|=*ptr>>(available&7); - _b->bits=available; - return window; -} - - -/*Read in bits without advancing the bit pointer. - Here we assume 0<=_bits&&_bits<=32.*/ -static long oc_pack_look(oc_pack_buf *_b,int _bits){ - oc_pb_window window; - int available; - long result; - window=_b->window; - available=_b->bits; - if(_bits==0)return 0; - if(_bits>available)_b->window=window=oc_pack_refill(_b,_bits); - result=window>>OC_PB_WINDOW_SIZE-_bits; - return result; -} - -/*Advance the bit pointer.*/ -static void oc_pack_adv(oc_pack_buf *_b,int _bits){ - /*We ignore the special cases for _bits==0 and _bits==32 here, since they are - never used actually used. - OC_HUFF_SLUSH (defined below) would have to be at least 27 to actually read - 32 bits in a single go, and would require a 32 GB lookup table (assuming - 8 byte pointers, since 4 byte pointers couldn't fit such a table).*/ - _b->window<<=_bits; - _b->bits-=_bits; -} +/*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 log_2 of the size of a lookup table is allowed to grow to relative to - the number of unique nodes it contains. - E.g., if OC_HUFF_SLUSH is 2, then at most 75% of the space in the tree is - wasted (each node will have an amortized cost of at most 20 bytes when using - 4-byte pointers). +/*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 (requiring as little as 8 bytes amortized per - node, though there will be more nodes). + 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 0 (59.8%). - 11144969 read calls are required when OC_HUFF_SLUSH is 1 (34.6%). - 10538563 read calls are required when OC_HUFF_SLUSH is 2 (32.7%). - 10192578 read calls are required when OC_HUFF_SLUSH is 3 (31.6%). - Since a value of 1 gets us the vast majority of the speed-up with only a - small amount of wasted memory, this is what we use.*/ -#define OC_HUFF_SLUSH (1) - - -/*Determines the size in bytes of a Huffman tree node that represents a - subtree of depth _nbits. - _nbits: The depth of the subtree. - If this is 0, the node is a leaf node. - Otherwise 1<<_nbits pointers are allocated for children. - Return: The number of bytes required to store the node.*/ -static size_t oc_huff_node_size(int _nbits){ - size_t size; - size=_ogg_offsetof(oc_huff_node,nodes); - if(_nbits>0)size+=sizeof(oc_huff_node *)*(1<<_nbits); - return size; -} - -static oc_huff_node *oc_huff_node_init(char **_storage,size_t _size,int _nbits){ - oc_huff_node *ret; - ret=(oc_huff_node *)*_storage; - ret->nbits=(unsigned char)_nbits; - (*_storage)+=_size; - return ret; -} - - -/*Determines the size in bytes of a Huffman tree. - _nbits: The depth of the subtree. - If this is 0, the node is a leaf node. - Otherwise storage for 1<<_nbits pointers are added for children. - Return: The number of bytes required to store the tree.*/ -static size_t oc_huff_tree_size(const oc_huff_node *_node){ - size_t size; - size=oc_huff_node_size(_node->nbits); - if(_node->nbits){ - int nchildren; - int i; - nchildren=1<<_node->nbits; - for(i=0;i<nchildren;i+=1<<_node->nbits-_node->nodes[i]->depth){ - size+=oc_huff_tree_size(_node->nodes[i]); - } - } - return size; -} - - -/*Unpacks a sub-tree from the given buffer. - _opb: The buffer to unpack from. - _binodes: The nodes to store the sub-tree in. - _nbinodes: The number of nodes available for the sub-tree. - Return: 0 on success, or a negative value on error.*/ -static int oc_huff_tree_unpack(oc_pack_buf *_opb, - oc_huff_node *_binodes,int _nbinodes){ - oc_huff_node *binode; - long bits; - int nused; - if(_nbinodes<1)return TH_EBADHEADER; - binode=_binodes; - nused=0; - bits=oc_pack_read1(_opb); - if(oc_pack_bytes_left(_opb)<0)return TH_EBADHEADER; - /*Read an internal node:*/ - if(!bits){ - int ret; - nused++; - binode->nbits=1; - binode->depth=1; - binode->nodes[0]=_binodes+nused; - ret=oc_huff_tree_unpack(_opb,_binodes+nused,_nbinodes-nused); - if(ret>=0){ - nused+=ret; - binode->nodes[1]=_binodes+nused; - ret=oc_huff_tree_unpack(_opb,_binodes+nused,_nbinodes-nused); - } - if(ret<0)return ret; - nused+=ret; - } - /*Read a leaf node:*/ - else{ - int ntokens; - int token; - int i; - bits=oc_pack_read(_opb,OC_NDCT_TOKEN_BITS); + 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; - /*Find out how many internal tokens we translate this external token into.*/ - ntokens=OC_DCT_TOKEN_MAP_ENTRIES[bits]; - if(_nbinodes<2*ntokens-1)return TH_EBADHEADER; - /*Fill in a complete binary tree pointing to the internal tokens.*/ - for(i=1;i<ntokens;i<<=1){ - int j; - binode=_binodes+nused; - nused+=i; - for(j=0;j<i;j++){ - binode[j].nbits=1; - binode[j].depth=1; - binode[j].nodes[0]=_binodes+nused+2*j; - binode[j].nodes[1]=_binodes+nused+2*j+1; - } + /*Read an internal node:*/ + if(!bits){ + len++; + /*Don't allow codewords longer than 32 bits.*/ + if(len>32)return TH_EBADHEADER; } - /*And now the leaf nodes with those tokens.*/ - token=OC_DCT_TOKEN_MAP[bits]; - for(i=0;i<ntokens;i++){ - binode=_binodes+nused++; - binode->nbits=0; - binode->depth=1; - binode->token=token+i; + /*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 nused; -} - -/*Finds the depth of shortest branch of the given sub-tree. - The tree must be binary. - _binode: The root of the given sub-tree. - _binode->nbits must be 0 or 1. - Return: The smallest depth of a leaf node in this sub-tree. - 0 indicates this sub-tree is a leaf node.*/ -static int oc_huff_tree_mindepth(oc_huff_node *_binode){ - int depth0; - int depth1; - if(_binode->nbits==0)return 0; - depth0=oc_huff_tree_mindepth(_binode->nodes[0]); - depth1=oc_huff_tree_mindepth(_binode->nodes[1]); - return OC_MINI(depth0,depth1)+1; -} - -/*Finds the number of internal nodes at a given depth, plus the number of - leaves at that depth or shallower. - The tree must be binary. - _binode: The root of the given sub-tree. - _binode->nbits must be 0 or 1. - Return: The number of entries that would be contained in a jump table of the - given depth.*/ -static int oc_huff_tree_occupancy(oc_huff_node *_binode,int _depth){ - if(_binode->nbits==0||_depth<=0)return 1; - else{ - return oc_huff_tree_occupancy(_binode->nodes[0],_depth-1)+ - oc_huff_tree_occupancy(_binode->nodes[1],_depth-1); - } + return ntokens; } -/*Makes a copy of the given Huffman tree. - _node: The Huffman tree to copy. - Return: The copy of the Huffman tree.*/ -static oc_huff_node *oc_huff_tree_copy(const oc_huff_node *_node, - char **_storage){ - oc_huff_node *ret; - ret=oc_huff_node_init(_storage,oc_huff_node_size(_node->nbits),_node->nbits); - ret->depth=_node->depth; - if(_node->nbits){ - int nchildren; - int i; - int inext; - nchildren=1<<_node->nbits; - for(i=0;i<nchildren;){ - ret->nodes[i]=oc_huff_tree_copy(_node->nodes[i],_storage); - inext=i+(1<<_node->nbits-ret->nodes[i]->depth); - while(++i<inext)ret->nodes[i]=ret->nodes[i-1]; +/*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); } } - else ret->token=_node->token; - return ret; + while(code<0x80000000U); + return ti; } -static size_t oc_huff_tree_collapse_size(oc_huff_node *_binode,int _depth){ - size_t size; - int mindepth; - int depth; - int loccupancy; - int occupancy; - if(_binode->nbits!=0&&_depth>0){ - return oc_huff_tree_collapse_size(_binode->nodes[0],_depth-1)+ - oc_huff_tree_collapse_size(_binode->nodes[1],_depth-1); - } - depth=mindepth=oc_huff_tree_mindepth(_binode); - occupancy=1<<mindepth; +/*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; - occupancy=oc_huff_tree_occupancy(_binode,++depth); - } - while(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0)); - depth--; - size=oc_huff_node_size(depth); - if(depth>0){ - size+=oc_huff_tree_collapse_size(_binode->nodes[0],depth-1); - size+=oc_huff_tree_collapse_size(_binode->nodes[1],depth-1); + 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); + } } - return size; + while(occupancy>loccupancy&&occupancy*slush>=1<<nbits); + return best_nbits; } -static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode, - char **_storage); - -/*Fills the given nodes table with all the children in the sub-tree at the - given depth. - The nodes in the sub-tree with a depth less than that stored in the table - are freed. - The sub-tree must be binary and complete up until the given depth. - _nodes: The nodes table to fill. - _binode: The root of the sub-tree to fill it with. - _binode->nbits must be 0 or 1. - _level: The current level in the table. - 0 indicates that the current node should be stored, regardless of - whether it is a leaf node or an internal node. - _depth: The depth of the nodes to fill the table with, relative to their - parent.*/ -static void oc_huff_node_fill(oc_huff_node **_nodes, - oc_huff_node *_binode,int _level,int _depth,char **_storage){ - if(_level<=0||_binode->nbits==0){ - int i; - _binode->depth=(unsigned char)(_depth-_level); - _nodes[0]=oc_huff_tree_collapse(_binode,_storage); - for(i=1;i<1<<_level;i++)_nodes[i]=_nodes[0]; - } - else{ - _level--; - oc_huff_node_fill(_nodes,_binode->nodes[0],_level,_depth,_storage); - _nodes+=1<<_level; - oc_huff_node_fill(_nodes,_binode->nodes[1],_level,_depth,_storage); - } +/*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); } -/*Finds the largest complete sub-tree rooted at the current node and collapses - it into a single node. - This procedure is then applied recursively to all the children of that node. - _binode: The root of the sub-tree to collapse. - _binode->nbits must be 0 or 1. - Return: The new root of the collapsed sub-tree.*/ -static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode, - char **_storage){ - oc_huff_node *root; - size_t size; - int mindepth; - int depth; - int loccupancy; - int occupancy; - depth=mindepth=oc_huff_tree_mindepth(_binode); - occupancy=1<<mindepth; +/*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{ - loccupancy=occupancy; - occupancy=oc_huff_tree_occupancy(_binode,++depth); + 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(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0)); - depth--; - if(depth<=1)return oc_huff_tree_copy(_binode,_storage); - size=oc_huff_node_size(depth); - root=oc_huff_node_init(_storage,size,depth); - root->depth=_binode->depth; - oc_huff_node_fill(root->nodes,_binode,depth,depth,_storage); - return root; + 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.*/ + 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, - oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){ + ogg_int16_t *_nodes[TH_NHUFFMAN_TABLES]){ int i; for(i=0;i<TH_NHUFFMAN_TABLES;i++){ - oc_huff_node nodes[511]; - char *storage; - size_t size; - int ret; + unsigned char tokens[256][2]; + int ntokens; + ogg_int16_t *tree; + size_t size; /*Unpack the full tree into a temporary buffer.*/ - ret=oc_huff_tree_unpack(_opb,nodes,sizeof(nodes)/sizeof(*nodes)); - if(ret<0)return ret; - /*Figure out how big the collapsed tree will be.*/ - size=oc_huff_tree_collapse_size(nodes,0); - storage=(char *)_ogg_calloc(1,size); - if(storage==NULL)return TH_EFAULT; - /*And collapse it.*/ - _nodes[i]=oc_huff_tree_collapse(nodes,&storage); + 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(oc_huff_node *_dst[TH_NHUFFMAN_TABLES], - const oc_huff_node *const _src[TH_NHUFFMAN_TABLES]){ +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; - char *storage; - size=oc_huff_tree_size(_src[i]); - storage=(char *)_ogg_calloc(1,size); - if(storage==NULL){ + 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; } - _dst[i]=oc_huff_tree_copy(_src[i],&storage); + 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(oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){ +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(oc_pack_buf *_opb,const oc_huff_node *_node){ - long bits; - while(_node->nbits!=0){ - bits=oc_pack_look(_opb,_node->nbits); - _node=_node->nodes[bits]; - oc_pack_adv(_opb,_node->depth); +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; } - return _node->token; + node=-node; + n=node>>8; + window<<=n; + available-=n; + _opb->ptr=ptr; + _opb->window=window; + _opb->bits=available; + return node&255; } |