1 /********************************************************************
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. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 *
9 * by the XIPHOPHORUS Company http://www.xiph.org/ *
11 ********************************************************************
13 function: bitrate tracking and management
14 last mod: $Id: bitrate.c,v 1.8 2001/12/23 11:53:52 xiphmont Exp $
16 ********************************************************************/
23 #include "vorbis/codec.h"
24 #include "codec_internal.h"
29 static long BINBITS(bitrate_manager_state *bm,long pos,long inbin){
30 int bins=bm->queue_bins;
31 int bin=((inbin&0x7fffffffUL)>>BITTRACK_BPT);
32 ogg_uint32_t lobits=0;
33 ogg_uint32_t hibits=0;
36 if(bin>0)lobits=bm->queue_binned[pos*bins+bin-1];
38 hibits=bm->queue_binned[pos*bins+bin];
44 return(lobits+bitdel*(inbin&((1<<BITTRACK_BPT)-1))/(1<<BITTRACK_BPT));
48 #define LIMITBITS(pos,bin) ((bin)>-bins?\
49 bm->minmax_binstack[(pos)*bins*2+((bin)+bins)-1]:0)
51 static long LACING_ADJUST(long bits){
52 int addto=((bits+7)/8+1)/256+1;
53 return( ((bits+7)/8+addto)*8 );
56 static double floater_interpolate(bitrate_manager_state *bm,vorbis_info *vi,
58 int bin=bm->avgfloat*BITTRACK_DIVISOR-1.;
62 lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
63 while(lobitrate>desired_rate && bin>0){
65 lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
68 hibitrate=(double)(bin>=bm->queue_bins?bm->avg_binacc[bm->queue_bins-1]:
69 bm->avg_binacc[bin])/bm->avg_sampleacc*vi->rate;
70 while(hibitrate<desired_rate && bin<bm->queue_bins){
72 if(bin<bm->queue_bins)
73 hibitrate=(double)bm->avg_binacc[bin]/bm->avg_sampleacc*vi->rate;
77 if(bin==bm->queue_bins){
78 return bin/(double)BITTRACK_DIVISOR;
80 double delta=(desired_rate-lobitrate)/(hibitrate-lobitrate);
81 return (bin+delta)/BITTRACK_DIVISOR;
85 /* try out a new limit */
86 static long limit_sum(bitrate_manager_state *bm,int limit){
87 int i=bm->minmax_stackptr;
88 long acc=bm->minmax_acctotal;
89 long bins=bm->queue_bins;
92 acc+=LIMITBITS(i,limit);
95 if(bm->minmax_limitstack[i]<=limit)break;
96 acc-=LIMITBITS(i,bm->minmax_limitstack[i]);
97 acc+=LIMITBITS(i,limit);
102 /* compute bitrate tracking setup, allocate circular packet size queue */
103 void vorbis_bitrate_init(vorbis_info *vi,bitrate_manager_state *bm){
105 codec_setup_info *ci=vi->codec_setup;
106 bitrate_manager_info *bi=&ci->bi;
109 memset(bm,0,sizeof(*bm));
113 bm->avg_sampledesired=bi->queue_avg_time*vi->rate;
114 bm->avg_centerdesired=bi->queue_avg_time*vi->rate*bi->queue_avg_center;
115 bm->minmax_sampledesired=bi->queue_minmax_time*vi->rate;
117 /* first find the max possible needed queue size */
118 maxlatency=max(bm->avg_sampledesired-bm->avg_centerdesired,
119 bm->minmax_sampledesired)+bm->avg_centerdesired;
122 (bi->queue_avgmin>0 || bi->queue_avgmax>0 || bi->queue_hardmax>0 ||
123 bi->queue_hardmin>0)){
124 long maxpackets=maxlatency/(ci->blocksizes[0]>>1)+3;
125 long bins=BITTRACK_DIVISOR*ci->passlimit[ci->coupling_passes-1];
127 bm->queue_size=maxpackets;
129 bm->queue_binned=_ogg_malloc(maxpackets*bins*sizeof(*bm->queue_binned));
130 bm->queue_actual=_ogg_malloc(maxpackets*sizeof(*bm->queue_actual));
132 if((bi->queue_avgmin>0 || bi->queue_avgmax>0) &&
133 bi->queue_avg_time>0){
135 bm->avg_binacc=_ogg_malloc(bins*sizeof(*bm->avg_binacc));
136 bm->avgfloat=bi->avgfloat_initial;
143 if((bi->queue_hardmin>0 || bi->queue_hardmax>0) &&
144 bi->queue_minmax_time>0){
146 bm->minmax_binstack=_ogg_calloc((bins+1)*bins*2,
147 sizeof(bm->minmax_binstack));
148 bm->minmax_posstack=_ogg_calloc((bins+1),
149 sizeof(bm->minmax_posstack));
150 bm->minmax_limitstack=_ogg_calloc((bins+1),
151 sizeof(bm->minmax_limitstack));
156 /* space for the packet queueing */
157 bm->queue_packet_buffers=calloc(maxpackets,sizeof(*bm->queue_packet_buffers));
158 bm->queue_packets=calloc(maxpackets,sizeof(*bm->queue_packets));
159 for(i=0;i<maxpackets;i++)
160 oggpack_writeinit(bm->queue_packet_buffers+i);
163 bm->queue_packet_buffers=calloc(1,sizeof(*bm->queue_packet_buffers));
164 bm->queue_packets=calloc(1,sizeof(*bm->queue_packets));
165 oggpack_writeinit(bm->queue_packet_buffers);
170 void vorbis_bitrate_clear(bitrate_manager_state *bm){
173 if(bm->queue_binned)_ogg_free(bm->queue_binned);
174 if(bm->queue_actual)_ogg_free(bm->queue_actual);
175 if(bm->avg_binacc)_ogg_free(bm->avg_binacc);
176 if(bm->minmax_binstack)_ogg_free(bm->minmax_binstack);
177 if(bm->minmax_posstack)_ogg_free(bm->minmax_posstack);
178 if(bm->minmax_limitstack)_ogg_free(bm->minmax_limitstack);
179 if(bm->queue_packet_buffers){
180 if(bm->queue_size==0){
181 oggpack_writeclear(bm->queue_packet_buffers);
182 _ogg_free(bm->queue_packet_buffers);
184 for(i=0;i<bm->queue_size;i++)
185 oggpack_writeclear(bm->queue_packet_buffers+i);
186 _ogg_free(bm->queue_packet_buffers);
189 if(bm->queue_packets)_ogg_free(bm->queue_packets);
190 memset(bm,0,sizeof(*bm));
194 int vorbis_bitrate_managed(vorbis_block *vb){
195 vorbis_dsp_state *vd=vb->vd;
196 backend_lookup_state *b=vd->backend_state;
197 bitrate_manager_state *bm=&b->bms;
199 if(bm->queue_binned)return(1);
203 int vorbis_bitrate_maxmarkers(void){
204 return 8*BITTRACK_DIVISOR;
207 /* finish taking in the block we just processed */
208 int vorbis_bitrate_addblock(vorbis_block *vb){
210 vorbis_block_internal *vbi=vb->internal;
211 vorbis_dsp_state *vd=vb->vd;
212 backend_lookup_state *b=vd->backend_state;
213 bitrate_manager_state *bm=&b->bms;
214 vorbis_info *vi=vd->vi;
215 codec_setup_info *ci=vi->codec_setup;
216 bitrate_manager_info *bi=&ci->bi;
217 int eofflag=vb->eofflag;
218 int head=bm->queue_head;
219 int next_head=head+1;
220 int bins=bm->queue_bins;
221 int minmax_head,new_minmax_head;
223 ogg_uint32_t *head_ptr;
226 if(!bm->queue_binned){
228 /* not a bitrate managed stream, but for API simplicity, we'll
229 buffer one packet to keep the code path clean */
231 if(bm->queue_head)return(-1); /* one has been submitted without
235 bm->queue_packets[0].packet=oggpack_get_buffer(&vb->opb);
236 bm->queue_packets[0].bytes=oggpack_bytes(&vb->opb);
237 bm->queue_packets[0].b_o_s=0;
238 bm->queue_packets[0].e_o_s=vb->eofflag;
239 bm->queue_packets[0].granulepos=vb->granulepos;
240 bm->queue_packets[0].packetno=vb->sequence; /* for sake of completeness */
242 memcpy(&temp,bm->queue_packet_buffers,sizeof(vb->opb));
243 memcpy(bm->queue_packet_buffers,&vb->opb,sizeof(vb->opb));
244 memcpy(&vb->opb,&temp,sizeof(vb->opb));
249 /* add encoded packet to head */
250 if(next_head>=bm->queue_size)next_head=0;
251 head_ptr=bm->queue_binned+bins*head;
253 /* is there room to add a block? In proper use of the API, this will
254 never come up... but guard it anyway */
255 if(next_head==bm->avg_tail || next_head==bm->minmax_tail)return(-1);
257 /* add the block to the toplevel queue */
258 bm->queue_head=next_head;
259 bm->queue_actual[head]=(vb->W?0x80000000UL:0);
261 /* buffer packet fields */
262 bm->queue_packets[head].packet=oggpack_get_buffer(&vb->opb);
263 bm->queue_packets[head].bytes=oggpack_bytes(&vb->opb);
264 bm->queue_packets[head].b_o_s=0;
265 bm->queue_packets[head].e_o_s=vb->eofflag;
266 bm->queue_packets[head].granulepos=vb->granulepos;
267 bm->queue_packets[head].packetno=vb->sequence; /* for sake of completeness */
269 /* swap packet buffers */
270 memcpy(&temp,bm->queue_packet_buffers+head,sizeof(vb->opb));
271 memcpy(bm->queue_packet_buffers+head,&vb->opb,sizeof(vb->opb));
272 memcpy(&vb->opb,&temp,sizeof(vb->opb));
275 memcpy(head_ptr,vbi->packet_markers,sizeof(*head_ptr)*bins);
278 new_minmax_head=minmax_head=bm->avg_center;
280 new_minmax_head=minmax_head=head;
282 /* the average tracking queue is updated first; its results (if it's
283 in use) are taken into account by the min/max limiter (if min/max
286 unsigned long desired_center=bm->avg_centerdesired;
287 if(eofflag)desired_center=0;
289 /* update the avg head */
291 bm->avg_binacc[i]+=LACING_ADJUST(head_ptr[i]);
292 bm->avg_sampleacc+=ci->blocksizes[vb->W]>>1;
293 bm->avg_centeracc+=ci->blocksizes[vb->W]>>1;
295 if(bm->avg_sampleacc>bm->avg_sampledesired || eofflag){
297 /* update the avg center */
298 if(bm->avg_centeracc>desired_center){
299 /* choose the new average floater */
300 int samples=ci->blocksizes[vb->W]>>1;
301 double upper=floater_interpolate(bm,vi,bi->queue_avgmax);
302 double lower=floater_interpolate(bm,vi,bi->queue_avgmin);
303 double new=bi->avgfloat_initial,slew;
306 if(upper>0. && upper<new)new=upper;
307 if(lower<bi->avgfloat_minimum)
308 lower=bi->avgfloat_minimum;
309 if(lower>new)new=lower;
311 slew=(new-bm->avgfloat)/samples*vi->rate;
313 if(slew<bi->avgfloat_downslew_max)
314 new=bm->avgfloat+bi->avgfloat_downslew_max/vi->rate*samples;
315 if(slew>bi->avgfloat_upslew_max)
316 new=bm->avgfloat+bi->avgfloat_upslew_max/vi->rate*samples;
320 fprintf(stderr,"%d float: %f\n",bm->avg_center,new);
322 /* apply the average floater to new blocks */
323 bin=bm->avgfloat*(BITTRACK_DIVISOR<<BITTRACK_BPT);
325 while(bm->avg_centeracc>desired_center){
326 samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
327 0x80000000UL?1:0]>>1;
329 bm->queue_actual[bm->avg_center]|=bin;
331 bm->avg_centeracc-=samples;
333 if(bm->noisetrigger_postpone)bm->noisetrigger_postpone-=samples;
334 if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
336 new_minmax_head=bm->avg_center;
338 /* track noise bias triggers and noise bias */
339 if(bm->avgfloat<bi->avgfloat_noise_lowtrigger)
340 bm->noisetrigger_request+=1.f;
342 if(bm->noisetrigger_request>0. && bm->avgnoise>0.)
343 bm->noisetrigger_request-=.2f;
345 if(bm->avgfloat>bi->avgfloat_noise_hightrigger)
346 bm->noisetrigger_request-=1.f;
348 if(bm->noisetrigger_request<0 && bm->avgnoise<0.)
349 bm->noisetrigger_request+=.2f;
351 if(bm->noisetrigger_postpone<=0){
352 if(bm->noisetrigger_request<0.){
354 if(-bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
356 bm->noisetrigger_postpone=bm->avg_sampleacc/2;
358 if(bm->noisetrigger_request>0.){
360 if(bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
362 bm->noisetrigger_postpone=bm->avg_sampleacc/2;
365 /* we generally want the noise bias to drift back to zero */
366 bm->noisetrigger_request=0.f;
368 bm->noisetrigger_request= -1.;
370 bm->noisetrigger_request= +1.;
372 if(bm->avgnoise<bi->avgfloat_noise_minval)
373 bm->avgnoise=bi->avgfloat_noise_minval;
374 if(bm->avgnoise>bi->avgfloat_noise_maxval)
375 bm->avgnoise=bi->avgfloat_noise_maxval;
379 /* update the avg tail if needed */
380 while(bm->avg_sampleacc>bm->avg_sampledesired){
382 ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
383 for(i=0;i<bm->queue_bins;i++)
384 bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
385 bm->avg_sampleacc-=samples;
387 if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
393 /* if we're not using an average tracker, the 'float' is nailed to
394 the avgfloat_initial value. It needs to be set for the min/max
396 long bin=bi->avgfloat_initial*(BITTRACK_DIVISOR<<BITTRACK_BPT);
397 bm->queue_actual[head]|=bin;
398 new_minmax_head=next_head;
401 /* update the min/max queues and enforce limits */
402 if(bm->minmax_binstack){
403 unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
405 /* add to stack recent */
406 while(minmax_head!=new_minmax_head){
408 int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
409 0x80000000UL?1:0]>>1;
411 /* the construction here is not parallel to the floater's
414 floater[bin-1] <-> floater supported at bin
416 floater[0] <-> floater supported at 1
417 supported at zero is implicit.
418 the BINBITS macro performs offsetting
421 bin minmax[bin*2-1] <-> floater supported at bin
423 1 minmax[bin] <-> floater supported at 1
424 0 minmax[bin-1] <-> no limit/support (limited to/supported at bin 0,
426 -1 minmax[bin-2] <-> floater limited to bin-1
428 -bin+1 minmax[0] <-> floater limited to 1
429 limited to zero (val= -bin) is implicit
431 for(i=0;i<(unsigned int)bins;i++){
432 bm->minmax_binstack[bm->minmax_stackptr*bins*2+bins+i]+=
434 BINBITS(bm,minmax_head,
435 (bm->queue_actual[minmax_head]&0x7fffffffUL)>
436 ((i+1)<<BITTRACK_BPT)?
437 bm->queue_actual[minmax_head]:
438 ((i+1)<<BITTRACK_BPT)));
440 bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
442 BINBITS(bm,minmax_head,
443 (bm->queue_actual[minmax_head]&0x7fffffffUL)<
444 ((i+1)<<BITTRACK_BPT)?
445 bm->queue_actual[minmax_head]:
446 ((i+1)<<BITTRACK_BPT)));
449 bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
453 bm->minmax_limitstack[bm->minmax_stackptr]=0;
454 bm->minmax_sampleacc+=samples;
455 bm->minmax_acctotal+=
456 LACING_ADJUST(BINBITS(bm,minmax_head,bm->queue_actual[minmax_head]));
459 if(minmax_head>=bm->queue_size)minmax_head=0;
462 /* check limits, enforce changes */
463 if(bm->minmax_sampleacc>sampledesired){
464 double bitrate=(double)bm->minmax_acctotal/bm->minmax_sampleacc*vi->rate;
467 if((bi->queue_hardmax>0 && bitrate>bi->queue_hardmax) ||
468 (bi->queue_hardmin>0 && bitrate<bi->queue_hardmin)){
471 long bitsum=limit_sum(bm,0);
473 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
475 /* we're off rate. Iteratively try out new hard floater
476 limits until we find one that brings us inside. Here's
477 where we see the whole point of the limit stacks. */
478 if(bi->queue_hardmax>0 && bitrate>bi->queue_hardmax){
479 for(limit=-1;limit>-bins;limit--){
480 long bitsum=limit_sum(bm,limit);
481 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
482 if(bitrate<=bi->queue_hardmax)break;
484 }else if(bitrate<bi->queue_hardmin){
485 for(limit=1;limit<bins;limit++){
486 long bitsum=limit_sum(bm,limit);
487 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
488 if(bitrate>=bi->queue_hardmin)break;
490 if(bitrate>bi->queue_hardmax)limit--;
493 for(i=limit-1;i>-bins;i--){
494 long bitsum=limit_sum(bm,i);
495 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
498 bitsum=limit_sum(bm,limit);
499 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
501 /* trace the limit backward, stop when we see a lower limit */
502 newstack=bm->minmax_stackptr-1;
504 if(bm->minmax_limitstack[newstack]<limit)break;
508 /* update bit counter with new limit and replace any stack
509 limits that have been replaced by our new lower limit */
510 stackctr=bm->minmax_stackptr;
511 while(stackctr>newstack){
512 bm->minmax_acctotal-=
513 LIMITBITS(stackctr,bm->minmax_limitstack[stackctr]);
514 bm->minmax_acctotal+=LIMITBITS(stackctr,limit);
516 if(stackctr<bm->minmax_stackptr)
517 for(i=0;i<bins*2;i++)
518 bm->minmax_binstack[stackctr*bins*2+i]+=
519 bm->minmax_binstack[(stackctr+1)*bins*2+i];
524 bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
525 bm->minmax_limitstack[stackctr]=limit;
527 /* set up new blank stack entry */
529 bm->minmax_stackptr=stackctr;
530 memset(&bm->minmax_binstack[stackctr*bins*2],
532 sizeof(*bm->minmax_binstack)*bins*2);
533 bm->minmax_limitstack[stackctr]=0;
534 bm->minmax_posstack[stackctr]=-1;
539 /* remove from tail */
540 while(bm->minmax_sampleacc>sampledesired){
542 ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
543 int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
546 bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
547 LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
548 actual>((i+1)<<BITTRACK_BPT)?
549 actual:((i+1)<<BITTRACK_BPT)));
550 bm->minmax_binstack[i]-=
551 LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
552 actual<((i+1)<<BITTRACK_BPT)?
553 actual:((i+1)<<BITTRACK_BPT)));
556 /* always perform in this order; max overrules min */
557 if((bm->minmax_limitstack[0]<<BITTRACK_BPT)>actual)
558 actual=(bm->minmax_limitstack[0]<<BITTRACK_BPT);
559 if(((bins+bm->minmax_limitstack[0])<<BITTRACK_BPT)<actual)
560 actual=(bins+bm->minmax_limitstack[0])<<BITTRACK_BPT;
562 bm->minmax_acctotal-=LACING_ADJUST(BINBITS(bm,bm->minmax_tail,actual));
563 bm->minmax_sampleacc-=samples;
565 /* revise queue_actual to reflect the limit */
566 bm->queue_actual[bm->minmax_tail]&=0x80000000UL;
567 bm->queue_actual[bm->minmax_tail]|=actual;
569 if(bm->minmax_tail==bm->minmax_posstack[0]){
570 /* the stack becomes a FIFO; the first data has fallen off */
571 memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
572 sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
573 memmove(bm->minmax_posstack,bm->minmax_posstack+1,
574 sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
575 memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
576 sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
577 bm->minmax_stackptr--;
581 if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
585 bm->last_to_flush=bm->minmax_tail;
587 bm->last_to_flush=bm->avg_center;
590 bm->last_to_flush=bm->queue_head;
594 int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
595 backend_lookup_state *b=vd->backend_state;
596 bitrate_manager_state *bm=&b->bms;
598 if(bm->queue_size==0){
599 if(bm->queue_head==0)return(0);
601 memcpy(op,bm->queue_packets,sizeof(*op));
608 if(bm->next_to_flush==bm->last_to_flush)return(0);
610 bin=bm->queue_actual[bm->next_to_flush];
611 bytes=(BINBITS(bm,bm->next_to_flush,bin)+7)/8;
613 memcpy(op,bm->queue_packets+bm->next_to_flush,sizeof(*op));
615 if(bytes<op->bytes)op->bytes=bytes;
618 if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;