cannam@86: /********************************************************************
cannam@86:  *                                                                  *
cannam@86:  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
cannam@86:  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
cannam@86:  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
cannam@86:  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
cannam@86:  *                                                                  *
cannam@86:  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009             *
cannam@86:  * by the Xiph.Org Foundation http://www.xiph.org/                  *
cannam@86:  *                                                                  *
cannam@86:  ********************************************************************
cannam@86: 
cannam@86:  function: basic codebook pack/unpack/code/decode operations
cannam@86:  last mod: $Id: codebook.c 18183 2012-02-03 20:51:27Z xiphmont $
cannam@86: 
cannam@86:  ********************************************************************/
cannam@86: 
cannam@86: #include <stdlib.h>
cannam@86: #include <string.h>
cannam@86: #include <math.h>
cannam@86: #include <ogg/ogg.h>
cannam@86: #include "vorbis/codec.h"
cannam@86: #include "codebook.h"
cannam@86: #include "scales.h"
cannam@86: #include "misc.h"
cannam@86: #include "os.h"
cannam@86: 
cannam@86: /* packs the given codebook into the bitstream **************************/
cannam@86: 
cannam@86: int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
cannam@86:   long i,j;
cannam@86:   int ordered=0;
cannam@86: 
cannam@86:   /* first the basic parameters */
cannam@86:   oggpack_write(opb,0x564342,24);
cannam@86:   oggpack_write(opb,c->dim,16);
cannam@86:   oggpack_write(opb,c->entries,24);
cannam@86: 
cannam@86:   /* pack the codewords.  There are two packings; length ordered and
cannam@86:      length random.  Decide between the two now. */
cannam@86: 
cannam@86:   for(i=1;i<c->entries;i++)
cannam@86:     if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
cannam@86:   if(i==c->entries)ordered=1;
cannam@86: 
cannam@86:   if(ordered){
cannam@86:     /* length ordered.  We only need to say how many codewords of
cannam@86:        each length.  The actual codewords are generated
cannam@86:        deterministically */
cannam@86: 
cannam@86:     long count=0;
cannam@86:     oggpack_write(opb,1,1);  /* ordered */
cannam@86:     oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
cannam@86: 
cannam@86:     for(i=1;i<c->entries;i++){
cannam@86:       long this=c->lengthlist[i];
cannam@86:       long last=c->lengthlist[i-1];
cannam@86:       if(this>last){
cannam@86:         for(j=last;j<this;j++){
cannam@86:           oggpack_write(opb,i-count,_ilog(c->entries-count));
cannam@86:           count=i;
cannam@86:         }
cannam@86:       }
cannam@86:     }
cannam@86:     oggpack_write(opb,i-count,_ilog(c->entries-count));
cannam@86: 
cannam@86:   }else{
cannam@86:     /* length random.  Again, we don't code the codeword itself, just
cannam@86:        the length.  This time, though, we have to encode each length */
cannam@86:     oggpack_write(opb,0,1);   /* unordered */
cannam@86: 
cannam@86:     /* algortihmic mapping has use for 'unused entries', which we tag
cannam@86:        here.  The algorithmic mapping happens as usual, but the unused
cannam@86:        entry has no codeword. */
cannam@86:     for(i=0;i<c->entries;i++)
cannam@86:       if(c->lengthlist[i]==0)break;
cannam@86: 
cannam@86:     if(i==c->entries){
cannam@86:       oggpack_write(opb,0,1); /* no unused entries */
cannam@86:       for(i=0;i<c->entries;i++)
cannam@86:         oggpack_write(opb,c->lengthlist[i]-1,5);
cannam@86:     }else{
cannam@86:       oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
cannam@86:       for(i=0;i<c->entries;i++){
cannam@86:         if(c->lengthlist[i]==0){
cannam@86:           oggpack_write(opb,0,1);
cannam@86:         }else{
cannam@86:           oggpack_write(opb,1,1);
cannam@86:           oggpack_write(opb,c->lengthlist[i]-1,5);
cannam@86:         }
cannam@86:       }
cannam@86:     }
cannam@86:   }
cannam@86: 
cannam@86:   /* is the entry number the desired return value, or do we have a
cannam@86:      mapping? If we have a mapping, what type? */
cannam@86:   oggpack_write(opb,c->maptype,4);
cannam@86:   switch(c->maptype){
cannam@86:   case 0:
cannam@86:     /* no mapping */
cannam@86:     break;
cannam@86:   case 1:case 2:
cannam@86:     /* implicitly populated value mapping */
cannam@86:     /* explicitly populated value mapping */
cannam@86: 
cannam@86:     if(!c->quantlist){
cannam@86:       /* no quantlist?  error */
cannam@86:       return(-1);
cannam@86:     }
cannam@86: 
cannam@86:     /* values that define the dequantization */
cannam@86:     oggpack_write(opb,c->q_min,32);
cannam@86:     oggpack_write(opb,c->q_delta,32);
cannam@86:     oggpack_write(opb,c->q_quant-1,4);
cannam@86:     oggpack_write(opb,c->q_sequencep,1);
cannam@86: 
cannam@86:     {
cannam@86:       int quantvals;
cannam@86:       switch(c->maptype){
cannam@86:       case 1:
cannam@86:         /* a single column of (c->entries/c->dim) quantized values for
cannam@86:            building a full value list algorithmically (square lattice) */
cannam@86:         quantvals=_book_maptype1_quantvals(c);
cannam@86:         break;
cannam@86:       case 2:
cannam@86:         /* every value (c->entries*c->dim total) specified explicitly */
cannam@86:         quantvals=c->entries*c->dim;
cannam@86:         break;
cannam@86:       default: /* NOT_REACHABLE */
cannam@86:         quantvals=-1;
cannam@86:       }
cannam@86: 
cannam@86:       /* quantized values */
cannam@86:       for(i=0;i<quantvals;i++)
cannam@86:         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
cannam@86: 
cannam@86:     }
cannam@86:     break;
cannam@86:   default:
cannam@86:     /* error case; we don't have any other map types now */
cannam@86:     return(-1);
cannam@86:   }
cannam@86: 
cannam@86:   return(0);
cannam@86: }
cannam@86: 
cannam@86: /* unpacks a codebook from the packet buffer into the codebook struct,
cannam@86:    readies the codebook auxiliary structures for decode *************/
cannam@86: static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
cannam@86:   long i,j;
cannam@86:   static_codebook *s=_ogg_calloc(1,sizeof(*s));
cannam@86:   s->allocedp=1;
cannam@86: 
cannam@86:   /* make sure alignment is correct */
cannam@86:   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
cannam@86: 
cannam@86:   /* first the basic parameters */
cannam@86:   s->dim=oggpack_read(opb,16);
cannam@86:   s->entries=oggpack_read(opb,24);
cannam@86:   if(s->entries==-1)goto _eofout;
cannam@86: 
cannam@86:   if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
cannam@86: 
cannam@86:   /* codeword ordering.... length ordered or unordered? */
cannam@86:   switch((int)oggpack_read(opb,1)){
cannam@86:   case 0:{
cannam@86:     long unused;
cannam@86:     /* allocated but unused entries? */
cannam@86:     unused=oggpack_read(opb,1);
cannam@86:     if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
cannam@86:       goto _eofout;
cannam@86:     /* unordered */
cannam@86:     s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
cannam@86: 
cannam@86:     /* allocated but unused entries? */
cannam@86:     if(unused){
cannam@86:       /* yes, unused entries */
cannam@86: 
cannam@86:       for(i=0;i<s->entries;i++){
cannam@86:         if(oggpack_read(opb,1)){
cannam@86:           long num=oggpack_read(opb,5);
cannam@86:           if(num==-1)goto _eofout;
cannam@86:           s->lengthlist[i]=num+1;
cannam@86:         }else
cannam@86:           s->lengthlist[i]=0;
cannam@86:       }
cannam@86:     }else{
cannam@86:       /* all entries used; no tagging */
cannam@86:       for(i=0;i<s->entries;i++){
cannam@86:         long num=oggpack_read(opb,5);
cannam@86:         if(num==-1)goto _eofout;
cannam@86:         s->lengthlist[i]=num+1;
cannam@86:       }
cannam@86:     }
cannam@86: 
cannam@86:     break;
cannam@86:   }
cannam@86:   case 1:
cannam@86:     /* ordered */
cannam@86:     {
cannam@86:       long length=oggpack_read(opb,5)+1;
cannam@86:       if(length==0)goto _eofout;
cannam@86:       s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
cannam@86: 
cannam@86:       for(i=0;i<s->entries;){
cannam@86:         long num=oggpack_read(opb,_ilog(s->entries-i));
cannam@86:         if(num==-1)goto _eofout;
cannam@86:         if(length>32 || num>s->entries-i ||
cannam@86:            (num>0 && (num-1)>>(length-1)>1)){
cannam@86:           goto _errout;
cannam@86:         }
cannam@86:         if(length>32)goto _errout;
cannam@86:         for(j=0;j<num;j++,i++)
cannam@86:           s->lengthlist[i]=length;
cannam@86:         length++;
cannam@86:       }
cannam@86:     }
cannam@86:     break;
cannam@86:   default:
cannam@86:     /* EOF */
cannam@86:     goto _eofout;
cannam@86:   }
cannam@86: 
cannam@86:   /* Do we have a mapping to unpack? */
cannam@86:   switch((s->maptype=oggpack_read(opb,4))){
cannam@86:   case 0:
cannam@86:     /* no mapping */
cannam@86:     break;
cannam@86:   case 1: case 2:
cannam@86:     /* implicitly populated value mapping */
cannam@86:     /* explicitly populated value mapping */
cannam@86: 
cannam@86:     s->q_min=oggpack_read(opb,32);
cannam@86:     s->q_delta=oggpack_read(opb,32);
cannam@86:     s->q_quant=oggpack_read(opb,4)+1;
cannam@86:     s->q_sequencep=oggpack_read(opb,1);
cannam@86:     if(s->q_sequencep==-1)goto _eofout;
cannam@86: 
cannam@86:     {
cannam@86:       int quantvals=0;
cannam@86:       switch(s->maptype){
cannam@86:       case 1:
cannam@86:         quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
cannam@86:         break;
cannam@86:       case 2:
cannam@86:         quantvals=s->entries*s->dim;
cannam@86:         break;
cannam@86:       }
cannam@86: 
cannam@86:       /* quantized values */
cannam@86:       if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
cannam@86:         goto _eofout;
cannam@86:       s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
cannam@86:       for(i=0;i<quantvals;i++)
cannam@86:         s->quantlist[i]=oggpack_read(opb,s->q_quant);
cannam@86: 
cannam@86:       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
cannam@86:     }
cannam@86:     break;
cannam@86:   default:
cannam@86:     goto _errout;
cannam@86:   }
cannam@86: 
cannam@86:   /* all set */
cannam@86:   return(s);
cannam@86: 
cannam@86:  _errout:
cannam@86:  _eofout:
cannam@86:   vorbis_staticbook_destroy(s);
cannam@86:   return(NULL);
cannam@86: }
cannam@86: 
cannam@86: /* returns the number of bits ************************************************/
cannam@86: int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
cannam@86:   if(a<0 || a>=book->c->entries)return(0);
cannam@86:   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
cannam@86:   return(book->c->lengthlist[a]);
cannam@86: }
cannam@86: 
cannam@86: /* the 'eliminate the decode tree' optimization actually requires the
cannam@86:    codewords to be MSb first, not LSb.  This is an annoying inelegancy
cannam@86:    (and one of the first places where carefully thought out design
cannam@86:    turned out to be wrong; Vorbis II and future Ogg codecs should go
cannam@86:    to an MSb bitpacker), but not actually the huge hit it appears to
cannam@86:    be.  The first-stage decode table catches most words so that
cannam@86:    bitreverse is not in the main execution path. */
cannam@86: 
cannam@86: static ogg_uint32_t bitreverse(ogg_uint32_t x){
cannam@86:   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
cannam@86:   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
cannam@86:   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
cannam@86:   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
cannam@86:   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
cannam@86: }
cannam@86: 
cannam@86: STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
cannam@86:   int  read=book->dec_maxlength;
cannam@86:   long lo,hi;
cannam@86:   long lok = oggpack_look(b,book->dec_firsttablen);
cannam@86: 
cannam@86:   if (lok >= 0) {
cannam@86:     long entry = book->dec_firsttable[lok];
cannam@86:     if(entry&0x80000000UL){
cannam@86:       lo=(entry>>15)&0x7fff;
cannam@86:       hi=book->used_entries-(entry&0x7fff);
cannam@86:     }else{
cannam@86:       oggpack_adv(b, book->dec_codelengths[entry-1]);
cannam@86:       return(entry-1);
cannam@86:     }
cannam@86:   }else{
cannam@86:     lo=0;
cannam@86:     hi=book->used_entries;
cannam@86:   }
cannam@86: 
cannam@86:   lok = oggpack_look(b, read);
cannam@86: 
cannam@86:   while(lok<0 && read>1)
cannam@86:     lok = oggpack_look(b, --read);
cannam@86:   if(lok<0)return -1;
cannam@86: 
cannam@86:   /* bisect search for the codeword in the ordered list */
cannam@86:   {
cannam@86:     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
cannam@86: 
cannam@86:     while(hi-lo>1){
cannam@86:       long p=(hi-lo)>>1;
cannam@86:       long test=book->codelist[lo+p]>testword;
cannam@86:       lo+=p&(test-1);
cannam@86:       hi-=p&(-test);
cannam@86:       }
cannam@86: 
cannam@86:     if(book->dec_codelengths[lo]<=read){
cannam@86:       oggpack_adv(b, book->dec_codelengths[lo]);
cannam@86:       return(lo);
cannam@86:     }
cannam@86:   }
cannam@86: 
cannam@86:   oggpack_adv(b, read);
cannam@86: 
cannam@86:   return(-1);
cannam@86: }
cannam@86: 
cannam@86: /* Decode side is specced and easier, because we don't need to find
cannam@86:    matches using different criteria; we simply read and map.  There are
cannam@86:    two things we need to do 'depending':
cannam@86: 
cannam@86:    We may need to support interleave.  We don't really, but it's
cannam@86:    convenient to do it here rather than rebuild the vector later.
cannam@86: 
cannam@86:    Cascades may be additive or multiplicitive; this is not inherent in
cannam@86:    the codebook, but set in the code using the codebook.  Like
cannam@86:    interleaving, it's easiest to do it here.
cannam@86:    addmul==0 -> declarative (set the value)
cannam@86:    addmul==1 -> additive
cannam@86:    addmul==2 -> multiplicitive */
cannam@86: 
cannam@86: /* returns the [original, not compacted] entry number or -1 on eof *********/
cannam@86: long vorbis_book_decode(codebook *book, oggpack_buffer *b){
cannam@86:   if(book->used_entries>0){
cannam@86:     long packed_entry=decode_packed_entry_number(book,b);
cannam@86:     if(packed_entry>=0)
cannam@86:       return(book->dec_index[packed_entry]);
cannam@86:   }
cannam@86: 
cannam@86:   /* if there's no dec_index, the codebook unpacking isn't collapsed */
cannam@86:   return(-1);
cannam@86: }
cannam@86: 
cannam@86: /* returns 0 on OK or -1 on eof *************************************/
cannam@86: /* decode vector / dim granularity gaurding is done in the upper layer */
cannam@86: long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
cannam@86:   if(book->used_entries>0){
cannam@86:     int step=n/book->dim;
cannam@86:     long *entry = alloca(sizeof(*entry)*step);
cannam@86:     float **t = alloca(sizeof(*t)*step);
cannam@86:     int i,j,o;
cannam@86: 
cannam@86:     for (i = 0; i < step; i++) {
cannam@86:       entry[i]=decode_packed_entry_number(book,b);
cannam@86:       if(entry[i]==-1)return(-1);
cannam@86:       t[i] = book->valuelist+entry[i]*book->dim;
cannam@86:     }
cannam@86:     for(i=0,o=0;i<book->dim;i++,o+=step)
cannam@86:       for (j=0;j<step;j++)
cannam@86:         a[o+j]+=t[j][i];
cannam@86:   }
cannam@86:   return(0);
cannam@86: }
cannam@86: 
cannam@86: /* decode vector / dim granularity gaurding is done in the upper layer */
cannam@86: long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
cannam@86:   if(book->used_entries>0){
cannam@86:     int i,j,entry;
cannam@86:     float *t;
cannam@86: 
cannam@86:     if(book->dim>8){
cannam@86:       for(i=0;i<n;){
cannam@86:         entry = decode_packed_entry_number(book,b);
cannam@86:         if(entry==-1)return(-1);
cannam@86:         t     = book->valuelist+entry*book->dim;
cannam@86:         for (j=0;j<book->dim;)
cannam@86:           a[i++]+=t[j++];
cannam@86:       }
cannam@86:     }else{
cannam@86:       for(i=0;i<n;){
cannam@86:         entry = decode_packed_entry_number(book,b);
cannam@86:         if(entry==-1)return(-1);
cannam@86:         t     = book->valuelist+entry*book->dim;
cannam@86:         j=0;
cannam@86:         switch((int)book->dim){
cannam@86:         case 8:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 7:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 6:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 5:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 4:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 3:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 2:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 1:
cannam@86:           a[i++]+=t[j++];
cannam@86:         case 0:
cannam@86:           break;
cannam@86:         }
cannam@86:       }
cannam@86:     }
cannam@86:   }
cannam@86:   return(0);
cannam@86: }
cannam@86: 
cannam@86: /* unlike the others, we guard against n not being an integer number
cannam@86:    of <dim> internally rather than in the upper layer (called only by
cannam@86:    floor0) */
cannam@86: long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
cannam@86:   if(book->used_entries>0){
cannam@86:     int i,j,entry;
cannam@86:     float *t;
cannam@86: 
cannam@86:     for(i=0;i<n;){
cannam@86:       entry = decode_packed_entry_number(book,b);
cannam@86:       if(entry==-1)return(-1);
cannam@86:       t     = book->valuelist+entry*book->dim;
cannam@86:       for (j=0;i<n && j<book->dim;){
cannam@86:         a[i++]=t[j++];
cannam@86:       }
cannam@86:     }
cannam@86:   }else{
cannam@86:     int i,j;
cannam@86: 
cannam@86:     for(i=0;i<n;){
cannam@86:       a[i++]=0.f;
cannam@86:     }
cannam@86:   }
cannam@86:   return(0);
cannam@86: }
cannam@86: 
cannam@86: long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
cannam@86:                               oggpack_buffer *b,int n){
cannam@86: 
cannam@86:   long i,j,entry;
cannam@86:   int chptr=0;
cannam@86:   if(book->used_entries>0){
cannam@86:     for(i=offset/ch;i<(offset+n)/ch;){
cannam@86:       entry = decode_packed_entry_number(book,b);
cannam@86:       if(entry==-1)return(-1);
cannam@86:       {
cannam@86:         const float *t = book->valuelist+entry*book->dim;
cannam@86:         for (j=0;j<book->dim;j++){
cannam@86:           a[chptr++][i]+=t[j];
cannam@86:           if(chptr==ch){
cannam@86:             chptr=0;
cannam@86:             i++;
cannam@86:           }
cannam@86:         }
cannam@86:       }
cannam@86:     }
cannam@86:   }
cannam@86:   return(0);
cannam@86: }