Incremental update
[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.25 2000/02/06 13:39:38 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   {
120     void *ret=vb->localstore+vb->localtop;
121     vb->localtop+=bytes;
122     return ret;
123   }
124 }
125
126 /* reap the chain, pull the ripcord */
127 void _vorbis_block_ripcord(vorbis_block *vb){
128   /* reap the chain */
129   struct alloc_chain *reap=vb->reap;
130   while(reap){
131     struct alloc_chain *next=reap->next;
132     free(reap->ptr);
133     memset(reap,0,sizeof(struct alloc_chain));
134     free(reap);
135     reap=next;
136   }
137   /* consolidate storage */
138   if(vb->totaluse){
139     vb->localstore=realloc(vb->localstore,vb->totaluse+vb->localalloc);
140     vb->localalloc+=vb->totaluse;
141     vb->totaluse=0;
142   }
143
144   /* pull the ripcord */
145   vb->localtop=0;
146   vb->reap=NULL;
147 }
148
149 int vorbis_block_clear(vorbis_block *vb){
150   if(vb->vd)
151     if(vb->vd->analysisp)
152       _oggpack_writeclear(&vb->opb);
153   _vorbis_block_ripcord(vb);
154   if(vb->localstore)free(vb->localstore);
155
156   memset(vb,0,sizeof(vorbis_block));
157   return(0);
158 }
159
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 */
163
164 static int _vds_shared_init(vorbis_dsp_state *v,vorbis_info *vi){
165   int i;
166   memset(v,0,sizeof(vorbis_dsp_state));
167
168   v->vi=vi;
169   v->modebits=ilog2(vi->modes);
170
171   v->transform[0]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
172   v->transform[1]=calloc(VI_TRANSFORMB,sizeof(vorbis_look_transform *));
173
174   /* MDCT is tranform 0 */
175
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]);
180
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 *));
189
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);
201   }
202
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]);
210   }
211
212   /* initialize the storage vectors to a decent size greater than the
213      minimum */
214   
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 *));
220   {
221     int i;
222     for(i=0;i<vi->channels;i++)
223       v->pcm[i]=calloc(v->pcm_storage,sizeof(double));
224   }
225
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 */
230
231   /* all vector indexes; multiples of samples_per_envelope_step */
232   v->centerW=vi->blocksizes[1]/2;
233
234   v->pcm_current=v->centerW;
235   return(0);
236 }
237
238 /* arbitrary settings and spec-mandated numbers get filled in here */
239 int vorbis_analysis_init(vorbis_dsp_state *v,vorbis_info *vi){
240   int i;
241   _vds_shared_init(v,vi);
242
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]);
247
248   /* Initialize the envelope multiplier storage */
249
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);
253
254   /* the coder init is different for read/write */
255   v->analysisp=1;
256
257   v->envelope_current=v->centerW/vi->envelopesa;
258   return(0);
259 }
260
261 void vorbis_dsp_clear(vorbis_dsp_state *v){
262   int i,j,k;
263   if(v){
264     vorbis_info *vi=v->vi;
265
266     for(i=0;i<VI_WINDOWB;i++){
267       if(v->window[0][0][0][i])free(v->window[0][0][0][i]);
268       for(j=0;j<2;j++)
269         for(k=0;k<2;k++)
270           if(v->window[1][j][k][i])free(v->window[1][j][k][i]);
271     }
272     if(v->pcm){
273       for(i=0;i<vi->channels;i++)
274         if(v->pcm[i])free(v->pcm[i]);
275       free(v->pcm);
276       if(v->pcmret)free(v->pcmret);
277     }
278     if(v->multipliers)free(v->multipliers);
279
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]);
285
286     free(v->transform[0]);
287     free(v->transform[1]);
288
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]);
294     }
295     if(v->mode)free(v->mode);
296     
297     /* free codebooks */
298     for(i=0;i<vi->books;i++)
299       vorbis_book_clear(v->fullbooks+i);
300     if(v->fullbooks)free(v->fullbooks);
301
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);
306
307     memset(v,0,sizeof(vorbis_dsp_state));
308   }
309 }
310
311 double **vorbis_analysis_buffer(vorbis_dsp_state *v, int vals){
312   int i;
313   vorbis_info *vi=v->vi;
314
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;
319
320   /* Do we have enough storage space for the requested buffer? If not,
321      expand the PCM (and envelope) storage */
322     
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;
326    
327     for(i=0;i<vi->channels;i++){
328       v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double));
329     }
330     v->multipliers=realloc(v->multipliers,v->envelope_storage*sizeof(double));
331   }
332
333   for(i=0;i<vi->channels;i++)
334     v->pcmret[i]=v->pcm[i]+v->pcm_current;
335     
336   return(v->pcmret);
337 }
338
339 /* call with val<=0 to set eof */
340
341 int vorbis_analysis_wrote(vorbis_dsp_state *v, int vals){
342   vorbis_info *vi=v->vi;
343   if(vals<=0){
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. */
346
347     int i;
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));
354   }else{
355     
356     if(v->pcm_current+vals>v->pcm_storage)
357       return(-1);
358
359     v->pcm_current+=vals;
360   }
361   return(0);
362 }
363
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){
367   int i;
368   vorbis_info *vi=v->vi;
369   long beginW=v->centerW-vi->blocksizes[v->W]/2,centerNext;
370
371   /* check to see if we're done... */
372   if(v->eofflag==-1)return(0);
373
374   /* if we have any unfilled envelope blocks for which we have PCM
375      data, fill them up in before proceeding. */
376
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);
381   }
382
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 */
386   
387   if(vi->blocksizes[0]<vi->blocksizes[1]){
388     
389     if(v->W)
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;
393     else
394       /* short window.  Search from centerW */
395       i=v->centerW;
396     i/=vi->envelopesa;
397     
398     for(;i<v->envelope_current-1;i++){
399       /* Compare last with current; do we have an abrupt energy change? */
400       
401       if(v->multipliers[i-1]*vi->preecho_thresh<  
402          v->multipliers[i])break;
403       
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
407          unlucky place */
408       
409       if(v->multipliers[i-1]*vi->preecho_thresh<  
410          v->multipliers[i+1])break;
411         
412     }
413     
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 ? */
417       long largebound;
418       if(v->W)
419         /* min boundary; nW large, next small */
420         largebound=v->centerW+vi->blocksizes[1]*3/4+vi->blocksizes[0]/4;
421       else
422         /* min boundary; nW large, next small */
423         largebound=v->centerW+vi->blocksizes[0]/2+vi->blocksizes[1]/2;
424       largebound/=vi->envelopesa;
425       
426       if(i>=largebound)
427         v->nW=1;
428       else
429         v->nW=0;
430       
431     }else{
432       /* Assume maximum; if the block is incomplete given current
433          buffered data, this will be detected below */
434       v->nW=1;
435     }
436   }else
437     v->nW=0;
438
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 */
444   
445   centerNext=v->centerW+vi->blocksizes[v->W]/4+vi->blocksizes[v->nW]/4;
446
447   {
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 */
452
453     long blockbound=centerNext+vi->blocksizes[v->nW]/2;
454     if(v->pcm_current<blockbound)return(0); /* not enough data yet */    
455   }
456   
457   /* fill in the block.  Note that for a short window, lW and nW are *short*
458      regardless of actual settings in the stream */
459
460   _vorbis_block_ripcord(vb);
461   if(v->W){
462     vb->lW=v->lW;
463     vb->W=v->W;
464     vb->nW=v->nW;
465   }else{
466     vb->lW=0;
467     vb->W=v->W;
468     vb->nW=0;
469   }
470   vb->vd=v;
471   vb->sequence=v->sequence;
472   vb->frameno=v->frameno;
473   vb->pcmend=vi->blocksizes[v->W];
474   
475   /* copy the vectors; this uses the local storage in vb */
476   {
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));
481     }
482   }
483   
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 */
487
488   if(v->eofflag){
489     if(v->centerW>=v->eofflag){
490       v->eofflag=-1;
491       vb->eofflag=1;
492     }
493   }
494
495   /* advance storage vectors and clean up */
496   {
497     int new_centerNext=vi->blocksizes[1]/2;
498     int movementW=centerNext-new_centerNext;
499     int movementM=movementW/vi->envelopesa;
500
501     /* the multipliers and pcm stay synced up because the blocksize
502        must be multiples of samples_per_envelope_step (minimum
503        multiple is 2) */
504
505     v->pcm_current-=movementW;
506     v->envelope_current-=movementM;
507
508     for(i=0;i<vi->channels;i++)
509       memmove(v->pcm[i],v->pcm[i]+movementW,
510               v->pcm_current*sizeof(double));
511     
512     memmove(v->multipliers,v->multipliers+movementM,
513             v->envelope_current*sizeof(double));
514
515     v->lW=v->W;
516     v->W=v->nW;
517     v->centerW=new_centerNext;
518
519     v->sequence++;
520     v->frameno+=movementW;
521
522     if(v->eofflag)
523       v->eofflag-=movementW;
524   }
525
526   /* done */
527   return(1);
528 }
529
530 int vorbis_synthesis_init(vorbis_dsp_state *v,vorbis_info *vi){
531   int i;
532   _vds_shared_init(v,vi);
533
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]);
538
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;
542   return(0);
543 }
544
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). */
548
549 int vorbis_synthesis_blockin(vorbis_dsp_state *v,vorbis_block *vb){
550   vorbis_info *vi=v->vi;
551
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){
555
556     /* don't shift too much; we need to have a minimum PCM buffer of
557        1/2 long block */
558
559     int shiftPCM=v->centerW-vi->blocksizes[1]/2;
560     shiftPCM=(v->pcm_returned<shiftPCM?v->pcm_returned:shiftPCM);
561
562     v->pcm_current-=shiftPCM;
563     v->centerW-=shiftPCM;
564     v->pcm_returned-=shiftPCM;
565     
566     if(shiftPCM){
567       int i;
568       for(i=0;i<vi->channels;i++)
569         memmove(v->pcm[i],v->pcm[i]+shiftPCM,
570                 v->pcm_current*sizeof(double));
571     }
572   }
573
574   v->lW=v->W;
575   v->W=vb->W;
576   v->nW=-1;
577
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;
583
584   {
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;
589     int beginSl;
590     int endSl;
591     int i,j;
592
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];
597    
598       for(i=0;i<vi->channels;i++)
599         v->pcm[i]=realloc(v->pcm[i],v->pcm_storage*sizeof(double)); 
600     }
601
602     /* overlap/add PCM */
603
604     switch(v->W){
605     case 0:
606       beginSl=0;
607       endSl=vi->blocksizes[0]/2;
608       break;
609     case 1:
610       beginSl=vi->blocksizes[1]/4-vi->blocksizes[v->lW]/4;
611       endSl=beginSl+vi->blocksizes[v->lW]/2;
612       break;
613     }
614
615     for(j=0;j<vi->channels;j++){
616       double *pcm=v->pcm[j]+beginW;
617       
618       /* the overlap/add section */
619       for(i=beginSl;i<endSl;i++)
620         pcm[i]+=vb->pcm[j][i];
621       /* the remaining section */
622       for(;i<sizeW;i++)
623         pcm[i]=vb->pcm[j][i];
624     }
625
626     /* Update, cleanup */
627
628     v->centerW=centerW;
629     v->pcm_current=endW;
630
631     if(vb->eofflag)v->eofflag=1;
632   }
633   return(0);
634 }
635
636 int vorbis_synthesis_pcmout(vorbis_dsp_state *v,double ***pcm){
637   vorbis_info *vi=v->vi;
638   if(v->pcm_returned<v->centerW){
639     int i;
640     for(i=0;i<vi->channels;i++)
641       v->pcmret[i]=v->pcm[i]+v->pcm_returned;
642     *pcm=v->pcmret;
643     return(v->centerW-v->pcm_returned);
644   }
645   return(0);
646 }
647
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;
651   return(0);
652 }
653