1 /********************************************************************
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
9 * by the XIPHOPHORUS Company http://www.xiph.org/ *
11 ********************************************************************
13 function: PCM data vector blocking, windowing and dis/reassembly
14 last mod: $Id: block.c,v 1.65 2002/06/28 22:19:35 xiphmont Exp $
16 Handle windowing, overlap-add, etc of the PCM vectors. This is made
17 more amusing by Vorbis' current two allowed block sizes.
19 ********************************************************************/
25 #include "vorbis/codec.h"
26 #include "codec_internal.h"
34 static int ilog2(unsigned int v){
44 /* pcm accumulator examples (not exhaustive):
46 <-------------- lW ---------------->
47 <--------------- W ---------------->
48 : .....|..... _______________ |
49 : .''' | '''_--- | |\ |
50 :.....''' |_____--- '''......| | \_______|
51 :.................|__________________|_______|__|______|
52 |<------ Sl ------>| > Sr < |endW
53 |beginSl |endSl | |endSr
54 |beginW |endlW |beginSr
58 <--------------- W ---------------->
59 | | .. ______________ |
61 |___.'___/`. | ---_____|
62 |_______|__|_______|_________________|
63 | >|Sl|< |<------ Sr ----->|endW
64 | | |endSl |beginSr |endSr
66 mult[0] |beginSl mult[n]
68 <-------------- lW ----------------->
70 : .............. ___ | |
72 :.....''' |/`....\|...|
73 :.........................|___|___|___|
82 /* block abstraction setup *********************************************/
88 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
89 memset(vb,0,sizeof(*vb));
94 vorbis_block_internal *vbi=
95 vb->internal=_ogg_calloc(1,sizeof(vorbis_block_internal));
96 oggpack_writeinit(&vb->opb);
103 void *_vorbis_block_alloc(vorbis_block *vb,long bytes){
104 bytes=(bytes+(WORD_ALIGN-1)) & ~(WORD_ALIGN-1);
105 if(bytes+vb->localtop>vb->localalloc){
106 /* can't just _ogg_realloc... there are outstanding pointers */
108 struct alloc_chain *link=_ogg_malloc(sizeof(*link));
109 vb->totaluse+=vb->localtop;
111 link->ptr=vb->localstore;
114 /* highly conservative */
115 vb->localalloc=bytes;
116 vb->localstore=_ogg_malloc(vb->localalloc);
120 void *ret=(void *)(((char *)vb->localstore)+vb->localtop);
126 /* reap the chain, pull the ripcord */
127 void _vorbis_block_ripcord(vorbis_block *vb){
129 struct alloc_chain *reap=vb->reap;
131 struct alloc_chain *next=reap->next;
132 _ogg_free(reap->ptr);
133 memset(reap,0,sizeof(*reap));
137 /* consolidate storage */
139 vb->localstore=_ogg_realloc(vb->localstore,vb->totaluse+vb->localalloc);
140 vb->localalloc+=vb->totaluse;
144 /* pull the ripcord */
149 int vorbis_block_clear(vorbis_block *vb){
151 if(vb->vd->analysisp)
152 oggpack_writeclear(&vb->opb);
153 _vorbis_block_ripcord(vb);
154 if(vb->localstore)_ogg_free(vb->localstore);
157 _ogg_free(vb->internal);
159 memset(vb,0,sizeof(*vb));
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 codec_setup_info *ci=vi->codec_setup;
170 backend_lookup_state *b=NULL;
172 memset(v,0,sizeof(*v));
173 b=v->backend_state=_ogg_calloc(1,sizeof(*b));
176 b->modebits=ilog2(ci->modes);
178 b->transform[0]=_ogg_calloc(VI_TRANSFORMB,sizeof(*b->transform[0]));
179 b->transform[1]=_ogg_calloc(VI_TRANSFORMB,sizeof(*b->transform[1]));
181 /* MDCT is tranform 0 */
183 b->transform[0][0]=_ogg_calloc(1,sizeof(mdct_lookup));
184 b->transform[1][0]=_ogg_calloc(1,sizeof(mdct_lookup));
185 mdct_init(b->transform[0][0],ci->blocksizes[0]);
186 mdct_init(b->transform[1][0],ci->blocksizes[1]);
188 /* Vorbis I uses only window type 0 */
189 b->window[0]=_vorbis_window(0,ci->blocksizes[0]/2);
190 b->window[1]=_vorbis_window(0,ci->blocksizes[1]/2);
192 if(encp){ /* encode/decode differ here */
194 /* analysis always needs an fft */
195 drft_init(&b->fft_look[0],ci->blocksizes[0]);
196 drft_init(&b->fft_look[1],ci->blocksizes[1]);
198 /* finish the codebooks */
200 ci->fullbooks=_ogg_calloc(ci->books,sizeof(*ci->fullbooks));
201 for(i=0;i<ci->books;i++)
202 vorbis_book_init_encode(ci->fullbooks+i,ci->book_param[i]);
205 b->psy=_ogg_calloc(ci->psys,sizeof(*b->psy));
206 for(i=0;i<ci->psys;i++){
207 _vp_psy_init(b->psy+i,
210 ci->blocksizes[ci->psy_param[i]->blockflag]/2,
216 /* finish the codebooks */
218 ci->fullbooks=_ogg_calloc(ci->books,sizeof(*ci->fullbooks));
219 for(i=0;i<ci->books;i++){
220 vorbis_book_init_decode(ci->fullbooks+i,ci->book_param[i]);
221 /* decode codebooks are now standalone after init */
222 vorbis_staticbook_destroy(ci->book_param[i]);
223 ci->book_param[i]=NULL;
228 /* initialize the storage vectors. blocksize[1] is small for encode,
229 but the correct size for decode */
230 v->pcm_storage=ci->blocksizes[1];
231 v->pcm=_ogg_malloc(vi->channels*sizeof(*v->pcm));
232 v->pcmret=_ogg_malloc(vi->channels*sizeof(*v->pcmret));
235 for(i=0;i<vi->channels;i++)
236 v->pcm[i]=_ogg_calloc(v->pcm_storage,sizeof(*v->pcm[i]));
239 /* all 1 (large block) or 0 (small block) */
240 /* explicitly set for the sake of clarity */
241 v->lW=0; /* previous window size */
242 v->W=0; /* current window size */
244 /* all vector indexes */
245 v->centerW=ci->blocksizes[1]/2;
247 v->pcm_current=v->centerW;
249 /* initialize all the backend lookups */
250 b->flr=_ogg_calloc(ci->floors,sizeof(*b->flr));
251 b->residue=_ogg_calloc(ci->residues,sizeof(*b->residue));
253 for(i=0;i<ci->floors;i++)
254 b->flr[i]=_floor_P[ci->floor_type[i]]->
255 look(v,ci->floor_param[i]);
257 for(i=0;i<ci->residues;i++)
258 b->residue[i]=_residue_P[ci->residue_type[i]]->
259 look(v,ci->residue_param[i]);
264 /* arbitrary settings and spec-mandated numbers get filled in here */
265 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
266 backend_lookup_state *b=NULL;
268 _vds_shared_init(v,vi,1);
270 b->psy_g_look=_vp_global_look(vi);
272 /* Initialize the envelope state storage */
273 b->ve=_ogg_calloc(1,sizeof(*b->ve));
274 _ve_envelope_init(b->ve,vi);
276 vorbis_bitrate_init(vi,&b->bms);
281 void vorbis_dsp_clear(vorbis_dsp_state *v){
284 vorbis_info *vi=v->vi;
285 codec_setup_info *ci=(vi?vi->codec_setup:NULL);
286 backend_lookup_state *b=v->backend_state;
290 _ogg_free(b->window[0]);
292 _ogg_free(b->window[1]);
295 _ve_envelope_clear(b->ve);
300 mdct_clear(b->transform[0][0]);
301 _ogg_free(b->transform[0][0]);
302 _ogg_free(b->transform[0]);
305 mdct_clear(b->transform[1][0]);
306 _ogg_free(b->transform[1][0]);
307 _ogg_free(b->transform[1]);
311 for(i=0;i<ci->floors;i++)
312 _floor_P[ci->floor_type[i]]->
313 free_look(b->flr[i]);
317 for(i=0;i<ci->residues;i++)
318 _residue_P[ci->residue_type[i]]->
319 free_look(b->residue[i]);
320 _ogg_free(b->residue);
323 for(i=0;i<ci->psys;i++)
324 _vp_psy_clear(b->psy+i);
328 if(b->psy_g_look)_vp_global_free(b->psy_g_look);
329 vorbis_bitrate_clear(&b->bms);
331 drft_clear(&b->fft_look[0]);
332 drft_clear(&b->fft_look[1]);
337 for(i=0;i<vi->channels;i++)
338 if(v->pcm[i])_ogg_free(v->pcm[i]);
340 if(v->pcmret)_ogg_free(v->pcmret);
344 /* free header, header1, header2 */
345 if(b->header)_ogg_free(b->header);
346 if(b->header1)_ogg_free(b->header1);
347 if(b->header2)_ogg_free(b->header2);
351 memset(v,0,sizeof(*v));
355 float **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
357 vorbis_info *vi=v->vi;
358 backend_lookup_state *b=v->backend_state;
360 /* free header, header1, header2 */
361 if(b->header)_ogg_free(b->header);b->header=NULL;
362 if(b->header1)_ogg_free(b->header1);b->header1=NULL;
363 if(b->header2)_ogg_free(b->header2);b->header2=NULL;
365 /* Do we have enough storage space for the requested buffer? If not,
366 expand the PCM (and envelope) storage */
368 if(v->pcm_current+vals>=v->pcm_storage){
369 v->pcm_storage=v->pcm_current+vals*2;
371 for(i=0;i<vi->channels;i++){
372 v->pcm[i]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(*v->pcm[i]));
376 for(i=0;i<vi->channels;i++)
377 v->pcmret[i]=v->pcm[i]+v->pcm_current;
382 static void _preextrapolate_helper(vorbis_dsp_state *v){
385 float *lpc=alloca(order*sizeof(*lpc));
386 float *work=alloca(v->pcm_current*sizeof(*work));
390 if(v->pcm_current-v->centerW>order*2){ /* safety */
391 for(i=0;i<v->vi->channels;i++){
392 /* need to run the extrapolation in reverse! */
393 for(j=0;j<v->pcm_current;j++)
394 work[j]=v->pcm[i][v->pcm_current-j-1];
397 vorbis_lpc_from_data(work,lpc,v->pcm_current-v->centerW,order);
399 /* run the predictor filter */
400 vorbis_lpc_predict(lpc,work+v->pcm_current-v->centerW-order,
402 work+v->pcm_current-v->centerW,
405 for(j=0;j<v->pcm_current;j++)
406 v->pcm[i][v->pcm_current-j-1]=work[j];
413 /* call with val<=0 to set eof */
415 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
416 vorbis_info *vi=v->vi;
417 codec_setup_info *ci=vi->codec_setup;
418 /*backend_lookup_state *b=v->backend_state;*/
423 float *lpc=alloca(order*sizeof(*lpc));
425 /* if it wasn't done earlier (very short sample) */
426 if(!v->preextrapolate)
427 _preextrapolate_helper(v);
429 /* We're encoding the end of the stream. Just make sure we have
430 [at least] a full block of zeroes at the end. */
431 /* actually, we don't want zeroes; that could drop a large
432 amplitude off a cliff, creating spread spectrum noise that will
433 suck to encode. Extrapolate for the sake of cleanliness. */
435 vorbis_analysis_buffer(v,ci->blocksizes[1]*2);
436 v->eofflag=v->pcm_current;
437 v->pcm_current+=ci->blocksizes[1]*2;
439 for(i=0;i<vi->channels;i++){
440 if(v->eofflag>order*2){
441 /* extrapolate with LPC to fill in */
444 /* make a predictor filter */
446 if(n>ci->blocksizes[1])n=ci->blocksizes[1];
447 vorbis_lpc_from_data(v->pcm[i]+v->eofflag-n,lpc,n,order);
449 /* run the predictor filter */
450 vorbis_lpc_predict(lpc,v->pcm[i]+v->eofflag-order,order,
451 v->pcm[i]+v->eofflag,v->pcm_current-v->eofflag);
453 /* not enough data to extrapolate (unlikely to happen due to
454 guarding the overlap, but bulletproof in case that
455 assumtion goes away). zeroes will do. */
456 memset(v->pcm[i]+v->eofflag,0,
457 (v->pcm_current-v->eofflag)*sizeof(*v->pcm[i]));
463 if(v->pcm_current+vals>v->pcm_storage)
466 v->pcm_current+=vals;
468 /* we may want to reverse extrapolate the beginning of a stream
469 too... in case we're beginning on a cliff! */
470 /* clumsy, but simple. It only runs once, so simple is good. */
471 if(!v->preextrapolate && v->pcm_current-v->centerW>ci->blocksizes[1])
472 _preextrapolate_helper(v);
478 /* do the deltas, envelope shaping, pre-echo and determine the size of
479 the next block on which to continue analysis */
480 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
482 vorbis_info *vi=v->vi;
483 codec_setup_info *ci=vi->codec_setup;
484 backend_lookup_state *b=v->backend_state;
485 vorbis_look_psy_global *g=b->psy_g_look;
486 vorbis_info_psy_global *gi=&ci->psy_g_param;
487 long beginW=v->centerW-ci->blocksizes[v->W]/2,centerNext;
488 vorbis_block_internal *vbi=(vorbis_block_internal *)vb->internal;
490 /* check to see if we're started... */
491 if(!v->preextrapolate)return(0);
493 /* check to see if we're done... */
494 if(v->eofflag==-1)return(0);
496 /* By our invariant, we have lW, W and centerW set. Search for
497 the next boundary so we can determine nW (the next window size)
498 which lets us compute the shape of the current block's window */
500 /* we do an envelope search even on a single blocksize; we may still
501 be throwing more bits at impulses, and envelope search handles
502 marking impulses too. */
504 long bp=_ve_envelope_search(v);
505 if(bp==-1)return(0); /* not enough data currently to search for a
511 centerNext=v->centerW+ci->blocksizes[v->W]/4+ci->blocksizes[v->nW]/4;
514 /* center of next block + next block maximum right side. */
516 long blockbound=centerNext+ci->blocksizes[v->nW]/2;
517 if(v->pcm_current<blockbound)return(0); /* not enough data yet;
518 although this check is
521 the search is not run
528 /* fill in the block. Note that for a short window, lW and nW are *short*
529 regardless of actual settings in the stream */
531 _vorbis_block_ripcord(vb);
537 if(!v->lW || !v->nW){
538 vbi->blocktype=BLOCKTYPE_TRANSITION;
539 /*fprintf(stderr,"-");*/
541 vbi->blocktype=BLOCKTYPE_LONG;
542 /*fprintf(stderr,"_");*/
545 if(_ve_envelope_mark(v)){
546 vbi->blocktype=BLOCKTYPE_IMPULSE;
547 /*fprintf(stderr,"|");*/
550 vbi->blocktype=BLOCKTYPE_PADDING;
551 /*fprintf(stderr,".");*/
557 vb->sequence=v->sequence++;
558 vb->granulepos=v->granulepos;
559 vb->pcmend=ci->blocksizes[v->W];
561 /* copy the vectors; this uses the local storage in vb */
563 /* this tracks 'strongest peak' for later psychoacoustics */
564 /* moved to the global psy state; clean this mess up */
565 if(vbi->ampmax>g->ampmax)g->ampmax=vbi->ampmax;
566 g->ampmax=_vp_ampmax_decay(g->ampmax,v);
567 vbi->ampmax=g->ampmax;
569 vb->pcm=_vorbis_block_alloc(vb,sizeof(*vb->pcm)*vi->channels);
570 vbi->pcmdelay=_vorbis_block_alloc(vb,sizeof(*vbi->pcmdelay)*vi->channels);
571 for(i=0;i<vi->channels;i++){
573 _vorbis_block_alloc(vb,(vb->pcmend+beginW)*sizeof(*vbi->pcmdelay[i]));
574 memcpy(vbi->pcmdelay[i],v->pcm[i],(vb->pcmend+beginW)*sizeof(*vbi->pcmdelay[i]));
575 vb->pcm[i]=vbi->pcmdelay[i]+beginW;
577 /* before we added the delay
578 vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(*vb->pcm[i]));
579 memcpy(vb->pcm[i],v->pcm[i]+beginW,ci->blocksizes[v->W]*sizeof(*vb->pcm[i]));
584 /* handle eof detection: eof==0 means that we've not yet received EOF
585 eof>0 marks the last 'real' sample in pcm[]
586 eof<0 'no more to do'; doesn't get here */
589 if(v->centerW>=v->eofflag){
596 /* advance storage vectors and clean up */
598 int new_centerNext=ci->blocksizes[1]/2;
599 int movementW=centerNext-new_centerNext;
603 _ve_envelope_shift(b->ve,movementW);
604 v->pcm_current-=movementW;
606 for(i=0;i<vi->channels;i++)
607 memmove(v->pcm[i],v->pcm[i]+movementW,
608 v->pcm_current*sizeof(*v->pcm[i]));
613 v->centerW=new_centerNext;
616 v->eofflag-=movementW;
617 /* do not add padding to end of stream! */
618 if(v->centerW>=v->eofflag){
619 v->granulepos+=movementW-(v->centerW-v->eofflag);
621 v->granulepos+=movementW;
624 v->granulepos+=movementW;
633 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
634 _vds_shared_init(v,vi,0);
643 /* Unlike in analysis, the window is only partially applied for each
644 block. The time domain envelope is not yet handled at the point of
645 calling (as it relies on the previous block). */
647 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
648 vorbis_info *vi=v->vi;
649 codec_setup_info *ci=vi->codec_setup;
652 if(!vb)return(OV_EINVAL);
653 if(v->pcm_current>v->pcm_returned && v->pcm_returned!=-1)return(OV_EINVAL);
659 if(v->sequence+1 != vb->sequence)v->granulepos=-1; /* out of sequence;
661 v->sequence=vb->sequence;
663 if(vb->pcm){ /* not pcm to process if vorbis_synthesis_trackonly
664 was called on block */
665 int n=ci->blocksizes[v->W]/2;
666 int n0=ci->blocksizes[0]/2;
667 int n1=ci->blocksizes[1]/2;
672 v->glue_bits+=vb->glue_bits;
673 v->time_bits+=vb->time_bits;
674 v->floor_bits+=vb->floor_bits;
675 v->res_bits+=vb->res_bits;
685 /* v->pcm is now used like a two-stage double buffer. We don't want
686 to have to constantly shift *or* adjust memory usage. Don't
687 accept a new block until the old is shifted out */
689 /* overlap/add PCM */
691 for(j=0;j<vi->channels;j++){
692 /* the overlap/add section */
696 float *pcm=v->pcm[j]+prevCenter;
702 float *pcm=v->pcm[j]+prevCenter+n1/2-n0/2;
710 float *pcm=v->pcm[j]+prevCenter;
711 float *p=vb->pcm[j]+n1/2-n0/2;
714 for(;i<n1/2+n0/2;i++)
718 float *pcm=v->pcm[j]+prevCenter;
725 /* the copy section */
727 float *pcm=v->pcm[j]+thisCenter;
728 float *p=vb->pcm[j]+n;
739 /* deal with initial packet state; we do this using the explicit
740 pcm_returned==-1 flag otherwise we're sensitive to first block
741 being short or long */
743 if(v->pcm_returned==-1){
744 v->pcm_returned=thisCenter;
745 v->pcm_current=thisCenter;
747 v->pcm_returned=prevCenter;
748 v->pcm_current=prevCenter+
749 ci->blocksizes[v->lW]/4+
750 ci->blocksizes[v->W]/4;
755 /* track the frame number... This is for convenience, but also
756 making sure our last packet doesn't end with added padding. If
757 the last packet is partial, the number of samples we'll have to
758 return will be past the vb->granulepos.
760 This is not foolproof! It will be confused if we begin
761 decoding at the last page after a seek or hole. In that case,
762 we don't have a starting point to judge where the last frame
763 is. For this reason, vorbisfile will always try to make sure
764 it reads the last two marked pages in proper sequence */
766 if(v->granulepos==-1){
767 if(vb->granulepos!=-1){ /* only set if we have a position to set to */
768 v->granulepos=vb->granulepos;
771 v->granulepos+=ci->blocksizes[v->lW]/4+ci->blocksizes[v->W]/4;
772 if(vb->granulepos!=-1 && v->granulepos!=vb->granulepos){
774 if(v->granulepos>vb->granulepos){
775 long extra=v->granulepos-vb->granulepos;
778 /* partial last frame. Strip the extra samples off */
779 v->pcm_current-=extra;
780 }else if(vb->sequence == 1){
781 /* ^^^ argh, this can be 1 from seeking! */
784 /* partial first frame. Discard extra leading samples */
785 v->pcm_returned+=extra;
786 if(v->pcm_returned>v->pcm_current)
787 v->pcm_returned=v->pcm_current;
789 } /* else {Shouldn't happen *unless* the bitstream is out of
790 spec. Either way, believe the bitstream } */
791 } /* else {Shouldn't happen *unless* the bitstream is out of
792 spec. Either way, believe the bitstream } */
793 v->granulepos=vb->granulepos;
797 /* Update, cleanup */
799 if(vb->eofflag)v->eofflag=1;
804 /* pcm==NULL indicates we just want the pending samples, no more */
805 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,float ***pcm){
806 vorbis_info *vi=v->vi;
807 if(v->pcm_returned>-1 && v->pcm_returned<v->pcm_current){
810 for(i=0;i<vi->channels;i++)
811 v->pcmret[i]=v->pcm[i]+v->pcm_returned;
814 return(v->pcm_current-v->pcm_returned);
819 int vorbis_synthesis_read(vorbis_dsp_state *v,int n){
820 if(n && v->pcm_returned+n>v->pcm_current)return(OV_EINVAL);