bitrate.c (16539B)
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 1919 2005-07-24 14:18:04Z baford $ 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 }