vq/bookutil.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
   5  * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
   6  * PLEASE READ THESE TERMS DISTRIBUTING.                            *
   7  *                                                                  *
   8  * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
   9  * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
  10  * http://www.xiph.org/                                             *
  11  *                                                                  *
  12  ********************************************************************
  13
  14  function: utility functions for loading .vqh and .vqd files
  15  last mod: $Id: bookutil.c,v 1.4 2000/01/10 10:42:01 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <math.h>
  22 #include <string.h>
  23 #include <errno.h>
  24 #include "vorbis/codebook.h"
  25 #include "bookutil.h"
  26
  27 void codebook_unquantize(codebook *b){
  28   long j,k;
  29   double mindel=float24_unpack(b->q_min);
  30   double delta=float24_unpack(b->q_delta);
  31   if(!b->valuelist)b->valuelist=malloc(sizeof(double)*b->entries*b->dim);
  32
  33   for(j=0;j<b->entries;j++){
  34     double last=0.;
  35     for(k=0;k<b->dim;k++){
  36       double val=b->quantlist[j*b->dim+k]*delta+last+mindel;
  37       b->valuelist[j*b->dim+k]=val;
  38       if(b->q_sequencep)last=val;
  39
  40     }
  41   }
  42 }
  43
  44 /* A few little utils for reading files */
  45 /* read a line.  Use global, persistent buffering */
  46 static char *linebuffer=NULL;
  47 static int  lbufsize=0;
  48 char *get_line(FILE *in){
  49   long sofar=0;
  50   if(feof(in))return NULL;
  51
  52   while(1){
  53     int gotline=0;
  54
  55     while(!gotline){
  56       if(sofar+1>=lbufsize){
  57         if(!lbufsize){
  58           lbufsize=1024;
  59           linebuffer=malloc(lbufsize);
  60         }else{
  61           lbufsize*=2;
  62           linebuffer=realloc(linebuffer,lbufsize);
  63         }
  64       }
  65       {
  66         long c=fgetc(in);
  67         switch(c){
  68         case EOF:
  69           if(sofar==0)return(NULL);
  70           /* fallthrough correct */
  71         case '\n':
  72           linebuffer[sofar]='\0';
  73           gotline=1;
  74           break;
  75         default:
  76           linebuffer[sofar++]=c;
  77           linebuffer[sofar]='\0';
  78           break;
  79         }
  80       }
  81     }
  82
  83     if(linebuffer[0]=='#'){
  84       sofar=0;
  85     }else{
  86       return(linebuffer);
  87     }
  88   }
  89 }
  90
  91 /* read the next numerical value from the given file */
  92 static char *value_line_buff=NULL;
  93
  94 int get_line_value(FILE *in,double *value){
  95   char *next;
  96
  97   if(!value_line_buff)return(-1);
  98
  99   *value=strtod(value_line_buff, &next);
 100   if(next==value_line_buff){
 101     value_line_buff=NULL;
 102     return(-1);
 103   }else{
 104     value_line_buff=next+1;
 105     return(0);
 106   }
 107 }
 108
 109 int get_next_value(FILE *in,double *value){
 110   while(1){
 111     if(get_line_value(in,value)){
 112       value_line_buff=get_line(in);
 113       if(!value_line_buff)return(-1);
 114     }else{
 115       return(0);
 116     }
 117   }
 118 }
 119
 120 int get_next_ivalue(FILE *in,long *ivalue){
 121   double value;
 122   int ret=get_next_value(in,&value);
 123   *ivalue=value;
 124   return(ret);
 125 }
 126
 127 static double sequence_base=0.;
 128 static int v_sofar=0;
 129 void reset_next_value(void){
 130   value_line_buff=NULL;
 131   sequence_base=0.;
 132   v_sofar=0;
 133 }
 134
 135 int get_vector(codebook *b,FILE *in,int start, int n,double *a){
 136   int i;
 137
 138   while(1){
 139
 140     if(v_sofar==n || get_line_value(in,a)){
 141       reset_next_value();
 142       if(get_next_value(in,a))
 143         break;
 144       for(i=0;i<start;i++){
 145         sequence_base=*a;
 146         get_line_value(in,a);
 147       }
 148     }
 149
 150     for(i=1;i<b->dim;i++)
 151       if(get_line_value(in,a+i))
 152         break;
 153
 154     if(i==b->dim){
 155       double temp=a[b->dim-1];
 156       for(i=0;i<b->dim;i++)a[i]-=sequence_base;
 157       if(b->q_sequencep)sequence_base=temp;
 158       v_sofar++;
 159       return(0);
 160     }
 161     sequence_base=0.;
 162   }
 163
 164   return(-1);
 165 }
 166
 167 /* read lines fromt he beginning until we find one containing the
 168    specified string */
 169 char *find_seek_to(FILE *in,char *s){
 170   rewind(in);
 171   while(1){
 172     char *line=get_line(in);
 173     if(line){
 174       if(strstr(line,s))
 175         return(line);
 176     }else
 177       return(NULL);
 178   }
 179 }
 180
 181
 182 /* this reads the format as written by vqbuild; innocent (legal)
 183    tweaking of the file that would not affect its valid header-ness
 184    will break this routine */
 185
 186 codebook *codebook_load(char *filename){
 187   codebook *b=calloc(1,sizeof(codebook));
 188   encode_aux *a=calloc(1,sizeof(encode_aux));
 189   FILE *in=fopen(filename,"r");
 190   char *line;
 191   long i;
 192
 193   b->encode_tree=a;
 194
 195   if(in==NULL){
 196     fprintf(stderr,"Couldn't open codebook %s\n",filename);
 197     exit(1);
 198   }
 199
 200   /* find the codebook struct */
 201   find_seek_to(in,"static codebook _vq_book_");
 202
 203   /* get the major important values */
 204   line=get_line(in);
 205   if(sscanf(line,"%ld, %ld, %ld, %ld, %d, %d",
 206             &(b->dim),&(b->entries),&(b->q_min),&(b->q_delta),&(b->q_quant),
 207             &(b->q_sequencep))!=6){
 208     fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
 209     exit(1);
 210   }
 211
 212   /* find the auxiliary encode struct (if any) */
 213   find_seek_to(in,"static encode_aux _vq_aux_");
 214   /* how big? */
 215   line=get_line(in);
 216   line=get_line(in);
 217   line=get_line(in);
 218   line=get_line(in);
 219   line=get_line(in);
 220   line=get_line(in);
 221   line=get_line(in);
 222   if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
 223     fprintf(stderr,"2: syntax in %s in line:\t %s",filename,line);
 224     exit(1);
 225   }
 226
 227   /* load the quantized entries */
 228   find_seek_to(in,"static long _vq_quantlist_");
 229   reset_next_value();
 230   b->quantlist=malloc(sizeof(long)*b->entries*b->dim);
 231   for(i=0;i<b->entries*b->dim;i++)
 232     if(get_next_ivalue(in,b->quantlist+i)){
 233       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 234       exit(1);
 235     }
 236
 237   /* load the codewords */
 238   find_seek_to(in,"static long _vq_codelist");
 239   reset_next_value();
 240   b->codelist=malloc(sizeof(long)*b->entries);
 241   for(i=0;i<b->entries;i++)
 242     if(get_next_ivalue(in,b->codelist+i)){
 243       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 244       exit(1);
 245     }
 246
 247   /* load the lengthlist */
 248   find_seek_to(in,"static long _vq_lengthlist");
 249   reset_next_value();
 250   b->lengthlist=malloc(sizeof(long)*b->entries);
 251   for(i=0;i<b->entries;i++)
 252     if(get_next_ivalue(in,b->lengthlist+i)){
 253       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 254       exit(1);
 255     }
 256
 257   /* load ptr0 */
 258   find_seek_to(in,"static long _vq_ptr0");
 259   reset_next_value();
 260   a->ptr0=malloc(sizeof(long)*a->aux);
 261   for(i=0;i<a->aux;i++)
 262     if(get_next_ivalue(in,a->ptr0+i)){
 263       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 264       exit(1);
 265     }
 266
 267   /* load ptr1 */
 268   find_seek_to(in,"static long _vq_ptr1");
 269   reset_next_value();
 270   a->ptr1=malloc(sizeof(long)*a->aux);
 271   for(i=0;i<a->aux;i++)
 272     if(get_next_ivalue(in,a->ptr1+i)){
 273       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 274       exit(1);
 275     }
 276
 277
 278   /* load p */
 279   find_seek_to(in,"static long _vq_p_");
 280   reset_next_value();
 281   a->p=malloc(sizeof(long)*a->aux);
 282   for(i=0;i<a->aux;i++)
 283     if(get_next_ivalue(in,a->p+i)){
 284       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 285       exit(1);
 286     }
 287
 288   /* load q */
 289   find_seek_to(in,"static long _vq_q_");
 290   reset_next_value();
 291   a->q=malloc(sizeof(long)*a->aux);
 292   for(i=0;i<a->aux;i++)
 293     if(get_next_ivalue(in,a->q+i)){
 294       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 295       exit(1);
 296     }
 297
 298   /* got it all */
 299   fclose(in);
 300
 301   /* might as well unquantize the entries while we're at it */
 302   codebook_unquantize(b);
 303
 304   /* don't need n and c */
 305   return(b);
 306 }
 307
 308 int codebook_entry(codebook *b,double *val){
 309   encode_aux *t=b->encode_tree;
 310   int ptr=0,k;
 311   double *n=alloca(b->dim*sizeof(double));
 312
 313   while(1){
 314     double c=0.;
 315     double *p=b->valuelist+t->p[ptr]*b->dim;
 316     double *q=b->valuelist+t->q[ptr]*b->dim;
 317
 318     for(k=0;k<b->dim;k++){
 319       n[k]=p[k]-q[k];
 320       c-=(p[k]+q[k])*n[k];
 321     }
 322     c/=2.;
 323
 324     for(k=0;k<b->dim;k++)
 325       c+=n[k]*val[k];
 326     if(c>0.) /* in A */
 327       ptr= -t->ptr0[ptr];
 328     else     /* in B */
 329       ptr= -t->ptr1[ptr];
 330     if(ptr<=0)break;
 331   }
 332   return(-ptr);
 333 }
 334
 335 /* 24 bit float (not IEEE; nonnormalized mantissa +
 336    biased exponent ): neeeeemm mmmmmmmm mmmmmmmm */
 337
 338 #define VQ_FEXP_BIAS 20 /* bias toward values smaller than 1. */
 339 long float24_pack(double val){
 340   int sign=0;
 341   long exp;
 342   long mant;
 343   if(val<0){
 344     sign=0x800000;
 345     val= -val;
 346   }
 347   exp= floor(log(val)/log(2));
 348   mant=rint(ldexp(val,17-exp));
 349   exp=(exp+VQ_FEXP_BIAS)<<18;
 350
 351   return(sign|exp|mant);
 352 }
 353
 354 double float24_unpack(long val){
 355   double mant=val&0x3ffff;
 356   double sign=val&0x800000;
 357   double exp =(val&0x7c0000)>>18;
 358   if(sign)mant= -mant;
 359   return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
 360 }
 361
 362 void spinnit(char *s,int n){
 363   static int p=0;
 364   static long lasttime=0;
 365   long test;
 366   struct timeval thistime;
 367
 368   gettimeofday(&thistime,NULL);
 369   test=thistime.tv_sec*10+thistime.tv_usec/100000;
 370   if(lasttime!=test){
 371     lasttime=test;
 372
 373     fprintf(stderr,"%s%d ",s,n);
 374
 375     p++;if(p>3)p=0;
 376     switch(p){
 377     case 0:
 378       fprintf(stderr,"|    \r");
 379       break;
 380     case 1:
 381       fprintf(stderr,"/    \r");
 382       break;
 383     case 2:
 384       fprintf(stderr,"-    \r");
 385       break;
 386     case 3:
 387       fprintf(stderr,"\\    \r");
 388       break;
 389     }
 390     fflush(stderr);
 391   }
 392 }
 393