+
−/********************************************************************
+
− *                                                                  *
+
− * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
+
− *                                                                  *
+
− * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
+
− * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
+
− * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
+
− *                                                                  *
+
− * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
+
− * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
+
− *                                                                  *
+
− ********************************************************************
+
−
+
− function: basic codebook pack/unpack/code/decode operations
+
−
+
− ********************************************************************/
+
−
+
−#include <stdlib.h>
+
−#include <string.h>
+
−#include <math.h>
+
−#include "ogg.h"
+
−#include "ivorbiscodec.h"
+
−#include "codebook.h"
+
−#include "misc.h"
+
−
+
−/* unpacks a codebook from the packet buffer into the codebook struct,
+
−   readies the codebook auxiliary structures for decode *************/
+
−int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
+
−  long i,j;
+
−  memset(s,0,sizeof(*s));
+
−
+
−  /* make sure alignment is correct */
+
−  if(oggpack_read(opb,24)!=0x564342)goto _eofout;
+
−
+
−  /* first the basic parameters */
+
−  s->dim=oggpack_read(opb,16);
+
−  s->entries=oggpack_read(opb,24);
+
−  if(s->entries==-1)goto _eofout;
+
−
+
−  /* codeword ordering.... length ordered or unordered? */
+
−  switch((int)oggpack_read(opb,1)){
+
−  case 0:
+
−    /* unordered */
+
−    s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
+
−
+
−    /* allocated but unused entries? */
+
−    if(oggpack_read(opb,1)){
+
−      /* yes, unused entries */
+
−
+
−      for(i=0;i<s->entries;i++){
+
−	if(oggpack_read(opb,1)){
+
−	  long num=oggpack_read(opb,5);
+
−	  if(num==-1)goto _eofout;
+
−	  s->lengthlist[i]=num+1;
+
−	}else
+
−	  s->lengthlist[i]=0;
+
−      }
+
−    }else{
+
−      /* all entries used; no tagging */
+
−      for(i=0;i<s->entries;i++){
+
−	long num=oggpack_read(opb,5);
+
−	if(num==-1)goto _eofout;
+
−	s->lengthlist[i]=num+1;
+
−      }
+
−    }
+
−    
+
−    break;
+
−  case 1:
+
−    /* ordered */
+
−    {
+
−      long length=oggpack_read(opb,5)+1;
+
−      s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
+
−
+
−      for(i=0;i<s->entries;){
+
−	long num=oggpack_read(opb,_ilog(s->entries-i));
+
−	if(num==-1)goto _eofout;
+
−	for(j=0;j<num && i<s->entries;j++,i++)
+
−	  s->lengthlist[i]=length;
+
−	length++;
+
−      }
+
−    }
+
−    break;
+
−  default:
+
−    /* EOF */
+
−    return(-1);
+
−  }
+
−  
+
−  /* Do we have a mapping to unpack? */
+
−  switch((s->maptype=oggpack_read(opb,4))){
+
−  case 0:
+
−    /* no mapping */
+
−    break;
+
−  case 1: case 2:
+
−    /* implicitly populated value mapping */
+
−    /* explicitly populated value mapping */
+
−
+
−    s->q_min=oggpack_read(opb,32);
+
−    s->q_delta=oggpack_read(opb,32);
+
−    s->q_quant=oggpack_read(opb,4)+1;
+
−    s->q_sequencep=oggpack_read(opb,1);
+
−
+
−    {
+
−      int quantvals=0;
+
−      switch(s->maptype){
+
−      case 1:
+
−	quantvals=_book_maptype1_quantvals(s);
+
−	break;
+
−      case 2:
+
−	quantvals=s->entries*s->dim;
+
−	break;
+
−      }
+
−      
+
−      /* quantized values */
+
−      s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
+
−      for(i=0;i<quantvals;i++)
+
−	s->quantlist[i]=oggpack_read(opb,s->q_quant);
+
−      
+
−      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
+
−    }
+
−    break;
+
−  default:
+
−    goto _errout;
+
−  }
+
−
+
−  /* all set */
+
−  return(0);
+
−  
+
− _errout:
+
− _eofout:
+
−  vorbis_staticbook_clear(s);
+
−  return(-1); 
+
−}
+
−
+
−/* the 'eliminate the decode tree' optimization actually requires the
+
−   codewords to be MSb first, not LSb.  This is an annoying inelegancy
+
−   (and one of the first places where carefully thought out design
+
−   turned out to be wrong; Vorbis II and future Ogg codecs should go
+
−   to an MSb bitpacker), but not actually the huge hit it appears to
+
−   be.  The first-stage decode table catches most words so that
+
−   bitreverse is not in the main execution path. */
+
−
+
−static ogg_uint32_t bitreverse(ogg_uint32_t x){
+
−  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
+
−  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
+
−  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
+
−  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
+
−  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
+
−}
+
−
+
−STIN long decode_packed_entry_number(codebook *book, 
+
−					      oggpack_buffer *b){
+
−  int  read=book->dec_maxlength;
+
−  long lo,hi;
+
−  long lok = oggpack_look(b,book->dec_firsttablen);
+
− 
+
−  if (lok >= 0) {
+
−    long entry = book->dec_firsttable[lok];
+
−    if(entry&0x80000000UL){
+
−      lo=(entry>>15)&0x7fff;
+
−      hi=book->used_entries-(entry&0x7fff);
+
−    }else{
+
−      oggpack_adv(b, book->dec_codelengths[entry-1]);
+
−      return(entry-1);
+
−    }
+
−  }else{
+
−    lo=0;
+
−    hi=book->used_entries;
+
−  }
+
−
+
−  lok = oggpack_look(b, read);
+
−
+
−  while(lok<0 && read>1)
+
−    lok = oggpack_look(b, --read);
+
−
+
−  if(lok<0){
+
−    oggpack_adv(b,1); /* force eop */
+
−    return -1;
+
−  }
+
−
+
−  /* bisect search for the codeword in the ordered list */
+
−  {
+
−    ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
+
−
+
−    while(hi-lo>1){
+
−      long p=(hi-lo)>>1;
+
−      long test=book->codelist[lo+p]>testword;    
+
−      lo+=p&(test-1);
+
−      hi-=p&(-test);
+
−    }
+
−
+
−    if(book->dec_codelengths[lo]<=read){
+
−      oggpack_adv(b, book->dec_codelengths[lo]);
+
−      return(lo);
+
−    }
+
−  }
+
−  
+
−  oggpack_adv(b, read+1);
+
−  return(-1);
+
−}
+
−
+
−/* Decode side is specced and easier, because we don't need to find
+
−   matches using different criteria; we simply read and map.  There are
+
−   two things we need to do 'depending':
+
−   
+
−   We may need to support interleave.  We don't really, but it's
+
−   convenient to do it here rather than rebuild the vector later.
+
−
+
−   Cascades may be additive or multiplicitive; this is not inherent in
+
−   the codebook, but set in the code using the codebook.  Like
+
−   interleaving, it's easiest to do it here.  
+
−   addmul==0 -> declarative (set the value)
+
−   addmul==1 -> additive
+
−   addmul==2 -> multiplicitive */
+
−
+
−/* returns the [original, not compacted] entry number or -1 on eof *********/
+
−long vorbis_book_decode(codebook *book, oggpack_buffer *b){
+
−  if(book->used_entries>0){
+
−    long packed_entry=decode_packed_entry_number(book,b);
+
−    if(packed_entry>=0)
+
−      return(book->dec_index[packed_entry]);
+
−  }
+
−
+
−  /* if there's no dec_index, the codebook unpacking isn't collapsed */
+
−  return(-1);
+
−}
+
−
+
−/* returns 0 on OK or -1 on eof *************************************/
+
−long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
+
−			      oggpack_buffer *b,int n,int point){
+
−  if(book->used_entries>0){  
+
−    int step=n/book->dim;
+
−    long *entry = (long *)alloca(sizeof(*entry)*step);
+
−    ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
+
−    int i,j,o;
+
−    int shift=point-book->binarypoint;
+
−    
+
−    if(shift>=0){
+
−      for (i = 0; i < step; i++) {
+
−	entry[i]=decode_packed_entry_number(book,b);
+
−	if(entry[i]==-1)return(-1);
+
−	t[i] = book->valuelist+entry[i]*book->dim;
+
−      }
+
−      for(i=0,o=0;i<book->dim;i++,o+=step)
+
−	for (j=0;j<step;j++)
+
−	  a[o+j]+=t[j][i]>>shift;
+
−    }else{
+
−      for (i = 0; i < step; i++) {
+
−	entry[i]=decode_packed_entry_number(book,b);
+
−	if(entry[i]==-1)return(-1);
+
−	t[i] = book->valuelist+entry[i]*book->dim;
+
−      }
+
−      for(i=0,o=0;i<book->dim;i++,o+=step)
+
−	for (j=0;j<step;j++)
+
−	  a[o+j]+=t[j][i]<<-shift;
+
−    }
+
−  }
+
−  return(0);
+
−}
+
−
+
−long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
+
−			     oggpack_buffer *b,int n,int point){
+
−  if(book->used_entries>0){
+
−    int i,j,entry;
+
−    ogg_int32_t *t;
+
−    int shift=point-book->binarypoint;
+
−    
+
−    if(shift>=0){
+
−      for(i=0;i<n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	t     = book->valuelist+entry*book->dim;
+
−	for (j=0;j<book->dim;)
+
−	  a[i++]+=t[j++]>>shift;
+
−      }
+
−    }else{
+
−      for(i=0;i<n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	t     = book->valuelist+entry*book->dim;
+
−	for (j=0;j<book->dim;)
+
−	  a[i++]+=t[j++]<<-shift;
+
−      }
+
−    }
+
−  }
+
−  return(0);
+
−}
+
−
+
−long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
+
−			     oggpack_buffer *b,int n,int point){
+
−  if(book->used_entries>0){
+
−    int i,j,entry;
+
−    ogg_int32_t *t;
+
−    int shift=point-book->binarypoint;
+
−    
+
−    if(shift>=0){
+
−      
+
−      for(i=0;i<n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	t     = book->valuelist+entry*book->dim;
+
−	for (j=0;j<book->dim;){
+
−	  a[i++]=t[j++]>>shift;
+
−	}
+
−      }
+
−    }else{
+
−      
+
−      for(i=0;i<n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	t     = book->valuelist+entry*book->dim;
+
−	for (j=0;j<book->dim;){
+
−	  a[i++]=t[j++]<<-shift;
+
−	}
+
−      }
+
−    }
+
−  }else{
+
−
+
−    int i,j;
+
−    for(i=0;i<n;){
+
−      for (j=0;j<book->dim;){
+
−	a[i++]=0;
+
−      }
+
−    }
+
−  }
+
−  return(0);
+
−}
+
−
+
−long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
+
−			      long offset,int ch,
+
−			      oggpack_buffer *b,int n,int point){
+
−  if(book->used_entries>0){
+
−    long i,j,entry;
+
−    int chptr=0;
+
−    int shift=point-book->binarypoint;
+
−    
+
−    if(shift>=0){
+
−      
+
−      for(i=offset;i<offset+n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	{
+
−	  const ogg_int32_t *t = book->valuelist+entry*book->dim;
+
−	  for (j=0;j<book->dim;j++){
+
−	    a[chptr++][i]+=t[j]>>shift;
+
−	    if(chptr==ch){
+
−	      chptr=0;
+
−	      i++;
+
−	    }
+
−	  }
+
−	}
+
−      }
+
−    }else{
+
−      
+
−      for(i=offset;i<offset+n;){
+
−	entry = decode_packed_entry_number(book,b);
+
−	if(entry==-1)return(-1);
+
−	{
+
−	  const ogg_int32_t *t = book->valuelist+entry*book->dim;
+
−	  for (j=0;j<book->dim;j++){
+
−	    a[chptr++][i]+=t[j]<<-shift;
+
−	    if(chptr==ch){
+
−	      chptr=0;
+
−	      i++;
+
−	    }
+
−	  }
+
−	}
+
−      }
+
−    }
+
−  }
+
−  return(0);
+
−}