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: 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 #include "window.h"
  33 #include "envelope.h"
  34
  35 /* pcm accumulator and multipliers
  36    examples (not exhaustive):
  37
  38  <-------------- lW----------------->
  39                    <--------------- W ---------------->
  40 :            .....|.....       _______________         |
  41 :        .'''     |     '''_---      |       |\        |
  42 :.....'''         |_____--- '''......|       | \_______|
  43 :.................|__________________|_______|__|______|
  44                   |<------ Sl ------>|      > Sr <     |endW
  45                   |beginSl           |endSl  |  |endSr
  46                   |beginW            |endlW  |beginSr
  47                   mult[0]                              mult[n]
  48
  49
  50                       |< lW >|
  51                    <--------------- W ---------------->
  52                   |   |  ..  ______________            |
  53                   |   | '  `/        |     ---_        |
  54                   |___.'___/`.       |         ---_____|
  55                   |_______|__|_______|_________________|
  56                   |      >|Sl|<      |<------ Sr ----->|endW
  57                   |       |  |endSl  |beginSr          |endSr
  58                   |beginW |  |endlW
  59                   mult[0] |beginSl                     mult[n]
  60
  61  <-------------- lW----------------->
  62                           |<-W-->|
  63 :            ..............  __  |   |
  64 :        .'''             |`/  \ |   |
  65 :.....'''                 |/`...\|...|
  66 :.........................|__||__|___|
  67                           |Sl||Sr|endW
  68                           |  ||  |endSr
  69                           |  ||beginSr
  70                           |  |endSl
  71                           |beginSl
  72                           |beginW
  73                           mult[0]
  74                                  mult[n]
  75 */
  76
  77 /* arbitrary settings and spec-mandated numbers get filled in here */
  78 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
  79   memset(v,0,sizeof(vorbis_dsp_state));
  80   v->samples_per_envelope_step=64;
  81   v->block_size[0]=512;
  82   v->block_size[1]=2048;
  83
  84   v->window[0][0][0]=_vorbis_window(v->block_size[0],
  85                                    v->block_size[0]/2,v->block_size[0]/2);
  86   v->window[0][0][1]=v->window[0][0][0];
  87   v->window[0][1][0]=v->window[0][0][0];
  88   v->window[0][1][1]=v->window[0][0][0];
  89
  90   v->window[1][0][0]=_vorbis_window(v->block_size[1],
  91                                    v->block_size[0]/2,v->block_size[0]/2);
  92   v->window[1][0][1]=_vorbis_window(v->block_size[1],
  93                                    v->block_size[0]/2,v->block_size[1]/2);
  94   v->window[1][1][0]=_vorbis_window(v->block_size[1],
  95                                    v->block_size[1]/2,v->block_size[0]/2);
  96   v->window[1][1][1]=_vorbis_window(v->block_size[1],
  97                                     v->block_size[1]/2,v->block_size[1]/2);
  98
  99   /* initialize the storage vectors to a decent size greater than the
 100      minimum */
 101
 102   v->pcm_storage=8192; /* we'll assume later that we have
 103                           a minimum of twice the blocksize of
 104                           accumulated samples in analysis */
 105   v->pcm_channels=v->vi.channels=vi->channels;
 106   v->pcm=malloc(vi->channels*sizeof(double *));
 107   v->pcmret=malloc(vi->channels*sizeof(double *));
 108   {
 109     int i;
 110     for(i=0;i<vi->channels;i++)
 111       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
 112   }
 113
 114   /* Initialize the envelope multiplier storage */
 115
 116   v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 117   v->envelope_channels=vi->channels;
 118   v->deltas=calloc(v->envelope_channels,sizeof(double *));
 119   v->multipliers=calloc(v->envelope_channels,sizeof(int *));
 120   {
 121     int i;
 122     for(i=0;i<v->envelope_channels;i++){
 123       v->deltas[i]=calloc(v->envelope_storage,sizeof(double));
 124       v->multipliers[i]=calloc(v->envelope_storage,sizeof(int));
 125     }
 126   }
 127
 128   /* all 1 (large block) or 0 (small block) */
 129   /* explicitly set for the sake of clarity */
 130   v->lW=0; /* previous window size */
 131   v->W=0;  /* current window size */
 132
 133   /* all vector indexes; multiples of samples_per_envelope_step */
 134   v->centerW=v->block_size[1]/2;
 135
 136   v->pcm_current=v->centerW;
 137   v->envelope_current=v->centerW/v->samples_per_envelope_step;
 138   return(0);
 139 }
 140
 141 void vorbis_analysis_clear(vorbis_dsp_state *v){
 142   int i,j,k;
 143   if(v){
 144
 145     if(v->window[0][0][0])free(v->window[0][0][0]);
 146     for(j=0;j<2;j++)
 147       for(k=0;k<2;k++)
 148         if(v->window[1][j][k])free(v->window[1][j][k]);
 149     if(v->pcm){
 150       for(i=0;i<v->pcm_channels;i++)
 151         if(v->pcm[i])free(v->pcm[i]);
 152       free(v->pcm);
 153       free(v->pcmret);
 154     }
 155     if(v->deltas){
 156       for(i=0;i<v->envelope_channels;i++)
 157         if(v->deltas[i])free(v->deltas[i]);
 158       free(v->deltas);
 159     }
 160     if(v->multipliers){
 161       for(i=0;i<v->envelope_channels;i++)
 162         if(v->multipliers[i])free(v->multipliers[i]);
 163       free(v->multipliers);
 164     }
 165     memset(v,0,sizeof(vorbis_dsp_state));
 166   }
 167 }
 168
 169 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
 170   int i;
 171
 172   /* Do we have enough storage space for the requested buffer? If not,
 173      expand the PCM (and envelope) storage */
 174
 175   if(v->pcm_current+vals>=v->pcm_storage){
 176     v->pcm_storage=v->pcm_current+vals*2;
 177     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
 178
 179     for(i=0;i<v->pcm_channels;i++){
 180       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
 181       v->deltas[i]=realloc(v->deltas[i],v->envelope_storage*sizeof(double));
 182       v->multipliers[i]=realloc(v->multipliers[i],
 183                                 v->envelope_storage*sizeof(double));
 184
 185     }
 186   }
 187
 188   for(i=0;i<v->pcm_channels;i++)
 189     v->pcmret[i]=v->pcm[i]+v->pcm_current;
 190
 191   return(v->pcmret);
 192 }
 193
 194 /* call with val<=0 to set eof */
 195
 196 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
 197   if(vals<=0){
 198     /* We're encoding the end of the stream.  Just make sure we have
 199        [at least] a full block of zeroes at the end. */
 200
 201     int i;
 202     vorbis_analysis_buffer(v,v->block_size[1]*2);
 203     v->eofflag=v->pcm_current;
 204     v->pcm_current+=v->block_size[1]*2;
 205     for(i=0;i<v->pcm_channels;i++)
 206       memset(v->pcm[i]+v->eofflag,0,
 207              (v->pcm_current-v->eofflag)*sizeof(double));
 208   }else{
 209
 210     if(v->pcm_current+vals>v->pcm_storage)
 211       return(-1);
 212
 213     v->pcm_current+=vals;
 214   }
 215   return(0);
 216 }
 217
 218 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
 219   int i;
 220   vb->pcm_storage=v->block_size[1];
 221   vb->pcm_channels=v->pcm_channels;
 222   vb->mult_storage=v->block_size[1]/v->samples_per_envelope_step;
 223   vb->mult_channels=v->envelope_channels;
 224
 225   vb->pcm=malloc(vb->pcm_channels*sizeof(double *));
 226   for(i=0;i<vb->pcm_channels;i++)
 227     vb->pcm[i]=malloc(vb->pcm_storage*sizeof(double));
 228
 229   vb->mult=malloc(vb->mult_channels*sizeof(int *));
 230   for(i=0;i<vb->mult_channels;i++)
 231     vb->mult[i]=malloc(vb->mult_storage*sizeof(int));
 232   return(0);
 233 }
 234
 235 int vorbis_block_clear(vorbis_block *vb){
 236   int i;
 237   if(vb->pcm){
 238     for(i=0;i<vb->pcm_channels;i++)
 239       free(vb->pcm[i]);
 240     free(vb->pcm);
 241   }
 242   if(vb->mult){
 243     for(i=0;i<vb->mult_channels;i++)
 244       free(vb->mult[i]);
 245     free(vb->mult);
 246   }
 247   memset(vb,0,sizeof(vorbis_block));
 248   return(0);
 249 }
 250
 251 /* do the deltas, envelope shaping, pre-echo and determine the size of
 252    the next block on which to continue analysis */
 253 int vorbis_analysis_block(vorbis_dsp_state *v,vorbis_block *vb){
 254   int i,j;
 255   long beginW=v->centerW-v->block_size[v->W]/2,centerNext;
 256   long beginM=beginW/v->samples_per_envelope_step;
 257
 258   /* check to see if we're done... */
 259   if(v->eofflag==-1)return(0);
 260
 261   /* if we have any unfilled envelope blocks for which we have PCM
 262      data, fill them up in before proceeding. */
 263
 264   if(v->pcm_current/v->samples_per_envelope_step>v->envelope_current){
 265     _va_envelope_deltas(v);
 266     _va_envelope_multipliers(v);
 267   }
 268
 269   /* By our invariant, we have lW, W and centerW set.  Search for
 270      the next boundary so we can determine nW (the next window size)
 271      which lets us compute the shape of the current block's window */
 272
 273   /* overconserve for now; any block with a non-placeholder multiplier
 274      should be minimal size. We can be greedy and only look at nW size */
 275
 276   if(v->W)
 277     /* this is a long window; we start the search forward of centerW
 278        because that's the fastest we could react anyway */
 279     i=v->centerW+v->block_size[1]/4-v->block_size[0]/4;
 280   else
 281     /* short window.  Search from centerW */
 282     i=v->centerW;
 283   i/=v->samples_per_envelope_step;
 284
 285   for(;i<v->envelope_current;i++){
 286     for(j=0;j<v->envelope_channels;j++)
 287       if(v->multipliers[j][i])break;
 288     if(j<v->envelope_channels)break;
 289   }
 290
 291   if(i<v->envelope_current){
 292     /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
 293        upcoming block large ? */
 294     long largebound;
 295     if(v->W)
 296       largebound=v->centerW+v->block_size[1];
 297     else
 298       largebound=v->centerW+v->block_size[0]/4+v->block_size[1]*3/4;
 299     largebound/=v->samples_per_envelope_step;
 300
 301     if(i>=largebound)
 302       v->nW=1;
 303     else
 304       v->nW=0;
 305
 306   }else{
 307     /* Assume maximum; if the block is incomplete given current
 308        buffered data, this will be detected below */
 309     v->nW=1;
 310   }
 311
 312   /* Do we actually have enough data *now* for the next block? The
 313      reason to check is that if we had no multipliers, that could
 314      simply been due to running out of data.  In that case, we don;t
 315      know the size of the next block for sure and we need that now to
 316      figure out the window shape of this block */
 317
 318   centerNext=v->centerW+v->block_size[v->W]/4+v->block_size[v->nW]/4;
 319
 320   {
 321     long blockbound=centerNext+v->block_size[v->nW]/2;
 322     if(v->pcm_current<blockbound)return(0); /* not enough data yet */
 323   }
 324
 325   /* fill in the block */
 326   vb->lW=v->lW;
 327   vb->W=v->W;
 328   vb->nW=v->nW;
 329   vb->vd=v;
 330
 331   vb->pcmend=v->block_size[v->W];
 332   vb->multend=vb->pcmend / v->samples_per_envelope_step;
 333
 334   if(v->pcm_channels!=vb->pcm_channels ||
 335      v->block_size[1]!=vb->pcm_storage ||
 336      v->envelope_channels!=vb->mult_channels){
 337
 338     /* Storage not initialized or initilized for some other codec
 339        instance with different settings */
 340
 341     vorbis_block_clear(vb);
 342     vorbis_block_init(v,vb);
 343   }
 344
 345   /* copy the vectors */
 346   for(i=0;i<v->pcm_channels;i++)
 347     memcpy(vb->pcm[i],v->pcm[i]+beginW,v->block_size[v->W]*sizeof(double));
 348   for(i=0;i<v->envelope_channels;i++)
 349     memcpy(vb->mult[i],v->multipliers[i]+beginM,v->block_size[v->W]/
 350            v->samples_per_envelope_step*sizeof(int));
 351
 352   vb->frameno=v->frame;
 353
 354   /* handle eof detection: eof==0 means that we've not yet received EOF
 355                            eof>0  marks the last 'real' sample in pcm[]
 356                            eof<0  'no more to do'; doesn't get here */
 357
 358   if(v->eofflag){
 359     if(v->centerW>=v->eofflag){
 360       v->eofflag=-1;
 361       vb->eofflag=1;
 362     }
 363   }
 364
 365   /* advance storage vectors and clean up */
 366   {
 367     int new_centerNext=v->block_size[1]/2;
 368     int movementW=centerNext-new_centerNext;
 369     int movementM=movementW/v->samples_per_envelope_step;
 370
 371     for(i=0;i<v->pcm_channels;i++)
 372       memmove(v->pcm[i],v->pcm[i]+movementW,
 373               (v->pcm_current-movementW)*sizeof(double));
 374
 375     for(i=0;i<v->envelope_channels;i++){
 376       memmove(v->deltas[i],v->deltas[i]+movementM,
 377               (v->envelope_current-movementM)*sizeof(double));
 378       memmove(v->multipliers[i],v->multipliers[i]+movementM,
 379               (v->envelope_current-movementM)*sizeof(int));
 380     }
 381
 382     v->pcm_current-=movementW;
 383     v->envelope_current-=movementM;
 384
 385     v->lW=v->W;
 386     v->W=v->nW;
 387     v->centerW=new_centerNext;
 388
 389     v->frame++;
 390     v->samples+=movementW;
 391
 392     if(v->eofflag)
 393       v->eofflag-=movementW;
 394   }
 395
 396   /* done */
 397   return(1);
 398 }
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409 int vorbis_analysis_packetout(vorbis_dsp_state *v, vorbis_block *vb,
 410                               ogg_packet *op){
 411
 412   /* find block's envelope vector and apply it */
 413
 414
 415   /* the real analysis begins; forward MDCT with window */
 416
 417
 418   /* Noise floor, resolution floor */
 419
 420   /* encode the floor into LSP; get the actual floor back for quant */
 421
 422   /* use noise floor, res floor for culling, actual floor for quant */
 423
 424   /* encode residue */
 425
 426 }
 427
 428
 429
 430 #ifdef _V_SELFTEST
 431 #include <stdio.h>
 432 #include <math.h>
 433
 434 void _va_envelope_deltas(vorbis_dsp_state *v){
 435   /* do nothing... */
 436 }
 437
 438 void _va_envelope_multipliers(vorbis_dsp_state *v){
 439   /* set 'random' deltas... */
 440   int new_current=v->pcm_current/v->samples_per_envelope_step;
 441   int i,j;
 442
 443   for(i=v->envelope_current;i<new_current;i++){
 444     int flag=0;
 445     for(j=0;j<v->samples_per_envelope_step;j++)
 446       if(v->pcm[0][j+i*v->samples_per_envelope_step]>5)flag=1;
 447
 448     for(j=0;j<v->envelope_channels;j++)
 449       v->multipliers[j][i]=flag;
 450   }
 451   v->envelope_current=i;
 452 }
 453
 454
 455 /* basic test of PCM blocking:
 456
 457    construct a PCM vector and block it using preset sizing in our fake
 458    delta/multiplier generation.  Immediately hand the block over to
 459    'synthesis' and rebuild it. */
 460
 461 int main(){
 462   int blocksize=1024;
 463   int fini=5000*1024;
 464   vorbis_dsp_state encode,decode;
 465   vorbis_info vi;
 466   vorbis_block vb;
 467   long counterin=0;
 468   long counterout=0;
 469   int done=0;
 470   char *temp[]={ "Test" ,"the Test band", "test records",NULL };
 471
 472   vi.channels=2;
 473   vi.rate=44100;
 474   vi.version=0;
 475   vi.mode=0;
 476
 477   vi.user_comments=temp;
 478   vi.vendor="Xiphophorus";
 479
 480   vorbis_analysis_init(&encode,&vi);
 481
 482   memset(&vb,0,sizeof(vorbis_block));
 483   vorbis_block_init(&encode,&vb);
 484
 485   /* Submit 100K samples of data reading out blocks... */
 486
 487   while(!done){
 488     int i;
 489     double **buf=vorbis_analysis_buffer(&encode,blocksize);
 490     for(i=0;i<blocksize;i++){
 491       buf[0][i]=1;
 492       buf[1][i]=-1;
 493
 494       if((counterin+i)%15000>13000)buf[0][i]+=10;
 495     }
 496
 497     i=(counterin+blocksize>fini?fini-counterin:blocksize);
 498     vorbis_analysis_wrote(&encode,i);
 499     counterin+=i;
 500
 501     while(vorbis_analysis_block(&encode,&vb)){
 502       double *window=encode.window[vb.W][vb.lW][vb.nW];
 503       FILE *out;
 504       char path[80];
 505       int begin=counterout-encode.block_size[vb.W]/2;
 506
 507       if(vb.eofflag){
 508         done=1;
 509         break;
 510       }
 511
 512       counterout=counterout+encode.block_size[vb.W]/4+
 513         encode.block_size[vb.nW]/4;
 514
 515     }
 516   }
 517   return 0;
 518 }
 519
 520 #endif