theora/lib/dec/huffdec.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2007                *
   9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13   function:
  14     last mod: $Id$
  15
  16  ********************************************************************/
  17
  18 #include <stdlib.h>
  19 #include <ogg/ogg.h>
  20 #include "huffdec.h"
  21 #include "decint.h"
  22
  23
  24 /*The ANSI offsetof macro is broken on some platforms (e.g., older DECs).*/
  25 #define _ogg_offsetof(_type,_field)\
  26  ((size_t)((char *)&((_type *)0)->_field-(char *)0))
  27
  28 /*The log_2 of the size of a lookup table is allowed to grow to relative to
  29    the number of unique nodes it contains.
  30   E.g., if OC_HUFF_SLUSH is 2, then at most 75% of the space in the tree is
  31    wasted (each node will have an amortized cost of at most 20 bytes when using
  32    4-byte pointers).
  33   Larger numbers can decode tokens with fewer read operations, while smaller
  34    numbers may save more space (requiring as little as 8 bytes amortized per
  35    node, though there will be more nodes).
  36   With a sample file:
  37   32233473 read calls are required when no tree collapsing is done (100.0%).
  38   19269269 read calls are required when OC_HUFF_SLUSH is 0 (59.8%).
  39   11144969 read calls are required when OC_HUFF_SLUSH is 1 (34.6%).
  40   10538563 read calls are required when OC_HUFF_SLUSH is 2 (32.7%).
  41   10192578 read calls are required when OC_HUFF_SLUSH is 3 (31.6%).
  42   Since a value of 1 gets us the vast majority of the speed-up with only a
  43    small amount of wasted memory, this is what we use.*/
  44 #define OC_HUFF_SLUSH (1)
  45
  46
  47 /*Allocates a Huffman tree node that represents a subtree of depth _nbits.
  48   _nbits: The depth of the subtree.
  49           If this is 0, the node is a leaf node.
  50           Otherwise 1<<_nbits pointers are allocated for children.
  51   Return: The newly allocated and fully initialized Huffman tree node.*/
  52 static oc_huff_node *oc_huff_node_alloc(int _nbits){
  53   oc_huff_node *ret;
  54   size_t        size;
  55   size=_ogg_offsetof(oc_huff_node,nodes);
  56   if(_nbits>0)size+=sizeof(oc_huff_node *)*(1<<_nbits);
  57   ret=_ogg_calloc(1,size);
  58   ret->nbits=(unsigned char)_nbits;
  59   return ret;
  60 }
  61
  62 /*Frees a Huffman tree node allocated with oc_huf_node_alloc.
  63   _node: The node to free.
  64          This may be NULL.*/
  65 static void oc_huff_node_free(oc_huff_node *_node){
  66   _ogg_free(_node);
  67 }
  68
  69 /*Frees the memory used by a Huffman tree.
  70   _node: The Huffman tree to free.
  71          This may be NULL.*/
  72 static void oc_huff_tree_free(oc_huff_node *_node){
  73   if(_node==NULL)return;
  74   if(_node->nbits){
  75     int nchildren;
  76     int i;
  77     int inext;
  78     nchildren=1<<_node->nbits;
  79     for(i=0;i<nchildren;i=inext){
  80       inext=i+(_node->nodes[i]!=NULL?1<<_node->nbits-_node->nodes[i]->depth:1);
  81       oc_huff_tree_free(_node->nodes[i]);
  82     }
  83   }
  84   oc_huff_node_free(_node);
  85 }
  86
  87 /*Unpacks a sub-tree from the given buffer.
  88   _opb:    The buffer to unpack from.
  89   _binode: The location to store a pointer to the sub-tree in.
  90   _depth:  The current depth of the tree.
  91            This is used to prevent infinite recursion.
  92   Return: 0 on success, or a negative value on error.*/
  93 static int oc_huff_tree_unpack(oggpack_buffer *_opb,
  94  oc_huff_node **_binode,int _depth){
  95   oc_huff_node *binode;
  96   long          bits;
  97   /*Prevent infinite recursion.*/
  98   if(++_depth>32)return TH_EBADHEADER;
  99   if(theorapackB_read1(_opb,&bits)<0)return TH_EBADHEADER;
 100   /*Read an internal node:*/
 101   if(!bits){
 102     int ret;
 103     binode=oc_huff_node_alloc(1);
 104     binode->depth=(unsigned char)(_depth>1);
 105     ret=oc_huff_tree_unpack(_opb,binode->nodes,_depth);
 106     if(ret>=0)ret=oc_huff_tree_unpack(_opb,binode->nodes+1,_depth);
 107     if(ret<0){
 108       oc_huff_tree_free(binode);
 109       *_binode=NULL;
 110       return ret;
 111     }
 112   }
 113   /*Read a leaf node:*/
 114   else{
 115     if(theorapackB_read(_opb,OC_NDCT_TOKEN_BITS,&bits)<0)return TH_EBADHEADER;
 116     binode=oc_huff_node_alloc(0);
 117     binode->depth=(unsigned char)(_depth>1);
 118     binode->token=(unsigned char)bits;
 119   }
 120   *_binode=binode;
 121   return 0;
 122 }
 123
 124 /*Finds the depth of shortest branch of the given sub-tree.
 125   The tree must be binary.
 126   _binode: The root of the given sub-tree.
 127            _binode->nbits must be 0 or 1.
 128   Return: The smallest depth of a leaf node in this sub-tree.
 129           0 indicates this sub-tree is a leaf node.*/
 130 static int oc_huff_tree_mindepth(oc_huff_node *_binode){
 131   int depth0;
 132   int depth1;
 133   if(_binode->nbits==0)return 0;
 134   depth0=oc_huff_tree_mindepth(_binode->nodes[0]);
 135   depth1=oc_huff_tree_mindepth(_binode->nodes[1]);
 136   return OC_MINI(depth0,depth1)+1;
 137 }
 138
 139 /*Finds the number of internal nodes at a given depth, plus the number of
 140    leaves at that depth or shallower.
 141   The tree must be binary.
 142   _binode: The root of the given sub-tree.
 143            _binode->nbits must be 0 or 1.
 144   Return: The number of entries that would be contained in a jump table of the
 145            given depth.*/
 146 static int oc_huff_tree_occupancy(oc_huff_node *_binode,int _depth){
 147   if(_binode->nbits==0||_depth<=0)return 1;
 148   else{
 149     return oc_huff_tree_occupancy(_binode->nodes[0],_depth-1)+
 150      oc_huff_tree_occupancy(_binode->nodes[1],_depth-1);
 151   }
 152 }
 153
 154 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode);
 155
 156 /*Fills the given nodes table with all the children in the sub-tree at the
 157    given depth.
 158   The nodes in the sub-tree with a depth less than that stored in the table
 159    are freed.
 160   The sub-tree must be binary and complete up until the given depth.
 161   _nodes:  The nodes table to fill.
 162   _binode: The root of the sub-tree to fill it with.
 163            _binode->nbits must be 0 or 1.
 164   _level:  The current level in the table.
 165            0 indicates that the current node should be stored, regardless of
 166             whether it is a leaf node or an internal node.
 167   _depth:  The depth of the nodes to fill the table with, relative to their
 168             parent.*/
 169 static void oc_huff_node_fill(oc_huff_node **_nodes,
 170  oc_huff_node *_binode,int _level,int _depth){
 171   if(_level<=0||_binode->nbits==0){
 172     int i;
 173     _binode->depth=(unsigned char)(_depth-_level);
 174     _nodes[0]=oc_huff_tree_collapse(_binode);
 175     for(i=1;i<1<<_level;i++)_nodes[i]=_nodes[0];
 176   }
 177   else{
 178     _level--;
 179     oc_huff_node_fill(_nodes,_binode->nodes[0],_level,_depth);
 180     oc_huff_node_fill(_nodes+(1<<_level),_binode->nodes[1],_level,_depth);
 181     oc_huff_node_free(_binode);
 182   }
 183 }
 184
 185 /*Finds the largest complete sub-tree rooted at the current node and collapses
 186    it into a single node.
 187   This procedure is then applied recursively to all the children of that node.
 188   _binode: The root of the sub-tree to collapse.
 189            _binode->nbits must be 0 or 1.
 190   Return: The new root of the collapsed sub-tree.*/
 191 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode){
 192   oc_huff_node *root;
 193   int           mindepth;
 194   int           depth;
 195   int           loccupancy;
 196   int           occupancy;
 197   depth=mindepth=oc_huff_tree_mindepth(_binode);
 198   occupancy=1<<mindepth;
 199   do{
 200     loccupancy=occupancy;
 201     occupancy=oc_huff_tree_occupancy(_binode,++depth);
 202   }
 203   while(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0));
 204   depth--;
 205   if(depth<=1)return _binode;
 206   root=oc_huff_node_alloc(depth);
 207   root->depth=_binode->depth;
 208   oc_huff_node_fill(root->nodes,_binode,depth,depth);
 209   return root;
 210 }
 211
 212 /*Makes a copy of the given Huffman tree.
 213   _node: The Huffman tree to copy.
 214   Return: The copy of the Huffman tree.*/
 215 static oc_huff_node *oc_huff_tree_copy(const oc_huff_node *_node){
 216   oc_huff_node *ret;
 217   ret=oc_huff_node_alloc(_node->nbits);
 218   ret->depth=_node->depth;
 219   if(_node->nbits){
 220     int nchildren;
 221     int i;
 222     int inext;
 223     nchildren=1<<_node->nbits;
 224     for(i=0;i<nchildren;){
 225       ret->nodes[i]=oc_huff_tree_copy(_node->nodes[i]);
 226       inext=i+(1<<_node->nbits-ret->nodes[i]->depth);
 227       while(++i<inext)ret->nodes[i]=ret->nodes[i-1];
 228     }
 229   }
 230   else ret->token=_node->token;
 231   return ret;
 232 }
 233
 234 /*Unpacks a set of Huffman trees, and reduces them to a collapsed
 235    representation.
 236   _opb:   The buffer to unpack the trees from.
 237   _nodes: The table to fill with the Huffman trees.
 238   Return: 0 on success, or a negative value on error.*/
 239 int oc_huff_trees_unpack(oggpack_buffer *_opb,
 240  oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
 241   int i;
 242   for(i=0;i<TH_NHUFFMAN_TABLES;i++){
 243     int ret;
 244     ret=oc_huff_tree_unpack(_opb,_nodes+i,0);
 245     if(ret<0)return ret;
 246     _nodes[i]=oc_huff_tree_collapse(_nodes[i]);
 247   }
 248   return 0;
 249 }
 250
 251 /*Makes a copy of the given set of Huffman trees.
 252   _dst: The array to store the copy in.
 253   _src: The array of trees to copy.*/
 254 void oc_huff_trees_copy(oc_huff_node *_dst[TH_NHUFFMAN_TABLES],
 255  const oc_huff_node *const _src[TH_NHUFFMAN_TABLES]){
 256   int i;
 257   for(i=0;i<TH_NHUFFMAN_TABLES;i++)_dst[i]=oc_huff_tree_copy(_src[i]);
 258 }
 259
 260 /*Frees the memory used by a set of Huffman trees.
 261   _nodes: The array of trees to free.*/
 262 void oc_huff_trees_clear(oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
 263   int i;
 264   for(i=0;i<TH_NHUFFMAN_TABLES;i++)oc_huff_tree_free(_nodes[i]);
 265 }
 266
 267 /*Unpacks a single token using the given Huffman tree.
 268   _opb:  The buffer to unpack the token from.
 269   _node: The tree to unpack the token with.
 270   Return: The token value.*/
 271 int oc_huff_token_decode(oggpack_buffer *_opb,const oc_huff_node *_node){
 272   long bits;
 273   while(_node->nbits!=0){
 274     theorapackB_look(_opb,_node->nbits,&bits);
 275     _node=_node->nodes[bits];
 276     theorapackB_adv(_opb,_node->depth);
 277   }
 278   return _node->token;
 279 }