Kill some warnings. Oh, and make examples compile again under
[platform/upstream/libvorbis.git] / 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-2001             *
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.33 2001/12/19 23:13:33 segher 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(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 /* res0 (multistage, interleave, lattice) */
294 /* returns the number of bits and *modifies a* to the remainder value ********/
295 int vorbis_book_encodevs(codebook *book,float *a,oggpack_buffer *b,
296                          int step,int addmul){
297
298   int best=vorbis_book_besterror(book,a,step,addmul);
299   return(vorbis_book_encode(book,best,b));
300 }
301
302 /* Decode side is specced and easier, because we don't need to find
303    matches using different criteria; we simply read and map.  There are
304    two things we need to do 'depending':
305    
306    We may need to support interleave.  We don't really, but it's
307    convenient to do it here rather than rebuild the vector later.
308
309    Cascades may be additive or multiplicitive; this is not inherent in
310    the codebook, but set in the code using the codebook.  Like
311    interleaving, it's easiest to do it here.  
312    addmul==0 -> declarative (set the value)
313    addmul==1 -> additive
314    addmul==2 -> multiplicitive */
315
316 /* returns the entry number or -1 on eof *************************************/
317 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
318   long ptr=0;
319   decode_aux *t=book->decode_tree;
320   int lok = oggpack_look(b, t->tabn);
321
322   if (lok >= 0) {
323     ptr = t->tab[lok];
324     oggpack_adv(b, t->tabl[lok]);
325     if (ptr <= 0)
326       return -ptr;
327   }
328
329   do{
330     switch(oggpack_read1(b)){
331     case 0:
332       ptr=t->ptr0[ptr];
333       break;
334     case 1:
335       ptr=t->ptr1[ptr];
336       break;
337     case -1:
338       return(-1);
339     }
340   }while(ptr>0);
341   return(-ptr);
342 }
343
344 /* returns 0 on OK or -1 on eof *************************************/
345 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
346   int step=n/book->dim;
347   long *entry = alloca(sizeof(*entry)*step);
348   float **t = alloca(sizeof(*t)*step);
349   int i,j,o;
350
351   for (i = 0; i < step; i++) {
352     entry[i]=vorbis_book_decode(book,b);
353     if(entry[i]==-1)return(-1);
354     t[i] = book->valuelist+entry[i]*book->dim;
355   }
356   for(i=0,o=0;i<book->dim;i++,o+=step)
357     for (j=0;j<step;j++)
358       a[o+j]+=t[j][i];
359   return(0);
360 }
361
362 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
363   int i,j,entry;
364   float *t;
365
366   if(book->dim>8){
367     for(i=0;i<n;){
368       entry = vorbis_book_decode(book,b);
369       if(entry==-1)return(-1);
370       t     = book->valuelist+entry*book->dim;
371       for (j=0;j<book->dim;)
372         a[i++]+=t[j++];
373     }
374   }else{
375     for(i=0;i<n;){
376       entry = vorbis_book_decode(book,b);
377       if(entry==-1)return(-1);
378       t     = book->valuelist+entry*book->dim;
379       j=0;
380       switch(book->dim){
381       case 8:
382         a[i++]+=t[j++];
383       case 7:
384         a[i++]+=t[j++];
385       case 6:
386         a[i++]+=t[j++];
387       case 5:
388         a[i++]+=t[j++];
389       case 4:
390         a[i++]+=t[j++];
391       case 3:
392         a[i++]+=t[j++];
393       case 2:
394         a[i++]+=t[j++];
395       case 1:
396         a[i++]+=t[j++];
397       case 0:
398         break;
399       }
400     }
401   }    
402   return(0);
403 }
404
405 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
406   int i,j,entry;
407   float *t;
408
409   for(i=0;i<n;){
410     entry = vorbis_book_decode(book,b);
411     if(entry==-1)return(-1);
412     t     = book->valuelist+entry*book->dim;
413     for (j=0;j<book->dim;)
414       a[i++]=t[j++];
415   }
416   return(0);
417 }
418
419 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
420                               oggpack_buffer *b,int n){
421   long i,j,entry;
422   int chptr=0;
423
424   for(i=offset/ch;i<(offset+n)/ch;){
425     entry = vorbis_book_decode(book,b);
426     if(entry==-1)return(-1);
427     {
428       const float *t = book->valuelist+entry*book->dim;
429       for (j=0;j<book->dim;j++){
430         a[chptr++][i]+=t[j];
431         if(chptr==ch){
432           chptr=0;
433           i++;
434         }
435       }
436     }
437   }
438   return(0);
439 }
440
441 #ifdef _V_SELFTEST
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
445    exactly equal out */
446
447 #include <stdio.h>
448
449 #include "vorbis/book/lsp20_0.vqh"
450 #include "vorbis/book/res0a_13.vqh"
451 #define TESTSIZE 40
452
453 float test1[TESTSIZE]={
454   0.105939f,
455   0.215373f,
456   0.429117f,
457   0.587974f,
458
459   0.181173f,
460   0.296583f,
461   0.515707f,
462   0.715261f,
463
464   0.162327f,
465   0.263834f,
466   0.342876f,
467   0.406025f,
468
469   0.103571f,
470   0.223561f,
471   0.368513f,
472   0.540313f,
473
474   0.136672f,
475   0.395882f,
476   0.587183f,
477   0.652476f,
478
479   0.114338f,
480   0.417300f,
481   0.525486f,
482   0.698679f,
483
484   0.147492f,
485   0.324481f,
486   0.643089f,
487   0.757582f,
488
489   0.139556f,
490   0.215795f,
491   0.324559f,
492   0.399387f,
493
494   0.120236f,
495   0.267420f,
496   0.446940f,
497   0.608760f,
498
499   0.115587f,
500   0.287234f,
501   0.571081f,
502   0.708603f,
503 };
504
505 float test3[TESTSIZE]={
506   0,1,-2,3,4,-5,6,7,8,9,
507   8,-2,7,-1,4,6,8,3,1,-9,
508   10,11,12,13,14,15,26,17,18,19,
509   30,-25,-30,-1,-5,-32,4,3,-2,0};
510
511 static_codebook *testlist[]={&_vq_book_lsp20_0,
512                              &_vq_book_res0a_13,NULL};
513 float   *testvec[]={test1,test3};
514
515 int main(){
516   oggpack_buffer write;
517   oggpack_buffer read;
518   long ptr=0,i;
519   oggpack_writeinit(&write);
520   
521   fprintf(stderr,"Testing codebook abstraction...:\n");
522
523   while(testlist[ptr]){
524     codebook c;
525     static_codebook s;
526     float *qv=alloca(sizeof(*qv)*TESTSIZE);
527     float *iv=alloca(sizeof(*iv)*TESTSIZE);
528     memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
529     memset(iv,0,sizeof(*iv)*TESTSIZE);
530
531     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
532
533     /* pack the codebook, write the testvector */
534     oggpack_reset(&write);
535     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
536                                                   we can write */
537     vorbis_staticbook_pack(testlist[ptr],&write);
538     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
539     for(i=0;i<TESTSIZE;i+=c.dim){
540       int best=_best(&c,qv+i,1);
541       vorbis_book_encodev(&c,best,qv+i,&write);
542     }
543     vorbis_book_clear(&c);
544     
545     fprintf(stderr,"OK.\n");
546     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
547
548     /* transfer the write data to a read buffer and unpack/read */
549     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
550     if(vorbis_staticbook_unpack(&read,&s)){
551       fprintf(stderr,"Error unpacking codebook.\n");
552       exit(1);
553     }
554     if(vorbis_book_init_decode(&c,&s)){
555       fprintf(stderr,"Error initializing codebook.\n");
556       exit(1);
557     }
558
559     for(i=0;i<TESTSIZE;i+=c.dim)
560       if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
561         fprintf(stderr,"Error reading codebook test data (EOP).\n");
562         exit(1);
563       }
564     for(i=0;i<TESTSIZE;i++)
565       if(fabs(qv[i]-iv[i])>.000001){
566         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
567                 iv[i],qv[i],i);
568         exit(1);
569       }
570           
571     fprintf(stderr,"OK\n");
572     ptr++;
573   }
574
575   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
576
577   exit(0);
578 }
579
580 #endif