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.7 2000/02/06 13:40:39 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 /* returns the number of bits and *modifies a* to the residual error *****/
365 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
366 encode_aux *t=book->c->encode_tree;
372 double *p=book->valuelist+t->p[ptr];
373 double *q=book->valuelist+t->q[ptr];
376 c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
384 for(k=0;k<dim;k++)a[k]-=(book->valuelist-ptr*dim)[k];
385 return(vorbis_book_encode(book,-ptr,b));
388 /* returns the entry number or -1 on eof ****************************/
389 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
391 decode_aux *t=book->decode_tree;
393 switch(_oggpack_read1(b)){
407 /* returns the entry number or -1 on eof ****************************/
408 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
409 long entry=vorbis_book_decode(book,b);
411 if(entry==-1)return(-1);
412 for(i=0;i<book->dim;i++)a[i]+=(book->valuelist+entry*book->dim)[i];
418 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
419 number of vectors through (keeping track of the quantized values),
420 and decode using the unpacked book. quantized version of in should
424 #include "vorbis/book/lsp20_0.vqh"
425 #include "vorbis/book/lsp32_0.vqh"
533 static_codebook *testlist[]={&_vq_book_lsp20_0,&_vq_book_lsp32_0,NULL};
534 double *testvec[]={test1,test2};
537 oggpack_buffer write;
540 _oggpack_writeinit(&write);
542 fprintf(stderr,"Testing codebook abstraction...:\n");
544 while(testlist[ptr]){
547 double *qv=alloca(sizeof(double)*TESTSIZE);
548 double *iv=alloca(sizeof(double)*TESTSIZE);
549 memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
550 memset(iv,0,sizeof(double)*TESTSIZE);
552 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
554 /* pack the codebook, write the testvector */
555 _oggpack_reset(&write);
556 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
558 vorbis_staticbook_pack(testlist[ptr],&write);
559 fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
560 for(i=0;i<TESTSIZE;i+=TESTDIM)
561 vorbis_book_encodev(&c,qv+i,&write);
562 vorbis_book_clear(&c);
564 fprintf(stderr,"OK.\n");
565 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
567 /* transfer the write data to a read buffer and unpack/read */
568 _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
569 if(vorbis_staticbook_unpack(&read,&s)){
570 fprintf(stderr,"Error unpacking codebook.\n");
573 if(vorbis_book_init_decode(&c,&s)){
574 fprintf(stderr,"Error initializing codebook.\n");
578 for(i=0;i<TESTSIZE;i+=TESTDIM)
579 if(vorbis_book_decodev(&c,iv+i,&read)==-1){
580 fprintf(stderr,"Error reading codebook test data (EOP).\n");
583 for(i=0;i<TESTSIZE;i++)
584 if(fabs(testvec[ptr][i]-qv[i]-iv[i])>.000001){
585 fprintf(stderr,"input (%g) != output (%g) at position (%ld)\n",
586 iv[i],testvec[ptr][i]-qv[i],i);
590 fprintf(stderr,"OK\n");