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+(1<<_node->nbits-_node->nodes[i]->depth);
  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       return ret;
 110     }
 111   }
 112   /*Read a leaf node:*/
 113   else{
 114     if(theorapackB_read(_opb,OC_NDCT_TOKEN_BITS,&bits)<0)return TH_EBADHEADER;
 115     binode=oc_huff_node_alloc(0);
 116     binode->depth=(unsigned char)(_depth>1);
 117     binode->token=(unsigned char)bits;
 118   }
 119   *_binode=binode;
 120   return 0;
 121 }
 122
 123 /*Finds the depth of shortest branch of the given sub-tree.
 124   The tree must be binary.
 125   _binode: The root of the given sub-tree.
 126            _binode->nbits must be 0 or 1.
 127   Return: The smallest depth of a leaf node in this sub-tree.
 128           0 indicates this sub-tree is a leaf node.*/
 129 static int oc_huff_tree_mindepth(oc_huff_node *_binode){
 130   int depth0;
 131   int depth1;
 132   if(_binode->nbits==0)return 0;
 133   depth0=oc_huff_tree_mindepth(_binode->nodes[0]);
 134   depth1=oc_huff_tree_mindepth(_binode->nodes[1]);
 135   return OC_MINI(depth0,depth1)+1;
 136 }
 137
 138 /*Finds the number of internal nodes at a given depth, plus the number of
 139    leaves at that depth or shallower.
 140   The tree must be binary.
 141   _binode: The root of the given sub-tree.
 142            _binode->nbits must be 0 or 1.
 143   Return: The number of entries that would be contained in a jump table of the
 144            given depth.*/
 145 static int oc_huff_tree_occupancy(oc_huff_node *_binode,int _depth){
 146   if(_binode->nbits==0||_depth<=0)return 1;
 147   else{
 148     return oc_huff_tree_occupancy(_binode->nodes[0],_depth-1)+
 149      oc_huff_tree_occupancy(_binode->nodes[1],_depth-1);
 150   }
 151 }
 152
 153 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode);
 154
 155 /*Fills the given nodes table with all the children in the sub-tree at the
 156    given depth.
 157   The nodes in the sub-tree with a depth less than that stored in the table
 158    are freed.
 159   The sub-tree must be binary and complete up until the given depth.
 160   _nodes:  The nodes table to fill.
 161   _binode: The root of the sub-tree to fill it with.
 162            _binode->nbits must be 0 or 1.
 163   _level:  The current level in the table.
 164            0 indicates that the current node should be stored, regardless of
 165             whether it is a leaf node or an internal node.
 166   _depth:  The depth of the nodes to fill the table with, relative to their
 167             parent.*/
 168 static void oc_huff_node_fill(oc_huff_node **_nodes,
 169  oc_huff_node *_binode,int _level,int _depth){
 170   if(_level<=0||_binode->nbits==0){
 171     int i;
 172     _binode->depth=(unsigned char)(_depth-_level);
 173     _nodes[0]=oc_huff_tree_collapse(_binode);
 174     for(i=1;i<1<<_level;i++)_nodes[i]=_nodes[0];
 175   }
 176   else{
 177     _level--;
 178     oc_huff_node_fill(_nodes,_binode->nodes[0],_level,_depth);
 179     oc_huff_node_fill(_nodes+(1<<_level),_binode->nodes[1],_level,_depth);
 180     oc_huff_node_free(_binode);
 181   }
 182 }
 183
 184 /*Finds the largest complete sub-tree rooted at the current node and collapses
 185    it into a single node.
 186   This procedure is then applied recursively to all the children of that node.
 187   _binode: The root of the sub-tree to collapse.
 188            _binode->nbits must be 0 or 1.
 189   Return: The new root of the collapsed sub-tree.*/
 190 static oc_huff_node *oc_huff_tree_collapse(oc_huff_node *_binode){
 191   oc_huff_node *root;
 192   int           mindepth;
 193   int           depth;
 194   int           loccupancy;
 195   int           occupancy;
 196   depth=mindepth=oc_huff_tree_mindepth(_binode);
 197   occupancy=1<<mindepth;
 198   do{
 199     loccupancy=occupancy;
 200     occupancy=oc_huff_tree_occupancy(_binode,++depth);
 201   }
 202   while(occupancy>loccupancy&&occupancy>=1<<OC_MAXI(depth-OC_HUFF_SLUSH,0));
 203   depth--;
 204   if(depth<=1)return _binode;
 205   root=oc_huff_node_alloc(depth);
 206   root->depth=_binode->depth;
 207   oc_huff_node_fill(root->nodes,_binode,depth,depth);
 208   return root;
 209 }
 210
 211 /*Makes a copy of the given Huffman tree.
 212   _node: The Huffman tree to copy.
 213   Return: The copy of the Huffman tree.*/
 214 static oc_huff_node *oc_huff_tree_copy(const oc_huff_node *_node){
 215   oc_huff_node *ret;
 216   ret=oc_huff_node_alloc(_node->nbits);
 217   ret->depth=_node->depth;
 218   if(_node->nbits){
 219     int nchildren;
 220     int i;
 221     int inext;
 222     nchildren=1<<_node->nbits;
 223     for(i=0;i<nchildren;){
 224       ret->nodes[i]=oc_huff_tree_copy(_node->nodes[i]);
 225       inext=i+(1<<_node->nbits-ret->nodes[i]->depth);
 226       while(++i<inext)ret->nodes[i]=ret->nodes[i-1];
 227     }
 228   }
 229   else ret->token=_node->token;
 230   return ret;
 231 }
 232
 233 /*Unpacks a set of Huffman trees, and reduces them to a collapsed
 234    representation.
 235   _opb:   The buffer to unpack the trees from.
 236   _nodes: The table to fill with the Huffman trees.
 237   Return: 0 on success, or a negative value on error.*/
 238 int oc_huff_trees_unpack(oggpack_buffer *_opb,
 239  oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
 240   int i;
 241   for(i=0;i<TH_NHUFFMAN_TABLES;i++){
 242     int ret;
 243     ret=oc_huff_tree_unpack(_opb,_nodes+i,0);
 244     if(ret<0)return ret;
 245     _nodes[i]=oc_huff_tree_collapse(_nodes[i]);
 246   }
 247   return 0;
 248 }
 249
 250 /*Makes a copy of the given set of Huffman trees.
 251   _dst: The array to store the copy in.
 252   _src: The array of trees to copy.*/
 253 void oc_huff_trees_copy(oc_huff_node *_dst[TH_NHUFFMAN_TABLES],
 254  const oc_huff_node *const _src[TH_NHUFFMAN_TABLES]){
 255   int i;
 256   for(i=0;i<TH_NHUFFMAN_TABLES;i++)_dst[i]=oc_huff_tree_copy(_src[i]);
 257 }
 258
 259 /*Frees the memory used by a set of Huffman trees.
 260   _nodes: The array of trees to free.*/
 261 void oc_huff_trees_clear(oc_huff_node *_nodes[TH_NHUFFMAN_TABLES]){
 262   int i;
 263   for(i=0;i<TH_NHUFFMAN_TABLES;i++)oc_huff_tree_free(_nodes[i]);
 264 }
 265
 266 /*Unpacks a single token using the given Huffman tree.
 267   _opb:  The buffer to unpack the token from.
 268   _node: The tree to unpack the token with.
 269   Return: The token value.*/
 270 int oc_huff_token_decode(oggpack_buffer *_opb,const oc_huff_node *_node){
 271   long bits;
 272   while(_node->nbits!=0){
 273     theorapackB_look(_opb,_node->nbits,&bits);
 274     _node=_node->nodes[bits];
 275     theorapackB_adv(_opb,_node->depth);
 276   }
 277   return _node->token;
 278 }