diff options
Diffstat (limited to 'drivers/theora/huffdec.c')
| -rw-r--r-- | drivers/theora/huffdec.c | 489 |
1 files changed, 0 insertions, 489 deletions
diff --git a/drivers/theora/huffdec.c b/drivers/theora/huffdec.c deleted file mode 100644 index 8cf27f0341..0000000000 --- a/drivers/theora/huffdec.c +++ /dev/null @@ -1,489 +0,0 @@ -/******************************************************************** - * * - * 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: huffdec.c 16503 2009-08-22 18:14:02Z giles $ - - ********************************************************************/ - -#include <stdlib.h> -#include <string.h> -#include <ogg/ogg.h> -#include "huffdec.h" -#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 -}; - -/*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 -}; - -/*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_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). - 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). - 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); - 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; - } - } - /*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; - } - } - 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); - } -} - -/*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]; - } - } - else ret->token=_node->token; - return ret; -} - -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; - do{ - 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); - } - return size; -} - -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); - } -} - -/*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; - do{ - loccupancy=occupancy; - occupancy=oc_huff_tree_occupancy(_binode,++depth); - } - 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; -} - -/*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.*/ -int oc_huff_trees_unpack(oc_pack_buf *_opb, - oc_huff_node *_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; - /*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); - } - return 0; -} - -/*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 i; - 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){ - while(i-->0)_ogg_free(_dst[i]); - return TH_EFAULT; - } - _dst[i]=oc_huff_tree_copy(_src[i],&storage); - } - 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]){ - 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); - } - return _node->token; -} |