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-2009             *
9 * by the Xiph.Org Foundation http://www.xiph.org/                  *
10 *                                                                  *
11 ********************************************************************
12
13 function: basic codebook pack/unpack/code/decode operations
14 last mod: $Id: codebook.c 16227 2009-07-08 06:58:46Z xiphmont $
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
30int 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 *************/
149int 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  if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
163
164  /* codeword ordering.... length ordered or unordered? */
165  switch((int)oggpack_read(opb,1)){
166  case 0:
167    /* unordered */
168    s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
169
170    /* allocated but unused entries? */
171    if(oggpack_read(opb,1)){
172      /* yes, unused entries */
173
174      for(i=0;i<s->entries;i++){
175        if(oggpack_read(opb,1)){
176          long num=oggpack_read(opb,5);
177          if(num==-1)goto _eofout;
178          s->lengthlist[i]=num+1;
179        }else
180          s->lengthlist[i]=0;
181      }
182    }else{
183      /* all entries used; no tagging */
184      for(i=0;i<s->entries;i++){
185        long num=oggpack_read(opb,5);
186        if(num==-1)goto _eofout;
187        s->lengthlist[i]=num+1;
188      }
189    }
190
191    break;
192  case 1:
193    /* ordered */
194    {
195      long length=oggpack_read(opb,5)+1;
196      s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
197
198      for(i=0;i<s->entries;){
199        long num=oggpack_read(opb,_ilog(s->entries-i));
200        if(num==-1)goto _eofout;
201        for(j=0;j<num && i<s->entries;j++,i++)
202          s->lengthlist[i]=length;
203        length++;
204      }
205    }
206    break;
207  default:
208    /* EOF */
209    return(-1);
210  }
211
212  /* Do we have a mapping to unpack? */
213  switch((s->maptype=oggpack_read(opb,4))){
214  case 0:
215    /* no mapping */
216    break;
217  case 1: case 2:
218    /* implicitly populated value mapping */
219    /* explicitly populated value mapping */
220
221    s->q_min=oggpack_read(opb,32);
222    s->q_delta=oggpack_read(opb,32);
223    s->q_quant=oggpack_read(opb,4)+1;
224    s->q_sequencep=oggpack_read(opb,1);
225    if(s->q_sequencep==-1)goto _eofout;
226
227    {
228      int quantvals=0;
229      switch(s->maptype){
230      case 1:
231        quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
232        break;
233      case 2:
234        quantvals=s->entries*s->dim;
235        break;
236      }
237
238      /* quantized values */
239      s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
240      for(i=0;i<quantvals;i++)
241        s->quantlist[i]=oggpack_read(opb,s->q_quant);
242
243      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
244    }
245    break;
246  default:
247    goto _errout;
248  }
249
250  /* all set */
251  return(0);
252
253 _errout:
254 _eofout:
255  vorbis_staticbook_clear(s);
256  return(-1);
257}
258
259/* returns the number of bits ************************************************/
260int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
261  if(a<0 || a>=book->c->entries)return(0);
262  oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
263  return(book->c->lengthlist[a]);
264}
265
266/* One the encode side, our vector writers are each designed for a
267specific purpose, and the encoder is not flexible without modification:
268
269The LSP vector coder uses a single stage nearest-match with no
270interleave, so no step and no error return.  This is specced by floor0
271and doesn't change.
272
273Residue0 encoding interleaves, uses multiple stages, and each stage
274peels of a specific amount of resolution from a lattice (thus we want
275to match by threshold, not nearest match).  Residue doesn't *have* to
276be encoded that way, but to change it, one will need to add more
277infrastructure on the encode side (decode side is specced and simpler) */
278
279/* floor0 LSP (single stage, non interleaved, nearest match) */
280/* returns entry number and *modifies a* to the quantization value *****/
281int vorbis_book_errorv(codebook *book,float *a){
282  int dim=book->dim,k;
283  int best=_best(book,a,1);
284  for(k=0;k<dim;k++)
285    a[k]=(book->valuelist+best*dim)[k];
286  return(best);
287}
288
289/* returns the number of bits and *modifies a* to the quantization value *****/
290int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
291  int k,dim=book->dim;
292  for(k=0;k<dim;k++)
293    a[k]=(book->valuelist+best*dim)[k];
294  return(vorbis_book_encode(book,best,b));
295}
296
297/* the 'eliminate the decode tree' optimization actually requires the
298   codewords to be MSb first, not LSb.  This is an annoying inelegancy
299   (and one of the first places where carefully thought out design
300   turned out to be wrong; Vorbis II and future Ogg codecs should go
301   to an MSb bitpacker), but not actually the huge hit it appears to
302   be.  The first-stage decode table catches most words so that
303   bitreverse is not in the main execution path. */
304
305static ogg_uint32_t bitreverse(ogg_uint32_t x){
306  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
307  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
308  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
309  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
310  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
311}
312
313STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
314  int  read=book->dec_maxlength;
315  long lo,hi;
316  long lok = oggpack_look(b,book->dec_firsttablen);
317
318  if (lok >= 0) {
319    long entry = book->dec_firsttable[lok];
320    if(entry&0x80000000UL){
321      lo=(entry>>15)&0x7fff;
322      hi=book->used_entries-(entry&0x7fff);
323    }else{
324      oggpack_adv(b, book->dec_codelengths[entry-1]);
325      return(entry-1);
326    }
327  }else{
328    lo=0;
329    hi=book->used_entries;
330  }
331
332  lok = oggpack_look(b, read);
333
334  while(lok<0 && read>1)
335    lok = oggpack_look(b, --read);
336  if(lok<0)return -1;
337
338  /* bisect search for the codeword in the ordered list */
339  {
340    ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
341
342    while(hi-lo>1){
343      long p=(hi-lo)>>1;
344      long test=book->codelist[lo+p]>testword;
345      lo+=p&(test-1);
346      hi-=p&(-test);
347      }
348
349    if(book->dec_codelengths[lo]<=read){
350      oggpack_adv(b, book->dec_codelengths[lo]);
351      return(lo);
352    }
353  }
354
355  oggpack_adv(b, read);
356
357  return(-1);
358}
359
360/* Decode side is specced and easier, because we don't need to find
361   matches using different criteria; we simply read and map.  There are
362   two things we need to do 'depending':
363
364   We may need to support interleave.  We don't really, but it's
365   convenient to do it here rather than rebuild the vector later.
366
367   Cascades may be additive or multiplicitive; this is not inherent in
368   the codebook, but set in the code using the codebook.  Like
369   interleaving, it's easiest to do it here.
370   addmul==0 -> declarative (set the value)
371   addmul==1 -> additive
372   addmul==2 -> multiplicitive */
373
374/* returns the [original, not compacted] entry number or -1 on eof *********/
375long vorbis_book_decode(codebook *book, oggpack_buffer *b){
376  if(book->used_entries>0){
377    long packed_entry=decode_packed_entry_number(book,b);
378    if(packed_entry>=0)
379      return(book->dec_index[packed_entry]);
380  }
381
382  /* if there's no dec_index, the codebook unpacking isn't collapsed */
383  return(-1);
384}
385
386/* returns 0 on OK or -1 on eof *************************************/
387long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
388  if(book->used_entries>0){
389    int step=n/book->dim;
390    long *entry = alloca(sizeof(*entry)*step);
391    float **t = alloca(sizeof(*t)*step);
392    int i,j,o;
393
394    for (i = 0; i < step; i++) {
395      entry[i]=decode_packed_entry_number(book,b);
396      if(entry[i]==-1)return(-1);
397      t[i] = book->valuelist+entry[i]*book->dim;
398    }
399    for(i=0,o=0;i<book->dim;i++,o+=step)
400      for (j=0;j<step;j++)
401        a[o+j]+=t[j][i];
402  }
403  return(0);
404}
405
406long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
407  if(book->used_entries>0){
408    int i,j,entry;
409    float *t;
410
411    if(book->dim>8){
412      for(i=0;i<n;){
413        entry = decode_packed_entry_number(book,b);
414        if(entry==-1)return(-1);
415        t     = book->valuelist+entry*book->dim;
416        for (j=0;j<book->dim;)
417          a[i++]+=t[j++];
418      }
419    }else{
420      for(i=0;i<n;){
421        entry = decode_packed_entry_number(book,b);
422        if(entry==-1)return(-1);
423        t     = book->valuelist+entry*book->dim;
424        j=0;
425        switch((int)book->dim){
426        case 8:
427          a[i++]+=t[j++];
428        case 7:
429          a[i++]+=t[j++];
430        case 6:
431          a[i++]+=t[j++];
432        case 5:
433          a[i++]+=t[j++];
434        case 4:
435          a[i++]+=t[j++];
436        case 3:
437          a[i++]+=t[j++];
438        case 2:
439          a[i++]+=t[j++];
440        case 1:
441          a[i++]+=t[j++];
442        case 0:
443          break;
444        }
445      }
446    }
447  }
448  return(0);
449}
450
451long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
452  if(book->used_entries>0){
453    int i,j,entry;
454    float *t;
455
456    for(i=0;i<n;){
457      entry = decode_packed_entry_number(book,b);
458      if(entry==-1)return(-1);
459      t     = book->valuelist+entry*book->dim;
460      for (j=0;j<book->dim;)
461        a[i++]=t[j++];
462    }
463  }else{
464    int i,j;
465
466    for(i=0;i<n;){
467      for (j=0;j<book->dim;)
468        a[i++]=0.f;
469    }
470  }
471  return(0);
472}
473
474long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
475                              oggpack_buffer *b,int n){
476
477  long i,j,entry;
478  int chptr=0;
479  if(book->used_entries>0){
480    for(i=offset/ch;i<(offset+n)/ch;){
481      entry = decode_packed_entry_number(book,b);
482      if(entry==-1)return(-1);
483      {
484        const float *t = book->valuelist+entry*book->dim;
485        for (j=0;j<book->dim;j++){
486          a[chptr++][i]+=t[j];
487          if(chptr==ch){
488            chptr=0;
489            i++;
490          }
491        }
492      }
493    }
494  }
495  return(0);
496}
497
498#ifdef _V_SELFTEST
499/* Simple enough; pack a few candidate codebooks, unpack them.  Code a
500   number of vectors through (keeping track of the quantized values),
501   and decode using the unpacked book.  quantized version of in should
502   exactly equal out */
503
504#include <stdio.h>
505
506#include "vorbis/book/lsp20_0.vqh"
507#include "vorbis/book/res0a_13.vqh"
508#define TESTSIZE 40
509
510float test1[TESTSIZE]={
511  0.105939f,
512  0.215373f,
513  0.429117f,
514  0.587974f,
515
516  0.181173f,
517  0.296583f,
518  0.515707f,
519  0.715261f,
520
521  0.162327f,
522  0.263834f,
523  0.342876f,
524  0.406025f,
525
526  0.103571f,
527  0.223561f,
528  0.368513f,
529  0.540313f,
530
531  0.136672f,
532  0.395882f,
533  0.587183f,
534  0.652476f,
535
536  0.114338f,
537  0.417300f,
538  0.525486f,
539  0.698679f,
540
541  0.147492f,
542  0.324481f,
543  0.643089f,
544  0.757582f,
545
546  0.139556f,
547  0.215795f,
548  0.324559f,
549  0.399387f,
550
551  0.120236f,
552  0.267420f,
553  0.446940f,
554  0.608760f,
555
556  0.115587f,
557  0.287234f,
558  0.571081f,
559  0.708603f,
560};
561
562float test3[TESTSIZE]={
563  0,1,-2,3,4,-5,6,7,8,9,
564  8,-2,7,-1,4,6,8,3,1,-9,
565  10,11,12,13,14,15,26,17,18,19,
566  30,-25,-30,-1,-5,-32,4,3,-2,0};
567
568static_codebook *testlist[]={&_vq_book_lsp20_0,
569                             &_vq_book_res0a_13,NULL};
570float   *testvec[]={test1,test3};
571
572int main(){
573  oggpack_buffer write;
574  oggpack_buffer read;
575  long ptr=0,i;
576  oggpack_writeinit(&write);
577
578  fprintf(stderr,"Testing codebook abstraction...:\n");
579
580  while(testlist[ptr]){
581    codebook c;
582    static_codebook s;
583    float *qv=alloca(sizeof(*qv)*TESTSIZE);
584    float *iv=alloca(sizeof(*iv)*TESTSIZE);
585    memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
586    memset(iv,0,sizeof(*iv)*TESTSIZE);
587
588    fprintf(stderr,"\tpacking/coding %ld... ",ptr);
589
590    /* pack the codebook, write the testvector */
591    oggpack_reset(&write);
592    vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
593                                                  we can write */
594    vorbis_staticbook_pack(testlist[ptr],&write);
595    fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
596    for(i=0;i<TESTSIZE;i+=c.dim){
597      int best=_best(&c,qv+i,1);
598      vorbis_book_encodev(&c,best,qv+i,&write);
599    }
600    vorbis_book_clear(&c);
601
602    fprintf(stderr,"OK.\n");
603    fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
604
605    /* transfer the write data to a read buffer and unpack/read */
606    oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
607    if(vorbis_staticbook_unpack(&read,&s)){
608      fprintf(stderr,"Error unpacking codebook.\n");
609      exit(1);
610    }
611    if(vorbis_book_init_decode(&c,&s)){
612      fprintf(stderr,"Error initializing codebook.\n");
613      exit(1);
614    }
615
616    for(i=0;i<TESTSIZE;i+=c.dim)
617      if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
618        fprintf(stderr,"Error reading codebook test data (EOP).\n");
619        exit(1);
620      }
621    for(i=0;i<TESTSIZE;i++)
622      if(fabs(qv[i]-iv[i])>.000001){
623        fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
624                iv[i],qv[i],i);
625        exit(1);
626      }
627
628    fprintf(stderr,"OK\n");
629    ptr++;
630  }
631
632  /* The above is the trivial stuff; now try unquantizing a log scale codebook */
633
634  exit(0);
635}
636
637#endif
638