codebook.java

java ogg player library. for play back ogg audio

    //memset(c,0,sizeof(codebook));
    c=s;
    entries=s.entries;
    dim=s.dim;
    codelist=make_words(s.lengthlist, s.entries);
    valuelist=s.unquantize();
    return(0);
  }
*/

  int init_decode(StaticCodeBook s){
    //memset(c,0,sizeof(codebook));
    c=s;
    entries=s.entries;
    dim=s.dim;
    valuelist=s.unquantize();

    decode_tree=make_decode_tree();
    if(decode_tree==null){
      //goto err_out;
      clear();
      return(-1);
    }
    return(0);
//  err_out:
//    vorbis_book_clear(c);
//    return(-1);
  }

  // given a list of word lengths, generate a list of codewords.  Works
  // for length ordered or unordered, always assigns the lowest valued
  // codewords first.  Extended to handle unused entries (length 0)
  static int[] make_words(int[] l, int n){
    int[] marker=new int[33];
    int[] r=new int[n];
    //memset(marker,0,sizeof(marker));

    for(int i=0;i<n;i++){
      int length=l[i];
      if(length>0){
	int entry=marker[length];
      
	// when we claim a node for an entry, we also claim the nodes
	// below it (pruning off the imagined tree that may have dangled
	// from it) as well as blocking the use of any nodes directly
	// above for leaves
      
	// update ourself
	if(length<32 && (entry>>>length)!=0){
	  // error condition; the lengths must specify an overpopulated tree
	  //free(r);
	  return(null);
	}
	r[i]=entry;
    
	// Look to see if the next shorter marker points to the node
	// above. if so, update it and repeat.
	{
	  for(int j=length;j>0;j--){
	    if((marker[j]&1)!=0){
	      // have to jump branches
	      if(j==1)marker[1]++;
	      else marker[j]=marker[j-1]<<1;
	      break; // invariant says next upper marker would already
                     // have been moved if it was on the same path
	    }
	    marker[j]++;
	  }
	}
      
	// prune the tree; the implicit invariant says all the longer
	// markers were dangling from our just-taken node.  Dangle them
	// from our *new* node.
	for(int j=length+1;j<33;j++){
	  if((marker[j]>>>1) == entry){
	    entry=marker[j];
	    marker[j]=marker[j-1]<<1;
	  }
	  else{
	    break;
	  }
	}    
      }
    }

    // bitreverse the words because our bitwise packer/unpacker is LSb
    // endian
    for(int i=0;i<n;i++){
      int temp=0;
      for(int j=0;j<l[i];j++){
	temp<<=1;
	temp|=(r[i]>>>j)&1;
      }
      r[i]=temp;
    }

    return(r);
  }

  // build the decode helper tree from the codewords 
  DecodeAux make_decode_tree(){
    int top=0;
    DecodeAux t=new DecodeAux();
    int[] ptr0=t.ptr0=new int[entries*2];
    int[] ptr1=t.ptr1=new int[entries*2];
    int[] codelist=make_words(c.lengthlist, c.entries);

    if(codelist==null)return(null);
    t.aux=entries*2;

    for(int i=0;i<entries;i++){
      if(c.lengthlist[i]>0){
	int ptr=0;
	int j;
	for(j=0;j<c.lengthlist[i]-1;j++){
	  int bit=(codelist[i]>>>j)&1;
	  if(bit==0){
	    if(ptr0[ptr]==0){
	      ptr0[ptr]=++top;
	    }
	    ptr=ptr0[ptr];
	  }
	  else{
	    if(ptr1[ptr]==0){
	      ptr1[ptr]= ++top;
	    }
	    ptr=ptr1[ptr];
	  }
	}

	if(((codelist[i]>>>j)&1)==0){ ptr0[ptr]=-i; }
	else{ ptr1[ptr]=-i; }

      }
    }
    //free(codelist);

    t.tabn = ilog(entries)-4;

    if(t.tabn<5)t.tabn=5;
    int n = 1<<t.tabn;
    t.tab = new int[n];
    t.tabl = new int[n];
    for(int i = 0; i < n; i++){
      int p = 0;
      int j=0;
      for(j = 0; j < t.tabn && (p > 0 || j == 0); j++){
        if ((i&(1<<j))!=0){
	  p = ptr1[p];
	}
        else{
	  p = ptr0[p];
	}
      }
      t.tab[i]=p;  // -code
      t.tabl[i]=j; // length 
    }

    return(t);
  }

  private static int ilog(int v){
    int ret=0;
    while(v!=0){
      ret++;
      v>>>=1;
    }
    return(ret);
  }

/*
  // TEST
  // Simple enough; pack a few candidate codebooks, unpack them.  Code a
  // number of vectors through (keeping track of the quantized values),
  // and decode using the unpacked book.  quantized version of in should
  // exactly equal out

  //#include "vorbis/book/lsp20_0.vqh"
  //#include "vorbis/book/lsp32_0.vqh"
  //#include "vorbis/book/res0_1a.vqh"
  static final int TESTSIZE=40;

  static float[] test1={
    0.105939,
    0.215373,
    0.429117,
    0.587974,

    0.181173,
    0.296583,
    0.515707,
    0.715261,

    0.162327,
    0.263834,
    0.342876,
    0.406025,

    0.103571,
    0.223561,
    0.368513,
    0.540313,

    0.136672,
    0.395882,
    0.587183,
    0.652476,

    0.114338,
    0.417300,
    0.525486,
    0.698679,

    0.147492,
    0.324481,
    0.643089,
    0.757582,

    0.139556,
    0.215795,
    0.324559,
    0.399387,

    0.120236,
    0.267420,
    0.446940,
    0.608760,

    0.115587,
    0.287234,
    0.571081,
    0.708603,
  };

  static float[] test2={
    0.088654,
    0.165742,
    0.279013,
    0.395894,

    0.110812,
    0.218422,
    0.283423,
    0.371719,

    0.136985,
    0.186066,
    0.309814,
    0.381521,

    0.123925,
    0.211707,
    0.314771,
    0.433026,

    0.088619,
    0.192276,
    0.277568,
    0.343509,

    0.068400,
    0.132901,
    0.223999,
    0.302538,

    0.202159,
    0.306131,
    0.360362,
    0.416066,

    0.072591,
    0.178019,
    0.304315,
    0.376516,

    0.094336,
    0.188401,
    0.325119,
    0.390264,

    0.091636,
    0.223099,
    0.282899,
    0.375124,
  };

  static float[] test3={
    0,1,-2,3,4,-5,6,7,8,9,
    8,-2,7,-1,4,6,8,3,1,-9,
    10,11,12,13,14,15,26,17,18,19,
    30,-25,-30,-1,-5,-32,4,3,-2,0};

//  static_codebook *testlist[]={&_vq_book_lsp20_0,
//			       &_vq_book_lsp32_0,
//			       &_vq_book_res0_1a,NULL};
  static[][] float testvec={test1,test2,test3};

  static void main(String[] arg){
    Buffer write=new Buffer();
    Buffer read=new Buffer();
    int ptr=0;
    write.writeinit();
  
    System.err.println("Testing codebook abstraction...:");

    while(testlist[ptr]!=null){
      CodeBook c=new CodeBook();
      StaticCodeBook s=new StaticCodeBook();;
      float *qv=alloca(sizeof(float)*TESTSIZE);
      float *iv=alloca(sizeof(float)*TESTSIZE);
      memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
      memset(iv,0,sizeof(float)*TESTSIZE);

      System.err.print("\tpacking/coding "+ptr+"... ");

      // pack the codebook, write the testvector
      write.reset();
      vorbis_book_init_encode(&c,testlist[ptr]); // get it into memory
						 // we can write
      vorbis_staticbook_pack(testlist[ptr],&write);
      System.err.print("Codebook size "+write.bytes()+" bytes... ");
      for(int i=0;i<TESTSIZE;i+=c.dim){
	vorbis_book_encodev(&c,qv+i,&write);
      }
      c.clear();
    
      System.err.print("OK.\n");
      System.err.print("\tunpacking/decoding "+ptr+"... ");

      // transfer the write data to a read buffer and unpack/read
      _oggpack_readinit(&read,_oggpack_buffer(&write),_oggpack_bytes(&write));
      if(s.unpack(read)){
	System.err.print("Error unpacking codebook.\n");
	System.exit(1);
      }
      if(vorbis_book_init_decode(&c,&s)){
	System.err.print("Error initializing codebook.\n");
	System.exit(1);
      }
      for(int i=0;i<TESTSIZE;i+=c.dim){
	if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
	  System.err.print("Error reading codebook test data (EOP).\n");
	  System.exit(1);
	}
      }
      for(int i=0;i<TESTSIZE;i++){
	if(fabs(qv[i]-iv[i])>.000001){
	  System.err.print("read ("+iv[i]+") != written ("+qv[i]+") at position ("+i+")\n");
	  System.exit(1);
	}
      }

      System.err.print("OK\n");
      ptr++;
    }
    // The above is the trivial stuff; 
    // now try unquantizing a log scale codebook
  }
*/
}

class DecodeAux{
  int[] tab;
  int[] tabl;
  int tabn;

  int[] ptr0;
  int[] ptr1;
  int   aux;        // number of tree entries
}