]> git.jsancho.org Git - lugaru.git/blob - libvorbis-1.0.1/lib/codebook.c
Cleaned up some things that don't compile on Mac OS X.
[lugaru.git] / libvorbis-1.0.1 / lib / codebook.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7  *                                                                  *
8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002             *
9  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13  function: basic codebook pack/unpack/code/decode operations
14  last mod: $Id: codebook.c,v 1.39 2002/06/28 22:19:35 xiphmont Exp $
15
16  ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include <ogg/ogg.h>
22 #include "vorbis/codec.h"
23 #include "codebook.h"
24 #include "scales.h"
25 #include "misc.h"
26 #include "os.h"
27
28 /* packs the given codebook into the bitstream **************************/
29
30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
31   long i,j;
32   int ordered=0;
33
34   /* first the basic parameters */
35   oggpack_write(opb,0x564342,24);
36   oggpack_write(opb,c->dim,16);
37   oggpack_write(opb,c->entries,24);
38
39   /* pack the codewords.  There are two packings; length ordered and
40      length random.  Decide between the two now. */
41   
42   for(i=1;i<c->entries;i++)
43     if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
44   if(i==c->entries)ordered=1;
45   
46   if(ordered){
47     /* length ordered.  We only need to say how many codewords of
48        each length.  The actual codewords are generated
49        deterministically */
50
51     long count=0;
52     oggpack_write(opb,1,1);  /* ordered */
53     oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
54
55     for(i=1;i<c->entries;i++){
56       long this=c->lengthlist[i];
57       long last=c->lengthlist[i-1];
58       if(this>last){
59         for(j=last;j<this;j++){
60           oggpack_write(opb,i-count,_ilog(c->entries-count));
61           count=i;
62         }
63       }
64     }
65     oggpack_write(opb,i-count,_ilog(c->entries-count));
66     
67   }else{
68     /* length random.  Again, we don't code the codeword itself, just
69        the length.  This time, though, we have to encode each length */
70     oggpack_write(opb,0,1);   /* unordered */
71     
72     /* algortihmic mapping has use for 'unused entries', which we tag
73        here.  The algorithmic mapping happens as usual, but the unused
74        entry has no codeword. */
75     for(i=0;i<c->entries;i++)
76       if(c->lengthlist[i]==0)break;
77
78     if(i==c->entries){
79       oggpack_write(opb,0,1); /* no unused entries */
80       for(i=0;i<c->entries;i++)
81         oggpack_write(opb,c->lengthlist[i]-1,5);
82     }else{
83       oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
84       for(i=0;i<c->entries;i++){
85         if(c->lengthlist[i]==0){
86           oggpack_write(opb,0,1);
87         }else{
88           oggpack_write(opb,1,1);
89           oggpack_write(opb,c->lengthlist[i]-1,5);
90         }
91       }
92     }
93   }
94
95   /* is the entry number the desired return value, or do we have a
96      mapping? If we have a mapping, what type? */
97   oggpack_write(opb,c->maptype,4);
98   switch(c->maptype){
99   case 0:
100     /* no mapping */
101     break;
102   case 1:case 2:
103     /* implicitly populated value mapping */
104     /* explicitly populated value mapping */
105     
106     if(!c->quantlist){
107       /* no quantlist?  error */
108       return(-1);
109     }
110     
111     /* values that define the dequantization */
112     oggpack_write(opb,c->q_min,32);
113     oggpack_write(opb,c->q_delta,32);
114     oggpack_write(opb,c->q_quant-1,4);
115     oggpack_write(opb,c->q_sequencep,1);
116     
117     {
118       int quantvals;
119       switch(c->maptype){
120       case 1:
121         /* a single column of (c->entries/c->dim) quantized values for
122            building a full value list algorithmically (square lattice) */
123         quantvals=_book_maptype1_quantvals(c);
124         break;
125       case 2:
126         /* every value (c->entries*c->dim total) specified explicitly */
127         quantvals=c->entries*c->dim;
128         break;
129       default: /* NOT_REACHABLE */
130         quantvals=-1;
131       }
132
133       /* quantized values */
134       for(i=0;i<quantvals;i++)
135         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
136
137     }
138     break;
139   default:
140     /* error case; we don't have any other map types now */
141     return(-1);
142   }
143
144   return(0);
145 }
146
147 /* unpacks a codebook from the packet buffer into the codebook struct,
148    readies the codebook auxiliary structures for decode *************/
149 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
150   long i,j;
151   memset(s,0,sizeof(*s));
152   s->allocedp=1;
153
154   /* make sure alignment is correct */
155   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
156
157   /* first the basic parameters */
158   s->dim=oggpack_read(opb,16);
159   s->entries=oggpack_read(opb,24);
160   if(s->entries==-1)goto _eofout;
161
162   /* codeword ordering.... length ordered or unordered? */
163   switch((int)oggpack_read(opb,1)){
164   case 0:
165     /* unordered */
166     s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
167
168     /* allocated but unused entries? */
169     if(oggpack_read(opb,1)){
170       /* yes, unused entries */
171
172       for(i=0;i<s->entries;i++){
173         if(oggpack_read(opb,1)){
174           long num=oggpack_read(opb,5);
175           if(num==-1)goto _eofout;
176           s->lengthlist[i]=num+1;
177         }else
178           s->lengthlist[i]=0;
179       }
180     }else{
181       /* all entries used; no tagging */
182       for(i=0;i<s->entries;i++){
183         long num=oggpack_read(opb,5);
184         if(num==-1)goto _eofout;
185         s->lengthlist[i]=num+1;
186       }
187     }
188     
189     break;
190   case 1:
191     /* ordered */
192     {
193       long length=oggpack_read(opb,5)+1;
194       s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
195
196       for(i=0;i<s->entries;){
197         long num=oggpack_read(opb,_ilog(s->entries-i));
198         if(num==-1)goto _eofout;
199         for(j=0;j<num && i<s->entries;j++,i++)
200           s->lengthlist[i]=length;
201         length++;
202       }
203     }
204     break;
205   default:
206     /* EOF */
207     return(-1);
208   }
209   
210   /* Do we have a mapping to unpack? */
211   switch((s->maptype=oggpack_read(opb,4))){
212   case 0:
213     /* no mapping */
214     break;
215   case 1: case 2:
216     /* implicitly populated value mapping */
217     /* explicitly populated value mapping */
218
219     s->q_min=oggpack_read(opb,32);
220     s->q_delta=oggpack_read(opb,32);
221     s->q_quant=oggpack_read(opb,4)+1;
222     s->q_sequencep=oggpack_read(opb,1);
223
224     {
225       int quantvals=0;
226       switch(s->maptype){
227       case 1:
228         quantvals=_book_maptype1_quantvals(s);
229         break;
230       case 2:
231         quantvals=s->entries*s->dim;
232         break;
233       }
234       
235       /* quantized values */
236       s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
237       for(i=0;i<quantvals;i++)
238         s->quantlist[i]=oggpack_read(opb,s->q_quant);
239       
240       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
241     }
242     break;
243   default:
244     goto _errout;
245   }
246
247   /* all set */
248   return(0);
249   
250  _errout:
251  _eofout:
252   vorbis_staticbook_clear(s);
253   return(-1); 
254 }
255
256 /* returns the number of bits ************************************************/
257 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
258   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
259   return(book->c->lengthlist[a]);
260 }
261
262 /* One the encode side, our vector writers are each designed for a
263 specific purpose, and the encoder is not flexible without modification:
264
265 The LSP vector coder uses a single stage nearest-match with no
266 interleave, so no step and no error return.  This is specced by floor0
267 and doesn't change.
268
269 Residue0 encoding interleaves, uses multiple stages, and each stage
270 peels of a specific amount of resolution from a lattice (thus we want
271 to match by threshold, not nearest match).  Residue doesn't *have* to
272 be encoded that way, but to change it, one will need to add more
273 infrastructure on the encode side (decode side is specced and simpler) */
274
275 /* floor0 LSP (single stage, non interleaved, nearest match) */
276 /* returns entry number and *modifies a* to the quantization value *****/
277 int vorbis_book_errorv(codebook *book,float *a){
278   int dim=book->dim,k;
279   int best=_best(book,a,1);
280   for(k=0;k<dim;k++)
281     a[k]=(book->valuelist+best*dim)[k];
282   return(best);
283 }
284
285 /* returns the number of bits and *modifies a* to the quantization value *****/
286 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
287   int k,dim=book->dim;
288   for(k=0;k<dim;k++)
289     a[k]=(book->valuelist+best*dim)[k];
290   return(vorbis_book_encode(book,best,b));
291 }
292
293 /* the 'eliminate the decode tree' optimization actually requires the
294    codewords to be MSb first, not LSb.  This is an annoying inelegancy
295    (and one of the first places where carefully thought out design
296    turned out to be wrong; Vorbis II and future Ogg codecs should go
297    to an MSb bitpacker), but not actually the huge hit it appears to
298    be.  The first-stage decode table catches most words so that
299    bitreverse is not in the main execution path. */
300
301 static ogg_uint32_t bitreverse(ogg_uint32_t x){
302   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
303   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
304   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
305   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
306   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
307 }
308
309 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
310   int  read=book->dec_maxlength;
311   long lo,hi;
312   long lok = oggpack_look(b,book->dec_firsttablen);
313  
314   if (lok >= 0) {
315     long entry = book->dec_firsttable[lok];
316     if(entry&0x80000000UL){
317       lo=(entry>>15)&0x7fff;
318       hi=book->used_entries-(entry&0x7fff);
319     }else{
320       oggpack_adv(b, book->dec_codelengths[entry-1]);
321       return(entry-1);
322     }
323   }else{
324     lo=0;
325     hi=book->used_entries;
326   }
327
328   lok = oggpack_look(b, read);
329
330   while(lok<0 && read>1)
331     lok = oggpack_look(b, --read);
332   if(lok<0)return -1;
333
334   /* bisect search for the codeword in the ordered list */
335   {
336     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
337
338     while(hi-lo>1){
339       long p=(hi-lo)>>1;
340       long test=book->codelist[lo+p]>testword;    
341       lo+=p&(test-1);
342       hi-=p&(-test);
343     }
344
345     if(book->dec_codelengths[lo]<=read){
346       oggpack_adv(b, book->dec_codelengths[lo]);
347       return(lo);
348     }
349   }
350   
351   oggpack_adv(b, read);
352   return(-1);
353 }
354
355 /* Decode side is specced and easier, because we don't need to find
356    matches using different criteria; we simply read and map.  There are
357    two things we need to do 'depending':
358    
359    We may need to support interleave.  We don't really, but it's
360    convenient to do it here rather than rebuild the vector later.
361
362    Cascades may be additive or multiplicitive; this is not inherent in
363    the codebook, but set in the code using the codebook.  Like
364    interleaving, it's easiest to do it here.  
365    addmul==0 -> declarative (set the value)
366    addmul==1 -> additive
367    addmul==2 -> multiplicitive */
368
369 /* returns the [original, not compacted] entry number or -1 on eof *********/
370 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
371   long packed_entry=decode_packed_entry_number(book,b);
372   if(packed_entry>=0)
373     return(book->dec_index[packed_entry]);
374   
375   /* if there's no dec_index, the codebook unpacking isn't collapsed */
376   return(packed_entry);
377 }
378
379 /* returns 0 on OK or -1 on eof *************************************/
380 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
381   int step=n/book->dim;
382   long *entry = alloca(sizeof(*entry)*step);
383   float **t = alloca(sizeof(*t)*step);
384   int i,j,o;
385
386   for (i = 0; i < step; i++) {
387     entry[i]=decode_packed_entry_number(book,b);
388     if(entry[i]==-1)return(-1);
389     t[i] = book->valuelist+entry[i]*book->dim;
390   }
391   for(i=0,o=0;i<book->dim;i++,o+=step)
392     for (j=0;j<step;j++)
393       a[o+j]+=t[j][i];
394   return(0);
395 }
396
397 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
398   int i,j,entry;
399   float *t;
400
401   if(book->dim>8){
402     for(i=0;i<n;){
403       entry = decode_packed_entry_number(book,b);
404       if(entry==-1)return(-1);
405       t     = book->valuelist+entry*book->dim;
406       for (j=0;j<book->dim;)
407         a[i++]+=t[j++];
408     }
409   }else{
410     for(i=0;i<n;){
411       entry = decode_packed_entry_number(book,b);
412       if(entry==-1)return(-1);
413       t     = book->valuelist+entry*book->dim;
414       j=0;
415       switch((int)book->dim){
416       case 8:
417         a[i++]+=t[j++];
418       case 7:
419         a[i++]+=t[j++];
420       case 6:
421         a[i++]+=t[j++];
422       case 5:
423         a[i++]+=t[j++];
424       case 4:
425         a[i++]+=t[j++];
426       case 3:
427         a[i++]+=t[j++];
428       case 2:
429         a[i++]+=t[j++];
430       case 1:
431         a[i++]+=t[j++];
432       case 0:
433         break;
434       }
435     }
436   }    
437   return(0);
438 }
439
440 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
441   int i,j,entry;
442   float *t;
443
444   for(i=0;i<n;){
445     entry = decode_packed_entry_number(book,b);
446     if(entry==-1)return(-1);
447     t     = book->valuelist+entry*book->dim;
448     for (j=0;j<book->dim;)
449       a[i++]=t[j++];
450   }
451   return(0);
452 }
453
454 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
455                               oggpack_buffer *b,int n){
456   long i,j,entry;
457   int chptr=0;
458
459   for(i=offset/ch;i<(offset+n)/ch;){
460     entry = decode_packed_entry_number(book,b);
461     if(entry==-1)return(-1);
462     {
463       const float *t = book->valuelist+entry*book->dim;
464       for (j=0;j<book->dim;j++){
465         a[chptr++][i]+=t[j];
466         if(chptr==ch){
467           chptr=0;
468           i++;
469         }
470       }
471     }
472   }
473   return(0);
474 }
475
476 #ifdef _V_SELFTEST
477 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
478    number of vectors through (keeping track of the quantized values),
479    and decode using the unpacked book.  quantized version of in should
480    exactly equal out */
481
482 #include <stdio.h>
483
484 #include "vorbis/book/lsp20_0.vqh"
485 #include "vorbis/book/res0a_13.vqh"
486 #define TESTSIZE 40
487
488 float test1[TESTSIZE]={
489   0.105939f,
490   0.215373f,
491   0.429117f,
492   0.587974f,
493
494   0.181173f,
495   0.296583f,
496   0.515707f,
497   0.715261f,
498
499   0.162327f,
500   0.263834f,
501   0.342876f,
502   0.406025f,
503
504   0.103571f,
505   0.223561f,
506   0.368513f,
507   0.540313f,
508
509   0.136672f,
510   0.395882f,
511   0.587183f,
512   0.652476f,
513
514   0.114338f,
515   0.417300f,
516   0.525486f,
517   0.698679f,
518
519   0.147492f,
520   0.324481f,
521   0.643089f,
522   0.757582f,
523
524   0.139556f,
525   0.215795f,
526   0.324559f,
527   0.399387f,
528
529   0.120236f,
530   0.267420f,
531   0.446940f,
532   0.608760f,
533
534   0.115587f,
535   0.287234f,
536   0.571081f,
537   0.708603f,
538 };
539
540 float test3[TESTSIZE]={
541   0,1,-2,3,4,-5,6,7,8,9,
542   8,-2,7,-1,4,6,8,3,1,-9,
543   10,11,12,13,14,15,26,17,18,19,
544   30,-25,-30,-1,-5,-32,4,3,-2,0};
545
546 static_codebook *testlist[]={&_vq_book_lsp20_0,
547                              &_vq_book_res0a_13,NULL};
548 float   *testvec[]={test1,test3};
549
550 int main(){
551   oggpack_buffer write;
552   oggpack_buffer read;
553   long ptr=0,i;
554   oggpack_writeinit(&write);
555   
556   fprintf(stderr,"Testing codebook abstraction...:\n");
557
558   while(testlist[ptr]){
559     codebook c;
560     static_codebook s;
561     float *qv=alloca(sizeof(*qv)*TESTSIZE);
562     float *iv=alloca(sizeof(*iv)*TESTSIZE);
563     memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
564     memset(iv,0,sizeof(*iv)*TESTSIZE);
565
566     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
567
568     /* pack the codebook, write the testvector */
569     oggpack_reset(&write);
570     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
571                                                   we can write */
572     vorbis_staticbook_pack(testlist[ptr],&write);
573     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
574     for(i=0;i<TESTSIZE;i+=c.dim){
575       int best=_best(&c,qv+i,1);
576       vorbis_book_encodev(&c,best,qv+i,&write);
577     }
578     vorbis_book_clear(&c);
579     
580     fprintf(stderr,"OK.\n");
581     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
582
583     /* transfer the write data to a read buffer and unpack/read */
584     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
585     if(vorbis_staticbook_unpack(&read,&s)){
586       fprintf(stderr,"Error unpacking codebook.\n");
587       exit(1);
588     }
589     if(vorbis_book_init_decode(&c,&s)){
590       fprintf(stderr,"Error initializing codebook.\n");
591       exit(1);
592     }
593
594     for(i=0;i<TESTSIZE;i+=c.dim)
595       if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
596         fprintf(stderr,"Error reading codebook test data (EOP).\n");
597         exit(1);
598       }
599     for(i=0;i<TESTSIZE;i++)
600       if(fabs(qv[i]-iv[i])>.000001){
601         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
602                 iv[i],qv[i],i);
603         exit(1);
604       }
605           
606     fprintf(stderr,"OK\n");
607     ptr++;
608   }
609
610   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
611
612   exit(0);
613 }
614
615 #endif