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.20 2000/12/21 21:04:39 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       default: /* NOT_REACHABLE */
 131         quantvals=-1;
 132       }
 133
 134       /* quantized values */
 135       for(i=0;i<quantvals;i++)
 136         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
 137
 138     }
 139     break;
 140   default:
 141     /* error case; we don't have any other map types now */
 142     return(-1);
 143   }
 144
 145   return(0);
 146 }
 147
 148 /* unpacks a codebook from the packet buffer into the codebook struct,
 149    readies the codebook auxiliary structures for decode *************/
 150 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
 151   long i,j;
 152   memset(s,0,sizeof(static_codebook));
 153   s->allocedp=1;
 154
 155   /* make sure alignment is correct */
 156   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
 157
 158   /* first the basic parameters */
 159   s->dim=oggpack_read(opb,16);
 160   s->entries=oggpack_read(opb,24);
 161   if(s->entries==-1)goto _eofout;
 162
 163   /* codeword ordering.... length ordered or unordered? */
 164   switch(oggpack_read(opb,1)){
 165   case 0:
 166     /* unordered */
 167     s->lengthlist=_ogg_malloc(sizeof(long)*s->entries);
 168
 169     /* allocated but unused entries? */
 170     if(oggpack_read(opb,1)){
 171       /* yes, unused entries */
 172
 173       for(i=0;i<s->entries;i++){
 174         if(oggpack_read(opb,1)){
 175           long num=oggpack_read(opb,5);
 176           if(num==-1)goto _eofout;
 177           s->lengthlist[i]=num+1;
 178         }else
 179           s->lengthlist[i]=0;
 180       }
 181     }else{
 182       /* all entries used; no tagging */
 183       for(i=0;i<s->entries;i++){
 184         long num=oggpack_read(opb,5);
 185         if(num==-1)goto _eofout;
 186         s->lengthlist[i]=num+1;
 187       }
 188     }
 189
 190     break;
 191   case 1:
 192     /* ordered */
 193     {
 194       long length=oggpack_read(opb,5)+1;
 195       s->lengthlist=_ogg_malloc(sizeof(long)*s->entries);
 196
 197       for(i=0;i<s->entries;){
 198         long num=oggpack_read(opb,_ilog(s->entries-i));
 199         if(num==-1)goto _eofout;
 200         for(j=0;j<num;j++,i++)
 201           s->lengthlist[i]=length;
 202         length++;
 203       }
 204     }
 205     break;
 206   default:
 207     /* EOF */
 208     return(-1);
 209   }
 210
 211   /* Do we have a mapping to unpack? */
 212   switch((s->maptype=oggpack_read(opb,4))){
 213   case 0:
 214     /* no mapping */
 215     break;
 216   case 1: case 2:
 217     /* implicitly populated value mapping */
 218     /* explicitly populated value mapping */
 219
 220     s->q_min=oggpack_read(opb,32);
 221     s->q_delta=oggpack_read(opb,32);
 222     s->q_quant=oggpack_read(opb,4)+1;
 223     s->q_sequencep=oggpack_read(opb,1);
 224
 225     {
 226       int quantvals;
 227       switch(s->maptype){
 228       case 1:
 229         quantvals=_book_maptype1_quantvals(s);
 230         break;
 231       case 2:
 232         quantvals=s->entries*s->dim;
 233         break;
 234       }
 235
 236       /* quantized values */
 237       s->quantlist=_ogg_malloc(sizeof(float)*quantvals);
 238       for(i=0;i<quantvals;i++)
 239         s->quantlist[i]=oggpack_read(opb,s->q_quant);
 240
 241       if(s->quantlist[quantvals-1]==-1)goto _eofout;
 242     }
 243     break;
 244   default:
 245     goto _errout;
 246   }
 247
 248   /* all set */
 249   return(0);
 250
 251  _errout:
 252  _eofout:
 253   vorbis_staticbook_clear(s);
 254   return(-1);
 255 }
 256
 257 /* returns the number of bits ************************************************/
 258 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
 259   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
 260   return(book->c->lengthlist[a]);
 261 }
 262
 263 /* One the encode side, our vector writers are each designed for a
 264 specific purpose, and the encoder is not flexible without modification:
 265
 266 The LSP vector coder uses a single stage nearest-match with no
 267 interleave, so no step and no error return.  This is specced by floor0
 268 and doesn't change.
 269
 270 Residue0 encoding interleaves, uses multiple stages, and each stage
 271 peels of a specific amount of resolution from a lattice (thus we want
 272 to match by threshold, not nearest match).  Residue doesn't *have* to
 273 be encoded that way, but to change it, one will need to add more
 274 infrastructure on the encode side (decode side is specced and simpler) */
 275
 276 /* floor0 LSP (single stage, non interleaved, nearest match) */
 277 /* returns entry number and *modifies a* to the quantization value *****/
 278 int vorbis_book_errorv(codebook *book,float *a){
 279   int dim=book->dim,k;
 280   int best=_best(book,a,1);
 281   for(k=0;k<dim;k++)
 282     a[k]=(book->valuelist+best*dim)[k];
 283   return(best);
 284 }
 285
 286 /* returns the number of bits and *modifies a* to the quantization value *****/
 287 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
 288   int k,dim=book->dim;
 289   for(k=0;k<dim;k++)
 290     a[k]=(book->valuelist+best*dim)[k];
 291   return(vorbis_book_encode(book,best,b));
 292 }
 293
 294 /* res0 (multistage, interleave, lattice) */
 295 /* returns the number of bits and *modifies a* to the remainder value ********/
 296 int vorbis_book_encodevs(codebook *book,float *a,oggpack_buffer *b,
 297                          int step,int addmul){
 298
 299   int best=vorbis_book_besterror(book,a,step,addmul);
 300   return(vorbis_book_encode(book,best,b));
 301 }
 302
 303 /* Decode side is specced and easier, because we don't need to find
 304    matches using different criteria; we simply read and map.  There are
 305    two things we need to do 'depending':
 306
 307    We may need to support interleave.  We don't really, but it's
 308    convenient to do it here rather than rebuild the vector later.
 309
 310    Cascades may be additive or multiplicitive; this is not inherent in
 311    the codebook, but set in the code using the codebook.  Like
 312    interleaving, it's easiest to do it here.
 313    addmul==0 -> declarative (set the value)
 314    addmul==1 -> additive
 315    addmul==2 -> multiplicitive */
 316
 317 /* returns the entry number or -1 on eof *************************************/
 318 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
 319   long ptr=0;
 320   decode_aux *t=book->decode_tree;
 321   int lok = oggpack_look(b, t->tabn);
 322
 323   if (lok >= 0) {
 324     ptr = t->tab[lok];
 325     oggpack_adv(b, t->tabl[lok]);
 326     if (ptr <= 0)
 327       return -ptr;
 328   }
 329
 330   do{
 331     switch(oggpack_read1(b)){
 332     case 0:
 333       ptr=t->ptr0[ptr];
 334       break;
 335     case 1:
 336       ptr=t->ptr1[ptr];
 337       break;
 338     case -1:
 339       return(-1);
 340     }
 341   }while(ptr>0);
 342   return(-ptr);
 343 }
 344
 345 /* returns the entry number or -1 on eof *************************************/
 346 long vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 347                           int step,int addmul){
 348   long entry=vorbis_book_decode(book,b);
 349   int i,o;
 350   float *t;
 351   if(entry==-1)return(-1);
 352   t = book->valuelist+entry*book->dim;
 353   switch(addmul){
 354   case -1:
 355     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 356       a[o]=t[i];
 357       a[o+step]=t[i+1];
 358       a[o+2*step]=t[i+2];
 359       a[o+3*step]=t[i+3];
 360     }
 361     for(;i<book->dim;i++,o+=step)
 362       a[o]=t[i];
 363     break;
 364   case 0:
 365     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 366       a[o]+=t[i];
 367       a[o+step]+=t[i+1];
 368       a[o+2*step]+=t[i+2];
 369       a[o+3*step]+=t[i+3];
 370     }
 371     for(;i<book->dim;i++,o+=step)
 372       a[o]+=t[i];
 373     break;
 374   case 1:
 375     for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
 376       a[o]*=t[i];
 377       a[o+step]*=t[i+1];
 378       a[o+2*step]*=t[i+2];
 379       a[o+3*step]*=t[i+3];
 380     }
 381     for(;i<book->dim;i++,o+=step)
 382       a[o]*=t[i];
 383     break;
 384   }
 385   return(entry);
 386 }
 387
 388 /* returns 0 on OK or -1 on eof *************************************/
 389 long s_vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
 390                          int step,int addmul){
 391   long *entry = alloca(sizeof(long)*step);
 392   float **t = alloca(sizeof(float *)*step);
 393   int i,j,o;
 394
 395   for (i = 0; i < step; i++) {
 396     entry[i]=vorbis_book_decode(book,b);
 397     if(entry[i]==-1)return(-1);
 398     t[i] = book->valuelist+entry[i]*book->dim;
 399   }
 400   switch(addmul){
 401   case -1:
 402     for(i=0,o=0;i<book->dim;i++,o+=step)
 403       for (j=0;j<step;j++)
 404        a[o+j]=t[j][i];
 405     break;
 406   case 0:
 407     for(i=0,o=0;i<book->dim;i++,o+=step)
 408       for (j=0;j<step;j++)
 409        a[o+j]+=t[j][i];
 410     break;
 411   case 1:
 412     for(i=0,o=0;i<book->dim;i++,o+=step)
 413       for (j=0;j<step;j++)
 414        a[o+j]*=t[j][i];
 415     break;
 416   }
 417   return(0);
 418 }
 419
 420 #ifdef _V_SELFTEST
 421
 422 /* Simple enough; pack a few candidate codebooks, unpack them.  Code a
 423    number of vectors through (keeping track of the quantized values),
 424    and decode using the unpacked book.  quantized version of in should
 425    exactly equal out */
 426
 427 #include <stdio.h>
 428
 429 #include "vorbis/book/lsp20_0.vqh"
 430 #include "vorbis/book/res0a_13.vqh"
 431 #define TESTSIZE 40
 432
 433 float test1[TESTSIZE]={
 434   0.105939f,
 435   0.215373f,
 436   0.429117f,
 437   0.587974f,
 438
 439   0.181173f,
 440   0.296583f,
 441   0.515707f,
 442   0.715261f,
 443
 444   0.162327f,
 445   0.263834f,
 446   0.342876f,
 447   0.406025f,
 448
 449   0.103571f,
 450   0.223561f,
 451   0.368513f,
 452   0.540313f,
 453
 454   0.136672f,
 455   0.395882f,
 456   0.587183f,
 457   0.652476f,
 458
 459   0.114338f,
 460   0.417300f,
 461   0.525486f,
 462   0.698679f,
 463
 464   0.147492f,
 465   0.324481f,
 466   0.643089f,
 467   0.757582f,
 468
 469   0.139556f,
 470   0.215795f,
 471   0.324559f,
 472   0.399387f,
 473
 474   0.120236f,
 475   0.267420f,
 476   0.446940f,
 477   0.608760f,
 478
 479   0.115587f,
 480   0.287234f,
 481   0.571081f,
 482   0.708603f,
 483 };
 484
 485 float test3[TESTSIZE]={
 486   0,1,-2,3,4,-5,6,7,8,9,
 487   8,-2,7,-1,4,6,8,3,1,-9,
 488   10,11,12,13,14,15,26,17,18,19,
 489   30,-25,-30,-1,-5,-32,4,3,-2,0};
 490
 491 static_codebook *testlist[]={&_vq_book_lsp20_0,
 492                              &_vq_book_res0a_13,NULL};
 493 float   *testvec[]={test1,test3};
 494
 495 int main(){
 496   oggpack_buffer write;
 497   oggpack_buffer read;
 498   long ptr=0,i;
 499   oggpack_writeinit(&write);
 500
 501   fprintf(stderr,"Testing codebook abstraction...:\n");
 502
 503   while(testlist[ptr]){
 504     codebook c;
 505     static_codebook s;
 506     float *qv=alloca(sizeof(float)*TESTSIZE);
 507     float *iv=alloca(sizeof(float)*TESTSIZE);
 508     memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
 509     memset(iv,0,sizeof(float)*TESTSIZE);
 510
 511     fprintf(stderr,"\tpacking/coding %ld... ",ptr);
 512
 513     /* pack the codebook, write the testvector */
 514     oggpack_reset(&write);
 515     vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
 516                                                   we can write */
 517     vorbis_staticbook_pack(testlist[ptr],&write);
 518     fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
 519     for(i=0;i<TESTSIZE;i+=c.dim){
 520       int best=_best(&c,qv+i,1);
 521       vorbis_book_encodev(&c,best,qv+i,&write);
 522     }
 523     vorbis_book_clear(&c);
 524
 525     fprintf(stderr,"OK.\n");
 526     fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
 527
 528     /* transfer the write data to a read buffer and unpack/read */
 529     oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
 530     if(vorbis_staticbook_unpack(&read,&s)){
 531       fprintf(stderr,"Error unpacking codebook.\n");
 532       exit(1);
 533     }
 534     if(vorbis_book_init_decode(&c,&s)){
 535       fprintf(stderr,"Error initializing codebook.\n");
 536       exit(1);
 537     }
 538
 539     for(i=0;i<TESTSIZE;i+=c.dim)
 540       if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 541         fprintf(stderr,"Error reading codebook test data (EOP).\n");
 542         exit(1);
 543       }
 544     for(i=0;i<TESTSIZE;i++)
 545       if(fabs(qv[i]-iv[i])>.000001){
 546         fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
 547                 iv[i],qv[i],i);
 548         exit(1);
 549       }
 550
 551     fprintf(stderr,"OK\n");
 552     ptr++;
 553   }
 554
 555   /* The above is the trivial stuff; now try unquantizing a log scale codebook */
 556
 557   exit(0);
 558 }
 559
 560 #endif