2 * Copyright (C) 2000 ymnk, JCraft,Inc.
4 * Written by: 2000 ymnk<ymnk@jcraft.com>
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.
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.
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.
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.
26 package com.jcraft.jorbis;
28 import com.jcraft.jogg.*;
31 int dim; // codebook dimensions (elements per vector)
32 int entries; // codebook entries
33 StaticCodeBook c=new StaticCodeBook();
35 float[] valuelist; // list of dim*entries actual entry values
36 int[] codelist; // list of bitstream codewords for each entry
37 DecodeAux decode_tree;
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]);
45 // One the encode side, our vector writers are each designed for a
46 // specific purpose, and the encoder is not flexible without modification:
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.
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)
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){
62 for(int k=0;k<dim;k++){
63 a[k]=valuelist[best*dim+k];
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];
73 return(encode(best,b));
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));
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){
93 for(i = 0; i < step; i++){
95 if(entry==-1)return(-1);
98 for(i=0,o=0;i<dim;i++,o+=step){
100 a[offset+o+j]+=valuelist[t[j]+i];
107 int decodev_add(float[]a, int offset, Buffer b,int n){
114 if(entry==-1)return(-1);
117 a[offset+(i++)]+=valuelist[t+(j++)];
124 if(entry==-1)return(-1);
129 a[offset+(i++)]+=valuelist[t+(j++)];
131 a[offset+(i++)]+=valuelist[t+(j++)];
133 a[offset+(i++)]+=valuelist[t+(j++)];
135 a[offset+(i++)]+=valuelist[t+(j++)];
137 a[offset+(i++)]+=valuelist[t+(j++)];
139 a[offset+(i++)]+=valuelist[t+(j++)];
141 a[offset+(i++)]+=valuelist[t+(j++)];
143 a[offset+(i++)]+=valuelist[t+(j++)];
152 int decodev_set(float[] a,int offset, Buffer b, int n){
158 if(entry==-1)return(-1);
161 a[offset+i++]=valuelist[t+(j++)];
167 int decodevv_add(float[][] a, int offset,int ch, Buffer b,int n){
170 //System.out.println("decodevv_add: a="+a+",b="+b+",valuelist="+valuelist);
172 for(i=offset/ch;i<(offset+n)/ch;){
174 if(entry==-1)return(-1);
178 a[chptr++][i]+=valuelist[t+j];
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':
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.
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
203 // returns the entry number or -1 on eof
204 int decode(Buffer b){
206 DecodeAux t=decode_tree;
207 int lok=b.look(t.tabn);
208 //System.err.println(this+" "+t+" lok="+lok+", tabn="+t.tabn);
234 // returns the entry number or -1 on eof
235 int decodevs(float[] a, int index, Buffer b, int step,int addmul){
237 if(entry==-1)return(-1);
240 for(int i=0,o=0;i<dim;i++,o+=step)
241 a[index+o]=valuelist[entry*dim+i];
244 for(int i=0,o=0;i<dim;i++,o+=step)
245 a[index+o]+=valuelist[entry*dim+i];
248 for(int i=0,o=0;i<dim;i++,o+=step)
249 a[index+o]*=valuelist[entry*dim+i];
252 //System.err.println("CodeBook.decodeves: addmul="+addmul);
257 int best(float[] a, int step){
258 EncodeAuxNearestMatch nt=c.nearest_tree;
259 EncodeAuxThreshMatch tt=c.thresh_tree;
262 // we assume for now that a thresh tree is the only other possibility
265 // find the quant val of each scalar
266 for(int k=0,o=step*(dim-1);k<dim;k++,o-=step){
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]){
276 index=(index*tt.quantvals)+tt.quantmap[i];
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
287 // optimized using the decision tree
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);
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){
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);
331 for(int i=0,o=0;i<dim;i++,o+=step)
332 a[o]-=valuelist[best*dim+i];
335 for(int i=0,o=0;i<dim;i++,o+=step){
336 float val=valuelist[best*dim+i];
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);
357 //if(valuelist!=null)free(b->valuelist);
358 //if(codelist!=null)free(b->codelist);
359 //memset(b,0,sizeof(codebook));
362 private static float dist(int el, float[] ref, int index, float[] b, int step){
364 for(int i=0; i<el; i++){
365 float val=(ref[index+i]-b[i*step]);
372 int init_encode(StaticCodeBook s){
373 //memset(c,0,sizeof(codebook));
377 codelist=make_words(s.lengthlist, s.entries);
378 valuelist=s.unquantize();
383 int init_decode(StaticCodeBook s){
384 //memset(c,0,sizeof(codebook));
388 valuelist=s.unquantize();
390 decode_tree=make_decode_tree();
391 if(decode_tree==null){
398 // vorbis_book_clear(c);
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];
408 //memset(marker,0,sizeof(marker));
410 for(int i=0;i<n;i++){
413 int entry=marker[length];
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
421 if(length<32 && (entry>>>length)!=0){
422 // error condition; the lengths must specify an overpopulated tree
428 // Look to see if the next shorter marker points to the node
429 // above. if so, update it and repeat.
431 for(int j=length;j>0;j--){
432 if((marker[j]&1)!=0){
433 // have to jump branches
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
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){
449 marker[j]=marker[j-1]<<1;
458 // bitreverse the words because our bitwise packer/unpacker is LSb
460 for(int i=0;i<n;i++){
462 for(int j=0;j<l[i];j++){
472 // build the decode helper tree from the codewords
473 DecodeAux make_decode_tree(){
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);
480 if(codelist==null)return(null);
483 for(int i=0;i<entries;i++){
484 if(c.lengthlist[i]>0){
487 for(j=0;j<c.lengthlist[i]-1;j++){
488 int bit=(codelist[i]>>>j)&1;
503 if(((codelist[i]>>>j)&1)==0){ ptr0[ptr]=-i; }
504 else{ ptr1[ptr]=-i; }
510 t.tabn = ilog(entries)-4;
512 if(t.tabn<5)t.tabn=5;
516 for(int i = 0; i < n; i++){
519 for(j = 0; j < t.tabn && (p > 0 || j == 0); j++){
528 t.tabl[i]=j; // length
534 private static int ilog(int v){
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
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;
555 static float[] test1={
607 static float[] test2={
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};
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};
670 static void main(String[] arg){
671 Buffer write=new Buffer();
672 Buffer read=new Buffer();
676 System.err.println("Testing codebook abstraction...:");
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);
686 System.err.print("\tpacking/coding "+ptr+"... ");
688 // pack the codebook, write the testvector
690 vorbis_book_init_encode(&c,testlist[ptr]); // get it into memory
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);
699 System.err.print("OK.\n");
700 System.err.print("\tunpacking/decoding "+ptr+"... ");
702 // transfer the write data to a read buffer and unpack/read
703 _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
705 System.err.print("Error unpacking codebook.\n");
708 if(vorbis_book_init_decode(&c,&s)){
709 System.err.print("Error initializing codebook.\n");
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");
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");
725 System.err.print("OK\n");
728 // The above is the trivial stuff;
729 // now try unquantizing a log scale codebook
741 int aux; // number of tree entries