1 /********************************************************************
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. *
8 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: PCM data vector blocking, windowing and dis/reassembly
15 last mod: $Id: block.c,v 1.39 2000/10/12 03:12:52 xiphmont Exp $
17 Handle windowing, overlap-add, etc of the PCM vectors. This is made
18 more amusing by Vorbis' current two allowed block sizes.
20 Vorbis manipulates the dynamic range of the incoming PCM data
21 envelope to minimise time-domain energy leakage from percussive and
22 plosive waveforms being quantized in the MDCT domain.
24 ********************************************************************/
30 #include "vorbis/codec.h"
37 #include "sharedbook.h"
38 #include "bookinternal.h"
42 static int ilog2(unsigned int v){
51 /* pcm accumulator examples (not exhaustive):
53 <-------------- lW ---------------->
54 <--------------- W ---------------->
55 : .....|..... _______________ |
56 : .''' | '''_--- | |\ |
57 :.....''' |_____--- '''......| | \_______|
58 :.................|__________________|_______|__|______|
59 |<------ Sl ------>| > Sr < |endW
60 |beginSl |endSl | |endSr
61 |beginW |endlW |beginSr
65 <--------------- W ---------------->
66 | | .. ______________ |
68 |___.'___/`. | ---_____|
69 |_______|__|_______|_________________|
70 | >|Sl|< |<------ Sr ----->|endW
71 | | |endSl |beginSr |endSr
73 mult[0] |beginSl mult[n]
75 <-------------- lW ----------------->
77 : .............. ___ | |
79 :.....''' |/`....\|...|
80 :.........................|___|___|___|
89 /* block abstraction setup *********************************************/
95 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
96 memset(vb,0,sizeof(vorbis_block));
101 oggpack_writeinit(&vb->opb);
106 void *_vorbis_block_alloc(vorbis_block *vb,long bytes){
107 bytes=(bytes+(WORD_ALIGN-1)) & ~(WORD_ALIGN-1);
108 if(bytes+vb->localtop>vb->localalloc){
109 /* can't just realloc... there are outstanding pointers */
111 struct alloc_chain *link=malloc(sizeof(struct alloc_chain));
112 vb->totaluse+=vb->localtop;
114 link->ptr=vb->localstore;
117 /* highly conservative */
118 vb->localalloc=bytes;
119 vb->localstore=malloc(vb->localalloc);
123 void *ret=(void *)(((char *)vb->localstore)+vb->localtop);
129 /* reap the chain, pull the ripcord */
130 void _vorbis_block_ripcord(vorbis_block *vb){
132 struct alloc_chain *reap=vb->reap;
134 struct alloc_chain *next=reap->next;
136 memset(reap,0,sizeof(struct alloc_chain));
140 /* consolidate storage */
142 vb->localstore=realloc(vb->localstore,vb->totaluse+vb->localalloc);
143 vb->localalloc+=vb->totaluse;
147 /* pull the ripcord */
152 int vorbis_block_clear(vorbis_block *vb){
154 if(vb->vd->analysisp)
155 oggpack_writeclear(&vb->opb);
156 _vorbis_block_ripcord(vb);
157 if(vb->localstore)free(vb->localstore);
159 memset(vb,0,sizeof(vorbis_block));
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 */
167 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi,int encp){
169 memset(v,0,sizeof(vorbis_dsp_state));
172 v->modebits=ilog2(vi->modes);
174 v->transform[0]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
175 v->transform[1]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
177 /* MDCT is tranform 0 */
179 v->transform[0][0]=calloc(1,sizeof(mdct_lookup));
180 v->transform[1][0]=calloc(1,sizeof(mdct_lookup));
181 mdct_init(v->transform[0][0],vi->blocksizes[0]);
182 mdct_init(v->transform[1][0],vi->blocksizes[1]);
184 v->window[0][0][0]=calloc(VI_WINDOWB,sizeof(float *));
185 v->window[0][0][1]=v->window[0][0][0];
186 v->window[0][1][0]=v->window[0][0][0];
187 v->window[0][1][1]=v->window[0][0][0];
188 v->window[1][0][0]=calloc(VI_WINDOWB,sizeof(float *));
189 v->window[1][0][1]=calloc(VI_WINDOWB,sizeof(float *));
190 v->window[1][1][0]=calloc(VI_WINDOWB,sizeof(float *));
191 v->window[1][1][1]=calloc(VI_WINDOWB,sizeof(float *));
193 for(i=0;i<VI_WINDOWB;i++){
194 v->window[0][0][0][i]=
195 _vorbis_window(i,vi->blocksizes[0],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
196 v->window[1][0][0][i]=
197 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
198 v->window[1][0][1][i]=
199 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[1]/2);
200 v->window[1][1][0][i]=
201 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[0]/2);
202 v->window[1][1][1][i]=
203 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[1]/2);
206 if(encp){ /* encode/decode differ here */
207 /* finish the codebooks */
208 v->fullbooks=calloc(vi->books,sizeof(codebook));
209 for(i=0;i<vi->books;i++)
210 vorbis_book_init_encode(v->fullbooks+i,vi->book_param[i]);
213 /* finish the codebooks */
214 v->fullbooks=calloc(vi->books,sizeof(codebook));
215 for(i=0;i<vi->books;i++)
216 vorbis_book_init_decode(v->fullbooks+i,vi->book_param[i]);
219 /* initialize the storage vectors to a decent size greater than the
222 v->pcm_storage=8192; /* we'll assume later that we have
223 a minimum of twice the blocksize of
224 accumulated samples in analysis */
225 v->pcm=malloc(vi->channels*sizeof(float *));
226 v->pcmret=malloc(vi->channels*sizeof(float *));
229 for(i=0;i<vi->channels;i++)
230 v->pcm[i]=calloc(v->pcm_storage,sizeof(float));
233 /* all 1 (large block) or 0 (small block) */
234 /* explicitly set for the sake of clarity */
235 v->lW=0; /* previous window size */
236 v->W=0; /* current window size */
238 /* all vector indexes */
239 v->centerW=vi->blocksizes[1]/2;
241 v->pcm_current=v->centerW;
243 /* initialize all the mapping/backend lookups */
244 v->mode=calloc(vi->modes,sizeof(vorbis_look_mapping *));
245 for(i=0;i<vi->modes;i++){
246 int mapnum=vi->mode_param[i]->mapping;
247 int maptype=vi->map_type[mapnum];
248 v->mode[i]=_mapping_P[maptype]->look(v,vi->mode_param[i],
249 vi->map_param[mapnum]);
255 /* arbitrary settings and spec-mandated numbers get filled in here */
256 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
257 _vds_shared_init(v,vi,1);
259 /* Initialize the envelope state storage */
260 v->ve=calloc(1,sizeof(envelope_lookup));
261 _ve_envelope_init(v->ve,vi);
266 void vorbis_dsp_clear(vorbis_dsp_state *v){
269 vorbis_info *vi=v->vi;
271 if(v->window[0][0][0]){
272 for(i=0;i<VI_WINDOWB;i++)
273 if(v->window[0][0][0][i])free(v->window[0][0][0][i]);
274 free(v->window[0][0][0]);
278 for(i=0;i<VI_WINDOWB;i++)
279 if(v->window[1][j][k][i])free(v->window[1][j][k][i]);
280 free(v->window[1][j][k]);
285 for(i=0;i<vi->channels;i++)
286 if(v->pcm[i])free(v->pcm[i]);
288 if(v->pcmret)free(v->pcmret);
292 _ve_envelope_clear(v->ve);
297 mdct_clear(v->transform[0][0]);
298 free(v->transform[0][0]);
299 free(v->transform[0]);
302 mdct_clear(v->transform[1][0]);
303 free(v->transform[1][0]);
304 free(v->transform[1]);
307 /* free mode lookups; these are actually vorbis_look_mapping structs */
309 for(i=0;i<vi->modes;i++){
310 int mapnum=vi->mode_param[i]->mapping;
311 int maptype=vi->map_type[mapnum];
312 _mapping_P[maptype]->free_look(v->mode[i]);
315 for(i=0;i<vi->books;i++)
316 vorbis_book_clear(v->fullbooks+i);
319 if(v->mode)free(v->mode);
320 if(v->fullbooks)free(v->fullbooks);
322 /* free header, header1, header2 */
323 if(v->header)free(v->header);
324 if(v->header1)free(v->header1);
325 if(v->header2)free(v->header2);
327 memset(v,0,sizeof(vorbis_dsp_state));
331 float **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
333 vorbis_info *vi=v->vi;
335 /* free header, header1, header2 */
336 if(v->header)free(v->header);v->header=NULL;
337 if(v->header1)free(v->header1);v->header1=NULL;
338 if(v->header2)free(v->header2);v->header2=NULL;
340 /* Do we have enough storage space for the requested buffer? If not,
341 expand the PCM (and envelope) storage */
343 if(v->pcm_current+vals>=v->pcm_storage){
344 v->pcm_storage=v->pcm_current+vals*2;
346 for(i=0;i<vi->channels;i++){
347 v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(float));
351 for(i=0;i<vi->channels;i++)
352 v->pcmret[i]=v->pcm[i]+v->pcm_current;
357 static void _preextrapolate_helper(vorbis_dsp_state *v){
360 float *lpc=alloca(order*sizeof(float));
361 float *work=alloca(v->pcm_current*sizeof(float));
365 if(v->pcm_current-v->centerW>order*2){ /* safety */
366 for(i=0;i<v->vi->channels;i++){
368 /* need to run the extrapolation in reverse! */
369 for(j=0;j<v->pcm_current;j++)
370 work[j]=v->pcm[i][v->pcm_current-j-1];
373 vorbis_lpc_from_data(work,lpc,v->pcm_current-v->centerW,order);
375 /* run the predictor filter */
376 vorbis_lpc_predict(lpc,work+v->pcm_current-v->centerW-order,
378 work+v->pcm_current-v->centerW,
380 for(j=0;j<v->pcm_current;j++)
381 v->pcm[i][v->pcm_current-j-1]=work[j];
387 /* call with val<=0 to set eof */
389 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
390 vorbis_info *vi=v->vi;
394 float *lpc=alloca(order*sizeof(float));
396 /* if it wasn't done earlier (very short sample) */
397 if(!v->preextrapolate)
398 _preextrapolate_helper(v);
400 /* We're encoding the end of the stream. Just make sure we have
401 [at least] a full block of zeroes at the end. */
402 /* actually, we don't want zeroes; that could drop a large
403 amplitude off a cliff, creating spread spectrum noise that will
404 suck to encode. Extrapolate for the sake of cleanliness. */
406 vorbis_analysis_buffer(v,v->vi->blocksizes[1]*2);
407 v->eofflag=v->pcm_current;
408 v->pcm_current+=v->vi->blocksizes[1]*2;
410 for(i=0;i<vi->channels;i++){
411 if(v->eofflag>order*2){
412 /* extrapolate with LPC to fill in */
415 /* make a predictor filter */
417 if(n>v->vi->blocksizes[1])n=v->vi->blocksizes[1];
418 vorbis_lpc_from_data(v->pcm[i]+v->eofflag-n,lpc,n,order);
420 /* run the predictor filter */
421 vorbis_lpc_predict(lpc,v->pcm[i]+v->eofflag-order,order,
422 v->pcm[i]+v->eofflag,v->pcm_current-v->eofflag);
424 /* not enough data to extrapolate (unlikely to happen due to
425 guarding the overlap, but bulletproof in case that
426 assumtion goes away). zeroes will do. */
427 memset(v->pcm[i]+v->eofflag,0,
428 (v->pcm_current-v->eofflag)*sizeof(float));
434 if(v->pcm_current+vals>v->pcm_storage)
437 v->pcm_current+=vals;
439 /* we may want to reverse extrapolate the beginning of a stream
440 too... in case we're beginning on a cliff! */
441 /* clumsy, but simple. It only runs once, so simple is good. */
442 if(!v->preextrapolate && v->pcm_current-v->centerW>v->vi->blocksizes[1])
443 _preextrapolate_helper(v);
449 /* do the deltas, envelope shaping, pre-echo and determine the size of
450 the next block on which to continue analysis */
451 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
453 vorbis_info *vi=v->vi;
454 long beginW=v->centerW-vi->blocksizes[v->W]/2,centerNext;
456 /* check to see if we're started... */
457 if(!v->preextrapolate)return(0);
459 /* check to see if we're done... */
460 if(v->eofflag==-1)return(0);
462 /* By our invariant, we have lW, W and centerW set. Search for
463 the next boundary so we can determine nW (the next window size)
464 which lets us compute the shape of the current block's window */
466 if(vi->blocksizes[0]<vi->blocksizes[1]){
471 /* min boundary; nW large, next small */
472 largebound=v->centerW+vi->blocksizes[1]*3/4+vi->blocksizes[0]/4;
474 /* min boundary; nW large, next small */
475 largebound=v->centerW+vi->blocksizes[1]*3/4+vi->blocksizes[0]*3/4;
477 bp=_ve_envelope_search(v,largebound);
478 if(bp==-1)return(0); /* not enough data currently to search for a
485 centerNext=v->centerW+vi->blocksizes[v->W]/4+vi->blocksizes[v->nW]/4;
488 /* center of next block + next block maximum right side. */
490 long blockbound=centerNext+vi->blocksizes[v->nW]/2;
491 if(v->pcm_current<blockbound)return(0); /* not enough data yet;
492 although this check is
495 the search is not run
500 /* fill in the block. Note that for a short window, lW and nW are *short*
501 regardless of actual settings in the stream */
503 _vorbis_block_ripcord(vb);
514 vb->sequence=v->sequence;
515 vb->granulepos=v->granulepos;
516 vb->pcmend=vi->blocksizes[v->W];
518 /* copy the vectors; this uses the local storage in vb */
520 vb->pcm=_vorbis_block_alloc(vb,sizeof(float *)*vi->channels);
521 for(i=0;i<vi->channels;i++){
522 vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(float));
523 memcpy(vb->pcm[i],v->pcm[i]+beginW,vi->blocksizes[v->W]*sizeof(float));
527 /* handle eof detection: eof==0 means that we've not yet received EOF
528 eof>0 marks the last 'real' sample in pcm[]
529 eof<0 'no more to do'; doesn't get here */
532 if(v->centerW>=v->eofflag){
539 /* advance storage vectors and clean up */
541 int new_centerNext=vi->blocksizes[1]/2;
542 int movementW=centerNext-new_centerNext;
544 _ve_envelope_shift(v->ve,movementW);
545 v->pcm_current-=movementW;
547 for(i=0;i<vi->channels;i++)
548 memmove(v->pcm[i],v->pcm[i]+movementW,
549 v->pcm_current*sizeof(float));
554 v->centerW=new_centerNext;
559 v->eofflag-=movementW;
560 /* do not add padding to end of stream! */
561 if(v->centerW>=v->eofflag){
562 v->granulepos+=movementW-(v->centerW-v->eofflag);
564 v->granulepos+=movementW;
567 v->granulepos+=movementW;
575 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
576 _vds_shared_init(v,vi,0);
578 /* Adjust centerW to allow an easier mechanism for determining output */
579 v->pcm_returned=v->centerW;
580 v->centerW-= vi->blocksizes[v->W]/4+vi->blocksizes[v->lW]/4;
587 /* Unlike in analysis, the window is only partially applied for each
588 block. The time domain envelope is not yet handled at the point of
589 calling (as it relies on the previous block). */
591 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
592 vorbis_info *vi=v->vi;
594 /* Shift out any PCM that we returned previously */
595 /* centerW is currently the center of the last block added */
596 if(v->pcm_returned && v->centerW>vi->blocksizes[1]/2){
598 /* don't shift too much; we need to have a minimum PCM buffer of
601 int shiftPCM=v->centerW-vi->blocksizes[1]/2;
602 shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
604 v->pcm_current-=shiftPCM;
605 v->centerW-=shiftPCM;
606 v->pcm_returned-=shiftPCM;
610 for(i=0;i<vi->channels;i++)
611 memmove(v->pcm[i],v->pcm[i]+shiftPCM,
612 v->pcm_current*sizeof(float));
620 v->glue_bits+=vb->glue_bits;
621 v->time_bits+=vb->time_bits;
622 v->floor_bits+=vb->floor_bits;
623 v->res_bits+=vb->res_bits;
625 if(v->sequence+1 != vb->sequence)v->granulepos=-1; /* out of sequence;
628 v->sequence=vb->sequence;
631 int sizeW=vi->blocksizes[v->W];
632 int centerW=v->centerW+vi->blocksizes[v->lW]/4+sizeW/4;
633 int beginW=centerW-sizeW/2;
634 int endW=beginW+sizeW;
639 /* Do we have enough PCM/mult storage for the block? */
640 if(endW>v->pcm_storage){
641 /* expand the storage */
642 v->pcm_storage=endW+vi->blocksizes[1];
644 for(i=0;i<vi->channels;i++)
645 v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(float));
648 /* overlap/add PCM */
653 endSl=vi->blocksizes[0]/2;
656 beginSl=vi->blocksizes[1]/4-vi->blocksizes[v->lW]/4;
657 endSl=beginSl+vi->blocksizes[v->lW]/2;
661 for(j=0;j<vi->channels;j++){
662 float *pcm=v->pcm[j]+beginW;
665 /* the overlap/add section */
666 for(i=beginSl;i<endSl;i++)
668 /* the remaining section */
673 /* track the frame number... This is for convenience, but also
674 making sure our last packet doesn't end with added padding. If
675 the last packet is partial, the number of samples we'll have to
676 return will be past the vb->granulepos.
678 This is not foolproof! It will be confused if we begin
679 decoding at the last page after a seek or hole. In that case,
680 we don't have a starting point to judge where the last frame
681 is. For this reason, vorbisfile will always try to make sure
682 it reads the last two marked pages in proper sequence */
684 if(v->granulepos==-1)
685 v->granulepos=vb->granulepos;
687 v->granulepos+=(centerW-v->centerW);
688 if(vb->granulepos!=-1 && v->granulepos!=vb->granulepos){
689 if(v->granulepos>vb->granulepos && vb->eofflag){
690 /* partial last frame. Strip the padding off */
691 centerW-=(v->granulepos-vb->granulepos);
692 }/* else{ Shouldn't happen *unless* the bitstream is out of
693 spec. Either way, believe the bitstream } */
694 v->granulepos=vb->granulepos;
698 /* Update, cleanup */
703 if(vb->eofflag)v->eofflag=1;
709 /* pcm==NULL indicates we just want the pending samples, no more */
710 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,float ***pcm){
711 vorbis_info *vi=v->vi;
712 if(v->pcm_returned<v->centerW){
715 for(i=0;i<vi->channels;i++)
716 v->pcmret[i]=v->pcm[i]+v->pcm_returned;
719 return(v->centerW-v->pcm_returned);
724 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
725 if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
726 v->pcm_returned+=bytes;