vq/residuedata.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
   5  * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH    *
   6  * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.        *
   7  *                                                                  *
   8  * THE OggVorbis 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: metrics and quantization code for residue VQ codebooks
  15  last mod: $Id: residuedata.c,v 1.5 2000/11/06 00:07:26 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 #include <stdlib.h>
  20 #include <math.h>
  21 #include <stdio.h>
  22 #include <string.h>
  23 #include "vqgen.h"
  24 #include "bookutil.h"
  25 #include "../lib/sharedbook.h"
  26 #include "../lib/scales.h"
  27 #include "vqext.h"
  28
  29 float scalequant=3.;
  30 char *vqext_booktype="RESdata";
  31 quant_meta q={0,0,0,0};          /* set sequence data */
  32 int vqext_aux=0;
  33
  34 static float *quant_save=NULL;
  35
  36 float *vqext_weight(vqgen *v,float *p){
  37   return p;
  38 }
  39
  40 /* quantize aligned on unit boundaries.  Because our grid is likely
  41    very coarse, play 'shuffle the blocks'; don't allow multiple
  42    entries to fill the same spot as is nearly certain to happen. */
  43
  44 void vqext_quantize(vqgen *v,quant_meta *q){
  45   int j,k;
  46   long dim=v->elements;
  47   long n=v->entries;
  48   float max=-1;
  49   float *test=alloca(sizeof(float)*dim);
  50   int moved=0;
  51
  52
  53   /* allow movement only to unoccupied coordinates on the coarse grid */
  54   for(j=0;j<n;j++){
  55     for(k=0;k<dim;k++){
  56       float val=_now(v,j)[k];
  57       float norm=rint(fabs(val)/scalequant);
  58       if(norm>max)max=norm;
  59       test[k]=norm;
  60     }
  61
  62     /* allow move only if unoccupied */
  63     if(quant_save){
  64       for(k=0;k<n;k++)
  65         if(j!=k && memcmp(test,quant_save+dim*k,dim*sizeof(float))==0)
  66           break;
  67       if(k==n){
  68         if(memcmp(test,quant_save+dim*j,dim*sizeof(float)))
  69           moved++;
  70         memcpy(quant_save+dim*j,test,sizeof(float)*dim);
  71       }
  72     }else{
  73       memcpy(_now(v,j),test,sizeof(float)*dim);
  74     }
  75   }
  76
  77   /* unlike the other trainers, we fill in our quantization
  78      information (as we know granularity beforehand and don't need to
  79      maximize it) */
  80
  81   q->min=_float32_pack(0.);
  82   q->delta=_float32_pack(scalequant);
  83   q->quant=_ilog(max);
  84
  85   if(quant_save){
  86     memcpy(_now(v,0),quant_save,sizeof(float)*dim*n);
  87     fprintf(stderr,"cells shifted this iteration: %d\n",moved);
  88   }
  89 }
  90
  91                             /* candidate,actual */
  92 float vqext_metric(vqgen *v,float *e, float *p){
  93   int i;
  94   float acc=0.;
  95   for(i=0;i<v->elements;i++){
  96     float val=p[i]-e[i];
  97     acc+=val*val;
  98   }
  99   return sqrt(acc);
 100 }
 101
 102 /* We don't interleave here; we assume that the interleave is provided
 103    for us by residuesplit in vorbis/huff/ */
 104 void vqext_addpoint_adj(vqgen *v,float *b,int start,int dim,int cols,int num){
 105   vqgen_addpoint(v,b+start,NULL);
 106 }
 107
 108 /* need to reseed because of the coarse quantization we tend to use on
 109    residuals (which causes lots & lots of dupes) */
 110 void vqext_preprocess(vqgen *v){
 111   long i,j,k,l;
 112   float *test=alloca(sizeof(float)*v->elements);
 113   scalequant=q.quant;
 114
 115   vqext_quantize(v,&q);
 116   vqgen_unquantize(v,&q);
 117
 118   /* if there are any dupes, reseed */
 119   for(k=0;k<v->entries;k++){
 120     for(l=0;l<k;l++){
 121       if(memcmp(_now(v,k),_now(v,l),sizeof(float)*v->elements)==0)
 122         break;
 123     }
 124     if(l<k)break;
 125   }
 126
 127   if(k<v->entries){
 128     fprintf(stderr,"reseeding with quantization....\n");
 129
 130     /* seed the inputs to input points, but points on unit boundaries,
 131      ignoring quantbits for now, making sure each seed is unique */
 132
 133     for(i=0,j=0;i<v->points && j<v->entries;i++){
 134       for(k=0;k<v->elements;k++){
 135         float val=_point(v,i)[k];
 136         test[k]=rint(val/scalequant)*scalequant;
 137       }
 138
 139       for(l=0;l<j;l++){
 140         for(k=0;k<v->elements;k++)
 141           if(test[k]!=_now(v,l)[k])
 142             break;
 143         if(k==v->elements)break;
 144       }
 145       if(l==j){
 146         memcpy(_now(v,j),test,v->elements*sizeof(float));
 147         j++;
 148       }
 149     }
 150
 151     if(j<v->elements){
 152       fprintf(stderr,"Not enough unique entries after prequantization\n");
 153       exit(1);
 154     }
 155   }
 156   vqext_quantize(v,&q);
 157   quant_save=_ogg_malloc(sizeof(float)*v->elements*v->entries);
 158   memcpy(quant_save,_now(v,0),sizeof(float)*v->elements*v->entries);
 159   vqgen_unquantize(v,&q);
 160
 161 }
 162