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