/********************************************************************

 *                                                                  *

 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *

 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *

 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *

 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *

 *                                                                  *

 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2014             *

 * by the Xiph.Org Foundation http://www.xiph.org/                  *

 *                                                                  *

 ********************************************************************

 function: utility functions for loading .vqh and .vqd files

 last mod: $Id: bookutil.c 19057 2014-01-22 12:32:31Z xiphmont $

 ********************************************************************/

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <errno.h>

#include "bookutil.h"

int _best(codebook *book, float *a, int step){

  int dim=book->dim;

  int i,j,o;

  int minval=book->minval;

  int del=book->delta;

  int qv=book->quantvals;

  int ze=(qv>>1);

  int index=0;

  /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */

  if(del!=1){

    for(i=0,o=step*(dim-1);i

      int v = ((int)rint(a[o])-minval+(del>>1))/del;

      int m = (v

      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));

    }

  }else{

    for(i=0,o=step*(dim-1);i

      int v = (int)rint(a[o])-minval;

      int m = (v

      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));

    }

  }

  if(book->c->lengthlist[index]<=0){

    const static_codebook *c=book->c;

    int best=-1;

    /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */

    int e[8]={0,0,0,0,0,0,0,0};

    int maxval = book->minval + book->delta*(book->quantvals-1);

    for(i=0;i<book->entries;i++){

      if(c->lengthlist[i]>0){

        float this=0;

        for(j=0;j

          float val=(e[j]-a[j*step]);

          this+=val*val;

        }

        if(best==-1 || this

          best=this;

          index=i;

        }

      }

      /* assumes the value patterning created by the tools in vq/ */

      j=0;

      while(e[j]>=maxval)

        e[j++]=0;

      if(e[j]>=0)

        e[j]+=book->delta;

      e[j]= -e[j];

    }

  }

  return index;

}

/* A few little utils for reading files */

/* read a line.  Use global, persistent buffering */

static char *linebuffer=NULL;

static int  lbufsize=0;

char *get_line(FILE *in){

  long sofar=0;

  if(feof(in))return NULL;

  while(1){

    int gotline=0;

    while(!gotline){

      if(sofar+1>=lbufsize){

        if(!lbufsize){  

          lbufsize=1024;

          linebuffer=_ogg_malloc(lbufsize);

        }else{

          lbufsize*=2;

          linebuffer=_ogg_realloc(linebuffer,lbufsize);

        }

      }

      {

        long c=fgetc(in);

        switch(c){

        case EOF:

          if(sofar==0)return(NULL);

          /* fallthrough correct */

        case '\n':

          linebuffer[sofar]='\0';

          gotline=1;

          break;

        default:

          linebuffer[sofar++]=c;

          linebuffer[sofar]='\0';

          break;

        }

      }

    }

    if(linebuffer[0]=='#'){

      sofar=0;

    }else{

      return(linebuffer);

    }

  }

}

/* read the next numerical value from the given file */

static char *value_line_buff=NULL;

int get_line_value(FILE *in,float *value){

  char *next;

  if(!value_line_buff)return(-1);

  *value=strtod(value_line_buff, &next;;

  if(next==value_line_buff){

    value_line_buff=NULL;

    return(-1);

  }else{

    value_line_buff=next;

    while(*value_line_buff>44)value_line_buff++;

    if(*value_line_buff==44)value_line_buff++;

    return(0);

  }

}

int get_next_value(FILE *in,float *value){

  while(1){

    if(get_line_value(in,value)){

      value_line_buff=get_line(in);

      if(!value_line_buff)return(-1);

    }else{

      return(0);

    }

  }

}

int get_next_ivalue(FILE *in,long *ivalue){

  float value;

  int ret=get_next_value(in,&value);

  *ivalue=value;

  return(ret);

}

static float sequence_base=0.f;

static int v_sofar=0;

void reset_next_value(void){

  value_line_buff=NULL;

  sequence_base=0.f;

  v_sofar=0;

}

char *setup_line(FILE *in){

  reset_next_value();

  value_line_buff=get_line(in);

  return(value_line_buff);

}

int get_vector(codebook *b,FILE *in,int start, int n,float *a){

  int i;

  const static_codebook *c=b->c;

  while(1){

    if(v_sofar==n || get_line_value(in,a)){

      reset_next_value();

      if(get_next_value(in,a))

        break;

      for(i=0;i

        sequence_base=*a;

        get_line_value(in,a);

      }

    }

    for(i=1;i<c->dim;i++)

      if(get_line_value(in,a+i))

        break;

    if(i==c->dim){

      float temp=a[c->dim-1];

      for(i=0;i<c->dim;i++)a[i]-=sequence_base;

      if(c->q_sequencep)sequence_base=temp;

      v_sofar++;

      return(0);

    }

    sequence_base=0.f;

  }

  return(-1);

}

/* read lines fromt he beginning until we find one containing the

   specified string */

char *find_seek_to(FILE *in,char *s){

  rewind(in);

  while(1){

    char *line=get_line(in);

    if(line){

      if(strstr(line,s))

        return(line);

    }else

      return(NULL);

  }

}

/* this reads the format as written by vqbuild/latticebuild; innocent

   (legal) tweaking of the file that would not affect its valid

   header-ness will break this routine */

codebook *codebook_load(char *filename){

  codebook *b=_ogg_calloc(1,sizeof(codebook));

  static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));

  int quant_to_read=0;

  FILE *in=fopen(filename,"r");

  char *line;

  long i;

  if(in==NULL){

    fprintf(stderr,"Couldn't open codebook %s\n",filename);

    exit(1);

  }

  /* find the codebook struct */

  find_seek_to(in,"static const static_codebook ");

  /* get the major important values */

  line=get_line(in);

  if(sscanf(line,"%ld, %ld,",

            &(c->dim),&(c->entries))!=2){

    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);

    exit(1);

  }

  line=get_line(in);

  line=get_line(in);

  if(sscanf(line,"%d, %ld, %ld, %d, %d,",

            &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),

            &(c->q_sequencep))!=5){

    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);

    exit(1);

  }

  switch(c->maptype){

  case 0:

    quant_to_read=0;

    break;

  case 1:

    quant_to_read=_book_maptype1_quantvals(c);

    break;

  case 2:

    quant_to_read=c->entries*c->dim;

    break;

  }

  /* load the quantized entries */

  find_seek_to(in,"static const long _vq_quantlist_");

  reset_next_value();

  c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);

  for(i=0;i

    if(get_next_ivalue(in,c->quantlist+i)){

      fprintf(stderr,"out of data while reading codebook %s\n",filename);

      exit(1);

    }

  /* load the lengthlist */

  find_seek_to(in,"_lengthlist");

  reset_next_value();

  c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);

  for(i=0;i<c->entries;i++)

    if(get_next_ivalue(in,c->lengthlist+i)){

      fprintf(stderr,"out of data while reading codebook %s\n",filename);

      exit(1);

    }

  /* got it all */

  fclose(in);

  vorbis_book_init_encode(b,c);

  b->valuelist=_book_unquantize(c,c->entries,NULL);

  return(b);

}

void spinnit(char *s,int n){

  static int p=0;

  static long lasttime=0;

  long test;

  struct timeval thistime;

  gettimeofday(&thistime,NULL);

  test=thistime.tv_sec*10+thistime.tv_usec/100000;

  if(lasttime!=test){

    lasttime=test;

    fprintf(stderr,"%s%d ",s,n);

    p++;if(p>3)p=0;

    switch(p){

    case 0:

      fprintf(stderr,"|    \r");

      break;

    case 1:

      fprintf(stderr,"/    \r");

      break;

    case 2:

      fprintf(stderr,"-    \r");

      break;

    case 3:

      fprintf(stderr,"\\    \r");

      break;

    }

    fflush(stderr);

  }

}

void build_tree_from_lengths(int vals, long *hist, long *lengths){

  int i,j;

  long *membership=_ogg_malloc(vals*sizeof(long));

  long *histsave=alloca(vals*sizeof(long));

  memcpy(histsave,hist,vals*sizeof(long));

  for(i=0;i

  /* find codeword lengths */

  /* much more elegant means exist.  Brute force n^2, minimum thought */

  for(i=vals;i>1;i--){

    int first=-1,second=-1;

    long least=-1;

    spinnit("building... ",i);

    /* find the two nodes to join */

    for(j=0;j

      if(least==-1 || hist[j]<=least){

        least=hist[j];

        first=membership[j];

      }

    least=-1;

    for(j=0;j

      if((least==-1 || hist[j]<=least) && membership[j]!=first){

        least=hist[j];

        second=membership[j];

      }

    if(first==-1 || second==-1){

      fprintf(stderr,"huffman fault; no free branch\n");

      exit(1);

    }

    /* join them */

    least=hist[first]+hist[second];

    for(j=0;j

      if(membership[j]==first || membership[j]==second){

        membership[j]=first;

        hist[j]=least;

        lengths[j]++;

      }

  }

  for(i=0;i

    if(membership[i]!=membership[i+1]){

      fprintf(stderr,"huffman fault; failed to build single tree\n");

      exit(1);

    }

  /* for sanity check purposes: how many bits would it have taken to

     encode the training set? */

  {

    long bitsum=0;

    long samples=0;

    for(i=0;i

      bitsum+=(histsave[i]-1)*lengths[i];

      samples+=histsave[i]-1;

    }

    if(samples){

      fprintf(stderr,"\rTotal samples in training set: %ld      \n",samples);

      fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",

              bitsum);

    }

  }

  free(membership);

}

/* wrap build_tree_from_lengths to allow zero entries in the histogram */

void build_tree_from_lengths0(int vals, long *hist, long *lengths){

  /* pack the 'sparse' hit list into a dense list, then unpack

     the lengths after the build */

  int upper=0,i;

  long *lengthlist=_ogg_calloc(vals,sizeof(long));

  long *newhist=alloca(vals*sizeof(long));

  for(i=0;i

    if(hist[i]>0)

      newhist[upper++]=hist[i];

  if(upper != vals){

    fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",

            vals-upper,upper);

  }

  build_tree_from_lengths(upper,newhist,lengthlist);

  upper=0;

  for(i=0;i

    if(hist[i]>0)

      lengths[i]=lengthlist[upper++];

    else

      lengths[i]=0;

  free(lengthlist);

}

void write_codebook(FILE *out,char *name,const static_codebook *c){

  int i,j,k;

  /* save the book in C header form */

  /* first, the static vectors, then the book structure to tie it together. */

  /* quantlist */

  if(c->quantlist){

    long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);

    fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name);

    for(j=0;j

      fprintf(out,"\t%ld,\n",c->quantlist[j]);

    }

    fprintf(out,"};\n\n");

  }

  /* lengthlist */

  fprintf(out,"static const char _vq_lengthlist_%s[] = {\n",name);

  for(j=0;j<c->entries;){

    fprintf(out,"\t");

    for(k=0;k<16 && j<c->entries;k++,j++)

      fprintf(out,"%2ld,",c->lengthlist[j]);

    fprintf(out,"\n");

  }

  fprintf(out,"};\n\n");

  /* tie it all together */

  fprintf(out,"static const static_codebook %s = {\n",name);

  fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);

  fprintf(out,"\t(char *)_vq_lengthlist_%s,\n",name);

  fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",

          c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);

  if(c->quantlist)

    fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name);

  else

    fprintf(out,"\tNULL,\n");

  fprintf(out,"\t0\n};\n\n");

}