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.3 2000/01/06 13:57:10 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 '\n':
  69         case EOF:
  70           linebuffer[sofar]='\0';
  71           gotline=1;
  72           break;
  73         default:
  74           linebuffer[sofar++]=c;
  75           linebuffer[sofar]='\0';
  76           break;
  77         }
  78       }
  79     }
  80
  81     if(linebuffer[0]=='#'){
  82       sofar=0;
  83     }else{
  84       return(linebuffer);
  85     }
  86   }
  87 }
  88
  89 /* read the next numerical value from the given file */
  90 static char *value_line_buff=NULL;
  91
  92 int get_line_value(FILE *in,double *value){
  93   char *next;
  94
  95   if(!value_line_buff)return(-1);
  96
  97   *value=strtod(value_line_buff, &next);
  98   if(next==value_line_buff){
  99     value_line_buff=NULL;
 100     return(-1);
 101   }else{
 102     value_line_buff=next+1;
 103     return(0);
 104   }
 105 }
 106
 107 int get_next_value(FILE *in,double *value){
 108   while(1){
 109     if(get_line_value(in,value)){
 110       value_line_buff=get_line(in);
 111       if(!value_line_buff)return(-1);
 112     }else{
 113       return(0);
 114     }
 115   }
 116 }
 117
 118 int get_next_ivalue(FILE *in,long *ivalue){
 119   double value;
 120   int ret=get_next_value(in,&value);
 121   *ivalue=value;
 122   return(ret);
 123 }
 124
 125 static double sequence_base=0.;
 126 void reset_next_value(void){
 127   value_line_buff=NULL;
 128   sequence_base=0.;
 129 }
 130
 131 int get_vector(codebook *b,FILE *in,double *a){
 132   int i;
 133
 134   while(1){
 135
 136     if(get_line_value(in,a)){
 137       sequence_base=0.;
 138       if(get_next_value(in,a))
 139         break;
 140     }
 141
 142     for(i=1;i<b->dim;i++)
 143       if(get_line_value(in,a+i))
 144         break;
 145
 146     if(i==b->dim){
 147       double temp=a[b->dim-1];
 148       for(i=0;i<b->dim;i++)a[i]-=sequence_base;
 149       if(b->q_sequencep)sequence_base=temp;
 150       return(0);
 151     }
 152     sequence_base=0.;
 153   }
 154
 155   return(-1);
 156 }
 157
 158 /* read lines fromt he beginning until we find one containing the
 159    specified string */
 160 char *find_seek_to(FILE *in,char *s){
 161   rewind(in);
 162   while(1){
 163     char *line=get_line(in);
 164     if(line){
 165       if(strstr(line,s))
 166         return(line);
 167     }else
 168       return(NULL);
 169   }
 170 }
 171
 172
 173 /* this reads the format as written by vqbuild; innocent (legal)
 174    tweaking of the file that would not affect its valid header-ness
 175    will break this routine */
 176
 177 codebook *codebook_load(char *filename){
 178   codebook *b=calloc(1,sizeof(codebook));
 179   encode_aux *a=calloc(1,sizeof(encode_aux));
 180   FILE *in=fopen(filename,"r");
 181   char *line;
 182   long i;
 183
 184   b->encode_tree=a;
 185
 186   if(in==NULL){
 187     fprintf(stderr,"Couldn't open codebook %s\n",filename);
 188     exit(1);
 189   }
 190
 191   /* find the codebook struct */
 192   find_seek_to(in,"static codebook _vq_book_");
 193
 194   /* get the major important values */
 195   line=get_line(in);
 196   if(sscanf(line,"%ld, %ld, %ld, %ld, %d, %d",
 197             &(b->dim),&(b->entries),&(b->q_min),&(b->q_delta),&(b->q_quant),
 198             &(b->q_sequencep))!=6){
 199     fprintf(stderr,"syntax in %s in line:\t %s",filename,line);
 200     exit(1);
 201   }
 202
 203   /* find the auxiliary encode struct (if any) */
 204   find_seek_to(in,"static encode_aux _vq_aux_");
 205   /* how big? */
 206   line=get_line(in);
 207   line=get_line(in);
 208   line=get_line(in);
 209   line=get_line(in);
 210   line=get_line(in);
 211   line=get_line(in);
 212   line=get_line(in);
 213   if(sscanf(line,"%ld, %ld",&(a->aux),&(a->alloc))!=2){
 214     fprintf(stderr,"syntax in %s in line:\t %s",filename,line);
 215     exit(1);
 216   }
 217
 218   /* load the quantized entries */
 219   find_seek_to(in,"static long _vq_quantlist_");
 220   reset_next_value();
 221   b->quantlist=malloc(sizeof(long)*b->entries*b->dim);
 222   for(i=0;i<b->entries*b->dim;i++)
 223     if(get_next_ivalue(in,b->quantlist+i)){
 224       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 225       exit(1);
 226     }
 227
 228   /* load the codewords */
 229   find_seek_to(in,"static long _vq_codelist");
 230   reset_next_value();
 231   b->codelist=malloc(sizeof(long)*b->entries);
 232   for(i=0;i<b->entries;i++)
 233     if(get_next_ivalue(in,b->codelist+i)){
 234       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 235       exit(1);
 236     }
 237
 238   /* load the lengthlist */
 239   find_seek_to(in,"static long _vq_lengthlist");
 240   reset_next_value();
 241   b->lengthlist=malloc(sizeof(long)*b->entries);
 242   for(i=0;i<b->entries;i++)
 243     if(get_next_ivalue(in,b->lengthlist+i)){
 244       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 245       exit(1);
 246     }
 247
 248   /* load ptr0 */
 249   find_seek_to(in,"static long _vq_ptr0");
 250   reset_next_value();
 251   a->ptr0=malloc(sizeof(long)*a->aux);
 252   for(i=0;i<a->aux;i++)
 253     if(get_next_ivalue(in,a->ptr0+i)){
 254       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 255       exit(1);
 256     }
 257
 258   /* load ptr1 */
 259   find_seek_to(in,"static long _vq_ptr1");
 260   reset_next_value();
 261   a->ptr1=malloc(sizeof(long)*a->aux);
 262   for(i=0;i<a->aux;i++)
 263     if(get_next_ivalue(in,a->ptr1+i)){
 264       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 265       exit(1);
 266     }
 267
 268
 269   /* load p */
 270   find_seek_to(in,"static long _vq_p_");
 271   reset_next_value();
 272   a->p=malloc(sizeof(long)*a->aux);
 273   for(i=0;i<a->aux;i++)
 274     if(get_next_ivalue(in,a->p+i)){
 275       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 276       exit(1);
 277     }
 278
 279   /* load q */
 280   find_seek_to(in,"static long _vq_q_");
 281   reset_next_value();
 282   a->q=malloc(sizeof(long)*a->aux);
 283   for(i=0;i<a->aux;i++)
 284     if(get_next_ivalue(in,a->q+i)){
 285       fprintf(stderr,"out of data while reading codebook %s\n",filename);
 286       exit(1);
 287     }
 288
 289   /* got it all */
 290   fclose(in);
 291
 292   /* might as well unquantize the entries while we're at it */
 293   codebook_unquantize(b);
 294
 295   /* don't need n and c */
 296   return(b);
 297 }
 298
 299 int codebook_entry(codebook *b,double *val){
 300   encode_aux *t=b->encode_tree;
 301   int ptr=0,k;
 302   double *n=alloca(b->dim*sizeof(double));
 303
 304   while(1){
 305     double c=0.;
 306     double *p=b->valuelist+t->p[ptr]*b->dim;
 307     double *q=b->valuelist+t->q[ptr]*b->dim;
 308
 309     for(k=0;k<b->dim;k++){
 310       n[k]=p[k]-q[k];
 311       c-=(p[k]+q[k])*n[k];
 312     }
 313     c/=2.;
 314
 315     for(k=0;k<b->dim;k++)
 316       c+=n[k]*val[k];
 317     if(c>0.) /* in A */
 318       ptr= -t->ptr0[ptr];
 319     else     /* in B */
 320       ptr= -t->ptr1[ptr];
 321     if(ptr<=0)break;
 322   }
 323   return(-ptr);
 324 }
 325
 326 /* 24 bit float (not IEEE; nonnormalized mantissa +
 327    biased exponent ): neeeeemm mmmmmmmm mmmmmmmm */
 328
 329 #define VQ_FEXP_BIAS 20 /* bias toward values smaller than 1. */
 330 long float24_pack(double val){
 331   int sign=0;
 332   long exp;
 333   long mant;
 334   if(val<0){
 335     sign=0x800000;
 336     val= -val;
 337   }
 338   exp= floor(log(val)/log(2));
 339   mant=rint(ldexp(val,17-exp));
 340   exp=(exp+VQ_FEXP_BIAS)<<18;
 341
 342   return(sign|exp|mant);
 343 }
 344
 345 double float24_unpack(long val){
 346   double mant=val&0x3ffff;
 347   double sign=val&0x800000;
 348   double exp =(val&0x7c0000)>>18;
 349   if(sign)mant= -mant;
 350   return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
 351 }
 352
 353 void spinnit(char *s,int n){
 354   static int p=0;
 355   static long lasttime=0;
 356   long test;
 357   struct timeval thistime;
 358
 359   gettimeofday(&thistime,NULL);
 360   test=thistime.tv_sec*10+thistime.tv_usec/100000;
 361   if(lasttime!=test){
 362     lasttime=test;
 363
 364     fprintf(stderr,"%s%d ",s,n);
 365
 366     p++;if(p>3)p=0;
 367     switch(p){
 368     case 0:
 369       fprintf(stderr,"|    \r");
 370       break;
 371     case 1:
 372       fprintf(stderr,"/    \r");
 373       break;
 374     case 2:
 375       fprintf(stderr,"-    \r");
 376       break;
 377     case 3:
 378       fprintf(stderr,"\\    \r");
 379       break;
 380     }
 381     fflush(stderr);
 382   }
 383 }
 384