jorbis/src/com/jcraft/jorbis/StaticCodeBook.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 StaticCodeBook{
  31   int   dim;            // codebook dimensions (elements per vector)
  32   int   entries;        // codebook entries
  33   int[] lengthlist;     // codeword lengths in bits
  34
  35   // mapping
  36   int   maptype;        // 0=none
  37                         // 1=implicitly populated values from map column
  38                         // 2=listed arbitrary values
  39
  40   // The below does a linear, single monotonic sequence mapping.
  41   int   q_min;       // packed 32 bit float; quant value 0 maps to minval
  42   int   q_delta;     // packed 32 bit float; val 1 - val 0 == delta
  43   int   q_quant;     // bits: 0 < quant <= 16
  44   int   q_sequencep; // bitflag
  45
  46   // additional information for log (dB) mapping; the linear mapping
  47   // is assumed to actually be values in dB.  encodebias is used to
  48   // assign an error weight to 0 dB. We have two additional flags:
  49   // zeroflag indicates if entry zero is to represent -Inf dB; negflag
  50   // indicates if we're to represent negative linear values in a
  51   // mirror of the positive mapping.
  52
  53   int[] quantlist;  // map == 1: (int)(entries/dim) element column map
  54                     // map == 2: list of dim*entries quantized entry vals
  55
  56   // encode helpers
  57   EncodeAuxNearestMatch nearest_tree;
  58   EncodeAuxThreshMatch  thresh_tree;
  59
  60   StaticCodeBook(){}
  61   StaticCodeBook(int dim, int entries, int[] lengthlist,
  62                  int maptype, int q_min, int q_delta,
  63                  int q_quant, int q_sequencep, int[] quantlist,
  64                  //EncodeAuxNearestmatch nearest_tree,
  65                  Object nearest_tree,
  66                  // EncodeAuxThreshmatch thresh_tree,
  67                  Object thresh_tree
  68                  ){
  69     this();
  70     this.dim=dim; this.entries=entries; this.lengthlist=lengthlist;
  71     this.maptype=maptype; this.q_min=q_min; this.q_delta=q_delta;
  72     this.q_quant=q_quant; this.q_sequencep=q_sequencep;
  73     this.quantlist=quantlist;
  74   }
  75
  76   int pack(Buffer opb){
  77     int i;
  78     boolean ordered=false;
  79
  80     opb.write(0x564342,24);
  81     opb.write(dim, 16);
  82     opb.write(entries, 24);
  83
  84     // pack the codewords.  There are two packings; length ordered and
  85     // length random.  Decide between the two now.
  86
  87     for(i=1;i<entries;i++){
  88       if(lengthlist[i]<lengthlist[i-1])break;
  89     }
  90     if(i==entries)ordered=true;
  91
  92     if(ordered){
  93       // length ordered.  We only need to say how many codewords of
  94       // each length.  The actual codewords are generated
  95       // deterministically
  96
  97       int count=0;
  98       opb.write(1,1);               // ordered
  99       opb.write(lengthlist[0]-1,5); // 1 to 32
 100
 101       for(i=1;i<entries;i++){
 102         int _this=lengthlist[i];
 103         int _last=lengthlist[i-1];
 104         if(_this>_last){
 105           for(int j=_last;j<_this;j++){
 106             opb.write(i-count,ilog(entries-count));
 107             count=i;
 108           }
 109         }
 110       }
 111       opb.write(i-count,ilog(entries-count));
 112     }
 113     else{
 114       // length random.  Again, we don't code the codeword itself, just
 115       // the length.  This time, though, we have to encode each length
 116       opb.write(0,1);   // unordered
 117
 118       // algortihmic mapping has use for 'unused entries', which we tag
 119       // here.  The algorithmic mapping happens as usual, but the unused
 120       // entry has no codeword.
 121       for(i=0;i<entries;i++){
 122         if(lengthlist[i]==0)break;
 123       }
 124
 125       if(i==entries){
 126         opb.write(0,1); // no unused entries
 127         for(i=0;i<entries;i++){
 128           opb.write(lengthlist[i]-1,5);
 129         }
 130       }
 131       else{
 132         opb.write(1,1); // we have unused entries; thus we tag
 133         for(i=0;i<entries;i++){
 134           if(lengthlist[i]==0){
 135             opb.write(0,1);
 136           }
 137           else{
 138             opb.write(1,1);
 139             opb.write(lengthlist[i]-1,5);
 140           }
 141         }
 142       }
 143     }
 144
 145     // is the entry number the desired return value, or do we have a
 146     // mapping? If we have a mapping, what type?
 147     opb.write(maptype,4);
 148     switch(maptype){
 149     case 0:
 150       // no mapping
 151       break;
 152     case 1:
 153     case 2:
 154       // implicitly populated value mapping
 155       // explicitly populated value mapping
 156       if(quantlist==null){
 157         // no quantlist?  error
 158         return(-1);
 159       }
 160
 161       // values that define the dequantization
 162       opb.write(q_min,32);
 163       opb.write(q_delta,32);
 164       opb.write(q_quant-1,4);
 165       opb.write(q_sequencep,1);
 166
 167       {
 168         int quantvals=0;
 169         switch(maptype){
 170         case 1:
 171           // a single column of (c->entries/c->dim) quantized values for
 172           // building a full value list algorithmically (square lattice)
 173           quantvals=maptype1_quantvals();
 174           break;
 175         case 2:
 176           // every value (c->entries*c->dim total) specified explicitly
 177           quantvals=entries*dim;
 178           break;
 179         }
 180
 181         // quantized values
 182         for(i=0;i<quantvals;i++){
 183           opb.write(Math.abs(quantlist[i]),q_quant);
 184         }
 185       }
 186       break;
 187     default:
 188       // error case; we don't have any other map types now
 189       return(-1);
 190     }
 191     return(0);
 192   }
 193 /*
 194 */
 195
 196   // unpacks a codebook from the packet buffer into the codebook struct,
 197   // readies the codebook auxiliary structures for decode
 198   int unpack(Buffer opb){
 199     int i;
 200     //memset(s,0,sizeof(static_codebook));
 201
 202     // make sure alignment is correct
 203     if(opb.read(24)!=0x564342){
 204 //    goto _eofout;
 205       clear();
 206       return(-1);
 207     }
 208
 209     // first the basic parameters
 210     dim=opb.read(16);
 211     entries=opb.read(24);
 212     if(entries==-1){
 213 //    goto _eofout;
 214       clear();
 215       return(-1);
 216     }
 217
 218     // codeword ordering.... length ordered or unordered?
 219     switch(opb.read(1)){
 220     case 0:
 221       // unordered
 222       lengthlist=new int[entries];
 223
 224       // allocated but unused entries?
 225       if(opb.read(1)!=0){
 226         // yes, unused entries
 227
 228         for(i=0;i<entries;i++){
 229           if(opb.read(1)!=0){
 230             int num=opb.read(5);
 231             if(num==-1){
 232 //            goto _eofout;
 233               clear();
 234               return(-1);
 235             }
 236             lengthlist[i]=num+1;
 237           }
 238           else{
 239             lengthlist[i]=0;
 240           }
 241         }
 242       }
 243       else{
 244         // all entries used; no tagging
 245         for(i=0;i<entries;i++){
 246           int num=opb.read(5);
 247           if(num==-1){
 248 //          goto _eofout;
 249             clear();
 250             return(-1);
 251           }
 252           lengthlist[i]=num+1;
 253         }
 254       }
 255       break;
 256     case 1:
 257       // ordered
 258       {
 259         int length=opb.read(5)+1;
 260         lengthlist=new int[entries];
 261
 262         for(i=0;i<entries;){
 263           int num=opb.read(ilog(entries-i));
 264           if(num==-1){
 265 //          goto _eofout;
 266             clear();
 267             return(-1);
 268           }
 269           for(int j=0;j<num;j++,i++){
 270             lengthlist[i]=length;
 271           }
 272           length++;
 273         }
 274       }
 275       break;
 276     default:
 277       // EOF
 278       return(-1);
 279     }
 280
 281     // Do we have a mapping to unpack?
 282     switch((maptype=opb.read(4))){
 283     case 0:
 284       // no mapping
 285       break;
 286     case 1:
 287     case 2:
 288       // implicitly populated value mapping
 289       // explicitly populated value mapping
 290       q_min=opb.read(32);
 291       q_delta=opb.read(32);
 292       q_quant=opb.read(4)+1;
 293       q_sequencep=opb.read(1);
 294
 295       {
 296         int quantvals=0;
 297         switch(maptype){
 298         case 1:
 299           quantvals=maptype1_quantvals();
 300           break;
 301         case 2:
 302           quantvals=entries*dim;
 303           break;
 304         }
 305
 306         // quantized values
 307         quantlist=new int[quantvals];
 308         for(i=0;i<quantvals;i++){
 309           quantlist[i]=opb.read(q_quant);
 310         }
 311         if(quantlist[quantvals-1]==-1){
 312 //        goto _eofout;
 313           clear();
 314           return(-1);
 315         }
 316       }
 317       break;
 318     default:
 319 //    goto _eofout;
 320       clear();
 321       return(-1);
 322     }
 323     // all set
 324     return(0);
 325 //    _errout:
 326 //    _eofout:
 327 //    vorbis_staticbook_clear(s);
 328 //    return(-1);
 329   }
 330
 331   // there might be a straightforward one-line way to do the below
 332   // that's portable and totally safe against roundoff, but I haven't
 333   // thought of it.  Therefore, we opt on the side of caution
 334   private int maptype1_quantvals(){
 335     int vals=(int)(Math.floor(Math.pow(entries,1./dim)));
 336
 337     // the above *should* be reliable, but we'll not assume that FP is
 338     // ever reliable when bitstream sync is at stake; verify via integer
 339     // means that vals really is the greatest value of dim for which
 340     // vals^b->bim <= b->entries
 341     // treat the above as an initial guess
 342     while(true){
 343       int acc=1;
 344       int acc1=1;
 345       for(int i=0;i<dim;i++){
 346         acc*=vals;
 347         acc1*=vals+1;
 348       }
 349       if(acc<=entries && acc1>entries){ return(vals); }
 350       else{
 351         if(acc>entries){ vals--; }
 352         else{ vals++; }
 353       }
 354     }
 355   }
 356
 357   void clear(){
 358 //  if(quantlist!=null)free(b->quantlist);
 359 //  if(lengthlist!=null)free(b->lengthlist);
 360 //  if(nearest_tree!=null){
 361 //    free(b->nearest_tree->ptr0);
 362 //    free(b->nearest_tree->ptr1);
 363 //    free(b->nearest_tree->p);
 364 //    free(b->nearest_tree->q);
 365 //    memset(b->nearest_tree,0,sizeof(encode_aux_nearestmatch));
 366 //    free(b->nearest_tree);
 367 //  }
 368 //  if(thresh_tree!=null){
 369 //    free(b->thresh_tree->quantthresh);
 370 //    free(b->thresh_tree->quantmap);
 371 //    memset(b->thresh_tree,0,sizeof(encode_aux_threshmatch));
 372 //    free(b->thresh_tree);
 373 //  }
 374 //  memset(b,0,sizeof(static_codebook));
 375   }
 376
 377   // unpack the quantized list of values for encode/decode
 378   // we need to deal with two map types: in map type 1, the values are
 379   // generated algorithmically (each column of the vector counts through
 380   // the values in the quant vector). in map type 2, all the values came
 381   // in in an explicit list.  Both value lists must be unpacked
 382   float[] unquantize(){
 383
 384     if(maptype==1 || maptype==2){
 385       int quantvals;
 386       float mindel=float32_unpack(q_min);
 387       float delta=float32_unpack(q_delta);
 388       float[] r=new float[entries*dim];
 389
 390        //System.err.println("q_min="+q_min+", mindel="+mindel);
 391
 392       // maptype 1 and 2 both use a quantized value vector, but
 393       // different sizes
 394       switch(maptype){
 395       case 1:
 396         // most of the time, entries%dimensions == 0, but we need to be
 397         // well defined.  We define that the possible vales at each
 398         // scalar is values == entries/dim.  If entries%dim != 0, we'll
 399         // have 'too few' values (values*dim<entries), which means that
 400         // we'll have 'left over' entries; left over entries use zeroed
 401         // values (and are wasted).  So don't generate codebooks like that
 402         quantvals=maptype1_quantvals();
 403         for(int j=0;j<entries;j++){
 404           float last=0.f;
 405           int indexdiv=1;
 406           for(int k=0;k<dim;k++){
 407             int index=(j/indexdiv)%quantvals;
 408             float val=quantlist[index];
 409             val=Math.abs(val)*delta+mindel+last;
 410             if(q_sequencep!=0)last=val;
 411             r[j*dim+k]=val;
 412             indexdiv*=quantvals;
 413           }
 414         }
 415         break;
 416       case 2:
 417         for(int j=0;j<entries;j++){
 418           float last=0.f;
 419           for(int k=0;k<dim;k++){
 420             float val=quantlist[j*dim+k];
 421 //if((j*dim+k)==0){System.err.println(" | 0 -> "+val+" | ");}
 422             val=Math.abs(val)*delta+mindel+last;
 423             if(q_sequencep!=0)last=val;
 424             r[j*dim+k]=val;
 425 //if((j*dim+k)==0){System.err.println(" $ r[0] -> "+r[0]+" | ");}
 426           }
 427         }
 428 //System.err.println("\nr[0]="+r[0]);
 429       }
 430       return(r);
 431     }
 432     return(null);
 433   }
 434
 435   private static int ilog(int v){
 436     int ret=0;
 437     while(v!=0){
 438       ret++;
 439       v>>>=1;
 440     }
 441     return(ret);
 442   }
 443
 444   // 32 bit float (not IEEE; nonnormalized mantissa +
 445   // biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
 446   // Why not IEEE?  It's just not that important here.
 447
 448   static final int VQ_FEXP=10;
 449   static final int VQ_FMAN=21;
 450   static final int VQ_FEXP_BIAS=768; // bias toward values smaller than 1.
 451
 452   // doesn't currently guard under/overflow
 453   static long float32_pack(float val){
 454     int sign=0;
 455     int exp;
 456     int mant;
 457     if(val<0){
 458       sign=0x80000000;
 459       val= -val;
 460     }
 461     exp=(int)Math.floor(Math.log(val)/Math.log(2));
 462     mant=(int)Math.rint(Math.pow(val,(VQ_FMAN-1)-exp));
 463     exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
 464     return(sign|exp|mant);
 465   }
 466
 467   static float float32_unpack(int val){
 468     float mant=val&0x1fffff;
 469     float sign=val&0x80000000;
 470     float exp =(val&0x7fe00000)>>>VQ_FMAN;
 471 //System.err.println("mant="+mant+", sign="+sign+", exp="+exp);
 472     //if(sign!=0.0)mant= -mant;
 473     if((val&0x80000000)!=0)mant= -mant;
 474 //System.err.println("mant="+mant);
 475     return(ldexp(mant,((int)exp)-(VQ_FMAN-1)-VQ_FEXP_BIAS));
 476   }
 477
 478   static float ldexp(float foo, int e){
 479     return (float)(foo*Math.pow(2, e));
 480   }
 481
 482 /*
 483   // TEST
 484   // Unit tests of the dequantizer; this stuff will be OK
 485   // cross-platform, I simply want to be sure that special mapping cases
 486   // actually work properly; a bug could go unnoticed for a while
 487
 488   // cases:
 489   //
 490   // no mapping
 491   // full, explicit mapping
 492   // algorithmic mapping
 493   //
 494   // nonsequential
 495   // sequential
 496
 497   static int[] full_quantlist1={0,1,2,3, 4,5,6,7, 8,3,6,1};
 498   static int[] partial_quantlist1={0,7,2};
 499
 500   // no mapping
 501   static StaticCodeBook test1=new StaticCodeBook(4,16,null,
 502                                                  0,0,0,0,0,
 503                                                  null,null,null);
 504   static float[] test1_result=null;
 505
 506   // linear, full mapping, nonsequential
 507   static StaticCodeBook test2=new StaticCodeBook(4,3,null,
 508                                                  2,-533200896,1611661312,4,0,
 509                                                  full_quantlist1, null, null);
 510   static float[] test2_result={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
 511
 512   // linear, full mapping, sequential
 513   static StaticCodeBook test3=new StaticCodeBook(4,3,null,
 514                                                  2, -533200896,1611661312,4,1,
 515                                                  full_quantlist1,null, null);
 516   static float[] test3_result={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
 517
 518   // linear, algorithmic mapping, nonsequential
 519   static StaticCodeBook test4=new StaticCodeBook(3,27,null,
 520                                                  1,-533200896,1611661312,4,0,
 521                                                  partial_quantlist1,null,null);
 522   static float[] test4_result={-3,-3,-3, 4,-3,-3, -1,-3,-3,
 523                                 -3, 4,-3, 4, 4,-3, -1, 4,-3,
 524                                 -3,-1,-3, 4,-1,-3, -1,-1,-3,
 525                                 -3,-3, 4, 4,-3, 4, -1,-3, 4,
 526                                 -3, 4, 4, 4, 4, 4, -1, 4, 4,
 527                                 -3,-1, 4, 4,-1, 4, -1,-1, 4,
 528                                 -3,-3,-1, 4,-3,-1, -1,-3,-1,
 529                                 -3, 4,-1, 4, 4,-1, -1, 4,-1,
 530                                 -3,-1,-1, 4,-1,-1, -1,-1,-1};
 531
 532   // linear, algorithmic mapping, sequential
 533   static StaticCodeBook test5=new StaticCodeBook(3,27,null,
 534                                                  1,-533200896,1611661312,4,1,
 535                                                  partial_quantlist1,null,null);
 536   static float[] test5_result={-3,-6,-9, 4, 1,-2, -1,-4,-7,
 537                                 -3, 1,-2, 4, 8, 5, -1, 3, 0,
 538                                 -3,-4,-7, 4, 3, 0, -1,-2,-5,
 539                                 -3,-6,-2, 4, 1, 5, -1,-4, 0,
 540                                 -3, 1, 5, 4, 8,12, -1, 3, 7,
 541                                 -3,-4, 0, 4, 3, 7, -1,-2, 2,
 542                                 -3,-6,-7, 4, 1, 0, -1,-4,-5,
 543                                 -3, 1, 0, 4, 8, 7, -1, 3, 2,
 544                                 -3,-4,-5, 4, 3, 2, -1,-2,-3};
 545
 546   void run_test(float[] comp){
 547     float[] out=unquantize();
 548     if(comp!=null){
 549       if(out==null){
 550         System.err.println("_book_unquantize incorrectly returned NULL");
 551         System.exit(1);
 552       }
 553       for(int i=0;i<entries*dim;i++){
 554         if(Math.abs(out[i]-comp[i])>.0001){
 555           System.err.println("disagreement in unquantized and reference data:\nposition "+i+": "+out[i]+" != "+comp[i]);
 556           System.exit(1);
 557         }
 558       }
 559     }
 560     else{
 561       if(out!=null){
 562         System.err.println("_book_unquantize returned a value array:\n  correct result should have been NULL");
 563         System.exit(1);
 564       }
 565     }
 566   }
 567
 568   public static void main(String[] arg){
 569     // run the nine dequant tests, and compare to the hand-rolled results
 570     System.err.print("Dequant test 1... ");
 571     test1.run_test(test1_result);
 572     System.err.print("OK\nDequant test 2... ");
 573     test2.run_test(test2_result);
 574     System.err.print("OK\nDequant test 3... ");
 575     test3.run_test(test3_result);
 576     System.err.print("OK\nDequant test 4... ");
 577     test4.run_test(test4_result);
 578     System.err.print("OK\nDequant test 5... ");
 579     test5.run_test(test5_result);
 580     System.err.print("OK\n\n");
 581   }
 582 */
 583 }
 584
 585
 586
 587
 588