lib/block.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: Aug 05 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.
  21
  22  Vorbis manipulates the dynamic range of the incoming PCM data
  23  envelope to minimise time-domain energy leakage from percussive and
  24  plosive waveforms being quantized in the MDCT domain.
  25
  26  ********************************************************************/
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include "codec.h"
  31 #include "window.h"
  32 #include "envelope.h"
  33 #include "mdct.h"
  34
  35 /* pcm accumulator examples (not exhaustive):
  36
  37  <-------------- lW ---------------->
  38                    <--------------- W ---------------->
  39 :            .....|.....       _______________         |
  40 :        .'''     |     '''_---      |       |\        |
  41 :.....'''         |_____--- '''......|       | \_______|
  42 :.................|__________________|_______|__|______|
  43                   |<------ Sl ------>|      > Sr <     |endW
  44                   |beginSl           |endSl  |  |endSr
  45                   |beginW            |endlW  |beginSr
  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 */
  72
  73 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi){
  74   memset(v,0,sizeof(vorbis_dsp_state));
  75
  76   memcpy(&v->vi,vi,sizeof(vorbis_info));
  77   _ve_envelope_init(&v->ve,vi->envelopesa);
  78   mdct_init(&v->vm[0],vi->smallblock);
  79   mdct_init(&v->vm[1],vi->largeblock);
  80
  81   v->samples_per_envelope_step=vi->envelopesa;
  82   v->block_size[0]=vi->smallblock;
  83   v->block_size[1]=vi->largeblock;
  84
  85   v->window[0][0][0]=_vorbis_window(v->block_size[0],
  86                                    v->block_size[0]/2,v->block_size[0]/2);
  87   v->window[0][0][1]=v->window[0][0][0];
  88   v->window[0][1][0]=v->window[0][0][0];
  89   v->window[0][1][1]=v->window[0][0][0];
  90
  91   v->window[1][0][0]=_vorbis_window(v->block_size[1],
  92                                    v->block_size[0]/2,v->block_size[0]/2);
  93   v->window[1][0][1]=_vorbis_window(v->block_size[1],
  94                                    v->block_size[0]/2,v->block_size[1]/2);
  95   v->window[1][1][0]=_vorbis_window(v->block_size[1],
  96                                    v->block_size[1]/2,v->block_size[0]/2);
  97   v->window[1][1][1]=_vorbis_window(v->block_size[1],
  98                                     v->block_size[1]/2,v->block_size[1]/2);
  99
 100   /* initialize the storage vectors to a decent size greater than the
 101      minimum */
 102
 103   v->pcm_storage=8192; /* we'll assume later that we have
 104                           a minimum of twice the blocksize of
 105                           accumulated samples in analysis */
 106   v->pcm_channels=v->vi.channels=vi->channels;
 107   v->pcm=malloc(vi->channels*sizeof(double *));
 108   v->pcmret=malloc(vi->channels*sizeof(double *));
 109   {
 110     int i;
 111     for(i=0;i<vi->channels;i++)
 112       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
 113   }
 114
 115   /* Initialize the envelope multiplier storage */
 116
 117   if(vi->envelopech){
 118     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 119     v->envelope_channels=vi->envelopech;
 120     v->multipliers=calloc(v->envelope_channels,sizeof(double *));
 121     {
 122       int i;
 123       for(i=0;i<v->envelope_channels;i++){
 124         v->multipliers[i]=calloc(v->envelope_storage,sizeof(double));
 125       }
 126     }
 127   }
 128
 129   /* all 1 (large block) or 0 (small block) */
 130   /* explicitly set for the sake of clarity */
 131   v->lW=0; /* previous window size */
 132   v->W=0;  /* current window size */
 133
 134   /* all vector indexes; multiples of samples_per_envelope_step */
 135   v->centerW=v->block_size[1]/2;
 136
 137   v->pcm_current=v->centerW;
 138   v->envelope_current=v->centerW/v->samples_per_envelope_step;
 139   return(0);
 140 }
 141
 142 /* arbitrary settings and spec-mandated numbers get filled in here */
 143 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
 144   _vds_shared_init(v,vi);
 145   drft_init(&v->vf[0],vi->smallblock); /* only used in analysis */
 146   drft_init(&v->vf[1],vi->largeblock); /* only used in analysis */
 147
 148   return(0);
 149 }
 150
 151 void vorbis_analysis_clear(vorbis_dsp_state *v){
 152   int i,j,k;
 153   if(v){
 154
 155     if(v->window[0][0][0])free(v->window[0][0][0]);
 156     for(j=0;j<2;j++)
 157       for(k=0;k<2;k++)
 158         if(v->window[1][j][k])free(v->window[1][j][k]);
 159     if(v->pcm){
 160       for(i=0;i<v->pcm_channels;i++)
 161         if(v->pcm[i])free(v->pcm[i]);
 162       free(v->pcm);
 163       free(v->pcmret);
 164     }
 165     if(v->multipliers){
 166       for(i=0;i<v->envelope_channels;i++)
 167         if(v->multipliers[i])free(v->multipliers[i]);
 168       free(v->multipliers);
 169     }
 170     _ve_envelope_clear(&v->ve);
 171     drft_clear(&v->vf[0]);
 172     drft_clear(&v->vf[1]);
 173     mdct_clear(&v->vm[0]);
 174     mdct_clear(&v->vm[1]);
 175     memset(v,0,sizeof(vorbis_dsp_state));
 176   }
 177 }
 178
 179 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
 180   int i;
 181
 182   /* Do we have enough storage space for the requested buffer? If not,
 183      expand the PCM (and envelope) storage */
 184
 185   if(v->pcm_current+vals>=v->pcm_storage){
 186     v->pcm_storage=v->pcm_current+vals*2;
 187     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 188
 189     for(i=0;i<v->pcm_channels;i++){
 190       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 191     }
 192     for(i=0;i<v->envelope_channels;i++){
 193       v->multipliers[i]=realloc(v->multipliers[i],
 194                                 v->envelope_storage*sizeof(double));
 195     }
 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 /* call with val<=0 to set eof */
 205
 206 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
 207   if(vals<=0){
 208     /* We're encoding the end of the stream.  Just make sure we have
 209        [at least] a full block of zeroes at the end. */
 210
 211     int i;
 212     vorbis_analysis_buffer(v,v->block_size[1]*2);
 213     v->eofflag=v->pcm_current;
 214     v->pcm_current+=v->block_size[1]*2;
 215     for(i=0;i<v->pcm_channels;i++)
 216       memset(v->pcm[i]+v->eofflag,0,
 217              (v->pcm_current-v->eofflag)*sizeof(double));
 218   }else{
 219
 220     if(v->pcm_current+vals>v->pcm_storage)
 221       return(-1);
 222
 223     v->pcm_current+=vals;
 224   }
 225   return(0);
 226 }
 227
 228 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
 229   int i;
 230   vb->pcm_storage=v->block_size[1];
 231   vb->pcm_channels=v->pcm_channels;
 232   vb->mult_storage=v->block_size[1]/v->samples_per_envelope_step;
 233   vb->mult_channels=v->envelope_channels;
 234
 235   vb->pcm=malloc(vb->pcm_channels*sizeof(double *));
 236   for(i=0;i<vb->pcm_channels;i++)
 237     vb->pcm[i]=malloc(vb->pcm_storage*sizeof(double));
 238
 239   vb->mult=malloc(vb->mult_channels*sizeof(double *));
 240   for(i=0;i<vb->mult_channels;i++)
 241     vb->mult[i]=malloc(vb->mult_storage*sizeof(double));
 242   return(0);
 243 }
 244
 245 int vorbis_block_clear(vorbis_block *vb){
 246   int i;
 247   if(vb->pcm){
 248     for(i=0;i<vb->pcm_channels;i++)
 249       free(vb->pcm[i]);
 250     free(vb->pcm);
 251   }
 252   if(vb->mult){
 253     for(i=0;i<vb->mult_channels;i++)
 254       free(vb->mult[i]);
 255     free(vb->mult);
 256   }
 257   memset(vb,0,sizeof(vorbis_block));
 258   return(0);
 259 }
 260
 261 /* do the deltas, envelope shaping, pre-echo and determine the size of
 262    the next block on which to continue analysis */
 263 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
 264   int i,j;
 265   long beginW=v->centerW-v->block_size[v->W]/2,centerNext;
 266   long beginM=beginW/v->samples_per_envelope_step;
 267
 268   /* check to see if we're done... */
 269   if(v->eofflag==-1)return(0);
 270
 271   /* if we have any unfilled envelope blocks for which we have PCM
 272      data, fill them up in before proceeding. */
 273
 274   if(v->pcm_current/v->samples_per_envelope_step>v->envelope_current){
 275     /* This generates the multipliers, but does not sparsify the vector.
 276        That's done by block before coding */
 277     _ve_envelope_multipliers(v);
 278   }
 279
 280   /* By our invariant, we have lW, W and centerW set.  Search for
 281      the next boundary so we can determine nW (the next window size)
 282      which lets us compute the shape of the current block's window */
 283
 284   /* overconserve for now; any block with a non-placeholder multiplier
 285      should be minimal size. We can be greedy and only look at nW size */
 286
 287   if(v->W)
 288     /* this is a long window; we start the search forward of centerW
 289        because that's the fastest we could react anyway */
 290     i=v->centerW+v->block_size[1]/4-v->block_size[0]/4;
 291   else
 292     /* short window.  Search from centerW */
 293     i=v->centerW;
 294   i/=v->samples_per_envelope_step;
 295
 296   for(;i<v->envelope_current;i++){
 297     for(j=0;j<v->envelope_channels;j++)
 298       if(v->multipliers[j][i-1]*v->vi.preecho_thresh<
 299          v->multipliers[j][i])break;
 300     if(j<v->envelope_channels)break;
 301   }
 302
 303   if(i<v->envelope_current){
 304     /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
 305        upcoming block large ? */
 306     long largebound;
 307     if(v->W)
 308       largebound=v->centerW+v->block_size[1];
 309     else
 310       largebound=v->centerW+v->block_size[0]/4+v->block_size[1]*3/4;
 311     largebound/=v->samples_per_envelope_step;
 312
 313     if(i>=largebound)
 314       v->nW=1;
 315     else
 316       v->nW=0;
 317
 318   }else{
 319     /* Assume maximum; if the block is incomplete given current
 320        buffered data, this will be detected below */
 321     v->nW=1;
 322   }
 323
 324   /* Do we actually have enough data *now* for the next block? The
 325      reason to check is that if we had no multipliers, that could
 326      simply been due to running out of data.  In that case, we don;t
 327      know the size of the next block for sure and we need that now to
 328      figure out the window shape of this block */
 329
 330   centerNext=v->centerW+v->block_size[v->W]/4+v->block_size[v->nW]/4;
 331
 332   {
 333     long blockbound=centerNext+v->block_size[v->nW]/2;
 334     if(v->pcm_current<blockbound)return(0); /* not enough data yet */
 335   }
 336
 337   /* fill in the block */
 338   vb->lW=v->lW;
 339   vb->W=v->W;
 340   vb->nW=v->nW;
 341   vb->vd=v;
 342
 343   vb->pcmend=v->block_size[v->W];
 344   vb->multend=vb->pcmend / v->samples_per_envelope_step;
 345
 346   if(v->pcm_channels!=vb->pcm_channels ||
 347      v->block_size[1]!=vb->pcm_storage ||
 348      v->envelope_channels!=vb->mult_channels){
 349
 350     /* Storage not initialized or initilized for some other codec
 351        instance with different settings */
 352
 353     vorbis_block_clear(vb);
 354     vorbis_block_init(v,vb);
 355   }
 356
 357   /* copy the vectors */
 358   for(i=0;i<v->pcm_channels;i++)
 359     memcpy(vb->pcm[i],v->pcm[i]+beginW,v->block_size[v->W]*sizeof(double));
 360   for(i=0;i<v->envelope_channels;i++)
 361     memcpy(vb->mult[i],v->multipliers[i]+beginM,v->block_size[v->W]/
 362            v->samples_per_envelope_step*sizeof(double));
 363
 364   vb->frameno=v->frame;
 365
 366   /* handle eof detection: eof==0 means that we've not yet received EOF
 367                            eof>0  marks the last 'real' sample in pcm[]
 368                            eof<0  'no more to do'; doesn't get here */
 369
 370   if(v->eofflag){
 371     if(v->centerW>=v->eofflag){
 372       v->eofflag=-1;
 373       vb->eofflag=1;
 374     }
 375   }
 376
 377   /* advance storage vectors and clean up */
 378   {
 379     int new_centerNext=v->block_size[1]/2;
 380     int movementW=centerNext-new_centerNext;
 381     int movementM=movementW/v->samples_per_envelope_step;
 382
 383     /* the multipliers and pcm stay synced up because the blocksizes
 384        must be multiples of samples_per_envelope_step (minimum
 385        multiple is 2) */
 386
 387     for(i=0;i<v->pcm_channels;i++)
 388       memmove(v->pcm[i],v->pcm[i]+movementW,
 389               (v->pcm_current-movementW)*sizeof(double));
 390
 391     for(i=0;i<v->envelope_channels;i++){
 392       memmove(v->multipliers[i],v->multipliers[i]+movementM,
 393               (v->envelope_current-movementM)*sizeof(double));
 394     }
 395
 396     v->pcm_current-=movementW;
 397     v->envelope_current-=movementM;
 398
 399     v->lW=v->W;
 400     v->W=v->nW;
 401     v->centerW=new_centerNext;
 402
 403     v->frame++;
 404     v->samples+=movementW;
 405
 406     if(v->eofflag)
 407       v->eofflag-=movementW;
 408   }
 409
 410   /* done */
 411   return(1);
 412 }
 413
 414 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
 415   int temp=vi->envelopech;
 416   vi->envelopech=0; /* we don't need multiplier buffering in syn */
 417   _vds_shared_init(v,vi);
 418   vi->envelopech=temp;
 419
 420   /* Adjust centerW to allow an easier mechanism for determining output */
 421   v->pcm_returned=v->centerW;
 422   v->centerW-= v->block_size[v->W]/4+v->block_size[v->lW]/4;
 423   return(0);
 424 }
 425
 426 /* Unike in analysis, the window is only partially applied.  Envelope
 427    is previously applied (the whole envelope, if any, is shipped in
 428    each block) */
 429
 430 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
 431
 432   /* Shift out any PCM that we returned previously */
 433
 434   if(v->pcm_returned  && v->centerW>v->block_size[1]/2){
 435
 436     /* don't shift too much; we need to have a minimum PCM buffer of
 437        1/2 long block */
 438
 439     int shift=v->centerW-v->block_size[1]/2;
 440     shift=(v->pcm_returned<shift?v->pcm_returned:shift);
 441
 442     v->pcm_current-=shift;
 443     v->centerW-=shift;
 444     v->pcm_returned-=shift;
 445
 446     if(shift){
 447       int i;
 448       for(i=0;i<v->pcm_channels;i++)
 449         memmove(v->pcm[i],v->pcm[i]+shift,
 450                 v->pcm_current*sizeof(double));
 451     }
 452   }
 453
 454   {
 455     int sizeW=v->block_size[vb->W];
 456     int centerW=v->centerW+v->block_size[vb->lW]/4+sizeW/4;
 457     int beginW=centerW-sizeW/2;
 458     int endW=beginW+sizeW;
 459     int beginSl;
 460     int endSl;
 461     int i,j;
 462     double *window;
 463
 464     /* Do we have enough PCM storage for the block? */
 465     if(endW>v->pcm_storage){
 466       /* expand the PCM storage */
 467
 468       v->pcm_storage=endW+v->block_size[1];
 469
 470       for(i=0;i<v->pcm_channels;i++)
 471         v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 472     }
 473
 474     /* Overlap/add */
 475     switch(vb->W){
 476     case 0:
 477       beginSl=0;
 478       endSl=v->block_size[0]/2;
 479       break;
 480     case 1:
 481       beginSl=v->block_size[1]/4-v->block_size[vb->lW]/4;
 482       endSl=beginSl+v->block_size[vb->lW]/2;
 483       break;
 484     }
 485
 486     window=v->window[vb->W][0][vb->lW]+v->block_size[vb->W]/2;
 487
 488     for(j=0;j<v->pcm_channels;j++){
 489       double *pcm=v->pcm[j]+beginW;
 490
 491       /* the add section */
 492       for(i=beginSl;i<endSl;i++)
 493         pcm[i]=pcm[i]*window[i]+vb->pcm[j][i];
 494       /* the remaining section */
 495       for(;i<sizeW;i++)
 496         pcm[i]=vb->pcm[j][i];
 497     }
 498
 499     /* Update, cleanup */
 500
 501     v->centerW=centerW;
 502     v->pcm_current=endW;
 503
 504     if(vb->eofflag)v->eofflag=1;
 505   }
 506   return(0);
 507 }
 508
 509 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
 510   if(v->pcm_returned<v->centerW){
 511     int i;
 512     for(i=0;i<v->pcm_channels;i++)
 513       v->pcmret[i]=v->pcm[i]+v->pcm_returned;
 514     *pcm=v->pcmret;
 515     return(v->centerW-v->pcm_returned);
 516   }
 517   return(0);
 518 }
 519
 520 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
 521   if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
 522   v->pcm_returned+=bytes;
 523   return(0);
 524 }
 525