Envelope infrastructure now in place. Basic preecho running (but
[platform/upstream/libvorbis.git] / lib / block.c
1 /********************************************************************
2  *                                                                  *
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.                            *
7  *                                                                  *
8  * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999             *
9  * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company       *
10  * http://www.xiph.org/                                             *
11  *                                                                  *
12  ********************************************************************
13
14  function: PCM data vector blocking, windowing and dis/reassembly
15  author: Monty <xiphmont@mit.edu>
16  modifications by: Monty
17  last modification date: Aug 05 1999
18
19  Handle windowing, overlap-add, etc of the PCM vectors.  This is made
20  more amusing by Vorbis' current two allowed block sizes.
21  
22  Vorbis manipulates the dynamic range of the incoming PCM data
23  envelope to minimise time-domain energy leakage from percussive and
24  plosive waveforms being quantized in the MDCT domain.
25
26  ********************************************************************/
27
28 #include <stdlib.h>
29 #include <string.h>
30 #include "codec.h"
31 #include "window.h"
32 #include "envelope.h"
33 #include "mdct.h"
34
35 /* pcm accumulator examples (not exhaustive):
36
37  <-------------- lW ---------------->
38                    <--------------- W ---------------->
39 :            .....|.....       _______________         |
40 :        .'''     |     '''_---      |       |\        |
41 :.....'''         |_____--- '''......|       | \_______|
42 :.................|__________________|_______|__|______|
43                   |<------ Sl ------>|      > Sr <     |endW
44                   |beginSl           |endSl  |  |endSr   
45                   |beginW            |endlW  |beginSr
46
47
48                       |< lW >|       
49                    <--------------- W ---------------->
50                   |   |  ..  ______________            |
51                   |   | '  `/        |     ---_        |
52                   |___.'___/`.       |         ---_____| 
53                   |_______|__|_______|_________________|
54                   |      >|Sl|<      |<------ Sr ----->|endW
55                   |       |  |endSl  |beginSr          |endSr
56                   |beginW |  |endlW                     
57                   mult[0] |beginSl                     mult[n]
58
59  <-------------- lW ----------------->
60                           |<--W-->|                               
61 :            ..............  ___  |   |                    
62 :        .'''             |`/   \ |   |                       
63 :.....'''                 |/`....\|...|                    
64 :.........................|___|___|___|                  
65                           |Sl |Sr |endW    
66                           |   |   |endSr
67                           |   |beginSr
68                           |   |endSl
69                           |beginSl
70                           |beginW
71 */
72
73 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi){
74   memset(v,0,sizeof(vorbis_dsp_state));
75
76   memcpy(&v->vi,vi,sizeof(vorbis_info));
77   _ve_envelope_init(&v->ve,vi->envelopesa);
78
79   v->samples_per_envelope_step=vi->envelopesa;
80   v->block_size[0]=vi->smallblock;
81   v->block_size[1]=vi->largeblock;
82   
83   v->window[0][0][0]=_vorbis_window(v->block_size[0],
84                                    v->block_size[0]/2,v->block_size[0]/2);
85   v->window[0][0][1]=v->window[0][0][0];
86   v->window[0][1][0]=v->window[0][0][0];
87   v->window[0][1][1]=v->window[0][0][0];
88
89   v->window[1][0][0]=_vorbis_window(v->block_size[1],
90                                    v->block_size[0]/2,v->block_size[0]/2);
91   v->window[1][0][1]=_vorbis_window(v->block_size[1],
92                                    v->block_size[0]/2,v->block_size[1]/2);
93   v->window[1][1][0]=_vorbis_window(v->block_size[1],
94                                    v->block_size[1]/2,v->block_size[0]/2);
95   v->window[1][1][1]=_vorbis_window(v->block_size[1],
96                                     v->block_size[1]/2,v->block_size[1]/2);
97
98   /* initialize the storage vectors to a decent size greater than the
99      minimum */
100   
101   v->pcm_storage=8192; /* we'll assume later that we have
102                           a minimum of twice the blocksize of
103                           accumulated samples in analysis */
104   v->pcm_channels=v->vi.channels=vi->channels;
105   v->pcm=malloc(vi->channels*sizeof(double *));
106   v->pcmret=malloc(vi->channels*sizeof(double *));
107   {
108     int i;
109     for(i=0;i<vi->channels;i++)
110       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
111   }
112
113   /* Initialize the envelope multiplier storage */
114
115   if(vi->envelopech){
116     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
117     v->envelope_channels=vi->envelopech;
118     v->multipliers=calloc(v->envelope_channels,sizeof(double *));
119     {
120       int i;
121       for(i=0;i<v->envelope_channels;i++){
122         v->multipliers[i]=calloc(v->envelope_storage,sizeof(double));
123       }
124     }
125   }
126
127   /* all 1 (large block) or 0 (small block) */
128   /* explicitly set for the sake of clarity */
129   v->lW=0; /* previous window size */
130   v->W=0;  /* current window size */
131
132   /* all vector indexes; multiples of samples_per_envelope_step */
133   v->centerW=v->block_size[1]/2;
134
135   v->pcm_current=v->centerW;
136   v->envelope_current=v->centerW/v->samples_per_envelope_step;
137   return(0);
138 }
139
140 /* arbitrary settings and spec-mandated numbers get filled in here */
141 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
142   vi->smallblock=512;
143   vi->largeblock=2048;
144   vi->envelopesa=64;
145   vi->envelopech=vi->channels;
146   vi->preecho_thresh=10.;
147   vi->preecho_thresh=4.;
148   vi->envelopemap=calloc(2,sizeof(int));
149   vi->envelopemap[0]=0;
150   vi->envelopemap[1]=1;
151
152   _vds_shared_init(v,vi);
153
154   return(0);
155 }
156
157 void vorbis_analysis_clear(vorbis_dsp_state *v){
158   int i,j,k;
159   if(v){
160
161     if(v->window[0][0][0])free(v->window[0][0][0]);
162     for(j=0;j<2;j++)
163       for(k=0;k<2;k++)
164         if(v->window[1][j][k])free(v->window[1][j][k]);
165     if(v->pcm){
166       for(i=0;i<v->pcm_channels;i++)
167         if(v->pcm[i])free(v->pcm[i]);
168       free(v->pcm);
169       free(v->pcmret);
170     }
171     if(v->multipliers){
172       for(i=0;i<v->envelope_channels;i++)
173         if(v->multipliers[i])free(v->multipliers[i]);
174       free(v->multipliers);
175     }
176     memset(v,0,sizeof(vorbis_dsp_state));
177   }
178 }
179
180 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
181   int i;
182
183   /* Do we have enough storage space for the requested buffer? If not,
184      expand the PCM (and envelope) storage */
185     
186   if(v->pcm_current+vals>=v->pcm_storage){
187     v->pcm_storage=v->pcm_current+vals*2;
188     v->envelope_storage=v->pcm_storage/v->samples_per_envelope_step;
189    
190     for(i=0;i<v->pcm_channels;i++){
191       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
192     }
193     for(i=0;i<v->envelope_channels;i++){
194       v->multipliers[i]=realloc(v->multipliers[i],
195                                 v->envelope_storage*sizeof(double));
196     }
197   }
198
199   for(i=0;i<v->pcm_channels;i++)
200     v->pcmret[i]=v->pcm[i]+v->pcm_current;
201     
202   return(v->pcmret);
203 }
204
205 /* call with val<=0 to set eof */
206
207 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
208   if(vals<=0){
209     /* We're encoding the end of the stream.  Just make sure we have
210        [at least] a full block of zeroes at the end. */
211
212     int i;
213     vorbis_analysis_buffer(v,v->block_size[1]*2);
214     v->eofflag=v->pcm_current;
215     v->pcm_current+=v->block_size[1]*2;
216     for(i=0;i<v->pcm_channels;i++)
217       memset(v->pcm[i]+v->eofflag,0,
218              (v->pcm_current-v->eofflag)*sizeof(double));
219   }else{
220     
221     if(v->pcm_current+vals>v->pcm_storage)
222       return(-1);
223
224     v->pcm_current+=vals;
225   }
226   return(0);
227 }
228
229 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
230   int i;
231   vb->pcm_storage=v->block_size[1];
232   vb->pcm_channels=v->pcm_channels;
233   vb->mult_storage=v->block_size[1]/v->samples_per_envelope_step;
234   vb->mult_channels=v->envelope_channels;
235   
236   vb->pcm=malloc(vb->pcm_channels*sizeof(double *));
237   for(i=0;i<vb->pcm_channels;i++)
238     vb->pcm[i]=malloc(vb->pcm_storage*sizeof(double));
239   
240   vb->mult=malloc(vb->mult_channels*sizeof(double *));
241   for(i=0;i<vb->mult_channels;i++)
242     vb->mult[i]=malloc(vb->mult_storage*sizeof(double));
243   return(0);
244 }
245
246 int vorbis_block_clear(vorbis_block *vb){
247   int i;
248   if(vb->pcm){
249     for(i=0;i<vb->pcm_channels;i++)
250       free(vb->pcm[i]);
251     free(vb->pcm);
252   }
253   if(vb->mult){
254     for(i=0;i<vb->mult_channels;i++)
255       free(vb->mult[i]);
256     free(vb->mult);
257   }
258   memset(vb,0,sizeof(vorbis_block));
259   return(0);
260 }
261
262 /* do the deltas, envelope shaping, pre-echo and determine the size of
263    the next block on which to continue analysis */
264 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
265   int i,j;
266   long beginW=v->centerW-v->block_size[v->W]/2,centerNext;
267   long beginM=beginW/v->samples_per_envelope_step;
268
269   /* check to see if we're done... */
270   if(v->eofflag==-1)return(0);
271
272   /* if we have any unfilled envelope blocks for which we have PCM
273      data, fill them up in before proceeding. */
274
275   if(v->pcm_current/v->samples_per_envelope_step>v->envelope_current){
276     /* This generates the multipliers, but does not sparsify the vector.
277        That's done by block before coding */
278     _ve_envelope_multipliers(v);
279   }
280
281   /* By our invariant, we have lW, W and centerW set.  Search for
282      the next boundary so we can determine nW (the next window size)
283      which lets us compute the shape of the current block's window */
284
285   /* overconserve for now; any block with a non-placeholder multiplier
286      should be minimal size. We can be greedy and only look at nW size */
287   
288   if(v->W)
289     /* this is a long window; we start the search forward of centerW
290        because that's the fastest we could react anyway */
291     i=v->centerW+v->block_size[1]/4-v->block_size[0]/4;
292   else
293     /* short window.  Search from centerW */
294     i=v->centerW;
295   i/=v->samples_per_envelope_step;
296
297   for(;i<v->envelope_current;i++){
298     for(j=0;j<v->envelope_channels;j++)
299       if(v->multipliers[j][i-1]*v->vi.preecho_thresh<  
300          v->multipliers[j][i])break;
301     if(j<v->envelope_channels)break;
302   }
303   
304   if(i<v->envelope_current){
305     /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
306        upcoming block large ? */
307     long largebound;
308     if(v->W)
309       largebound=v->centerW+v->block_size[1];
310     else
311       largebound=v->centerW+v->block_size[0]/4+v->block_size[1]*3/4;
312     largebound/=v->samples_per_envelope_step;
313
314     if(i>=largebound)
315       v->nW=1;
316     else
317       v->nW=0;
318
319   }else{
320     /* Assume maximum; if the block is incomplete given current
321        buffered data, this will be detected below */
322     v->nW=1;
323   }
324
325   /* Do we actually have enough data *now* for the next block? The
326      reason to check is that if we had no multipliers, that could
327      simply been due to running out of data.  In that case, we don;t
328      know the size of the next block for sure and we need that now to
329      figure out the window shape of this block */
330   
331   centerNext=v->centerW+v->block_size[v->W]/4+v->block_size[v->nW]/4;
332
333   {
334     long blockbound=centerNext+v->block_size[v->nW]/2;
335     if(v->pcm_current<blockbound)return(0); /* not enough data yet */    
336   }
337
338   /* fill in the block */
339   vb->lW=v->lW;
340   vb->W=v->W;
341   vb->nW=v->nW;
342   vb->vd=v;
343
344   vb->pcmend=v->block_size[v->W];
345   vb->multend=vb->pcmend / v->samples_per_envelope_step;
346
347   if(v->pcm_channels!=vb->pcm_channels ||
348      v->block_size[1]!=vb->pcm_storage ||
349      v->envelope_channels!=vb->mult_channels){
350
351     /* Storage not initialized or initilized for some other codec
352        instance with different settings */
353
354     vorbis_block_clear(vb);
355     vorbis_block_init(v,vb);
356   }
357
358   /* copy the vectors */
359   for(i=0;i<v->pcm_channels;i++)
360     memcpy(vb->pcm[i],v->pcm[i]+beginW,v->block_size[v->W]*sizeof(double));
361   for(i=0;i<v->envelope_channels;i++)
362     memcpy(vb->mult[i],v->multipliers[i]+beginM,v->block_size[v->W]/
363            v->samples_per_envelope_step*sizeof(double));
364
365   vb->frameno=v->frame;
366
367   /* handle eof detection: eof==0 means that we've not yet received EOF
368                            eof>0  marks the last 'real' sample in pcm[]
369                            eof<0  'no more to do'; doesn't get here */
370
371   if(v->eofflag){
372     if(v->centerW>=v->eofflag){
373       v->eofflag=-1;
374       vb->eofflag=1;
375     }
376   }
377
378   /* advance storage vectors and clean up */
379   {
380     int new_centerNext=v->block_size[1]/2;
381     int movementW=centerNext-new_centerNext;
382     int movementM=movementW/v->samples_per_envelope_step;
383
384     /* the multipliers and pcm stay synced up because the blocksizes
385        must be multiples of samples_per_envelope_step (minimum
386        multiple is 2) */
387
388     for(i=0;i<v->pcm_channels;i++)
389       memmove(v->pcm[i],v->pcm[i]+movementW,
390               (v->pcm_current-movementW)*sizeof(double));
391     
392     for(i=0;i<v->envelope_channels;i++){
393       memmove(v->multipliers[i],v->multipliers[i]+movementM,
394               (v->envelope_current-movementM)*sizeof(double));
395     }
396
397     v->pcm_current-=movementW;
398     v->envelope_current-=movementM;
399
400     v->lW=v->W;
401     v->W=v->nW;
402     v->centerW=new_centerNext;
403
404     v->frame++;
405     v->samples+=movementW;
406
407     if(v->eofflag)
408       v->eofflag-=movementW;
409   }
410
411   /* done */
412   return(1);
413 }
414
415 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
416   int temp=vi->envelopech;
417   vi->envelopech=0; /* we don't need multiplier buffering in syn */
418   _vds_shared_init(v,vi);
419   vi->envelopech=temp;
420
421   /* Adjust centerW to allow an easier mechanism for determining output */
422   v->pcm_returned=v->centerW;
423   v->centerW-= v->block_size[v->W]/4+v->block_size[v->lW]/4;
424   return(0);
425 }
426
427 /* Unike in analysis, the window is only partially applied.  Envelope
428    is previously applied (the whole envelope, if any, is shipped in
429    each block) */
430
431 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
432
433   /* Shift out any PCM that we returned previously */
434
435   if(v->pcm_returned  && v->centerW>v->block_size[1]/2){
436
437     /* don't shift too much; we need to have a minimum PCM buffer of
438        1/2 long block */
439
440     int shift=v->centerW-v->block_size[1]/2;
441     shift=(v->pcm_returned<shift?v->pcm_returned:shift);
442
443     v->pcm_current-=shift;
444     v->centerW-=shift;
445     v->pcm_returned-=shift;
446     
447     if(shift){
448       int i;
449       for(i=0;i<v->pcm_channels;i++)
450         memmove(v->pcm[i],v->pcm[i]+shift,
451                 v->pcm_current*sizeof(double));
452     }
453   }
454
455   {
456     int sizeW=v->block_size[vb->W];
457     int centerW=v->centerW+v->block_size[vb->lW]/4+sizeW/4;
458     int beginW=centerW-sizeW/2;
459     int endW=beginW+sizeW;
460     int beginSl;
461     int endSl;
462     int i,j;
463     double *window;
464
465     /* Do we have enough PCM storage for the block? */
466     if(endW>v->pcm_storage){
467       /* expand the PCM storage */
468
469       v->pcm_storage=endW+v->block_size[1];
470    
471       for(i=0;i<v->pcm_channels;i++)
472         v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double)); 
473     }
474
475     /* Overlap/add */
476     switch(vb->W){
477     case 0:
478       beginSl=0;
479       endSl=v->block_size[0]/2;
480       break;
481     case 1:
482       beginSl=v->block_size[1]/4-v->block_size[vb->lW]/4;
483       endSl=beginSl+v->block_size[vb->lW]/2;
484       break;
485     }
486
487     window=v->window[vb->W][0][vb->lW]+v->block_size[vb->W]/2;
488
489     for(j=0;j<v->pcm_channels;j++){
490       double *pcm=v->pcm[j]+beginW;
491
492       /* the add section */
493       for(i=beginSl;i<endSl;i++)
494         pcm[i]=pcm[i]*window[i]+vb->pcm[j][i];
495       /* the remaining section */
496       for(;i<sizeW;i++)
497         pcm[i]=vb->pcm[j][i];
498     }
499
500     /* Update, cleanup */
501
502     v->centerW=centerW;
503     v->pcm_current=endW;
504
505     if(vb->eofflag)v->eofflag=1;
506   }
507   return(0);
508 }
509
510 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
511   if(v->pcm_returned<v->centerW){
512     int i;
513     for(i=0;i<v->pcm_channels;i++)
514       v->pcmret[i]=v->pcm[i]+v->pcm_returned;
515     *pcm=v->pcmret;
516     return(v->centerW-v->pcm_returned);
517   }
518   return(0);
519 }
520
521 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
522   if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
523   v->pcm_returned+=bytes;
524   return(0);
525 }
526
527 #ifdef _V_SELFTEST
528 #include <stdio.h>
529 #include <math.h>
530
531 /* basic test of PCM blocking:
532
533    construct a PCM vector and block it using preset sizing in our fake
534    delta/multiplier generation.  Immediately hand the block over to
535    'synthesis' and rebuild it. */
536
537 int main(){
538   int blocksize=1024;
539   int fini=100*1024;
540   vorbis_dsp_state encode,decode;
541   vorbis_info vi;
542   vorbis_block vb;
543   long counterin=0;
544   long countermid=0;
545   long counterout=0;
546   int done=0;
547   char *temp[]={ "Test" ,"the Test band", "test records",NULL };
548   int frame=0;
549
550   MDCT_lookup *ml[2];
551
552   vi.channels=2;
553   vi.rate=44100;
554   vi.version=0;
555   vi.mode=0;
556   vi.user_comments=temp;
557   vi.vendor="Xiphophorus";
558
559   vorbis_analysis_init(&encode,&vi);
560   vorbis_synthesis_init(&decode,&vi);
561
562   memset(&vb,0,sizeof(vorbis_block));
563   vorbis_block_init(&encode,&vb);
564
565   ml[0]=MDCT_init(encode.block_size[0]);
566   ml[1]=MDCT_init(encode.block_size[1]);
567
568   /* Submit 100K samples of data reading out blocks... */
569   
570   while(!done){
571     int i;
572     double **buf=vorbis_analysis_buffer(&encode,blocksize);
573     for(i=0;i<blocksize;i++){
574       buf[0][i]=sin((counterin+i)%500/500.*M_PI*2)+2;
575       buf[1][i]=-1;
576
577       if((counterin+i)%15000>13000)buf[0][i]+=10;
578     }
579
580     i=(counterin+blocksize>fini?fini-counterin:blocksize);
581     vorbis_analysis_wrote(&encode,i);
582     counterin+=i;
583
584     while(vorbis_analysis_blockout(&encode,&vb)){
585       double **pcm;
586       int avail;
587
588       /* temp fixup */
589
590       double *window=encode.window[vb.W][vb.lW][vb.nW];
591
592       /* apply envelope */
593       _ve_envelope_sparsify(&vb);
594       _ve_envelope_apply(&vb,0);
595
596       for(i=0;i<vb.pcm_channels;i++)
597         MDCT(vb.pcm[i],vb.pcm[i],ml[vb.W],window);
598
599       for(i=0;i<vb.pcm_channels;i++)
600         iMDCT(vb.pcm[i],vb.pcm[i],ml[vb.W],window);
601
602
603       {
604         FILE *out;
605         char path[80];
606         int i;
607
608         int avail=encode.block_size[vb.W];
609         int beginW=countermid-avail/2;
610         
611         sprintf(path,"ana%d",vb.frameno);
612         out=fopen(path,"w");
613
614         for(i=0;i<avail;i++)
615           fprintf(out,"%d %g\n",i+beginW,vb.pcm[0][i]);
616         fprintf(out,"\n");
617         for(i=0;i<avail;i++)
618           fprintf(out,"%d %g\n",i+beginW,window[i]);
619
620         fclose(out);
621         countermid+=encode.block_size[vb.W]/4+encode.block_size[vb.nW]/4;
622       }
623
624
625       _ve_envelope_apply(&vb,1);
626       vorbis_synthesis_blockin(&decode,&vb);
627       
628
629       while((avail=vorbis_synthesis_pcmout(&decode,&pcm))){
630         FILE *out;
631         char path[80];
632         int i;
633         
634         sprintf(path,"syn%d",frame);
635         out=fopen(path,"w");
636
637         for(i=0;i<avail;i++)
638           fprintf(out,"%ld %g\n",i+counterout,pcm[0][i]);
639         fprintf(out,"\n");
640         for(i=0;i<avail;i++)
641           fprintf(out,"%ld %g\n",i+counterout,pcm[1][i]);
642
643         fclose(out);
644
645         vorbis_synthesis_read(&decode,avail);
646
647         counterout+=avail;
648         frame++;
649       }
650       
651
652       if(vb.eofflag){
653         done=1;
654         break;
655       }
656     }
657   }
658   return 0;
659 }
660
661 #endif