X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=lib%2Fcodebook.c;h=78672e222d858012a7bcb08b0553697944a15b31;hb=018ca26dece618457dd13585cad52941193c4a25;hp=13bb8a44fb3e7bea0202c55533764653e775de26;hpb=67f833635368a912b53f68ec55840e4f7cdd69c5;p=platform%2Fupstream%2Flibvorbis.git diff --git a/lib/codebook.c b/lib/codebook.c index 13bb8a4..78672e2 100644 --- a/lib/codebook.c +++ b/lib/codebook.c @@ -1,31 +1,28 @@ /******************************************************************** * * - * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. * - * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY * - * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. * - * PLEASE READ THESE TERMS DISTRIBUTING. * + * 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 OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 * - * by Monty and The XIPHOPHORUS Company * - * http://www.xiph.org/ * + * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2015 * + * by the Xiph.Org Foundation http://www.xiph.org/ * * * ******************************************************************** function: basic codebook pack/unpack/code/decode operations - last mod: $Id: codebook.c,v 1.15 2000/06/14 01:38:31 xiphmont Exp $ ********************************************************************/ #include #include #include +#include #include "vorbis/codec.h" -#include "vorbis/codebook.h" -#include "bitwise.h" +#include "codebook.h" #include "scales.h" -#include "sharedbook.h" -#include "bookinternal.h" #include "misc.h" +#include "os.h" /* packs the given codebook into the bitstream **************************/ @@ -34,43 +31,43 @@ int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ int ordered=0; /* first the basic parameters */ - _oggpack_write(opb,0x564342,24); - _oggpack_write(opb,c->dim,16); - _oggpack_write(opb,c->entries,24); + 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;ientries;i++) - if(c->lengthlist[i]lengthlist[i-1])break; + if(c->lengthlist[i-1]==0 || c->lengthlist[i]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 */ + oggpack_write(opb,1,1); /* ordered */ + oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */ for(i=1;ientries;i++){ - long this=c->lengthlist[i]; - long last=c->lengthlist[i-1]; + char this=c->lengthlist[i]; + char last=c->lengthlist[i-1]; if(this>last){ - for(j=last;jentries-count)); - count=i; - } + for(j=last;jentries-count)); + count=i; + } } } - _oggpack_write(opb,i-count,_ilog(c->entries-count)); - + oggpack_write(opb,i-count,ov_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 */ - + 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. */ @@ -78,25 +75,25 @@ int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ if(c->lengthlist[i]==0)break; if(i==c->entries){ - _oggpack_write(opb,0,1); /* no unused entries */ + oggpack_write(opb,0,1); /* no unused entries */ for(i=0;ientries;i++) - _oggpack_write(opb,c->lengthlist[i]-1,5); + oggpack_write(opb,c->lengthlist[i]-1,5); }else{ - _oggpack_write(opb,1,1); /* we have unused entries; thus we tag */ + oggpack_write(opb,1,1); /* we have unused entries; thus we tag */ for(i=0;ientries;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); - } + 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); + oggpack_write(opb,c->maptype,4); switch(c->maptype){ case 0: /* no mapping */ @@ -104,35 +101,37 @@ int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ 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); - + 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; + /* 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; + /* 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;iquantlist[i]),c->q_quant); + oggpack_write(opb,labs(c->quantlist[i]),c->q_quant); } break; @@ -146,68 +145,83 @@ int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ /* 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){ +static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){ long i,j; - memset(s,0,sizeof(static_codebook)); + static_codebook *s=_ogg_calloc(1,sizeof(*s)); + s->allocedp=1; /* make sure alignment is correct */ - if(_oggpack_read(opb,24)!=0x564342)goto _eofout; + if(oggpack_read(opb,24)!=0x564342)goto _eofout; /* first the basic parameters */ - s->dim=_oggpack_read(opb,16); - s->entries=_oggpack_read(opb,24); + s->dim=oggpack_read(opb,16); + s->entries=oggpack_read(opb,24); if(s->entries==-1)goto _eofout; + if(ov_ilog(s->dim)+ov_ilog(s->entries)>24)goto _eofout; + /* codeword ordering.... length ordered or unordered? */ - switch(_oggpack_read(opb,1)){ - case 0: + switch((int)oggpack_read(opb,1)){ + case 0:{ + long unused; + /* allocated but unused entries? */ + unused=oggpack_read(opb,1); + if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb)) + goto _eofout; /* unordered */ - s->lengthlist=malloc(sizeof(long)*s->entries); + s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); /* allocated but unused entries? */ - if(_oggpack_read(opb,1)){ + if(unused){ /* yes, unused entries */ for(i=0;ientries;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; + 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;ientries;i++){ - long num=_oggpack_read(opb,5); - if(num==-1)goto _eofout; - s->lengthlist[i]=num+1; + 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=malloc(sizeof(long)*s->entries); + long length=oggpack_read(opb,5)+1; + if(length==0)goto _eofout; + s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); for(i=0;ientries;){ - long num=_oggpack_read(opb,_ilog(s->entries-i)); - if(num==-1)goto _eofout; - for(j=0;jlengthlist[i]=length; - length++; + long num=oggpack_read(opb,ov_ilog(s->entries-i)); + if(num==-1)goto _eofout; + if(length>32 || num>s->entries-i || + (num>0 && (num-1)>>(length-1)>1)){ + goto _errout; + } + if(length>32)goto _errout; + for(j=0;jlengthlist[i]=length; + length++; } } break; default: /* EOF */ - return(-1); + goto _eofout; } - + /* Do we have a mapping to unpack? */ - switch((s->maptype=_oggpack_read(opb,4))){ + switch((s->maptype=oggpack_read(opb,4))){ case 0: /* no mapping */ break; @@ -215,28 +229,31 @@ int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){ /* 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); + 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; + int quantvals=0; switch(s->maptype){ case 1: - quantvals=_book_maptype1_quantvals(s); - break; + quantvals=(s->dim==0?0:_book_maptype1_quantvals(s)); + break; case 2: - quantvals=s->entries*s->dim; - break; + quantvals=s->entries*s->dim; + break; } - + /* quantized values */ - s->quantlist=malloc(sizeof(double)*quantvals); + if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb)) + goto _eofout; + s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals); for(i=0;iquantlist[i]=_oggpack_read(opb,s->q_quant); - - if(s->quantlist[quantvals-1]==-1)goto _eofout; + s->quantlist[i]=oggpack_read(opb,s->q_quant); + + if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; } break; default: @@ -244,305 +261,201 @@ int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){ } /* all set */ - return(0); - + return(s); + _errout: _eofout: - vorbis_staticbook_clear(s); - return(-1); + vorbis_staticbook_destroy(s); + return(NULL); } /* returns the number of bits ************************************************/ int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){ - _oggpack_write(b,book->codelist[a],book->c->lengthlist[a]); + if(a<0 || a>=book->c->entries)return(0); + oggpack_write(b,book->codelist[a],book->c->lengthlist[a]); return(book->c->lengthlist[a]); } -/* One the encode side, our vector writers are each designed for a -specific purpose, and the encoder is not flexible without modification: - -The LSP vector coder uses a single stage nearest-match with no -interleave, so no step and no error return. This is specced by floor0 -and doesn't change. - -Residue0 encoding interleaves, uses multiple stages, and each stage -peels of a specific amount of resolution from a lattice (thus we want -to match by threshhold, not nearest match). Residue doesn't *have* to -be encoded that way, but to change it, one will need to add more -infrastructure on the encode side (decode side is specced and simpler) */ - -/* floor0 LSP (single stage, non interleaved, nearest match) */ -/* returns entry number and *modifies a* to the quantization value *****/ -int vorbis_book_errorv(codebook *book,double *a){ - int dim=book->dim,k; - int best=_best(book,a,1); - for(k=0;kvaluelist+best*dim)[k]; - return(best); +/* 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); } -/* returns the number of bits and *modifies a* to the quantization value *****/ -int vorbis_book_encodev(codebook *book,int best,double *a,oggpack_buffer *b){ - int k,dim=book->dim; - for(k=0;kvaluelist+best*dim)[k]; - return(vorbis_book_encode(book,best,b)); -} +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; + } -/* res0 (multistage, interleave, lattice) */ -/* returns the number of bits and *modifies a* to the remainder value ********/ -int vorbis_book_encodevs(codebook *book,double *a,oggpack_buffer *b, - int step,int addmul){ + /* Single entry codebooks use a firsttablen of 1 and a + dec_maxlength of 1. If a single-entry codebook gets here (due to + failure to read one bit above), the next look attempt will also + fail and we'll correctly kick out instead of trying to walk the + underformed tree */ + + 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); + } + } - int best=vorbis_book_besterror(book,a,step,addmul); - return(vorbis_book_encode(book,best,b)); + 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. - stage==0 -> declarative (set the value) - stage==1 -> additive - stage==2 -> multiplicitive */ + interleaving, it's easiest to do it here. + addmul==0 -> declarative (set the value) + addmul==1 -> additive + addmul==2 -> multiplicitive */ -/* returns the entry number or -1 on eof *************************************/ +/* returns the [original, not compacted] entry number or -1 on eof *********/ long vorbis_book_decode(codebook *book, oggpack_buffer *b){ - long ptr=0; - decode_aux *t=book->decode_tree; - do{ - switch(_oggpack_read1(b)){ - case 0: - ptr=t->ptr0[ptr]; - break; - case 1: - ptr=t->ptr1[ptr]; - break; - case -1: - return(-1); - } - }while(ptr>0); - return(-ptr); + 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 the entry number or -1 on eof *************************************/ -long vorbis_book_decodevs(codebook *book,double *a,oggpack_buffer *b, - int step,int addmul){ - long entry=vorbis_book_decode(book,b); - int i,o; - if(entry==-1)return(-1); - switch(addmul){ - case -1: - for(i=0,o=0;idim;i++,o+=step) - a[o]=(book->valuelist+entry*book->dim)[i]; - break; - case 0: - for(i=0,o=0;idim;i++,o+=step) - a[o]+=(book->valuelist+entry*book->dim)[i]; - break; - case 1: +/* returns 0 on OK or -1 on eof *************************************/ +/* decode vector / dim granularity gaurding is done in the upper layer */ +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;idim;i++,o+=step) - a[o]*=(book->valuelist+entry*book->dim)[i]; - break; + for (j=0;o+j -#include "vorbis/book/lsp20_0.vqh" -#include "vorbis/book/lsp32_0.vqh" -#include "vorbis/book/res0_1a.vqh" -#define TESTSIZE 40 - -double test1[TESTSIZE]={ - 0.105939, - 0.215373, - 0.429117, - 0.587974, - - 0.181173, - 0.296583, - 0.515707, - 0.715261, - - 0.162327, - 0.263834, - 0.342876, - 0.406025, - - 0.103571, - 0.223561, - 0.368513, - 0.540313, - - 0.136672, - 0.395882, - 0.587183, - 0.652476, - - 0.114338, - 0.417300, - 0.525486, - 0.698679, - - 0.147492, - 0.324481, - 0.643089, - 0.757582, - - 0.139556, - 0.215795, - 0.324559, - 0.399387, - - 0.120236, - 0.267420, - 0.446940, - 0.608760, - - 0.115587, - 0.287234, - 0.571081, - 0.708603, -}; - -double test2[TESTSIZE]={ - 0.088654, - 0.165742, - 0.279013, - 0.395894, - - 0.110812, - 0.218422, - 0.283423, - 0.371719, - - 0.136985, - 0.186066, - 0.309814, - 0.381521, - - 0.123925, - 0.211707, - 0.314771, - 0.433026, - - 0.088619, - 0.192276, - 0.277568, - 0.343509, - - 0.068400, - 0.132901, - 0.223999, - 0.302538, - - 0.202159, - 0.306131, - 0.360362, - 0.416066, - - 0.072591, - 0.178019, - 0.304315, - 0.376516, - - 0.094336, - 0.188401, - 0.325119, - 0.390264, - - 0.091636, - 0.223099, - 0.282899, - 0.375124, -}; - -double test3[TESTSIZE]={ - 0,1,-2,3,4,-5,6,7,8,9, - 8,-2,7,-1,4,6,8,3,1,-9, - 10,11,12,13,14,15,26,17,18,19, - 30,-25,-30,-1,-5,-32,4,3,-2,0}; - -static_codebook *testlist[]={&_vq_book_lsp20_0, - &_vq_book_lsp32_0, - &_vq_book_res0_1a,NULL}; -double *testvec[]={test1,test2,test3}; - -int main(){ - oggpack_buffer write; - oggpack_buffer read; - long ptr=0,i; - _oggpack_writeinit(&write); - - fprintf(stderr,"Testing codebook abstraction...:\n"); - - while(testlist[ptr]){ - codebook c; - static_codebook s; - double *qv=alloca(sizeof(double)*TESTSIZE); - double *iv=alloca(sizeof(double)*TESTSIZE); - memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE); - memset(iv,0,sizeof(double)*TESTSIZE); - - fprintf(stderr,"\tpacking/coding %ld... ",ptr); - - /* pack the codebook, write the testvector */ - _oggpack_reset(&write); - vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory - we can write */ - vorbis_staticbook_pack(testlist[ptr],&write); - fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write)); - for(i=0;iused_entries>0){ + int i,j,entry; + float *t; + + for(i=0;ivaluelist+entry*book->dim; + for(j=0;idim;) + a[i++]+=t[j++]; } - - for(i=0;i.000001){ - fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n", - iv[i],qv[i],i); - exit(1); - } - - fprintf(stderr,"OK\n"); - ptr++; } + return(0); +} - /* The above is the trivial stuff; now try unquantizing a log scale codebook */ +/* unlike the others, we guard against n not being an integer number + of internally rather than in the upper layer (called only by + floor0) */ +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;ivaluelist+entry*book->dim; + for (j=0;idim;){ + a[i++]=t[j++]; + } + } + }else{ + int i; - exit(0); + for(i=0;iused_entries>0){ + int m=(offset+n)/ch; + for(i=offset/ch;ivaluelist+entry*book->dim; + for (j=0;idim;j++){ + a[chptr++][i]+=t[j]; + if(chptr==ch){ + chptr=0; + i++; + } + } + } + } + } + return(0); +}