Merge of the current Monty branch; this brings in new psychoacoustic
[platform/upstream/libvorbis.git] / lib / codebook.c
1 /********************************************************************
2  *                                                                  *
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.                            *
7  *                                                                  *
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/                                             *
11  *                                                                  *
12  ********************************************************************
13
14  function: basic codebook pack/unpack/code/decode operations
15  last mod: $Id: codebook.c,v 1.15 2000/06/14 01:38:31 xiphmont Exp $
16
17  ********************************************************************/
18
19 #include <stdlib.h>
20 #include <string.h>
21 #include <math.h>
22 #include "vorbis/codec.h"
23 #include "vorbis/codebook.h"
24 #include "bitwise.h"
25 #include "scales.h"
26 #include "sharedbook.h"
27 #include "bookinternal.h"
28 #include "misc.h"
29
30 /* packs the given codebook into the bitstream **************************/
31
32 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
33   long i,j;
34   int ordered=0;
35
36   /* first the basic parameters */
37   _oggpack_write(opb,0x564342,24);
38   _oggpack_write(opb,c->dim,16);
39   _oggpack_write(opb,c->entries,24);
40
41   /* pack the codewords.  There are two packings; length ordered and
42      length random.  Decide between the two now. */
43   
44   for(i=1;i<c->entries;i++)
45     if(c->lengthlist[i]<c->lengthlist[i-1])break;
46   if(i==c->entries)ordered=1;
47   
48   if(ordered){
49     /* length ordered.  We only need to say how many codewords of
50        each length.  The actual codewords are generated
51        deterministically */
52
53     long count=0;
54     _oggpack_write(opb,1,1);  /* ordered */
55     _oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
56
57     for(i=1;i<c->entries;i++){
58       long this=c->lengthlist[i];
59       long last=c->lengthlist[i-1];
60       if(this>last){
61         for(j=last;j<this;j++){
62           _oggpack_write(opb,i-count,_ilog(c->entries-count));
63           count=i;
64         }
65       }
66     }
67     _oggpack_write(opb,i-count,_ilog(c->entries-count));
68     
69   }else{
70     /* length random.  Again, we don't code the codeword itself, just
71        the length.  This time, though, we have to encode each length */
72     _oggpack_write(opb,0,1);   /* unordered */
73     
74     /* algortihmic mapping has use for 'unused entries', which we tag
75        here.  The algorithmic mapping happens as usual, but the unused
76        entry has no codeword. */
77     for(i=0;i<c->entries;i++)
78       if(c->lengthlist[i]==0)break;
79
80     if(i==c->entries){
81       _oggpack_write(opb,0,1); /* no unused entries */
82       for(i=0;i<c->entries;i++)
83         _oggpack_write(opb,c->lengthlist[i]-1,5);
84     }else{
85       _oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
86       for(i=0;i<c->entries;i++){
87         if(c->lengthlist[i]==0){
88           _oggpack_write(opb,0,1);
89         }else{
90           _oggpack_write(opb,1,1);
91           _oggpack_write(opb,c->lengthlist[i]-1,5);
92         }
93       }
94     }
95   }
96
97   /* is the entry number the desired return value, or do we have a
98      mapping? If we have a mapping, what type? */
99   _oggpack_write(opb,c->maptype,4);
100   switch(c->maptype){
101   case 0:
102     /* no mapping */
103     break;
104   case 1:case 2:
105     /* implicitly populated value mapping */
106     /* explicitly populated value mapping */
107     
108     if(!c->quantlist){
109       /* no quantlist?  error */
110       return(-1);
111     }
112     
113     /* values that define the dequantization */
114     _oggpack_write(opb,c->q_min,32);
115     _oggpack_write(opb,c->q_delta,32);
116     _oggpack_write(opb,c->q_quant-1,4);
117     _oggpack_write(opb,c->q_sequencep,1);
118     
119     {
120       int quantvals;
121       switch(c->maptype){
122       case 1:
123         /* a single column of (c->entries/c->dim) quantized values for
124            building a full value list algorithmically (square lattice) */
125         quantvals=_book_maptype1_quantvals(c);
126         break;
127       case 2:
128         /* every value (c->entries*c->dim total) specified explicitly */
129         quantvals=c->entries*c->dim;
130         break;
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(static_codebook));
152
153   /* make sure alignment is correct */
154   if(_oggpack_read(opb,24)!=0x564342)goto _eofout;
155
156   /* first the basic parameters */
157   s->dim=_oggpack_read(opb,16);
158   s->entries=_oggpack_read(opb,24);
159   if(s->entries==-1)goto _eofout;
160
161   /* codeword ordering.... length ordered or unordered? */
162   switch(_oggpack_read(opb,1)){
163   case 0:
164     /* unordered */
165     s->lengthlist=malloc(sizeof(long)*s->entries);
166
167     /* allocated but unused entries? */
168     if(_oggpack_read(opb,1)){
169       /* yes, unused entries */
170
171       for(i=0;i<s->entries;i++){
172         if(_oggpack_read(opb,1)){
173           long num=_oggpack_read(opb,5);
174           if(num==-1)goto _eofout;
175           s->lengthlist[i]=num+1;
176         }else
177           s->lengthlist[i]=0;
178       }
179     }else{
180       /* all entries used; no tagging */
181       for(i=0;i<s->entries;i++){
182         long num=_oggpack_read(opb,5);
183         if(num==-1)goto _eofout;
184         s->lengthlist[i]=num+1;
185       }
186     }
187     
188     break;
189   case 1:
190     /* ordered */
191     {
192       long length=_oggpack_read(opb,5)+1;
193       s->lengthlist=malloc(sizeof(long)*s->entries);
194
195       for(i=0;i<s->entries;){
196         long num=_oggpack_read(opb,_ilog(s->entries-i));
197         if(num==-1)goto _eofout;
198         for(j=0;j<num;j++,i++)
199           s->lengthlist[i]=length;
200         length++;
201       }
202     }
203     break;
204   default:
205     /* EOF */
206     return(-1);
207   }
208   
209   /* Do we have a mapping to unpack? */
210   switch((s->maptype=_oggpack_read(opb,4))){
211   case 0:
212     /* no mapping */
213     break;
214   case 1: case 2:
215     /* implicitly populated value mapping */
216     /* explicitly populated value mapping */
217
218     s->q_min=_oggpack_read(opb,32);
219     s->q_delta=_oggpack_read(opb,32);
220     s->q_quant=_oggpack_read(opb,4)+1;
221     s->q_sequencep=_oggpack_read(opb,1);
222
223     {
224       int quantvals;
225       switch(s->maptype){
226       case 1:
227         quantvals=_book_maptype1_quantvals(s);
228         break;
229       case 2:
230         quantvals=s->entries*s->dim;
231         break;
232       }
233       
234       /* quantized values */
235       s->quantlist=malloc(sizeof(double)*quantvals);
236       for(i=0;i<quantvals;i++)
237         s->quantlist[i]=_oggpack_read(opb,s->q_quant);
238       
239       if(s->quantlist[quantvals-1]==-1)goto _eofout;
240     }
241     break;
242   default:
243     goto _errout;
244   }
245
246   /* all set */
247   return(0);
248   
249  _errout:
250  _eofout:
251   vorbis_staticbook_clear(s);
252   return(-1); 
253 }
254
255 /* returns the number of bits ************************************************/
256 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
257   _oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
258   return(book->c->lengthlist[a]);
259 }
260
261 /* One the encode side, our vector writers are each designed for a
262 specific purpose, and the encoder is not flexible without modification:
263
264 The LSP vector coder uses a single stage nearest-match with no
265 interleave, so no step and no error return.  This is specced by floor0
266 and doesn't change.
267
268 Residue0 encoding interleaves, uses multiple stages, and each stage
269 peels of a specific amount of resolution from a lattice (thus we want
270 to match by threshhold, not nearest match).  Residue doesn't *have* to
271 be encoded that way, but to change it, one will need to add more
272 infrastructure on the encode side (decode side is specced and simpler) */
273
274 /* floor0 LSP (single stage, non interleaved, nearest match) */
275 /* returns entry number and *modifies a* to the quantization value *****/
276 int vorbis_book_errorv(codebook *book,double *a){
277   int dim=book->dim,k;
278   int best=_best(book,a,1);
279   for(k=0;k<dim;k++)
280     a[k]=(book->valuelist+best*dim)[k];
281   return(best);
282 }
283
284 /* returns the number of bits and *modifies a* to the quantization value *****/
285 int vorbis_book_encodev(codebook *book,int best,double *a,oggpack_buffer *b){
286   int k,dim=book->dim;
287   for(k=0;k<dim;k++)
288     a[k]=(book->valuelist+best*dim)[k];
289   return(vorbis_book_encode(book,best,b));
290 }
291
292 /* res0 (multistage, interleave, lattice) */
293 /* returns the number of bits and *modifies a* to the remainder value ********/
294 int vorbis_book_encodevs(codebook *book,double *a,oggpack_buffer *b,
295                          int step,int addmul){
296
297   int best=vorbis_book_besterror(book,a,step,addmul);
298   return(vorbis_book_encode(book,best,b));
299 }
300
301 /* Decode side is specced and easier, because we don't need to find
302    matches using different criteria; we simply read and map.  There are
303    two things we need to do 'depending':
304    
305    We may need to support interleave.  We don't really, but it's
306    convenient to do it here rather than rebuild the vector later.
307
308    Cascades may be additive or multiplicitive; this is not inherent in
309    the codebook, but set in the code using the codebook.  Like
310    interleaving, it's easiest to do it here.  
311    stage==0 -> declarative (set the value)
312    stage==1 -> additive
313    stage==2 -> multiplicitive */
314
315 /* returns the entry number or -1 on eof *************************************/
316 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
317   long ptr=0;
318   decode_aux *t=book->decode_tree;
319   do{
320     switch(_oggpack_read1(b)){
321     case 0:
322       ptr=t->ptr0[ptr];
323       break;
324     case 1:
325       ptr=t->ptr1[ptr];
326       break;
327     case -1:
328       return(-1);
329     }
330   }while(ptr>0);
331   return(-ptr);
332 }
333
334 /* returns the entry number or -1 on eof *************************************/
335 long vorbis_book_decodevs(codebook *book,double *a,oggpack_buffer *b,
336                           int step,int addmul){
337   long entry=vorbis_book_decode(book,b);
338   int i,o;
339   if(entry==-1)return(-1);
340   switch(addmul){
341   case -1:
342     for(i=0,o=0;i<book->dim;i++,o+=step)
343       a[o]=(book->valuelist+entry*book->dim)[i];
344     break;
345   case 0:
346     for(i=0,o=0;i<book->dim;i++,o+=step)
347       a[o]+=(book->valuelist+entry*book->dim)[i];
348     break;
349   case 1:
350     for(i=0,o=0;i<book->dim;i++,o+=step)
351       a[o]*=(book->valuelist+entry*book->dim)[i];
352     break;
353   }
354   return(entry);
355 }
356
357 #ifdef _V_SELFTEST
358
359 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
360    number of vectors through (keeping track of the quantized values),
361    and decode using the unpacked book.  quantized version of in should
362    exactly equal out */
363
364 #include <stdio.h>
365 #include "vorbis/book/lsp20_0.vqh"
366 #include "vorbis/book/lsp32_0.vqh"
367 #include "vorbis/book/res0_1a.vqh"
368 #define TESTSIZE 40
369
370 double test1[TESTSIZE]={
371   0.105939,
372   0.215373,
373   0.429117,
374   0.587974,
375
376   0.181173,
377   0.296583,
378   0.515707,
379   0.715261,
380
381   0.162327,
382   0.263834,
383   0.342876,
384   0.406025,
385
386   0.103571,
387   0.223561,
388   0.368513,
389   0.540313,
390
391   0.136672,
392   0.395882,
393   0.587183,
394   0.652476,
395
396   0.114338,
397   0.417300,
398   0.525486,
399   0.698679,
400
401   0.147492,
402   0.324481,
403   0.643089,
404   0.757582,
405
406   0.139556,
407   0.215795,
408   0.324559,
409   0.399387,
410
411   0.120236,
412   0.267420,
413   0.446940,
414   0.608760,
415
416   0.115587,
417   0.287234,
418   0.571081,
419   0.708603,
420 };
421
422 double test2[TESTSIZE]={
423   0.088654,
424   0.165742,
425   0.279013,
426   0.395894,
427
428   0.110812,
429   0.218422,
430   0.283423,
431   0.371719,
432
433   0.136985,
434   0.186066,
435   0.309814,
436   0.381521,
437
438   0.123925,
439   0.211707,
440   0.314771,
441   0.433026,
442
443   0.088619,
444   0.192276,
445   0.277568,
446   0.343509,
447
448   0.068400,
449   0.132901,
450   0.223999,
451   0.302538,
452
453   0.202159,
454   0.306131,
455   0.360362,
456   0.416066,
457
458   0.072591,
459   0.178019,
460   0.304315,
461   0.376516,
462
463   0.094336,
464   0.188401,
465   0.325119,
466   0.390264,
467
468   0.091636,
469   0.223099,
470   0.282899,
471   0.375124,
472 };
473
474 double test3[TESTSIZE]={
475   0,1,-2,3,4,-5,6,7,8,9,
476   8,-2,7,-1,4,6,8,3,1,-9,
477   10,11,12,13,14,15,26,17,18,19,
478   30,-25,-30,-1,-5,-32,4,3,-2,0};
479
480 static_codebook *testlist[]={&_vq_book_lsp20_0,
481                              &_vq_book_lsp32_0,
482                              &_vq_book_res0_1a,NULL};
483 double   *testvec[]={test1,test2,test3};
484
485 int main(){
486   oggpack_buffer write;
487   oggpack_buffer read;
488   long ptr=0,i;
489   _oggpack_writeinit(&write);
490   
491   fprintf(stderr,"Testing codebook abstraction...:\n");
492
493   while(testlist[ptr]){
494     codebook c;
495     static_codebook s;
496     double *qv=alloca(sizeof(double)*TESTSIZE);
497     double *iv=alloca(sizeof(double)*TESTSIZE);
498     memcpy(qv,testvec[ptr],sizeof(double)*TESTSIZE);
499     memset(iv,0,sizeof(double)*TESTSIZE);
500
501     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
502
503     /* pack the codebook, write the testvector */
504     _oggpack_reset(&write);
505     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
506                                                   we can write */
507     vorbis_staticbook_pack(testlist[ptr],&write);
508     fprintf(stderr,"Codebook size %ld bytes... ",_oggpack_bytes(&write));
509     for(i=0;i<TESTSIZE;i+=c.dim)
510       vorbis_book_encodev(&c,qv+i,&write);
511     vorbis_book_clear(&c);
512     
513     fprintf(stderr,"OK.\n");
514     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
515
516     /* transfer the write data to a read buffer and unpack/read */
517     _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
518     if(vorbis_staticbook_unpack(&read,&s)){
519       fprintf(stderr,"Error unpacking codebook.\n");
520       exit(1);
521     }
522     if(vorbis_book_init_decode(&c,&s)){
523       fprintf(stderr,"Error initializing codebook.\n");
524       exit(1);
525     }
526
527     for(i=0;i<TESTSIZE;i+=c.dim)
528       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
529         fprintf(stderr,"Error reading codebook test data (EOP).\n");
530         exit(1);
531       }
532     for(i=0;i<TESTSIZE;i++)
533       if(fabs(qv[i]-iv[i])>.000001){
534         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
535                 iv[i],qv[i],i);
536         exit(1);
537       }
538           
539     fprintf(stderr,"OK\n");
540     ptr++;
541   }
542
543   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
544
545   exit(0);
546 }
547
548 #endif