misc/libtremor/tremor/codebook.c
branchhedgeroid
changeset 6045 9a7cc0f29430
parent 6043 9bd2d6b1ba52
child 7697 767d3c4153a1
equal deleted inserted replaced
6043:9bd2d6b1ba52 6045:9a7cc0f29430
       
     1 /********************************************************************
       
     2  *                                                                  *
       
     3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
       
     4  *                                                                  *
       
     5  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
       
     6  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
       
     7  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
       
     8  *                                                                  *
       
     9  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
       
    10  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
       
    11  *                                                                  *
       
    12  ********************************************************************
       
    13 
       
    14  function: basic codebook pack/unpack/code/decode operations
       
    15 
       
    16  ********************************************************************/
       
    17 
       
    18 #include <stdlib.h>
       
    19 #include <string.h>
       
    20 #include <math.h>
       
    21 #include "ogg.h"
       
    22 #include "ivorbiscodec.h"
       
    23 #include "codebook.h"
       
    24 #include "misc.h"
       
    25 
       
    26 /* unpacks a codebook from the packet buffer into the codebook struct,
       
    27    readies the codebook auxiliary structures for decode *************/
       
    28 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
       
    29   long i,j;
       
    30   memset(s,0,sizeof(*s));
       
    31 
       
    32   /* make sure alignment is correct */
       
    33   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
       
    34 
       
    35   /* first the basic parameters */
       
    36   s->dim=oggpack_read(opb,16);
       
    37   s->entries=oggpack_read(opb,24);
       
    38   if(s->entries==-1)goto _eofout;
       
    39 
       
    40   /* codeword ordering.... length ordered or unordered? */
       
    41   switch((int)oggpack_read(opb,1)){
       
    42   case 0:
       
    43     /* unordered */
       
    44     s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
       
    45 
       
    46     /* allocated but unused entries? */
       
    47     if(oggpack_read(opb,1)){
       
    48       /* yes, unused entries */
       
    49 
       
    50       for(i=0;i<s->entries;i++){
       
    51 	if(oggpack_read(opb,1)){
       
    52 	  long num=oggpack_read(opb,5);
       
    53 	  if(num==-1)goto _eofout;
       
    54 	  s->lengthlist[i]=num+1;
       
    55 	}else
       
    56 	  s->lengthlist[i]=0;
       
    57       }
       
    58     }else{
       
    59       /* all entries used; no tagging */
       
    60       for(i=0;i<s->entries;i++){
       
    61 	long num=oggpack_read(opb,5);
       
    62 	if(num==-1)goto _eofout;
       
    63 	s->lengthlist[i]=num+1;
       
    64       }
       
    65     }
       
    66     
       
    67     break;
       
    68   case 1:
       
    69     /* ordered */
       
    70     {
       
    71       long length=oggpack_read(opb,5)+1;
       
    72       s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
       
    73 
       
    74       for(i=0;i<s->entries;){
       
    75 	long num=oggpack_read(opb,_ilog(s->entries-i));
       
    76 	if(num==-1)goto _eofout;
       
    77 	for(j=0;j<num && i<s->entries;j++,i++)
       
    78 	  s->lengthlist[i]=length;
       
    79 	length++;
       
    80       }
       
    81     }
       
    82     break;
       
    83   default:
       
    84     /* EOF */
       
    85     return(-1);
       
    86   }
       
    87   
       
    88   /* Do we have a mapping to unpack? */
       
    89   switch((s->maptype=oggpack_read(opb,4))){
       
    90   case 0:
       
    91     /* no mapping */
       
    92     break;
       
    93   case 1: case 2:
       
    94     /* implicitly populated value mapping */
       
    95     /* explicitly populated value mapping */
       
    96 
       
    97     s->q_min=oggpack_read(opb,32);
       
    98     s->q_delta=oggpack_read(opb,32);
       
    99     s->q_quant=oggpack_read(opb,4)+1;
       
   100     s->q_sequencep=oggpack_read(opb,1);
       
   101 
       
   102     {
       
   103       int quantvals=0;
       
   104       switch(s->maptype){
       
   105       case 1:
       
   106 	quantvals=_book_maptype1_quantvals(s);
       
   107 	break;
       
   108       case 2:
       
   109 	quantvals=s->entries*s->dim;
       
   110 	break;
       
   111       }
       
   112       
       
   113       /* quantized values */
       
   114       s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
       
   115       for(i=0;i<quantvals;i++)
       
   116 	s->quantlist[i]=oggpack_read(opb,s->q_quant);
       
   117       
       
   118       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
       
   119     }
       
   120     break;
       
   121   default:
       
   122     goto _errout;
       
   123   }
       
   124 
       
   125   /* all set */
       
   126   return(0);
       
   127   
       
   128  _errout:
       
   129  _eofout:
       
   130   vorbis_staticbook_clear(s);
       
   131   return(-1); 
       
   132 }
       
   133 
       
   134 /* the 'eliminate the decode tree' optimization actually requires the
       
   135    codewords to be MSb first, not LSb.  This is an annoying inelegancy
       
   136    (and one of the first places where carefully thought out design
       
   137    turned out to be wrong; Vorbis II and future Ogg codecs should go
       
   138    to an MSb bitpacker), but not actually the huge hit it appears to
       
   139    be.  The first-stage decode table catches most words so that
       
   140    bitreverse is not in the main execution path. */
       
   141 
       
   142 static ogg_uint32_t bitreverse(ogg_uint32_t x){
       
   143   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
       
   144   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
       
   145   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
       
   146   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
       
   147   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
       
   148 }
       
   149 
       
   150 STIN long decode_packed_entry_number(codebook *book, 
       
   151 					      oggpack_buffer *b){
       
   152   int  read=book->dec_maxlength;
       
   153   long lo,hi;
       
   154   long lok = oggpack_look(b,book->dec_firsttablen);
       
   155  
       
   156   if (lok >= 0) {
       
   157     long entry = book->dec_firsttable[lok];
       
   158     if(entry&0x80000000UL){
       
   159       lo=(entry>>15)&0x7fff;
       
   160       hi=book->used_entries-(entry&0x7fff);
       
   161     }else{
       
   162       oggpack_adv(b, book->dec_codelengths[entry-1]);
       
   163       return(entry-1);
       
   164     }
       
   165   }else{
       
   166     lo=0;
       
   167     hi=book->used_entries;
       
   168   }
       
   169 
       
   170   lok = oggpack_look(b, read);
       
   171 
       
   172   while(lok<0 && read>1)
       
   173     lok = oggpack_look(b, --read);
       
   174 
       
   175   if(lok<0){
       
   176     oggpack_adv(b,1); /* force eop */
       
   177     return -1;
       
   178   }
       
   179 
       
   180   /* bisect search for the codeword in the ordered list */
       
   181   {
       
   182     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
       
   183 
       
   184     while(hi-lo>1){
       
   185       long p=(hi-lo)>>1;
       
   186       long test=book->codelist[lo+p]>testword;    
       
   187       lo+=p&(test-1);
       
   188       hi-=p&(-test);
       
   189     }
       
   190 
       
   191     if(book->dec_codelengths[lo]<=read){
       
   192       oggpack_adv(b, book->dec_codelengths[lo]);
       
   193       return(lo);
       
   194     }
       
   195   }
       
   196   
       
   197   oggpack_adv(b, read+1);
       
   198   return(-1);
       
   199 }
       
   200 
       
   201 /* Decode side is specced and easier, because we don't need to find
       
   202    matches using different criteria; we simply read and map.  There are
       
   203    two things we need to do 'depending':
       
   204    
       
   205    We may need to support interleave.  We don't really, but it's
       
   206    convenient to do it here rather than rebuild the vector later.
       
   207 
       
   208    Cascades may be additive or multiplicitive; this is not inherent in
       
   209    the codebook, but set in the code using the codebook.  Like
       
   210    interleaving, it's easiest to do it here.  
       
   211    addmul==0 -> declarative (set the value)
       
   212    addmul==1 -> additive
       
   213    addmul==2 -> multiplicitive */
       
   214 
       
   215 /* returns the [original, not compacted] entry number or -1 on eof *********/
       
   216 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
       
   217   if(book->used_entries>0){
       
   218     long packed_entry=decode_packed_entry_number(book,b);
       
   219     if(packed_entry>=0)
       
   220       return(book->dec_index[packed_entry]);
       
   221   }
       
   222 
       
   223   /* if there's no dec_index, the codebook unpacking isn't collapsed */
       
   224   return(-1);
       
   225 }
       
   226 
       
   227 /* returns 0 on OK or -1 on eof *************************************/
       
   228 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
       
   229 			      oggpack_buffer *b,int n,int point){
       
   230   if(book->used_entries>0){  
       
   231     int step=n/book->dim;
       
   232     long *entry = (long *)alloca(sizeof(*entry)*step);
       
   233     ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
       
   234     int i,j,o;
       
   235     int shift=point-book->binarypoint;
       
   236     
       
   237     if(shift>=0){
       
   238       for (i = 0; i < step; i++) {
       
   239 	entry[i]=decode_packed_entry_number(book,b);
       
   240 	if(entry[i]==-1)return(-1);
       
   241 	t[i] = book->valuelist+entry[i]*book->dim;
       
   242       }
       
   243       for(i=0,o=0;i<book->dim;i++,o+=step)
       
   244 	for (j=0;j<step;j++)
       
   245 	  a[o+j]+=t[j][i]>>shift;
       
   246     }else{
       
   247       for (i = 0; i < step; i++) {
       
   248 	entry[i]=decode_packed_entry_number(book,b);
       
   249 	if(entry[i]==-1)return(-1);
       
   250 	t[i] = book->valuelist+entry[i]*book->dim;
       
   251       }
       
   252       for(i=0,o=0;i<book->dim;i++,o+=step)
       
   253 	for (j=0;j<step;j++)
       
   254 	  a[o+j]+=t[j][i]<<-shift;
       
   255     }
       
   256   }
       
   257   return(0);
       
   258 }
       
   259 
       
   260 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
       
   261 			     oggpack_buffer *b,int n,int point){
       
   262   if(book->used_entries>0){
       
   263     int i,j,entry;
       
   264     ogg_int32_t *t;
       
   265     int shift=point-book->binarypoint;
       
   266     
       
   267     if(shift>=0){
       
   268       for(i=0;i<n;){
       
   269 	entry = decode_packed_entry_number(book,b);
       
   270 	if(entry==-1)return(-1);
       
   271 	t     = book->valuelist+entry*book->dim;
       
   272 	for (j=0;j<book->dim;)
       
   273 	  a[i++]+=t[j++]>>shift;
       
   274       }
       
   275     }else{
       
   276       for(i=0;i<n;){
       
   277 	entry = decode_packed_entry_number(book,b);
       
   278 	if(entry==-1)return(-1);
       
   279 	t     = book->valuelist+entry*book->dim;
       
   280 	for (j=0;j<book->dim;)
       
   281 	  a[i++]+=t[j++]<<-shift;
       
   282       }
       
   283     }
       
   284   }
       
   285   return(0);
       
   286 }
       
   287 
       
   288 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
       
   289 			     oggpack_buffer *b,int n,int point){
       
   290   if(book->used_entries>0){
       
   291     int i,j,entry;
       
   292     ogg_int32_t *t;
       
   293     int shift=point-book->binarypoint;
       
   294     
       
   295     if(shift>=0){
       
   296       
       
   297       for(i=0;i<n;){
       
   298 	entry = decode_packed_entry_number(book,b);
       
   299 	if(entry==-1)return(-1);
       
   300 	t     = book->valuelist+entry*book->dim;
       
   301 	for (j=0;j<book->dim;){
       
   302 	  a[i++]=t[j++]>>shift;
       
   303 	}
       
   304       }
       
   305     }else{
       
   306       
       
   307       for(i=0;i<n;){
       
   308 	entry = decode_packed_entry_number(book,b);
       
   309 	if(entry==-1)return(-1);
       
   310 	t     = book->valuelist+entry*book->dim;
       
   311 	for (j=0;j<book->dim;){
       
   312 	  a[i++]=t[j++]<<-shift;
       
   313 	}
       
   314       }
       
   315     }
       
   316   }else{
       
   317 
       
   318     int i,j;
       
   319     for(i=0;i<n;){
       
   320       for (j=0;j<book->dim;){
       
   321 	a[i++]=0;
       
   322       }
       
   323     }
       
   324   }
       
   325   return(0);
       
   326 }
       
   327 
       
   328 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
       
   329 			      long offset,int ch,
       
   330 			      oggpack_buffer *b,int n,int point){
       
   331   if(book->used_entries>0){
       
   332     long i,j,entry;
       
   333     int chptr=0;
       
   334     int shift=point-book->binarypoint;
       
   335     
       
   336     if(shift>=0){
       
   337       
       
   338       for(i=offset;i<offset+n;){
       
   339 	entry = decode_packed_entry_number(book,b);
       
   340 	if(entry==-1)return(-1);
       
   341 	{
       
   342 	  const ogg_int32_t *t = book->valuelist+entry*book->dim;
       
   343 	  for (j=0;j<book->dim;j++){
       
   344 	    a[chptr++][i]+=t[j]>>shift;
       
   345 	    if(chptr==ch){
       
   346 	      chptr=0;
       
   347 	      i++;
       
   348 	    }
       
   349 	  }
       
   350 	}
       
   351       }
       
   352     }else{
       
   353       
       
   354       for(i=offset;i<offset+n;){
       
   355 	entry = decode_packed_entry_number(book,b);
       
   356 	if(entry==-1)return(-1);
       
   357 	{
       
   358 	  const ogg_int32_t *t = book->valuelist+entry*book->dim;
       
   359 	  for (j=0;j<book->dim;j++){
       
   360 	    a[chptr++][i]+=t[j]<<-shift;
       
   361 	    if(chptr==ch){
       
   362 	      chptr=0;
       
   363 	      i++;
       
   364 	    }
       
   365 	  }
       
   366 	}
       
   367       }
       
   368     }
       
   369   }
       
   370   return(0);
       
   371 }