lib/res0.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: residue backend 0 implementation
  15  last mod: $Id: res0.c,v 1.9 2000/04/03 09:45:55 xiphmont Exp $
  16
  17  ********************************************************************/
  18
  19 /* Slow, slow, slow, simpleminded and did I mention it was slow?  The
  20    encode/decode loops are coded for clarity and performance is not
  21    yet even a nagging little idea lurking in the shadows.  Oh and BTW,
  22    it's slow. */
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <math.h>
  27 #include <stdio.h>
  28 #include "vorbis/codec.h"
  29 #include "bitwise.h"
  30 #include "registry.h"
  31 #include "scales.h"
  32 #include "bookinternal.h"
  33 #include "misc.h"
  34
  35 typedef struct {
  36   vorbis_info_residue0 *info;
  37
  38   int         parts;
  39   codebook   *phrasebook;
  40
  41   codebook ***partbooks;
  42   int        *partstages;
  43
  44   int         partvals;
  45   int       **decodemap;
  46 } vorbis_look_residue0;
  47
  48 void free_info(vorbis_info_residue *i){
  49   if(i){
  50     memset(i,0,sizeof(vorbis_info_residue0));
  51     free(i);
  52   }
  53 }
  54
  55 void free_look(vorbis_look_residue *i){
  56   int j;
  57   if(i){
  58     vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
  59     for(j=0;j<look->parts;j++)
  60       if(look->partbooks[j])free(look->partbooks[j]);
  61     free(look->partbooks);
  62     for(j=0;j<look->partvals;j++)
  63       free(look->decodemap[j]);
  64     free(look->decodemap);
  65     if(look->partstages)free(look->partstages);
  66     memset(i,0,sizeof(vorbis_look_residue0));
  67     free(i);
  68   }
  69 }
  70
  71 void pack(vorbis_info_residue *vr,oggpack_buffer *opb){
  72   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  73   int j,acc=0;
  74   _oggpack_write(opb,info->begin,24);
  75   _oggpack_write(opb,info->end,24);
  76
  77   _oggpack_write(opb,info->grouping-1,24);  /* residue vectors to group and
  78                                              code with a partitioned book */
  79   _oggpack_write(opb,info->partitions-1,6); /* possible partition choices */
  80   _oggpack_write(opb,info->groupbook,8);  /* group huffman book */
  81   for(j=0;j<info->partitions;j++){
  82     _oggpack_write(opb,info->secondstages[j],4); /* zero *is* a valid choice */
  83     acc+=info->secondstages[j];
  84   }
  85   for(j=0;j<acc;j++)
  86     _oggpack_write(opb,info->booklist[j],8);
  87
  88 }
  89
  90 /* vorbis_info is for range checking */
  91 vorbis_info_residue *unpack(vorbis_info *vi,oggpack_buffer *opb){
  92   int j,acc=0;
  93   vorbis_info_residue0 *info=calloc(1,sizeof(vorbis_info_residue0));
  94
  95   info->begin=_oggpack_read(opb,24);
  96   info->end=_oggpack_read(opb,24);
  97   info->grouping=_oggpack_read(opb,24)+1;
  98   info->partitions=_oggpack_read(opb,6)+1;
  99   info->groupbook=_oggpack_read(opb,8);
 100   for(j=0;j<info->partitions;j++)
 101     acc+=info->secondstages[j]=_oggpack_read(opb,4);
 102   for(j=0;j<acc;j++)
 103     info->booklist[j]=_oggpack_read(opb,8);
 104
 105   if(info->groupbook>=vi->books)goto errout;
 106   for(j=0;j<acc;j++)
 107     if(info->booklist[j]>=vi->books)goto errout;
 108
 109   return(info);
 110  errout:
 111   free_info(info);
 112   return(NULL);
 113 }
 114
 115 vorbis_look_residue *look (vorbis_dsp_state *vd,vorbis_info_mode *vm,
 116                           vorbis_info_residue *vr){
 117   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
 118   vorbis_look_residue0 *look=calloc(1,sizeof(vorbis_look_residue0));
 119   int j,k,acc=0;
 120   int dim;
 121   look->info=info;
 122
 123   look->parts=info->partitions;
 124   look->phrasebook=vd->fullbooks+info->groupbook;
 125   dim=look->phrasebook->dim;
 126
 127   look->partbooks=calloc(look->parts,sizeof(codebook **));
 128   look->partstages=calloc(look->parts,sizeof(int));
 129
 130   for(j=0;j<look->parts;j++){
 131     int stages=info->secondstages[j];
 132     if(stages){
 133       look->partbooks[j]=malloc(stages*sizeof(codebook *));
 134       for(k=0;k<stages;k++)
 135         look->partbooks[j][k]=vd->fullbooks+info->booklist[acc++];
 136     }
 137     look->partstages[j]=stages;
 138   }
 139
 140   look->partvals=pow(look->parts,dim);
 141   look->decodemap=malloc(look->partvals*sizeof(int *));
 142   for(j=0;j<look->partvals;j++){
 143     long val=j;
 144     long mult=look->partvals/look->parts;
 145     look->decodemap[j]=malloc(dim*sizeof(int));
 146     for(k=0;k<dim;k++){
 147       long deco=val/mult;
 148       val-=deco*mult;
 149       mult/=look->parts;
 150       look->decodemap[j][k]=deco;
 151     }
 152   }
 153
 154   return(look);
 155 }
 156
 157 /* returns the distance error from encoding with this book set */
 158 static double _testpart(double *vec,int n, int stages, codebook **books){
 159   int i,j;
 160
 161   double *work=alloca(n*sizeof(double)),acc=0.;
 162   memcpy(work,vec,n*sizeof(double));
 163
 164   if(stages==0){
 165     /* a mild hack.  We want partitions with samples values under
 166        fabs(.5) to be fully zeroed; if this case is met, we return an
 167        error of -1 (which cannot be beaten).  If the samples values
 168        don't meet this criteria, return the real error */
 169     for(i=0;i<n;i++)
 170       if(fabs(vec[i])>.5)break;
 171     if(i==n)return(-1.);
 172
 173     /* real (squared) error */
 174     for(i=0;i<n;i++)
 175       acc+=vec[i]*vec[i];
 176
 177   }else{
 178     for(j=0;j<stages;j++){
 179       acc=0.;
 180       for(i=0;i<n;i+=books[j]->dim)
 181         acc+=vorbis_book_vE(books[j],work+i);
 182     }
 183   }
 184
 185   return(acc);
 186 }
 187
 188 static int _testhack(double *vec,int n){
 189   int i;
 190   double acc=0.;
 191   double max=0.;
 192   for(i=0;i<n;i++)
 193     acc+=todB(fabs(vec[i]));
 194   acc=fromdB(acc/n);
 195   for(i=0;i<n;i++)
 196     max=(fabs(vec[i])>max?fabs(vec[i]):max);
 197
 198   if(max<.5)return(0);
 199   if(max<2.5 && acc<1.5)return(1);
 200   if(max<6.)return(2);
 201   return(3);
 202 }
 203
 204 static int _encodepart(oggpack_buffer *opb,double *vec, int n,
 205                        int stages, codebook **books){
 206   int i,j,bits=0;
 207
 208   double *work=alloca(n*sizeof(double));
 209   memcpy(work,vec,n*sizeof(double));
 210
 211   for(j=0;j<stages;j++)
 212     for(i=0;i<n;i+=books[j]->dim)
 213       bits+=vorbis_book_encodevE(books[j],work+i,opb);
 214
 215   return(bits);
 216 }
 217
 218 static int _decodepart(oggpack_buffer *opb,double *work,double *vec, int n,
 219                        int stages, codebook **books){
 220   int i,j;
 221
 222   memset(work,0,n*sizeof(double));
 223   for(j=0;j<stages;j++)
 224     for(i=0;i<n;i+=books[j]->dim)
 225       vorbis_book_decodev(books[j],work+i,opb);
 226
 227   for(i=0;i<n;i++)
 228     vec[i]*=work[i];
 229
 230   return(0);
 231 }
 232
 233 int forward(vorbis_block *vb,vorbis_look_residue *vl,
 234             double **in,int ch){
 235   long i,j,k,l;
 236   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 237   vorbis_info_residue0 *info=look->info;
 238
 239   /* move all this setup out later */
 240   int samples_per_partition=info->grouping;
 241   int possible_partitions=info->partitions;
 242   int partitions_per_word=look->phrasebook->dim;
 243   int n=info->end-info->begin;
 244   long phrasebits=0,resbitsT=0;
 245   long *resbits=alloca(sizeof(long)*possible_partitions);
 246   long *resvals=alloca(sizeof(long)*possible_partitions);
 247
 248   int partvals=n/samples_per_partition;
 249   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 250   long **partword=_vorbis_block_alloc(vb,ch*sizeof(long *));
 251   partvals=partwords*partitions_per_word;
 252
 253   /* we find/encode the patition type for each partition of each
 254      channel.  We'll go back and do the interleaved encoding in a
 255      bit.  For now, clarity */
 256
 257   if(ch)_analysis_output("a_res",vb->sequence,in[0],n);
 258   memset(resbits,0,sizeof(long)*possible_partitions);
 259   memset(resvals,0,sizeof(long)*possible_partitions);
 260
 261   for(i=0;i<ch;i++){
 262     partword[i]=_vorbis_block_alloc(vb,n/samples_per_partition*sizeof(long));
 263     memset(partword[i],0,n/samples_per_partition*sizeof(long));
 264   }
 265
 266   for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
 267     for(j=0;j<ch;j++){
 268
 269       /* find the best encoding for the partition using each possible
 270          book.  Use the book that had lowest error (we arrange the
 271          books to make optimal choice very obvious and not even think
 272          about bits) */
 273       partword[j][l]=_testhack(in[j]+i,samples_per_partition);
 274
 275 #if 0
 276       double best=_testpart(in[j]+i,samples_per_partition,
 277                             look->partstages[0],look->partbooks[0]);
 278       for(k=1;k<info->partitions;k++){
 279         double this=_testpart(in[j]+i,samples_per_partition,
 280                               look->partstages[k],look->partbooks[k]);
 281         if(this<best){
 282           best=this;
 283           partword[j][l]=k;
 284         }
 285       }
 286 #endif
 287     }
 288   }
 289
 290   /* we code the partition words for each channel, then the residual
 291      words for a partition per channel until we've written all the
 292      partitions for that partition word.  Then write the next parition
 293      channel words... */
 294
 295   for(i=info->begin,l=0;i<info->end;){
 296     /* first we encode a partition codeword for each channel */
 297     for(j=0;j<ch;j++){
 298       long val=partword[j][l];
 299       for(k=1;k<partitions_per_word;k++)
 300         val= val*possible_partitions+partword[j][l+k];
 301       phrasebits+=vorbis_book_encode(look->phrasebook,val,&vb->opb);
 302     }
 303     /* now we encode interleaved residual values for the partitions */
 304     for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition)
 305       for(j=0;j<ch;j++){
 306         resbits[partword[j][l]]+=
 307           _encodepart(&vb->opb,in[j]+i,samples_per_partition,
 308                       look->partstages[partword[j][l]],
 309                       look->partbooks[partword[j][l]]);
 310         resvals[partword[j][l]]+=samples_per_partition;
 311       }
 312
 313   }
 314
 315   for(i=0;i<possible_partitions;i++)resbitsT+=resbits[i];
 316   fprintf(stderr,"Encoded %ld res vectors in %ld phrasing and %ld res bits\n\t",
 317           ch*(info->end-info->begin),phrasebits,resbitsT);
 318   for(i=0;i<possible_partitions;i++)
 319     fprintf(stderr,"%ld(%ld):%ld ",i,resvals[i],resbits[i]);
 320   fprintf(stderr,"\n");
 321
 322   return(0);
 323 }
 324
 325 int inverse(vorbis_block *vb,vorbis_look_residue *vl,double **in,int ch){
 326   long i,j,k,l;
 327   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 328   vorbis_info_residue0 *info=look->info;
 329
 330   /* move all this setup out later */
 331   int samples_per_partition=info->grouping;
 332   int partitions_per_word=look->phrasebook->dim;
 333   int n=info->end-info->begin;
 334
 335   int partvals=n/samples_per_partition;
 336   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 337   int **partword=alloca(ch*sizeof(long *));
 338   double *work=alloca(sizeof(double)*samples_per_partition);
 339   partvals=partwords*partitions_per_word;
 340
 341   for(i=info->begin,l=0;i<info->end;){
 342     /* fetch the partition word for each channel */
 343     for(j=0;j<ch;j++){
 344       int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 345       partword[j]=look->decodemap[temp];
 346       if(partword[j]==NULL)exit(1);
 347     }
 348
 349     /* now we decode interleaved residual values for the partitions */
 350     for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition)
 351       for(j=0;j<ch;j++){
 352         int part=partword[j][k];
 353         _decodepart(&vb->opb,work,in[j]+i,samples_per_partition,
 354                     look->partstages[part],
 355                     look->partbooks[part]);
 356       }
 357   }
 358
 359   if(ch)_analysis_output("s_res",vb->sequence,in[0],n);
 360
 361   return(0);
 362 }
 363
 364 vorbis_func_residue residue0_exportbundle={
 365   &pack,
 366   &unpack,
 367   &look,
 368   &free_info,
 369   &free_look,
 370   &forward,
 371   &inverse
 372 };