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.63 2002/03/29 07:10:38 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){
43 /* pcm accumulator examples (not exhaustive):
45 <-------------- lW ---------------->
46 <--------------- W ---------------->
47 : .....|..... _______________ |
48 : .''' | '''_--- | |\ |
49 :.....''' |_____--- '''......| | \_______|
50 :.................|__________________|_______|__|______|
51 |<------ Sl ------>| > Sr < |endW
52 |beginSl |endSl | |endSr
53 |beginW |endlW |beginSr
57 <--------------- W ---------------->
58 | | .. ______________ |
60 |___.'___/`. | ---_____|
61 |_______|__|_______|_________________|
62 | >|Sl|< |<------ Sr ----->|endW
63 | | |endSl |beginSr |endSr
65 mult[0] |beginSl mult[n]
67 <-------------- lW ----------------->
69 : .............. ___ | |
71 :.....''' |/`....\|...|
72 :.........................|___|___|___|
81 /* block abstraction setup *********************************************/
87 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
88 memset(vb,0,sizeof(*vb));
93 vorbis_block_internal *vbi=
94 vb->internal=_ogg_calloc(1,sizeof(vorbis_block_internal));
95 oggpack_writeinit(&vb->opb);
97 vbi->packet_markers=_ogg_malloc(vorbis_bitrate_maxmarkers()*
98 sizeof(*vbi->packet_markers));
104 void *_vorbis_block_alloc(vorbis_block *vb,long bytes){
105 bytes=(bytes+(WORD_ALIGN-1)) & ~(WORD_ALIGN-1);
106 if(bytes+vb->localtop>vb->localalloc){
107 /* can't just _ogg_realloc... there are outstanding pointers */
109 struct alloc_chain *link=_ogg_malloc(sizeof(*link));
110 vb->totaluse+=vb->localtop;
112 link->ptr=vb->localstore;
115 /* highly conservative */
116 vb->localalloc=bytes;
117 vb->localstore=_ogg_malloc(vb->localalloc);
121 void *ret=(void *)(((char *)vb->localstore)+vb->localtop);
127 /* reap the chain, pull the ripcord */
128 void _vorbis_block_ripcord(vorbis_block *vb){
130 struct alloc_chain *reap=vb->reap;
132 struct alloc_chain *next=reap->next;
133 _ogg_free(reap->ptr);
134 memset(reap,0,sizeof(*reap));
138 /* consolidate storage */
140 vb->localstore=_ogg_realloc(vb->localstore,vb->totaluse+vb->localalloc);
141 vb->localalloc+=vb->totaluse;
145 /* pull the ripcord */
150 int vorbis_block_clear(vorbis_block *vb){
152 if(vb->vd->analysisp)
153 oggpack_writeclear(&vb->opb);
154 _vorbis_block_ripcord(vb);
155 if(vb->localstore)_ogg_free(vb->localstore);
158 vorbis_block_internal *vbi=(vorbis_block_internal *)vb->internal;
159 if(vbi->packet_markers)_ogg_free(vbi->packet_markers);
161 _ogg_free(vb->internal);
164 memset(vb,0,sizeof(*vb));
168 /* Analysis side code, but directly related to blocking. Thus it's
169 here and not in analysis.c (which is for analysis transforms only).
170 The init is here because some of it is shared */
172 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi,int encp){
174 codec_setup_info *ci=vi->codec_setup;
175 backend_lookup_state *b=NULL;
177 memset(v,0,sizeof(*v));
178 b=v->backend_state=_ogg_calloc(1,sizeof(*b));
181 b->modebits=ilog2(ci->modes);
183 b->transform[0]=_ogg_calloc(VI_TRANSFORMB,sizeof(*b->transform[0]));
184 b->transform[1]=_ogg_calloc(VI_TRANSFORMB,sizeof(*b->transform[1]));
186 /* MDCT is tranform 0 */
188 b->transform[0][0]=_ogg_calloc(1,sizeof(mdct_lookup));
189 b->transform[1][0]=_ogg_calloc(1,sizeof(mdct_lookup));
190 mdct_init(b->transform[0][0],ci->blocksizes[0]);
191 mdct_init(b->transform[1][0],ci->blocksizes[1]);
193 /* Vorbis I uses only window type 0 */
194 b->window[0]=_vorbis_window(0,ci->blocksizes[0]/2);
195 b->window[1]=_vorbis_window(0,ci->blocksizes[1]/2);
197 if(encp){ /* encode/decode differ here */
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]);
206 /* finish the codebooks */
208 ci->fullbooks=_ogg_calloc(ci->books,sizeof(*ci->fullbooks));
209 for(i=0;i<ci->books;i++){
210 vorbis_book_init_decode(ci->fullbooks+i,ci->book_param[i]);
211 /* decode codebooks are now standalone after init */
212 vorbis_staticbook_destroy(ci->book_param[i]);
213 ci->book_param[i]=NULL;
218 /* initialize the storage vectors. blocksize[1] is small for encode,
219 but the correct size for decode */
220 v->pcm_storage=ci->blocksizes[1];
221 v->pcm=_ogg_malloc(vi->channels*sizeof(*v->pcm));
222 v->pcmret=_ogg_malloc(vi->channels*sizeof(*v->pcmret));
225 for(i=0;i<vi->channels;i++)
226 v->pcm[i]=_ogg_calloc(v->pcm_storage,sizeof(*v->pcm[i]));
229 /* all 1 (large block) or 0 (small block) */
230 /* explicitly set for the sake of clarity */
231 v->lW=0; /* previous window size */
232 v->W=0; /* current window size */
234 /* all vector indexes */
235 v->centerW=ci->blocksizes[1]/2;
237 v->pcm_current=v->centerW;
239 /* initialize all the mapping/backend lookups */
240 b->mode=_ogg_calloc(ci->modes,sizeof(*b->mode));
241 for(i=0;i<ci->modes;i++){
242 int mapnum=ci->mode_param[i]->mapping;
243 int maptype=ci->map_type[mapnum];
244 b->mode[i]=_mapping_P[maptype]->look(v,ci->mode_param[i],
245 ci->map_param[mapnum]);
251 /* arbitrary settings and spec-mandated numbers get filled in here */
252 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
253 backend_lookup_state *b=NULL;
255 _vds_shared_init(v,vi,1);
257 b->psy_g_look=_vp_global_look(vi);
259 /* Initialize the envelope state storage */
260 b->ve=_ogg_calloc(1,sizeof(*b->ve));
261 _ve_envelope_init(b->ve,vi);
263 vorbis_bitrate_init(vi,&b->bms);
268 void vorbis_dsp_clear(vorbis_dsp_state *v){
271 vorbis_info *vi=v->vi;
272 codec_setup_info *ci=(vi?vi->codec_setup:NULL);
273 backend_lookup_state *b=v->backend_state;
277 _ogg_free(b->window[0]);
279 _ogg_free(b->window[1]);
282 _ve_envelope_clear(b->ve);
287 mdct_clear(b->transform[0][0]);
288 _ogg_free(b->transform[0][0]);
289 _ogg_free(b->transform[0]);
292 mdct_clear(b->transform[1][0]);
293 _ogg_free(b->transform[1][0]);
294 _ogg_free(b->transform[1]);
296 if(b->psy_g_look)_vp_global_free(b->psy_g_look);
297 vorbis_bitrate_clear(&b->bms);
301 for(i=0;i<vi->channels;i++)
302 if(v->pcm[i])_ogg_free(v->pcm[i]);
304 if(v->pcmret)_ogg_free(v->pcmret);
307 /* free mode lookups; these are actually vorbis_look_mapping structs */
309 for(i=0;i<ci->modes;i++){
310 int mapnum=ci->mode_param[i]->mapping;
311 int maptype=ci->map_type[mapnum];
312 if(b && b->mode)_mapping_P[maptype]->free_look(b->mode[i]);
317 if(b->mode)_ogg_free(b->mode);
319 /* free header, header1, header2 */
320 if(b->header)_ogg_free(b->header);
321 if(b->header1)_ogg_free(b->header1);
322 if(b->header2)_ogg_free(b->header2);
326 memset(v,0,sizeof(*v));
330 float **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
332 vorbis_info *vi=v->vi;
333 backend_lookup_state *b=v->backend_state;
335 /* free header, header1, header2 */
336 if(b->header)_ogg_free(b->header);b->header=NULL;
337 if(b->header1)_ogg_free(b->header1);b->header1=NULL;
338 if(b->header2)_ogg_free(b->header2);b->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]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(*v->pcm[i]));
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(*lpc));
361 float *work=alloca(v->pcm_current*sizeof(*work));
365 if(v->pcm_current-v->centerW>order*2){ /* safety */
366 for(i=0;i<v->vi->channels;i++){
367 /* need to run the extrapolation in reverse! */
368 for(j=0;j<v->pcm_current;j++)
369 work[j]=v->pcm[i][v->pcm_current-j-1];
372 vorbis_lpc_from_data(work,lpc,v->pcm_current-v->centerW,order);
374 /* run the predictor filter */
375 vorbis_lpc_predict(lpc,work+v->pcm_current-v->centerW-order,
377 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];
388 /* call with val<=0 to set eof */
390 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
391 vorbis_info *vi=v->vi;
392 codec_setup_info *ci=vi->codec_setup;
393 /*backend_lookup_state *b=v->backend_state;*/
398 float *lpc=alloca(order*sizeof(*lpc));
400 /* if it wasn't done earlier (very short sample) */
401 if(!v->preextrapolate)
402 _preextrapolate_helper(v);
404 /* We're encoding the end of the stream. Just make sure we have
405 [at least] a full block of zeroes at the end. */
406 /* actually, we don't want zeroes; that could drop a large
407 amplitude off a cliff, creating spread spectrum noise that will
408 suck to encode. Extrapolate for the sake of cleanliness. */
410 vorbis_analysis_buffer(v,ci->blocksizes[1]*2);
411 v->eofflag=v->pcm_current;
412 v->pcm_current+=ci->blocksizes[1]*2;
414 for(i=0;i<vi->channels;i++){
415 if(v->eofflag>order*2){
416 /* extrapolate with LPC to fill in */
419 /* make a predictor filter */
421 if(n>ci->blocksizes[1])n=ci->blocksizes[1];
422 vorbis_lpc_from_data(v->pcm[i]+v->eofflag-n,lpc,n,order);
424 /* run the predictor filter */
425 vorbis_lpc_predict(lpc,v->pcm[i]+v->eofflag-order,order,
426 v->pcm[i]+v->eofflag,v->pcm_current-v->eofflag);
428 /* not enough data to extrapolate (unlikely to happen due to
429 guarding the overlap, but bulletproof in case that
430 assumtion goes away). zeroes will do. */
431 memset(v->pcm[i]+v->eofflag,0,
432 (v->pcm_current-v->eofflag)*sizeof(*v->pcm[i]));
438 if(v->pcm_current+vals>v->pcm_storage)
441 v->pcm_current+=vals;
443 /* we may want to reverse extrapolate the beginning of a stream
444 too... in case we're beginning on a cliff! */
445 /* clumsy, but simple. It only runs once, so simple is good. */
446 if(!v->preextrapolate && v->pcm_current-v->centerW>ci->blocksizes[1])
447 _preextrapolate_helper(v);
453 /* do the deltas, envelope shaping, pre-echo and determine the size of
454 the next block on which to continue analysis */
455 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
457 vorbis_info *vi=v->vi;
458 codec_setup_info *ci=vi->codec_setup;
459 backend_lookup_state *b=v->backend_state;
460 vorbis_look_psy_global *g=b->psy_g_look;
461 vorbis_info_psy_global *gi=&ci->psy_g_param;
462 long beginW=v->centerW-ci->blocksizes[v->W]/2,centerNext;
463 vorbis_block_internal *vbi=(vorbis_block_internal *)vb->internal;
465 /* check to see if we're started... */
466 if(!v->preextrapolate)return(0);
468 /* check to see if we're done... */
469 if(v->eofflag==-1)return(0);
471 /* By our invariant, we have lW, W and centerW set. Search for
472 the next boundary so we can determine nW (the next window size)
473 which lets us compute the shape of the current block's window */
475 if(ci->blocksizes[0]<ci->blocksizes[1]){
476 long bp=_ve_envelope_search(v);
477 if(bp==-1)return(0); /* not enough data currently to search for a
484 centerNext=v->centerW+ci->blocksizes[v->W]/4+ci->blocksizes[v->nW]/4;
487 /* center of next block + next block maximum right side. */
489 long blockbound=centerNext+ci->blocksizes[v->nW]/2;
490 if(v->pcm_current<blockbound)return(0); /* not enough data yet;
491 although this check is
494 the search is not run
501 /* fill in the block. Note that for a short window, lW and nW are *short*
502 regardless of actual settings in the stream */
504 _vorbis_block_ripcord(vb);
510 if(!v->lW || !v->nW){
511 vbi->blocktype=BLOCKTYPE_TRANSITION;
514 vbi->blocktype=BLOCKTYPE_LONG;
518 if(_ve_envelope_mark(v)){
519 vbi->blocktype=BLOCKTYPE_IMPULSE;
523 vbi->blocktype=BLOCKTYPE_PADDING;
530 vb->sequence=v->sequence++;
531 vb->granulepos=v->granulepos;
532 vb->pcmend=ci->blocksizes[v->W];
534 /* copy the vectors; this uses the local storage in vb */
536 /* this tracks 'strongest peak' for later psychoacoustics */
537 /* moved to the global psy state; clean this mess up */
538 if(vbi->ampmax>g->ampmax)g->ampmax=vbi->ampmax;
539 g->ampmax=_vp_ampmax_decay(g->ampmax,v);
540 vbi->ampmax=g->ampmax;
542 vb->pcm=_vorbis_block_alloc(vb,sizeof(*vb->pcm)*vi->channels);
543 vbi->pcmdelay=_vorbis_block_alloc(vb,sizeof(*vbi->pcmdelay)*vi->channels);
544 for(i=0;i<vi->channels;i++){
546 _vorbis_block_alloc(vb,(vb->pcmend+beginW)*sizeof(*vbi->pcmdelay[i]));
547 memcpy(vbi->pcmdelay[i],v->pcm[i],(vb->pcmend+beginW)*sizeof(*vbi->pcmdelay[i]));
548 vb->pcm[i]=vbi->pcmdelay[i]+beginW;
550 /* before we added the delay
551 vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(*vb->pcm[i]));
552 memcpy(vb->pcm[i],v->pcm[i]+beginW,ci->blocksizes[v->W]*sizeof(*vb->pcm[i]));
557 /* handle eof detection: eof==0 means that we've not yet received EOF
558 eof>0 marks the last 'real' sample in pcm[]
559 eof<0 'no more to do'; doesn't get here */
562 if(v->centerW>=v->eofflag){
569 /* advance storage vectors and clean up */
571 int new_centerNext=ci->blocksizes[1]/2+gi->delaycache;
572 int movementW=centerNext-new_centerNext;
576 _ve_envelope_shift(b->ve,movementW);
577 v->pcm_current-=movementW;
579 for(i=0;i<vi->channels;i++)
580 memmove(v->pcm[i],v->pcm[i]+movementW,
581 v->pcm_current*sizeof(*v->pcm[i]));
586 v->centerW=new_centerNext;
589 v->eofflag-=movementW;
590 /* do not add padding to end of stream! */
591 if(v->centerW>=v->eofflag){
592 v->granulepos+=movementW-(v->centerW-v->eofflag);
594 v->granulepos+=movementW;
597 v->granulepos+=movementW;
606 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
607 _vds_shared_init(v,vi,0);
616 /* Unlike in analysis, the window is only partially applied for each
617 block. The time domain envelope is not yet handled at the point of
618 calling (as it relies on the previous block). */
620 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
621 vorbis_info *vi=v->vi;
622 codec_setup_info *ci=vi->codec_setup;
625 if(!vb)return(OV_EINVAL);
626 if(v->pcm_current>v->pcm_returned && v->pcm_returned!=-1)return(OV_EINVAL);
632 if(v->sequence+1 != vb->sequence)v->granulepos=-1; /* out of sequence;
634 v->sequence=vb->sequence;
636 if(vb->pcm){ /* not pcm to process if vorbis_synthesis_trackonly
637 was called on block */
638 int n=ci->blocksizes[v->W]/2;
639 int n0=ci->blocksizes[0]/2;
640 int n1=ci->blocksizes[1]/2;
645 v->glue_bits+=vb->glue_bits;
646 v->time_bits+=vb->time_bits;
647 v->floor_bits+=vb->floor_bits;
648 v->res_bits+=vb->res_bits;
658 /* v->pcm is now used like a two-stage double buffer. We don't want
659 to have to constantly shift *or* adjust memory usage. Don't
660 accept a new block until the old is shifted out */
662 /* overlap/add PCM */
664 for(j=0;j<vi->channels;j++){
665 /* the overlap/add section */
669 float *pcm=v->pcm[j]+prevCenter;
675 float *pcm=v->pcm[j]+prevCenter+n1/2-n0/2;
683 float *pcm=v->pcm[j]+prevCenter;
684 float *p=vb->pcm[j]+n1/2-n0/2;
687 for(;i<n1/2+n0/2;i++)
691 float *pcm=v->pcm[j]+prevCenter;
698 /* the copy section */
700 float *pcm=v->pcm[j]+thisCenter;
701 float *p=vb->pcm[j]+n;
712 /* deal with initial packet state; we do this using the explicit
713 pcm_returned==-1 flag otherwise we're sensitive to first block
714 being short or long */
716 if(v->pcm_returned==-1){
717 v->pcm_returned=thisCenter;
718 v->pcm_current=thisCenter;
720 v->pcm_returned=prevCenter;
721 v->pcm_current=prevCenter+
722 ci->blocksizes[v->lW]/4+
723 ci->blocksizes[v->W]/4;
728 /* track the frame number... This is for convenience, but also
729 making sure our last packet doesn't end with added padding. If
730 the last packet is partial, the number of samples we'll have to
731 return will be past the vb->granulepos.
733 This is not foolproof! It will be confused if we begin
734 decoding at the last page after a seek or hole. In that case,
735 we don't have a starting point to judge where the last frame
736 is. For this reason, vorbisfile will always try to make sure
737 it reads the last two marked pages in proper sequence */
739 if(v->granulepos==-1){
740 if(vb->granulepos!=-1){ /* only set if we have a position to set to */
741 v->granulepos=vb->granulepos;
744 v->granulepos+=ci->blocksizes[v->lW]/4+ci->blocksizes[v->W]/4;
745 if(vb->granulepos!=-1 && v->granulepos!=vb->granulepos){
747 if(v->granulepos>vb->granulepos){
748 long extra=v->granulepos-vb->granulepos;
751 /* partial last frame. Strip the extra samples off */
752 v->pcm_current-=extra;
753 }else if(vb->sequence == 1){
754 /* ^^^ argh, this can be 1 from seeking! */
757 /* partial first frame. Discard extra leading samples */
758 v->pcm_returned+=extra;
759 if(v->pcm_returned>v->pcm_current)
760 v->pcm_returned=v->pcm_current;
762 } /* else {Shouldn't happen *unless* the bitstream is out of
763 spec. Either way, believe the bitstream } */
764 } /* else {Shouldn't happen *unless* the bitstream is out of
765 spec. Either way, believe the bitstream } */
766 v->granulepos=vb->granulepos;
770 /* Update, cleanup */
772 if(vb->eofflag)v->eofflag=1;
777 /* pcm==NULL indicates we just want the pending samples, no more */
778 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,float ***pcm){
779 vorbis_info *vi=v->vi;
780 if(v->pcm_returned>-1 && v->pcm_returned<v->pcm_current){
783 for(i=0;i<vi->channels;i++)
784 v->pcmret[i]=v->pcm[i]+v->pcm_returned;
787 return(v->pcm_current-v->pcm_returned);
792 int vorbis_synthesis_read(vorbis_dsp_state *v,int n){
793 if(n && v->pcm_returned+n>v->pcm_current)return(OV_EINVAL);