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
 146   /* Yes, wasteful to have four lookups.  This will get collapsed once
 147      things crystallize */
 148   lpc_init(&v->vl[0],vi->smallblock/2,vi->smallblock/2,
 149            vi->floororder,vi->flooroctaves,1);
 150   lpc_init(&v->vl[1],vi->largeblock/2,vi->largeblock/2,
 151            vi->floororder,vi->flooroctaves,1);
 152
 153   lpc_init(&v->vbal[0],vi->smallblock/2,256,
 154            vi->balanceorder,vi->balanceoctaves,1);
 155   lpc_init(&v->vbal[1],vi->largeblock/2,256,
 156            vi->balanceorder,vi->balanceoctaves,1);
 157
 158   return(0);
 159 }
 160
 161 void vorbis_analysis_clear(vorbis_dsp_state *v){
 162   int i,j,k;
 163   if(v){
 164
 165     if(v->window[0][0][0])free(v->window[0][0][0]);
 166     for(j=0;j<2;j++)
 167       for(k=0;k<2;k++)
 168         if(v->window[1][j][k])free(v->window[1][j][k]);
 169     if(v->pcm){
 170       for(i=0;i<v->pcm_channels;i++)
 171         if(v->pcm[i])free(v->pcm[i]);
 172       free(v->pcm);
 173       free(v->pcmret);
 174     }
 175     if(v->multipliers){
 176       for(i=0;i<v->envelope_channels;i++)
 177         if(v->multipliers[i])free(v->multipliers[i]);
 178       free(v->multipliers);
 179     }
 180     _ve_envelope_clear(&v->ve);
 181     mdct_clear(&v->vm[0]);
 182     mdct_clear(&v->vm[1]);
 183     memset(v,0,sizeof(vorbis_dsp_state));
 184   }
 185 }
 186
 187 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
 188   int i;
 189
 190   /* Do we have enough storage space for the requested buffer? If not,
 191      expand the PCM (and envelope) storage */
 192
 193   if(v->pcm_current+vals>=v->pcm_storage){
 194     v->pcm_storage=v->pcm_current+vals*2;
 195     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 196
 197     for(i=0;i<v->pcm_channels;i++){
 198       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 199     }
 200     for(i=0;i<v->envelope_channels;i++){
 201       v->multipliers[i]=realloc(v->multipliers[i],
 202                                 v->envelope_storage*sizeof(double));
 203     }
 204   }
 205
 206   for(i=0;i<v->pcm_channels;i++)
 207     v->pcmret[i]=v->pcm[i]+v->pcm_current;
 208
 209   return(v->pcmret);
 210 }
 211
 212 /* call with val<=0 to set eof */
 213
 214 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
 215   if(vals<=0){
 216     /* We're encoding the end of the stream.  Just make sure we have
 217        [at least] a full block of zeroes at the end. */
 218
 219     int i;
 220     vorbis_analysis_buffer(v,v->block_size[1]*2);
 221     v->eofflag=v->pcm_current;
 222     v->pcm_current+=v->block_size[1]*2;
 223     for(i=0;i<v->pcm_channels;i++)
 224       memset(v->pcm[i]+v->eofflag,0,
 225              (v->pcm_current-v->eofflag)*sizeof(double));
 226   }else{
 227
 228     if(v->pcm_current+vals>v->pcm_storage)
 229       return(-1);
 230
 231     v->pcm_current+=vals;
 232   }
 233   return(0);
 234 }
 235
 236 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
 237   int i;
 238   memset(vb,0,sizeof(vorbis_block));
 239   vb->pcm_storage=v->block_size[1];
 240   vb->pcm_channels=v->pcm_channels;
 241   vb->mult_storage=v->block_size[1]/v->samples_per_envelope_step;
 242   vb->mult_channels=v->envelope_channels;
 243   vb->floor_channels=v->vi.floorch;
 244   vb->floor_storage=v->vi.floororder;
 245
 246   vb->pcm=malloc(vb->pcm_channels*sizeof(double *));
 247   for(i=0;i<vb->pcm_channels;i++)
 248     vb->pcm[i]=malloc(vb->pcm_storage*sizeof(double));
 249
 250   vb->mult=malloc(vb->mult_channels*sizeof(double *));
 251   for(i=0;i<vb->mult_channels;i++)
 252     vb->mult[i]=malloc(vb->mult_storage*sizeof(double));
 253
 254   vb->lsp=malloc(vb->floor_channels*sizeof(double *));
 255   vb->lpc=malloc(vb->floor_channels*sizeof(double *));
 256   vb->amp=malloc(vb->floor_channels*sizeof(double));
 257   for(i=0;i<vb->floor_channels;i++){
 258     vb->lsp[i]=malloc(vb->floor_storage*sizeof(double));
 259     vb->lpc[i]=malloc(vb->floor_storage*sizeof(double));
 260   }
 261
 262   return(0);
 263 }
 264
 265 int vorbis_block_clear(vorbis_block *vb){
 266   int i;
 267   if(vb->pcm){
 268     for(i=0;i<vb->pcm_channels;i++)
 269       free(vb->pcm[i]);
 270     free(vb->pcm);
 271   }
 272   if(vb->mult){
 273     for(i=0;i<vb->mult_channels;i++)
 274       free(vb->mult[i]);
 275     free(vb->mult);
 276   }
 277   memset(vb,0,sizeof(vorbis_block));
 278   return(0);
 279 }
 280
 281 /* do the deltas, envelope shaping, pre-echo and determine the size of
 282    the next block on which to continue analysis */
 283 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
 284   int i,j;
 285   long beginW=v->centerW-v->block_size[v->W]/2,centerNext;
 286   long beginM=beginW/v->samples_per_envelope_step;
 287
 288   /* check to see if we're done... */
 289   if(v->eofflag==-1)return(0);
 290
 291   /* if we have any unfilled envelope blocks for which we have PCM
 292      data, fill them up in before proceeding. */
 293
 294   if(v->pcm_current/v->samples_per_envelope_step>v->envelope_current){
 295     /* This generates the multipliers, but does not sparsify the vector.
 296        That's done by block before coding */
 297     _ve_envelope_multipliers(v);
 298   }
 299
 300   /* By our invariant, we have lW, W and centerW set.  Search for
 301      the next boundary so we can determine nW (the next window size)
 302      which lets us compute the shape of the current block's window */
 303
 304   /* overconserve for now; any block with a non-placeholder multiplier
 305      should be minimal size. We can be greedy and only look at nW size */
 306
 307   if(v->vi.smallblock<v->vi.largeblock){
 308
 309     if(v->W)
 310       /* this is a long window; we start the search forward of centerW
 311          because that's the fastest we could react anyway */
 312       i=v->centerW+v->block_size[1]/4-v->block_size[0]/4;
 313     else
 314       /* short window.  Search from centerW */
 315       i=v->centerW;
 316     i/=v->samples_per_envelope_step;
 317
 318     for(;i<v->envelope_current;i++){
 319       for(j=0;j<v->envelope_channels;j++)
 320         if(v->multipliers[j][i-1]*v->vi.preecho_thresh<
 321            v->multipliers[j][i])break;
 322       if(j<v->envelope_channels)break;
 323     }
 324
 325     if(i<v->envelope_current){
 326       /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
 327          upcoming block large ? */
 328       long largebound;
 329       if(v->W)
 330         largebound=v->centerW+v->block_size[1];
 331       else
 332         largebound=v->centerW+v->block_size[0]/4+v->block_size[1]*3/4;
 333       largebound/=v->samples_per_envelope_step;
 334
 335       if(i>=largebound)
 336         v->nW=1;
 337       else
 338         v->nW=0;
 339
 340     }else{
 341       /* Assume maximum; if the block is incomplete given current
 342          buffered data, this will be detected below */
 343       v->nW=1;
 344     }
 345   }else
 346     v->nW=1;
 347     v->nW=1;
 348
 349   /* Do we actually have enough data *now* for the next block? The
 350      reason to check is that if we had no multipliers, that could
 351      simply been due to running out of data.  In that case, we don;t
 352      know the size of the next block for sure and we need that now to
 353      figure out the window shape of this block */
 354
 355   centerNext=v->centerW+v->block_size[v->W]/4+v->block_size[v->nW]/4;
 356
 357   {
 358     long blockbound=centerNext+v->block_size[v->nW]/2;
 359     if(v->pcm_current<blockbound)return(0); /* not enough data yet */
 360   }
 361
 362   /* fill in the block */
 363   vb->lW=v->lW;
 364   vb->W=v->W;
 365   vb->nW=v->nW;
 366   vb->vd=v;
 367
 368   vb->pcmend=v->block_size[v->W];
 369   vb->multend=vb->pcmend / v->samples_per_envelope_step;
 370
 371   if(vb->floor_channels!=v->vi.floorch ||
 372      vb->floor_storage!=v->vi.floororder ||
 373      v->pcm_channels!=vb->pcm_channels ||
 374      v->block_size[1]!=vb->pcm_storage ||
 375      v->envelope_channels!=vb->mult_channels){
 376
 377     /* Storage not initialized or initilized for some other codec
 378        instance with different settings */
 379
 380     vorbis_block_clear(vb);
 381     vorbis_block_init(v,vb);
 382   }
 383
 384   /* copy the vectors */
 385   for(i=0;i<v->pcm_channels;i++)
 386     memcpy(vb->pcm[i],v->pcm[i]+beginW,v->block_size[v->W]*sizeof(double));
 387   for(i=0;i<v->envelope_channels;i++)
 388     memcpy(vb->mult[i],v->multipliers[i]+beginM,v->block_size[v->W]/
 389            v->samples_per_envelope_step*sizeof(double));
 390
 391   vb->frameno=v->frame;
 392
 393   /* handle eof detection: eof==0 means that we've not yet received EOF
 394                            eof>0  marks the last 'real' sample in pcm[]
 395                            eof<0  'no more to do'; doesn't get here */
 396
 397   if(v->eofflag){
 398     if(v->centerW>=v->eofflag){
 399       v->eofflag=-1;
 400       vb->eofflag=1;
 401     }
 402   }
 403
 404   /* advance storage vectors and clean up */
 405   {
 406     int new_centerNext=v->block_size[1]/2;
 407     int movementW=centerNext-new_centerNext;
 408     int movementM=movementW/v->samples_per_envelope_step;
 409
 410     /* the multipliers and pcm stay synced up because the blocksizes
 411        must be multiples of samples_per_envelope_step (minimum
 412        multiple is 2) */
 413
 414     for(i=0;i<v->pcm_channels;i++)
 415       memmove(v->pcm[i],v->pcm[i]+movementW,
 416               (v->pcm_current-movementW)*sizeof(double));
 417
 418     for(i=0;i<v->envelope_channels;i++){
 419       memmove(v->multipliers[i],v->multipliers[i]+movementM,
 420               (v->envelope_current-movementM)*sizeof(double));
 421     }
 422
 423     v->pcm_current-=movementW;
 424     v->envelope_current-=movementM;
 425
 426     v->lW=v->W;
 427     v->W=v->nW;
 428     v->centerW=new_centerNext;
 429
 430     v->frame++;
 431     v->samples+=movementW;
 432
 433     if(v->eofflag)
 434       v->eofflag-=movementW;
 435   }
 436
 437   /* done */
 438   return(1);
 439 }
 440
 441 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
 442   int temp=vi->envelopech;
 443   vi->envelopech=0; /* we don't need multiplier buffering in syn */
 444   _vds_shared_init(v,vi);
 445   vi->envelopech=temp;
 446
 447   /* Yes, wasteful to have four lookups.  This will get collapsed once
 448      things crystallize */
 449   lpc_init(&v->vl[0],vi->smallblock/2,vi->smallblock/2,
 450            vi->floororder,vi->flooroctaves,0);
 451   lpc_init(&v->vl[1],vi->largeblock/2,vi->largeblock/2,
 452            vi->floororder,vi->flooroctaves,0);
 453   lpc_init(&v->vbal[0],vi->smallblock/2,256,
 454            vi->balanceorder,vi->balanceoctaves,0);
 455   lpc_init(&v->vbal[1],vi->largeblock/2,256,
 456            vi->balanceorder,vi->balanceoctaves,0);
 457
 458
 459   /* Adjust centerW to allow an easier mechanism for determining output */
 460   v->pcm_returned=v->centerW;
 461   v->centerW-= v->block_size[v->W]/4+v->block_size[v->lW]/4;
 462   return(0);
 463 }
 464
 465 /* Unike in analysis, the window is only partially applied.  Envelope
 466    is previously applied (the whole envelope, if any, is shipped in
 467    each block) */
 468
 469 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
 470
 471   /* Shift out any PCM that we returned previously */
 472
 473   if(v->pcm_returned  && v->centerW>v->block_size[1]/2){
 474
 475     /* don't shift too much; we need to have a minimum PCM buffer of
 476        1/2 long block */
 477
 478     int shift=v->centerW-v->block_size[1]/2;
 479     shift=(v->pcm_returned<shift?v->pcm_returned:shift);
 480
 481     v->pcm_current-=shift;
 482     v->centerW-=shift;
 483     v->pcm_returned-=shift;
 484
 485     if(shift){
 486       int i;
 487       for(i=0;i<v->pcm_channels;i++)
 488         memmove(v->pcm[i],v->pcm[i]+shift,
 489                 v->pcm_current*sizeof(double));
 490     }
 491   }
 492
 493   {
 494     int sizeW=v->block_size[vb->W];
 495     int centerW=v->centerW+v->block_size[vb->lW]/4+sizeW/4;
 496     int beginW=centerW-sizeW/2;
 497     int endW=beginW+sizeW;
 498     int beginSl;
 499     int endSl;
 500     int i,j;
 501     double *window;
 502
 503     /* Do we have enough PCM storage for the block? */
 504     if(endW>v->pcm_storage){
 505       /* expand the PCM storage */
 506
 507       v->pcm_storage=endW+v->block_size[1];
 508
 509       for(i=0;i<v->pcm_channels;i++)
 510         v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 511     }
 512
 513     /* Overlap/add */
 514     switch(vb->W){
 515     case 0:
 516       beginSl=0;
 517       endSl=v->block_size[0]/2;
 518       break;
 519     case 1:
 520       beginSl=v->block_size[1]/4-v->block_size[vb->lW]/4;
 521       endSl=beginSl+v->block_size[vb->lW]/2;
 522       break;
 523     }
 524
 525     window=v->window[vb->W][0][vb->lW]+v->block_size[vb->W]/2;
 526
 527     for(j=0;j<v->pcm_channels;j++){
 528       double *pcm=v->pcm[j]+beginW;
 529
 530       /* the add section */
 531       for(i=beginSl;i<endSl;i++)
 532         pcm[i]=pcm[i]*window[i]+vb->pcm[j][i];
 533       /* the remaining section */
 534       for(;i<sizeW;i++)
 535         pcm[i]=vb->pcm[j][i];
 536     }
 537
 538     /* Update, cleanup */
 539
 540     v->centerW=centerW;
 541     v->pcm_current=endW;
 542
 543     if(vb->eofflag)v->eofflag=1;
 544   }
 545   return(0);
 546 }
 547
 548 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
 549   if(v->pcm_returned<v->centerW){
 550     int i;
 551     for(i=0;i<v->pcm_channels;i++)
 552       v->pcmret[i]=v->pcm[i]+v->pcm_returned;
 553     *pcm=v->pcmret;
 554     return(v->centerW-v->pcm_returned);
 555   }
 556   return(0);
 557 }
 558
 559 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
 560   if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
 561   v->pcm_returned+=bytes;
 562   return(0);
 563 }
 564