vq/residuedata.c

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