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.5 2001/12/19 07:33:51 xiphmont Exp $
16 ********************************************************************/
23 #include "vorbis/codec.h"
24 #include "codec_internal.h"
28 #define BINBITS(pos,bin) ((bin)>0?bm->queue_binned[(pos)*bins+(bin)-1]:0)
29 #define LIMITBITS(pos,bin) ((bin)>-bins?\
30 bm->minmax_binstack[(pos)*bins*2+((bin)+bins)-1]:0)
32 static long LACING_ADJUST(long bits){
33 int addto=((bits+7)/8+1)/256+1;
34 return( ((bits+7)/8+addto)*8 );
37 static double floater_interpolate(bitrate_manager_state *bm,vorbis_info *vi,
39 int bin=bm->avgfloat*BITTRACK_DIVISOR-1.;
43 lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
44 while(lobitrate>desired_rate && bin>0){
46 lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
49 hibitrate=(double)(bin>=bm->queue_bins?bm->avg_binacc[bm->queue_bins-1]:
50 bm->avg_binacc[bin])/bm->avg_sampleacc*vi->rate;
51 while(hibitrate<desired_rate && bin<bm->queue_bins){
53 if(bin<bm->queue_bins)
54 hibitrate=(double)bm->avg_binacc[bin]/bm->avg_sampleacc*vi->rate;
58 if(bin==bm->queue_bins){
59 return bin/(double)BITTRACK_DIVISOR;
61 double delta=(desired_rate-lobitrate)/(hibitrate-lobitrate);
62 return (bin+delta)/(double)BITTRACK_DIVISOR;
66 /* try out a new limit */
67 static long limit_sum(bitrate_manager_state *bm,int limit){
68 int i=bm->minmax_stackptr;
69 long acc=bm->minmax_acctotal;
70 long bins=bm->queue_bins;
73 acc+=LIMITBITS(i,limit);
76 if(bm->minmax_limitstack[i]<=limit)break;
77 acc-=LIMITBITS(i,bm->minmax_limitstack[i]);
78 acc+=LIMITBITS(i,limit);
83 /* compute bitrate tracking setup, allocate circular packet size queue */
84 void vorbis_bitrate_init(vorbis_info *vi,bitrate_manager_state *bm){
86 codec_setup_info *ci=vi->codec_setup;
87 bitrate_manager_info *bi=&ci->bi;
90 memset(bm,0,sizeof(*bm));
94 bm->avg_sampledesired=bi->queue_avg_time*vi->rate;
95 bm->avg_centerdesired=bi->queue_avg_time*vi->rate*bi->queue_avg_center;
96 bm->minmax_sampledesired=bi->queue_minmax_time*vi->rate;
98 /* first find the max possible needed queue size */
99 maxlatency=max(bm->avg_sampledesired-bm->avg_centerdesired,
100 bm->minmax_sampledesired)+bm->avg_centerdesired;
103 (bi->queue_avgmin>0 || bi->queue_avgmax>0 || bi->queue_hardmax>0 ||
104 bi->queue_hardmin>0)){
105 long maxpackets=maxlatency/(ci->blocksizes[0]>>1)+3;
106 long bins=BITTRACK_DIVISOR*ci->passlimit[ci->coupling_passes-1];
108 bm->queue_size=maxpackets;
110 bm->queue_binned=_ogg_malloc(maxpackets*bins*sizeof(*bm->queue_binned));
111 bm->queue_actual=_ogg_malloc(maxpackets*sizeof(*bm->queue_actual));
113 if((bi->queue_avgmin>0 || bi->queue_avgmax>0) &&
114 bi->queue_avg_time>0){
116 bm->avg_binacc=_ogg_malloc(bins*sizeof(*bm->avg_binacc));
117 bm->avgfloat=bi->avgfloat_initial;
124 if((bi->queue_hardmin>0 || bi->queue_hardmax>0) &&
125 bi->queue_minmax_time>0){
127 bm->minmax_binstack=_ogg_malloc((bins+1)*bins*2*
128 sizeof(bm->minmax_binstack));
129 bm->minmax_posstack=_ogg_malloc((bins+1)*
130 sizeof(bm->minmax_posstack));
131 bm->minmax_limitstack=_ogg_malloc((bins+1)*
132 sizeof(bm->minmax_limitstack));
137 /* space for the packet queueing */
138 bm->queue_packet_buffers=calloc(maxpackets,sizeof(*bm->queue_packet_buffers));
139 bm->queue_packets=calloc(maxpackets,sizeof(*bm->queue_packets));
140 for(i=0;i<maxpackets;i++)
141 oggpack_writeinit(bm->queue_packet_buffers+i);
144 bm->queue_packet_buffers=calloc(1,sizeof(*bm->queue_packet_buffers));
145 bm->queue_packets=calloc(1,sizeof(*bm->queue_packets));
146 oggpack_writeinit(bm->queue_packet_buffers);
151 void vorbis_bitrate_clear(bitrate_manager_state *bm){
154 if(bm->queue_binned)_ogg_free(bm->queue_binned);
155 if(bm->queue_actual)_ogg_free(bm->queue_actual);
156 if(bm->avg_binacc)_ogg_free(bm->avg_binacc);
157 if(bm->minmax_binstack)_ogg_free(bm->minmax_binstack);
158 if(bm->minmax_posstack)_ogg_free(bm->minmax_posstack);
159 if(bm->minmax_limitstack)_ogg_free(bm->minmax_limitstack);
160 if(bm->queue_packet_buffers){
161 if(bm->queue_size==0){
162 oggpack_writeclear(bm->queue_packet_buffers);
163 _ogg_free(bm->queue_packet_buffers);
165 for(i=0;i<bm->queue_size;i++)
166 oggpack_writeclear(bm->queue_packet_buffers+i);
167 _ogg_free(bm->queue_packet_buffers);
170 if(bm->queue_packets)_ogg_free(bm->queue_packets);
171 memset(bm,0,sizeof(*bm));
175 int vorbis_bitrate_managed(vorbis_block *vb){
176 vorbis_dsp_state *vd=vb->vd;
177 backend_lookup_state *b=vd->backend_state;
178 bitrate_manager_state *bm=&b->bms;
180 if(bm->queue_binned)return(1);
184 int vorbis_bitrate_maxmarkers(void){
185 return 8*BITTRACK_DIVISOR;
188 /* finish taking in the block we just processed */
189 int vorbis_bitrate_addblock(vorbis_block *vb){
191 vorbis_block_internal *vbi=vb->internal;
192 vorbis_dsp_state *vd=vb->vd;
193 backend_lookup_state *b=vd->backend_state;
194 bitrate_manager_state *bm=&b->bms;
195 vorbis_info *vi=vd->vi;
196 codec_setup_info *ci=vi->codec_setup;
197 bitrate_manager_info *bi=&ci->bi;
198 int eofflag=vb->eofflag;
199 int head=bm->queue_head;
200 int next_head=head+1;
201 int bins=bm->queue_bins;
202 int minmax_head,new_minmax_head;
204 ogg_uint32_t *head_ptr;
207 if(!bm->queue_binned){
209 /* not a bitrate managed stream, but for API simplicity, we'll
210 buffer one packet to keep the code path clean */
212 if(bm->queue_head)return(-1); /* one has been submitted without
216 bm->queue_packets[0].packet=oggpack_get_buffer(&vb->opb);
217 bm->queue_packets[0].bytes=oggpack_bytes(&vb->opb);
218 bm->queue_packets[0].b_o_s=0;
219 bm->queue_packets[0].e_o_s=vb->eofflag;
220 bm->queue_packets[0].granulepos=vb->granulepos;
221 bm->queue_packets[0].packetno=vb->sequence; /* for sake of completeness */
223 memcpy(&temp,bm->queue_packet_buffers,sizeof(vb->opb));
224 memcpy(bm->queue_packet_buffers,&vb->opb,sizeof(vb->opb));
225 memcpy(&vb->opb,&temp,sizeof(vb->opb));
230 /* add encoded packet to head */
231 if(next_head>=bm->queue_size)next_head=0;
232 head_ptr=bm->queue_binned+bins*head;
234 /* is there room to add a block? In proper use of the API, this will
235 never come up... but guard it anyway */
236 if(next_head==bm->avg_tail || next_head==bm->minmax_tail)return(-1);
238 /* add the block to the toplevel queue */
239 bm->queue_head=next_head;
240 bm->queue_actual[head]=(vb->W?0x80000000UL:0);
242 /* buffer packet fields */
243 bm->queue_packets[head].packet=oggpack_get_buffer(&vb->opb);
244 bm->queue_packets[head].bytes=oggpack_bytes(&vb->opb);
245 bm->queue_packets[head].b_o_s=0;
246 bm->queue_packets[head].e_o_s=vb->eofflag;
247 bm->queue_packets[head].granulepos=vb->granulepos;
248 bm->queue_packets[head].packetno=vb->sequence; /* for sake of completeness */
250 /* swap packet buffers */
251 memcpy(&temp,bm->queue_packet_buffers+head,sizeof(vb->opb));
252 memcpy(bm->queue_packet_buffers+head,&vb->opb,sizeof(vb->opb));
253 memcpy(&vb->opb,&temp,sizeof(vb->opb));
256 memcpy(head_ptr,vbi->packet_markers,sizeof(*head_ptr)*bins);
259 new_minmax_head=minmax_head=bm->avg_center;
261 new_minmax_head=minmax_head=head;
263 /* the average tracking queue is updated first; its results (if it's
264 in use) are taken into account by the min/max limiter (if min/max
267 unsigned long desired_center=bm->avg_centerdesired;
268 if(eofflag)desired_center=0;
270 /* update the avg head */
272 bm->avg_binacc[i]+=LACING_ADJUST(head_ptr[i]);
273 bm->avg_sampleacc+=ci->blocksizes[vb->W]>>1;
274 bm->avg_centeracc+=ci->blocksizes[vb->W]>>1;
276 /* update the avg tail if needed */
277 while(bm->avg_sampleacc>bm->avg_sampledesired){
279 ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
280 for(i=0;i<bm->queue_bins;i++)
281 bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
282 bm->avg_sampleacc-=samples;
284 if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
287 /* update the avg center */
288 if(bm->avg_centeracc>desired_center){
289 /* choose the new average floater */
290 double upper=floater_interpolate(bm,vi,bi->queue_avgmax);
291 double lower=floater_interpolate(bm,vi,bi->queue_avgmin);
292 double new=bi->avgfloat_initial,slew;
295 if(upper>0. && upper<new)new=upper;
296 if(lower<bi->avgfloat_minimum)
297 lower=bi->avgfloat_minimum;
298 if(lower>new)new=lower;
300 slew=new-bm->avgfloat;
302 if(slew<bi->avgfloat_downhyst || slew>bi->avgfloat_uphyst){
303 if(slew<bi->avgfloat_downslew_max)
304 new=bm->avgfloat+bi->avgfloat_downslew_max;
305 if(slew>bi->avgfloat_upslew_max)
306 new=bm->avgfloat+bi->avgfloat_upslew_max;
311 /* apply the average floater to new blocks */
312 bin=bm->avgfloat*BITTRACK_DIVISOR; /* truncate on purpose */
313 fprintf(stderr,"u:%f l:%f float:%d ",upper,lower,bin);
314 while(bm->avg_centeracc>desired_center){
316 samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
317 0x80000000UL?1:0]>>1;
319 bm->queue_actual[bm->avg_center]|=bin;
321 bm->avg_centeracc-=samples;
323 if(bm->noisetrigger_postpone)bm->noisetrigger_postpone-=samples;
324 if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
326 new_minmax_head=bm->avg_center;
328 /* track noise bias triggers and noise bias */
329 if(bm->avgfloat<bi->avgfloat_noise_lowtrigger)
330 bm->noisetrigger_request+=1.f;
332 if(bm->noisetrigger_request>0. && bm->avgnoise>0.)
333 bm->noisetrigger_request-=.2f;
335 if(bm->avgfloat>bi->avgfloat_noise_hightrigger)
336 bm->noisetrigger_request-=1.f;
338 if(bm->noisetrigger_request<0 && bm->avgnoise<0.)
339 bm->noisetrigger_request+=.2f;
341 if(bm->noisetrigger_postpone<=0){
342 if(bm->noisetrigger_request<0.){
344 if(-bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
346 bm->noisetrigger_postpone=bm->avg_sampleacc/2;
348 if(bm->noisetrigger_request>0.){
350 if(bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
352 bm->noisetrigger_postpone=bm->avg_sampleacc/2;
355 /* we generally want the noise bias to drift back to zero */
356 bm->noisetrigger_request=0.f;
358 bm->noisetrigger_request= -1.;
360 bm->noisetrigger_request= +1.;
362 if(bm->avgnoise<bi->avgfloat_noise_minval)
363 bm->avgnoise=bi->avgfloat_noise_minval;
364 if(bm->avgnoise>bi->avgfloat_noise_maxval)
365 bm->avgnoise=bi->avgfloat_noise_maxval;
367 fprintf(stderr,"noise:%f req:%f trigger:%ld\n",bm->avgnoise,
368 bm->noisetrigger_request,bm->noisetrigger_postpone);
372 /* if we're not using an average tracker, the 'float' is nailed to
373 the avgfloat_initial value. It needs to be set for the min/max
375 long bin=bi->avgfloat_initial*BITTRACK_DIVISOR; /* truncate on purpose */
376 bm->queue_actual[head]|=bin;
377 new_minmax_head=next_head;
380 /* update the min/max queues and enforce limits */
381 if(bm->minmax_binstack){
382 unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
384 /* add to stack recent */
385 while(minmax_head!=new_minmax_head){
387 int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
388 0x80000000UL?1:0]>>1;
390 /* the construction here is not parallel to the floater's
393 floater[bin-1] <-> floater supported at bin
395 floater[0] <-> floater supported at 1
396 supported at zero is implicit.
397 the BINBITS macro performs offsetting
400 bin minmax[bin*2-1] <-> floater supported at bin
402 1 minmax[bin] <-> floater supported at 1
403 0 minmax[bin-1] <-> no limit/support (limited to/supported at bin 0,
405 -1 minmax[bin-2] <-> floater limited to bin-1
407 -bin+1 minmax[0] <-> floater limited to 1
408 limited to zero (val= -bin) is implicit
410 for(i=0;i<(unsigned int)bins;i++){
411 bm->minmax_binstack[bm->minmax_stackptr*bins*2+bins+i]+=
414 (bm->queue_actual[minmax_head]&0x7fffffffUL)>i+1?
415 (bm->queue_actual[minmax_head]&0x7fffffffUL):i+1));
417 bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
420 (bm->queue_actual[minmax_head]&0x7fffffffUL)<i+1?
421 (bm->queue_actual[minmax_head]&0x7fffffffUL):i+1));
424 bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
428 bm->minmax_limitstack[bm->minmax_stackptr]=0;
429 bm->minmax_sampleacc+=samples;
430 bm->minmax_acctotal+=
432 BINBITS(minmax_head,(bm->queue_actual[minmax_head]&0x7fffffffUL)));
435 if(minmax_head>=bm->queue_size)minmax_head=0;
438 /* check limits, enforce changes */
439 if(bm->minmax_sampleacc>sampledesired){
440 double bitrate=(double)bm->minmax_acctotal/bm->minmax_sampleacc*vi->rate;
443 fprintf(stderr,"prelimit:%dkbps ",(int)bitrate/1000);
444 if((bi->queue_hardmax>0 && bitrate>bi->queue_hardmax) ||
445 (bi->queue_hardmin>0 && bitrate<bi->queue_hardmin)){
448 long bitsum=limit_sum(bm,0);
449 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
451 /* we're off rate. Iteratively try out new hard floater
452 limits until we find one that brings us inside. Here's
453 where we see the whole point of the limit stacks. */
454 if(bitrate>bi->queue_hardmax){
455 for(limit=-1;limit>-bins;limit--){
456 long bitsum=limit_sum(bm,limit);
457 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
458 if(bitrate<=bi->queue_hardmax)break;
460 }else if(bitrate<bi->queue_hardmin){
461 for(limit=1;limit<bins;limit++){
462 long bitsum=limit_sum(bm,limit);
463 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
464 if(bitrate>=bi->queue_hardmin)break;
466 if(bitrate>bi->queue_hardmax)limit--;
469 bitsum=limit_sum(bm,limit);
470 bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
471 fprintf(stderr,"postlimit:%dkbps ",(int)bitrate/1000);
473 /* trace the limit backward, stop when we see a lower limit */
474 newstack=bm->minmax_stackptr-1;
476 if(bm->minmax_limitstack[newstack]<limit)break;
480 /* update bit counter with new limit and replace any stack
481 limits that have been replaced by our new lower limit */
482 stackctr=bm->minmax_stackptr;
483 while(stackctr>newstack){
484 bm->minmax_acctotal-=
485 LIMITBITS(stackctr,bm->minmax_limitstack[stackctr]);
486 bm->minmax_acctotal+=LIMITBITS(stackctr,limit);
488 if(stackctr<bm->minmax_stackptr)
489 for(i=0;i<bins*2;i++)
490 bm->minmax_binstack[stackctr*bins*2+i]+=
491 bm->minmax_binstack[(stackctr+1)*bins*2+i];
496 bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
497 bm->minmax_limitstack[stackctr]=limit;
498 fprintf(stderr,"limit:%d\n",limit);
500 /* set up new blank stack entry */
502 bm->minmax_stackptr=stackctr;
503 memset(&bm->minmax_binstack[stackctr*bins*2],
505 sizeof(*bm->minmax_binstack)*bins*2);
506 bm->minmax_limitstack[stackctr]=0;
507 bm->minmax_posstack[stackctr]=-1;
512 /* remove from tail */
513 while(bm->minmax_sampleacc>sampledesired){
515 ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
516 int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
519 bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
520 LACING_ADJUST(BINBITS(bm->minmax_tail,actual>i+1?actual:i+1));
521 bm->minmax_binstack[i]-=
522 LACING_ADJUST(BINBITS(bm->minmax_tail,actual<i+1?actual:i+1));
525 /* always perform in this order; max overrules min */
526 if(bm->minmax_limitstack[0]>actual)
527 actual=bm->minmax_limitstack[0];
528 if(bins+bm->minmax_limitstack[0]<actual)
529 actual=bins+bm->minmax_limitstack[0];
531 bm->minmax_acctotal-=LACING_ADJUST(BINBITS(bm->minmax_tail,actual));
532 bm->minmax_sampleacc-=samples;
534 /* revise queue_actual to reflect the limit */
535 bm->queue_actual[bm->minmax_tail]=actual;
537 if(bm->minmax_tail==bm->minmax_posstack[0]){
538 /* the stack becomes a FIFO; the first data has fallen off */
539 memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
540 sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
541 memmove(bm->minmax_posstack,bm->minmax_posstack+1,
542 sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
543 memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
544 sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
545 bm->minmax_stackptr--;
549 if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
553 bm->last_to_flush=bm->minmax_tail;
555 bm->last_to_flush=bm->avg_center;
558 bm->last_to_flush=bm->queue_head;
562 int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
563 backend_lookup_state *b=vd->backend_state;
564 bitrate_manager_state *bm=&b->bms;
566 if(bm->queue_size==0){
567 if(bm->queue_head==0)return(0);
569 memcpy(op,bm->queue_packets,sizeof(*op));
573 long bins=bm->queue_bins;
577 if(bm->next_to_flush==bm->last_to_flush)return(0);
579 bin=bm->queue_actual[bm->next_to_flush]&0x7fffffffUL;
580 bytes=(BINBITS(bm->next_to_flush,bin)+7)/8;
582 memcpy(op,bm->queue_packets+bm->next_to_flush,sizeof(*op));
583 if(bytes<op->bytes)op->bytes=bytes;
586 if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;