Update encoder and decoder examples. One inch away from everything
[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-2000             *
9  * by 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  last mod: $Id: block.c,v 1.24 2000/01/28 09:05:06 xiphmont Exp $
16
17  Handle windowing, overlap-add, etc of the PCM vectors.  This is made
18  more amusing by Vorbis' current two allowed block sizes.
19  
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.
23
24  ********************************************************************/
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include "vorbis/codec.h"
30
31 #include "window.h"
32 #include "envelope.h"
33 #include "mdct.h"
34 #include "lpc.h"
35 #include "bitwise.h"
36 #include "registry.h"
37 #include "bookinternal.h"
38
39 static int ilog2(unsigned int v){
40   int ret=0;
41   while(v>1){
42     ret++;
43     v>>=1;
44   }
45   return(ret);
46 }
47
48 /* pcm accumulator examples (not exhaustive):
49
50  <-------------- lW ---------------->
51                    <--------------- W ---------------->
52 :            .....|.....       _______________         |
53 :        .'''     |     '''_---      |       |\        |
54 :.....'''         |_____--- '''......|       | \_______|
55 :.................|__________________|_______|__|______|
56                   |<------ Sl ------>|      > Sr <     |endW
57                   |beginSl           |endSl  |  |endSr   
58                   |beginW            |endlW  |beginSr
59
60
61                       |< lW >|       
62                    <--------------- W ---------------->
63                   |   |  ..  ______________            |
64                   |   | '  `/        |     ---_        |
65                   |___.'___/`.       |         ---_____| 
66                   |_______|__|_______|_________________|
67                   |      >|Sl|<      |<------ Sr ----->|endW
68                   |       |  |endSl  |beginSr          |endSr
69                   |beginW |  |endlW                     
70                   mult[0] |beginSl                     mult[n]
71
72  <-------------- lW ----------------->
73                           |<--W-->|                               
74 :            ..............  ___  |   |                    
75 :        .'''             |`/   \ |   |                       
76 :.....'''                 |/`....\|...|                    
77 :.........................|___|___|___|                  
78                           |Sl |Sr |endW    
79                           |   |   |endSr
80                           |   |beginSr
81                           |   |endSl
82                           |beginSl
83                           |beginW
84 */
85
86 /* block abstraction setup *********************************************/
87
88 #ifndef WORD_ALIGN
89 #define WORD_ALIGN 8
90 #endif
91
92 int vorbis_block_init(vorbis_dsp_state *v, vorbis_block *vb){
93   memset(vb,0,sizeof(vorbis_block));
94   vb->vd=v;
95   vb->localalloc=0;
96   vb->localstore=NULL;
97   if(v->analysisp)
98     _oggpack_writeinit(&vb->opb);
99
100   return(0);
101 }
102
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 */
107     if(vb->localstore){
108       struct alloc_chain *link=malloc(sizeof(struct alloc_chain));
109       vb->totaluse+=vb->localtop;
110       link->next=vb->reap;
111       link->ptr=vb->localstore;
112       vb->reap=link;
113     }
114     /* highly conservative */
115     vb->localalloc=bytes;
116     vb->localstore=malloc(vb->localalloc);
117     vb->localtop=0;
118   }
119   return(vb->localstore+vb->localtop);
120 }
121
122 /* reap the chain, pull the ripcord */
123 void _vorbis_block_ripcord(vorbis_block *vb){
124   /* reap the chain */
125   struct alloc_chain *reap=vb->reap;
126   while(reap){
127     struct alloc_chain *next=reap->next;
128     free(reap->ptr);
129     memset(reap,0,sizeof(struct alloc_chain));
130     free(reap);
131     reap=next;
132   }
133   /* consolidate storage */
134   if(vb->totaluse){
135     vb->localstore=realloc(vb->localstore,vb->totaluse+vb->localalloc);
136     vb->localalloc+=vb->totaluse;
137     vb->totaluse=0;
138   }
139
140   /* pull the ripcord */
141   vb->localtop=0;
142   vb->reap=NULL;
143 }
144
145 int vorbis_block_clear(vorbis_block *vb){
146   if(vb->vd)
147     if(vb->vd->analysisp)
148       _oggpack_writeclear(&vb->opb);
149   _vorbis_block_ripcord(vb);
150   if(vb->localstore)free(vb->localstore);
151
152   memset(vb,0,sizeof(vorbis_block));
153   return(0);
154 }
155
156 /* Analysis side code, but directly related to blocking.  Thus it's
157    here and not in analysis.c (which is for analysis transforms only).
158    The init is here because some of it is shared */
159
160 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi){
161   int i;
162   memset(v,0,sizeof(vorbis_dsp_state));
163
164   v->vi=vi;
165   v->modebits=ilog2(vi->modes);
166
167   v->transform[0]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
168   v->transform[1]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
169
170   /* MDCT is tranform 0 */
171
172   v->transform[0][0]=calloc(1,sizeof(mdct_lookup));
173   v->transform[1][0]=calloc(1,sizeof(mdct_lookup));
174   mdct_init(v->transform[0][0],vi->blocksizes[0]);
175   mdct_init(v->transform[1][0],vi->blocksizes[1]);
176
177   v->window[0][0][0]=calloc(VI_WINDOWB,sizeof(double *));
178   v->window[0][0][1]=v->window[0][0][0];
179   v->window[0][1][0]=v->window[0][0][0];
180   v->window[0][1][1]=v->window[0][0][0];
181   v->window[1][0][0]=calloc(VI_WINDOWB,sizeof(double *));
182   v->window[1][0][1]=calloc(VI_WINDOWB,sizeof(double *));
183   v->window[1][1][0]=calloc(VI_WINDOWB,sizeof(double *));
184   v->window[1][1][1]=calloc(VI_WINDOWB,sizeof(double *));
185
186   for(i=0;i<VI_WINDOWB;i++){
187     v->window[0][0][0][i]=
188       _vorbis_window(i,vi->blocksizes[0],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
189     v->window[1][0][0][i]=
190       _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[0]/2);
191     v->window[1][0][1][i]=
192       _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[0]/2,vi->blocksizes[1]/2);
193     v->window[1][1][0][i]=
194       _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[0]/2);
195     v->window[1][1][1][i]=
196       _vorbis_window(i,vi->blocksizes[1],vi->blocksizes[1]/2,vi->blocksizes[1]/2);
197   }
198
199   /* initialize all the mapping/backend lookups */
200   v->mode=calloc(vi->modes,sizeof(vorbis_look_mapping *));
201   for(i=0;i<vi->modes;i++){
202     int maptype=vi->mode_param[i]->mapping;
203     v->mode[i]=_mapping_P[maptype]->look(vi,vi->mode_param[i],
204                                          vi->map_param[maptype]);
205   }
206
207   /* initialize the storage vectors to a decent size greater than the
208      minimum */
209   
210   v->pcm_storage=8192; /* we'll assume later that we have
211                           a minimum of twice the blocksize of
212                           accumulated samples in analysis */
213   v->pcm=malloc(vi->channels*sizeof(double *));
214   v->pcmret=malloc(vi->channels*sizeof(double *));
215   {
216     int i;
217     for(i=0;i<vi->channels;i++)
218       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
219   }
220
221   /* all 1 (large block) or 0 (small block) */
222   /* explicitly set for the sake of clarity */
223   v->lW=0; /* previous window size */
224   v->W=0;  /* current window size */
225
226   /* all vector indexes; multiples of samples_per_envelope_step */
227   v->centerW=vi->blocksizes[1]/2;
228
229   v->pcm_current=v->centerW;
230   return(0);
231 }
232
233 /* arbitrary settings and spec-mandated numbers get filled in here */
234 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
235   int i;
236   _vds_shared_init(v,vi);
237
238   /* finish the codebooks */
239   v->fullbooks=calloc(vi->books,sizeof(codebook));
240   for(i=0;i<vi->books;i++)
241     vorbis_book_init_encode(v->fullbooks+i,vi->book_param[i]);
242
243   /* Initialize the envelope multiplier storage */
244
245   v->envelope_storage=v->pcm_storage/vi->envelopesa;
246   v->multipliers=calloc(v->envelope_storage,sizeof(double));
247   _ve_envelope_init(&v->ve,vi->envelopesa);
248
249   /* the coder init is different for read/write */
250   v->analysisp=1;
251
252   v->envelope_current=v->centerW/vi->envelopesa;
253   return(0);
254 }
255
256 void vorbis_dsp_clear(vorbis_dsp_state *v){
257   int i,j,k;
258   if(v){
259     vorbis_info *vi=v->vi;
260
261     for(i=0;i<VI_WINDOWB;i++){
262       if(v->window[0][0][0][i])free(v->window[0][0][0][i]);
263       for(j=0;j<2;j++)
264         for(k=0;k<2;k++)
265           if(v->window[1][j][k][i])free(v->window[1][j][k][i]);
266     }
267     if(v->pcm){
268       for(i=0;i<vi->channels;i++)
269         if(v->pcm[i])free(v->pcm[i]);
270       free(v->pcm);
271       if(v->pcmret)free(v->pcmret);
272     }
273     if(v->multipliers)free(v->multipliers);
274
275     _ve_envelope_clear(&v->ve);
276     mdct_clear(v->transform[0][0]);
277     mdct_clear(v->transform[1][0]);
278     free(v->transform[0][0]);
279     free(v->transform[1][0]);
280
281     free(v->transform[0]);
282     free(v->transform[1]);
283
284     /* free mode lookups */
285     for(i=0;i<vi->modes;i++){
286       int maptype=vi->mode_param[i]->mapping;
287       _mapping_P[maptype]->free_look(v->mode[i]);
288     }
289     if(v->mode)free(v->mode);
290     
291     /* free codebooks */
292     for(i=0;i<vi->books;i++)
293       vorbis_book_clear(v->fullbooks+i);
294     if(v->fullbooks)free(v->fullbooks);
295
296     /* free header, header1, header2 */
297     if(v->header)free(v->header);
298     if(v->header1)free(v->header1);
299     if(v->header2)free(v->header2);
300
301     memset(v,0,sizeof(vorbis_dsp_state));
302   }
303 }
304
305 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
306   int i;
307   vorbis_info *vi=v->vi;
308
309   /* free header, header1, header2 */
310   if(v->header)free(v->header);v->header=NULL;
311   if(v->header1)free(v->header1);v->header1=NULL;
312   if(v->header2)free(v->header2);v->header2=NULL;
313
314   /* Do we have enough storage space for the requested buffer? If not,
315      expand the PCM (and envelope) storage */
316     
317   if(v->pcm_current+vals>=v->pcm_storage){
318     v->pcm_storage=v->pcm_current+vals*2;
319     v->envelope_storage=v->pcm_storage/v->vi->envelopesa;
320    
321     for(i=0;i<vi->channels;i++){
322       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
323     }
324     v->multipliers=realloc(v->multipliers,v->envelope_storage*sizeof(double));
325   }
326
327   for(i=0;i<vi->channels;i++)
328     v->pcmret[i]=v->pcm[i]+v->pcm_current;
329     
330   return(v->pcmret);
331 }
332
333 /* call with val<=0 to set eof */
334
335 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
336   vorbis_info *vi=v->vi;
337   if(vals<=0){
338     /* We're encoding the end of the stream.  Just make sure we have
339        [at least] a full block of zeroes at the end. */
340
341     int i;
342     vorbis_analysis_buffer(v,v->vi->blocksizes[1]*2);
343     v->eofflag=v->pcm_current;
344     v->pcm_current+=v->vi->blocksizes[1]*2;
345     for(i=0;i<vi->channels;i++)
346       memset(v->pcm[i]+v->eofflag,0,
347              (v->pcm_current-v->eofflag)*sizeof(double));
348   }else{
349     
350     if(v->pcm_current+vals>v->pcm_storage)
351       return(-1);
352
353     v->pcm_current+=vals;
354   }
355   return(0);
356 }
357
358 /* do the deltas, envelope shaping, pre-echo and determine the size of
359    the next block on which to continue analysis */
360 int vorbis_analysis_blockout(vorbis_dsp_state *v,vorbis_block *vb){
361   int i;
362   vorbis_info *vi=v->vi;
363   long beginW=v->centerW-vi->blocksizes[v->W]/2,centerNext;
364
365   /* check to see if we're done... */
366   if(v->eofflag==-1)return(0);
367
368   /* if we have any unfilled envelope blocks for which we have PCM
369      data, fill them up in before proceeding. */
370
371   if(v->pcm_current/vi->envelopesa>v->envelope_current){
372     /* This generates the multipliers, but does not sparsify the vector.
373        That's done by block before coding */
374     _ve_envelope_deltas(v);
375   }
376
377   /* By our invariant, we have lW, W and centerW set.  Search for
378      the next boundary so we can determine nW (the next window size)
379      which lets us compute the shape of the current block's window */
380   
381   if(vi->blocksizes[0]<vi->blocksizes[1]){
382     
383     if(v->W)
384       /* this is a long window; we start the search forward of centerW
385          because that's the fastest we could react anyway */
386       i=v->centerW+vi->blocksizes[1]/4-vi->blocksizes[0]/4;
387     else
388       /* short window.  Search from centerW */
389       i=v->centerW;
390     i/=vi->envelopesa;
391     
392     for(;i<v->envelope_current-1;i++){
393       /* Compare last with current; do we have an abrupt energy change? */
394       
395       if(v->multipliers[i-1]*vi->preecho_thresh<  
396          v->multipliers[i])break;
397       
398       /* because the overlapping nature of the delta finding
399          'smears' the energy cliffs, also compare completely
400          unoverlapped areas just in case the plosive happened in an
401          unlucky place */
402       
403       if(v->multipliers[i-1]*vi->preecho_thresh<  
404          v->multipliers[i+1])break;
405         
406     }
407     
408     if(i<v->envelope_current-1){
409       /* Ooo, we hit a multiplier. Is it beyond the boundary to make the
410          upcoming block large ? */
411       long largebound;
412       if(v->W)
413         /* min boundary; nW large, next small */
414         largebound=v->centerW+vi->blocksizes[1]*3/4+vi->blocksizes[0]/4;
415       else
416         /* min boundary; nW large, next small */
417         largebound=v->centerW+vi->blocksizes[0]/2+vi->blocksizes[1]/2;
418       largebound/=vi->envelopesa;
419       
420       if(i>=largebound)
421         v->nW=1;
422       else
423         v->nW=0;
424       
425     }else{
426       /* Assume maximum; if the block is incomplete given current
427          buffered data, this will be detected below */
428       v->nW=1;
429     }
430   }else
431     v->nW=0;
432
433   /* Do we actually have enough data *now* for the next block? The
434      reason to check is that if we had no multipliers, that could
435      simply been due to running out of data.  In that case, we don't
436      know the size of the next block for sure and we need that now to
437      figure out the window shape of this block */
438   
439   centerNext=v->centerW+vi->blocksizes[v->W]/4+vi->blocksizes[v->nW]/4;
440
441   {
442     /* center of next block + next block maximum right side.  Note
443        that the next block needs an additional vi->envelopesa samples 
444        to actually be written (for the last multiplier), but we didn't
445        need that to determine its size */
446
447     long blockbound=centerNext+vi->blocksizes[v->nW]/2;
448     if(v->pcm_current<blockbound)return(0); /* not enough data yet */    
449   }
450   
451   /* fill in the block.  Note that for a short window, lW and nW are *short*
452      regardless of actual settings in the stream */
453
454   _vorbis_block_ripcord(vb);
455   if(v->W){
456     vb->lW=v->lW;
457     vb->W=v->W;
458     vb->nW=v->nW;
459   }else{
460     vb->lW=0;
461     vb->W=v->W;
462     vb->nW=0;
463   }
464   vb->vd=v;
465   vb->sequence=v->sequence;
466   vb->frameno=v->frameno;
467   vb->pcmend=vi->blocksizes[v->W];
468   
469   /* copy the vectors; this uses the local storage in vb */
470   {
471     vb->pcm=_vorbis_block_alloc(vb,sizeof(double *)*vi->channels);
472     for(i=0;i<vi->channels;i++){
473       vb->pcm[i]=_vorbis_block_alloc(vb,vb->pcmend*sizeof(double));
474       memcpy(vb->pcm[i],v->pcm[i]+beginW,vi->blocksizes[v->W]*sizeof(double));
475     }
476   }
477   
478   /* handle eof detection: eof==0 means that we've not yet received EOF
479                            eof>0  marks the last 'real' sample in pcm[]
480                            eof<0  'no more to do'; doesn't get here */
481
482   if(v->eofflag){
483     if(v->centerW>=v->eofflag){
484       v->eofflag=-1;
485       vb->eofflag=1;
486     }
487   }
488
489   /* advance storage vectors and clean up */
490   {
491     int new_centerNext=vi->blocksizes[1]/2;
492     int movementW=centerNext-new_centerNext;
493     int movementM=movementW/vi->envelopesa;
494
495     /* the multipliers and pcm stay synced up because the blocksize
496        must be multiples of samples_per_envelope_step (minimum
497        multiple is 2) */
498
499     v->pcm_current-=movementW;
500     v->envelope_current-=movementM;
501
502     for(i=0;i<vi->channels;i++)
503       memmove(v->pcm[i],v->pcm[i]+movementW,
504               v->pcm_current*sizeof(double));
505     
506     memmove(v->multipliers,v->multipliers+movementM,
507             v->envelope_current*sizeof(double));
508
509     v->lW=v->W;
510     v->W=v->nW;
511     v->centerW=new_centerNext;
512
513     v->sequence++;
514     v->frameno+=movementW;
515
516     if(v->eofflag)
517       v->eofflag-=movementW;
518   }
519
520   /* done */
521   return(1);
522 }
523
524 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
525   int i;
526   _vds_shared_init(v,vi);
527
528   /* finish the codebooks */
529   v->fullbooks=calloc(vi->books,sizeof(codebook));
530   for(i=0;i<vi->books;i++)
531     vorbis_book_init_decode(v->fullbooks+i,vi->book_param[i]);
532
533   /* Adjust centerW to allow an easier mechanism for determining output */
534   v->pcm_returned=v->centerW;
535   v->centerW-= vi->blocksizes[v->W]/4+vi->blocksizes[v->lW]/4;
536   return(0);
537 }
538
539 /* Unike in analysis, the window is only partially applied for each
540    block.  The time domain envelope is not yet handled at the point of
541    calling (as it relies on the previous block). */
542
543 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
544   vorbis_info *vi=v->vi;
545
546   /* Shift out any PCM/multipliers that we returned previously */
547   /* centerW is currently the center of the last block added */
548   if(v->pcm_returned  && v->centerW>vi->blocksizes[1]/2){
549
550     /* don't shift too much; we need to have a minimum PCM buffer of
551        1/2 long block */
552
553     int shiftPCM=v->centerW-vi->blocksizes[1]/2;
554     shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
555
556     v->pcm_current-=shiftPCM;
557     v->centerW-=shiftPCM;
558     v->pcm_returned-=shiftPCM;
559     
560     if(shiftPCM){
561       int i;
562       for(i=0;i<vi->channels;i++)
563         memmove(v->pcm[i],v->pcm[i]+shiftPCM,
564                 v->pcm_current*sizeof(double));
565     }
566   }
567
568   v->lW=v->W;
569   v->W=vb->W;
570   v->nW=-1;
571
572   v->glue_bits+=vb->glue_bits;
573   v->time_bits+=vb->time_bits;
574   v->floor_bits+=vb->floor_bits;
575   v->res_bits+=vb->res_bits;
576   v->sequence=vb->sequence;
577
578   {
579     int sizeW=vi->blocksizes[v->W];
580     int centerW=v->centerW+vi->blocksizes[v->lW]/4+sizeW/4;
581     int beginW=centerW-sizeW/2;
582     int endW=beginW+sizeW;
583     int beginSl;
584     int endSl;
585     int i,j;
586
587     /* Do we have enough PCM/mult storage for the block? */
588     if(endW>v->pcm_storage){
589       /* expand the storage */
590       v->pcm_storage=endW+vi->blocksizes[1];
591    
592       for(i=0;i<vi->channels;i++)
593         v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double)); 
594     }
595
596     /* overlap/add PCM */
597
598     switch(v->W){
599     case 0:
600       beginSl=0;
601       endSl=vi->blocksizes[0]/2;
602       break;
603     case 1:
604       beginSl=vi->blocksizes[1]/4-vi->blocksizes[v->lW]/4;
605       endSl=beginSl+vi->blocksizes[v->lW]/2;
606       break;
607     }
608
609     for(j=0;j<vi->channels;j++){
610       double *pcm=v->pcm[j]+beginW;
611       
612       /* the overlap/add section */
613       for(i=beginSl;i<endSl;i++)
614         pcm[i]+=vb->pcm[j][i];
615       /* the remaining section */
616       for(;i<sizeW;i++)
617         pcm[i]=vb->pcm[j][i];
618     }
619
620     /* Update, cleanup */
621
622     v->centerW=centerW;
623     v->pcm_current=endW;
624
625     if(vb->eofflag)v->eofflag=1;
626   }
627   return(0);
628 }
629
630 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
631   vorbis_info *vi=v->vi;
632   if(v->pcm_returned<v->centerW){
633     int i;
634     for(i=0;i<vi->channels;i++)
635       v->pcmret[i]=v->pcm[i]+v->pcm_returned;
636     *pcm=v->pcmret;
637     return(v->centerW-v->pcm_returned);
638   }
639   return(0);
640 }
641
642 int vorbis_synthesis_read(vorbis_dsp_state *v,int bytes){
643   if(bytes && v->pcm_returned+bytes>v->centerW)return(-1);
644   v->pcm_returned+=bytes;
645   return(0);
646 }
647