| /******************************************************************** |
| * * |
| * THIS FILE IS PART OF THE OggVorbis SOFTWARE 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 SOURCE CODE IS (C) COPYRIGHT 1994-2009 * |
| * by the Xiph.Org Foundation http://www.xiph.org/ * |
| * * |
| ******************************************************************** |
| |
| function: basic codebook pack/unpack/code/decode operations |
| last mod: $Id: codebook.c 17030 2010-03-25 06:52:55Z xiphmont $ |
| |
| ********************************************************************/ |
| |
| #include <stdlib.h> |
| #include <string.h> |
| #include <math.h> |
| #include <ogg/ogg.h> |
| #include "vorbis/codec.h" |
| #include "codebook.h" |
| #include "scales.h" |
| #include "misc.h" |
| #include "os.h" |
| |
| /* packs the given codebook into the bitstream **************************/ |
| |
| int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ |
| long i,j; |
| int ordered=0; |
| |
| /* first the basic parameters */ |
| oggpack_write(opb,0x564342,24); |
| oggpack_write(opb,c->dim,16); |
| oggpack_write(opb,c->entries,24); |
| |
| /* pack the codewords. There are two packings; length ordered and |
| length random. Decide between the two now. */ |
| |
| for(i=1;i<c->entries;i++) |
| if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break; |
| if(i==c->entries)ordered=1; |
| |
| if(ordered){ |
| /* length ordered. We only need to say how many codewords of |
| each length. The actual codewords are generated |
| deterministically */ |
| |
| long count=0; |
| oggpack_write(opb,1,1); /* ordered */ |
| oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */ |
| |
| for(i=1;i<c->entries;i++){ |
| long this=c->lengthlist[i]; |
| long last=c->lengthlist[i-1]; |
| if(this>last){ |
| for(j=last;j<this;j++){ |
| oggpack_write(opb,i-count,_ilog(c->entries-count)); |
| count=i; |
| } |
| } |
| } |
| oggpack_write(opb,i-count,_ilog(c->entries-count)); |
| |
| }else{ |
| /* length random. Again, we don't code the codeword itself, just |
| the length. This time, though, we have to encode each length */ |
| oggpack_write(opb,0,1); /* unordered */ |
| |
| /* algortihmic mapping has use for 'unused entries', which we tag |
| here. The algorithmic mapping happens as usual, but the unused |
| entry has no codeword. */ |
| for(i=0;i<c->entries;i++) |
| if(c->lengthlist[i]==0)break; |
| |
| if(i==c->entries){ |
| oggpack_write(opb,0,1); /* no unused entries */ |
| for(i=0;i<c->entries;i++) |
| oggpack_write(opb,c->lengthlist[i]-1,5); |
| }else{ |
| oggpack_write(opb,1,1); /* we have unused entries; thus we tag */ |
| for(i=0;i<c->entries;i++){ |
| if(c->lengthlist[i]==0){ |
| oggpack_write(opb,0,1); |
| }else{ |
| oggpack_write(opb,1,1); |
| oggpack_write(opb,c->lengthlist[i]-1,5); |
| } |
| } |
| } |
| } |
| |
| /* is the entry number the desired return value, or do we have a |
| mapping? If we have a mapping, what type? */ |
| oggpack_write(opb,c->maptype,4); |
| switch(c->maptype){ |
| case 0: |
| /* no mapping */ |
| break; |
| case 1:case 2: |
| /* implicitly populated value mapping */ |
| /* explicitly populated value mapping */ |
| |
| if(!c->quantlist){ |
| /* no quantlist? error */ |
| return(-1); |
| } |
| |
| /* values that define the dequantization */ |
| oggpack_write(opb,c->q_min,32); |
| oggpack_write(opb,c->q_delta,32); |
| oggpack_write(opb,c->q_quant-1,4); |
| oggpack_write(opb,c->q_sequencep,1); |
| |
| { |
| int quantvals; |
| switch(c->maptype){ |
| case 1: |
| /* a single column of (c->entries/c->dim) quantized values for |
| building a full value list algorithmically (square lattice) */ |
| quantvals=_book_maptype1_quantvals(c); |
| break; |
| case 2: |
| /* every value (c->entries*c->dim total) specified explicitly */ |
| quantvals=c->entries*c->dim; |
| break; |
| default: /* NOT_REACHABLE */ |
| quantvals=-1; |
| } |
| |
| /* quantized values */ |
| for(i=0;i<quantvals;i++) |
| oggpack_write(opb,labs(c->quantlist[i]),c->q_quant); |
| |
| } |
| break; |
| default: |
| /* error case; we don't have any other map types now */ |
| return(-1); |
| } |
| |
| return(0); |
| } |
| |
| /* unpacks a codebook from the packet buffer into the codebook struct, |
| readies the codebook auxiliary structures for decode *************/ |
| static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){ |
| long i,j; |
| static_codebook *s=_ogg_calloc(1,sizeof(*s)); |
| s->allocedp=1; |
| |
| /* 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; |
| |
| if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout; |
| |
| /* codeword ordering.... length ordered or unordered? */ |
| switch((int)oggpack_read(opb,1)){ |
| case 0: |
| /* unordered */ |
| s->lengthlist=_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=_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; |
| if(length>32)goto _errout; |
| for(j=0;j<num && i<s->entries;j++,i++) |
| s->lengthlist[i]=length; |
| length++; |
| } |
| } |
| break; |
| default: |
| /* EOF */ |
| goto _eofout; |
| } |
| |
| /* 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); |
| if(s->q_sequencep==-1)goto _eofout; |
| |
| { |
| int quantvals=0; |
| switch(s->maptype){ |
| case 1: |
| quantvals=(s->dim==0?0:_book_maptype1_quantvals(s)); |
| break; |
| case 2: |
| quantvals=s->entries*s->dim; |
| break; |
| } |
| |
| /* quantized values */ |
| s->quantlist=_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(s); |
| |
| _errout: |
| _eofout: |
| vorbis_staticbook_destroy(s); |
| return(NULL); |
| } |
| |
| /* returns the number of bits ************************************************/ |
| int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){ |
| if(a<0 || a>=book->c->entries)return(0); |
| oggpack_write(b,book->codelist[a],book->c->lengthlist[a]); |
| return(book->c->lengthlist[a]); |
| } |
| |
| /* 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)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); |
| |
| 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,float *a,oggpack_buffer *b,int n){ |
| if(book->used_entries>0){ |
| int step=n/book->dim; |
| long *entry = alloca(sizeof(*entry)*step); |
| float **t = alloca(sizeof(*t)*step); |
| int i,j,o; |
| |
| 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]; |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){ |
| if(book->used_entries>0){ |
| int i,j,entry; |
| float *t; |
| |
| if(book->dim>8){ |
| 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++]; |
| } |
| }else{ |
| for(i=0;i<n;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| t = book->valuelist+entry*book->dim; |
| j=0; |
| switch((int)book->dim){ |
| case 8: |
| a[i++]+=t[j++]; |
| case 7: |
| a[i++]+=t[j++]; |
| case 6: |
| a[i++]+=t[j++]; |
| case 5: |
| a[i++]+=t[j++]; |
| case 4: |
| a[i++]+=t[j++]; |
| case 3: |
| a[i++]+=t[j++]; |
| case 2: |
| a[i++]+=t[j++]; |
| case 1: |
| a[i++]+=t[j++]; |
| case 0: |
| break; |
| } |
| } |
| } |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){ |
| if(book->used_entries>0){ |
| int i,j,entry; |
| float *t; |
| |
| 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++]; |
| } |
| }else{ |
| int i,j; |
| |
| for(i=0;i<n;){ |
| for (j=0;j<book->dim;) |
| a[i++]=0.f; |
| } |
| } |
| return(0); |
| } |
| |
| long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch, |
| oggpack_buffer *b,int n){ |
| |
| long i,j,entry; |
| int chptr=0; |
| if(book->used_entries>0){ |
| for(i=offset/ch;i<(offset+n)/ch;){ |
| entry = decode_packed_entry_number(book,b); |
| if(entry==-1)return(-1); |
| { |
| const float *t = book->valuelist+entry*book->dim; |
| for (j=0;j<book->dim;j++){ |
| a[chptr++][i]+=t[j]; |
| if(chptr==ch){ |
| chptr=0; |
| i++; |
| } |
| } |
| } |
| } |
| } |
| return(0); |
| } |
