lib/codebook.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
   5  * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH    *
   6  * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.        *
   7  *                                                                  *
   8  * THE OggVorbis 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.19 2000/11/06 00:07:00 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <math.h>
  22 #include <ogg/ogg.h>
  23 #include "vorbis/codec.h"
  24 #include "codebook.h"
  25 #include "scales.h"
  26 #include "misc.h"
  27 #include "os.h"
  28
  29 /* packs the given codebook into the bitstream **************************/
  30
  31 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
  32   long i,j;
  33   int ordered=0;
  34
  35   /* first the basic parameters */
  36   oggpack_write(opb,0x564342,24);
  37   oggpack_write(opb,c->dim,16);
  38   oggpack_write(opb,c->entries,24);
  39
  40   /* pack the codewords.  There are two packings; length ordered and
  41      length random.  Decide between the two now. */
  42
  43   for(i=1;i<c->entries;i++)
  44     if(c->lengthlist[i]<c->lengthlist[i-1])break;
  45   if(i==c->entries)ordered=1;
  46
  47   if(ordered){
  48     /* length ordered.  We only need to say how many codewords of
  49        each length.  The actual codewords are generated
  50        deterministically */
  51
  52     long count=0;
  53     oggpack_write(opb,1,1);  /* ordered */
  54     oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
  55
  56     for(i=1;i<c->entries;i++){
  57       long this=c->lengthlist[i];
  58       long last=c->lengthlist[i-1];
  59       if(this>last){
  60         for(j=last;j<this;j++){
  61           oggpack_write(opb,i-count,_ilog(c->entries-count));
  62           count=i;
  63         }
  64       }
  65     }
  66     oggpack_write(opb,i-count,_ilog(c->entries-count));
  67
  68   }else{
  69     /* length random.  Again, we don't code the codeword itself, just
  70        the length.  This time, though, we have to encode each length */
  71     oggpack_write(opb,0,1);   /* unordered */
  72
  73     /* algortihmic mapping has use for 'unused entries', which we tag
  74        here.  The algorithmic mapping happens as usual, but the unused
  75        entry has no codeword. */
  76     for(i=0;i<c->entries;i++)
  77       if(c->lengthlist[i]==0)break;
  78
  79     if(i==c->entries){
  80       oggpack_write(opb,0,1); /* no unused entries */
  81       for(i=0;i<c->entries;i++)
  82         oggpack_write(opb,c->lengthlist[i]-1,5);
  83     }else{
  84       oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
  85       for(i=0;i<c->entries;i++){
  86         if(c->lengthlist[i]==0){
  87           oggpack_write(opb,0,1);
  88         }else{
  89           oggpack_write(opb,1,1);
  90           oggpack_write(opb,c->lengthlist[i]-1,5);
  91         }
  92       }
  93     }
  94   }
  95
  96   /* is the entry number the desired return value, or do we have a
  97      mapping? If we have a mapping, what type? */
  98   oggpack_write(opb,c->maptype,4);
  99   switch(c->maptype){
 100   case 0:
 101     /* no mapping */
 102     break;
 103   case 1:case 2:
 104     /* implicitly populated value mapping */
 105     /* explicitly populated value mapping */
 106
 107     if(!c->quantlist){
 108       /* no quantlist?  error */
 109       return(-1);
 110     }
 111
 112     /* values that define the dequantization */
 113     oggpack_write(opb,c->q_min,32);
 114     oggpack_write(opb,c->q_delta,32);
 115     oggpack_write(opb,c->q_quant-1,4);
 116     oggpack_write(opb,c->q_sequencep,1);
 117
 118     {
 119       int quantvals;
 120       switch(c->maptype){
 121       case 1:
 122         /* a single column of (c->entries/c->dim) quantized values for
 123            building a full value list algorithmically (square lattice) */
 124         quantvals=_book_maptype1_quantvals(c);
 125         break;
 126       case 2:
 127         /* every value (c->entries*c->dim total) specified explicitly */
 128         quantvals=c->entries*c->dim;
 129         break;
 130       }
 131
 132       /* quantized values */
 133       for(i=0;i<quantvals;i++)
 134         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
 135
 136     }
 137     break;
 138   default:
 139     /* error case; we don't have any other map types now */
 140     return(-1);
 141   }
 142
 143   return(0);
 144 }
 145
 146 /* unpacks a codebook from the packet buffer into the codebook struct,
 147    readies the codebook auxiliary structures for decode *************/
 148 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
 149   long i,j;
 150   memset(s,0,sizeof(static_codebook));
 151   s->allocedp=1;
 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=_ogg_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=_ogg_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=_ogg_malloc(sizeof(float)*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 threshold, 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,float *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,float *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,float *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    addmul==0 -> declarative (set the value)
 312    addmul==1 -> additive
 313    addmul==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   int lok = oggpack_look(b, t->tabn);
 320
 321   if (lok >= 0) {
 322     ptr = t->tab[lok];
 323     oggpack_adv(b, t->tabl[lok]);
 324     if (ptr <= 0)
 325       return -ptr;
 326   }
 327
 328   do{
 329     switch(oggpack_read1(b)){
 330     case 0:
 331       ptr=t->ptr0[ptr];
 332       break;
 333     case 1:
 334       ptr=t->ptr1[ptr];
 335       break;
 336     case -1:
 337       return(-1);
 338     }
 339   }while(ptr>0);
 340   return(-ptr);
 341 }
 342
 343 /* returns the entry number or -1 on eof *************************************/
 344 long vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 345                           int step,int addmul){
 346   long entry=vorbis_book_decode(book,b);
 347   int i,o;
 348   float *t;
 349   if(entry==-1)return(-1);
 350   t = book->valuelist+entry*book->dim;
 351   switch(addmul){
 352   case -1:
 353     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 354       a[o]=t[i];
 355       a[o+step]=t[i+1];
 356       a[o+2*step]=t[i+2];
 357       a[o+3*step]=t[i+3];
 358     }
 359     for(;i<book->dim;i++,o+=step)
 360       a[o]=t[i];
 361     break;
 362   case 0:
 363     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 364       a[o]+=t[i];
 365       a[o+step]+=t[i+1];
 366       a[o+2*step]+=t[i+2];
 367       a[o+3*step]+=t[i+3];
 368     }
 369     for(;i<book->dim;i++,o+=step)
 370       a[o]+=t[i];
 371     break;
 372   case 1:
 373     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 374       a[o]*=t[i];
 375       a[o+step]*=t[i+1];
 376       a[o+2*step]*=t[i+2];
 377       a[o+3*step]*=t[i+3];
 378     }
 379     for(;i<book->dim;i++,o+=step)
 380       a[o]*=t[i];
 381     break;
 382   }
 383   return(entry);
 384 }
 385
 386 /* returns 0 on OK or -1 on eof *************************************/
 387 long s_vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 388                          int step,int addmul){
 389   long *entry = alloca(sizeof(long)*step);
 390   float **t = alloca(sizeof(float *)*step);
 391   int i,j,o;
 392
 393   for (i = 0; i < step; i++) {
 394     entry[i]=vorbis_book_decode(book,b);
 395     if(entry[i]==-1)return(-1);
 396     t[i] = book->valuelist+entry[i]*book->dim;
 397   }
 398   switch(addmul){
 399   case -1:
 400     for(i=0,o=0;i<book->dim;i++,o+=step)
 401       for (j=0;j<step;j++)
 402        a[o+j]=t[j][i];
 403     break;
 404   case 0:
 405     for(i=0,o=0;i<book->dim;i++,o+=step)
 406       for (j=0;j<step;j++)
 407        a[o+j]+=t[j][i];
 408     break;
 409   case 1:
 410     for(i=0,o=0;i<book->dim;i++,o+=step)
 411       for (j=0;j<step;j++)
 412        a[o+j]*=t[j][i];
 413     break;
 414   }
 415   return(0);
 416 }
 417
 418 #ifdef _V_SELFTEST
 419
 420 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 421    number of vectors through (keeping track of the quantized values),
 422    and decode using the unpacked book.  quantized version of in should
 423    exactly equal out */
 424
 425 #include <stdio.h>
 426
 427 #include "vorbis/book/lsp20_0.vqh"
 428 #include "vorbis/book/res0a_13.vqh"
 429 #define TESTSIZE 40
 430
 431 float test1[TESTSIZE]={
 432   0.105939,
 433   0.215373,
 434   0.429117,
 435   0.587974,
 436
 437   0.181173,
 438   0.296583,
 439   0.515707,
 440   0.715261,
 441
 442   0.162327,
 443   0.263834,
 444   0.342876,
 445   0.406025,
 446
 447   0.103571,
 448   0.223561,
 449   0.368513,
 450   0.540313,
 451
 452   0.136672,
 453   0.395882,
 454   0.587183,
 455   0.652476,
 456
 457   0.114338,
 458   0.417300,
 459   0.525486,
 460   0.698679,
 461
 462   0.147492,
 463   0.324481,
 464   0.643089,
 465   0.757582,
 466
 467   0.139556,
 468   0.215795,
 469   0.324559,
 470   0.399387,
 471
 472   0.120236,
 473   0.267420,
 474   0.446940,
 475   0.608760,
 476
 477   0.115587,
 478   0.287234,
 479   0.571081,
 480   0.708603,
 481 };
 482
 483 float test3[TESTSIZE]={
 484   0,1,-2,3,4,-5,6,7,8,9,
 485   8,-2,7,-1,4,6,8,3,1,-9,
 486   10,11,12,13,14,15,26,17,18,19,
 487   30,-25,-30,-1,-5,-32,4,3,-2,0};
 488
 489 static_codebook *testlist[]={&_vq_book_lsp20_0,
 490                              &_vq_book_res0a_13,NULL};
 491 float   *testvec[]={test1,test3};
 492
 493 int main(){
 494   oggpack_buffer write;
 495   oggpack_buffer read;
 496   long ptr=0,i;
 497   oggpack_writeinit(&write);
 498
 499   fprintf(stderr,"Testing codebook abstraction...:\n");
 500
 501   while(testlist[ptr]){
 502     codebook c;
 503     static_codebook s;
 504     float *qv=alloca(sizeof(float)*TESTSIZE);
 505     float *iv=alloca(sizeof(float)*TESTSIZE);
 506     memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
 507     memset(iv,0,sizeof(float)*TESTSIZE);
 508
 509     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 510
 511     /* pack the codebook, write the testvector */
 512     oggpack_reset(&write);
 513     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 514                                                   we can write */
 515     vorbis_staticbook_pack(testlist[ptr],&write);
 516     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
 517     for(i=0;i<TESTSIZE;i+=c.dim){
 518       int best=_best(&c,qv+i,1);
 519       vorbis_book_encodev(&c,best,qv+i,&write);
 520     }
 521     vorbis_book_clear(&c);
 522
 523     fprintf(stderr,"OK.\n");
 524     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 525
 526     /* transfer the write data to a read buffer and unpack/read */
 527     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
 528     if(vorbis_staticbook_unpack(&read,&s)){
 529       fprintf(stderr,"Error unpacking codebook.\n");
 530       exit(1);
 531     }
 532     if(vorbis_book_init_decode(&c,&s)){
 533       fprintf(stderr,"Error initializing codebook.\n");
 534       exit(1);
 535     }
 536
 537     for(i=0;i<TESTSIZE;i+=c.dim)
 538       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 539         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 540         exit(1);
 541       }
 542     for(i=0;i<TESTSIZE;i++)
 543       if(fabs(qv[i]-iv[i])>.000001){
 544         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 545                 iv[i],qv[i],i);
 546         exit(1);
 547       }
 548
 549     fprintf(stderr,"OK\n");
 550     ptr++;
 551   }
 552
 553   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 554
 555   exit(0);
 556 }
 557
 558 #endif