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-2001             *
   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.7 2001/12/23 10:12:03 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 "bitrate.h"
  27
  28
  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;
  34   ogg_uint32_t bitdel;
  35
  36   if(bin>0)lobits=bm->queue_binned[pos*bins+bin-1];
  37   if(bin<bins)
  38     hibits=bm->queue_binned[pos*bins+bin];
  39   else
  40     hibits=lobits;
  41
  42   bitdel=hibits-lobits;
  43
  44   return(lobits+bitdel*(inbin&((1<<BITTRACK_BPT)-1))/(1<<BITTRACK_BPT));
  45
  46 }
  47
  48 #define LIMITBITS(pos,bin) ((bin)>-bins?\
  49                  bm->minmax_binstack[(pos)*bins*2+((bin)+bins)-1]:0)
  50
  51 static long LACING_ADJUST(long bits){
  52   int addto=((bits+7)/8+1)/256+1;
  53   return( ((bits+7)/8+addto)*8 );
  54 }
  55
  56 static double floater_interpolate(bitrate_manager_state *bm,vorbis_info *vi,
  57                                   double desired_rate){
  58   int bin=bm->avgfloat*BITTRACK_DIVISOR-1.;
  59   double lobitrate;
  60   double hibitrate;
  61
  62   lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
  63   while(lobitrate>desired_rate && bin>0){
  64     bin--;
  65     lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
  66   }
  67
  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){
  71     bin++;
  72     if(bin<bm->queue_bins)
  73       hibitrate=(double)bm->avg_binacc[bin]/bm->avg_sampleacc*vi->rate;
  74   }
  75
  76   /* interpolate */
  77   if(bin==bm->queue_bins){
  78     return bin/(double)BITTRACK_DIVISOR;
  79   }else{
  80     double delta=(desired_rate-lobitrate)/(hibitrate-lobitrate);
  81     return (bin+delta)/BITTRACK_DIVISOR;
  82   }
  83 }
  84
  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;
  90
  91   acc-=LIMITBITS(i,0);
  92   acc+=LIMITBITS(i,limit);
  93
  94   while(i-->0){
  95     if(bm->minmax_limitstack[i]<=limit)break;
  96     acc-=LIMITBITS(i,bm->minmax_limitstack[i]);
  97     acc+=LIMITBITS(i,limit);
  98   }
  99   return(acc);
 100 }
 101
 102 /* compute bitrate tracking setup, allocate circular packet size queue */
 103 void vorbis_bitrate_init(vorbis_info *vi,bitrate_manager_state *bm){
 104   int i;
 105   codec_setup_info *ci=vi->codec_setup;
 106   bitrate_manager_info *bi=&ci->bi;
 107   long maxlatency;
 108
 109   memset(bm,0,sizeof(*bm));
 110
 111   if(bi){
 112
 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;
 116
 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;
 120
 121     if(maxlatency>0 &&
 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];
 126
 127       bm->queue_size=maxpackets;
 128       bm->queue_bins=bins;
 129       bm->queue_binned=_ogg_malloc(maxpackets*bins*sizeof(*bm->queue_binned));
 130       bm->queue_actual=_ogg_malloc(maxpackets*sizeof(*bm->queue_actual));
 131
 132       if((bi->queue_avgmin>0 || bi->queue_avgmax>0) &&
 133          bi->queue_avg_time>0){
 134
 135         bm->avg_binacc=_ogg_malloc(bins*sizeof(*bm->avg_binacc));
 136         bm->avgfloat=bi->avgfloat_initial;
 137
 138
 139       }else{
 140         bm->avg_tail= -1;
 141       }
 142
 143       if((bi->queue_hardmin>0 || bi->queue_hardmax>0) &&
 144          bi->queue_minmax_time>0){
 145
 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));
 152       }else{
 153         bm->minmax_tail= -1;
 154       }
 155
 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);
 161
 162     }else{
 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);
 166     }
 167   }
 168 }
 169
 170 void vorbis_bitrate_clear(bitrate_manager_state *bm){
 171   int i;
 172   if(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);
 183       }else{
 184         for(i=0;i<bm->queue_size;i++)
 185           oggpack_writeclear(bm->queue_packet_buffers+i);
 186         _ogg_free(bm->queue_packet_buffers);
 187       }
 188     }
 189     if(bm->queue_packets)_ogg_free(bm->queue_packets);
 190     memset(bm,0,sizeof(*bm));
 191   }
 192 }
 193
 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;
 198
 199   if(bm->queue_binned)return(1);
 200   return(0);
 201 }
 202
 203 int vorbis_bitrate_maxmarkers(void){
 204   return 8*BITTRACK_DIVISOR;
 205 }
 206
 207 /* finish taking in the block we just processed */
 208 int vorbis_bitrate_addblock(vorbis_block *vb){
 209   int i;
 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;
 222
 223   ogg_uint32_t           *head_ptr;
 224   oggpack_buffer          temp;
 225
 226   if(!bm->queue_binned){
 227     oggpack_buffer temp;
 228     /* not a bitrate managed stream, but for API simplicity, we'll
 229        buffer one packet to keep the code path clean */
 230
 231     if(bm->queue_head)return(-1); /* one has been submitted without
 232                                      being claimed */
 233     bm->queue_head++;
 234
 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 */
 241
 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));
 245
 246     return(0);
 247   }
 248
 249   /* add encoded packet to head */
 250   if(next_head>=bm->queue_size)next_head=0;
 251   head_ptr=bm->queue_binned+bins*head;
 252
 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);
 256
 257   /* add the block to the toplevel queue */
 258   bm->queue_head=next_head;
 259   bm->queue_actual[head]=(vb->W?0x80000000UL:0);
 260
 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 */
 268
 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));
 273
 274   /* save markers */
 275   memcpy(head_ptr,vbi->packet_markers,sizeof(*head_ptr)*bins);
 276
 277   if(bm->avg_binacc)
 278     new_minmax_head=minmax_head=bm->avg_center;
 279   else
 280     new_minmax_head=minmax_head=head;
 281
 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
 284      is in use) */
 285   if(bm->avg_binacc){
 286     unsigned long desired_center=bm->avg_centerdesired;
 287     if(eofflag)desired_center=0;
 288
 289     /* update the avg head */
 290     for(i=0;i<bins;i++)
 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;
 294
 295     if(bm->avg_sampleacc>bm->avg_sampledesired || eofflag){
 296
 297       /* update the avg tail if needed */
 298       while(bm->avg_sampleacc>bm->avg_sampledesired){
 299         int samples=
 300           ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
 301         for(i=0;i<bm->queue_bins;i++)
 302           bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
 303         bm->avg_sampleacc-=samples;
 304         bm->avg_tail++;
 305         if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
 306       }
 307
 308       /* update the avg center */
 309       if(bm->avg_centeracc>desired_center){
 310         /* choose the new average floater */
 311         int samples=ci->blocksizes[vb->W]>>1;
 312         double upper=floater_interpolate(bm,vi,bi->queue_avgmax);
 313         double lower=floater_interpolate(bm,vi,bi->queue_avgmin);
 314         double new=bi->avgfloat_initial,slew;
 315         int bin;
 316
 317         if(upper>0. && upper<new)new=upper;
 318         if(lower<bi->avgfloat_minimum)
 319           lower=bi->avgfloat_minimum;
 320         if(lower>new)new=lower;
 321
 322         slew=(new-bm->avgfloat)/samples*vi->rate;
 323
 324         if(slew<bi->avgfloat_downhyst || slew>bi->avgfloat_uphyst){
 325           if(slew<bi->avgfloat_downslew_max)
 326             new=bm->avgfloat+bi->avgfloat_downslew_max/vi->rate*samples;
 327           if(slew>bi->avgfloat_upslew_max)
 328             new=bm->avgfloat+bi->avgfloat_upslew_max/vi->rate*samples;
 329
 330           bm->avgfloat=new;
 331         }
 332
 333         /* apply the average floater to new blocks */
 334         bin=bm->avgfloat*(BITTRACK_DIVISOR<<BITTRACK_BPT);
 335
 336         while(bm->avg_centeracc>desired_center){
 337           samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
 338                                 0x80000000UL?1:0]>>1;
 339
 340           bm->queue_actual[bm->avg_center]|=bin;
 341
 342           bm->avg_centeracc-=samples;
 343           bm->avg_center++;
 344           if(bm->noisetrigger_postpone)bm->noisetrigger_postpone-=samples;
 345           if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
 346         }
 347         new_minmax_head=bm->avg_center;
 348
 349         /* track noise bias triggers and noise bias */
 350         if(bm->avgfloat<bi->avgfloat_noise_lowtrigger)
 351           bm->noisetrigger_request+=1.f;
 352         else
 353           if(bm->noisetrigger_request>0. && bm->avgnoise>0.)
 354             bm->noisetrigger_request-=.2f;
 355
 356         if(bm->avgfloat>bi->avgfloat_noise_hightrigger)
 357           bm->noisetrigger_request-=1.f;
 358         else
 359           if(bm->noisetrigger_request<0 && bm->avgnoise<0.)
 360             bm->noisetrigger_request+=.2f;
 361
 362         if(bm->noisetrigger_postpone<=0){
 363           if(bm->noisetrigger_request<0.){
 364             bm->avgnoise-=1.f;
 365             if(-bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
 366               bm->avgnoise-=1.f;
 367             bm->noisetrigger_postpone=bm->avg_sampleacc/2;
 368           }
 369           if(bm->noisetrigger_request>0.){
 370             bm->avgnoise+=1.f;
 371             if(bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
 372               bm->avgnoise+=1.f;
 373             bm->noisetrigger_postpone=bm->avg_sampleacc/2;
 374           }
 375
 376           /* we generally want the noise bias to drift back to zero */
 377           bm->noisetrigger_request=0.f;
 378           if(bm->avgnoise>0)
 379             bm->noisetrigger_request= -1.;
 380           if(bm->avgnoise<0)
 381             bm->noisetrigger_request= +1.;
 382
 383           if(bm->avgnoise<bi->avgfloat_noise_minval)
 384             bm->avgnoise=bi->avgfloat_noise_minval;
 385           if(bm->avgnoise>bi->avgfloat_noise_maxval)
 386             bm->avgnoise=bi->avgfloat_noise_maxval;
 387         }
 388       }
 389     }
 390   }else{
 391     /* if we're not using an average tracker, the 'float' is nailed to
 392        the avgfloat_initial value.  It needs to be set for the min/max
 393        to deal properly */
 394     long bin=bi->avgfloat_initial*(BITTRACK_DIVISOR<<BITTRACK_BPT);
 395     bm->queue_actual[head]|=bin;
 396     new_minmax_head=next_head;
 397   }
 398
 399   /* update the min/max queues and enforce limits */
 400   if(bm->minmax_binstack){
 401     unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
 402
 403     /* add to stack recent */
 404     while(minmax_head!=new_minmax_head){
 405       unsigned int i;
 406       int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
 407                                 0x80000000UL?1:0]>>1;
 408
 409         /* the construction here is not parallel to the floater's
 410            stack.
 411
 412            floater[bin-1]  <-> floater supported at bin
 413            ...
 414            floater[0]      <-> floater supported at 1
 415            supported at zero is implicit.
 416            the BINBITS macro performs offsetting
 417
 418
 419       bin  minmax[bin*2-1] <-> floater supported at bin
 420            ...
 421         1  minmax[bin]     <-> floater supported at 1
 422         0  minmax[bin-1]   <-> no limit/support (limited to/supported at bin 0,
 423                                                  ie, no effect)
 424        -1  minmax[bin-2]   <-> floater limited to bin-1
 425            ...
 426     -bin+1  minmax[0]       <-> floater limited to 1
 427             limited to zero (val= -bin) is implicit
 428         */
 429       for(i=0;i<(unsigned int)bins;i++){
 430         bm->minmax_binstack[bm->minmax_stackptr*bins*2+bins+i]+=
 431           LACING_ADJUST(
 432           BINBITS(bm,minmax_head,
 433                   (bm->queue_actual[minmax_head]&0x7fffffffUL)>
 434                   ((i+1)<<BITTRACK_BPT)?
 435                   bm->queue_actual[minmax_head]:
 436                   ((i+1)<<BITTRACK_BPT)));
 437
 438         bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
 439           LACING_ADJUST(
 440           BINBITS(bm,minmax_head,
 441                   (bm->queue_actual[minmax_head]&0x7fffffffUL)<
 442                   ((i+1)<<BITTRACK_BPT)?
 443                   bm->queue_actual[minmax_head]:
 444                   ((i+1)<<BITTRACK_BPT)));
 445       }
 446
 447       bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
 448                                                                past
 449                                                                like
 450                                                                typical */
 451       bm->minmax_limitstack[bm->minmax_stackptr]=0;
 452       bm->minmax_sampleacc+=samples;
 453       bm->minmax_acctotal+=
 454         LACING_ADJUST(
 455         BINBITS(bm,minmax_head,bm->queue_actual[minmax_head]));
 456
 457       minmax_head++;
 458       if(minmax_head>=bm->queue_size)minmax_head=0;
 459     }
 460
 461     /* check limits, enforce changes */
 462     if(bm->minmax_sampleacc>sampledesired){
 463       double bitrate=(double)bm->minmax_acctotal/bm->minmax_sampleacc*vi->rate;
 464       int limit=0;
 465
 466       if((bi->queue_hardmax>0 && bitrate>bi->queue_hardmax) ||
 467          (bi->queue_hardmin>0 && bitrate<bi->queue_hardmin)){
 468         int newstack;
 469         int stackctr;
 470         long bitsum=limit_sum(bm,0);
 471
 472         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 473
 474         /* we're off rate.  Iteratively try out new hard floater
 475            limits until we find one that brings us inside.  Here's
 476            where we see the whole point of the limit stacks.  */
 477         if(bi->queue_hardmax>0 && bitrate>bi->queue_hardmax){
 478           for(limit=-1;limit>-bins;limit--){
 479             long bitsum=limit_sum(bm,limit);
 480             bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 481             if(bitrate<=bi->queue_hardmax)break;
 482           }
 483         }else if(bitrate<bi->queue_hardmin){
 484           for(limit=1;limit<bins;limit++){
 485             long bitsum=limit_sum(bm,limit);
 486             bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 487             if(bitrate>=bi->queue_hardmin)break;
 488           }
 489           if(bitrate>bi->queue_hardmax)limit--;
 490         }
 491
 492         for(i=limit-1;i>-bins;i--){
 493           long bitsum=limit_sum(bm,i);
 494           bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 495         }
 496
 497         bitsum=limit_sum(bm,limit);
 498         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 499
 500         /* trace the limit backward, stop when we see a lower limit */
 501         newstack=bm->minmax_stackptr-1;
 502         while(newstack>=0){
 503           if(bm->minmax_limitstack[newstack]<limit)break;
 504           newstack--;
 505         }
 506
 507         /* update bit counter with new limit and replace any stack
 508            limits that have been replaced by our new lower limit */
 509         stackctr=bm->minmax_stackptr;
 510         while(stackctr>newstack){
 511           bm->minmax_acctotal-=
 512             LIMITBITS(stackctr,bm->minmax_limitstack[stackctr]);
 513           bm->minmax_acctotal+=LIMITBITS(stackctr,limit);
 514
 515           if(stackctr<bm->minmax_stackptr)
 516             for(i=0;i<bins*2;i++)
 517               bm->minmax_binstack[stackctr*bins*2+i]+=
 518               bm->minmax_binstack[(stackctr+1)*bins*2+i];
 519
 520           stackctr--;
 521         }
 522         stackctr++;
 523         bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
 524         bm->minmax_limitstack[stackctr]=limit;
 525
 526         /* set up new blank stack entry */
 527         stackctr++;
 528         bm->minmax_stackptr=stackctr;
 529         memset(&bm->minmax_binstack[stackctr*bins*2],
 530                0,
 531                sizeof(*bm->minmax_binstack)*bins*2);
 532         bm->minmax_limitstack[stackctr]=0;
 533         bm->minmax_posstack[stackctr]=-1;
 534
 535       }
 536     }
 537
 538     /* remove from tail */
 539     while(bm->minmax_sampleacc>sampledesired){
 540       int samples=
 541         ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
 542       int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
 543
 544       for(i=0;i<bins;i++){
 545         bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
 546           LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
 547                                 actual>((i+1)<<BITTRACK_BPT)?
 548                                 actual:((i+1)<<BITTRACK_BPT)));
 549         bm->minmax_binstack[i]-=
 550           LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
 551                                 actual<((i+1)<<BITTRACK_BPT)?
 552                                 actual:((i+1)<<BITTRACK_BPT)));
 553       }
 554
 555       /* always perform in this order; max overrules min */
 556       if((bm->minmax_limitstack[0]<<BITTRACK_BPT)>actual)
 557         actual=(bm->minmax_limitstack[0]<<BITTRACK_BPT);
 558       if(((bins+bm->minmax_limitstack[0])<<BITTRACK_BPT)<actual)
 559         actual=(bins+bm->minmax_limitstack[0])<<BITTRACK_BPT;
 560
 561       bm->minmax_acctotal-=LACING_ADJUST(BINBITS(bm,bm->minmax_tail,actual));
 562       bm->minmax_sampleacc-=samples;
 563
 564       /* revise queue_actual to reflect the limit */
 565       bm->queue_actual[bm->minmax_tail]&=0x80000000UL;
 566       bm->queue_actual[bm->minmax_tail]|=actual;
 567
 568       if(bm->minmax_tail==bm->minmax_posstack[0]){
 569         /* the stack becomes a FIFO; the first data has fallen off */
 570         memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
 571                 sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
 572         memmove(bm->minmax_posstack,bm->minmax_posstack+1,
 573                 sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
 574         memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
 575                 sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
 576         bm->minmax_stackptr--;
 577       }
 578
 579       bm->minmax_tail++;
 580       if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
 581     }
 582
 583
 584     bm->last_to_flush=bm->minmax_tail;
 585   }else{
 586     bm->last_to_flush=bm->avg_center;
 587   }
 588   if(eofflag)
 589     bm->last_to_flush=bm->queue_head;
 590   return(0);
 591 }
 592
 593 int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
 594   backend_lookup_state  *b=vd->backend_state;
 595   bitrate_manager_state *bm=&b->bms;
 596
 597   if(bm->queue_size==0){
 598     if(bm->queue_head==0)return(0);
 599
 600     memcpy(op,bm->queue_packets,sizeof(*op));
 601     bm->queue_head=0;
 602
 603   }else{
 604     long bin;
 605     long bytes;
 606
 607     if(bm->next_to_flush==bm->last_to_flush)return(0);
 608
 609     bin=bm->queue_actual[bm->next_to_flush];
 610     bytes=(BINBITS(bm,bm->next_to_flush,bin)+7)/8;
 611
 612     memcpy(op,bm->queue_packets+bm->next_to_flush,sizeof(*op));
 613     if(bytes<op->bytes)op->bytes=bytes;
 614
 615     bm->next_to_flush++;
 616     if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;
 617
 618     if(bytes==0)exit(1);
 619   }
 620
 621   return(1);
 622 }