1 /********************************************************************
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. *
8 * THE OggVorbis 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.40 2000/11/06 00:07:00 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"
41 static int ilog2(unsigned int v){
50 /* pcm accumulator examples (not exhaustive):
52 <-------------- lW ---------------->
53 <--------------- W ---------------->
54 : .....|..... _______________ |
55 : .''' | '''_--- | |\ |
56 :.....''' |_____--- '''......| | \_______|
57 :.................|__________________|_______|__|______|
58 |<------ Sl ------>| > Sr < |endW
59 |beginSl |endSl | |endSr
60 |beginW |endlW |beginSr
64 <--------------- W ---------------->
65 | | .. ______________ |
67 |___.'___/`. | ---_____|
68 |_______|__|_______|_________________|
69 | >|Sl|< |<------ Sr ----->|endW
70 | | |endSl |beginSr |endSr
72 mult[0] |beginSl mult[n]
74 <-------------- lW ----------------->
76 : .............. ___ | |
78 :.....''' |/`....\|...|
79 :.........................|___|___|___|
88 /* block abstraction setup *********************************************/
94 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
95 memset(vb,0,sizeof(vorbis_block));
100 oggpack_writeinit(&vb->opb);
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 */
110 struct alloc_chain *link=_ogg_malloc(sizeof(struct alloc_chain));
111 vb->totaluse+=vb->localtop;
113 link->ptr=vb->localstore;
116 /* highly conservative */
117 vb->localalloc=bytes;
118 vb->localstore=_ogg_malloc(vb->localalloc);
122 void *ret=(void *)(((char *)vb->localstore)+vb->localtop);
128 /* reap the chain, pull the ripcord */
129 void _vorbis_block_ripcord(vorbis_block *vb){
131 struct alloc_chain *reap=vb->reap;
133 struct alloc_chain *next=reap->next;
135 memset(reap,0,sizeof(struct alloc_chain));
139 /* consolidate storage */
141 vb->localstore=_ogg_realloc(vb->localstore,vb->totaluse+vb->localalloc);
142 vb->localalloc+=vb->totaluse;
146 /* pull the ripcord */
151 int vorbis_block_clear(vorbis_block *vb){
153 if(vb->vd->analysisp)
154 oggpack_writeclear(&vb->opb);
155 _vorbis_block_ripcord(vb);
156 if(vb->localstore)free(vb->localstore);
158 memset(vb,0,sizeof(vorbis_block));
162 /* Analysis side code, but directly related to blocking. Thus it's
163 here and not in analysis.c (which is for analysis transforms only).
164 The init is here because some of it is shared */
166 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi,int encp){
168 codec_setup_info *ci=vi->codec_setup;
169 backend_lookup_state *b=NULL;
171 memset(v,0,sizeof(vorbis_dsp_state));
172 b=v->backend_state=_ogg_calloc(1,sizeof(backend_lookup_state));
175 b->modebits=ilog2(ci->modes);
177 b->transform[0]=_ogg_calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
178 b->transform[1]=_ogg_calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
180 /* MDCT is tranform 0 */
182 b->transform[0][0]=_ogg_calloc(1,sizeof(mdct_lookup));
183 b->transform[1][0]=_ogg_calloc(1,sizeof(mdct_lookup));
184 mdct_init(b->transform[0][0],ci->blocksizes[0]);
185 mdct_init(b->transform[1][0],ci->blocksizes[1]);
187 b->window[0][0][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
188 b->window[0][0][1]=b->window[0][0][0];
189 b->window[0][1][0]=b->window[0][0][0];
190 b->window[0][1][1]=b->window[0][0][0];
191 b->window[1][0][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
192 b->window[1][0][1]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
193 b->window[1][1][0]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
194 b->window[1][1][1]=_ogg_calloc(VI_WINDOWB,sizeof(float *));
196 for(i=0;i<VI_WINDOWB;i++){
197 b->window[0][0][0][i]=
198 _vorbis_window(i,ci->blocksizes[0],ci->blocksizes[0]/2,ci->blocksizes[0]/2);
199 b->window[1][0][0][i]=
200 _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[0]/2,ci->blocksizes[0]/2);
201 b->window[1][0][1][i]=
202 _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[0]/2,ci->blocksizes[1]/2);
203 b->window[1][1][0][i]=
204 _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[1]/2,ci->blocksizes[0]/2);
205 b->window[1][1][1][i]=
206 _vorbis_window(i,ci->blocksizes[1],ci->blocksizes[1]/2,ci->blocksizes[1]/2);
209 if(encp){ /* encode/decode differ here */
210 /* finish the codebooks */
211 b->fullbooks=_ogg_calloc(ci->books,sizeof(codebook));
212 for(i=0;i<ci->books;i++)
213 vorbis_book_init_encode(b->fullbooks+i,ci->book_param[i]);
216 /* finish the codebooks */
217 b->fullbooks=_ogg_calloc(ci->books,sizeof(codebook));
218 for(i=0;i<ci->books;i++)
219 vorbis_book_init_decode(b->fullbooks+i,ci->book_param[i]);
222 /* initialize the storage vectors to a decent size greater than the
225 v->pcm_storage=8192; /* we'll assume later that we have
226 a minimum of twice the blocksize of
227 accumulated samples in analysis */
228 v->pcm=_ogg_malloc(vi->channels*sizeof(float *));
229 v->pcmret=_ogg_malloc(vi->channels*sizeof(float *));
232 for(i=0;i<vi->channels;i++)
233 v->pcm[i]=_ogg_calloc(v->pcm_storage,sizeof(float));
236 /* all 1 (large block) or 0 (small block) */
237 /* explicitly set for the sake of clarity */
238 v->lW=0; /* previous window size */
239 v->W=0; /* current window size */
241 /* all vector indexes */
242 v->centerW=ci->blocksizes[1]/2;
244 v->pcm_current=v->centerW;
246 /* initialize all the mapping/backend lookups */
247 b->mode=_ogg_calloc(ci->modes,sizeof(vorbis_look_mapping *));
248 for(i=0;i<ci->modes;i++){
249 int mapnum=ci->mode_param[i]->mapping;
250 int maptype=ci->map_type[mapnum];
251 b->mode[i]=_mapping_P[maptype]->look(v,ci->mode_param[i],
252 ci->map_param[mapnum]);
258 /* arbitrary settings and spec-mandated numbers get filled in here */
259 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
260 backend_lookup_state *b=NULL;
262 _vds_shared_init(v,vi,1);
265 /* Initialize the envelope state storage */
266 b->ve=_ogg_calloc(1,sizeof(envelope_lookup));
267 _ve_envelope_init(b->ve,vi);
272 void vorbis_dsp_clear(vorbis_dsp_state *v){
275 vorbis_info *vi=v->vi;
276 codec_setup_info *ci=(vi?vi->codec_setup:NULL);
277 backend_lookup_state *b=v->backend_state;
280 if(b->window[0][0][0]){
281 for(i=0;i<VI_WINDOWB;i++)
282 if(b->window[0][0][0][i])free(b->window[0][0][0][i]);
283 free(b->window[0][0][0]);
287 for(i=0;i<VI_WINDOWB;i++)
288 if(b->window[1][j][k][i])free(b->window[1][j][k][i]);
289 free(b->window[1][j][k]);
294 _ve_envelope_clear(b->ve);
299 mdct_clear(b->transform[0][0]);
300 free(b->transform[0][0]);
301 free(b->transform[0]);
304 mdct_clear(b->transform[1][0]);
305 free(b->transform[1][0]);
306 free(b->transform[1]);
312 for(i=0;i<vi->channels;i++)
313 if(v->pcm[i])free(v->pcm[i]);
315 if(v->pcmret)free(v->pcmret);
318 /* free mode lookups; these are actually vorbis_look_mapping structs */
320 for(i=0;i<ci->modes;i++){
321 int mapnum=ci->mode_param[i]->mapping;
322 int maptype=ci->map_type[mapnum];
323 if(b && b->mode)_mapping_P[maptype]->free_look(b->mode[i]);
326 for(i=0;i<ci->books;i++)
327 if(b && b->fullbooks)vorbis_book_clear(b->fullbooks+i);
331 if(b->mode)free(b->mode);
332 if(b->fullbooks)free(b->fullbooks);
334 /* free header, header1, header2 */
335 if(b->header)free(b->header);
336 if(b->header1)free(b->header1);
337 if(b->header2)free(b->header2);
341 memset(v,0,sizeof(vorbis_dsp_state));
345 float **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
347 vorbis_info *vi=v->vi;
348 backend_lookup_state *b=v->backend_state;
350 /* free header, header1, header2 */
351 if(b->header)free(b->header);b->header=NULL;
352 if(b->header1)free(b->header1);b->header1=NULL;
353 if(b->header2)free(b->header2);b->header2=NULL;
355 /* Do we have enough storage space for the requested buffer? If not,
356 expand the PCM (and envelope) storage */
358 if(v->pcm_current+vals>=v->pcm_storage){
359 v->pcm_storage=v->pcm_current+vals*2;
361 for(i=0;i<vi->channels;i++){
362 v->pcm[i]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(float));
366 for(i=0;i<vi->channels;i++)
367 v->pcmret[i]=v->pcm[i]+v->pcm_current;
372 static void _preextrapolate_helper(vorbis_dsp_state *v){
375 float *lpc=alloca(order*sizeof(float));
376 float *work=alloca(v->pcm_current*sizeof(float));
380 if(v->pcm_current-v->centerW>order*2){ /* safety */
381 for(i=0;i<v->vi->channels;i++){
383 /* need to run the extrapolation in reverse! */
384 for(j=0;j<v->pcm_current;j++)
385 work[j]=v->pcm[i][v->pcm_current-j-1];
388 vorbis_lpc_from_data(work,lpc,v->pcm_current-v->centerW,order);
390 /* run the predictor filter */
391 vorbis_lpc_predict(lpc,work+v->pcm_current-v->centerW-order,
393 work+v->pcm_current-v->centerW,
395 for(j=0;j<v->pcm_current;j++)
396 v->pcm[i][v->pcm_current-j-1]=work[j];
402 /* call with val<=0 to set eof */
404 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
405 vorbis_info *vi=v->vi;
406 codec_setup_info *ci=vi->codec_setup;
411 float *lpc=alloca(order*sizeof(float));
413 /* if it wasn't done earlier (very short sample) */
414 if(!v->preextrapolate)
415 _preextrapolate_helper(v);
417 /* We're encoding the end of the stream. Just make sure we have
418 [at least] a full block of zeroes at the end. */
419 /* actually, we don't want zeroes; that could drop a large
420 amplitude off a cliff, creating spread spectrum noise that will
421 suck to encode. Extrapolate for the sake of cleanliness. */
423 vorbis_analysis_buffer(v,ci->blocksizes[1]*2);
424 v->eofflag=v->pcm_current;
425 v->pcm_current+=ci->blocksizes[1]*2;
427 for(i=0;i<vi->channels;i++){
428 if(v->eofflag>order*2){
429 /* extrapolate with LPC to fill in */
432 /* make a predictor filter */
434 if(n>ci->blocksizes[1])n=ci->blocksizes[1];
435 vorbis_lpc_from_data(v->pcm[i]+v->eofflag-n,lpc,n,order);
437 /* run the predictor filter */
438 vorbis_lpc_predict(lpc,v->pcm[i]+v->eofflag-order,order,
439 v->pcm[i]+v->eofflag,v->pcm_current-v->eofflag);
441 /* not enough data to extrapolate (unlikely to happen due to
442 guarding the overlap, but bulletproof in case that
443 assumtion goes away). zeroes will do. */
444 memset(v->pcm[i]+v->eofflag,0,
445 (v->pcm_current-v->eofflag)*sizeof(float));
451 if(v->pcm_current+vals>v->pcm_storage)
454 v->pcm_current+=vals;
456 /* we may want to reverse extrapolate the beginning of a stream
457 too... in case we're beginning on a cliff! */
458 /* clumsy, but simple. It only runs once, so simple is good. */
459 if(!v->preextrapolate && v->pcm_current-v->centerW>ci->blocksizes[1])
460 _preextrapolate_helper(v);
466 /* do the deltas, envelope shaping, pre-echo and determine the size of
467 the next block on which to continue analysis */
468 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
470 vorbis_info *vi=v->vi;
471 codec_setup_info *ci=vi->codec_setup;
472 backend_lookup_state *b=v->backend_state;
473 long beginW=v->centerW-ci->blocksizes[v->W]/2,centerNext;
475 /* check to see if we're started... */
476 if(!v->preextrapolate)return(0);
478 /* check to see if we're done... */
479 if(v->eofflag==-1)return(0);
481 /* By our invariant, we have lW, W and centerW set. Search for
482 the next boundary so we can determine nW (the next window size)
483 which lets us compute the shape of the current block's window */
485 if(ci->blocksizes[0]<ci->blocksizes[1]){
490 /* min boundary; nW large, next small */
491 largebound=v->centerW+ci->blocksizes[1]*3/4+ci->blocksizes[0]/4;
493 /* min boundary; nW large, next small */
494 largebound=v->centerW+ci->blocksizes[1]*3/4+ci->blocksizes[0]*3/4;
496 bp=_ve_envelope_search(v,largebound);
497 if(bp==-1)return(0); /* not enough data currently to search for a
504 centerNext=v->centerW+ci->blocksizes[v->W]/4+ci->blocksizes[v->nW]/4;
507 /* center of next block + next block maximum right side. */
509 long blockbound=centerNext+ci->blocksizes[v->nW]/2;
510 if(v->pcm_current<blockbound)return(0); /* not enough data yet;
511 although this check is
514 the search is not run
519 /* fill in the block. Note that for a short window, lW and nW are *short*
520 regardless of actual settings in the stream */
522 _vorbis_block_ripcord(vb);
533 vb->sequence=v->sequence;
534 vb->granulepos=v->granulepos;
535 vb->pcmend=ci->blocksizes[v->W];
537 /* copy the vectors; this uses the local storage in vb */
539 vb->pcm=_vorbis_block_alloc(vb,sizeof(float *)*vi->channels);
540 for(i=0;i<vi->channels;i++){
541 vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(float));
542 memcpy(vb->pcm[i],v->pcm[i]+beginW,ci->blocksizes[v->W]*sizeof(float));
546 /* handle eof detection: eof==0 means that we've not yet received EOF
547 eof>0 marks the last 'real' sample in pcm[]
548 eof<0 'no more to do'; doesn't get here */
551 if(v->centerW>=v->eofflag){
558 /* advance storage vectors and clean up */
560 int new_centerNext=ci->blocksizes[1]/2;
561 int movementW=centerNext-new_centerNext;
563 _ve_envelope_shift(b->ve,movementW);
564 v->pcm_current-=movementW;
566 for(i=0;i<vi->channels;i++)
567 memmove(v->pcm[i],v->pcm[i]+movementW,
568 v->pcm_current*sizeof(float));
573 v->centerW=new_centerNext;
578 v->eofflag-=movementW;
579 /* do not add padding to end of stream! */
580 if(v->centerW>=v->eofflag){
581 v->granulepos+=movementW-(v->centerW-v->eofflag);
583 v->granulepos+=movementW;
586 v->granulepos+=movementW;
594 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
595 codec_setup_info *ci=vi->codec_setup;
596 _vds_shared_init(v,vi,0);
598 /* Adjust centerW to allow an easier mechanism for determining output */
599 v->pcm_returned=v->centerW;
600 v->centerW-= ci->blocksizes[v->W]/4+ci->blocksizes[v->lW]/4;
607 /* Unlike in analysis, the window is only partially applied for each
608 block. The time domain envelope is not yet handled at the point of
609 calling (as it relies on the previous block). */
611 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
612 vorbis_info *vi=v->vi;
613 codec_setup_info *ci=vi->codec_setup;
615 /* Shift out any PCM that we returned previously */
616 /* centerW is currently the center of the last block added */
617 if(v->pcm_returned && v->centerW>ci->blocksizes[1]/2){
619 /* don't shift too much; we need to have a minimum PCM buffer of
622 int shiftPCM=v->centerW-ci->blocksizes[1]/2;
623 shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
625 v->pcm_current-=shiftPCM;
626 v->centerW-=shiftPCM;
627 v->pcm_returned-=shiftPCM;
631 for(i=0;i<vi->channels;i++)
632 memmove(v->pcm[i],v->pcm[i]+shiftPCM,
633 v->pcm_current*sizeof(float));
641 v->glue_bits+=vb->glue_bits;
642 v->time_bits+=vb->time_bits;
643 v->floor_bits+=vb->floor_bits;
644 v->res_bits+=vb->res_bits;
646 if(v->sequence+1 != vb->sequence)v->granulepos=-1; /* out of sequence;
649 v->sequence=vb->sequence;
652 int sizeW=ci->blocksizes[v->W];
653 int centerW=v->centerW+ci->blocksizes[v->lW]/4+sizeW/4;
654 int beginW=centerW-sizeW/2;
655 int endW=beginW+sizeW;
660 /* Do we have enough PCM/mult storage for the block? */
661 if(endW>v->pcm_storage){
662 /* expand the storage */
663 v->pcm_storage=endW+ci->blocksizes[1];
665 for(i=0;i<vi->channels;i++)
666 v->pcm[i]=_ogg_realloc(v->pcm[i],v->pcm_storage*sizeof(float));
669 /* overlap/add PCM */
674 endSl=ci->blocksizes[0]/2;
677 beginSl=ci->blocksizes[1]/4-ci->blocksizes[v->lW]/4;
678 endSl=beginSl+ci->blocksizes[v->lW]/2;
682 for(j=0;j<vi->channels;j++){
683 float *pcm=v->pcm[j]+beginW;
686 /* the overlap/add section */
687 for(i=beginSl;i<endSl;i++)
689 /* the remaining section */
694 /* track the frame number... This is for convenience, but also
695 making sure our last packet doesn't end with added padding. If
696 the last packet is partial, the number of samples we'll have to
697 return will be past the vb->granulepos.
699 This is not foolproof! It will be confused if we begin
700 decoding at the last page after a seek or hole. In that case,
701 we don't have a starting point to judge where the last frame
702 is. For this reason, vorbisfile will always try to make sure
703 it reads the last two marked pages in proper sequence */
705 if(v->granulepos==-1)
706 if(vb->granulepos==-1){
709 v->granulepos=vb->granulepos;
712 v->granulepos+=(centerW-v->centerW);
713 if(vb->granulepos!=-1 && v->granulepos!=vb->granulepos){
715 if(v->granulepos>vb->granulepos){
716 long extra=v->granulepos-vb->granulepos;
719 /* partial last frame. Strip the extra samples off */
721 }else if(vb->sequence == 1){
722 /* partial first frame. Discard extra leading samples */
723 v->pcm_returned+=extra;
724 if(v->pcm_returned>centerW)v->pcm_returned=centerW;
728 }/* else{ Shouldn't happen *unless* the bitstream is out of
729 spec. Either way, believe the bitstream } */
730 v->granulepos=vb->granulepos;
734 /* Update, cleanup */
739 if(vb->eofflag)v->eofflag=1;
745 /* pcm==NULL indicates we just want the pending samples, no more */
746 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,float ***pcm){
747 vorbis_info *vi=v->vi;
748 if(v->pcm_returned<v->centerW){
751 for(i=0;i<vi->channels;i++)
752 v->pcmret[i]=v->pcm[i]+v->pcm_returned;
755 return(v->centerW-v->pcm_returned);
760 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
761 if(bytes && v->pcm_returned+bytes>v->centerW)return(OV_EINVAL);
762 v->pcm_returned+=bytes;