]> git.jsancho.org Git - lugaru.git/blob - libvorbis-1.0.1/lib/bitrate.c
Cleaned up some things that don't compile on Mac OS X.
[lugaru.git] / libvorbis-1.0.1 / lib / bitrate.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7  *                                                                  *
8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002             *
9  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13  function: bitrate tracking and management
14  last mod: $Id: bitrate.c,v 1.21 2002/10/11 11:14:41 xiphmont Exp $
15
16  ********************************************************************/
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <math.h>
22 #include <ogg/ogg.h>
23 #include "vorbis/codec.h"
24 #include "codec_internal.h"
25 #include "os.h"
26 #include "misc.h"
27 #include "bitrate.h"
28
29
30 static long BINBYTES(bitrate_manager_state *bm,long pos,long bin){
31   int bins=bm->queue_bins;
32   return(bm->queue_binned[pos*bins+bin]);
33 }
34
35 #define LIMITBYTES(pos,bin) (bm->minmax_binstack[(pos)*bins*2+((bin)+bins)])
36
37 static long LACING_ADJUST(long bytes){
38   int addto=bytes/255+1;
39   return(bytes+addto);
40 }
41
42 static int floater_interpolate(bitrate_manager_state *bm,vorbis_info *vi,
43                                   double desired_rate){
44   int bin=rint(bm->avgfloat);
45   double lobitrate,hibitrate;
46
47
48   lobitrate=(double)(bm->avg_binacc[bin]*8)/bm->avg_sampleacc*vi->rate;
49   while(lobitrate>desired_rate && bin>0){
50     bin--;
51     lobitrate=(double)(bm->avg_binacc[bin]*8)/bm->avg_sampleacc*vi->rate;
52   }
53
54   if(bin+1<bm->queue_bins){
55     hibitrate=(double)(bm->avg_binacc[bin+1]*8)/bm->avg_sampleacc*vi->rate;
56     if(fabs(hibitrate-desired_rate) < fabs(lobitrate-desired_rate))bin++;
57   }
58   return(bin);
59 }
60
61 /* try out a new limit */
62 static long limit_sum(bitrate_manager_state *bm,int limit){
63   int i=bm->minmax_stackptr;
64   long acc=bm->minmax_acctotal;
65   long bins=bm->queue_bins;
66   
67   acc-=LIMITBYTES(i,0);
68   acc+=LIMITBYTES(i,limit);
69
70   while(i-->0){
71     if(bm->minmax_limitstack[i]<=limit)break;
72     acc-=LIMITBYTES(i,bm->minmax_limitstack[i]);
73     acc+=LIMITBYTES(i,limit);
74   }
75   return(acc);
76 }
77
78 /* compute bitrate tracking setup, allocate circular packet size queue */
79 void vorbis_bitrate_init(vorbis_info *vi,bitrate_manager_state *bm){
80   int i;
81   codec_setup_info *ci=vi->codec_setup;
82   bitrate_manager_info *bi=&ci->bi;
83   long maxlatency;
84
85   memset(bm,0,sizeof(*bm));
86   
87   if(bi){
88     
89     bm->avg_sampledesired=bi->queue_avg_time*vi->rate;
90     bm->avg_centerdesired=bi->queue_avg_time*vi->rate*bi->queue_avg_center;
91     bm->minmax_sampledesired=bi->queue_minmax_time*vi->rate;
92     
93     /* first find the max possible needed queue size */
94     maxlatency=max(bm->avg_sampledesired-bm->avg_centerdesired,
95                    bm->minmax_sampledesired)+bm->avg_centerdesired;
96     
97     if(maxlatency>0 &&
98        (bi->queue_avgmin>0 || bi->queue_avgmax>0 || bi->queue_hardmax>0 ||
99         bi->queue_hardmin>0)){
100       long maxpackets=maxlatency/(ci->blocksizes[0]>>1)+3;
101       long bins=PACKETBLOBS;
102       
103       bm->queue_size=maxpackets;
104       bm->queue_bins=bins;
105       bm->queue_binned=_ogg_calloc(maxpackets,bins*sizeof(*bm->queue_binned));
106       bm->queue_actual=_ogg_calloc(maxpackets,sizeof(*bm->queue_actual));
107       
108       if((bi->queue_avgmin>0 || bi->queue_avgmax>0) &&
109          bi->queue_avg_time>0){
110         
111         bm->avg_binacc=_ogg_calloc(bins,sizeof(*bm->avg_binacc));
112         bm->avgfloat=PACKETBLOBS/2;
113         
114       }else{
115         bm->avg_tail= -1;
116       }
117       
118       if((bi->queue_hardmin>0 || bi->queue_hardmax>0) &&
119          bi->queue_minmax_time>0){
120         
121         bm->minmax_binstack=_ogg_calloc((bins*2+1)*bins*2,
122                                         sizeof(*bm->minmax_binstack));
123         bm->minmax_posstack=_ogg_calloc((bins*2+1),
124                                       sizeof(*bm->minmax_posstack));
125         bm->minmax_limitstack=_ogg_calloc((bins*2+1),
126                                           sizeof(*bm->minmax_limitstack));
127       }else{
128         bm->minmax_tail= -1;
129       }
130       
131       /* space for the packet queueing */
132       bm->packetbuffers=_ogg_calloc(maxpackets,sizeof(*bm->packetbuffers));
133       bm->packets=_ogg_calloc(maxpackets,sizeof(*bm->packets));
134       for(i=0;i<maxpackets;i++)
135         oggpack_writeinit(bm->packetbuffers+i);
136       
137     }else{
138       bm->packetbuffers=_ogg_calloc(1,sizeof(*bm->packetbuffers));
139       bm->packets=_ogg_calloc(1,sizeof(*bm->packets));
140       oggpack_writeinit(bm->packetbuffers);
141
142     }      
143   }
144 }
145
146 void vorbis_bitrate_clear(bitrate_manager_state *bm){
147   int i;
148   if(bm){
149     if(bm->queue_binned)_ogg_free(bm->queue_binned);
150     if(bm->queue_actual)_ogg_free(bm->queue_actual);
151     if(bm->avg_binacc)_ogg_free(bm->avg_binacc);
152     if(bm->minmax_binstack)_ogg_free(bm->minmax_binstack);
153     if(bm->minmax_posstack)_ogg_free(bm->minmax_posstack);
154     if(bm->minmax_limitstack)_ogg_free(bm->minmax_limitstack);
155
156     if(bm->packetbuffers){
157       if(bm->queue_size==0){
158         oggpack_writeclear(bm->packetbuffers);
159       }else{
160         for(i=0;i<bm->queue_size;i++)
161           oggpack_writeclear(bm->packetbuffers+i);      
162       }
163       _ogg_free(bm->packetbuffers);
164     }
165     if(bm->packets)_ogg_free(bm->packets);
166     
167     memset(bm,0,sizeof(*bm));
168   }
169 }
170
171 int vorbis_bitrate_managed(vorbis_block *vb){
172   vorbis_dsp_state      *vd=vb->vd;
173   private_state         *b=vd->backend_state; 
174   bitrate_manager_state *bm=&b->bms;
175
176   if(bm->queue_binned)return(1);
177   return(0);
178 }
179
180 /* finish taking in the block we just processed */
181 int vorbis_bitrate_addblock(vorbis_block *vb){
182   int i; 
183   vorbis_block_internal *vbi=vb->internal;
184   vorbis_dsp_state      *vd=vb->vd;
185   private_state         *b=vd->backend_state; 
186   bitrate_manager_state *bm=&b->bms;
187   vorbis_info           *vi=vd->vi;
188   codec_setup_info      *ci=vi->codec_setup;
189   bitrate_manager_info  *bi=&ci->bi;
190   int                    eofflag=vb->eofflag;
191   int                    head=bm->queue_head;
192   int                    next_head=head+1;
193   int                    bins=bm->queue_bins;
194   int                    minmax_head,new_minmax_head;
195   
196   ogg_uint32_t           *head_ptr;
197   oggpack_buffer          temp;
198
199   if(!bm->queue_binned){
200     oggpack_buffer temp;
201     /* not a bitrate managed stream, but for API simplicity, we'll
202        buffer one packet to keep the code path clean */
203     
204     if(bm->queue_head)return(-1); /* one has been submitted without
205                                      being claimed */
206     bm->queue_head++;
207
208     bm->packets[0].packet=oggpack_get_buffer(&vb->opb);
209     bm->packets[0].bytes=oggpack_bytes(&vb->opb);
210     bm->packets[0].b_o_s=0;
211     bm->packets[0].e_o_s=vb->eofflag;
212     bm->packets[0].granulepos=vb->granulepos;
213     bm->packets[0].packetno=vb->sequence; /* for sake of completeness */
214
215     memcpy(&temp,bm->packetbuffers,sizeof(vb->opb));
216     memcpy(bm->packetbuffers,&vb->opb,sizeof(vb->opb));
217     memcpy(&vb->opb,&temp,sizeof(vb->opb));
218
219     return(0);
220   }
221
222   /* add encoded packet to head */
223   if(next_head>=bm->queue_size)next_head=0;
224   head_ptr=bm->queue_binned+bins*head;
225
226   /* is there room to add a block? In proper use of the API, this will
227      never come up... but guard it anyway */
228   if(next_head==bm->avg_tail || next_head==bm->minmax_tail)return(-1);
229
230   /* add the block to the toplevel queue */
231   bm->queue_head=next_head;
232   bm->queue_actual[head]=(vb->W?0x80000000UL:0);
233
234   /* buffer packet fields */
235   bm->packets[head].packet=oggpack_get_buffer(&vb->opb);
236   bm->packets[head].bytes=oggpack_bytes(&vb->opb);
237   bm->packets[head].b_o_s=0;
238   bm->packets[head].e_o_s=vb->eofflag;
239   bm->packets[head].granulepos=vb->granulepos;
240   bm->packets[head].packetno=vb->sequence; /* for sake of completeness */
241
242   /* swap packet buffers */
243   memcpy(&temp,bm->packetbuffers+head,sizeof(vb->opb));
244   memcpy(bm->packetbuffers+head,&vb->opb,sizeof(vb->opb));
245   memcpy(&vb->opb,&temp,sizeof(vb->opb));
246
247   /* save markers */
248   head_ptr[0]=vbi->packetblob_markers[0];
249   for(i=1;i<PACKETBLOBS;i++){
250     head_ptr[i]=vbi->packetblob_markers[i]-vbi->packetblob_markers[i-1];
251   }
252
253   if(bm->avg_binacc)
254     new_minmax_head=minmax_head=bm->avg_center;
255   else
256     new_minmax_head=minmax_head=head;
257
258   /* the average tracking queue is updated first; its results (if it's
259      in use) are taken into account by the min/max limiter (if min/max
260      is in use) */
261   if(bm->avg_binacc){
262     unsigned long desired_center=bm->avg_centerdesired;
263     if(eofflag)desired_center=0;
264
265     /* update the avg head */
266     for(i=0;i<bins;i++)
267       bm->avg_binacc[i]+=LACING_ADJUST(head_ptr[i]);
268     bm->avg_sampleacc+=ci->blocksizes[vb->W]>>1;
269     bm->avg_centeracc+=ci->blocksizes[vb->W]>>1;
270
271     if(bm->avg_sampleacc>bm->avg_sampledesired || eofflag){
272
273       /* update the avg center */
274       if(bm->avg_centeracc>desired_center){
275         /* choose the new average floater */
276         int samples=ci->blocksizes[vb->W]>>1;
277         double upper=floater_interpolate(bm,vi,bi->queue_avgmax);
278         double lower=floater_interpolate(bm,vi,bi->queue_avgmin);
279         double new=PACKETBLOBS/2.,slew;
280         int bin;
281         
282         if(upper<new)new=upper;
283         if(lower>new)new=lower;
284         
285         slew=(new-bm->avgfloat)/samples*vi->rate;
286         
287         if(slew<bi->avgfloat_downslew_max)
288           new=bm->avgfloat+bi->avgfloat_downslew_max/vi->rate*samples;
289         if(slew>bi->avgfloat_upslew_max)
290           new=bm->avgfloat+bi->avgfloat_upslew_max/vi->rate*samples;
291         
292         bm->avgfloat=new;
293         /* apply the average floater to new blocks */
294         bin=rint(bm->avgfloat);
295
296         /*fprintf(stderr,"%d ",bin);*/
297         
298         while(bm->avg_centeracc>desired_center){
299           samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
300                                 0x80000000UL?1:0]>>1;
301           
302           bm->queue_actual[bm->avg_center]|=bin;
303           
304           bm->avg_centeracc-=samples;
305           bm->avg_center++;
306           if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
307         }
308         new_minmax_head=bm->avg_center;
309         
310       }
311       
312       /* update the avg tail if needed */
313       while(bm->avg_sampleacc>bm->avg_sampledesired){
314         int samples=
315           ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
316         for(i=0;i<bm->queue_bins;i++)
317           bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
318         bm->avg_sampleacc-=samples;
319         bm->avg_tail++;
320         if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
321       }
322       
323       
324     }
325   }else{
326     /* if we're not using an average tracker, the 'float' is nailed to
327        the avgfloat_initial value.  It needs to be set for the min/max
328        to deal properly */
329     long bin=PACKETBLOBS/2;
330     bm->queue_actual[head]|=bin;
331     new_minmax_head=next_head;
332   }     
333   
334   /* update the min/max queues and enforce limits */
335   if(bm->minmax_binstack){
336     unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
337     
338     /* add to stack recent */
339     while(minmax_head!=new_minmax_head){
340       unsigned int i;
341       int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
342                                 0x80000000UL?1:0]>>1;
343       int actual=bm->queue_actual[minmax_head]&0x7fffffffUL;
344
345       for(i=0;i<(unsigned int)bins;i++){
346         bm->minmax_binstack[bm->minmax_stackptr*bins*2+bins+i]+=
347           LACING_ADJUST(BINBYTES(bm,minmax_head,
348                                 actual>i?actual:i));
349         
350         bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
351           LACING_ADJUST(BINBYTES(bm,minmax_head,
352                                 actual<i?actual:i));
353       }
354       
355       bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
356                                                                past
357                                                                like
358                                                                typical */
359       bm->minmax_limitstack[bm->minmax_stackptr]=0;
360       bm->minmax_sampleacc+=samples;
361       bm->minmax_acctotal+=
362         LACING_ADJUST(BINBYTES(bm,minmax_head,actual));
363       
364       minmax_head++;
365       if(minmax_head>=bm->queue_size)minmax_head=0;
366
367
368     }
369     
370     /* check limits, enforce changes */
371     if(bm->minmax_sampleacc>sampledesired){
372       double bitrate=(double)(bm->minmax_acctotal*8)/
373         bm->minmax_sampleacc*vi->rate;
374       int limit=0;
375       
376       if((bi->queue_hardmax>0 && bitrate>bi->queue_hardmax) || 
377          (bi->queue_hardmin>0 && bitrate<bi->queue_hardmin)){
378         int newstack;
379         int stackctr;
380         long bitsum=bm->minmax_acctotal*8;
381
382         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
383
384         /* we're off rate.  Iteratively try out new hard floater
385            limits until we find one that brings us inside.  Here's
386            where we see the whole point of the limit stacks.  */
387         if(bi->queue_hardmax>0 && bitrate>bi->queue_hardmax){
388           for(limit=-1;limit>-bins+1;limit--){
389             long bitsum=limit_sum(bm,limit)*8;
390             bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
391             if(bitrate<=bi->queue_hardmax)break;
392           }
393         }else if(bitrate<bi->queue_hardmin){
394           for(limit=1;limit<bins-1;limit++){
395             long bitsum=limit_sum(bm,limit)*8;
396             bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
397             if(bitrate>=bi->queue_hardmin)break;
398           }
399           if(bitrate>bi->queue_hardmax)limit--;
400         }
401
402         /* trace the limit backward, stop when we see a lower limit */
403         newstack=bm->minmax_stackptr-1;
404         while(newstack>=0){
405           if(bm->minmax_limitstack[newstack]<limit)break;
406           newstack--;
407         }
408         
409         /* update bit counter with new limit and replace any stack
410            limits that have been replaced by our new lower limit */
411         stackctr=bm->minmax_stackptr;
412         while(stackctr>newstack){
413           bm->minmax_acctotal-=
414             LIMITBYTES(stackctr,bm->minmax_limitstack[stackctr]);
415           bm->minmax_acctotal+=LIMITBYTES(stackctr,limit);
416           
417           if(stackctr<bm->minmax_stackptr)
418             for(i=0;i<bins*2;i++)
419               bm->minmax_binstack[stackctr*bins*2+i]+=
420                 bm->minmax_binstack[(stackctr+1)*bins*2+i];
421
422           stackctr--;
423         }
424         stackctr++;
425         bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
426         bm->minmax_limitstack[stackctr]=limit;
427
428         /* set up new blank stack entry */
429         stackctr++;
430         bm->minmax_stackptr=stackctr;
431         memset(&bm->minmax_binstack[stackctr*bins*2],
432                0,
433                sizeof(*bm->minmax_binstack)*bins*2);
434         bm->minmax_limitstack[stackctr]=0;
435         bm->minmax_posstack[stackctr]=-1;
436         
437       }
438     }
439     
440     /* remove from tail */
441     while(bm->minmax_sampleacc>sampledesired){
442       int samples=
443         ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
444       int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
445
446       for(i=0;i<bins;i++){
447         bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
448           LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,
449                                 actual>i?
450                                 actual:i));
451         bm->minmax_binstack[i]-= 
452           LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,
453                                 actual<i?
454                                 actual:i));
455       }
456
457       if(bm->minmax_limitstack[0]>actual)
458         actual=bm->minmax_limitstack[0];
459       if(bins+bm->minmax_limitstack[0]<actual)
460         actual=bins+bm->minmax_limitstack[0];
461       
462       bm->minmax_acctotal-=LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,actual));
463       bm->minmax_sampleacc-=samples;
464
465       /* revise queue_actual to reflect the limit */
466       bm->queue_actual[bm->minmax_tail]&=0x80000000UL;
467       bm->queue_actual[bm->minmax_tail]|=actual;
468       
469       if(bm->minmax_tail==bm->minmax_posstack[0]){
470         /* the stack becomes a FIFO; the first data has fallen off */
471         memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
472                 sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
473         memmove(bm->minmax_posstack,bm->minmax_posstack+1,
474                 sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
475         memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
476                 sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
477         bm->minmax_stackptr--;
478       }
479       
480       bm->minmax_tail++;
481       if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
482
483     }
484     
485     
486     bm->last_to_flush=bm->minmax_tail;
487   }else{
488     bm->last_to_flush=bm->avg_center;
489   }
490   if(eofflag)
491     bm->last_to_flush=bm->queue_head;
492   return(0);
493 }
494
495 int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
496   private_state         *b=vd->backend_state;
497   bitrate_manager_state *bm=&b->bms;
498
499   if(bm->queue_size==0){
500     if(bm->queue_head==0)return(0);
501
502     memcpy(op,bm->packets,sizeof(*op));
503     bm->queue_head=0;
504
505   }else{
506
507     if(bm->next_to_flush==bm->last_to_flush)return(0);
508
509     {
510       long bin=bm->queue_actual[bm->next_to_flush]&0x7fffffff,i;
511       long bins=bm->queue_bins;
512       ogg_uint32_t *markers=bm->queue_binned+bins*bm->next_to_flush;
513       long bytes=markers[bin];
514
515       memcpy(op,bm->packets+bm->next_to_flush,sizeof(*op));
516
517       /* we have [PACKETBLOBS] possible packets all squished together in
518          the buffer, in sequence.  count in to number [bin] */
519       for(i=0;i<bin;i++)
520         op->packet+=markers[i];
521       op->bytes=bytes;
522         
523     }
524
525     bm->next_to_flush++;
526     if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;
527
528   }
529
530   return(1);
531 }