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.25 2000/02/06 13:39:38 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 ********************************************************************/
29 #include "vorbis/codec.h"
37 #include "bookinternal.h"
39 static int ilog2(unsigned int v){
48 /* pcm accumulator examples (not exhaustive):
50 <-------------- lW ---------------->
51 <--------------- W ---------------->
52 : .....|..... _______________ |
53 : .''' | '''_--- | |\ |
54 :.....''' |_____--- '''......| | \_______|
55 :.................|__________________|_______|__|______|
56 |<------ Sl ------>| > Sr < |endW
57 |beginSl |endSl | |endSr
58 |beginW |endlW |beginSr
62 <--------------- W ---------------->
63 | | .. ______________ |
65 |___.'___/`. | ---_____|
66 |_______|__|_______|_________________|
67 | >|Sl|< |<------ Sr ----->|endW
68 | | |endSl |beginSr |endSr
70 mult[0] |beginSl mult[n]
72 <-------------- lW ----------------->
74 : .............. ___ | |
76 :.....''' |/`....\|...|
77 :.........................|___|___|___|
86 /* block abstraction setup *********************************************/
92 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
93 memset(vb,0,sizeof(vorbis_block));
98 _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 realloc... there are outstanding pointers */
108 struct alloc_chain *link=malloc(sizeof(struct alloc_chain));
109 vb->totaluse+=vb->localtop;
111 link->ptr=vb->localstore;
114 /* highly conservative */
115 vb->localalloc=bytes;
116 vb->localstore=malloc(vb->localalloc);
120 void *ret=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;
133 memset(reap,0,sizeof(struct alloc_chain));
137 /* consolidate storage */
139 vb->localstore=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)free(vb->localstore);
156 memset(vb,0,sizeof(vorbis_block));
160 /* Analysis side code, but directly related to blocking. Thus it's
161 here and not in analysis.c (which is for analysis transforms only).
162 The init is here because some of it is shared */
164 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi){
166 memset(v,0,sizeof(vorbis_dsp_state));
169 v->modebits=ilog2(vi->modes);
171 v->transform[0]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
172 v->transform[1]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
174 /* MDCT is tranform 0 */
176 v->transform[0][0]=calloc(1,sizeof(mdct_lookup));
177 v->transform[1][0]=calloc(1,sizeof(mdct_lookup));
178 mdct_init(v->transform[0][0],vi->blocksizes[0]);
179 mdct_init(v->transform[1][0],vi->blocksizes[1]);
181 v->window[0][0][0]=calloc(VI_WINDOWB,sizeof(double *));
182 v->window[0][0][1]=v->window[0][0][0];
183 v->window[0][1][0]=v->window[0][0][0];
184 v->window[0][1][1]=v->window[0][0][0];
185 v->window[1][0][0]=calloc(VI_WINDOWB,sizeof(double *));
186 v->window[1][0][1]=calloc(VI_WINDOWB,sizeof(double *));
187 v->window[1][1][0]=calloc(VI_WINDOWB,sizeof(double *));
188 v->window[1][1][1]=calloc(VI_WINDOWB,sizeof(double *));
190 for(i=0;i<VI_WINDOWB;i++){
191 v->window[0][0][0][i]=
192 _vorbis_window(i,vi->blocksizes[0],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
193 v->window[1][0][0][i]=
194 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
195 v->window[1][0][1][i]=
196 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[1]/2);
197 v->window[1][1][0][i]=
198 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[0]/2);
199 v->window[1][1][1][i]=
200 _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[1]/2);
203 /* initialize all the mapping/backend lookups */
204 v->mode=calloc(vi->modes,sizeof(vorbis_look_mapping *));
205 for(i=0;i<vi->modes;i++){
206 int mapnum=vi->mode_param[i]->mapping;
207 int maptype=vi->map_type[mapnum];
208 v->mode[i]=_mapping_P[maptype]->look(vi,vi->mode_param[i],
209 vi->map_param[mapnum]);
212 /* initialize the storage vectors to a decent size greater than the
215 v->pcm_storage=8192; /* we'll assume later that we have
216 a minimum of twice the blocksize of
217 accumulated samples in analysis */
218 v->pcm=malloc(vi->channels*sizeof(double *));
219 v->pcmret=malloc(vi->channels*sizeof(double *));
222 for(i=0;i<vi->channels;i++)
223 v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
226 /* all 1 (large block) or 0 (small block) */
227 /* explicitly set for the sake of clarity */
228 v->lW=0; /* previous window size */
229 v->W=0; /* current window size */
231 /* all vector indexes; multiples of samples_per_envelope_step */
232 v->centerW=vi->blocksizes[1]/2;
234 v->pcm_current=v->centerW;
238 /* arbitrary settings and spec-mandated numbers get filled in here */
239 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
241 _vds_shared_init(v,vi);
243 /* finish the codebooks */
244 v->fullbooks=calloc(vi->books,sizeof(codebook));
245 for(i=0;i<vi->books;i++)
246 vorbis_book_init_encode(v->fullbooks+i,vi->book_param[i]);
248 /* Initialize the envelope multiplier storage */
250 v->envelope_storage=v->pcm_storage/vi->envelopesa;
251 v->multipliers=calloc(v->envelope_storage,sizeof(double));
252 _ve_envelope_init(&v->ve,vi->envelopesa);
254 /* the coder init is different for read/write */
257 v->envelope_current=v->centerW/vi->envelopesa;
261 void vorbis_dsp_clear(vorbis_dsp_state *v){
264 vorbis_info *vi=v->vi;
266 for(i=0;i<VI_WINDOWB;i++){
267 if(v->window[0][0][0][i])free(v->window[0][0][0][i]);
270 if(v->window[1][j][k][i])free(v->window[1][j][k][i]);
273 for(i=0;i<vi->channels;i++)
274 if(v->pcm[i])free(v->pcm[i]);
276 if(v->pcmret)free(v->pcmret);
278 if(v->multipliers)free(v->multipliers);
280 _ve_envelope_clear(&v->ve);
281 mdct_clear(v->transform[0][0]);
282 mdct_clear(v->transform[1][0]);
283 free(v->transform[0][0]);
284 free(v->transform[1][0]);
286 free(v->transform[0]);
287 free(v->transform[1]);
289 /* free mode lookups; these are actually vorbis_look_mapping structs */
290 for(i=0;i<vi->modes;i++){
291 int mapnum=vi->mode_param[i]->mapping;
292 int maptype=vi->map_type[mapnum];
293 _mapping_P[maptype]->free_look(v->mode[i]);
295 if(v->mode)free(v->mode);
298 for(i=0;i<vi->books;i++)
299 vorbis_book_clear(v->fullbooks+i);
300 if(v->fullbooks)free(v->fullbooks);
302 /* free header, header1, header2 */
303 if(v->header)free(v->header);
304 if(v->header1)free(v->header1);
305 if(v->header2)free(v->header2);
307 memset(v,0,sizeof(vorbis_dsp_state));
311 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
313 vorbis_info *vi=v->vi;
315 /* free header, header1, header2 */
316 if(v->header)free(v->header);v->header=NULL;
317 if(v->header1)free(v->header1);v->header1=NULL;
318 if(v->header2)free(v->header2);v->header2=NULL;
320 /* Do we have enough storage space for the requested buffer? If not,
321 expand the PCM (and envelope) storage */
323 if(v->pcm_current+vals>=v->pcm_storage){
324 v->pcm_storage=v->pcm_current+vals*2;
325 v->envelope_storage=v->pcm_storage/v->vi->envelopesa;
327 for(i=0;i<vi->channels;i++){
328 v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
330 v->multipliers=realloc(v->multipliers,v->envelope_storage*sizeof(double));
333 for(i=0;i<vi->channels;i++)
334 v->pcmret[i]=v->pcm[i]+v->pcm_current;
339 /* call with val<=0 to set eof */
341 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
342 vorbis_info *vi=v->vi;
344 /* We're encoding the end of the stream. Just make sure we have
345 [at least] a full block of zeroes at the end. */
348 vorbis_analysis_buffer(v,v->vi->blocksizes[1]*2);
349 v->eofflag=v->pcm_current;
350 v->pcm_current+=v->vi->blocksizes[1]*2;
351 for(i=0;i<vi->channels;i++)
352 memset(v->pcm[i]+v->eofflag,0,
353 (v->pcm_current-v->eofflag)*sizeof(double));
356 if(v->pcm_current+vals>v->pcm_storage)
359 v->pcm_current+=vals;
364 /* do the deltas, envelope shaping, pre-echo and determine the size of
365 the next block on which to continue analysis */
366 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
368 vorbis_info *vi=v->vi;
369 long beginW=v->centerW-vi->blocksizes[v->W]/2,centerNext;
371 /* check to see if we're done... */
372 if(v->eofflag==-1)return(0);
374 /* if we have any unfilled envelope blocks for which we have PCM
375 data, fill them up in before proceeding. */
377 if(v->pcm_current/vi->envelopesa>v->envelope_current){
378 /* This generates the multipliers, but does not sparsify the vector.
379 That's done by block before coding */
380 _ve_envelope_deltas(v);
383 /* By our invariant, we have lW, W and centerW set. Search for
384 the next boundary so we can determine nW (the next window size)
385 which lets us compute the shape of the current block's window */
387 if(vi->blocksizes[0]<vi->blocksizes[1]){
390 /* this is a long window; we start the search forward of centerW
391 because that's the fastest we could react anyway */
392 i=v->centerW+vi->blocksizes[1]/4-vi->blocksizes[0]/4;
394 /* short window. Search from centerW */
398 for(;i<v->envelope_current-1;i++){
399 /* Compare last with current; do we have an abrupt energy change? */
401 if(v->multipliers[i-1]*vi->preecho_thresh<
402 v->multipliers[i])break;
404 /* because the overlapping nature of the delta finding
405 'smears' the energy cliffs, also compare completely
406 unoverlapped areas just in case the plosive happened in an
409 if(v->multipliers[i-1]*vi->preecho_thresh<
410 v->multipliers[i+1])break;
414 if(i<v->envelope_current-1){
415 /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
416 upcoming block large ? */
419 /* min boundary; nW large, next small */
420 largebound=v->centerW+vi->blocksizes[1]*3/4+vi->blocksizes[0]/4;
422 /* min boundary; nW large, next small */
423 largebound=v->centerW+vi->blocksizes[0]/2+vi->blocksizes[1]/2;
424 largebound/=vi->envelopesa;
432 /* Assume maximum; if the block is incomplete given current
433 buffered data, this will be detected below */
439 /* Do we actually have enough data *now* for the next block? The
440 reason to check is that if we had no multipliers, that could
441 simply been due to running out of data. In that case, we don't
442 know the size of the next block for sure and we need that now to
443 figure out the window shape of this block */
445 centerNext=v->centerW+vi->blocksizes[v->W]/4+vi->blocksizes[v->nW]/4;
448 /* center of next block + next block maximum right side. Note
449 that the next block needs an additional vi->envelopesa samples
450 to actually be written (for the last multiplier), but we didn't
451 need that to determine its size */
453 long blockbound=centerNext+vi->blocksizes[v->nW]/2;
454 if(v->pcm_current<blockbound)return(0); /* not enough data yet */
457 /* fill in the block. Note that for a short window, lW and nW are *short*
458 regardless of actual settings in the stream */
460 _vorbis_block_ripcord(vb);
471 vb->sequence=v->sequence;
472 vb->frameno=v->frameno;
473 vb->pcmend=vi->blocksizes[v->W];
475 /* copy the vectors; this uses the local storage in vb */
477 vb->pcm=_vorbis_block_alloc(vb,sizeof(double *)*vi->channels);
478 for(i=0;i<vi->channels;i++){
479 vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(double));
480 memcpy(vb->pcm[i],v->pcm[i]+beginW,vi->blocksizes[v->W]*sizeof(double));
484 /* handle eof detection: eof==0 means that we've not yet received EOF
485 eof>0 marks the last 'real' sample in pcm[]
486 eof<0 'no more to do'; doesn't get here */
489 if(v->centerW>=v->eofflag){
495 /* advance storage vectors and clean up */
497 int new_centerNext=vi->blocksizes[1]/2;
498 int movementW=centerNext-new_centerNext;
499 int movementM=movementW/vi->envelopesa;
501 /* the multipliers and pcm stay synced up because the blocksize
502 must be multiples of samples_per_envelope_step (minimum
505 v->pcm_current-=movementW;
506 v->envelope_current-=movementM;
508 for(i=0;i<vi->channels;i++)
509 memmove(v->pcm[i],v->pcm[i]+movementW,
510 v->pcm_current*sizeof(double));
512 memmove(v->multipliers,v->multipliers+movementM,
513 v->envelope_current*sizeof(double));
517 v->centerW=new_centerNext;
520 v->frameno+=movementW;
523 v->eofflag-=movementW;
530 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
532 _vds_shared_init(v,vi);
534 /* finish the codebooks */
535 v->fullbooks=calloc(vi->books,sizeof(codebook));
536 for(i=0;i<vi->books;i++)
537 vorbis_book_init_decode(v->fullbooks+i,vi->book_param[i]);
539 /* Adjust centerW to allow an easier mechanism for determining output */
540 v->pcm_returned=v->centerW;
541 v->centerW-= vi->blocksizes[v->W]/4+vi->blocksizes[v->lW]/4;
545 /* Unike in analysis, the window is only partially applied for each
546 block. The time domain envelope is not yet handled at the point of
547 calling (as it relies on the previous block). */
549 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
550 vorbis_info *vi=v->vi;
552 /* Shift out any PCM/multipliers that we returned previously */
553 /* centerW is currently the center of the last block added */
554 if(v->pcm_returned && v->centerW>vi->blocksizes[1]/2){
556 /* don't shift too much; we need to have a minimum PCM buffer of
559 int shiftPCM=v->centerW-vi->blocksizes[1]/2;
560 shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
562 v->pcm_current-=shiftPCM;
563 v->centerW-=shiftPCM;
564 v->pcm_returned-=shiftPCM;
568 for(i=0;i<vi->channels;i++)
569 memmove(v->pcm[i],v->pcm[i]+shiftPCM,
570 v->pcm_current*sizeof(double));
578 v->glue_bits+=vb->glue_bits;
579 v->time_bits+=vb->time_bits;
580 v->floor_bits+=vb->floor_bits;
581 v->res_bits+=vb->res_bits;
582 v->sequence=vb->sequence;
585 int sizeW=vi->blocksizes[v->W];
586 int centerW=v->centerW+vi->blocksizes[v->lW]/4+sizeW/4;
587 int beginW=centerW-sizeW/2;
588 int endW=beginW+sizeW;
593 /* Do we have enough PCM/mult storage for the block? */
594 if(endW>v->pcm_storage){
595 /* expand the storage */
596 v->pcm_storage=endW+vi->blocksizes[1];
598 for(i=0;i<vi->channels;i++)
599 v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
602 /* overlap/add PCM */
607 endSl=vi->blocksizes[0]/2;
610 beginSl=vi->blocksizes[1]/4-vi->blocksizes[v->lW]/4;
611 endSl=beginSl+vi->blocksizes[v->lW]/2;
615 for(j=0;j<vi->channels;j++){
616 double *pcm=v->pcm[j]+beginW;
618 /* the overlap/add section */
619 for(i=beginSl;i<endSl;i++)
620 pcm[i]+=vb->pcm[j][i];
621 /* the remaining section */
623 pcm[i]=vb->pcm[j][i];
626 /* Update, cleanup */
631 if(vb->eofflag)v->eofflag=1;
636 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
637 vorbis_info *vi=v->vi;
638 if(v->pcm_returned<v->centerW){
640 for(i=0;i<vi->channels;i++)
641 v->pcmret[i]=v->pcm[i]+v->pcm_returned;
643 return(v->centerW-v->pcm_returned);
648 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
649 if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
650 v->pcm_returned+=bytes;