lib/analysis.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-1999             *
   9  * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company       *
  10  * http://www.xiph.org/                                             *
  11  *                                                                  *
  12  ********************************************************************
  13
  14  function: PCM data vector blocking, windowing and dis/reassembly
  15  author: Monty <xiphmont@mit.edu>
  16  modifications by: Monty
  17  last modification date: Jul 27 1999
  18
  19  Handle windowing, overlap-add, etc of the PCM vectors.  This is made
  20  more amusing by Vorbis' current two allowed block sizes (512 and 2048
  21  elements/channel).
  22
  23  Vorbis manipulates the dynamic range of the incoming PCM data
  24  envelope to minimise time-domain energy leakage from percussive and
  25  plosive waveforms being quantized in the MDCT domain.
  26
  27  ********************************************************************/
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include "codec.h"
  32
  33 /* pcm accumulator and multipliers
  34    examples (not exhaustive):
  35
  36  <-------------- lW----------------->
  37                    <--------------- W ---------------->
  38 :            .....|.....       _______________         |
  39 :        .'''     |     '''_---      |       |\        |
  40 :.....'''         |_____--- '''......|       | \_______|
  41 :.................|__________________|_______|__|______|
  42                   |<------ Sl ------>|      > Sr <     |endW
  43                   |beginSl           |endSl  |  |endSr
  44                   |beginW            |endlW  |beginSr
  45                   mult[0]                              mult[n]
  46
  47
  48                       |< lW >|
  49                    <--------------- W ---------------->
  50                   |   |  ..  ______________            |
  51                   |   | '  `/        |     ---_        |
  52                   |___.'___/`.       |         ---_____|
  53                   |_______|__|_______|_________________|
  54                   |      >|Sl|<      |<------ Sr ----->|endW
  55                   |       |  |endSl  |beginSr          |endSr
  56                   |beginW |  |endlW
  57                   mult[0] |beginSl                     mult[n]
  58
  59  <-------------- lW----------------->
  60                           |<-W-->|
  61 :            ..............  __  |   |
  62 :        .'''             |`/  \ |   |
  63 :.....'''                 |/`...\|...|
  64 :.........................|__||__|___|
  65                           |Sl||Sr|endW
  66                           |  ||  |endSr
  67                           |  ||beginSr
  68                           |  |endSl
  69                           |beginSl
  70                           |beginW
  71                           mult[0]
  72                                  mult[n]
  73 */
  74
  75 /* arbitrary settings and spec-mandated numbers get filled in here */
  76 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
  77   memset(v,0,sizeof(vorbis_dsp_state));
  78   v->samples_per_envelope_step=64;
  79   v->block_size[0]=512;
  80   v->block_size[1]=2048;
  81
  82   /*  v->window[0][0][0]=vorbis_window(v->block_size[0],
  83                                    v->block_size[0]/2,v->block_size[0]/2);
  84   v->window[1][0][0]=vorbis_window(v->block_size[1],
  85                                    v->block_size[0]/2,v->block_size[0]/2);
  86   v->window[1][0][1]=vorbis_window(v->block_size[1],
  87                                    v->block_size[0]/2,v->block_size[1]/2);
  88   v->window[1][1][0]=vorbis_window(v->block_size[1],
  89                                    v->block_size[1]/2,v->block_size[0]/2);
  90   v->window[1][1][1]=vorbis_window(v->block_size[1],
  91   v->block_size[1]/2,v->block_size[1]/2);*/
  92
  93   /* initialize the storage vectors to a decent size greater than the
  94      minimum */
  95
  96   v->pcm_storage=8192; /* we'll assume later that we have
  97                           a minimum of twice the blocksize of
  98                           accumulated samples in analysis */
  99   v->pcm_channels=v->vi.channels=vi->channels;
 100   v->pcm=malloc(vi->channels*sizeof(double *));
 101   v->pcmret=malloc(vi->channels*sizeof(double *));
 102   {
 103     int i;
 104     for(i=0;i<vi->channels;i++)
 105       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
 106   }
 107
 108   /* Initialize the envelope multiplier storage */
 109
 110   v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 111   v->envelope_channels=vi->channels;
 112   v->deltas=calloc(v->envelope_channels,sizeof(double *));
 113   v->multipliers=calloc(v->envelope_channels,sizeof(int *));
 114   {
 115     int i;
 116     for(i=0;i<v->envelope_channels;i++){
 117       v->deltas[i]=calloc(v->envelope_storage,sizeof(double));
 118       v->multipliers[i]=calloc(v->envelope_storage,sizeof(int));
 119     }
 120   }
 121
 122   /* all 1 (large block) or 0 (small block) */
 123   /* explicitly set for the sake of clarity */
 124   v->lW=0; /* previous window size */
 125   v->W=0;  /* current window size */
 126
 127   /* all vector indexes; multiples of samples_per_envelope_step */
 128   v->centerW=v->block_size[1]/2;
 129
 130   v->pcm_current=v->centerW;
 131   v->envelope_current=v->centerW/v->samples_per_envelope_step;
 132   return(0);
 133 }
 134
 135 void vorbis_analysis_clear(vorbis_dsp_state *v){
 136   int i,j,k;
 137   if(v){
 138     for(i=0;i<2;i++)
 139       for(j=0;j<2;j++)
 140         for(k=0;k<2;k++)
 141           if(v->window[i][j][k])free(v->window[i][j][k]);
 142     if(v->pcm){
 143       for(i=0;i<v->pcm_channels;i++)
 144         if(v->pcm[i])free(v->pcm[i]);
 145       free(v->pcm);
 146       free(v->pcmret);
 147     }
 148     if(v->deltas){
 149       for(i=0;i<v->envelope_channels;i++)
 150         if(v->deltas[i])free(v->deltas[i]);
 151       free(v->deltas);
 152     }
 153     if(v->multipliers){
 154       for(i=0;i<v->envelope_channels;i++)
 155         if(v->multipliers[i])free(v->multipliers[i]);
 156       free(v->multipliers);
 157     }
 158     memset(v,0,sizeof(vorbis_dsp_state));
 159   }
 160 }
 161
 162 /* call with val==0 to set eof */
 163 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
 164   int i;
 165   if(vals<=0){
 166     /* We're encoding the end of the stream.  Just make sure we have
 167        [at least] a full block of zeroes at the end. */
 168     v->eofflag=v->pcm_current;
 169     v->pcm_current+=v->block_size[1]*2;
 170     vals=0;
 171   }
 172
 173   /* Do we have enough storage space for the requested buffer? If not,
 174      expand the PCM (and envelope) storage */
 175
 176   if(v->pcm_current+vals>=v->pcm_storage){
 177     v->pcm_storage=v->pcm_current+vals*2;
 178     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 179
 180     for(i=0;i<v->pcm_channels;i++){
 181       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 182       v->deltas[i]=realloc(v->deltas[i],v->envelope_storage*sizeof(double));
 183       v->multipliers[i]=realloc(v->multipliers[i],
 184                                 v->envelope_storage*sizeof(double));
 185
 186     }
 187   }
 188
 189   if(vals<=0){
 190     /* We're encoding the end of the stream.  Just make sure we have
 191        [at least] a full block of zeroes at the end. */
 192
 193     for(i=0;i<v->pcm_channels;i++)
 194       memset(v->pcm[i]+v->eofflag,0,
 195              (v->pcm_current-v->eofflag)*sizeof(double));
 196   }
 197
 198   for(i=0;i<v->pcm_channels;i++)
 199     v->pcmret[i]=v->pcm[i]+v->pcm_current;
 200
 201   return(v->pcmret);
 202 }
 203
 204 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
 205   if(v->pcm_current+vals>v->pcm_storage)
 206     return(-1);
 207
 208   v->pcm_current+=vals;
 209   return(0);
 210 }
 211
 212 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
 213   int i;
 214   vb->pcm_storage=v->block_size[1];
 215   vb->pcm_channels=v->pcm_channels;
 216   vb->mult_storage=v->block_size[1]/v->samples_per_envelope_step;
 217   vb->mult_channels=v->envelope_channels;
 218
 219   vb->pcm=malloc(vb->pcm_channels*sizeof(double *));
 220   for(i=0;i<vb->pcm_channels;i++)
 221     vb->pcm[i]=malloc(vb->pcm_storage*sizeof(double));
 222
 223   vb->mult=malloc(vb->mult_channels*sizeof(int *));
 224   for(i=0;i<vb->mult_channels;i++)
 225     vb->mult[i]=malloc(vb->mult_storage*sizeof(int));
 226   return(0);
 227 }
 228
 229 int vorbis_block_clear(vorbis_block *vb){
 230   int i;
 231   if(vb->pcm){
 232     for(i=0;i<vb->pcm_channels;i++)
 233       free(vb->pcm[i]);
 234     free(vb->pcm);
 235   }
 236   if(vb->mult){
 237     for(i=0;i<vb->mult_channels;i++)
 238       free(vb->mult[i]);
 239     free(vb->mult);
 240   }
 241   memset(vb,0,sizeof(vorbis_block));
 242   return(0);
 243 }
 244
 245 /* do the deltas, envelope shaping, pre-echo and determine the size of
 246    the next block on which to continue analysis */
 247 int vorbis_analysis_block(vorbis_dsp_state *v,vorbis_block *vb){
 248   int i;
 249   long beginW=v->centerW-v->block_size[v->W]/2,centerNext;
 250   long beginM=beginW/v->samples_per_envelope_step;
 251
 252   /* check to see if we're done... */
 253   if(v->eofflag==-1)return(0);
 254
 255   /* if we have any unfilled envelope blocks for which we have PCM
 256      data, fill them up in before proceeding. */
 257
 258   if(v->pcm_current/v->samples_per_envelope_step>v->envelope_current){
 259     _va_envelope_deltas(v);
 260     _va_envelope_multipliers(v);
 261   }
 262
 263   /* By our invariant, we have lW, W and centerW set.  Search for
 264      the next boundary so we can determine nW (the next window size)
 265      which lets us compute the shape of the current block's window */
 266
 267   /* overconserve for now; any block with a non-placeholder multiplier
 268      should be minimal size. We can be greedy and only look at nW size */
 269
 270   if(v->W)
 271     /* this is a long window; we start the search forward of centerW
 272        because that's the fastest we could react anyway */
 273     i=v->centerW+v->block_size[1]/4-v->block_size[0]/4;
 274   else
 275     /* short window.  Search from centerW */
 276     i=v->centerW;
 277   i/=v->samples_per_envelope_step;
 278
 279   for(;i<v->envelope_storage;i++)if(v->multipliers[i])break;
 280
 281   if(i<v->envelope_storage){
 282     /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
 283        upcoming block large ? */
 284     long largebound;
 285     if(v->W)
 286       largebound=v->centerW+v->block_size[1];
 287     else
 288       largebound=v->centerW+v->block_size[0]/4+v->block_size[1]*3/4;
 289     largebound/=v->samples_per_envelope_step;
 290
 291     if(i>=largebound)
 292       v->nW=1;
 293     else
 294       v->nW=0;
 295
 296   }else{
 297     /* Assume maximum; if the block is incomplete given current
 298        buffered data, this will be detected below */
 299     v->nW=1;
 300   }
 301
 302   /* Do we actually have enough data *now* for the next block? The
 303      reason to check is that if we had no multipliers, that could
 304      simply been due to running out of data.  In that case, we don;t
 305      know the size of the next block for sure and we need that now to
 306      figure out the window shape of this block */
 307
 308   {
 309     long blockbound=centerNext+v->block_size[v->nW]/2;
 310     if(v->pcm_current<blockbound)return(0); /* not enough data yet */
 311   }
 312
 313   /* fill in the block */
 314   vb->lW=v->lW;
 315   vb->W=v->W;
 316   vb->nW=v->nW;
 317   vb->vd=v;
 318
 319   vb->pcmend=v->block_size[v->W];
 320   vb->multend=vb->pcmend / v->samples_per_envelope_step;
 321
 322   if(v->pcm_channels!=vb->pcm_channels ||
 323      v->block_size[1]!=vb->pcm_storage ||
 324      v->envelope_channels!=vb->mult_channels){
 325
 326     /* Storage not initialized or initilized for some other codec
 327        instance with different settings */
 328
 329     vorbis_block_clear(vb);
 330     vorbis_block_init(v,vb);
 331   }
 332
 333   /* copy the vectors */
 334   for(i=0;i<v->pcm_channels;i++)
 335     memcpy(vb->pcm[i],v->pcm[i]+beginW,v->block_size[v->W]*sizeof(double));
 336   for(i=0;i<v->envelope_channels;i++)
 337     memcpy(vb->mult[i],v->multipliers[i]+beginM,v->block_size[v->W]/
 338            v->samples_per_envelope_step*sizeof(int));
 339
 340   vb->frameno=v->frame;
 341
 342   /* handle eof detection: eof==0 means that we've not yet received EOF
 343                            eof>0  marks the last 'real' sample in pcm[]
 344                            eof<0  'no more to do'; doesn't get here */
 345
 346   if(v->eofflag){
 347     long endW=beginW+v->block_size[v->W];
 348     if(endW>=v->eofflag){
 349       v->eofflag=-1;
 350       vb->eofflag=1;
 351     }
 352   }
 353
 354   /* advance storage vectors and clean up */
 355   {
 356     int new_centerNext=v->block_size[1]/2;
 357     int movementW=centerNext-new_centerNext;
 358     int movementM=movementW/v->samples_per_envelope_step;
 359
 360     for(i=0;i<v->pcm_channels;i++)
 361       memmove(v->pcm[i],v->pcm[i]+movementW,
 362               (v->pcm_current-movementW)*sizeof(double));
 363
 364     for(i=0;i<v->envelope_channels;i++){
 365       memmove(v->deltas[i],v->deltas[i]+movementM,
 366               (v->envelope_current-movementM)*sizeof(double));
 367       memmove(v->multipliers[i],v->multipliers[i]+movementM,
 368               (v->envelope_current-movementM)*sizeof(int));
 369     }
 370
 371     v->pcm_current-=movementW;
 372     v->envelope_current-=movementM;
 373
 374     v->lW=v->W;
 375     v->W=v->nW;
 376     v->centerW=new_centerNext;
 377
 378     v->frame++;
 379     v->samples+=movementW;
 380   }
 381
 382   /* done */
 383   return(1);
 384 }
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395 int vorbis_analysis_packetout(vorbis_dsp_state *v, vorbis_block *vb,
 396                               ogg_packet *op){
 397
 398   /* find block's envelope vector and apply it */
 399
 400
 401   /* the real analysis begins; forward MDCT with window */
 402
 403
 404   /* Noise floor, resolution floor */
 405
 406   /* encode the floor into LSP; get the actual floor back for quant */
 407
 408   /* use noise floor, res floor for culling, actual floor for quant */
 409
 410   /* encode residue */
 411
 412 }
 413
 414
 415
 416