25 

    25 #include "os.h"

    26 /* unpacks a codebook from the packet buffer into the codebook struct,

    26 

    27    readies the codebook auxiliary structures for decode *************/

    27 

    28 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){

    28 /**** pack/unpack helpers ******************************************/

    29   long i,j;

    29 int _ilog(unsigned int v){

    30   int ret=0;

    31   while(v){

    32     ret++;

    33     v>>=1;

    34   }

    35   return(ret);

    36 }

    37 

    38 static ogg_uint32_t decpack(long entry,long used_entry,long quantvals,

    39 			    codebook *b,oggpack_buffer *opb,int maptype){

    40   ogg_uint32_t ret=0;

    41   int j;

    42   

    43   switch(b->dec_type){

    44 

    45   case 0:

    46     return (ogg_uint32_t)entry;

    47 

    48   case 1:

    49     if(maptype==1){

    50       /* vals are already read into temporary colum vector here */

    51       for(j=0;j<b->dim;j++){

    52 	ogg_uint32_t off=entry%quantvals;

    53 	entry/=quantvals;

    54 	ret|=((ogg_uint16_t *)(b->q_val))[off]<<(b->q_bits*j);

    55       }

    56     }else{

    57       for(j=0;j<b->dim;j++)

    58 	ret|=oggpack_read(opb,b->q_bits)<<(b->q_bits*j);

    59     }

    60     return ret;

    61     

    62   case 2:

    63     for(j=0;j<b->dim;j++){

    64       ogg_uint32_t off=entry%quantvals;

    65       entry/=quantvals;

    66       ret|=off<<(b->q_pack*j);

    67     }

    68     return ret;

    69 

    70   case 3:

    71     return (ogg_uint32_t)used_entry;

    72 

    73   }

    74 }

    75 

    76 /* 32 bit float (not IEEE; nonnormalized mantissa +

    77    biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm 

    78    Why not IEEE?  It's just not that important here. */

    79 

    80 static ogg_int32_t _float32_unpack(long val,int *point){

    81   long   mant=val&0x1fffff;

    82   int    sign=val&0x80000000;

    83   

    84   *point=((val&0x7fe00000L)>>21)-788;

    85 

    86   if(mant){

    87     while(!(mant&0x40000000)){

    88       mant<<=1;

    89       *point-=1;

    90     }

    91     if(sign)mant= -mant;

    92   }else{

    93     *point=-9999;

    94   }

    95   return mant;

    96 }

    97 

    98 /* choose the smallest supported node size that fits our decode table.

    99    Legal bytewidths are 1/1 1/2 2/2 2/4 4/4 */

   100 static int _determine_node_bytes(long used, int leafwidth){

   101 

   102   /* special case small books to size 4 to avoid multiple special

   103      cases in repack */

   104   if(used<2)

   105     return 4;

   106 

   107   if(leafwidth==3)leafwidth=4;

   108   if(_ilog(3*used-6)+1 <= leafwidth*4) 

   109     return leafwidth/2?leafwidth/2:1;

   110   return leafwidth;

   111 }

   112 

   113 /* convenience/clarity; leaves are specified as multiple of node word

   114    size (1 or 2) */

   115 static int _determine_leaf_words(int nodeb, int leafwidth){

   116   if(leafwidth>nodeb)return 2;

   117   return 1;

   118 }

   119 

   120 /* given a list of word lengths, number of used entries, and byte

   121    width of a leaf, generate the decode table */

   122 static int _make_words(char *l,long n,ogg_uint32_t *r,long quantvals,

   123 		       codebook *b, oggpack_buffer *opb,int maptype){

   124   long i,j,count=0;

   125   long top=0;

   126   ogg_uint32_t marker[33];

   127 

   128   if(n<2){

   129     r[0]=0x80000000;

   130   }else{

   131     memset(marker,0,sizeof(marker));

   132     

   133     for(i=0;i<n;i++){

   134       long length=l[i];

   135       if(length){

   136 	ogg_uint32_t entry=marker[length];

   137 	long chase=0;

   138 	if(count && !entry)return -1; /* overpopulated tree! */

   139 	

   140 	/* chase the tree as far as it's already populated, fill in past */

   141 	for(j=0;j<length-1;j++){

   142 	  int bit=(entry>>(length-j-1))&1;

   143 	  if(chase>=top){ 

   144 	    top++;

   145 	    r[chase*2]=top;

   146 	    r[chase*2+1]=0;

   147 	  }else

   148 	    if(!r[chase*2+bit])

   149 	      r[chase*2+bit]=top;

   150 	  chase=r[chase*2+bit];

   151 	}

   152 	{	

   153 	  int bit=(entry>>(length-j-1))&1;

   154 	  if(chase>=top){ 

   155 	    top++;

   156 	    r[chase*2+1]=0;

   157 	  }

   158 	  r[chase*2+bit]= decpack(i,count++,quantvals,b,opb,maptype) | 

   159 	    0x80000000;

   160 	}

   161 

   162 	/* Look to see if the next shorter marker points to the node

   163 	   above. if so, update it and repeat.  */

   164 	for(j=length;j>0;j--){          

   165 	  if(marker[j]&1){

   166 	    marker[j]=marker[j-1]<<1;

   167 	    break;

   168 	  }

   169 	  marker[j]++;

   170 	}

   171 	

   172 	/* prune the tree; the implicit invariant says all the longer

   173 	   markers were dangling from our just-taken node.  Dangle them

   174 	   from our *new* node. */

   175 	for(j=length+1;j<33;j++)

   176 	  if((marker[j]>>1) == entry){

   177 	    entry=marker[j];

   178 	    marker[j]=marker[j-1]<<1;

   179 	  }else

   180 	    break;

   181       }

   182     }

   183   }

   184   

   185   return 0;

   186 }

   187 

   188 static int _make_decode_table(codebook *s,char *lengthlist,long quantvals,

   189 			      oggpack_buffer *opb,int maptype){

   190   int i;

   191   ogg_uint32_t *work;

   192 

   193   if(s->dec_nodeb==4){

   194     s->dec_table=_ogg_malloc((s->used_entries*2+1)*sizeof(*work));

   195     /* +1 (rather than -2) is to accommodate 0 and 1 sized books,

   196        which are specialcased to nodeb==4 */

   197     if(_make_words(lengthlist,s->entries,

   198 		   s->dec_table,quantvals,s,opb,maptype))return 1;

   199     

   200     return 0;

   201   }

   202 

   203   work=alloca((s->used_entries*2-2)*sizeof(*work));

   204   if(_make_words(lengthlist,s->entries,work,quantvals,s,opb,maptype))return 1;

   205   s->dec_table=_ogg_malloc((s->used_entries*(s->dec_leafw+1)-2)*

   206 			   s->dec_nodeb);

   207     

   208   if(s->dec_leafw==1){

   209     switch(s->dec_nodeb){

   210     case 1:

   211       for(i=0;i<s->used_entries*2-2;i++)

   212 	  ((unsigned char *)s->dec_table)[i]=

   213 	    ((work[i] & 0x80000000UL) >> 24) | work[i];

   214       break;

   215     case 2:

   216       for(i=0;i<s->used_entries*2-2;i++)

   217 	  ((ogg_uint16_t *)s->dec_table)[i]=

   218 	    ((work[i] & 0x80000000UL) >> 16) | work[i];

   219       break; 

   220     }

   221 

   222   }else{

   223     /* more complex; we have to do a two-pass repack that updates the

   224        node indexing. */

   225     long top=s->used_entries*3-2;

   226     if(s->dec_nodeb==1){

   227       unsigned char *out=(unsigned char *)s->dec_table;

   228 

   229       for(i=s->used_entries*2-4;i>=0;i-=2){

   230 	if(work[i]&0x80000000UL){

   231 	  if(work[i+1]&0x80000000UL){

   232 	    top-=4;

   233 	    out[top]=(work[i]>>8 & 0x7f)|0x80;

   234 	    out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;

   235 	    out[top+2]=work[i] & 0xff;

   236 	    out[top+3]=work[i+1] & 0xff;

   237 	  }else{

   238 	    top-=3;

   239 	    out[top]=(work[i]>>8 & 0x7f)|0x80;

   240 	    out[top+1]=work[work[i+1]*2];

   241 	    out[top+2]=work[i] & 0xff;

   242 	  }

   243 	}else{

   244 	  if(work[i+1]&0x80000000UL){

   245 	    top-=3;

   246 	    out[top]=work[work[i]*2];

   247 	    out[top+1]=(work[i+1]>>8 & 0x7f)|0x80;

   248 	    out[top+2]=work[i+1] & 0xff;

   249 	  }else{

   250 	    top-=2;

   251 	    out[top]=work[work[i]*2];

   252 	    out[top+1]=work[work[i+1]*2];

   253 	  }

   254 	}

   255 	work[i]=top;

   256       }

   257     }else{

   258       ogg_uint16_t *out=(ogg_uint16_t *)s->dec_table;

   259       for(i=s->used_entries*2-4;i>=0;i-=2){

   260 	if(work[i]&0x80000000UL){

   261 	  if(work[i+1]&0x80000000UL){

   262 	    top-=4;

   263 	    out[top]=(work[i]>>16 & 0x7fff)|0x8000;

   264 	    out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;

   265 	    out[top+2]=work[i] & 0xffff;

   266 	    out[top+3]=work[i+1] & 0xffff;

   267 	  }else{

   268 	    top-=3;

   269 	    out[top]=(work[i]>>16 & 0x7fff)|0x8000;

   270 	    out[top+1]=work[work[i+1]*2];

   271 	    out[top+2]=work[i] & 0xffff;

   272 	  }

   273 	}else{

   274 	  if(work[i+1]&0x80000000UL){

   275 	    top-=3;

   276 	    out[top]=work[work[i]*2];

   277 	    out[top+1]=(work[i+1]>>16 & 0x7fff)|0x8000;

   278 	    out[top+2]=work[i+1] & 0xffff;

   279 	  }else{

   280 	    top-=2;

   281 	    out[top]=work[work[i]*2];

   282 	    out[top+1]=work[work[i+1]*2];

   283 	  }

   284 	}

   285 	work[i]=top;

   286       }

   287     }

   288   }

   289 	

   290   return 0;

   291 }

   292 

   293 /* most of the time, entries%dimensions == 0, but we need to be

   294    well defined.  We define that the possible vales at each

   295    scalar is values == entries/dim.  If entries%dim != 0, we'll

   296    have 'too few' values (values*dim<entries), which means that

   297    we'll have 'left over' entries; left over entries use zeroed

   298    values (and are wasted).  So don't generate codebooks like

   299    that */

   300 /* there might be a straightforward one-line way to do the below

   301    that's portable and totally safe against roundoff, but I haven't

   302    thought of it.  Therefore, we opt on the side of caution */

   303 long _book_maptype1_quantvals(codebook *b){

   304   /* get us a starting hint, we'll polish it below */

   305   int bits=_ilog(b->entries);

   306   int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);

   307 

   308   while(1){

   309     long acc=1;

   310     long acc1=1;

   311     int i;

   312     for(i=0;i<b->dim;i++){

   313       acc*=vals;

   314       acc1*=vals+1;

   315     }

   316     if(acc<=b->entries && acc1>b->entries){

   317       return(vals);

   318     }else{

   319       if(acc>b->entries){

   320         vals--;

   321       }else{

   322         vals++;

   323       }

   324     }

   325   }

   326 }

   327 

   328 void vorbis_book_clear(codebook *b){

   329   /* static book is not cleared; we're likely called on the lookup and

   330      the static codebook belongs to the info struct */

   331   if(b->q_val)_ogg_free(b->q_val);

   332   if(b->dec_table)_ogg_free(b->dec_table);

   333 

   334   memset(b,0,sizeof(*b));

   335 }

   336 

   337 int vorbis_book_unpack(oggpack_buffer *opb,codebook *s){

   338   char         *lengthlist=NULL;

   339   int           quantvals=0;

   340   long          i,j,k;

   341   int           maptype;

   342 

    44     s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);

   357     lengthlist=(char *)alloca(sizeof(*lengthlist)*s->entries);

    54 	  s->lengthlist[i]=num+1;

   367 	  lengthlist[i]=num+1;

   368 	  s->used_entries++;

   369 	  if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;

    56 	  s->lengthlist[i]=0;

   371 	  lengthlist[i]=0;

    63 	s->lengthlist[i]=num+1;

   379 	lengthlist[i]=num+1;

   380 	if(num+1>s->dec_maxlength)s->dec_maxlength=num+1;

    72       s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);

   389 

    73 

   390       s->used_entries=s->entries;

   391       lengthlist=(char *)alloca(sizeof(*lengthlist)*s->entries);

   392       

    78 	  s->lengthlist[i]=length;

   397 	  lengthlist[i]=length;

   398 	s->dec_maxlength=length;

    88   /* Do we have a mapping to unpack? */

   411   if((maptype=oggpack_read(opb,4))>0){

    89   switch((s->maptype=oggpack_read(opb,4))){

   412     s->q_min=_float32_unpack(oggpack_read(opb,32),&s->q_minp);

   413     s->q_del=_float32_unpack(oggpack_read(opb,32),&s->q_delp);

   414     s->q_bits=oggpack_read(opb,4)+1;

   415     s->q_seq=oggpack_read(opb,1);

   416 

   417     s->q_del>>=s->q_bits;

   418     s->q_delp+=s->q_bits;

   419   }

   420 

   421   switch(maptype){

    91     /* no mapping */

   423 

   424     /* no mapping; decode type 0 */

   425 

   426     /* how many bytes for the indexing? */

   427     /* this is the correct boundary here; we lose one bit to

   428        node/leaf mark */

   429     s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->entries)/8+1); 

   430     s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->entries)/8+1); 

   431     s->dec_type=0;

   432 

   433     if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)) goto _errout;

    93   case 1: case 2:

   435 

    94     /* implicitly populated value mapping */

   436   case 1:

    95     /* explicitly populated value mapping */

   437 

    96 

   438     /* mapping type 1; implicit values by lattice  position */

    97     s->q_min=oggpack_read(opb,32);

   439     quantvals=_book_maptype1_quantvals(s);

    98     s->q_delta=oggpack_read(opb,32);

   440     

    99     s->q_quant=oggpack_read(opb,4)+1;

   441     /* dec_type choices here are 1,2; 3 doesn't make sense */

   100     s->q_sequencep=oggpack_read(opb,1);

   101 

   103       int quantvals=0;

   443       /* packed values */

   104       switch(s->maptype){

   444       long total1=(s->q_bits*s->dim+8)/8; /* remember flag bit */

   105       case 1:

   445       /* vector of column offsets; remember flag bit */

   106 	quantvals=_book_maptype1_quantvals(s);

   446       long total2=(_ilog(quantvals-1)*s->dim+8)/8+(s->q_bits+7)/8;

   107 	break;

   447 

   108       case 2:

   109 	quantvals=s->entries*s->dim;

   110 	break;

   111       }

   113       /* quantized values */

   449       if(total1<=4 && total1<=total2){

   114       s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);

   450 	/* use dec_type 1: vector of packed values */

   115       for(i=0;i<quantvals;i++)

   451 

   116 	s->quantlist[i]=oggpack_read(opb,s->q_quant);

   452 	/* need quantized values before  */

   453 	s->q_val=alloca(sizeof(ogg_uint16_t)*quantvals);

   454 	for(i=0;i<quantvals;i++)

   455 	  ((ogg_uint16_t *)s->q_val)[i]=oggpack_read(opb,s->q_bits);

   456 	

   457 	if(oggpack_eop(opb)){

   458 	  s->q_val=0; /* cleanup must not free alloca memory */

   459 	  goto _eofout;

   460 	}

   461 

   462 	s->dec_type=1;

   463 	s->dec_nodeb=_determine_node_bytes(s->used_entries,

   464 					   (s->q_bits*s->dim+8)/8); 

   465 	s->dec_leafw=_determine_leaf_words(s->dec_nodeb,

   466 					   (s->q_bits*s->dim+8)/8); 

   467 	if(_make_decode_table(s,lengthlist,quantvals,opb,maptype)){

   468 	  s->q_val=0; /* cleanup must not free alloca memory */

   469 	  goto _errout;

   470 	}

   471 	

   472 	s->q_val=0; /* about to go out of scope; _make_decode_table

   473                        was using it */

   474 	

   475       }else{

   476 	/* use dec_type 2: packed vector of column offsets */

   477 

   478 	/* need quantized values before */

   479 	if(s->q_bits<=8){

   480 	  s->q_val=_ogg_malloc(quantvals);

   481 	  for(i=0;i<quantvals;i++)

   482 	    ((unsigned char *)s->q_val)[i]=oggpack_read(opb,s->q_bits);

   483 	}else{

   484 	  s->q_val=_ogg_malloc(quantvals*2);

   485 	  for(i=0;i<quantvals;i++)

   486 	    ((ogg_uint16_t *)s->q_val)[i]=oggpack_read(opb,s->q_bits);

   487 	}

   488 

   489 	if(oggpack_eop(opb))goto _eofout;

   490 

   491 	s->q_pack=_ilog(quantvals-1); 

   492 	s->dec_type=2;

   493 	s->dec_nodeb=_determine_node_bytes(s->used_entries,

   494 					   (_ilog(quantvals-1)*s->dim+8)/8); 

   495 	s->dec_leafw=_determine_leaf_words(s->dec_nodeb,

   496 					   (_ilog(quantvals-1)*s->dim+8)/8); 

   497 	if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;

   498 

   499       }

   500     }

   501     break;

   502   case 2:

   503 

   504     /* mapping type 2; explicit array of values */

   505     quantvals=s->entries*s->dim;

   506     /* dec_type choices here are 1,3; 2 is not possible */

   507 

   508     if( (s->q_bits*s->dim+8)/8 <=4){ /* remember flag bit */

   509       /* use dec_type 1: vector of packed values */

   510 

   511       s->dec_type=1;

   512       s->dec_nodeb=_determine_node_bytes(s->used_entries,(s->q_bits*s->dim+8)/8); 

   513       s->dec_leafw=_determine_leaf_words(s->dec_nodeb,(s->q_bits*s->dim+8)/8); 

   514       if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;

   118       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;

   516     }else{

   517       /* use dec_type 3: scalar offset into packed value array */

   518 

   519       s->dec_type=3;

   520       s->dec_nodeb=_determine_node_bytes(s->used_entries,_ilog(s->used_entries-1)/8+1); 

   521       s->dec_leafw=_determine_leaf_words(s->dec_nodeb,_ilog(s->used_entries-1)/8+1); 

   522       if(_make_decode_table(s,lengthlist,quantvals,opb,maptype))goto _errout;

   523 

   524       /* get the vals & pack them */

   525       s->q_pack=(s->q_bits+7)/8*s->dim;

   526       s->q_val=_ogg_malloc(s->q_pack*s->used_entries);

   527 

   528       if(s->q_bits<=8){

   529 	for(i=0;i<s->used_entries*s->dim;i++)

   530 	  ((unsigned char *)(s->q_val))[i]=oggpack_read(opb,s->q_bits);

   531       }else{

   532 	for(i=0;i<s->used_entries*s->dim;i++)

   533 	  ((ogg_uint16_t *)(s->q_val))[i]=oggpack_read(opb,s->q_bits);

   534       }

   125   /* all set */

   541   if(oggpack_eop(opb))goto _eofout;

   126   return(0);

   542 

   127   

   543   return 0;

   130   vorbis_staticbook_clear(s);

   546   vorbis_book_clear(s);

   131   return(-1); 

   547   return -1;

   132 }

   548 }

   133 

   549 

   134 /* the 'eliminate the decode tree' optimization actually requires the

   550 static inline ogg_uint32_t decode_packed_entry_number(codebook *book, 

   135    codewords to be MSb first, not LSb.  This is an annoying inelegancy

   551 						      oggpack_buffer *b){

   136    (and one of the first places where carefully thought out design

   552   ogg_uint32_t chase=0;

   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){

   153   long lo,hi;

   554   long lok = oggpack_look(b,read),i;

   154   long lok = oggpack_look(b,book->dec_firsttablen);

   555   

   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 

   180   /* bisect search for the codeword in the ordered list */

   564   /* chase the tree with the bits we got */

   181   {

   565   if(book->dec_nodeb==1){

   182     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);

   566     if(book->dec_leafw==1){

   183 

   567 

   184     while(hi-lo>1){

   568       /* 8/8 */

   185       long p=(hi-lo)>>1;

   569       unsigned char *t=(unsigned char *)book->dec_table;

   186       long test=book->codelist[lo+p]>testword;    

   570       for(i=0;i<read;i++){

   187       lo+=p&(test-1);

   571 	chase=t[chase*2+((lok>>i)&1)];

   188       hi-=p&(-test);

   572 	if(chase&0x80UL)break;

   189     }

   573       }

   190 

   574       chase&=0x7fUL;

   191     if(book->dec_codelengths[lo]<=read){

   575 

   192       oggpack_adv(b, book->dec_codelengths[lo]);

   576     }else{

   193       return(lo);

   577 

   578       /* 8/16 */

   579       unsigned char *t=(unsigned char *)book->dec_table;

   580       for(i=0;i<read;i++){

   581 	int bit=(lok>>i)&1;

   582 	int next=t[chase+bit];

   583 	if(next&0x80){

   584 	  chase= (next<<8) | t[chase+bit+1+(!bit || t[chase]&0x80)];

   585 	  break;

   586 	}

   587 	chase=next;

   588       }

   589       chase&=0x7fffUL;

   590     }

   591 

   592   }else{

   593     if(book->dec_nodeb==2){

   594       if(book->dec_leafw==1){

   595 	

   596 	/* 16/16 */

   597 	for(i=0;i<read;i++){

   598 	  chase=((ogg_uint16_t *)(book->dec_table))[chase*2+((lok>>i)&1)];

   599 	  if(chase&0x8000UL)break;

   600 	}

   601 	chase&=0x7fffUL;

   602 	

   603       }else{

   604 	

   605 	/* 16/32 */

   606 	ogg_uint16_t *t=(ogg_uint16_t *)book->dec_table;

   607 	for(i=0;i<read;i++){

   608 	  int bit=(lok>>i)&1;

   609 	  int next=t[chase+bit];

   610 	  if(next&0x8000){

   611 	    chase= (next<<16) | t[chase+bit+1+(!bit || t[chase]&0x8000)];

   612 	    break;

   613 	  }

   614 	  chase=next;

   615 	}

   616 	chase&=0x7fffffffUL;

   617       }

   618       

   619     }else{

   620       

   621       for(i=0;i<read;i++){

   622 	chase=((ogg_uint32_t *)(book->dec_table))[chase*2+((lok>>i)&1)];

   623 	if(chase&0x80000000UL)break;

   624       }

   625       chase&=0x7fffffffUL;

   626       

   197   oggpack_adv(b, read+1);

   630   if(i<read){

   631     oggpack_adv(b,i+1);

   632     return chase;

   633   }

   634   oggpack_adv(b,read+1);

   217   if(book->used_entries>0){

   640   if(book->dec_type)return -1;

   218     long packed_entry=decode_packed_entry_number(book,b);

   641   return decode_packed_entry_number(book,b);

   219     if(packed_entry>=0)

   642 }

   220       return(book->dec_index[packed_entry]);

   643 

   221   }

   644 int decode_map(codebook *s, oggpack_buffer *b, ogg_int32_t *v, int point){

   222 

   645   ogg_uint32_t entry = decode_packed_entry_number(s,b);

   223   /* if there's no dec_index, the codebook unpacking isn't collapsed */

   646   int i;

   224   return(-1);

   647   if(oggpack_eop(b))return(-1);

   648 

   649   /* according to decode type */

   650   switch(s->dec_type){

   651   case 1:{

   652     /* packed vector of values */

   653     int mask=(1<<s->q_bits)-1;

   654     for(i=0;i<s->dim;i++){

   655       v[i]=entry&mask;

   656       entry>>=s->q_bits;

   657     }

   658     break;

   659   }

   660   case 2:{

   661     /* packed vector of column offsets */

   662     int mask=(1<<s->q_pack)-1;

   663     for(i=0;i<s->dim;i++){

   664       if(s->q_bits<=8)

   665 	v[i]=((unsigned char *)(s->q_val))[entry&mask];

   666       else

   667 	v[i]=((ogg_uint16_t *)(s->q_val))[entry&mask];

   668       entry>>=s->q_pack;

   669     }

   670     break;

   671   }

   672   case 3:{

   673     /* offset into array */

   674     void *ptr=s->q_val+entry*s->q_pack;

   675 

   676     if(s->q_bits<=8){

   677       for(i=0;i<s->dim;i++)

   678 	v[i]=((unsigned char *)ptr)[i];

   679     }else{

   680       for(i=0;i<s->dim;i++)

   681 	v[i]=((ogg_uint16_t *)ptr)[i];

   682     }

   683     break;

   684   }

   685   default:

   686     return -1;

   687   }

   688 

   689   /* we have the unpacked multiplicands; compute final vals */

   690   {

   691     int shiftM=point-s->q_delp;

   692     ogg_int32_t add=point-s->q_minp;

   693     if(add>0)

   694       add= s->q_min >> add;

   695     else

   696       add= s->q_min << -add;

   697 

   698     if(shiftM>0)

   699       for(i=0;i<s->dim;i++)

   700 	v[i]= add + ((v[i] * s->q_del) >> shiftM);

   701     else

   702       for(i=0;i<s->dim;i++)

   703 	v[i]= add + ((v[i] * s->q_del) << -shiftM);

   704 

   705     if(s->q_seq)

   706       for(i=1;i<s->dim;i++)

   707 	v[i]+=v[i-1];

   708   }

   709 

   710   return 0;

   230   if(book->used_entries>0){  

   716   if(book->used_entries>0){

   232     long *entry = (long *)alloca(sizeof(*entry)*step);

   718     ogg_int32_t *v = (ogg_int32_t *)alloca(sizeof(*v)*book->dim);

   233     ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);

   235     int shift=point-book->binarypoint;

   720     

   236     

   721     for (j=0;j<step;j++){

   237     if(shift>=0){

   722       if(decode_map(book,b,v,point))return -1;

   238       for (i = 0; i < step; i++) {

   723       for(i=0,o=j;i<book->dim;i++,o+=step)

   239 	entry[i]=decode_packed_entry_number(book,b);

   724 	a[o]+=v[i];

   240 	if(entry[i]==-1)return(-1);

   725     }

   241 	t[i] = book->valuelist+entry[i]*book->dim;

   726   }

   242       }

   727   return 0;

   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);

   263     int i,j,entry;

   733     ogg_int32_t *v = (ogg_int32_t *)alloca(sizeof(*v)*book->dim);

   264     ogg_int32_t *t;

   734     int i,j;

   265     int shift=point-book->binarypoint;

   735     

   266     

   736     for(i=0;i<n;){

   267     if(shift>=0){

   737       if(decode_map(book,b,v,point))return -1;

   268       for(i=0;i<n;){

   738       for (j=0;j<book->dim;j++)

   269 	entry = decode_packed_entry_number(book,b);

   739 	a[i++]+=v[j];

   270 	if(entry==-1)return(-1);

   740     }

   271 	t     = book->valuelist+entry*book->dim;

   741   }

   272 	for (j=0;j<book->dim;)

   742   return 0;

   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);

   291     int i,j,entry;

   748     ogg_int32_t *v = (ogg_int32_t *)alloca(sizeof(*v)*book->dim);

   292     ogg_int32_t *t;

   749     int i,j;

   293     int shift=point-book->binarypoint;

   750     

   294     

   751     for(i=0;i<n;){

   295     if(shift>=0){

   752       if(decode_map(book,b,v,point))return -1;

   296       

   753       for (j=0;j<book->dim;j++)

   297       for(i=0;i<n;){

   754 	a[i++]=v[j];

   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       }

   320       for (j=0;j<book->dim;){

   760       for (j=0;j<book->dim;j++)

   322       }

   762     }

   323     }

   763   }

   324   }

   764 

   325   return(0);

   765   return 0;

   326 }

   766 }

   327 

   767 

   328 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\

   768 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,

   332     long i,j,entry;

   773     ogg_int32_t *v = (ogg_int32_t *)alloca(sizeof(*v)*book->dim);

   774     long i,j;

   334     int shift=point-book->binarypoint;

   776     

   335     

   777     for(i=offset;i<offset+n;){

   336     if(shift>=0){

   778       if(decode_map(book,b,v,point))return -1;

   337       

   779       for (j=0;j<book->dim;j++){

   338       for(i=offset;i<offset+n;){

   780 	a[chptr++][i]+=v[j];

   339 	entry = decode_packed_entry_number(book,b);

   781 	if(chptr==ch){

   340 	if(entry==-1)return(-1);

   782 	  chptr=0;

   341 	{

   783 	  i++;

   342 	  const ogg_int32_t *t = book->valuelist+entry*book->dim;

   784 	}

   343 	  for (j=0;j<book->dim;j++){

   785       }

   344 	    a[chptr++][i]+=t[j]>>shift;

   786     }

   345 	    if(chptr==ch){

   787   }

   346 	      chptr=0;

   788   return 0;

   347 	      i++;

   789 }

   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 }