001/* JOrbis 002 * Copyright (C) 2000 ymnk, JCraft,Inc. 003 * 004 * Written by: 2000 ymnk<ymnk@jcaft.com> 005 * 006 * Many thanks to 007 * Monty <monty@xiph.org> and 008 * The XIPHOPHORUS Company http://www.xiph.org/ . 009 * JOrbis has been based on their awesome works, Vorbis codec. 010 * 011 * This program is free software; you can redistribute it and/or 012 * modify it under the terms of the GNU Library General Public License 013 * as published by the Free Software Foundation; either version 2 of 014 * the License, or (at your option) any later version. 015 016 * This program is distributed in the hope that it will be useful, 017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 019 * GNU Library General Public License for more details. 020 * 021 * You should have received a copy of the GNU Library General Public 022 * License along with this program; if not, write to the Free Software 023 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 024 */ 025 026package com.jcraft.jorbis; 027 028import com.jcraft.jogg.*; 029 030class StaticCodeBook{ 031 int dim; // codebook dimensions (elements per vector) 032 int entries; // codebook entries 033 int[] lengthlist; // codeword lengths in bits 034 035 // mapping 036 int maptype; // 0=none 037 // 1=implicitly populated values from map column 038 // 2=listed arbitrary values 039 040 // The below does a linear, single monotonic sequence mapping. 041 int q_min; // packed 32 bit float; quant value 0 maps to minval 042 int q_delta; // packed 32 bit float; val 1 - val 0 == delta 043 int q_quant; // bits: 0 < quant <= 16 044 int q_sequencep; // bitflag 045 046 // additional information for log (dB) mapping; the linear mapping 047 // is assumed to actually be values in dB. encodebias is used to 048 // assign an error weight to 0 dB. We have two additional flags: 049 // zeroflag indicates if entry zero is to represent -Inf dB; negflag 050 // indicates if we're to represent negative linear values in a 051 // mirror of the positive mapping. 052 053 int[] quantlist; // map == 1: (int)(entries/dim) element column map 054 // map == 2: list of dim*entries quantized entry vals 055 056 // encode helpers 057 EncodeAuxNearestMatch nearest_tree; 058 EncodeAuxThreshMatch thresh_tree; 059 060 StaticCodeBook(){} 061 StaticCodeBook(int dim, int entries, int[] lengthlist, 062 int maptype, int q_min, int q_delta, 063 int q_quant, int q_sequencep, int[] quantlist, 064 //EncodeAuxNearestmatch nearest_tree, 065 Object nearest_tree, 066 // EncodeAuxThreshmatch thresh_tree, 067 Object thresh_tree 068 ){ 069 this(); 070 this.dim=dim; this.entries=entries; this.lengthlist=lengthlist; 071 this.maptype=maptype; this.q_min=q_min; this.q_delta=q_delta; 072 this.q_quant=q_quant; this.q_sequencep=q_sequencep; 073 this.quantlist=quantlist; 074 } 075 076 int pack(Buffer opb){ 077 int i; 078 boolean ordered=false; 079 080 opb.write(0x564342,24); 081 opb.write(dim, 16); 082 opb.write(entries, 24); 083 084 // pack the codewords. There are two packings; length ordered and 085 // length random. Decide between the two now. 086 087 for(i=1;i<entries;i++){ 088 if(lengthlist[i]<lengthlist[i-1])break; 089 } 090 if(i==entries)ordered=true; 091 092 if(ordered){ 093 // length ordered. We only need to say how many codewords of 094 // each length. The actual codewords are generated 095 // deterministically 096 097 int count=0; 098 opb.write(1,1); // ordered 099 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