theora-old/lib/huffman.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-2003                *
   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 <stdio.h>
  20 #include "codec_internal.h"
  21 #include "hufftables.h"
  22
  23 static void CreateHuffmanList(HUFF_ENTRY ** HuffRoot,
  24                               ogg_uint32_t HIndex,
  25                               const ogg_uint32_t *FreqList ) {
  26   int i;
  27   HUFF_ENTRY *entry_ptr;
  28   HUFF_ENTRY *search_ptr;
  29
  30   /* Create a HUFF entry for token zero. */
  31   HuffRoot[HIndex] = (HUFF_ENTRY *)_ogg_calloc(1,sizeof(*HuffRoot[HIndex]));
  32
  33   HuffRoot[HIndex]->Previous = NULL;
  34   HuffRoot[HIndex]->Next = NULL;
  35   HuffRoot[HIndex]->ZeroChild = NULL;
  36   HuffRoot[HIndex]->OneChild = NULL;
  37   HuffRoot[HIndex]->Value = 0;
  38   HuffRoot[HIndex]->Frequency = FreqList[0];
  39
  40   if ( HuffRoot[HIndex]->Frequency == 0 )
  41     HuffRoot[HIndex]->Frequency = 1;
  42
  43   /* Now add entries for all the other possible tokens. */
  44   for ( i = 1; i < MAX_ENTROPY_TOKENS; i++ ) {
  45     entry_ptr = (HUFF_ENTRY *)_ogg_calloc(1,sizeof(*entry_ptr));
  46
  47     entry_ptr->Value = i;
  48     entry_ptr->Frequency = FreqList[i];
  49     entry_ptr->ZeroChild = NULL;
  50     entry_ptr->OneChild = NULL;
  51
  52     /* Force min value of 1. This prevents the tree getting too deep. */
  53     if ( entry_ptr->Frequency == 0 )
  54       entry_ptr->Frequency = 1;
  55
  56     if ( entry_ptr->Frequency <= HuffRoot[HIndex]->Frequency ){
  57       entry_ptr->Next = HuffRoot[HIndex];
  58       HuffRoot[HIndex]->Previous = entry_ptr;
  59       entry_ptr->Previous = NULL;
  60       HuffRoot[HIndex] = entry_ptr;
  61     }else{
  62       search_ptr = HuffRoot[HIndex];
  63       while ( (search_ptr->Next != NULL) &&
  64               (search_ptr->Frequency < entry_ptr->Frequency) ){
  65         search_ptr = (HUFF_ENTRY *)search_ptr->Next;
  66       }
  67
  68       if ( search_ptr->Frequency < entry_ptr->Frequency ){
  69         entry_ptr->Next = NULL;
  70         entry_ptr->Previous = search_ptr;
  71         search_ptr->Next = entry_ptr;
  72       }else{
  73         entry_ptr->Next = search_ptr;
  74         entry_ptr->Previous = search_ptr->Previous;
  75         search_ptr->Previous->Next = entry_ptr;
  76         search_ptr->Previous = entry_ptr;
  77       }
  78     }
  79   }
  80 }
  81
  82 static void CreateCodeArray( HUFF_ENTRY * HuffRoot,
  83                       ogg_uint32_t *HuffCodeArray,
  84                       unsigned char *HuffCodeLengthArray,
  85                       ogg_uint32_t CodeValue,
  86                       unsigned char CodeLength ) {
  87
  88   /* If we are at a leaf then fill in a code array entry. */
  89   if ( ( HuffRoot->ZeroChild == NULL ) && ( HuffRoot->OneChild == NULL ) ){
  90     HuffCodeArray[HuffRoot->Value] = CodeValue;
  91     HuffCodeLengthArray[HuffRoot->Value] = CodeLength;
  92   }else{
  93     /* Recursive calls to scan down the tree. */
  94     CodeLength++;
  95     CreateCodeArray(HuffRoot->ZeroChild, HuffCodeArray, HuffCodeLengthArray,
  96                     ((CodeValue << 1) + 0), CodeLength);
  97     CreateCodeArray(HuffRoot->OneChild, HuffCodeArray, HuffCodeLengthArray,
  98                     ((CodeValue << 1) + 1), CodeLength);
  99   }
 100 }
 101
 102 static void  BuildHuffmanTree( HUFF_ENTRY **HuffRoot,
 103                         ogg_uint32_t *HuffCodeArray,
 104                         unsigned char *HuffCodeLengthArray,
 105                         ogg_uint32_t HIndex,
 106                         const ogg_uint32_t *FreqList ){
 107
 108   HUFF_ENTRY *entry_ptr;
 109   HUFF_ENTRY *search_ptr;
 110
 111   /* First create a sorted linked list representing the frequencies of
 112      each token. */
 113   CreateHuffmanList( HuffRoot, HIndex, FreqList );
 114
 115   /* Now build the tree from the list. */
 116
 117   /* While there are at least two items left in the list. */
 118   while ( HuffRoot[HIndex]->Next != NULL ){
 119     /* Create the new node as the parent of the first two in the list. */
 120     entry_ptr = (HUFF_ENTRY *)_ogg_calloc(1,sizeof(*entry_ptr));
 121     entry_ptr->Value = -1;
 122     entry_ptr->Frequency = HuffRoot[HIndex]->Frequency +
 123       HuffRoot[HIndex]->Next->Frequency ;
 124     entry_ptr->ZeroChild = HuffRoot[HIndex];
 125     entry_ptr->OneChild = HuffRoot[HIndex]->Next;
 126
 127     /* If there are still more items in the list then insert the new
 128        node into the list. */
 129     if (entry_ptr->OneChild->Next != NULL ){
 130       /* Set up the provisional 'new root' */
 131       HuffRoot[HIndex] = entry_ptr->OneChild->Next;
 132       HuffRoot[HIndex]->Previous = NULL;
 133
 134       /* Now scan through the remaining list to insert the new entry
 135          at the appropriate point. */
 136       if ( entry_ptr->Frequency <= HuffRoot[HIndex]->Frequency ){
 137         entry_ptr->Next = HuffRoot[HIndex];
 138         HuffRoot[HIndex]->Previous = entry_ptr;
 139         entry_ptr->Previous = NULL;
 140         HuffRoot[HIndex] = entry_ptr;
 141       }else{
 142         search_ptr = HuffRoot[HIndex];
 143         while ( (search_ptr->Next != NULL) &&
 144                 (search_ptr->Frequency < entry_ptr->Frequency) ){
 145           search_ptr = search_ptr->Next;
 146         }
 147
 148         if ( search_ptr->Frequency < entry_ptr->Frequency ){
 149           entry_ptr->Next = NULL;
 150           entry_ptr->Previous = search_ptr;
 151           search_ptr->Next = entry_ptr;
 152         }else{
 153           entry_ptr->Next = search_ptr;
 154           entry_ptr->Previous = search_ptr->Previous;
 155           search_ptr->Previous->Next = entry_ptr;
 156           search_ptr->Previous = entry_ptr;
 157         }
 158       }
 159     }else{
 160       /* Build has finished. */
 161       entry_ptr->Next = NULL;
 162       entry_ptr->Previous = NULL;
 163       HuffRoot[HIndex] = entry_ptr;
 164     }
 165
 166     /* Delete the Next/Previous properties of the children (PROB NOT NEC). */
 167     entry_ptr->ZeroChild->Next = NULL;
 168     entry_ptr->ZeroChild->Previous = NULL;
 169     entry_ptr->OneChild->Next = NULL;
 170     entry_ptr->OneChild->Previous = NULL;
 171
 172   }
 173
 174   /* Now build a code array from the tree. */
 175   CreateCodeArray( HuffRoot[HIndex], HuffCodeArray,
 176                    HuffCodeLengthArray, 0, 0);
 177 }
 178
 179 static void  DestroyHuffTree(HUFF_ENTRY *root_ptr){
 180   if (root_ptr){
 181     if ( root_ptr->ZeroChild )
 182       DestroyHuffTree(root_ptr->ZeroChild);
 183
 184     if ( root_ptr->OneChild )
 185       DestroyHuffTree(root_ptr->OneChild);
 186
 187     _ogg_free(root_ptr);
 188   }
 189 }
 190
 191 void ClearHuffmanSet( PB_INSTANCE *pbi ){
 192   int i;
 193
 194   ClearHuffmanTrees(pbi->HuffRoot_VP3x);
 195
 196   for ( i = 0; i < NUM_HUFF_TABLES; i++ )
 197     if (pbi->HuffCodeArray_VP3x[i])
 198       _ogg_free (pbi->HuffCodeArray_VP3x[i]);
 199
 200   for ( i = 0; i < NUM_HUFF_TABLES; i++ )
 201     if (pbi->HuffCodeLengthArray_VP3x[i])
 202       _ogg_free (pbi->HuffCodeLengthArray_VP3x[i]);
 203 }
 204
 205 void InitHuffmanSet( PB_INSTANCE *pbi ){
 206   int i;
 207
 208   ClearHuffmanSet(pbi);
 209
 210   pbi->ExtraBitLengths_VP3x = ExtraBitLengths_VP31;
 211
 212   for ( i = 0; i < NUM_HUFF_TABLES; i++ ){
 213     pbi->HuffCodeArray_VP3x[i] =
 214       _ogg_calloc(MAX_ENTROPY_TOKENS,
 215                   sizeof(*pbi->HuffCodeArray_VP3x[i]));
 216     pbi->HuffCodeLengthArray_VP3x[i] =
 217       _ogg_calloc(MAX_ENTROPY_TOKENS,
 218                   sizeof(*pbi->HuffCodeLengthArray_VP3x[i]));
 219     BuildHuffmanTree( pbi->HuffRoot_VP3x,
 220                       pbi->HuffCodeArray_VP3x[i],
 221                       pbi->HuffCodeLengthArray_VP3x[i],
 222                       i, FrequencyCounts_VP3[i]);
 223   }
 224 }
 225
 226 static int ReadHuffTree(HUFF_ENTRY * HuffRoot, int depth,
 227                         oggpack_buffer *opb) {
 228   long bit;
 229   long ret;
 230   theora_read(opb,1,&bit);
 231   if(bit < 0) return OC_BADHEADER;
 232   else if(!bit) {
 233     int ret;
 234     if (++depth > 32) return OC_BADHEADER;
 235     HuffRoot->ZeroChild = (HUFF_ENTRY *)_ogg_calloc(1, sizeof(HUFF_ENTRY));
 236     ret = ReadHuffTree(HuffRoot->ZeroChild, depth, opb);
 237     if (ret < 0) return ret;
 238     HuffRoot->OneChild = (HUFF_ENTRY *)_ogg_calloc(1, sizeof(HUFF_ENTRY));
 239     ret = ReadHuffTree(HuffRoot->OneChild, depth, opb);
 240     if (ret < 0) return ret;
 241     HuffRoot->Value = -1;
 242   } else {
 243     HuffRoot->ZeroChild = NULL;
 244     HuffRoot->OneChild = NULL;
 245     theora_read(opb,5,&ret);
 246     HuffRoot->Value=ret;;
 247     if (HuffRoot->Value < 0) return OC_BADHEADER;
 248   }
 249   return 0;
 250 }
 251
 252 int ReadHuffmanTrees(codec_setup_info *ci, oggpack_buffer *opb) {
 253   int i;
 254   for (i=0; i<NUM_HUFF_TABLES; i++) {
 255      int ret;
 256      ci->HuffRoot[i] = (HUFF_ENTRY *)_ogg_calloc(1, sizeof(HUFF_ENTRY));
 257      ret = ReadHuffTree(ci->HuffRoot[i], 0, opb);
 258      if (ret) return ret;
 259   }
 260   return 0;
 261 }
 262
 263 static void WriteHuffTree(HUFF_ENTRY *HuffRoot, oggpack_buffer *opb) {
 264   if (HuffRoot->Value >= 0) {
 265     oggpackB_write(opb, 1, 1);
 266     oggpackB_write(opb, HuffRoot->Value, 5);
 267   } else {
 268     oggpackB_write(opb, 0, 1);
 269     WriteHuffTree(HuffRoot->ZeroChild, opb);
 270     WriteHuffTree(HuffRoot->OneChild, opb);
 271   }
 272 }
 273
 274 void WriteHuffmanTrees(HUFF_ENTRY *HuffRoot[NUM_HUFF_TABLES],
 275                        oggpack_buffer *opb) {
 276   int i;
 277   for(i=0; i<NUM_HUFF_TABLES; i++) {
 278     WriteHuffTree(HuffRoot[i], opb);
 279   }
 280 }
 281
 282 static HUFF_ENTRY *CopyHuffTree(const HUFF_ENTRY *HuffSrc) {
 283   if(HuffSrc){
 284     HUFF_ENTRY *HuffDst;
 285     HuffDst = (HUFF_ENTRY *)_ogg_calloc(1, sizeof(HUFF_ENTRY));
 286     HuffDst->Value = HuffSrc->Value;
 287     if (HuffSrc->Value < 0) {
 288       HuffDst->ZeroChild = CopyHuffTree(HuffSrc->ZeroChild);
 289       HuffDst->OneChild = CopyHuffTree(HuffSrc->OneChild);
 290     }
 291     return HuffDst;
 292   }
 293   return NULL;
 294 }
 295
 296 void InitHuffmanTrees(PB_INSTANCE *pbi, const codec_setup_info *ci) {
 297   int i;
 298   pbi->ExtraBitLengths_VP3x = ExtraBitLengths_VP31;
 299   for(i=0; i<NUM_HUFF_TABLES; i++){
 300     pbi->HuffRoot_VP3x[i] = CopyHuffTree(ci->HuffRoot[i]);
 301   }
 302 }
 303
 304 void  ClearHuffmanTrees(HUFF_ENTRY *HuffRoot[NUM_HUFF_TABLES]){
 305   int i;
 306   for(i=0; i<NUM_HUFF_TABLES; i++) {
 307     DestroyHuffTree(HuffRoot[i]);
 308     HuffRoot[i] = NULL;
 309   }
 310 }