codebook.java

java ogg player library. for play back ogg audio

/* JOrbis
 * Copyright (C) 2000 ymnk, JCraft,Inc.
 *  
 * Written by: 2000 ymnk<[e-mail]>
 *   
 * Many thanks to 
 *   Monty <[e-mail]> and 
 *   The XIPHOPHORUS Company http://www.xiph.org/ .
 * JOrbis has been based on their awesome works, Vorbis codec.
 *   
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public License
 * as published by the Free Software Foundation; either version 2 of
 * the License, or (at your option) any later version.
   
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package com.jcraft.jorbis;

import com.jcraft.jogg.*;

class CodeBook{
  int dim;            // codebook dimensions (elements per vector)
  int entries;        // codebook entries
  StaticCodeBook c=new StaticCodeBook();

  float[] valuelist; // list of dim*entries actual entry values
  int[] codelist;     // list of bitstream codewords for each entry
  DecodeAux decode_tree;

  // returns the number of bits
  int encode(int a, Buffer b){
    b.write(codelist[a], c.lengthlist[a]);
    return(c.lengthlist[a]);
  }

  // One the encode side, our vector writers are each designed for a
  // specific purpose, and the encoder is not flexible without modification:
  // 
  // The LSP vector coder uses a single stage nearest-match with no
  // interleave, so no step and no error return.  This is specced by floor0
  // and doesn't change.
  // 
  // Residue0 encoding interleaves, uses multiple stages, and each stage
  // peels of a specific amount of resolution from a lattice (thus we want
  // to match by threshhold, not nearest match).  Residue doesn't *have* to
  // be encoded that way, but to change it, one will need to add more
  // infrastructure on the encode side (decode side is specced and simpler)

  // floor0 LSP (single stage, non interleaved, nearest match)
  // returns entry number and *modifies a* to the quantization value
  int errorv(float[] a){
    int best=best(a,1);
    for(int k=0;k<dim;k++){
      a[k]=valuelist[best*dim+k];
    }
    return(best);
  }

  // returns the number of bits and *modifies a* to the quantization value
  int encodev(int best, float[] a, Buffer b){
    for(int k=0;k<dim;k++){
      a[k]=valuelist[best*dim+k];
    }
    return(encode(best,b));
  }

  // res0 (multistage, interleave, lattice)
  // returns the number of bits and *modifies a* to the remainder value
  int encodevs(float[] a, Buffer b, int step,int addmul){
    int best=besterror(a,step,addmul);
    return(encode(best,b));
  }

  private int[] t=new int[15];  // decodevs_add is synchronized for re-using t.
  synchronized int decodevs_add(float[]a, int offset, Buffer b, int n){
    int step=n/dim;
    int entry;
    int i,j,o;

    if(t.length<step){
      t=new int[step];
    }

    for(i = 0; i < step; i++){
      entry=decode(b);
      if(entry==-1)return(-1);
      t[i]=entry*dim;
    }
    for(i=0,o=0;i<dim;i++,o+=step){
      for(j=0;j<step;j++){
	a[offset+o+j]+=valuelist[t[j]+i];
      }
    }

    return(0);
  }

  int decodev_add(float[]a, int offset, Buffer b,int n){
    int i,j,entry;
    int t;

    if(dim>8){
      for(i=0;i<n;){
        entry = decode(b);
        if(entry==-1)return(-1);
	t=entry*dim;
	for(j=0;j<dim;){
	  a[offset+(i++)]+=valuelist[t+(j++)];
	}
      }
    }
    else{
      for(i=0;i<n;){
	entry=decode(b);
	if(entry==-1)return(-1);
	t=entry*dim;
	j=0;
	switch(dim){
	case 8:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 7:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 6:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 5:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 4:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 3:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 2:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 1:
	  a[offset+(i++)]+=valuelist[t+(j++)];
	case 0:
	break;
	}
      }
    }    
    return(0);
  }

  int decodev_set(float[] a,int offset, Buffer b, int n){
    int i,j,entry;
    int t;

    for(i=0;i<n;){
      entry = decode(b);
      if(entry==-1)return(-1);
      t=entry*dim;
      for(j=0;j<dim;){
        a[offset+i++]=valuelist[t+(j++)];
      }
    }
    return(0);
  }

  int decodevv_add(float[][] a, int offset,int ch, Buffer b,int n){
    int i,j,k,entry;
    int chptr=0;
    //System.out.println("decodevv_add: a="+a+",b="+b+",valuelist="+valuelist);

    for(i=offset/ch;i<(offset+n)/ch;){
      entry = decode(b);
      if(entry==-1)return(-1);

      int t = entry*dim;
      for(j=0;j<dim;j++){
        a[chptr++][i]+=valuelist[t+j];
        if(chptr==ch){
          chptr=0;
	  i++;
	}
      }
    }
    return(0);
  }


  // Decode side is specced and easier, because we don't need to find
  // matches using different criteria; we simply read and map.  There are
  // two things we need to do 'depending':
  //   
  // We may need to support interleave.  We don't really, but it's
  // convenient to do it here rather than rebuild the vector later.
  //
  // Cascades may be additive or multiplicitive; this is not inherent in
  // the codebook, but set in the code using the codebook.  Like
  // interleaving, it's easiest to do it here.  
  // stage==0 -> declarative (set the value)
  // stage==1 -> additive
  // stage==2 -> multiplicitive

  // returns the entry number or -1 on eof
  int decode(Buffer b){
    int ptr=0;
    DecodeAux t=decode_tree;
    int lok=b.look(t.tabn);
    //System.err.println(this+" "+t+" lok="+lok+", tabn="+t.tabn);

    if(lok>=0){
      ptr=t.tab[lok];
      b.adv(t.tabl[lok]);
      if(ptr<=0){
        return -ptr;
      }
    }
    do{
      switch(b.read1()){
      case 0:
	ptr=t.ptr0[ptr];
	break;
      case 1:
	ptr=t.ptr1[ptr];
	break;
      case -1:
      default:
	return(-1);
      }
    }
    while(ptr>0);
    return(-ptr);
  }

  // returns the entry number or -1 on eof
  int decodevs(float[] a, int index, Buffer b, int step,int addmul){
    int entry=decode(b);
    if(entry==-1)return(-1);
    switch(addmul){
    case -1:
      for(int i=0,o=0;i<dim;i++,o+=step)
	a[index+o]=valuelist[entry*dim+i];
      break;
    case 0:
      for(int i=0,o=0;i<dim;i++,o+=step)
	a[index+o]+=valuelist[entry*dim+i];
      break;
    case 1:
      for(int i=0,o=0;i<dim;i++,o+=step)
	a[index+o]*=valuelist[entry*dim+i];
      break;
    default:
      //System.err.println("CodeBook.decodeves: addmul="+addmul); 
    }
    return(entry);
  }

  int best(float[] a, int step){
    EncodeAuxNearestMatch nt=c.nearest_tree;
    EncodeAuxThreshMatch tt=c.thresh_tree;
    int ptr=0;

    // we assume for now that a thresh tree is the only other possibility
    if(tt!=null){
      int index=0;
      // find the quant val of each scalar
      for(int k=0,o=step*(dim-1);k<dim;k++,o-=step){
	int i;
	// linear search the quant list for now; it's small and although
	// with > 8 entries, it would be faster to bisect, this would be
	// a misplaced optimization for now
	for(i=0;i<tt.threshvals-1;i++){
	  if(a[o]<tt.quantthresh[i]){
	    break;
	  }
	}
	index=(index*tt.quantvals)+tt.quantmap[i];
      }
      // regular lattices are easy :-)
      if(c.lengthlist[index]>0){
	// is this unused?  If so, we'll
	// use a decision tree after all
	// and fall through
	return(index);
      }
    }
    if(nt!=null){
      // optimized using the decision tree
      while(true){
	float c=0.f;
	int p=nt.p[ptr];
	int q=nt.q[ptr];
	for(int k=0,o=0;k<dim;k++,o+=step){
	  c+=(valuelist[p+k]-valuelist[q+k])*
	     (a[o]-(valuelist[p+k]+valuelist[q+k])*.5);
	}
	if(c>0.){ // in A
	  ptr= -nt.ptr0[ptr];
	}
	else{     // in B
	  ptr= -nt.ptr1[ptr];
	}
	if(ptr<=0)break;
      }
      return(-ptr);
    }

    // brute force it!
    {
      int besti=-1;
      float best=0.f;
      int e=0;
      for(int i=0;i<entries;i++){
	if(c.lengthlist[i]>0){
	  float _this=dist(dim, valuelist, e, a, step);
	  if(besti==-1 || _this<best){
	    best=_this;
	    besti=i;
	  }
	}
	e+=dim;
      }
      return(besti);
    }
  }

  // returns the entry number and *modifies a* to the remainder value
  int besterror(float[] a, int step, int addmul){
    int best=best(a,step);
    switch(addmul){
    case 0:
      for(int i=0,o=0;i<dim;i++,o+=step)
	a[o]-=valuelist[best*dim+i];
      break;
    case 1:
      for(int i=0,o=0;i<dim;i++,o+=step){
	float val=valuelist[best*dim+i];
	if(val==0){
	  a[o]=0;
	}else{
	  a[o]/=val;
	}
      }
      break;
    }
    return(best);
  }

  void clear(){
    // static book is not cleared; we're likely called on the lookup and
    // the static codebook belongs to the info struct
    //if(decode_tree!=null){
    //  free(b->decode_tree->ptr0);
    //  free(b->decode_tree->ptr1);
    //  memset(b->decode_tree,0,sizeof(decode_aux));
    //  free(b->decode_tree);
    //}
    //if(valuelist!=null)free(b->valuelist);
    //if(codelist!=null)free(b->codelist);
    //memset(b,0,sizeof(codebook));
  }

  private static float dist(int el, float[] ref, int index, float[] b, int step){
    float acc=(float)0.;
    for(int i=0; i<el; i++){
      float val=(ref[index+i]-b[i*step]);
      acc+=val*val;
    }
    return(acc);
  }

/*
  int init_encode(StaticCodeBook s){