lib/block.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
   5  * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH    *
   6  * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.        *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
   9  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: PCM data vector blocking, windowing and dis/reassembly
  14  last mod: $Id: block.c,v 1.45 2001/02/15 19:05:45 xiphmont Exp $
  15
  16  Handle windowing, overlap-add, etc of the PCM vectors.  This is made
  17  more amusing by Vorbis' current two allowed block sizes.
  18
  19  ********************************************************************/
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <ogg/ogg.h>
  25 #include "vorbis/codec.h"
  26 #include "codec_internal.h"
  27
  28 #include "window.h"
  29 #include "envelope.h"
  30 #include "mdct.h"
  31 #include "lpc.h"
  32 #include "registry.h"
  33 #include "codebook.h"
  34 #include "misc.h"
  35 #include "os.h"
  36 #include "psy.h"
  37
  38 static int ilog2(unsigned int v){
  39   int ret=0;
  40   while(v>1){
  41     ret++;
  42     v>>=1;
  43   }
  44   return(ret);
  45 }
  46
  47 /* pcm accumulator examples (not exhaustive):
  48
  49  <-------------- lW ---------------->
  50                    <--------------- W ---------------->
  51 :            .....|.....       _______________         |
  52 :        .'''     |     '''_---      |       |\        |
  53 :.....'''         |_____--- '''......|       | \_______|
  54 :.................|__________________|_______|__|______|
  55                   |<------ Sl ------>|      > Sr <     |endW
  56                   |beginSl           |endSl  |  |endSr
  57                   |beginW            |endlW  |beginSr
  58
  59
  60                       |< lW >|
  61                    <--------------- W ---------------->
  62                   |   |  ..  ______________            |
  63                   |   | '  `/        |     ---_        |
  64                   |___.'___/`.       |         ---_____|
  65                   |_______|__|_______|_________________|
  66                   |      >|Sl|<      |<------ Sr ----->|endW
  67                   |       |  |endSl  |beginSr          |endSr
  68                   |beginW |  |endlW
  69                   mult[0] |beginSl                     mult[n]
  70
  71  <-------------- lW ----------------->
  72                           |<--W-->|
  73 :            ..............  ___  |   |
  74 :        .'''             |`/   \ |   |
  75 :.....'''                 |/`....\|...|
  76 :.........................|___|___|___|
  77                           |Sl |Sr |endW
  78                           |   |   |endSr
  79                           |   |beginSr
  80                           |   |endSl
  81                           |beginSl
  82                           |beginW
  83 */
  84
  85 /* block abstraction setup *********************************************/
  86
  87 #ifndef WORD_ALIGN
  88 #define WORD_ALIGN 8
  89 #endif
  90
  91 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
  92   memset(vb,0,sizeof(vorbis_block));
  93   vb->vd=v;
  94   vb->localalloc=0;
  95   vb->localstore=NULL;
  96   if(v->analysisp){
  97     oggpack_writeinit(&vb->opb);
  98     vb->internal=_ogg_calloc(1,sizeof(vorbis_block_internal));
  99     ((vorbis_block_internal *)vb->internal)->ampmax=-9999;
 100   }
 101
 102   return(0);
 103 }
 104
 105 void *_vorbis_block_alloc(vorbis_block *vb,long bytes){
 106   bytes=(bytes+(WORD_ALIGN-1)) & ~(WORD_ALIGN-1);
 107   if(bytes+vb->localtop>vb->localalloc){
 108     /* can't just _ogg_realloc... there are outstanding pointers */
 109     if(vb->localstore){
 110       struct alloc_chain *link=_ogg_malloc(sizeof(struct alloc_chain));
 111       vb->totaluse+=vb->localtop;
 112       link->next=vb->reap;
 113       link->ptr=vb->localstore;
 114       vb->reap=link;
 115     }
 116     /* highly conservative */
 117     vb->localalloc=bytes;
 118     vb->localstore=_ogg_malloc(vb->localalloc);
 119     vb->localtop=0;
 120   }
 121   {
 122     void *ret=(void *)(((char *)vb->localstore)+vb->localtop);
 123     vb->localtop+=bytes;
 124     return ret;
 125   }
 126 }
 127
 128 /* reap the chain, pull the ripcord */
 129 void _vorbis_block_ripcord(vorbis_block *vb){
 130   /* reap the chain */
 131   struct alloc_chain *reap=vb->reap;
 132   while(reap){
 133     struct alloc_chain *next=reap->next;
 134     _ogg_free(reap->ptr);
 135     memset(reap,0,sizeof(struct alloc_chain));
 136     _ogg_free(reap);
 137     reap=next;
 138   }
 139   /* consolidate storage */
 140   if(vb->totaluse){
 141     vb->localstore=_ogg_realloc(vb->localstore,vb->totaluse+vb->localalloc);
 142     vb->localalloc+=vb->totaluse;
 143     vb->totaluse=0;
 144   }
 145
 146   /* pull the ripcord */
 147   vb->localtop=0;
 148   vb->reap=NULL;
 149 }
 150
 151 int vorbis_block_clear(vorbis_block *vb){
 152   if(vb->vd)
 153     if(vb->vd->analysisp)
 154       oggpack_writeclear(&vb->opb);
 155   _vorbis_block_ripcord(vb);
 156   if(vb->localstore)_ogg_free(vb->localstore);
 157   if(vb->internal)_ogg_free(vb->internal);
 158
 159   memset(vb,0,sizeof(vorbis_block));
 160   return(0);
 161 }
 162
 163 /* Analysis side code, but directly related to blocking.  Thus it's
 164    here and not in analysis.c (which is for analysis transforms only).
 165    The init is here because some of it is shared */
 166
 167 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi,int encp){
 168   int i;
 169   codec_setup_info *ci=vi->codec_setup;
 170   backend_lookup_state *b=NULL;
 171
 172   memset(v,0,sizeof(vorbis_dsp_state));
 173   b=v->backend_state=_ogg_calloc(1,sizeof(backend_lookup_state));
 174
 175   v->vi=vi;
 176   b->modebits=ilog2(ci->modes);
 177   b->ampmax=-9999;
 178
 179   b->transform[0]=_ogg_calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
 180   b->transform[1]=_ogg_calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
 181
 182   /* MDCT is tranform 0 */
 183
 184   b->transform[0][0]=_ogg_calloc(1,sizeof(mdct_lookup));
 185   b->transform[1][0]=_ogg_calloc(1,sizeof(mdct_lookup));
 186   mdct_init(b->transform[0][0],ci->blocksizes[0]);
 187   mdct_init(b->transform[1][0],ci->blocksizes[1]);
 188
 189   b->window[0][0][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
 190   b->window[0][0][1]=b->window[0][0][0];
 191   b->window[0][1][0]=b->window[0][0][0];
 192   b->window[0][1][1]=b->window[0][0][0];
 193   b->window[1][0][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
 194   b->window[1][0][1]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
 195   b->window[1][1][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
 196   b->window[1][1][1]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
 197
 198   for(i=0;i<VI_WINDOWB;i++){
 199     b->window[0][0][0][i]=
 200       _vorbis_window(i,ci->blocksizes[0],ci->blocksizes[0]/2,ci->blocksizes[0]/2);
 201     b->window[1][0][0][i]=
 202       _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[0]/2,ci->blocksizes[0]/2);
 203     b->window[1][0][1][i]=
 204       _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[0]/2,ci->blocksizes[1]/2);
 205     b->window[1][1][0][i]=
 206       _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[1]/2,ci->blocksizes[0]/2);
 207     b->window[1][1][1][i]=
 208       _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[1]/2,ci->blocksizes[1]/2);
 209   }
 210
 211   if(encp){ /* encode/decode differ here */
 212     /* finish the codebooks */
 213     b->fullbooks=_ogg_calloc(ci->books,sizeof(codebook));
 214     for(i=0;i<ci->books;i++)
 215       vorbis_book_init_encode(b->fullbooks+i,ci->book_param[i]);
 216     v->analysisp=1;
 217   }else{
 218     /* finish the codebooks */
 219     b->fullbooks=_ogg_calloc(ci->books,sizeof(codebook));
 220     for(i=0;i<ci->books;i++)
 221       vorbis_book_init_decode(b->fullbooks+i,ci->book_param[i]);
 222   }
 223
 224   /* initialize the storage vectors to a decent size greater than the
 225      minimum */
 226
 227   v->pcm_storage=8192; /* we'll assume later that we have
 228                           a minimum of twice the blocksize of
 229                           accumulated samples in analysis */
 230   v->pcm=_ogg_malloc(vi->channels*sizeof(float *));
 231   v->pcmret=_ogg_malloc(vi->channels*sizeof(float *));
 232   {
 233     int i;
 234     for(i=0;i<vi->channels;i++)
 235       v->pcm[i]=_ogg_calloc(v->pcm_storage,sizeof(float));
 236   }
 237
 238   /* all 1 (large block) or 0 (small block) */
 239   /* explicitly set for the sake of clarity */
 240   v->lW=0; /* previous window size */
 241   v->W=0;  /* current window size */
 242
 243   /* all vector indexes */
 244   v->centerW=ci->blocksizes[1]/2;
 245
 246   v->pcm_current=v->centerW;
 247
 248   /* initialize all the mapping/backend lookups */
 249   b->mode=_ogg_calloc(ci->modes,sizeof(vorbis_look_mapping *));
 250   for(i=0;i<ci->modes;i++){
 251     int mapnum=ci->mode_param[i]->mapping;
 252     int maptype=ci->map_type[mapnum];
 253     b->mode[i]=_mapping_P[maptype]->look(v,ci->mode_param[i],
 254                                          ci->map_param[mapnum]);
 255   }
 256
 257   return(0);
 258 }
 259
 260 /* arbitrary settings and spec-mandated numbers get filled in here */
 261 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
 262   backend_lookup_state *b=NULL;
 263
 264   _vds_shared_init(v,vi,1);
 265   b=v->backend_state;
 266
 267   /* Initialize the envelope state storage */
 268   b->ve=_ogg_calloc(1,sizeof(envelope_lookup));
 269   _ve_envelope_init(b->ve,vi);
 270
 271   return(0);
 272 }
 273
 274 void vorbis_dsp_clear(vorbis_dsp_state *v){
 275   int i,j,k;
 276   if(v){
 277     vorbis_info *vi=v->vi;
 278     codec_setup_info *ci=(vi?vi->codec_setup:NULL);
 279     backend_lookup_state *b=v->backend_state;
 280
 281     if(b){
 282       if(b->window[0][0][0]){
 283         for(i=0;i<VI_WINDOWB;i++)
 284           if(b->window[0][0][0][i])_ogg_free(b->window[0][0][0][i]);
 285         _ogg_free(b->window[0][0][0]);
 286
 287         for(j=0;j<2;j++)
 288           for(k=0;k<2;k++){
 289             for(i=0;i<VI_WINDOWB;i++)
 290               if(b->window[1][j][k][i])_ogg_free(b->window[1][j][k][i]);
 291             _ogg_free(b->window[1][j][k]);
 292           }
 293       }
 294
 295       if(b->ve){
 296         _ve_envelope_clear(b->ve);
 297         _ogg_free(b->ve);
 298       }
 299
 300       if(b->transform[0]){
 301         mdct_clear(b->transform[0][0]);
 302         _ogg_free(b->transform[0][0]);
 303         _ogg_free(b->transform[0]);
 304       }
 305       if(b->transform[1]){
 306         mdct_clear(b->transform[1][0]);
 307         _ogg_free(b->transform[1][0]);
 308         _ogg_free(b->transform[1]);
 309       }
 310
 311     }
 312
 313     if(v->pcm){
 314       for(i=0;i<vi->channels;i++)
 315         if(v->pcm[i])_ogg_free(v->pcm[i]);
 316       _ogg_free(v->pcm);
 317       if(v->pcmret)_ogg_free(v->pcmret);
 318     }
 319
 320     /* free mode lookups; these are actually vorbis_look_mapping structs */
 321     if(ci){
 322       for(i=0;i<ci->modes;i++){
 323         int mapnum=ci->mode_param[i]->mapping;
 324         int maptype=ci->map_type[mapnum];
 325         if(b && b->mode)_mapping_P[maptype]->free_look(b->mode[i]);
 326       }
 327       /* free codebooks */
 328       for(i=0;i<ci->books;i++)
 329         if(b && b->fullbooks)vorbis_book_clear(b->fullbooks+i);
 330     }
 331
 332     if(b){
 333       if(b->mode)_ogg_free(b->mode);
 334       if(b->fullbooks)_ogg_free(b->fullbooks);
 335
 336       /* free header, header1, header2 */
 337       if(b->header)_ogg_free(b->header);
 338       if(b->header1)_ogg_free(b->header1);
 339       if(b->header2)_ogg_free(b->header2);
 340       _ogg_free(b);
 341     }
 342
 343     memset(v,0,sizeof(vorbis_dsp_state));
 344   }
 345 }
 346
 347 float **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
 348   int i;
 349   vorbis_info *vi=v->vi;
 350   backend_lookup_state *b=v->backend_state;
 351
 352   /* free header, header1, header2 */
 353   if(b->header)_ogg_free(b->header);b->header=NULL;
 354   if(b->header1)_ogg_free(b->header1);b->header1=NULL;
 355   if(b->header2)_ogg_free(b->header2);b->header2=NULL;
 356
 357   /* Do we have enough storage space for the requested buffer? If not,
 358      expand the PCM (and envelope) storage */
 359
 360   if(v->pcm_current+vals>=v->pcm_storage){
 361     v->pcm_storage=v->pcm_current+vals*2;
 362
 363     for(i=0;i<vi->channels;i++){
 364       v->pcm[i]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(float));
 365     }
 366   }
 367
 368   for(i=0;i<vi->channels;i++)
 369     v->pcmret[i]=v->pcm[i]+v->pcm_current;
 370
 371   return(v->pcmret);
 372 }
 373
 374 static void _preextrapolate_helper(vorbis_dsp_state *v){
 375   int i;
 376   int order=32;
 377   float *lpc=alloca(order*sizeof(float));
 378   float *work=alloca(v->pcm_current*sizeof(float));
 379   long j;
 380   v->preextrapolate=1;
 381
 382   if(v->pcm_current-v->centerW>order*2){ /* safety */
 383     for(i=0;i<v->vi->channels;i++){
 384
 385       /* need to run the extrapolation in reverse! */
 386       for(j=0;j<v->pcm_current;j++)
 387         work[j]=v->pcm[i][v->pcm_current-j-1];
 388
 389       /* prime as above */
 390       vorbis_lpc_from_data(work,lpc,v->pcm_current-v->centerW,order);
 391
 392       /* run the predictor filter */
 393       vorbis_lpc_predict(lpc,work+v->pcm_current-v->centerW-order,
 394                          order,
 395                          work+v->pcm_current-v->centerW,
 396                          v->centerW);
 397       for(j=0;j<v->pcm_current;j++)
 398         v->pcm[i][v->pcm_current-j-1]=work[j];
 399     }
 400   }
 401 }
 402
 403
 404 /* call with val<=0 to set eof */
 405
 406 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
 407   vorbis_info *vi=v->vi;
 408   codec_setup_info *ci=vi->codec_setup;
 409
 410   if(vals<=0){
 411     int order=32;
 412     int i;
 413     float *lpc=alloca(order*sizeof(float));
 414
 415     /* if it wasn't done earlier (very short sample) */
 416     if(!v->preextrapolate)
 417       _preextrapolate_helper(v);
 418
 419     /* We're encoding the end of the stream.  Just make sure we have
 420        [at least] a full block of zeroes at the end. */
 421     /* actually, we don't want zeroes; that could drop a large
 422        amplitude off a cliff, creating spread spectrum noise that will
 423        suck to encode.  Extrapolate for the sake of cleanliness. */
 424
 425     vorbis_analysis_buffer(v,ci->blocksizes[1]*2);
 426     v->eofflag=v->pcm_current;
 427     v->pcm_current+=ci->blocksizes[1]*2;
 428
 429     for(i=0;i<vi->channels;i++){
 430       if(v->eofflag>order*2){
 431         /* extrapolate with LPC to fill in */
 432         long n;
 433
 434         /* make a predictor filter */
 435         n=v->eofflag;
 436         if(n>ci->blocksizes[1])n=ci->blocksizes[1];
 437         vorbis_lpc_from_data(v->pcm[i]+v->eofflag-n,lpc,n,order);
 438
 439         /* run the predictor filter */
 440         vorbis_lpc_predict(lpc,v->pcm[i]+v->eofflag-order,order,
 441                            v->pcm[i]+v->eofflag,v->pcm_current-v->eofflag);
 442       }else{
 443         /* not enough data to extrapolate (unlikely to happen due to
 444            guarding the overlap, but bulletproof in case that
 445            assumtion goes away). zeroes will do. */
 446         memset(v->pcm[i]+v->eofflag,0,
 447                (v->pcm_current-v->eofflag)*sizeof(float));
 448
 449       }
 450     }
 451   }else{
 452
 453     if(v->pcm_current+vals>v->pcm_storage)
 454       return(OV_EINVAL);
 455
 456     v->pcm_current+=vals;
 457
 458     /* we may want to reverse extrapolate the beginning of a stream
 459        too... in case we're beginning on a cliff! */
 460     /* clumsy, but simple.  It only runs once, so simple is good. */
 461     if(!v->preextrapolate && v->pcm_current-v->centerW>ci->blocksizes[1])
 462       _preextrapolate_helper(v);
 463
 464   }
 465   return(0);
 466 }
 467
 468 /* do the deltas, envelope shaping, pre-echo and determine the size of
 469    the next block on which to continue analysis */
 470 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
 471   int i;
 472   vorbis_info *vi=v->vi;
 473   codec_setup_info *ci=vi->codec_setup;
 474   backend_lookup_state *b=v->backend_state;
 475   long beginW=v->centerW-ci->blocksizes[v->W]/2,centerNext;
 476
 477   /* check to see if we're started... */
 478   if(!v->preextrapolate)return(0);
 479
 480   /* check to see if we're done... */
 481   if(v->eofflag==-1)return(0);
 482
 483   /* By our invariant, we have lW, W and centerW set.  Search for
 484      the next boundary so we can determine nW (the next window size)
 485      which lets us compute the shape of the current block's window */
 486
 487   if(ci->blocksizes[0]<ci->blocksizes[1]){
 488     long largebound;
 489     long bp;
 490
 491     if(v->W)
 492       /* min boundary; nW large, next small */
 493       largebound=v->centerW+ci->blocksizes[1]*3/4+ci->blocksizes[0]/4;
 494     else
 495       /* min boundary; nW large, next small */
 496       largebound=v->centerW+ci->blocksizes[1]/2+ci->blocksizes[0]/2;
 497
 498     bp=_ve_envelope_search(v,largebound);
 499     if(bp==-1)return(0); /* not enough data currently to search for a
 500                             full long block */
 501     v->nW=bp;
 502
 503   }else
 504     v->nW=0;
 505
 506   centerNext=v->centerW+ci->blocksizes[v->W]/4+ci->blocksizes[v->nW]/4;
 507
 508   {
 509     /* center of next block + next block maximum right side. */
 510
 511     long blockbound=centerNext+ci->blocksizes[v->nW]/2;
 512     if(v->pcm_current<blockbound)return(0); /* not enough data yet;
 513                                                although this check is
 514                                                less strict that the
 515                                                _ve_envelope_search,
 516                                                the search is not run
 517                                                if we only use one
 518                                                block size */
 519   }
 520
 521   /* fill in the block.  Note that for a short window, lW and nW are *short*
 522      regardless of actual settings in the stream */
 523
 524   _vorbis_block_ripcord(vb);
 525   if(v->W){
 526     vb->lW=v->lW;
 527     vb->W=v->W;
 528     vb->nW=v->nW;
 529   }else{
 530     vb->lW=0;
 531     vb->W=v->W;
 532     vb->nW=0;
 533   }
 534   vb->vd=v;
 535   vb->sequence=v->sequence;
 536   vb->granulepos=v->granulepos;
 537   vb->pcmend=ci->blocksizes[v->W];
 538
 539
 540   /* copy the vectors; this uses the local storage in vb */
 541   {
 542     vorbis_block_internal *vbi=(vorbis_block_internal *)vb->internal;
 543
 544     /* this tracks 'strongest peak' for later psychoacoustics */
 545     if(vbi->ampmax>b->ampmax)b->ampmax=vbi->ampmax;
 546     b->ampmax=_vp_ampmax_decay(b->ampmax,v);
 547     vbi->ampmax=b->ampmax;
 548
 549     vb->pcm=_vorbis_block_alloc(vb,sizeof(float *)*vi->channels);
 550     vbi->pcmdelay=_vorbis_block_alloc(vb,sizeof(float *)*vi->channels);
 551     for(i=0;i<vi->channels;i++){
 552       vbi->pcmdelay[i]=
 553         _vorbis_block_alloc(vb,(vb->pcmend+beginW)*sizeof(float));
 554       memcpy(vbi->pcmdelay[i],v->pcm[i],(vb->pcmend+beginW)*sizeof(float));
 555       vb->pcm[i]=vbi->pcmdelay[i]+beginW;
 556
 557       /* before we added the delay
 558       vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(float));
 559       memcpy(vb->pcm[i],v->pcm[i]+beginW,ci->blocksizes[v->W]*sizeof(float));
 560       */
 561
 562     }
 563   }
 564
 565   /* handle eof detection: eof==0 means that we've not yet received EOF
 566                            eof>0  marks the last 'real' sample in pcm[]
 567                            eof<0  'no more to do'; doesn't get here */
 568
 569   if(v->eofflag){
 570     if(v->centerW>=v->eofflag){
 571       v->eofflag=-1;
 572       vb->eofflag=1;
 573       return(1);
 574     }
 575   }
 576
 577   /* advance storage vectors and clean up */
 578   {
 579     int new_centerNext=ci->blocksizes[1]/2+ci->delaycache;
 580     int movementW=centerNext-new_centerNext;
 581
 582     if(movementW>0){
 583
 584       _ve_envelope_shift(b->ve,movementW);
 585       v->pcm_current-=movementW;
 586
 587       for(i=0;i<vi->channels;i++)
 588         memmove(v->pcm[i],v->pcm[i]+movementW,
 589                 v->pcm_current*sizeof(float));
 590
 591
 592       v->lW=v->W;
 593       v->W=v->nW;
 594       v->centerW=new_centerNext;
 595
 596       v->sequence++;
 597
 598       if(v->eofflag){
 599         v->eofflag-=movementW;
 600         /* do not add padding to end of stream! */
 601         if(v->centerW>=v->eofflag){
 602           v->granulepos+=movementW-(v->centerW-v->eofflag);
 603         }else{
 604           v->granulepos+=movementW;
 605         }
 606       }else{
 607         v->granulepos+=movementW;
 608       }
 609     }
 610   }
 611
 612   /* done */
 613   return(1);
 614 }
 615
 616 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
 617   codec_setup_info *ci=vi->codec_setup;
 618   _vds_shared_init(v,vi,0);
 619
 620   /* Adjust centerW to allow an easier mechanism for determining output */
 621   v->pcm_returned=v->centerW;
 622   v->centerW-= ci->blocksizes[v->W]/4+ci->blocksizes[v->lW]/4;
 623   v->granulepos=-1;
 624   v->sequence=-1;
 625
 626   return(0);
 627 }
 628
 629 /* Unlike in analysis, the window is only partially applied for each
 630    block.  The time domain envelope is not yet handled at the point of
 631    calling (as it relies on the previous block). */
 632
 633 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
 634   vorbis_info *vi=v->vi;
 635   codec_setup_info *ci=vi->codec_setup;
 636
 637   /* Shift out any PCM that we returned previously */
 638   /* centerW is currently the center of the last block added */
 639
 640   if(v->centerW>ci->blocksizes[1]/2 &&
 641   /* Quick additional hack; to avoid *alot* of shifts, use an
 642      oversized buffer.  This increases memory usage, but doesn't make
 643      much difference wrt L1/L2 cache pressure. */
 644      v->pcm_returned>8192){
 645
 646     /* don't shift too much; we need to have a minimum PCM buffer of
 647        1/2 long block */
 648
 649     int shiftPCM=v->centerW-ci->blocksizes[1]/2;
 650     shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
 651
 652     v->pcm_current-=shiftPCM;
 653     v->centerW-=shiftPCM;
 654     v->pcm_returned-=shiftPCM;
 655
 656     if(shiftPCM){
 657       int i;
 658       for(i=0;i<vi->channels;i++)
 659         memmove(v->pcm[i],v->pcm[i]+shiftPCM,
 660                 v->pcm_current*sizeof(float));
 661     }
 662   }
 663
 664   v->lW=v->W;
 665   v->W=vb->W;
 666   v->nW=-1;
 667
 668   v->glue_bits+=vb->glue_bits;
 669   v->time_bits+=vb->time_bits;
 670   v->floor_bits+=vb->floor_bits;
 671   v->res_bits+=vb->res_bits;
 672
 673   if(v->sequence+1 != vb->sequence)v->granulepos=-1; /* out of sequence;
 674                                                      lose count */
 675
 676   v->sequence=vb->sequence;
 677
 678   {
 679     int sizeW=ci->blocksizes[v->W];
 680     int centerW=v->centerW+ci->blocksizes[v->lW]/4+sizeW/4;
 681     int beginW=centerW-sizeW/2;
 682     int endW=beginW+sizeW;
 683     int beginSl;
 684     int endSl;
 685     int i,j;
 686
 687     /* Do we have enough PCM/mult storage for the block? */
 688     if(endW>v->pcm_storage){
 689       /* expand the storage */
 690       v->pcm_storage=endW+ci->blocksizes[1];
 691
 692       for(i=0;i<vi->channels;i++)
 693         v->pcm[i]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(float));
 694     }
 695
 696     /* overlap/add PCM */
 697
 698     switch(v->W){
 699     case 0:
 700       beginSl=0;
 701       endSl=ci->blocksizes[0]/2;
 702       break;
 703     case 1:
 704       beginSl=ci->blocksizes[1]/4-ci->blocksizes[v->lW]/4;
 705       endSl=beginSl+ci->blocksizes[v->lW]/2;
 706       break;
 707     default:
 708       return(-1);
 709     }
 710
 711     for(j=0;j<vi->channels;j++){
 712       static int seq=0;
 713       float *pcm=v->pcm[j]+beginW;
 714       float *p=vb->pcm[j];
 715
 716       /* the overlap/add section */
 717       for(i=beginSl;i<endSl;i++)
 718         pcm[i]+=p[i];
 719       /* the remaining section */
 720       for(;i<sizeW;i++)
 721         pcm[i]=p[i];
 722
 723       _analysis_output("lapped",seq,pcm,sizeW,0,0);
 724       _analysis_output("buffered",seq++,v->pcm[j],sizeW+beginW,0,0);
 725
 726     }
 727
 728
 729     /* track the frame number... This is for convenience, but also
 730        making sure our last packet doesn't end with added padding.  If
 731        the last packet is partial, the number of samples we'll have to
 732        return will be past the vb->granulepos.
 733
 734        This is not foolproof!  It will be confused if we begin
 735        decoding at the last page after a seek or hole.  In that case,
 736        we don't have a starting point to judge where the last frame
 737        is.  For this reason, vorbisfile will always try to make sure
 738        it reads the last two marked pages in proper sequence */
 739
 740     if(v->granulepos==-1)
 741       if(vb->granulepos==-1){
 742         v->granulepos=0;
 743       }else{
 744         v->granulepos=vb->granulepos;
 745       }
 746     else{
 747       v->granulepos+=(centerW-v->centerW);
 748       if(vb->granulepos!=-1 && v->granulepos!=vb->granulepos){
 749
 750         if(v->granulepos>vb->granulepos){
 751           long extra=v->granulepos-vb->granulepos;
 752
 753           if(vb->eofflag){
 754             /* partial last frame.  Strip the extra samples off */
 755             centerW-=extra;
 756           }else if(vb->sequence == 1){
 757             /* partial first frame.  Discard extra leading samples */
 758             v->pcm_returned+=extra;
 759             if(v->pcm_returned>centerW)v->pcm_returned=centerW;
 760
 761           }
 762
 763         }/* else{ Shouldn't happen *unless* the bitstream is out of
 764             spec.  Either way, believe the bitstream } */
 765         v->granulepos=vb->granulepos;
 766       }
 767     }
 768
 769     /* Update, cleanup */
 770
 771     v->centerW=centerW;
 772     v->pcm_current=endW;
 773
 774     if(vb->eofflag)v->eofflag=1;
 775   }
 776
 777   return(0);
 778 }
 779
 780 /* pcm==NULL indicates we just want the pending samples, no more */
 781 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,float ***pcm){
 782   vorbis_info *vi=v->vi;
 783   if(v->pcm_returned<v->centerW){
 784     if(pcm){
 785       int i;
 786       for(i=0;i<vi->channels;i++)
 787         v->pcmret[i]=v->pcm[i]+v->pcm_returned;
 788       *pcm=v->pcmret;
 789     }
 790     return(v->centerW-v->pcm_returned);
 791   }
 792   return(0);
 793 }
 794
 795 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
 796   if(bytes && v->pcm_returned+bytes>v->centerW)return(OV_EINVAL);
 797   v->pcm_returned+=bytes;
 798   return(0);
 799 }
 800