Fix some broken clamping in rate control.
[theora.git] / lib / rate.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggTheora 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 Theora SOURCE CODE IS COPYRIGHT (C) 2002-2009                *
9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13   function:
14   last mod: $Id$
15
16  ********************************************************************/
17 #include <stdlib.h>
18 #include <string.h>
19 #include "encint.h"
20
21 /*A rough lookup table for tan(x), 0<=x<pi/2.
22   The values are Q12 fixed-point and spaced at 5 degree intervals.
23   These decisions are somewhat arbitrary, but sufficient for the 2nd order
24    Bessel follower below.
25   Values of x larger than 85 degrees are extrapolated from the last inteval,
26    which is way off, but "good enough".*/
27 static unsigned short OC_ROUGH_TAN_LOOKUP[18]={
28       0,  358,  722, 1098, 1491, 1910,
29    2365, 2868, 3437, 4096, 4881, 5850,
30    7094, 8784,11254,15286,23230,46817
31 };
32
33 /*_alpha is Q24 in the range [0,0.5).
34   The return values is 5.12.*/
35 static int oc_warp_alpha(int _alpha){
36   int i;
37   int d;
38   int t0;
39   int t1;
40   i=_alpha*36>>24;
41   if(i>=17)i=16;
42   t0=OC_ROUGH_TAN_LOOKUP[i];
43   t1=OC_ROUGH_TAN_LOOKUP[i+1];
44   d=_alpha*36-(i<<24);
45   return (int)(((ogg_int64_t)t0<<32)+(t1-t0<<8)*(ogg_int64_t)d>>32);
46 }
47
48 /*Re-initialize the Bessel filter coefficients with the specified delay.
49   This does not alter the x/y state, but changes the reaction time of the
50    filter.
51   Altering the time constant of a reactive filter without alterning internal
52    state is something that has to be done carefuly, but our design operates at
53    high enough delays and with small enough time constant changes to make it
54    safe.*/
55 static void oc_iir_filter_reinit(oc_iir_filter *_f,int _delay){
56   int         alpha;
57   ogg_int64_t one48;
58   ogg_int64_t warp;
59   ogg_int64_t k1;
60   ogg_int64_t k2;
61   ogg_int64_t d;
62   ogg_int64_t a;
63   ogg_int64_t ik2;
64   ogg_int64_t b1;
65   ogg_int64_t b2;
66   /*This borrows some code from an unreleased version of Postfish.
67     See the recipe at http://unicorn.us.com/alex/2polefilters.html for details
68      on deriving the filter coefficients.*/
69   /*alpha is Q24*/
70   alpha=(1<<24)/_delay;
71   one48=(ogg_int64_t)1<<48;
72   /*warp is 7.12*/
73   warp=OC_MAXI(oc_warp_alpha(alpha),1);
74   /*k1 is 9.12*/
75   k1=3*warp;
76   /*k2 is 16.24.*/
77   k2=k1*warp;
78   /*d is 16.15.*/
79   d=((1<<12)+k1<<12)+k2+256>>9;
80   /*a is 0.32, since d is larger than both 1.0 and k2.*/
81   a=(k2<<23)/d;
82   /*ik2 is 25.24.*/
83   ik2=one48/k2;
84   /*b1 is Q56; in practice, the integer ranges between -2 and 2.*/
85   b1=2*a*(ik2-(1<<24));
86   /*b2 is Q56; in practice, the integer ranges between -2 and 2.*/
87   b2=(one48<<8)-(4*a<<24)-b1;
88   /*All of the filter parameters are Q24.*/
89   _f->c[0]=(ogg_int32_t)(b1+((ogg_int64_t)1<<31)>>32);
90   _f->c[1]=(ogg_int32_t)(b2+((ogg_int64_t)1<<31)>>32);
91   _f->g=(ogg_int32_t)(a+128>>8);
92 }
93
94 /*Initialize a 2nd order low-pass Bessel filter with the corresponding delay
95    and initial value.
96   _value is Q24.*/
97 static void oc_iir_filter_init(oc_iir_filter *_f,int _delay,ogg_int32_t _value){
98   oc_iir_filter_reinit(_f,_delay);
99   _f->y[1]=_f->y[0]=_f->x[1]=_f->x[0]=_value;
100 }
101
102 static ogg_int64_t oc_iir_filter_update(oc_iir_filter *_f,ogg_int32_t _x){
103   ogg_int64_t c0;
104   ogg_int64_t c1;
105   ogg_int64_t g;
106   ogg_int64_t x0;
107   ogg_int64_t x1;
108   ogg_int64_t y0;
109   ogg_int64_t y1;
110   ogg_int64_t ya;
111   c0=_f->c[0];
112   c1=_f->c[1];
113   g=_f->g;
114   x0=_f->x[0];
115   x1=_f->x[1];
116   y0=_f->y[0];
117   y1=_f->y[1];
118   ya=(_x+x0*2+x1)*g+y0*c0+y1*c1+(1<<23)>>24;
119   _f->x[1]=(ogg_int32_t)x0;
120   _f->x[0]=_x;
121   _f->y[1]=(ogg_int32_t)y0;
122   _f->y[0]=(ogg_int32_t)ya;
123   return ya;
124 }
125
126
127
128 /*Search for the quantizer that matches the target most closely.
129   We don't assume a linear ordering, but when there are ties we pick the
130    quantizer closest to the old one.*/
131 static int oc_enc_find_qi_for_target(oc_enc_ctx *_enc,int _qti,int _qi_old,
132  int _qi_min,ogg_int64_t _log_qtarget){
133   ogg_int64_t best_qdiff;
134   int         best_qi;
135   int         qi;
136   best_qi=_qi_min;
137   best_qdiff=_enc->log_qavg[_qti][best_qi]-_log_qtarget;
138   best_qdiff=best_qdiff+OC_SIGNMASK(best_qdiff)^OC_SIGNMASK(best_qdiff);
139   for(qi=_qi_min+1;qi<64;qi++){
140     ogg_int64_t qdiff;
141     qdiff=_enc->log_qavg[_qti][qi]-_log_qtarget;
142     qdiff=qdiff+OC_SIGNMASK(qdiff)^OC_SIGNMASK(qdiff);
143     if(qdiff<best_qdiff||
144      qdiff==best_qdiff&&abs(qi-_qi_old)<abs(best_qi-_qi_old)){
145       best_qi=qi;
146       best_qdiff=qdiff;
147     }
148   }
149   return best_qi;
150 }
151
152 void oc_enc_calc_lambda(oc_enc_ctx *_enc,int _qti){
153   ogg_int64_t lq;
154   int         qi;
155   int         qi1;
156   int         nqis;
157   /*For now, lambda is fixed depending on the qi value and frame type:
158       lambda=qscale*(qavg[qti][qi]**2),
159      where qscale=0.2125.
160     This was derived by exhaustively searching for the optimal quantizer for
161      the AC coefficients in each block from a number of test sequences for a
162      number of fixed lambda values and fitting the peaks of the resulting
163      histograms (on the log(qavg) scale).
164     The same model applies to both inter and intra frames.
165     A more adaptive scheme might perform better.*/
166   qi=_enc->state.qis[0];
167   /*If rate control is active, use the lambda for the _target_ quantizer.
168     This allows us to scale to rates slightly lower than we'd normally be able
169      to reach, and give the rate control a semblance of "fractional qi"
170      precision.
171     TODO: Add API for changing QI, and allow extra precision.*/
172   if(_enc->state.info.target_bitrate>0)lq=_enc->rc.log_qtarget;
173   else lq=_enc->log_qavg[_qti][qi];
174   /*The resulting lambda value is less than 0x500000.*/
175   _enc->lambda=(int)oc_bexp64(2*lq-0x4780BD468D6B62BLL);
176   /*Select additional quantizers.
177     The R-D optimal block AC quantizer statistics suggest that the distribution
178      is roughly Gaussian-like with a slight positive skew.
179     K-means clustering on log_qavg to select 3 quantizers produces cluster
180      centers of {log_qavg-0.6,log_qavg,log_qavg+0.7}.
181     Experiments confirm these are relatively good choices.
182
183     Although we do greedy R-D optimization of the qii flags to avoid switching
184      too frequently, this becomes ineffective at low rates, either because we
185      do a poor job of predicting the actual R-D cost, or the greedy
186      optimization is not sufficient.
187     Therefore adaptive quantization is disabled above an (experimentally
188      suggested) threshold of log_qavg=7.00 (e.g., below INTRA qi=12 or
189      INTER qi=20 with current matrices).
190     This may need to be revised if the R-D cost estimation or qii flag
191      optimization strategies change.*/
192   nqis=1;
193   if(lq<(OC_Q57(56)>>3)&&!_enc->vp3_compatible&&
194    _enc->sp_level<OC_SP_LEVEL_FAST_ANALYSIS){
195     qi1=oc_enc_find_qi_for_target(_enc,_qti,OC_MAXI(qi-1,0),0,
196      lq+(OC_Q57(7)+5)/10);
197     if(qi1!=qi)_enc->state.qis[nqis++]=qi1;
198     qi1=oc_enc_find_qi_for_target(_enc,_qti,OC_MINI(qi+1,63),0,
199      lq-(OC_Q57(6)+5)/10);
200     if(qi1!=qi&&qi1!=_enc->state.qis[nqis-1])_enc->state.qis[nqis++]=qi1;
201   }
202   _enc->state.nqis=nqis;
203 }
204
205 /*Binary exponential of _log_scale with 24-bit fractional precision and
206    saturation.
207   _log_scale: A binary logarithm in Q24 format.
208   Return: The binary exponential in Q24 format, saturated to 2**47-1 if
209    _log_scale was too large.*/
210 static ogg_int64_t oc_bexp_q24(ogg_int32_t _log_scale){
211   if(_log_scale<(ogg_int32_t)23<<24){
212     ogg_int64_t ret;
213     ret=oc_bexp64(((ogg_int64_t)_log_scale<<33)+OC_Q57(24));
214     return ret<0x7FFFFFFFFFFFLL?ret:0x7FFFFFFFFFFFLL;
215   }
216   return 0x7FFFFFFFFFFFLL;
217 }
218
219 /*Convenience function converts Q57 value to a clamped 32-bit Q24 value
220   _in: input in Q57 format.
221   Return: same number in Q24 */
222 static ogg_int32_t oc_q57_to_q24(ogg_int64_t _in){
223   ogg_int64_t ret;
224   ret=_in+((ogg_int64_t)1<<32)>>33;
225   /*0x80000000 is automatically converted to unsigned on 32-bit systems.
226     -0x7FFFFFFF-1 is needed to avoid "promoting" the whole expression to
227     unsigned.*/
228   return (ogg_int32_t)OC_CLAMPI(-0x7FFFFFFF-1,ret,0x7FFFFFFF);
229 }
230
231 /*Binary exponential of _log_scale with 24-bit fractional precision and
232    saturation.
233   _log_scale: A binary logarithm in Q57 format.
234   Return: The binary exponential in Q24 format, saturated to 2**31-1 if
235    _log_scale was too large.*/
236 static ogg_int32_t oc_bexp64_q24(ogg_int64_t _log_scale){
237   if(_log_scale<OC_Q57(8)){
238     ogg_int64_t ret;
239     ret=oc_bexp64(_log_scale+OC_Q57(24));
240     return ret<0x7FFFFFFF?(ogg_int32_t)ret:0x7FFFFFFF;
241   }
242   return 0x7FFFFFFF;
243 }
244
245
246 static void oc_enc_rc_reset(oc_enc_ctx *_enc){
247   ogg_int64_t npixels;
248   ogg_int64_t ibpp;
249   int         inter_delay;
250   /*TODO: These parameters should be exposed in a th_encode_ctl() API.*/
251   _enc->rc.bits_per_frame=(_enc->state.info.target_bitrate*
252    (ogg_int64_t)_enc->state.info.fps_denominator)/
253    _enc->state.info.fps_numerator;
254   /*Insane framerates or frame sizes mean insane bitrates.
255     Let's not get carried away.*/
256   if(_enc->rc.bits_per_frame>0x400000000000LL){
257     _enc->rc.bits_per_frame=(ogg_int64_t)0x400000000000LL;
258   }
259   else if(_enc->rc.bits_per_frame<32)_enc->rc.bits_per_frame=32;
260   _enc->rc.buf_delay=OC_MAXI(_enc->rc.buf_delay,12);
261   _enc->rc.max=_enc->rc.bits_per_frame*_enc->rc.buf_delay;
262   /*Start with a buffer fullness of 50% plus 25% of the amount we plan to spend
263      on a single keyframe interval.
264     We can require fully half the bits in an interval for a keyframe, so this
265      initial level gives us maximum flexibility for over/under-shooting in
266      subsequent frames.*/
267   _enc->rc.target=(_enc->rc.max+1>>1)+(_enc->rc.bits_per_frame+2>>2)*
268    OC_MINI(_enc->keyframe_frequency_force,_enc->rc.buf_delay);
269   _enc->rc.fullness=_enc->rc.target;
270   /*Pick exponents and initial scales for quantizer selection.*/
271   npixels=_enc->state.info.frame_width*
272    (ogg_int64_t)_enc->state.info.frame_height;
273   _enc->rc.log_npixels=oc_blog64(npixels);
274   ibpp=npixels/_enc->rc.bits_per_frame;
275   if(ibpp<1){
276     _enc->rc.exp[0]=59;
277     _enc->rc.log_scale[0]=oc_blog64(1997)-OC_Q57(8);
278   }
279   else if(ibpp<2){
280     _enc->rc.exp[0]=55;
281     _enc->rc.log_scale[0]=oc_blog64(1604)-OC_Q57(8);
282   }
283   else{
284     _enc->rc.exp[0]=48;
285     _enc->rc.log_scale[0]=oc_blog64(834)-OC_Q57(8);
286   }
287   if(ibpp<4){
288     _enc->rc.exp[1]=100;
289     _enc->rc.log_scale[1]=oc_blog64(2249)-OC_Q57(8);
290   }
291   else if(ibpp<8){
292     _enc->rc.exp[1]=95;
293     _enc->rc.log_scale[1]=oc_blog64(1751)-OC_Q57(8);
294   }
295   else{
296     _enc->rc.exp[1]=73;
297     _enc->rc.log_scale[1]=oc_blog64(1260)-OC_Q57(8);
298   }
299   _enc->rc.prev_drop_count=0;
300   _enc->rc.log_drop_scale=OC_Q57(0);
301   /*Set up second order followers, initialized according to corresponding
302      time constants.*/
303   oc_iir_filter_init(&_enc->rc.scalefilter[0],4,
304    oc_q57_to_q24(_enc->rc.log_scale[0]));
305   inter_delay=(_enc->rc.twopass?
306    OC_MAXI(_enc->keyframe_frequency_force,12):_enc->rc.buf_delay)>>1;
307   _enc->rc.inter_count=0;
308   /*We clamp the actual inter_delay to a minimum of 10 to work within the range
309      of values where later incrementing the delay works as designed.
310     10 is not an exact choice, but rather a good working trade-off.*/
311   _enc->rc.inter_delay=10;
312   _enc->rc.inter_delay_target=inter_delay;
313   oc_iir_filter_init(&_enc->rc.scalefilter[1],_enc->rc.inter_delay,
314    oc_q57_to_q24(_enc->rc.log_scale[1]));
315   oc_iir_filter_init(&_enc->rc.vfrfilter,4,
316    oc_bexp64_q24(_enc->rc.log_drop_scale));
317 }
318
319 void oc_rc_state_init(oc_rc_state *_rc,oc_enc_ctx *_enc){
320   _rc->twopass=0;
321   _rc->twopass_buffer_bytes=0;
322   _rc->twopass_force_kf=0;
323   _rc->frame_metrics=NULL;
324   _rc->rate_bias=0;
325   if(_enc->state.info.target_bitrate>0){
326     /*The buffer size is set equal to the keyframe interval, clamped to the
327        range [12,256] frames.
328       The 12 frame minimum gives us some chance to distribute bit estimation
329        errors.
330       The 256 frame maximum means we'll require 8-10 seconds of pre-buffering
331        at 24-30 fps, which is not unreasonable.*/
332     _rc->buf_delay=_enc->keyframe_frequency_force>256?
333      256:_enc->keyframe_frequency_force;
334     /*By default, enforce all buffer constraints.*/
335     _rc->drop_frames=1;
336     _rc->cap_overflow=1;
337     _rc->cap_underflow=0;
338     oc_enc_rc_reset(_enc);
339   }
340 }
341
342 void oc_rc_state_clear(oc_rc_state *_rc){
343   _ogg_free(_rc->frame_metrics);
344 }
345
346 void oc_enc_rc_resize(oc_enc_ctx *_enc){
347   /*If encoding has not yet begun, reset the buffer state.*/
348   if(_enc->state.curframe_num<0)oc_enc_rc_reset(_enc);
349   else{
350     int idt;
351     /*Otherwise, update the bounds on the buffer, but not the current
352        fullness.*/
353     _enc->rc.bits_per_frame=(_enc->state.info.target_bitrate*
354      (ogg_int64_t)_enc->state.info.fps_denominator)/
355      _enc->state.info.fps_numerator;
356     /*Insane framerates or frame sizes mean insane bitrates.
357       Let's not get carried away.*/
358     if(_enc->rc.bits_per_frame>0x400000000000LL){
359       _enc->rc.bits_per_frame=(ogg_int64_t)0x400000000000LL;
360     }
361     else if(_enc->rc.bits_per_frame<32)_enc->rc.bits_per_frame=32;
362     _enc->rc.buf_delay=OC_MAXI(_enc->rc.buf_delay,12);
363     _enc->rc.max=_enc->rc.bits_per_frame*_enc->rc.buf_delay;
364     _enc->rc.target=(_enc->rc.max+1>>1)+(_enc->rc.bits_per_frame+2>>2)*
365      OC_MINI(_enc->keyframe_frequency_force,_enc->rc.buf_delay);
366     /*Update the INTER-frame scale filter delay.
367       We jump to it immediately if we've already seen enough frames; otherwise
368        it is simply set as the new target.*/
369     _enc->rc.inter_delay_target=idt=OC_MAXI(_enc->rc.buf_delay>>1,10);
370     if(idt<OC_MINI(_enc->rc.inter_delay,_enc->rc.inter_count)){
371       oc_iir_filter_init(&_enc->rc.scalefilter[1],idt,
372        _enc->rc.scalefilter[1].y[0]);
373       _enc->rc.inter_delay=idt;
374     }
375   }
376   /*If we're in pass-2 mode, make sure the frame metrics array is big enough
377      to hold frame statistics for the full buffer.*/
378   if(_enc->rc.twopass==2){
379     int cfm;
380     int buf_delay;
381     int reset_window;
382     buf_delay=_enc->rc.buf_delay;
383     reset_window=_enc->rc.frame_metrics==NULL&&(_enc->rc.frames_total[0]==0||
384      buf_delay<_enc->rc.frames_total[0]+_enc->rc.frames_total[1]
385      +_enc->rc.frames_total[2]);
386     cfm=_enc->rc.cframe_metrics;
387     /*Only try to resize the frame metrics buffer if a) it's too small and
388        b) we were using a finite buffer, or are about to start.*/
389     if(cfm<buf_delay&&(_enc->rc.frame_metrics!=NULL||reset_window)){
390       oc_frame_metrics *fm;
391       int               nfm;
392       int               fmh;
393       fm=(oc_frame_metrics *)_ogg_realloc(_enc->rc.frame_metrics,
394        buf_delay*sizeof(*_enc->rc.frame_metrics));
395       if(fm==NULL){
396         /*We failed to allocate a finite buffer.*/
397         /*If we don't have a valid 2-pass header yet, just return; we'll reset
398            the buffer size when we read the header.*/
399         if(_enc->rc.frames_total[0]==0)return;
400         /*Otherwise revert to the largest finite buffer previously set, or to
401            whole-file buffering if we were still using that.*/
402         _enc->rc.buf_delay=_enc->rc.frame_metrics!=NULL?
403          cfm:_enc->rc.frames_total[0]+_enc->rc.frames_total[1]
404          +_enc->rc.frames_total[2];
405         oc_enc_rc_resize(_enc);
406         return;
407       }
408       _enc->rc.frame_metrics=fm;
409       _enc->rc.cframe_metrics=buf_delay;
410       /*Re-organize the circular buffer.*/
411       fmh=_enc->rc.frame_metrics_head;
412       nfm=_enc->rc.nframe_metrics;
413       if(fmh+nfm>cfm){
414         int shift;
415         shift=OC_MINI(fmh+nfm-cfm,buf_delay-cfm);
416         memcpy(fm+cfm,fm,OC_MINI(fmh+nfm-cfm,buf_delay-cfm)*sizeof(*fm));
417         if(fmh+nfm>buf_delay)memmove(fm,fm+shift,fmh+nfm-buf_delay);
418       }
419     }
420     /*We were using whole-file buffering; now we're not.*/
421     if(reset_window){
422       _enc->rc.nframes[0]=_enc->rc.nframes[1]=_enc->rc.nframes[2]=0;
423       _enc->rc.scale_sum[0]=_enc->rc.scale_sum[1]=0;
424       _enc->rc.scale_window_end=_enc->rc.scale_window0=
425        _enc->state.curframe_num+_enc->prev_dup_count+1;
426       if(_enc->rc.twopass_buffer_bytes){
427         int qti;
428         /*We already read the metrics for the first frame in the window.*/
429         *(_enc->rc.frame_metrics)=*&_enc->rc.cur_metrics;
430         _enc->rc.nframe_metrics++;
431         qti=_enc->rc.cur_metrics.frame_type;
432         _enc->rc.nframes[qti]++;
433         _enc->rc.nframes[2]+=_enc->rc.cur_metrics.dup_count;
434         _enc->rc.scale_sum[qti]+=oc_bexp_q24(_enc->rc.cur_metrics.log_scale);
435         _enc->rc.scale_window_end+=_enc->rc.cur_metrics.dup_count+1;
436         if(_enc->rc.scale_window_end-_enc->rc.scale_window0<buf_delay){
437           /*We need more frame data.*/
438           _enc->rc.twopass_buffer_bytes=0;
439         }
440       }
441     }
442     /*Otherwise, we could shrink the size of the current window, if necessary,
443        but leaving it like it is lets us adapt to the new buffer size more
444        gracefully.*/
445   }
446 }
447
448 /*Scale the number of frames by the number of expected drops/duplicates.*/
449 static int oc_rc_scale_drop(oc_rc_state *_rc,int _nframes){
450   if(_rc->prev_drop_count>0||_rc->log_drop_scale>OC_Q57(0)){
451     ogg_int64_t dup_scale;
452     dup_scale=oc_bexp64((_rc->log_drop_scale
453      +oc_blog64(_rc->prev_drop_count+1)>>1)+OC_Q57(8));
454     if(dup_scale<_nframes<<8){
455       int dup_scalei;
456       dup_scalei=(int)dup_scale;
457       if(dup_scalei>0)_nframes=((_nframes<<8)+dup_scalei-1)/dup_scalei;
458     }
459     else _nframes=!!_nframes;
460   }
461   return _nframes;
462 }
463
464 int oc_enc_select_qi(oc_enc_ctx *_enc,int _qti,int _clamp){
465   ogg_int64_t  rate_total;
466   ogg_int64_t  rate_bias;
467   int          nframes[2];
468   int          buf_delay;
469   int          buf_pad;
470   ogg_int64_t  log_qtarget;
471   ogg_int64_t  log_scale0;
472   ogg_int64_t  log_cur_scale;
473   ogg_int64_t  log_qexp;
474   int          exp0;
475   int          old_qi;
476   int          qi;
477   /*Figure out how to re-distribute bits so that we hit our fullness target
478      before the last keyframe in our current buffer window (after the current
479      frame), or the end of the buffer window, whichever comes first.*/
480   log_cur_scale=(ogg_int64_t)_enc->rc.scalefilter[_qti].y[0]<<33;
481   buf_pad=0;
482   switch(_enc->rc.twopass){
483     default:{
484       ogg_uint32_t next_key_frame;
485       /*Single pass mode: assume only forced keyframes and attempt to estimate
486          the drop count for VFR content.*/
487       next_key_frame=_qti?_enc->keyframe_frequency_force
488        -(_enc->state.curframe_num-_enc->state.keyframe_num):0;
489       nframes[0]=(_enc->rc.buf_delay-OC_MINI(next_key_frame,_enc->rc.buf_delay)
490        +_enc->keyframe_frequency_force-1)/_enc->keyframe_frequency_force;
491       if(nframes[0]+_qti>1){
492         nframes[0]--;
493         buf_delay=next_key_frame+nframes[0]*_enc->keyframe_frequency_force;
494       }
495       else buf_delay=_enc->rc.buf_delay;
496       nframes[1]=buf_delay-nframes[0];
497       /*Downgrade the delta frame rate to correspond to the recent drop count
498          history.*/
499       nframes[1]=oc_rc_scale_drop(&_enc->rc,nframes[1]);
500     }break;
501     case 1:{
502       /*Pass 1 mode: use a fixed qi value.*/
503       qi=_enc->state.qis[0];
504       _enc->rc.log_qtarget=_enc->log_qavg[_qti][qi];
505       return qi;
506     }break;
507     case 2:{
508       ogg_int64_t scale_sum[2];
509       int         qti;
510       /*Pass 2 mode: we know exactly how much of each frame type there is in
511          the current buffer window, and have estimates for the scales.*/
512       nframes[0]=_enc->rc.nframes[0];
513       nframes[1]=_enc->rc.nframes[1];
514       scale_sum[0]=_enc->rc.scale_sum[0];
515       scale_sum[1]=_enc->rc.scale_sum[1];
516       /*The window size can be slightly larger than the buffer window for VFR
517          content; clamp it down, if appropriate (the excess will all be dup
518          frames).*/
519       buf_delay=OC_MINI(_enc->rc.scale_window_end-_enc->rc.scale_window0,
520        _enc->rc.buf_delay);
521       /*If we're approaching the end of the file, add some slack to keep us
522          from slamming into a rail.
523         Our rate accuracy goes down, but it keeps the result sensible.
524         We position the target where the first forced keyframe beyond the end
525          of the file would be (for consistency with 1-pass mode).*/
526       buf_pad=OC_MINI(_enc->rc.buf_delay,_enc->state.keyframe_num
527        +_enc->keyframe_frequency_force-_enc->rc.scale_window0);
528       if(buf_delay<buf_pad)buf_pad-=buf_delay;
529       else{
530         /*Otherwise, search for the last keyframe in the buffer window and
531            target that.*/
532         buf_pad=0;
533         /*TODO: Currently we only do this when using a finite buffer; we could
534            save the position of the last keyframe in the summary data and do it
535            with a whole-file buffer as well, but it isn't likely to make a
536            difference.*/
537         if(_enc->rc.frame_metrics!=NULL){
538           int fmi;
539           int fm_tail;
540           fm_tail=_enc->rc.frame_metrics_head+_enc->rc.nframe_metrics;
541           if(fm_tail>=_enc->rc.cframe_metrics)fm_tail-=_enc->rc.cframe_metrics;
542           for(fmi=fm_tail;;){
543             oc_frame_metrics *m;
544             fmi--;
545             if(fmi<0)fmi+=_enc->rc.cframe_metrics;
546             /*Stop before we remove the first frame.*/
547             if(fmi==_enc->rc.frame_metrics_head)break;
548             m=_enc->rc.frame_metrics+fmi;
549             /*If we find a keyframe, remove it and everything past it.*/
550             if(m->frame_type==OC_INTRA_FRAME){
551               do{
552                 qti=m->frame_type;
553                 nframes[qti]--;
554                 scale_sum[qti]-=oc_bexp_q24(m->log_scale);
555                 buf_delay-=m->dup_count+1;
556                 fmi++;
557                 if(fmi>=_enc->rc.cframe_metrics)fmi=0;
558                 m=_enc->rc.frame_metrics+fmi;
559               }
560               while(fmi!=fm_tail);
561               /*And stop scanning backwards.*/
562               break;
563             }
564           }
565         }
566       }
567       /*If we're not using the same frame type as in pass 1 (because someone
568          changed the keyframe interval), remove that scale estimate.
569         We'll add in a replacement for the correct frame type below.*/
570       qti=_enc->rc.cur_metrics.frame_type;
571       if(qti!=_qti){
572         nframes[qti]--;
573         scale_sum[qti]-=oc_bexp_q24(_enc->rc.cur_metrics.log_scale);
574       }
575       /*Compute log_scale estimates for each frame type from the pass-1 scales
576          we measured in the current window.*/
577       for(qti=0;qti<2;qti++){
578         _enc->rc.log_scale[qti]=nframes[qti]>0?
579          oc_blog64(scale_sum[qti])-oc_blog64(nframes[qti])-OC_Q57(24):
580          -_enc->rc.log_npixels;
581       }
582       /*If we're not using the same frame type as in pass 1, add a scale
583          estimate for the corresponding frame using the current low-pass
584          filter value.
585         This is mostly to ensure we have a valid estimate even when pass 1 had
586          no frames of this type in the buffer window.
587         TODO: We could also plan ahead and figure out how many keyframes we'll
588          be forced to add in the current buffer window.*/
589       qti=_enc->rc.cur_metrics.frame_type;
590       if(qti!=_qti){
591         ogg_int64_t scale;
592         scale=_enc->rc.log_scale[_qti]<OC_Q57(23)?
593          oc_bexp64(_enc->rc.log_scale[_qti]+OC_Q57(24)):0x7FFFFFFFFFFFLL;
594         scale*=nframes[_qti];
595         nframes[_qti]++;
596         scale+=oc_bexp_q24(log_cur_scale>>33);
597         _enc->rc.log_scale[_qti]=oc_blog64(scale)
598          -oc_blog64(nframes[qti])-OC_Q57(24);
599       }
600       else log_cur_scale=(ogg_int64_t)_enc->rc.cur_metrics.log_scale<<33;
601       /*Add the padding from above.
602         This basically reverts to 1-pass estimations in the last keyframe
603          interval.*/
604       if(buf_pad>0){
605         ogg_int64_t scale;
606         int         nextra_frames;
607         /*Extend the buffer.*/
608         buf_delay+=buf_pad;
609         /*Add virtual delta frames according to the estimated drop count.*/
610         nextra_frames=oc_rc_scale_drop(&_enc->rc,buf_pad);
611         /*And blend in the low-pass filtered scale according to how many frames
612            we added.*/
613         scale=
614          oc_bexp64(_enc->rc.log_scale[1]+OC_Q57(24))*(ogg_int64_t)nframes[1]
615          +oc_bexp_q24(_enc->rc.scalefilter[1].y[0])*(ogg_int64_t)nextra_frames;
616         nframes[1]+=nextra_frames;
617         _enc->rc.log_scale[1]=oc_blog64(scale)-oc_blog64(nframes[1])-OC_Q57(24);
618       }
619     }break;
620   }
621   /*If we've been missing our target, add a penalty term.*/
622   rate_bias=(_enc->rc.rate_bias/(_enc->state.curframe_num+1000))*
623    (buf_delay-buf_pad);
624   /*rate_total is the total bits available over the next buf_delay frames.*/
625   rate_total=_enc->rc.fullness-_enc->rc.target+rate_bias
626    +buf_delay*_enc->rc.bits_per_frame;
627   log_scale0=_enc->rc.log_scale[_qti]+_enc->rc.log_npixels;
628   /*If there aren't enough bits to achieve our desired fullness level, use the
629      minimum quality permitted.*/
630   if(rate_total<=buf_delay)log_qtarget=OC_QUANT_MAX_LOG;
631   else{
632     static const ogg_int64_t LOG_KEY_RATIO=0x0137222BB70747BALL;
633     ogg_int64_t log_scale1;
634     ogg_int64_t rlo;
635     ogg_int64_t rhi;
636     log_scale1=_enc->rc.log_scale[1-_qti]+_enc->rc.log_npixels;
637     rlo=0;
638     rhi=(rate_total+nframes[_qti]-1)/nframes[_qti];
639     while(rlo<rhi){
640       ogg_int64_t curr;
641       ogg_int64_t rdiff;
642       ogg_int64_t log_rpow;
643       ogg_int64_t rscale;
644       curr=rlo+rhi>>1;
645       log_rpow=oc_blog64(curr)-log_scale0;
646       log_rpow=(log_rpow+(_enc->rc.exp[_qti]>>1))/_enc->rc.exp[_qti];
647       if(_qti)log_rpow+=LOG_KEY_RATIO>>6;
648       else log_rpow-=LOG_KEY_RATIO>>6;
649       log_rpow*=_enc->rc.exp[1-_qti];
650       rscale=nframes[1-_qti]*oc_bexp64(log_scale1+log_rpow);
651       rdiff=nframes[_qti]*curr+rscale-rate_total;
652       if(rdiff<0)rlo=curr+1;
653       else if(rdiff>0)rhi=curr-1;
654       else break;
655     }
656     log_qtarget=OC_Q57(2)-((oc_blog64(rlo)-log_scale0+(_enc->rc.exp[_qti]>>1))/
657      _enc->rc.exp[_qti]<<6);
658     log_qtarget=OC_MINI(log_qtarget,OC_QUANT_MAX_LOG);
659   }
660   /*The above allocation looks only at the total rate we'll accumulate in the
661      next buf_delay frames.
662     However, we could overflow the buffer on the very next frame, so check for
663      that here, if we're not using a soft target.*/
664   exp0=_enc->rc.exp[_qti];
665   if(_enc->rc.cap_overflow){
666     ogg_int64_t margin;
667     ogg_int64_t soft_limit;
668     ogg_int64_t log_soft_limit;
669     /*Allow 3% of the buffer for prediction error.
670       This should be plenty, and we don't mind if we go a bit over; we only
671        want to keep these bits from being completely wasted.*/
672     margin=_enc->rc.max+31>>5;
673     /*We want to use at least this many bits next frame.*/
674     soft_limit=_enc->rc.fullness+_enc->rc.bits_per_frame-(_enc->rc.max-margin);
675     log_soft_limit=oc_blog64(soft_limit);
676     /*If we're predicting we won't use that many...*/
677     log_qexp=(log_qtarget-OC_Q57(2)>>6)*exp0;
678     if(log_scale0-log_qexp<log_soft_limit){
679       /*Scale the adjustment based on how far into the margin we are.*/
680       log_qexp+=(log_scale0-log_soft_limit-log_qexp>>32)*
681        ((OC_MINI(margin,soft_limit)<<32)/margin);
682       log_qtarget=((log_qexp+(exp0>>1))/exp0<<6)+OC_Q57(2);
683     }
684   }
685   /*If this was not one of the initial frames, limit the change in quality.*/
686   old_qi=_enc->state.qis[0];
687   if(_clamp){
688     ogg_int64_t log_qmin;
689     ogg_int64_t log_qmax;
690     /*Clamp the target quantizer to within [0.8*Q,1.2*Q], where Q is the
691        current quantizer.
692       TODO: With user-specified quant matrices, we need to enlarge these limits
693        if they don't actually let us change qi values.*/
694     log_qmin=_enc->log_qavg[_qti][old_qi]-0x00A4D3C25E68DC58LL;
695     log_qmax=_enc->log_qavg[_qti][old_qi]+0x00A4D3C25E68DC58LL;
696     log_qtarget=OC_CLAMPI(log_qmin,log_qtarget,log_qmax);
697   }
698   /*The above allocation looks only at the total rate we'll accumulate in the
699      next buf_delay frames.
700     However, we could bust the budget on the very next frame, so check for that
701      here, if we're not using a soft target.*/
702   /* Disabled when our minimum qi > 0; if we saturate log_qtarget to
703      to the maximum possible size when we have a minimum qi, the
704      resulting lambda will interact very strangely with SKIP.  The
705      resulting artifacts look like waterfalls. */
706   if(_enc->state.info.quality==0){
707     ogg_int64_t log_hard_limit;
708     /*Compute the maximum number of bits we can use in the next frame.
709       Allow 50% of the rate for a single frame for prediction error.
710       This may not be enough for keyframes or sudden changes in complexity.*/
711     log_hard_limit=oc_blog64(_enc->rc.fullness+(_enc->rc.bits_per_frame>>1));
712     /*If we're predicting we'll use more than this...*/
713     log_qexp=(log_qtarget-OC_Q57(2)>>6)*exp0;
714     if(log_scale0-log_qexp>log_hard_limit){
715       /*Force the target to hit our limit exactly.*/
716       log_qexp=log_scale0-log_hard_limit;
717       log_qtarget=((log_qexp+(exp0>>1))/exp0<<6)+OC_Q57(2);
718       /*If that target is unreasonable, oh well; we'll have to drop.*/
719       log_qtarget=OC_MINI(log_qtarget,OC_QUANT_MAX_LOG);
720     }
721   }
722   /*Compute a final estimate of the number of bits we plan to use.*/
723   log_qexp=(log_qtarget-OC_Q57(2)>>6)*_enc->rc.exp[_qti];
724   _enc->rc.rate_bias+=oc_bexp64(log_cur_scale+_enc->rc.log_npixels-log_qexp);
725   qi=oc_enc_find_qi_for_target(_enc,_qti,old_qi,
726    _enc->state.info.quality,log_qtarget);
727   /*Save the quantizer target for lambda calculations.*/
728   _enc->rc.log_qtarget=log_qtarget;
729   return qi;
730 }
731
732 int oc_enc_update_rc_state(oc_enc_ctx *_enc,
733  long _bits,int _qti,int _qi,int _trial,int _droppable){
734   ogg_int64_t buf_delta;
735   ogg_int64_t log_scale;
736   int         dropped;
737   dropped=0;
738   /* Drop frames also disabled for now in the case of infinite-buffer
739      two-pass mode */
740   if(!_enc->rc.drop_frames||_enc->rc.twopass&&_enc->rc.frame_metrics==NULL){
741     _droppable=0;
742   }
743   buf_delta=_enc->rc.bits_per_frame*(1+_enc->dup_count);
744   if(_bits<=0){
745     /*We didn't code any blocks in this frame.*/
746     log_scale=OC_Q57(-64);
747     _bits=0;
748   }
749   else{
750     ogg_int64_t log_bits;
751     ogg_int64_t log_qexp;
752     /*Compute the estimated scale factor for this frame type.*/
753     log_bits=oc_blog64(_bits);
754     log_qexp=_enc->rc.log_qtarget-OC_Q57(2);
755     log_qexp=(log_qexp>>6)*(_enc->rc.exp[_qti]);
756     log_scale=OC_MINI(log_bits-_enc->rc.log_npixels+log_qexp,OC_Q57(16));
757   }
758   /*Special two-pass processing.*/
759   switch(_enc->rc.twopass){
760     case 1:{
761       /*Pass 1 mode: save the metrics for this frame.*/
762       _enc->rc.cur_metrics.log_scale=oc_q57_to_q24(log_scale);
763       _enc->rc.cur_metrics.dup_count=_enc->dup_count;
764       _enc->rc.cur_metrics.frame_type=_enc->state.frame_type;
765       _enc->rc.cur_metrics.activity_avg=_enc->activity_avg;
766       _enc->rc.twopass_buffer_bytes=0;
767     }break;
768     case 2:{
769       /*Pass 2 mode:*/
770       if(!_trial){
771         ogg_int64_t next_frame_num;
772         int         qti;
773         /*Move the current metrics back one frame.*/
774         *&_enc->rc.prev_metrics=*&_enc->rc.cur_metrics;
775         next_frame_num=_enc->state.curframe_num+_enc->dup_count+1;
776         /*Back out the last frame's statistics from the sliding window.*/
777         qti=_enc->rc.prev_metrics.frame_type;
778         _enc->rc.frames_left[qti]--;
779         _enc->rc.frames_left[2]-=_enc->rc.prev_metrics.dup_count;
780         _enc->rc.nframes[qti]--;
781         _enc->rc.nframes[2]-=_enc->rc.prev_metrics.dup_count;
782         _enc->rc.scale_sum[qti]-=oc_bexp_q24(_enc->rc.prev_metrics.log_scale);
783         _enc->rc.scale_window0=(int)next_frame_num;
784         /*Free the corresponding entry in the circular buffer.*/
785         if(_enc->rc.frame_metrics!=NULL){
786           _enc->rc.nframe_metrics--;
787           _enc->rc.frame_metrics_head++;
788           if(_enc->rc.frame_metrics_head>=_enc->rc.cframe_metrics){
789             _enc->rc.frame_metrics_head=0;
790           }
791         }
792         /*Mark us ready for the next 2-pass packet.*/
793         _enc->rc.twopass_buffer_bytes=0;
794         /*Update state, so the user doesn't have to keep calling 2pass_in after
795            they've fed in all the data when we're using a finite buffer.*/
796         _enc->prev_dup_count=_enc->dup_count;
797         oc_enc_rc_2pass_in(_enc,NULL,0);
798       }
799     }break;
800   }
801   /*Common to all passes:*/
802   if(_bits>0){
803     if(_trial){
804       oc_iir_filter *f;
805       /*Use the estimated scale factor directly if this was a trial.*/
806       f=_enc->rc.scalefilter+_qti;
807       f->y[1]=f->y[0]=f->x[1]=f->x[0]=oc_q57_to_q24(log_scale);
808       _enc->rc.log_scale[_qti]=log_scale;
809     }
810     else{
811       /*Lengthen the time constant for the INTER filter as we collect more
812          frame statistics, until we reach our target.*/
813       if(_enc->rc.inter_delay<_enc->rc.inter_delay_target&&
814        _enc->rc.inter_count>=_enc->rc.inter_delay&&_qti==OC_INTER_FRAME){
815         oc_iir_filter_reinit(&_enc->rc.scalefilter[1],++_enc->rc.inter_delay);
816       }
817       /*Otherwise update the low-pass scale filter for this frame type,
818          regardless of whether or not we dropped this frame.*/
819       _enc->rc.log_scale[_qti]=oc_iir_filter_update(
820        _enc->rc.scalefilter+_qti,oc_q57_to_q24(log_scale))<<33;
821       /*If this frame busts our budget, it must be dropped.*/
822       if(_droppable&&_enc->rc.fullness+buf_delta<_bits){
823         _enc->rc.prev_drop_count+=1+_enc->dup_count;
824         _bits=0;
825         dropped=1;
826       }
827       else{
828         ogg_uint32_t drop_count;
829         /*Update a low-pass filter to estimate the "real" frame rate taking
830            drops and duplicates into account.
831           This is only done if the frame is coded, as it needs the final
832            count of dropped frames.*/
833         drop_count=_enc->rc.prev_drop_count+1;
834         if(drop_count>0x7F)drop_count=0x7FFFFFFF;
835         else drop_count<<=24;
836         _enc->rc.log_drop_scale=oc_blog64(oc_iir_filter_update(
837          &_enc->rc.vfrfilter,drop_count))-OC_Q57(24);
838         /*Initialize the drop count for this frame to the user-requested dup
839            count.
840           It will be increased if we drop more frames.*/
841         _enc->rc.prev_drop_count=_enc->dup_count;
842       }
843     }
844     /*Increment the INTER frame count, for filter adaptation purposes.*/
845     if(_enc->rc.inter_count<INT_MAX)_enc->rc.inter_count+=_qti;
846   }
847   /*Increase the drop count.*/
848   else _enc->rc.prev_drop_count+=1+_enc->dup_count;
849   /*And update the buffer fullness level.*/
850   if(!_trial){
851     _enc->rc.fullness+=buf_delta-_bits;
852     /*If we're too quick filling the buffer and overflow is capped,
853       that rate is lost forever.*/
854     if(_enc->rc.cap_overflow&&_enc->rc.fullness>_enc->rc.max){
855       _enc->rc.fullness=_enc->rc.max;
856     }
857     /*If we're too quick draining the buffer and underflow is capped,
858       don't try to make up that rate later.*/
859     if(_enc->rc.cap_underflow&&_enc->rc.fullness<0){
860       _enc->rc.fullness=0;
861     }
862     /*Adjust the bias for the real bits we've used.*/
863     _enc->rc.rate_bias-=_bits;
864   }
865   return dropped;
866 }
867
868 #define OC_RC_2PASS_VERSION   (2)
869 #define OC_RC_2PASS_HDR_SZ    (38)
870 #define OC_RC_2PASS_PACKET_SZ (12)
871
872 static void oc_rc_buffer_val(oc_rc_state *_rc,ogg_int64_t _val,int _bytes){
873   while(_bytes-->0){
874     _rc->twopass_buffer[_rc->twopass_buffer_bytes++]=(unsigned char)(_val&0xFF);
875     _val>>=8;
876   }
877 }
878
879 int oc_enc_rc_2pass_out(oc_enc_ctx *_enc,unsigned char **_buf){
880   if(_enc->rc.twopass_buffer_bytes==0){
881     if(_enc->rc.twopass==0){
882       int qi;
883       /*Pick first-pass qi for scale calculations.*/
884       qi=oc_enc_select_qi(_enc,0,0);
885       _enc->state.nqis=1;
886       _enc->state.qis[0]=qi;
887       _enc->rc.twopass=1;
888       _enc->rc.frames_total[0]=_enc->rc.frames_total[1]=
889        _enc->rc.frames_total[2]=0;
890       _enc->rc.scale_sum[0]=_enc->rc.scale_sum[1]=0;
891       /*Fill in dummy summary values.*/
892       oc_rc_buffer_val(&_enc->rc,0x5032544F,4);
893       oc_rc_buffer_val(&_enc->rc,OC_RC_2PASS_VERSION,4);
894       oc_rc_buffer_val(&_enc->rc,0,OC_RC_2PASS_HDR_SZ-8);
895     }
896     else{
897       int qti;
898       qti=_enc->rc.cur_metrics.frame_type;
899       _enc->rc.scale_sum[qti]+=oc_bexp_q24(_enc->rc.cur_metrics.log_scale);
900       _enc->rc.frames_total[qti]++;
901       _enc->rc.frames_total[2]+=_enc->rc.cur_metrics.dup_count;
902       oc_rc_buffer_val(&_enc->rc,
903        _enc->rc.cur_metrics.dup_count|_enc->rc.cur_metrics.frame_type<<31,4);
904       oc_rc_buffer_val(&_enc->rc,_enc->rc.cur_metrics.log_scale,4);
905       oc_rc_buffer_val(&_enc->rc,_enc->rc.cur_metrics.activity_avg,4);
906     }
907   }
908   else if(_enc->packet_state==OC_PACKET_DONE&&
909    _enc->rc.twopass_buffer_bytes!=OC_RC_2PASS_HDR_SZ){
910     _enc->rc.twopass_buffer_bytes=0;
911     oc_rc_buffer_val(&_enc->rc,0x5032544F,4);
912     oc_rc_buffer_val(&_enc->rc,OC_RC_2PASS_VERSION,4);
913     oc_rc_buffer_val(&_enc->rc,_enc->rc.frames_total[0],4);
914     oc_rc_buffer_val(&_enc->rc,_enc->rc.frames_total[1],4);
915     oc_rc_buffer_val(&_enc->rc,_enc->rc.frames_total[2],4);
916     oc_rc_buffer_val(&_enc->rc,_enc->rc.exp[0],1);
917     oc_rc_buffer_val(&_enc->rc,_enc->rc.exp[1],1);
918     oc_rc_buffer_val(&_enc->rc,_enc->rc.scale_sum[0],8);
919     oc_rc_buffer_val(&_enc->rc,_enc->rc.scale_sum[1],8);
920   }
921   else{
922     /*The data for this frame has already been retrieved.*/
923     *_buf=NULL;
924     return 0;
925   }
926   *_buf=_enc->rc.twopass_buffer;
927   return _enc->rc.twopass_buffer_bytes;
928 }
929
930 static size_t oc_rc_buffer_fill(oc_rc_state *_rc,
931  unsigned char *_buf,size_t _bytes,size_t _consumed,size_t _goal){
932   while(_rc->twopass_buffer_fill<_goal&&_consumed<_bytes){
933     _rc->twopass_buffer[_rc->twopass_buffer_fill++]=_buf[_consumed++];
934   }
935   return _consumed;
936 }
937
938 static ogg_int64_t oc_rc_unbuffer_val(oc_rc_state *_rc,int _bytes){
939   ogg_int64_t ret;
940   int         shift;
941   ret=0;
942   shift=0;
943   while(_bytes-->0){
944     ret|=((ogg_int64_t)_rc->twopass_buffer[_rc->twopass_buffer_bytes++])<<shift;
945     shift+=8;
946   }
947   return ret;
948 }
949
950 int oc_enc_rc_2pass_in(oc_enc_ctx *_enc,unsigned char *_buf,size_t _bytes){
951   size_t consumed;
952   consumed=0;
953   /*Enable pass 2 mode if this is the first call.*/
954   if(_enc->rc.twopass==0){
955     _enc->rc.twopass=2;
956     _enc->rc.twopass_buffer_fill=0;
957     _enc->rc.frames_total[0]=0;
958     _enc->rc.nframe_metrics=0;
959     _enc->rc.cframe_metrics=0;
960     _enc->rc.frame_metrics_head=0;
961     _enc->rc.scale_window0=0;
962     _enc->rc.scale_window_end=0;
963   }
964   /*If we haven't got a valid summary header yet, try to parse one.*/
965   if(_enc->rc.frames_total[0]==0){
966     if(!_buf){
967       int frames_needed;
968       /*If we're using a whole-file buffer, we just need the first frame.
969         Otherwise, we may need as many as one per buffer slot.*/
970       frames_needed=_enc->rc.frame_metrics==NULL?1:_enc->rc.buf_delay;
971       return OC_RC_2PASS_HDR_SZ+frames_needed*OC_RC_2PASS_PACKET_SZ
972        -_enc->rc.twopass_buffer_fill;
973     }
974     consumed=oc_rc_buffer_fill(&_enc->rc,
975      _buf,_bytes,consumed,OC_RC_2PASS_HDR_SZ);
976     if(_enc->rc.twopass_buffer_fill>=OC_RC_2PASS_HDR_SZ){
977       ogg_int64_t scale_sum[2];
978       int         exp[2];
979       int         buf_delay;
980       /*Read the summary header data.*/
981       /*Check the magic value and version number.*/
982       if(oc_rc_unbuffer_val(&_enc->rc,4)!=0x5032544F||
983        oc_rc_unbuffer_val(&_enc->rc,4)!=OC_RC_2PASS_VERSION){
984         _enc->rc.twopass_buffer_bytes=0;
985         return TH_ENOTFORMAT;
986       }
987       _enc->rc.frames_total[0]=(ogg_uint32_t)oc_rc_unbuffer_val(&_enc->rc,4);
988       _enc->rc.frames_total[1]=(ogg_uint32_t)oc_rc_unbuffer_val(&_enc->rc,4);
989       _enc->rc.frames_total[2]=(ogg_uint32_t)oc_rc_unbuffer_val(&_enc->rc,4);
990       exp[0]=(int)oc_rc_unbuffer_val(&_enc->rc,1);
991       exp[1]=(int)oc_rc_unbuffer_val(&_enc->rc,1);
992       scale_sum[0]=oc_rc_unbuffer_val(&_enc->rc,8);
993       scale_sum[1]=oc_rc_unbuffer_val(&_enc->rc,8);
994       /*Make sure the file claims to have at least one frame.
995         Otherwise we probably got the placeholder data from an aborted pass 1.
996         Also make sure the total frame count doesn't overflow an integer.*/
997       buf_delay=_enc->rc.frames_total[0]+_enc->rc.frames_total[1]
998        +_enc->rc.frames_total[2];
999       if(_enc->rc.frames_total[0]==0||buf_delay<0||
1000        (ogg_uint32_t)buf_delay<_enc->rc.frames_total[0]||
1001        (ogg_uint32_t)buf_delay<_enc->rc.frames_total[1]){
1002         _enc->rc.frames_total[0]=0;
1003         _enc->rc.twopass_buffer_bytes=0;
1004         return TH_EBADHEADER;
1005       }
1006       /*Got a valid header; set up pass 2.*/
1007       _enc->rc.frames_left[0]=_enc->rc.frames_total[0];
1008       _enc->rc.frames_left[1]=_enc->rc.frames_total[1];
1009       _enc->rc.frames_left[2]=_enc->rc.frames_total[2];
1010       /*If the user hasn't specified a buffer size, use the whole file.*/
1011       if(_enc->rc.frame_metrics==NULL){
1012         _enc->rc.buf_delay=buf_delay;
1013         _enc->rc.nframes[0]=_enc->rc.frames_total[0];
1014         _enc->rc.nframes[1]=_enc->rc.frames_total[1];
1015         _enc->rc.nframes[2]=_enc->rc.frames_total[2];
1016         _enc->rc.scale_sum[0]=scale_sum[0];
1017         _enc->rc.scale_sum[1]=scale_sum[1];
1018         _enc->rc.scale_window_end=buf_delay;
1019         oc_enc_rc_reset(_enc);
1020       }
1021       _enc->rc.exp[0]=exp[0];
1022       _enc->rc.exp[1]=exp[1];
1023       /*Clear the header data from the buffer to make room for packet data.*/
1024       _enc->rc.twopass_buffer_fill=0;
1025       _enc->rc.twopass_buffer_bytes=0;
1026     }
1027   }
1028   if(_enc->rc.frames_total[0]!=0){
1029     ogg_int64_t curframe_num;
1030     int         nframes_total;
1031     curframe_num=_enc->state.curframe_num;
1032     if(curframe_num>=0){
1033       /*We just encoded a frame; make sure things matched.*/
1034       if(_enc->rc.prev_metrics.dup_count!=_enc->prev_dup_count){
1035         _enc->rc.twopass_buffer_bytes=0;
1036         return TH_EINVAL;
1037       }
1038     }
1039     curframe_num+=_enc->prev_dup_count+1;
1040     nframes_total=_enc->rc.frames_total[0]+_enc->rc.frames_total[1]
1041      +_enc->rc.frames_total[2];
1042     if(curframe_num>=nframes_total){
1043       /*We don't want any more data after the last frame, and we don't want to
1044          allow any more frames to be encoded.*/
1045       _enc->rc.twopass_buffer_bytes=0;
1046     }
1047     else if(_enc->rc.twopass_buffer_bytes==0){
1048       if(_enc->rc.frame_metrics==NULL){
1049         /*We're using a whole-file buffer:*/
1050         if(!_buf)return OC_RC_2PASS_PACKET_SZ-_enc->rc.twopass_buffer_fill;
1051         consumed=oc_rc_buffer_fill(&_enc->rc,
1052          _buf,_bytes,consumed,OC_RC_2PASS_PACKET_SZ);
1053         if(_enc->rc.twopass_buffer_fill>=OC_RC_2PASS_PACKET_SZ){
1054           ogg_uint32_t dup_count;
1055           ogg_int32_t  log_scale;
1056           unsigned     activity;
1057           int          qti;
1058           int          arg;
1059           /*Read the metrics for the next frame.*/
1060           dup_count=oc_rc_unbuffer_val(&_enc->rc,4);
1061           log_scale=oc_rc_unbuffer_val(&_enc->rc,4);
1062           activity=oc_rc_unbuffer_val(&_enc->rc,4);
1063           _enc->rc.cur_metrics.log_scale=log_scale;
1064           qti=(dup_count&0x80000000)>>31;
1065           _enc->rc.cur_metrics.dup_count=dup_count&0x7FFFFFFF;
1066           _enc->rc.cur_metrics.frame_type=qti;
1067           _enc->rc.twopass_force_kf=qti==OC_INTRA_FRAME;
1068           _enc->activity_avg=_enc->rc.cur_metrics.activity_avg=activity;
1069           /*"Helpfully" set the dup count back to what it was in pass 1.*/
1070           arg=_enc->rc.cur_metrics.dup_count;
1071           th_encode_ctl(_enc,TH_ENCCTL_SET_DUP_COUNT,&arg,sizeof(arg));
1072           /*Clear the buffer for the next frame.*/
1073           _enc->rc.twopass_buffer_fill=0;
1074         }
1075       }
1076       else{
1077         int frames_needed;
1078         /*We're using a finite buffer:*/
1079         frames_needed=OC_MINI(_enc->rc.buf_delay-OC_MINI(_enc->rc.buf_delay,
1080          _enc->rc.scale_window_end-_enc->rc.scale_window0),
1081          _enc->rc.frames_left[0]+_enc->rc.frames_left[1]
1082          -_enc->rc.nframes[0]-_enc->rc.nframes[1]);
1083         while(frames_needed>0){
1084           if(!_buf){
1085             return OC_RC_2PASS_PACKET_SZ*frames_needed
1086            -_enc->rc.twopass_buffer_fill;
1087           }
1088           consumed=oc_rc_buffer_fill(&_enc->rc,
1089            _buf,_bytes,consumed,OC_RC_2PASS_PACKET_SZ);
1090           if(_enc->rc.twopass_buffer_fill>=OC_RC_2PASS_PACKET_SZ){
1091             oc_frame_metrics *m;
1092             int               fmi;
1093             ogg_uint32_t      dup_count;
1094             ogg_int32_t       log_scale;
1095             int               qti;
1096             unsigned          activity;
1097             /*Read the metrics for the next frame.*/
1098             dup_count=oc_rc_unbuffer_val(&_enc->rc,4);
1099             log_scale=oc_rc_unbuffer_val(&_enc->rc,4);
1100             activity=oc_rc_unbuffer_val(&_enc->rc,4);
1101             /*Add the to the circular buffer.*/
1102             fmi=_enc->rc.frame_metrics_head+_enc->rc.nframe_metrics++;
1103             if(fmi>=_enc->rc.cframe_metrics)fmi-=_enc->rc.cframe_metrics;
1104             m=_enc->rc.frame_metrics+fmi;
1105             m->log_scale=log_scale;
1106             qti=(dup_count&0x80000000)>>31;
1107             m->dup_count=dup_count&0x7FFFFFFF;
1108             m->frame_type=qti;
1109             m->activity_avg=activity;
1110             /*And accumulate the statistics over the window.*/
1111             _enc->rc.nframes[qti]++;
1112             _enc->rc.nframes[2]+=m->dup_count;
1113             _enc->rc.scale_sum[qti]+=oc_bexp_q24(m->log_scale);
1114             _enc->rc.scale_window_end+=m->dup_count+1;
1115             /*Compute an upper bound on the number of remaining packets needed
1116                for the current window.*/
1117             frames_needed=OC_MINI(_enc->rc.buf_delay-OC_MINI(_enc->rc.buf_delay,
1118              _enc->rc.scale_window_end-_enc->rc.scale_window0),
1119              _enc->rc.frames_left[0]+_enc->rc.frames_left[1]
1120              -_enc->rc.nframes[0]-_enc->rc.nframes[1]);
1121             /*Clear the buffer for the next frame.*/
1122             _enc->rc.twopass_buffer_fill=0;
1123             _enc->rc.twopass_buffer_bytes=0;
1124           }
1125           /*Go back for more data.*/
1126           else break;
1127         }
1128         /*If we've got all the frames we need, fill in the current metrics.
1129           We're ready to go.*/
1130         if(frames_needed<=0){
1131           int arg;
1132           *&_enc->rc.cur_metrics=
1133            *(_enc->rc.frame_metrics+_enc->rc.frame_metrics_head);
1134           _enc->rc.twopass_force_kf=
1135            _enc->rc.cur_metrics.frame_type==OC_INTRA_FRAME;
1136           _enc->activity_avg=_enc->rc.cur_metrics.activity_avg;
1137           /*"Helpfully" set the dup count back to what it was in pass 1.*/
1138           arg=_enc->rc.cur_metrics.dup_count;
1139           th_encode_ctl(_enc,TH_ENCCTL_SET_DUP_COUNT,&arg,sizeof(arg));
1140           /*Mark us ready for the next frame.*/
1141           _enc->rc.twopass_buffer_bytes=1;
1142         }
1143       }
1144     }
1145   }
1146   return (int)consumed;
1147 }