1/********************************************************************
2 *                                                                  *
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7 *                                                                  *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2010             *
9 * by the Xiph.Org Foundation http://www.xiph.org/                  *
10 *                                                                  *
11 ********************************************************************
12
13 function: utility functions for loading .vqh and .vqd files
14 last mod: $Id: bookutil.c 16959 2010-03-10 16:03:11Z xiphmont $
15
16 ********************************************************************/
17
18#include <stdlib.h>
19#include <stdio.h>
20#include <math.h>
21#include <string.h>
22#include <errno.h>
23#include "bookutil.h"
24
25int _best(codebook *book, float *a, int step){
26
27  int dim=book->dim;
28  int i,j,o;
29  int minval=book->minval;
30  int del=book->delta;
31  int qv=book->quantvals;
32  int ze=(qv>>1);
33  int index=0;
34  /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
35
36  if(del!=1){
37    for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
38      int v = ((int)rint(a[o])-minval+(del>>1))/del;
39      int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
40      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
41    }
42  }else{
43    for(i=0,o=step*(dim-1);i<dim;i++,o-=step){
44      int v = (int)rint(a[o])-minval;
45      int m = (v<ze ? ((ze-v)<<1)-1 : ((v-ze)<<1));
46      index = index*qv+ (m<0?0:(m>=qv?qv-1:m));
47    }
48  }
49
50  if(book->c->lengthlist[index]<=0){
51    const static_codebook *c=book->c;
52    int best=-1;
53    /* assumes integer/centered encoder codebook maptype 1 no more than dim 8 */
54    int e[8]={0,0,0,0,0,0,0,0};
55    int maxval = book->minval + book->delta*(book->quantvals-1);
56    for(i=0;i<book->entries;i++){
57      if(c->lengthlist[i]>0){
58        float this=0;
59        for(j=0;j<dim;j++){
60          float val=(e[j]-a[j*step]);
61          this+=val*val;
62        }
63        if(best==-1 || this<best){
64          best=this;
65          index=i;
66        }
67      }
68      /* assumes the value patterning created by the tools in vq/ */
69      j=0;
70      while(e[j]>=maxval)
71        e[j++]=0;
72      if(e[j]>=0)
73        e[j]+=book->delta;
74      e[j]= -e[j];
75    }
76  }
77
78  return index;
79}
80
81/* A few little utils for reading files */
82/* read a line.  Use global, persistent buffering */
83static char *linebuffer=NULL;
84static int  lbufsize=0;
85char *get_line(FILE *in){
86  long sofar=0;
87  if(feof(in))return NULL;
88
89  while(1){
90    int gotline=0;
91
92    while(!gotline){
93      if(sofar+1>=lbufsize){
94        if(!lbufsize){
95          lbufsize=1024;
96          linebuffer=_ogg_malloc(lbufsize);
97        }else{
98          lbufsize*=2;
99          linebuffer=_ogg_realloc(linebuffer,lbufsize);
100        }
101      }
102      {
103        long c=fgetc(in);
104        switch(c){
105        case EOF:
106          if(sofar==0)return(NULL);
107          /* fallthrough correct */
108        case '\n':
109          linebuffer[sofar]='\0';
110          gotline=1;
111          break;
112        default:
113          linebuffer[sofar++]=c;
114          linebuffer[sofar]='\0';
115          break;
116        }
117      }
118    }
119
120    if(linebuffer[0]=='#'){
121      sofar=0;
122    }else{
123      return(linebuffer);
124    }
125  }
126}
127
128/* read the next numerical value from the given file */
129static char *value_line_buff=NULL;
130
131int get_line_value(FILE *in,float *value){
132  char *next;
133
134  if(!value_line_buff)return(-1);
135
136  *value=strtod(value_line_buff, &next);
137  if(next==value_line_buff){
138    value_line_buff=NULL;
139    return(-1);
140  }else{
141    value_line_buff=next;
142    while(*value_line_buff>44)value_line_buff++;
143    if(*value_line_buff==44)value_line_buff++;
144    return(0);
145  }
146}
147
148int get_next_value(FILE *in,float *value){
149  while(1){
150    if(get_line_value(in,value)){
151      value_line_buff=get_line(in);
152      if(!value_line_buff)return(-1);
153    }else{
154      return(0);
155    }
156  }
157}
158
159int get_next_ivalue(FILE *in,long *ivalue){
160  float value;
161  int ret=get_next_value(in,&value);
162  *ivalue=value;
163  return(ret);
164}
165
166static float sequence_base=0.f;
167static int v_sofar=0;
168void reset_next_value(void){
169  value_line_buff=NULL;
170  sequence_base=0.f;
171  v_sofar=0;
172}
173
174char *setup_line(FILE *in){
175  reset_next_value();
176  value_line_buff=get_line(in);
177  return(value_line_buff);
178}
179
180
181int get_vector(codebook *b,FILE *in,int start, int n,float *a){
182  int i;
183  const static_codebook *c=b->c;
184
185  while(1){
186
187    if(v_sofar==n || get_line_value(in,a)){
188      reset_next_value();
189      if(get_next_value(in,a))
190        break;
191      for(i=0;i<start;i++){
192        sequence_base=*a;
193        get_line_value(in,a);
194      }
195    }
196
197    for(i=1;i<c->dim;i++)
198      if(get_line_value(in,a+i))
199        break;
200
201    if(i==c->dim){
202      float temp=a[c->dim-1];
203      for(i=0;i<c->dim;i++)a[i]-=sequence_base;
204      if(c->q_sequencep)sequence_base=temp;
205      v_sofar++;
206      return(0);
207    }
208    sequence_base=0.f;
209  }
210
211  return(-1);
212}
213
214/* read lines fromt he beginning until we find one containing the
215   specified string */
216char *find_seek_to(FILE *in,char *s){
217  rewind(in);
218  while(1){
219    char *line=get_line(in);
220    if(line){
221      if(strstr(line,s))
222        return(line);
223    }else
224      return(NULL);
225  }
226}
227
228
229/* this reads the format as written by vqbuild/latticebuild; innocent
230   (legal) tweaking of the file that would not affect its valid
231   header-ness will break this routine */
232
233codebook *codebook_load(char *filename){
234  codebook *b=_ogg_calloc(1,sizeof(codebook));
235  static_codebook *c=(static_codebook *)(b->c=_ogg_calloc(1,sizeof(static_codebook)));
236  int quant_to_read=0;
237  FILE *in=fopen(filename,"r");
238  char *line;
239  long i;
240
241  if(in==NULL){
242    fprintf(stderr,"Couldn't open codebook %s\n",filename);
243    exit(1);
244  }
245
246  /* find the codebook struct */
247  find_seek_to(in,"static const static_codebook ");
248
249  /* get the major important values */
250  line=get_line(in);
251  if(sscanf(line,"%ld, %ld,",
252            &(c->dim),&(c->entries))!=2){
253    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
254    exit(1);
255  }
256  line=get_line(in);
257  line=get_line(in);
258  if(sscanf(line,"%d, %ld, %ld, %d, %d,",
259            &(c->maptype),&(c->q_min),&(c->q_delta),&(c->q_quant),
260            &(c->q_sequencep))!=5){
261    fprintf(stderr,"1: syntax in %s in line:\t %s",filename,line);
262    exit(1);
263  }
264
265  switch(c->maptype){
266  case 0:
267    quant_to_read=0;
268    break;
269  case 1:
270    quant_to_read=_book_maptype1_quantvals(c);
271    break;
272  case 2:
273    quant_to_read=c->entries*c->dim;
274    break;
275  }
276
277  /* load the quantized entries */
278  find_seek_to(in,"static const long _vq_quantlist_");
279  reset_next_value();
280  c->quantlist=_ogg_malloc(sizeof(long)*quant_to_read);
281  for(i=0;i<quant_to_read;i++)
282    if(get_next_ivalue(in,c->quantlist+i)){
283      fprintf(stderr,"out of data while reading codebook %s\n",filename);
284      exit(1);
285    }
286
287  /* load the lengthlist */
288  find_seek_to(in,"_lengthlist");
289  reset_next_value();
290  c->lengthlist=_ogg_malloc(sizeof(long)*c->entries);
291  for(i=0;i<c->entries;i++)
292    if(get_next_ivalue(in,c->lengthlist+i)){
293      fprintf(stderr,"out of data while reading codebook %s\n",filename);
294      exit(1);
295    }
296
297  /* got it all */
298  fclose(in);
299
300  vorbis_book_init_encode(b,c);
301  b->valuelist=_book_unquantize(c,c->entries,NULL);
302
303  return(b);
304}
305
306void spinnit(char *s,int n){
307  static int p=0;
308  static long lasttime=0;
309  long test;
310  struct timeval thistime;
311
312  gettimeofday(&thistime,NULL);
313  test=thistime.tv_sec*10+thistime.tv_usec/100000;
314  if(lasttime!=test){
315    lasttime=test;
316
317    fprintf(stderr,"%s%d ",s,n);
318
319    p++;if(p>3)p=0;
320    switch(p){
321    case 0:
322      fprintf(stderr,"|    \r");
323      break;
324    case 1:
325      fprintf(stderr,"/    \r");
326      break;
327    case 2:
328      fprintf(stderr,"-    \r");
329      break;
330    case 3:
331      fprintf(stderr,"\\    \r");
332      break;
333    }
334    fflush(stderr);
335  }
336}
337
338void build_tree_from_lengths(int vals, long *hist, long *lengths){
339  int i,j;
340  long *membership=_ogg_malloc(vals*sizeof(long));
341  long *histsave=alloca(vals*sizeof(long));
342  memcpy(histsave,hist,vals*sizeof(long));
343
344  for(i=0;i<vals;i++)membership[i]=i;
345
346  /* find codeword lengths */
347  /* much more elegant means exist.  Brute force n^2, minimum thought */
348  for(i=vals;i>1;i--){
349    int first=-1,second=-1;
350    long least=-1;
351
352    spinnit("building... ",i);
353
354    /* find the two nodes to join */
355    for(j=0;j<vals;j++)
356      if(least==-1 || hist[j]<=least){
357        least=hist[j];
358        first=membership[j];
359      }
360    least=-1;
361    for(j=0;j<vals;j++)
362      if((least==-1 || hist[j]<=least) && membership[j]!=first){
363        least=hist[j];
364        second=membership[j];
365      }
366    if(first==-1 || second==-1){
367      fprintf(stderr,"huffman fault; no free branch\n");
368      exit(1);
369    }
370
371    /* join them */
372    least=hist[first]+hist[second];
373    for(j=0;j<vals;j++)
374      if(membership[j]==first || membership[j]==second){
375        membership[j]=first;
376        hist[j]=least;
377        lengths[j]++;
378      }
379  }
380  for(i=0;i<vals-1;i++)
381    if(membership[i]!=membership[i+1]){
382      fprintf(stderr,"huffman fault; failed to build single tree\n");
383      exit(1);
384    }
385
386  /* for sanity check purposes: how many bits would it have taken to
387     encode the training set? */
388  {
389    long bitsum=0;
390    long samples=0;
391    for(i=0;i<vals;i++){
392      bitsum+=(histsave[i]-1)*lengths[i];
393      samples+=histsave[i]-1;
394    }
395
396    if(samples){
397      fprintf(stderr,"\rTotal samples in training set: %ld      \n",samples);
398      fprintf(stderr,"\rTotal bits used to represent training set: %ld\n",
399              bitsum);
400    }
401  }
402
403  free(membership);
404}
405
406/* wrap build_tree_from_lengths to allow zero entries in the histogram */
407void build_tree_from_lengths0(int vals, long *hist, long *lengths){
408
409  /* pack the 'sparse' hit list into a dense list, then unpack
410     the lengths after the build */
411
412  int upper=0,i;
413  long *lengthlist=_ogg_calloc(vals,sizeof(long));
414  long *newhist=alloca(vals*sizeof(long));
415
416  for(i=0;i<vals;i++)
417    if(hist[i]>0)
418      newhist[upper++]=hist[i];
419
420  if(upper != vals){
421    fprintf(stderr,"\rEliminating %d unused entries; %d entries remain\n",
422            vals-upper,upper);
423  }
424
425  build_tree_from_lengths(upper,newhist,lengthlist);
426
427  upper=0;
428  for(i=0;i<vals;i++)
429    if(hist[i]>0)
430      lengths[i]=lengthlist[upper++];
431    else
432      lengths[i]=0;
433
434  free(lengthlist);
435}
436
437void write_codebook(FILE *out,char *name,const static_codebook *c){
438  int i,j,k;
439
440  /* save the book in C header form */
441
442  /* first, the static vectors, then the book structure to tie it together. */
443  /* quantlist */
444  if(c->quantlist){
445    long vals=(c->maptype==1?_book_maptype1_quantvals(c):c->entries*c->dim);
446    fprintf(out,"static const long _vq_quantlist_%s[] = {\n",name);
447    for(j=0;j<vals;j++){
448      fprintf(out,"\t%ld,\n",c->quantlist[j]);
449    }
450    fprintf(out,"};\n\n");
451  }
452
453  /* lengthlist */
454  fprintf(out,"static const long _vq_lengthlist_%s[] = {\n",name);
455  for(j=0;j<c->entries;){
456    fprintf(out,"\t");
457    for(k=0;k<16 && j<c->entries;k++,j++)
458      fprintf(out,"%2ld,",c->lengthlist[j]);
459    fprintf(out,"\n");
460  }
461  fprintf(out,"};\n\n");
462
463  /* tie it all together */
464
465  fprintf(out,"static const static_codebook %s = {\n",name);
466
467  fprintf(out,"\t%ld, %ld,\n",c->dim,c->entries);
468  fprintf(out,"\t(long *)_vq_lengthlist_%s,\n",name);
469  fprintf(out,"\t%d, %ld, %ld, %d, %d,\n",
470          c->maptype,c->q_min,c->q_delta,c->q_quant,c->q_sequencep);
471  if(c->quantlist)
472    fprintf(out,"\t(long *)_vq_quantlist_%s,\n",name);
473  else
474    fprintf(out,"\tNULL,\n");
475
476  fprintf(out,"\t0\n};\n\n");
477}
478