1 /********************************************************************
3 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
6 * PLEASE READ THESE TERMS DISTRIBUTING. *
8 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: basic codebook pack/unpack/code/decode operations
15 last mod: $Id: codebook.c,v 1.8 2000/02/07 20:03:15 xiphmont Exp $
17 ********************************************************************/
21 #include "vorbis/codec.h"
22 #include "vorbis/codebook.h"
24 #include "bookinternal.h"
26 /**** pack/unpack helpers ******************************************/
27 static int ilog(unsigned int v){
36 /* code that packs the 24 bit float can be found in vq/bookutil.c */
38 static double _float24_unpack(long val){
39 double mant=val&0x3ffff;
40 double sign=val&0x800000;
41 double exp =(val&0x7c0000)>>18;
43 return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
46 /* given a list of word lengths, generate a list of codewords. Works
47 for length ordered or unordered, always assigns the lowest valued
49 long *_make_words(long *l,long n){
52 long *r=malloc(n*sizeof(long));
53 memset(marker,0,sizeof(marker));
57 long entry=marker[l[i]];
59 /* when we claim a node for an entry, we also claim the nodes
60 below it (pruning off the imagined tree that may have dangled
61 from it) as well as blocking the use of any nodes directly
65 if(length<32 && (entry>>length)){
66 /* error condition; the lengths must specify an overpopulated tree */
72 /* Look to see if the next shorter marker points to the node
73 above. if so, update it and repeat. */
75 for(j=length;j>0;j--){
78 /* have to jump branches */
82 marker[j]=marker[j-1]<<1;
83 break; /* invariant says next upper marker would already
84 have been moved if it was on the same path */
90 /* prune the tree; the implicit invariant says all the longer
91 markers were dangling from our just-taken node. Dangle them
92 from our *new* node. */
93 for(j=length+1;j<33;j++)
94 marker[j]=marker[j-1]<<1;
97 /* bitreverse the words because our bitwise packer/unpacker is LSb
111 /* build the decode helper tree from the codewords */
112 decode_aux *_make_decode_tree(codebook *c){
113 const static_codebook *s=c->c;
115 decode_aux *t=malloc(sizeof(decode_aux));
116 long *ptr0=t->ptr0=calloc(c->entries*2,sizeof(long));
117 long *ptr1=t->ptr1=calloc(c->entries*2,sizeof(long));
118 long *codelist=_make_words(s->lengthlist,s->entries);
120 if(codelist==NULL)return(NULL);
123 for(i=0;i<c->entries;i++){
125 for(j=0;j<s->lengthlist[i]-1;j++){
126 int bit=(codelist[i]>>j)&1;
137 if(!((codelist[i]>>j)&1))
146 /* unpack the quantized list of values for encode/decode ***********/
147 static double *_book_unquantize(const static_codebook *b){
149 double mindel=_float24_unpack(b->q_min);
150 double delta=_float24_unpack(b->q_delta);
151 double *r=malloc(sizeof(double)*b->entries*b->dim);
153 for(j=0;j<b->entries;j++){
155 for(k=0;k<b->dim;k++){
156 double val=b->quantlist[j*b->dim+k]*delta+last+mindel;
158 if(b->q_sequencep)last=val;
164 void vorbis_staticbook_clear(static_codebook *b){
165 if(b->quantlist)free(b->quantlist);
166 if(b->lengthlist)free(b->lengthlist);
168 free(b->encode_tree->ptr0);
169 free(b->encode_tree->ptr1);
170 free(b->encode_tree->p);
171 free(b->encode_tree->q);
172 memset(b->encode_tree,0,sizeof(encode_aux));
173 free(b->encode_tree);
175 memset(b,0,sizeof(static_codebook));
178 void vorbis_book_clear(codebook *b){
179 /* static book is not cleared; we're likely called on the lookup and
180 the static codebook belongs to the info struct */
182 free(b->decode_tree->ptr0);
183 free(b->decode_tree->ptr1);
184 memset(b->decode_tree,0,sizeof(decode_aux));
185 free(b->decode_tree);
187 if(b->valuelist)free(b->valuelist);
188 if(b->codelist)free(b->codelist);
189 memset(b,0,sizeof(codebook));
192 int vorbis_book_init_encode(codebook *c,const static_codebook *s){
193 memset(c,0,sizeof(codebook));
195 c->entries=s->entries;
197 c->codelist=_make_words(s->lengthlist,s->entries);
198 c->valuelist=_book_unquantize(s);
202 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
203 memset(c,0,sizeof(codebook));
205 c->entries=s->entries;
207 c->valuelist=_book_unquantize(s);
208 c->decode_tree=_make_decode_tree(c);
209 if(c->decode_tree==NULL)goto err_out;
212 vorbis_book_clear(c);
216 /* packs the given codebook into the bitstream **************************/
218 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
222 /* first the basic parameters */
223 _oggpack_write(opb,0x564342,24);
224 _oggpack_write(opb,c->dim,16);
225 _oggpack_write(opb,c->entries,24);
227 /* pack the codewords. There are two packings; length ordered and
228 length random. Decide between the two now. */
230 for(i=1;i<c->entries;i++)
231 if(c->lengthlist[i]<c->lengthlist[i-1])break;
232 if(i==c->entries)ordered=1;
235 /* length ordered. We only need to say how many codewords of
236 each length. The actual codewords are generated
240 _oggpack_write(opb,1,1); /* ordered */
241 _oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
243 for(i=1;i<c->entries;i++){
244 long this=c->lengthlist[i];
245 long last=c->lengthlist[i-1];
247 for(j=last;j<this;j++){
248 _oggpack_write(opb,i-count,ilog(c->entries-count));
253 _oggpack_write(opb,i-count,ilog(c->entries-count));
256 /* length random. Again, we don't code the codeword itself, just
257 the length. This time, though, we have to encode each length */
258 _oggpack_write(opb,0,1); /* unordered */
259 for(i=0;i<c->entries;i++)
260 _oggpack_write(opb,c->lengthlist[i]-1,5);
263 /* is the entry number the desired return value, or do we have a
266 /* we have a mapping. bundle it out. */
267 _oggpack_write(opb,1,1);
269 /* values that define the dequantization */
270 _oggpack_write(opb,c->q_min,24);
271 _oggpack_write(opb,c->q_delta,24);
272 _oggpack_write(opb,c->q_quant-1,4);
273 _oggpack_write(opb,c->q_sequencep,1);
275 /* quantized values */
276 for(i=0;i<c->entries*c->dim;i++)
277 _oggpack_write(opb,c->quantlist[i],c->q_quant);
281 _oggpack_write(opb,0,1);
287 /* unpacks a codebook from the packet buffer into the codebook struct,
288 readies the codebook auxiliary structures for decode *************/
289 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
291 memset(s,0,sizeof(static_codebook));
293 /* make sure alignment is correct */
294 if(_oggpack_read(opb,24)!=0x564342)goto _eofout;
296 /* first the basic parameters */
297 s->dim=_oggpack_read(opb,16);
298 s->entries=_oggpack_read(opb,24);
299 if(s->entries==-1)goto _eofout;
301 /* codeword ordering.... length ordered or unordered? */
302 switch(_oggpack_read(opb,1)){
305 s->lengthlist=malloc(sizeof(long)*s->entries);
306 for(i=0;i<s->entries;i++){
307 long num=_oggpack_read(opb,5);
308 if(num==-1)goto _eofout;
309 s->lengthlist[i]=num+1;
316 long length=_oggpack_read(opb,5)+1;
317 s->lengthlist=malloc(sizeof(long)*s->entries);
319 for(i=0;i<s->entries;){
320 long num=_oggpack_read(opb,ilog(s->entries-i));
321 if(num==-1)goto _eofout;
322 for(j=0;j<num;j++,i++)
323 s->lengthlist[i]=length;
333 /* Do we have a mapping to unpack? */
334 if(_oggpack_read(opb,1)){
336 /* values that define the dequantization */
337 s->q_min=_oggpack_read(opb,24);
338 s->q_delta=_oggpack_read(opb,24);
339 s->q_quant=_oggpack_read(opb,4)+1;
340 s->q_sequencep=_oggpack_read(opb,1);
342 /* quantized values */
343 s->quantlist=malloc(sizeof(double)*s->entries*s->dim);
344 for(i=0;i<s->entries*s->dim;i++)
345 s->quantlist[i]=_oggpack_read(opb,s->q_quant);
346 if(s->quantlist[i-1]==-1)goto _eofout;
354 vorbis_staticbook_clear(s);
358 /* returns the number of bits ***************************************/
359 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
360 _oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
361 return(book->c->lengthlist[a]);
364 static double _dist(int el,double *a, double *b){
368 double val=(a[i]-b[i]);
374 /* returns the number of bits and *modifies a* to the quantized value *****/
375 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
376 encode_aux *t=book->c->encode_tree;
381 /* optimized, using the decision tree */
384 double *p=book->valuelist+t->p[ptr];
385 double *q=book->valuelist+t->q[ptr];
388 c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
398 double this,best=_dist(book->dim,a,book->valuelist);
400 for(i=1;i<book->entries;i++){
401 this=_dist(book->dim,a,book->valuelist+i*book->dim);
408 memcpy(a,book->valuelist-ptr*dim,dim*sizeof(double));
409 return(vorbis_book_encode(book,-ptr,b));
412 /* returns the entry number or -1 on eof ****************************/
413 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
415 decode_aux *t=book->decode_tree;
417 switch(_oggpack_read1(b)){
431 /* returns the entry number or -1 on eof ****************************/
432 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
433 long entry=vorbis_book_decode(book,b);
435 if(entry==-1)return(-1);
436 for(i=0;i<book->dim;i++)a[i]+=(book->valuelist+entry*book->dim)[i];
442 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
443 number of vectors through (keeping track of the quantized values),
444 and decode using the unpacked book. quantized version of in should
448 #include "vorbis/book/lsp20_0.vqh"
449 #include "vorbis/book/lsp32_0.vqh"
557 static_codebook *testlist[]={&_vq_book_lsp20_0,&_vq_book_lsp32_0,NULL};
558 double *testvec[]={test1,test2};
561 oggpack_buffer write;
564 _oggpack_writeinit(&write);
566 fprintf(stderr,"Testing codebook abstraction...:\n");
568 while(testlist[ptr]){
571 double *qv=alloca(sizeof(double)*TESTSIZE);
572 double *iv=alloca(sizeof(double)*TESTSIZE);
573 memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
574 memset(iv,0,sizeof(double)*TESTSIZE);
576 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
578 /* pack the codebook, write the testvector */
579 _oggpack_reset(&write);
580 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
582 vorbis_staticbook_pack(testlist[ptr],&write);
583 fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
584 for(i=0;i<TESTSIZE;i+=TESTDIM)
585 vorbis_book_encodev(&c,qv+i,&write);
586 vorbis_book_clear(&c);
588 fprintf(stderr,"OK.\n");
589 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
591 /* transfer the write data to a read buffer and unpack/read */
592 _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
593 if(vorbis_staticbook_unpack(&read,&s)){
594 fprintf(stderr,"Error unpacking codebook.\n");
597 if(vorbis_book_init_decode(&c,&s)){
598 fprintf(stderr,"Error initializing codebook.\n");
602 for(i=0;i<TESTSIZE;i+=TESTDIM)
603 if(vorbis_book_decodev(&c,iv+i,&read)==-1){
604 fprintf(stderr,"Error reading codebook test data (EOP).\n");
607 for(i=0;i<TESTSIZE;i++)
608 if(fabs(qv[i]-iv[i])>.000001){
609 fprintf(stderr,"input (%g) != output (%g) at position (%ld)\n",
610 iv[i],testvec[ptr][i]-qv[i],i);
614 fprintf(stderr,"OK\n");