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 }