jorbis/src/com/jcraft/jorbis/CodeBook.java

   1 /* JOrbis
   2  * Copyright (C) 2000 ymnk, JCraft,Inc.
   3  *
   4  * Written by: 2000 ymnk<ymnk@jcraft.com>
   5  *
   6  * Many thanks to
   7  *   Monty <monty@xiph.org> and
   8  *   The XIPHOPHORUS Company http://www.xiph.org/ .
   9  * JOrbis has been based on their awesome works, Vorbis codec.
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Library General Public License
  13  * as published by the Free Software Foundation; either version 2 of
  14  * the License, or (at your option) any later version.
  15
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU Library General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Library General Public
  22  * License along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24  */
  25
  26 package com.jcraft.jorbis;
  27
  28 import com.jcraft.jogg.*;
  29
  30 class CodeBook{
  31   int dim;            // codebook dimensions (elements per vector)
  32   int entries;        // codebook entries
  33   StaticCodeBook c=new StaticCodeBook();
  34
  35   float[] valuelist; // list of dim*entries actual entry values
  36   int[] codelist;     // list of bitstream codewords for each entry
  37   DecodeAux decode_tree;
  38
  39   // returns the number of bits
  40   int encode(int a, Buffer b){
  41     b.write(codelist[a], c.lengthlist[a]);
  42     return(c.lengthlist[a]);
  43   }
  44
  45   // One the encode side, our vector writers are each designed for a
  46   // specific purpose, and the encoder is not flexible without modification:
  47   //
  48   // The LSP vector coder uses a single stage nearest-match with no
  49   // interleave, so no step and no error return.  This is specced by floor0
  50   // and doesn't change.
  51   //
  52   // Residue0 encoding interleaves, uses multiple stages, and each stage
  53   // peels of a specific amount of resolution from a lattice (thus we want
  54   // to match by threshhold, not nearest match).  Residue doesn't *have* to
  55   // be encoded that way, but to change it, one will need to add more
  56   // infrastructure on the encode side (decode side is specced and simpler)
  57
  58   // floor0 LSP (single stage, non interleaved, nearest match)
  59   // returns entry number and *modifies a* to the quantization value
  60   int errorv(float[] a){
  61     int best=best(a,1);
  62     for(int k=0;k<dim;k++){
  63       a[k]=valuelist[best*dim+k];
  64     }
  65     return(best);
  66   }
  67
  68   // returns the number of bits and *modifies a* to the quantization value
  69   int encodev(int best, float[] a, Buffer b){
  70     for(int k=0;k<dim;k++){
  71       a[k]=valuelist[best*dim+k];
  72     }
  73     return(encode(best,b));
  74   }
  75
  76   // res0 (multistage, interleave, lattice)
  77   // returns the number of bits and *modifies a* to the remainder value
  78   int encodevs(float[] a, Buffer b, int step,int addmul){
  79     int best=besterror(a,step,addmul);
  80     return(encode(best,b));
  81   }
  82
  83   private int[] t=new int[15];  // decodevs_add is synchronized for re-using t.
  84   synchronized int decodevs_add(float[]a, int offset, Buffer b, int n){
  85     int step=n/dim;
  86     int entry;
  87     int i,j,o;
  88
  89     if(t.length<step){
  90       t=new int[step];
  91     }
  92
  93     for(i = 0; i < step; i++){
  94       entry=decode(b);
  95       if(entry==-1)return(-1);
  96       t[i]=entry*dim;
  97     }
  98     for(i=0,o=0;i<dim;i++,o+=step){
  99       for(j=0;j<step;j++){
 100         a[offset+o+j]+=valuelist[t[j]+i];
 101       }
 102     }
 103
 104     return(0);
 105   }
 106
 107   int decodev_add(float[]a, int offset, Buffer b,int n){
 108     int i,j,entry;
 109     int t;
 110
 111     if(dim>8){
 112       for(i=0;i<n;){
 113         entry = decode(b);
 114         if(entry==-1)return(-1);
 115         t=entry*dim;
 116         for(j=0;j<dim;){
 117           a[offset+(i++)]+=valuelist[t+(j++)];
 118         }
 119       }
 120     }
 121     else{
 122       for(i=0;i<n;){
 123         entry=decode(b);
 124         if(entry==-1)return(-1);
 125         t=entry*dim;
 126         j=0;
 127         switch(dim){
 128         case 8:
 129           a[offset+(i++)]+=valuelist[t+(j++)];
 130         case 7:
 131           a[offset+(i++)]+=valuelist[t+(j++)];
 132         case 6:
 133           a[offset+(i++)]+=valuelist[t+(j++)];
 134         case 5:
 135           a[offset+(i++)]+=valuelist[t+(j++)];
 136         case 4:
 137           a[offset+(i++)]+=valuelist[t+(j++)];
 138         case 3:
 139           a[offset+(i++)]+=valuelist[t+(j++)];
 140         case 2:
 141           a[offset+(i++)]+=valuelist[t+(j++)];
 142         case 1:
 143           a[offset+(i++)]+=valuelist[t+(j++)];
 144         case 0:
 145         break;
 146         }
 147       }
 148     }
 149     return(0);
 150   }
 151
 152   int decodev_set(float[] a,int offset, Buffer b, int n){
 153     int i,j,entry;
 154     int t;
 155
 156     for(i=0;i<n;){
 157       entry = decode(b);
 158       if(entry==-1)return(-1);
 159       t=entry*dim;
 160       for(j=0;j<dim;){
 161         a[offset+i++]=valuelist[t+(j++)];
 162       }
 163     }
 164     return(0);
 165   }
 166
 167   int decodevv_add(float[][] a, int offset,int ch, Buffer b,int n){
 168     int i,j,k,entry;
 169     int chptr=0;
 170     //System.out.println("decodevv_add: a="+a+",b="+b+",valuelist="+valuelist);
 171
 172     for(i=offset/ch;i<(offset+n)/ch;){
 173       entry = decode(b);
 174       if(entry==-1)return(-1);
 175
 176       int t = entry*dim;
 177       for(j=0;j<dim;j++){
 178         a[chptr++][i]+=valuelist[t+j];
 179         if(chptr==ch){
 180           chptr=0;
 181           i++;
 182         }
 183       }
 184     }
 185     return(0);
 186   }
 187
 188
 189   // Decode side is specced and easier, because we don't need to find
 190   // matches using different criteria; we simply read and map.  There are
 191   // two things we need to do 'depending':
 192   //
 193   // We may need to support interleave.  We don't really, but it's
 194   // convenient to do it here rather than rebuild the vector later.
 195   //
 196   // Cascades may be additive or multiplicitive; this is not inherent in
 197   // the codebook, but set in the code using the codebook.  Like
 198   // interleaving, it's easiest to do it here.
 199   // stage==0 -> declarative (set the value)
 200   // stage==1 -> additive
 201   // stage==2 -> multiplicitive
 202
 203   // returns the entry number or -1 on eof
 204   int decode(Buffer b){
 205     int ptr=0;
 206     DecodeAux t=decode_tree;
 207     int lok=b.look(t.tabn);
 208     //System.err.println(this+" "+t+" lok="+lok+", tabn="+t.tabn);
 209
 210     if(lok>=0){
 211       ptr=t.tab[lok];
 212       b.adv(t.tabl[lok]);
 213       if(ptr<=0){
 214         return -ptr;
 215       }
 216     }
 217     do{
 218       switch(b.read1()){
 219       case 0:
 220         ptr=t.ptr0[ptr];
 221         break;
 222       case 1:
 223         ptr=t.ptr1[ptr];
 224         break;
 225       case -1:
 226       default:
 227         return(-1);
 228       }
 229     }
 230     while(ptr>0);
 231     return(-ptr);
 232   }
 233
 234   // returns the entry number or -1 on eof
 235   int decodevs(float[] a, int index, Buffer b, int step,int addmul){
 236     int entry=decode(b);
 237     if(entry==-1)return(-1);
 238     switch(addmul){
 239     case -1:
 240       for(int i=0,o=0;i<dim;i++,o+=step)
 241         a[index+o]=valuelist[entry*dim+i];
 242       break;
 243     case 0:
 244       for(int i=0,o=0;i<dim;i++,o+=step)
 245         a[index+o]+=valuelist[entry*dim+i];
 246       break;
 247     case 1:
 248       for(int i=0,o=0;i<dim;i++,o+=step)
 249         a[index+o]*=valuelist[entry*dim+i];
 250       break;
 251     default:
 252       //System.err.println("CodeBook.decodeves: addmul="+addmul);
 253     }
 254     return(entry);
 255   }
 256
 257   int best(float[] a, int step){
 258     EncodeAuxNearestMatch nt=c.nearest_tree;
 259     EncodeAuxThreshMatch tt=c.thresh_tree;
 260     int ptr=0;
 261
 262     // we assume for now that a thresh tree is the only other possibility
 263     if(tt!=null){
 264       int index=0;
 265       // find the quant val of each scalar
 266       for(int k=0,o=step*(dim-1);k<dim;k++,o-=step){
 267         int i;
 268         // linear search the quant list for now; it's small and although
 269         // with > 8 entries, it would be faster to bisect, this would be
 270         // a misplaced optimization for now
 271         for(i=0;i<tt.threshvals-1;i++){
 272           if(a[o]<tt.quantthresh[i]){
 273             break;
 274           }
 275         }
 276         index=(index*tt.quantvals)+tt.quantmap[i];
 277       }
 278       // regular lattices are easy :-)
 279       if(c.lengthlist[index]>0){
 280         // is this unused?  If so, we'll
 281         // use a decision tree after all
 282         // and fall through
 283         return(index);
 284       }
 285     }
 286     if(nt!=null){
 287       // optimized using the decision tree
 288       while(true){
 289         float c=0.f;
 290         int p=nt.p[ptr];
 291         int q=nt.q[ptr];
 292         for(int k=0,o=0;k<dim;k++,o+=step){
 293           c+=(valuelist[p+k]-valuelist[q+k])*
 294              (a[o]-(valuelist[p+k]+valuelist[q+k])*.5);
 295         }
 296         if(c>0.){ // in A
 297           ptr= -nt.ptr0[ptr];
 298         }
 299         else{     // in B
 300           ptr= -nt.ptr1[ptr];
 301         }
 302         if(ptr<=0)break;
 303       }
 304       return(-ptr);
 305     }
 306
 307     // brute force it!
 308     {
 309       int besti=-1;
 310       float best=0.f;
 311       int e=0;
 312       for(int i=0;i<entries;i++){
 313         if(c.lengthlist[i]>0){
 314           float _this=dist(dim, valuelist, e, a, step);
 315           if(besti==-1 || _this<best){
 316             best=_this;
 317             besti=i;
 318           }
 319         }
 320         e+=dim;
 321       }
 322       return(besti);
 323     }
 324   }
 325
 326   // returns the entry number and *modifies a* to the remainder value
 327   int besterror(float[] a, int step, int addmul){
 328     int best=best(a,step);
 329     switch(addmul){
 330     case 0:
 331       for(int i=0,o=0;i<dim;i++,o+=step)
 332         a[o]-=valuelist[best*dim+i];
 333       break;
 334     case 1:
 335       for(int i=0,o=0;i<dim;i++,o+=step){
 336         float val=valuelist[best*dim+i];
 337         if(val==0){
 338           a[o]=0;
 339         }else{
 340           a[o]/=val;
 341         }
 342       }
 343       break;
 344     }
 345     return(best);
 346   }
 347
 348   void clear(){
 349     // static book is not cleared; we're likely called on the lookup and
 350     // the static codebook belongs to the info struct
 351     //if(decode_tree!=null){
 352     //  free(b->decode_tree->ptr0);
 353     //  free(b->decode_tree->ptr1);
 354     //  memset(b->decode_tree,0,sizeof(decode_aux));
 355     //  free(b->decode_tree);
 356     //}
 357     //if(valuelist!=null)free(b->valuelist);
 358     //if(codelist!=null)free(b->codelist);
 359     //memset(b,0,sizeof(codebook));
 360   }
 361
 362   private static float dist(int el, float[] ref, int index, float[] b, int step){
 363     float acc=(float)0.;
 364     for(int i=0; i<el; i++){
 365       float val=(ref[index+i]-b[i*step]);
 366       acc+=val*val;
 367     }
 368     return(acc);
 369   }
 370
 371 /*
 372   int init_encode(StaticCodeBook s){
 373     //memset(c,0,sizeof(codebook));
 374     c=s;
 375     entries=s.entries;
 376     dim=s.dim;
 377     codelist=make_words(s.lengthlist, s.entries);
 378     valuelist=s.unquantize();
 379     return(0);
 380   }
 381 */
 382
 383   int init_decode(StaticCodeBook s){
 384     //memset(c,0,sizeof(codebook));
 385     c=s;
 386     entries=s.entries;
 387     dim=s.dim;
 388     valuelist=s.unquantize();
 389
 390     decode_tree=make_decode_tree();
 391     if(decode_tree==null){
 392       //goto err_out;
 393       clear();
 394       return(-1);
 395     }
 396     return(0);
 397 //  err_out:
 398 //    vorbis_book_clear(c);
 399 //    return(-1);
 400   }
 401
 402   // given a list of word lengths, generate a list of codewords.  Works
 403   // for length ordered or unordered, always assigns the lowest valued
 404   // codewords first.  Extended to handle unused entries (length 0)
 405   static int[] make_words(int[] l, int n){
 406     int[] marker=new int[33];
 407     int[] r=new int[n];
 408     //memset(marker,0,sizeof(marker));
 409
 410     for(int i=0;i<n;i++){
 411       int length=l[i];
 412       if(length>0){
 413         int entry=marker[length];
 414
 415         // when we claim a node for an entry, we also claim the nodes
 416         // below it (pruning off the imagined tree that may have dangled
 417         // from it) as well as blocking the use of any nodes directly
 418         // above for leaves
 419
 420         // update ourself
 421         if(length<32 && (entry>>>length)!=0){
 422           // error condition; the lengths must specify an overpopulated tree
 423           //free(r);
 424           return(null);
 425         }
 426         r[i]=entry;
 427
 428         // Look to see if the next shorter marker points to the node
 429         // above. if so, update it and repeat.
 430         {
 431           for(int j=length;j>0;j--){
 432             if((marker[j]&1)!=0){
 433               // have to jump branches
 434               if(j==1)marker[1]++;
 435               else marker[j]=marker[j-1]<<1;
 436               break; // invariant says next upper marker would already
 437                      // have been moved if it was on the same path
 438             }
 439             marker[j]++;
 440           }
 441         }
 442
 443         // prune the tree; the implicit invariant says all the longer
 444         // markers were dangling from our just-taken node.  Dangle them
 445         // from our *new* node.
 446         for(int j=length+1;j<33;j++){
 447           if((marker[j]>>>1) == entry){
 448             entry=marker[j];
 449             marker[j]=marker[j-1]<<1;
 450           }
 451           else{
 452             break;
 453           }
 454         }
 455       }
 456     }
 457
 458     // bitreverse the words because our bitwise packer/unpacker is LSb
 459     // endian
 460     for(int i=0;i<n;i++){
 461       int temp=0;
 462       for(int j=0;j<l[i];j++){
 463         temp<<=1;
 464         temp|=(r[i]>>>j)&1;
 465       }
 466       r[i]=temp;
 467     }
 468
 469     return(r);
 470   }
 471
 472   // build the decode helper tree from the codewords
 473   DecodeAux make_decode_tree(){
 474     int top=0;
 475     DecodeAux t=new DecodeAux();
 476     int[] ptr0=t.ptr0=new int[entries*2];
 477     int[] ptr1=t.ptr1=new int[entries*2];
 478     int[] codelist=make_words(c.lengthlist, c.entries);
 479
 480     if(codelist==null)return(null);
 481     t.aux=entries*2;
 482
 483     for(int i=0;i<entries;i++){
 484       if(c.lengthlist[i]>0){
 485         int ptr=0;
 486         int j;
 487         for(j=0;j<c.lengthlist[i]-1;j++){
 488           int bit=(codelist[i]>>>j)&1;
 489           if(bit==0){
 490             if(ptr0[ptr]==0){
 491               ptr0[ptr]=++top;
 492             }
 493             ptr=ptr0[ptr];
 494           }
 495           else{
 496             if(ptr1[ptr]==0){
 497               ptr1[ptr]= ++top;
 498             }
 499             ptr=ptr1[ptr];
 500           }
 501         }
 502
 503         if(((codelist[i]>>>j)&1)==0){ ptr0[ptr]=-i; }
 504         else{ ptr1[ptr]=-i; }
 505
 506       }
 507     }
 508     //free(codelist);
 509
 510     t.tabn = ilog(entries)-4;
 511
 512     if(t.tabn<5)t.tabn=5;
 513     int n = 1<<t.tabn;
 514     t.tab = new int[n];
 515     t.tabl = new int[n];
 516     for(int i = 0; i < n; i++){
 517       int p = 0;
 518       int j=0;
 519       for(j = 0; j < t.tabn && (p > 0 || j == 0); j++){
 520         if ((i&(1<<j))!=0){
 521           p = ptr1[p];
 522         }
 523         else{
 524           p = ptr0[p];
 525         }
 526       }
 527       t.tab[i]=p;  // -code
 528       t.tabl[i]=j; // length
 529     }
 530
 531     return(t);
 532   }
 533
 534   private static int ilog(int v){
 535     int ret=0;
 536     while(v!=0){
 537       ret++;
 538       v>>>=1;
 539     }
 540     return(ret);
 541   }
 542
 543 /*
 544   // TEST
 545   // Simple enough; pack a few candidate codebooks, unpack them.  Code a
 546   // number of vectors through (keeping track of the quantized values),
 547   // and decode using the unpacked book.  quantized version of in should
 548   // exactly equal out
 549
 550   //#include "vorbis/book/lsp20_0.vqh"
 551   //#include "vorbis/book/lsp32_0.vqh"
 552   //#include "vorbis/book/res0_1a.vqh"
 553   static final int TESTSIZE=40;
 554
 555   static float[] test1={
 556     0.105939,
 557     0.215373,
 558     0.429117,
 559     0.587974,
 560
 561     0.181173,
 562     0.296583,
 563     0.515707,
 564     0.715261,
 565
 566     0.162327,
 567     0.263834,
 568     0.342876,
 569     0.406025,
 570
 571     0.103571,
 572     0.223561,
 573     0.368513,
 574     0.540313,
 575
 576     0.136672,
 577     0.395882,
 578     0.587183,
 579     0.652476,
 580
 581     0.114338,
 582     0.417300,
 583     0.525486,
 584     0.698679,
 585
 586     0.147492,
 587     0.324481,
 588     0.643089,
 589     0.757582,
 590
 591     0.139556,
 592     0.215795,
 593     0.324559,
 594     0.399387,
 595
 596     0.120236,
 597     0.267420,
 598     0.446940,
 599     0.608760,
 600
 601     0.115587,
 602     0.287234,
 603     0.571081,
 604     0.708603,
 605   };
 606
 607   static float[] test2={
 608     0.088654,
 609     0.165742,
 610     0.279013,
 611     0.395894,
 612
 613     0.110812,
 614     0.218422,
 615     0.283423,
 616     0.371719,
 617
 618     0.136985,
 619     0.186066,
 620     0.309814,
 621     0.381521,
 622
 623     0.123925,
 624     0.211707,
 625     0.314771,
 626     0.433026,
 627
 628     0.088619,
 629     0.192276,
 630     0.277568,
 631     0.343509,
 632
 633     0.068400,
 634     0.132901,
 635     0.223999,
 636     0.302538,
 637
 638     0.202159,
 639     0.306131,
 640     0.360362,
 641     0.416066,
 642
 643     0.072591,
 644     0.178019,
 645     0.304315,
 646     0.376516,
 647
 648     0.094336,
 649     0.188401,
 650     0.325119,
 651     0.390264,
 652
 653     0.091636,
 654     0.223099,
 655     0.282899,
 656     0.375124,
 657   };
 658
 659   static float[] test3={
 660     0,1,-2,3,4,-5,6,7,8,9,
 661     8,-2,7,-1,4,6,8,3,1,-9,
 662     10,11,12,13,14,15,26,17,18,19,
 663     30,-25,-30,-1,-5,-32,4,3,-2,0};
 664
 665 //  static_codebook *testlist[]={&_vq_book_lsp20_0,
 666 //                             &_vq_book_lsp32_0,
 667 //                             &_vq_book_res0_1a,NULL};
 668   static[][] float testvec={test1,test2,test3};
 669
 670   static void main(String[] arg){
 671     Buffer write=new Buffer();
 672     Buffer read=new Buffer();
 673     int ptr=0;
 674     write.writeinit();
 675
 676     System.err.println("Testing codebook abstraction...:");
 677
 678     while(testlist[ptr]!=null){
 679       CodeBook c=new CodeBook();
 680       StaticCodeBook s=new StaticCodeBook();;
 681       float *qv=alloca(sizeof(float)*TESTSIZE);
 682       float *iv=alloca(sizeof(float)*TESTSIZE);
 683       memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
 684       memset(iv,0,sizeof(float)*TESTSIZE);
 685
 686       System.err.print("\tpacking/coding "+ptr+"... ");
 687
 688       // pack the codebook, write the testvector
 689       write.reset();
 690       vorbis_book_init_encode(&c,testlist[ptr]); // get it into memory
 691                                                  // we can write
 692       vorbis_staticbook_pack(testlist[ptr],&write);
 693       System.err.print("Codebook size "+write.bytes()+" bytes... ");
 694       for(int i=0;i<TESTSIZE;i+=c.dim){
 695         vorbis_book_encodev(&c,qv+i,&write);
 696       }
 697       c.clear();
 698
 699       System.err.print("OK.\n");
 700       System.err.print("\tunpacking/decoding "+ptr+"... ");
 701
 702       // transfer the write data to a read buffer and unpack/read
 703       _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
 704       if(s.unpack(read)){
 705         System.err.print("Error unpacking codebook.\n");
 706         System.exit(1);
 707       }
 708       if(vorbis_book_init_decode(&c,&s)){
 709         System.err.print("Error initializing codebook.\n");
 710         System.exit(1);
 711       }
 712       for(int i=0;i<TESTSIZE;i+=c.dim){
 713         if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
 714           System.err.print("Error reading codebook test data (EOP).\n");
 715           System.exit(1);
 716         }
 717       }
 718       for(int i=0;i<TESTSIZE;i++){
 719         if(fabs(qv[i]-iv[i])>.000001){
 720           System.err.print("read ("+iv[i]+") != written ("+qv[i]+") at position ("+i+")\n");
 721           System.exit(1);
 722         }
 723       }
 724
 725       System.err.print("OK\n");
 726       ptr++;
 727     }
 728     // The above is the trivial stuff;
 729     // now try unquantizing a log scale codebook
 730   }
 731 */
 732 }
 733
 734 class DecodeAux{
 735   int[] tab;
 736   int[] tabl;
 737   int tabn;
 738
 739   int[] ptr0;
 740   int[] ptr1;
 741   int   aux;        // number of tree entries
 742 }