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.13 2002/06/28 22:19:35 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+1)*bins*2,
 122                                         sizeof(bm->minmax_binstack));
 123         bm->minmax_posstack=_ogg_calloc((bins+1),
 124                                       sizeof(bm->minmax_posstack));
 125         bm->minmax_limitstack=_ogg_calloc((bins+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   backend_lookup_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   backend_lookup_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
 299         while(bm->avg_centeracc>desired_center){
 300           samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
 301                                 0x80000000UL?1:0]>>1;
 302
 303           bm->queue_actual[bm->avg_center]|=bin;
 304
 305           bm->avg_centeracc-=samples;
 306           bm->avg_center++;
 307           if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
 308         }
 309         new_minmax_head=bm->avg_center;
 310
 311       }
 312
 313       /* update the avg tail if needed */
 314       while(bm->avg_sampleacc>bm->avg_sampledesired){
 315         int samples=
 316           ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
 317         for(i=0;i<bm->queue_bins;i++)
 318           bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
 319         bm->avg_sampleacc-=samples;
 320         bm->avg_tail++;
 321         if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
 322       }
 323
 324
 325     }
 326   }else{
 327     /* if we're not using an average tracker, the 'float' is nailed to
 328        the avgfloat_initial value.  It needs to be set for the min/max
 329        to deal properly */
 330     long bin=PACKETBLOBS/2;
 331     bm->queue_actual[head]|=bin;
 332     new_minmax_head=next_head;
 333   }
 334
 335   /* update the min/max queues and enforce limits */
 336   if(bm->minmax_binstack){
 337     unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
 338
 339     /* add to stack recent */
 340     while(minmax_head!=new_minmax_head){
 341       unsigned int i;
 342       int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
 343                                 0x80000000UL?1:0]>>1;
 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                                 (bm->queue_actual[minmax_head]&0x7fffffffUL)>i?
 349                                 bm->queue_actual[minmax_head]:i));
 350
 351         bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
 352           LACING_ADJUST(BINBYTES(bm,minmax_head,
 353                                 (bm->queue_actual[minmax_head]&0x7fffffffUL)<i?
 354                                 bm->queue_actual[minmax_head]:i));
 355       }
 356
 357       bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
 358                                                                past
 359                                                                like
 360                                                                typical */
 361       bm->minmax_limitstack[bm->minmax_stackptr]=0;
 362       bm->minmax_sampleacc+=samples;
 363       bm->minmax_acctotal+=
 364         LACING_ADJUST(BINBYTES(bm,minmax_head,bm->queue_actual[minmax_head]));
 365
 366       minmax_head++;
 367       if(minmax_head>=bm->queue_size)minmax_head=0;
 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=limit_sum(bm,0)*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;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;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         for(i=limit-1;i>-bins;i--){
 403           long bitsum=limit_sum(bm,i)*8;
 404           bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 405         }
 406
 407         bitsum=limit_sum(bm,limit)*8;
 408         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
 409
 410         /* trace the limit backward, stop when we see a lower limit */
 411         newstack=bm->minmax_stackptr-1;
 412         while(newstack>=0){
 413           if(bm->minmax_limitstack[newstack]<limit)break;
 414           newstack--;
 415         }
 416
 417         /* update bit counter with new limit and replace any stack
 418            limits that have been replaced by our new lower limit */
 419         stackctr=bm->minmax_stackptr;
 420         while(stackctr>newstack){
 421           bm->minmax_acctotal-=
 422             LIMITBYTES(stackctr,bm->minmax_limitstack[stackctr]);
 423           bm->minmax_acctotal+=LIMITBYTES(stackctr,limit);
 424
 425           if(stackctr<bm->minmax_stackptr)
 426             for(i=0;i<bins*2;i++)
 427               bm->minmax_binstack[stackctr*bins*2+i]+=
 428               bm->minmax_binstack[(stackctr+1)*bins*2+i];
 429
 430           stackctr--;
 431         }
 432         stackctr++;
 433         bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
 434         bm->minmax_limitstack[stackctr]=limit;
 435
 436         /* set up new blank stack entry */
 437         stackctr++;
 438         bm->minmax_stackptr=stackctr;
 439         memset(&bm->minmax_binstack[stackctr*bins*2],
 440                0,
 441                sizeof(*bm->minmax_binstack)*bins*2);
 442         bm->minmax_limitstack[stackctr]=0;
 443         bm->minmax_posstack[stackctr]=-1;
 444
 445       }
 446     }
 447
 448     /* remove from tail */
 449     while(bm->minmax_sampleacc>sampledesired){
 450       int samples=
 451         ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
 452       int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
 453
 454       for(i=0;i<bins;i++){
 455         bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
 456           LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,
 457                                 actual>i?
 458                                 actual:i));
 459         bm->minmax_binstack[i]-=
 460           LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,
 461                                 actual<i?
 462                                 actual:i));
 463       }
 464
 465       /* always perform in this order; max overrules min */
 466       if(bm->minmax_limitstack[0]>actual)
 467         actual=bm->minmax_limitstack[0];
 468       if(bins+bm->minmax_limitstack[0]<actual)
 469         actual=bins+bm->minmax_limitstack[0];
 470
 471       bm->minmax_acctotal-=LACING_ADJUST(BINBYTES(bm,bm->minmax_tail,actual));
 472       bm->minmax_sampleacc-=samples;
 473
 474       /* revise queue_actual to reflect the limit */
 475       bm->queue_actual[bm->minmax_tail]&=0x80000000UL;
 476       bm->queue_actual[bm->minmax_tail]|=actual;
 477
 478       if(bm->minmax_tail==bm->minmax_posstack[0]){
 479         /* the stack becomes a FIFO; the first data has fallen off */
 480         memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
 481                 sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
 482         memmove(bm->minmax_posstack,bm->minmax_posstack+1,
 483                 sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
 484         memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
 485                 sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
 486         bm->minmax_stackptr--;
 487       }
 488
 489       bm->minmax_tail++;
 490       if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
 491     }
 492
 493
 494     bm->last_to_flush=bm->minmax_tail;
 495   }else{
 496     bm->last_to_flush=bm->avg_center;
 497   }
 498   if(eofflag)
 499     bm->last_to_flush=bm->queue_head;
 500   return(0);
 501 }
 502
 503 int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
 504   backend_lookup_state  *b=vd->backend_state;
 505   bitrate_manager_state *bm=&b->bms;
 506
 507   if(bm->queue_size==0){
 508     if(bm->queue_head==0)return(0);
 509
 510     memcpy(op,bm->packets,sizeof(*op));
 511     bm->queue_head=0;
 512
 513   }else{
 514
 515     if(bm->next_to_flush==bm->last_to_flush)return(0);
 516
 517     {
 518       long bin=bm->queue_actual[bm->next_to_flush]&0x7fffffff,i;
 519       long bins=bm->queue_bins;
 520       ogg_uint32_t *markers=bm->queue_binned+bins*bm->next_to_flush;
 521       long bytes=markers[bin];
 522
 523       memcpy(op,bm->packets+bm->next_to_flush,sizeof(*op));
 524
 525       /* we have [PACKETBLOBS] possible packets all squished together in
 526          the buffer, in sequence.  count in to number [bin] */
 527       for(i=0;i<bin;i++)
 528         op->packet+=markers[i];
 529       op->bytes=bytes;
 530
 531     }
 532
 533     bm->next_to_flush++;
 534     if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;
 535
 536   }
 537
 538   return(1);
 539 }