allow non-mod16 resolutions
[x262.git] / encoder / ratecontrol.c
1 /***************************************************-*- coding: iso-8859-1 -*-
2  * ratecontrol.c: h264 encoder library (Rate Control)
3  *****************************************************************************
4  * Copyright (C) 2005 x264 project
5  * $Id: ratecontrol.c,v 1.1 2004/06/03 19:27:08 fenrir Exp $
6  *
7  * Authors: Loren Merritt <lorenm@u.washington.edu>
8  *          Michael Niedermayer <michaelni@gmx.at>
9  *          Måns Rullgård <mru@mru.ath.cx>
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
24  *****************************************************************************/
25
26 #define _ISOC99_SOURCE
27 #undef NDEBUG // always check asserts, the speed effect is far too small to disable them
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <string.h>
31 #include <math.h>
32 #include <limits.h>
33 #include <assert.h>
34
35 #include "common/common.h"
36 #include "common/cpu.h"
37 #include "ratecontrol.h"
38
39 #if defined(SYS_FREEBSD) || defined(SYS_BEOS) || defined(SYS_NETBSD)
40 #define exp2f(x) powf( 2, (x) )
41 #endif
42 #if defined(_MSC_VER) || defined(SYS_SunOS)
43 #define exp2f(x) pow( 2, (x) )
44 #define sqrtf sqrt
45 #endif
46 #ifdef WIN32 // POSIX says that rename() removes the destination, but win32 doesn't.
47 #define rename(src,dst) (unlink(dst), rename(src,dst))
48 #endif
49
50 typedef struct
51 {
52     int pict_type;
53     int kept_as_ref;
54     float qscale;
55     int mv_bits;
56     int i_tex_bits;
57     int p_tex_bits;
58     int misc_bits;
59     uint64_t expected_bits;
60     float new_qscale;
61     int new_qp;
62     int i_count;
63     int p_count;
64     int s_count;
65     float blurred_complexity;
66 } ratecontrol_entry_t;
67
68 typedef struct
69 {
70     double coeff;
71     double count;
72     double decay;
73 } predictor_t;
74
75 struct x264_ratecontrol_t
76 {
77     /* constants */
78     int b_abr;
79     int b_2pass;
80     double fps;
81     double bitrate;
82     double rate_tolerance;
83     int nmb;                    /* number of macroblocks in a frame */
84     int qp_constant[5];
85
86     /* current frame */
87     ratecontrol_entry_t *rce;
88     int qp;                     /* qp for current frame */
89     float qpa;                  /* average of macroblocks' qp (same as qp if no adaptive quant) */
90     int slice_type;
91     int qp_force;
92
93     /* VBV stuff */
94     double buffer_size;
95     double buffer_fill;
96     double buffer_rate;         /* # of bits added to buffer_fill after each frame */
97     predictor_t pred[5];        /* predict frame size from satd */
98
99     /* ABR stuff */
100     int    last_satd;
101     double last_rceq;
102     double cplxr_sum;           /* sum of bits*qscale/rceq */
103     double expected_bits_sum;   /* sum of qscale2bits after rceq, ratefactor, and overflow */
104     double wanted_bits_window;  /* target bitrate * window */
105     double cbr_decay;
106     double short_term_cplxsum;
107     double short_term_cplxcount;
108
109     /* 2pass stuff */
110     FILE *p_stat_file_out;
111     char *psz_stat_file_tmpname;
112
113     int num_entries;            /* number of ratecontrol_entry_ts */
114     ratecontrol_entry_t *entry; /* FIXME: copy needed data and free this once init is done */
115     double last_qscale;
116     double last_qscale_for[5];  /* last qscale for a specific pict type, used for max_diff & ipb factor stuff  */
117     int last_non_b_pict_type;
118     double accum_p_qp;          /* for determining I-frame quant */
119     double accum_p_norm;
120     double last_accum_p_norm;
121     double lmin[5];             /* min qscale by frame type */
122     double lmax[5];
123     double lstep;               /* max change (multiply) in qscale per frame */
124     double i_cplx_sum[5];       /* estimated total texture bits in intra MBs at qscale=1 */
125     double p_cplx_sum[5];
126     double mv_bits_sum[5];
127     int frame_count[5];         /* number of frames of each type */
128
129     int i_zones;
130     x264_zone_t *zones;
131 };
132
133
134 static int parse_zones( x264_t *h );
135 static int init_pass2(x264_t *);
136 static float rate_estimate_qscale( x264_t *h, int pict_type );
137 static void update_vbv( x264_t *h, int bits );
138 int  x264_rc_analyse_slice( x264_t *h );
139
140 /* Terminology:
141  * qp = h.264's quantizer
142  * qscale = linearized quantizer = Lagrange multiplier
143  */
144 static inline double qp2qscale(double qp)
145 {
146     return 0.85 * pow(2.0, ( qp - 12.0 ) / 6.0);
147 }
148 static inline double qscale2qp(double qscale)
149 {
150     return 12.0 + 6.0 * log(qscale/0.85) / log(2.0);
151 }
152
153 /* Texture bitrate is not quite inversely proportional to qscale,
154  * probably due the the changing number of SKIP blocks.
155  * MV bits level off at about qp<=12, because the lambda used
156  * for motion estimation is constant there. */
157 static inline double qscale2bits(ratecontrol_entry_t *rce, double qscale)
158 {
159     if(qscale<0.1)
160         qscale = 0.1;
161     return (rce->i_tex_bits + rce->p_tex_bits + .1) * pow( rce->qscale / qscale, 1.1 )
162            + rce->mv_bits * pow( X264_MAX(rce->qscale, 12) / X264_MAX(qscale, 12), 0.5 );
163 }
164
165 /* There is no analytical inverse to the above formula. */
166 #if 0
167 static inline double bits2qscale(ratecontrol_entry_t *rce, double bits)
168 {
169     if(bits<1.0)
170         bits = 1.0;
171     return (rce->i_tex_bits + rce->p_tex_bits + rce->mv_bits + .1) * rce->qscale / bits;
172 }
173 #endif
174
175
176 int x264_ratecontrol_new( x264_t *h )
177 {
178     x264_ratecontrol_t *rc;
179     int i;
180
181     x264_cpu_restore( h->param.cpu );
182
183     h->rc = rc = x264_malloc( sizeof( x264_ratecontrol_t ) );
184     memset(rc, 0, sizeof(*rc));
185
186     rc->b_abr = h->param.rc.b_cbr && !h->param.rc.b_stat_read;
187     rc->b_2pass = h->param.rc.b_cbr && h->param.rc.b_stat_read;
188     h->mb.b_variable_qp = 0;
189     
190     /* FIXME: use integers */
191     if(h->param.i_fps_num > 0 && h->param.i_fps_den > 0)
192         rc->fps = (float) h->param.i_fps_num / h->param.i_fps_den;
193     else
194         rc->fps = 25.0;
195
196     rc->bitrate = h->param.rc.i_bitrate * 1000;
197     rc->rate_tolerance = h->param.rc.f_rate_tolerance;
198     rc->nmb = h->mb.i_mb_count;
199     rc->last_non_b_pict_type = -1;
200     rc->cbr_decay = 1.0;
201
202     if( h->param.rc.i_vbv_max_bitrate < h->param.rc.i_bitrate &&
203         h->param.rc.i_vbv_max_bitrate > 0)
204         x264_log(h, X264_LOG_ERROR, "max bitrate less than average bitrate, ignored.\n");
205     else if( h->param.rc.i_vbv_max_bitrate > 0 &&
206              h->param.rc.i_vbv_buffer_size > 0 )
207     {
208         if( h->param.rc.i_vbv_buffer_size < 10 * h->param.rc.i_vbv_max_bitrate / rc->fps ) {
209             h->param.rc.i_vbv_buffer_size = 10 * h->param.rc.i_vbv_max_bitrate / rc->fps;
210             x264_log( h, X264_LOG_ERROR, "VBV buffer size too small, using %d kbit\n",
211                       h->param.rc.i_vbv_buffer_size );
212         }
213         rc->buffer_rate = h->param.rc.i_vbv_max_bitrate * 1000 / rc->fps;
214         rc->buffer_size = h->param.rc.i_vbv_buffer_size * 1000;
215         rc->buffer_fill = rc->buffer_size * h->param.rc.f_vbv_buffer_init;
216         rc->cbr_decay = 1.0 - rc->buffer_rate / rc->buffer_size
217                       * 0.5 * X264_MAX(0, 1.5 - rc->buffer_rate * rc->fps / rc->bitrate);
218     }
219     else if( h->param.rc.i_vbv_max_bitrate || h->param.rc.i_vbv_buffer_size )
220         x264_log(h, X264_LOG_ERROR, "VBV maxrate or buffer size specified, but not both.\n");
221     if(rc->rate_tolerance < 0.01) {
222         x264_log(h, X264_LOG_ERROR, "bitrate tolerance too small, using .01\n");
223         rc->rate_tolerance = 0.01;
224     }
225
226     if( rc->b_abr )
227     {
228         /* FIXME shouldn't need to arbitrarily specify a QP,
229          * but this is more robust than BPP measures */
230 #define ABR_INIT_QP 24
231         rc->accum_p_norm = .01;
232         rc->accum_p_qp = ABR_INIT_QP * rc->accum_p_norm;
233         rc->cplxr_sum = .01;
234         rc->wanted_bits_window = .01;
235     }
236
237     rc->qp_constant[SLICE_TYPE_P] = h->param.rc.i_qp_constant;
238     rc->qp_constant[SLICE_TYPE_I] = x264_clip3( (int)( qscale2qp( qp2qscale( h->param.rc.i_qp_constant ) / fabs( h->param.rc.f_ip_factor )) + 0.5 ), 0, 51 );
239     rc->qp_constant[SLICE_TYPE_B] = x264_clip3( (int)( qscale2qp( qp2qscale( h->param.rc.i_qp_constant ) * fabs( h->param.rc.f_pb_factor )) + 0.5 ), 0, 51 );
240
241     rc->lstep = exp2f(h->param.rc.i_qp_step / 6.0);
242     rc->last_qscale = qp2qscale(26);
243     for( i = 0; i < 5; i++ )
244     {
245         rc->last_qscale_for[i] = qp2qscale(26);
246         rc->lmin[i] = qp2qscale( h->param.rc.i_qp_min );
247         rc->lmax[i] = qp2qscale( h->param.rc.i_qp_max );
248         rc->pred[i].coeff= 2.0;
249         rc->pred[i].count= 1.0;
250         rc->pred[i].decay= 0.5;
251     }
252 #if 0 // FIXME: do we want to assign lmin/lmax based on ip_factor, or leave them all the same?
253     rc->lmin[SLICE_TYPE_I] /= fabs(h->param.f_ip_factor);
254     rc->lmax[SLICE_TYPE_I] /= fabs(h->param.f_ip_factor);
255     rc->lmin[SLICE_TYPE_B] *= fabs(h->param.f_pb_factor);
256     rc->lmax[SLICE_TYPE_B] *= fabs(h->param.f_pb_factor);
257 #endif
258
259     if( parse_zones( h ) < 0 )
260         return -1;
261
262     /* Load stat file and init 2pass algo */
263     if( h->param.rc.b_stat_read )
264     {
265         char *p, *stats_in;
266
267         /* read 1st pass stats */
268         assert( h->param.rc.psz_stat_in );
269         stats_in = x264_slurp_file( h->param.rc.psz_stat_in );
270         if( !stats_in )
271         {
272             x264_log(h, X264_LOG_ERROR, "ratecontrol_init: can't open stats file\n");
273             return -1;
274         }
275
276         /* find number of pics */
277         p = stats_in;
278         for(i=-1; p; i++)
279             p = strchr(p+1, ';');
280         if(i==0)
281         {
282             x264_log(h, X264_LOG_ERROR, "empty stats file\n");
283             return -1;
284         }
285         i += h->param.i_bframe;
286         rc->entry = (ratecontrol_entry_t*) x264_malloc(i*sizeof(ratecontrol_entry_t));
287         memset(rc->entry, 0, i*sizeof(ratecontrol_entry_t));
288         /* FIXME: num_entries is sometimes treated as number of frames in the video */
289         rc->num_entries= i;
290
291         /* init all to skipped p frames */
292         for(i=0; i<rc->num_entries; i++){
293             ratecontrol_entry_t *rce = &rc->entry[i];
294             rce->pict_type = SLICE_TYPE_P;
295             rce->qscale = rce->new_qscale = qp2qscale(20);
296             rce->misc_bits = rc->nmb + 10;
297             rce->new_qp = 0;
298         }
299
300         /* read stats */
301         p = stats_in;
302         for(i=0; i < rc->num_entries - h->param.i_bframe; i++){
303             ratecontrol_entry_t *rce;
304             int frame_number;
305             char pict_type;
306             int e;
307             char *next;
308             float qp;
309
310             next= strchr(p, ';');
311             if(next){
312                 (*next)=0; //sscanf is unbelievably slow on looong strings
313                 next++;
314             }
315             e = sscanf(p, " in:%d ", &frame_number);
316
317             if(frame_number < 0 || frame_number >= rc->num_entries)
318             {
319                 x264_log(h, X264_LOG_ERROR, "bad frame number (%d) at stats line %d\n", frame_number, i);
320                 return -1;
321             }
322             rce = &rc->entry[frame_number];
323
324             e += sscanf(p, " in:%*d out:%*d type:%c q:%f itex:%d ptex:%d mv:%d misc:%d imb:%d pmb:%d smb:%d",
325                    &pict_type, &qp, &rce->i_tex_bits, &rce->p_tex_bits,
326                    &rce->mv_bits, &rce->misc_bits, &rce->i_count, &rce->p_count, &rce->s_count);
327
328             switch(pict_type){
329                 case 'I': rce->kept_as_ref = 1;
330                 case 'i': rce->pict_type = SLICE_TYPE_I; break;
331                 case 'P': rce->pict_type = SLICE_TYPE_P; break;
332                 case 'B': rce->kept_as_ref = 1;
333                 case 'b': rce->pict_type = SLICE_TYPE_B; break;
334                 default:  e = -1; break;
335             }
336             if(e != 10){
337                 x264_log(h, X264_LOG_ERROR, "statistics are damaged at line %d, parser out=%d\n", i, e);
338                 return -1;
339             }
340             rce->qscale = qp2qscale(qp);
341             p = next;
342         }
343
344         x264_free(stats_in);
345
346         if(h->param.rc.b_cbr)
347         {
348             if(init_pass2(h) < 0) return -1;
349         } /* else we're using constant quant, so no need to run the bitrate allocation */
350     }
351
352     /* Open output file */
353     /* If input and output files are the same, output to a temp file
354      * and move it to the real name only when it's complete */
355     if( h->param.rc.b_stat_write )
356     {
357         rc->psz_stat_file_tmpname = x264_malloc( strlen(h->param.rc.psz_stat_out) + 6 );
358         strcpy( rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out );
359         strcat( rc->psz_stat_file_tmpname, ".temp" );
360
361         rc->p_stat_file_out = fopen( rc->psz_stat_file_tmpname, "wb" );
362         if( rc->p_stat_file_out == NULL )
363         {
364             x264_log(h, X264_LOG_ERROR, "ratecontrol_init: can't open stats file\n");
365             return -1;
366         }
367     }
368
369     return 0;
370 }
371
372 static int parse_zones( x264_t *h )
373 {
374     x264_ratecontrol_t *rc = h->rc;
375     int i;
376     if( h->param.rc.psz_zones && !h->param.rc.i_zones )
377     {
378         char *p;
379         h->param.rc.i_zones = 1;
380         for( p = h->param.rc.psz_zones; *p; p++ )
381             h->param.rc.i_zones += (*p == '/');
382         h->param.rc.zones = x264_malloc( h->param.rc.i_zones * sizeof(x264_zone_t) );
383         p = h->param.rc.psz_zones;
384         for( i = 0; i < h->param.rc.i_zones; i++)
385         {
386             x264_zone_t *z = &h->param.rc.zones[i];
387             if( 3 == sscanf(p, "%u,%u,q=%u", &z->i_start, &z->i_end, &z->i_qp) )
388                 z->b_force_qp = 1;
389             else if( 3 == sscanf(p, "%u,%u,b=%f", &z->i_start, &z->i_end, &z->f_bitrate_factor) )
390                 z->b_force_qp = 0;
391             else
392             {
393                 char *slash = strchr(p, '/');
394                 if(slash) *slash = '\0';
395                 x264_log( h, X264_LOG_ERROR, "invalid zone: \"%s\"\n", p );
396                 return -1;
397             }
398             p = strchr(p, '/') + 1;
399         }
400     }
401
402     if( h->param.rc.i_zones > 0 )
403     {
404         for( i = 0; i < h->param.rc.i_zones; i++ )
405         {
406             x264_zone_t z = h->param.rc.zones[i];
407             if( z.i_start < 0 || z.i_start > z.i_end )
408             {
409                 x264_log( h, X264_LOG_ERROR, "invalid zone: start=%d end=%d\n",
410                           z.i_start, z.i_end );
411                 return -1;
412             }
413             else if( !z.b_force_qp && z.f_bitrate_factor <= 0 )
414             {
415                 x264_log( h, X264_LOG_ERROR, "invalid zone: bitrate_factor=%f\n",
416                           z.f_bitrate_factor );
417                 return -1;
418             }
419         }
420
421         rc->i_zones = h->param.rc.i_zones;
422         rc->zones = x264_malloc( rc->i_zones * sizeof(x264_zone_t) );
423         memcpy( rc->zones, h->param.rc.zones, rc->i_zones * sizeof(x264_zone_t) );
424     }
425
426     return 0;
427 }
428
429 void x264_ratecontrol_delete( x264_t *h )
430 {
431     x264_ratecontrol_t *rc = h->rc;
432
433     if( rc->p_stat_file_out )
434     {
435         fclose( rc->p_stat_file_out );
436         if( h->i_frame >= rc->num_entries - h->param.i_bframe )
437             if( rename( rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out ) != 0 )
438             {
439                 x264_log( h, X264_LOG_ERROR, "failed to rename \"%s\" to \"%s\"\n",
440                           rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out );
441             }
442         x264_free( rc->psz_stat_file_tmpname );
443     }
444     x264_free( rc->entry );
445     x264_free( rc->zones );
446     x264_free( rc );
447 }
448
449 /* Before encoding a frame, choose a QP for it */
450 void x264_ratecontrol_start( x264_t *h, int i_slice_type, int i_force_qp )
451 {
452     x264_ratecontrol_t *rc = h->rc;
453
454     x264_cpu_restore( h->param.cpu );
455
456     rc->qp_force = i_force_qp;
457     rc->slice_type = i_slice_type;
458
459     if( i_force_qp )
460     {
461         rc->qpa = rc->qp = i_force_qp - 1;
462     }
463     else if( rc->b_abr )
464     {
465         rc->qpa = rc->qp =
466             x264_clip3( (int)(qscale2qp( rate_estimate_qscale( h, i_slice_type ) ) + .5), 0, 51 );
467     }
468     else if( rc->b_2pass )
469     {
470         int frame = h->fenc->i_frame;
471         ratecontrol_entry_t *rce;
472         assert( frame >= 0 && frame < rc->num_entries );
473         rce = h->rc->rce = &h->rc->entry[frame];
474
475         rce->new_qscale = rate_estimate_qscale( h, i_slice_type );
476         rc->qpa = rc->qp = rce->new_qp =
477             x264_clip3( (int)(qscale2qp(rce->new_qscale) + 0.5), 0, 51 );
478     }
479     else /* CQP */
480     {
481         int q;
482         if( i_slice_type == SLICE_TYPE_B && h->fdec->b_kept_as_ref )
483             q = ( rc->qp_constant[ SLICE_TYPE_B ] + rc->qp_constant[ SLICE_TYPE_P ] ) / 2;
484         else
485             q = rc->qp_constant[ i_slice_type ];
486         rc->qpa = rc->qp = q;
487     }
488 }
489
490 void x264_ratecontrol_mb( x264_t *h, int bits )
491 {
492     /* currently no adaptive quant */
493 }
494
495 int x264_ratecontrol_qp( x264_t *h )
496 {
497     return h->rc->qp;
498 }
499
500 /* In 2pass, force the same frame types as in the 1st pass */
501 int x264_ratecontrol_slice_type( x264_t *h, int frame_num )
502 {
503     if( h->param.rc.b_stat_read )
504     {
505         if( frame_num >= h->rc->num_entries )
506         {
507             x264_log(h, X264_LOG_ERROR, "More input frames than in the 1st pass\n");
508             return X264_TYPE_P;
509         }
510         switch( h->rc->entry[frame_num].pict_type )
511         {
512             case SLICE_TYPE_I:
513                 return h->rc->entry[frame_num].kept_as_ref ? X264_TYPE_IDR : X264_TYPE_I;
514
515             case SLICE_TYPE_B:
516                 return h->rc->entry[frame_num].kept_as_ref ? X264_TYPE_BREF : X264_TYPE_B;
517
518             case SLICE_TYPE_P:
519             default:
520                 return X264_TYPE_P;
521         }
522     }
523     else
524     {
525         return X264_TYPE_AUTO;
526     }
527 }
528
529 /* After encoding one frame, save stats and update ratecontrol state */
530 void x264_ratecontrol_end( x264_t *h, int bits )
531 {
532     x264_ratecontrol_t *rc = h->rc;
533     const int *mbs = h->stat.frame.i_mb_count;
534     int i;
535
536     x264_cpu_restore( h->param.cpu );
537
538     h->stat.frame.i_mb_count_skip = mbs[P_SKIP] + mbs[B_SKIP];
539     h->stat.frame.i_mb_count_i = mbs[I_16x16] + mbs[I_8x8] + mbs[I_4x4];
540     h->stat.frame.i_mb_count_p = mbs[P_L0] + mbs[P_8x8];
541     for( i = B_DIRECT; i < B_8x8; i++ )
542         h->stat.frame.i_mb_count_p += mbs[i];
543
544     if( h->param.rc.b_stat_write )
545     {
546         char c_type = rc->slice_type==SLICE_TYPE_I ? (h->fenc->i_poc==0 ? 'I' : 'i')
547                     : rc->slice_type==SLICE_TYPE_P ? 'P'
548                     : h->fenc->b_kept_as_ref ? 'B' : 'b';
549         fprintf( rc->p_stat_file_out,
550                  "in:%d out:%d type:%c q:%.2f itex:%d ptex:%d mv:%d misc:%d imb:%d pmb:%d smb:%d;\n",
551                  h->fenc->i_frame, h->i_frame-1,
552                  c_type, rc->qpa,
553                  h->stat.frame.i_itex_bits, h->stat.frame.i_ptex_bits,
554                  h->stat.frame.i_hdr_bits, h->stat.frame.i_misc_bits,
555                  h->stat.frame.i_mb_count_i,
556                  h->stat.frame.i_mb_count_p,
557                  h->stat.frame.i_mb_count_skip);
558     }
559
560     if( rc->b_abr )
561     {
562         if( rc->slice_type != SLICE_TYPE_B )
563             rc->cplxr_sum += bits * qp2qscale(rc->qpa) / rc->last_rceq;
564         else
565         {
566             /* Depends on the fact that B-frame's QP is an offset from the following P-frame's.
567              * Not perfectly accurate with B-refs, but good enough. */
568             rc->cplxr_sum += bits * qp2qscale(rc->qpa) / (rc->last_rceq * fabs(h->param.rc.f_pb_factor));
569         }
570         rc->cplxr_sum *= rc->cbr_decay;
571         rc->wanted_bits_window += rc->bitrate / rc->fps;
572         rc->wanted_bits_window *= rc->cbr_decay;
573
574         rc->accum_p_qp   *= .95;
575         rc->accum_p_norm *= .95;
576         rc->accum_p_norm += 1;
577         if( rc->slice_type == SLICE_TYPE_I )
578             rc->accum_p_qp += rc->qpa * fabs(h->param.rc.f_ip_factor);
579         else
580             rc->accum_p_qp += rc->qpa;
581     }
582
583     if( rc->b_2pass )
584     {
585         rc->expected_bits_sum += qscale2bits( rc->rce, qp2qscale(rc->rce->new_qp) );
586     }
587
588     update_vbv( h, bits );
589
590     if( rc->slice_type != SLICE_TYPE_B )
591         rc->last_non_b_pict_type = rc->slice_type;
592 }
593
594 /****************************************************************************
595  * 2 pass functions
596  ***************************************************************************/
597
598 double x264_eval( char *s, double *const_value, const char **const_name,
599                   double (**func1)(void *, double), const char **func1_name,
600                   double (**func2)(void *, double, double), char **func2_name,
601                   void *opaque );
602
603 /**
604  * modify the bitrate curve from pass1 for one frame
605  */
606 static double get_qscale(x264_t *h, ratecontrol_entry_t *rce, double rate_factor, int frame_num)
607 {
608     x264_ratecontrol_t *rcc= h->rc;
609     const int pict_type = rce->pict_type;
610     double q;
611     int i;
612
613     double const_values[]={
614         rce->i_tex_bits * rce->qscale,
615         rce->p_tex_bits * rce->qscale,
616         (rce->i_tex_bits + rce->p_tex_bits) * rce->qscale,
617         rce->mv_bits * rce->qscale,
618         (double)rce->i_count / rcc->nmb,
619         (double)rce->p_count / rcc->nmb,
620         (double)rce->s_count / rcc->nmb,
621         rce->pict_type == SLICE_TYPE_I,
622         rce->pict_type == SLICE_TYPE_P,
623         rce->pict_type == SLICE_TYPE_B,
624         h->param.rc.f_qcompress,
625         rcc->i_cplx_sum[SLICE_TYPE_I] / rcc->frame_count[SLICE_TYPE_I],
626         rcc->i_cplx_sum[SLICE_TYPE_P] / rcc->frame_count[SLICE_TYPE_P],
627         rcc->p_cplx_sum[SLICE_TYPE_P] / rcc->frame_count[SLICE_TYPE_P],
628         rcc->p_cplx_sum[SLICE_TYPE_B] / rcc->frame_count[SLICE_TYPE_B],
629         (rcc->i_cplx_sum[pict_type] + rcc->p_cplx_sum[pict_type]) / rcc->frame_count[pict_type],
630         rce->blurred_complexity,
631         0
632     };
633     static const char *const_names[]={
634         "iTex",
635         "pTex",
636         "tex",
637         "mv",
638         "iCount",
639         "pCount",
640         "sCount",
641         "isI",
642         "isP",
643         "isB",
644         "qComp",
645         "avgIITex",
646         "avgPITex",
647         "avgPPTex",
648         "avgBPTex",
649         "avgTex",
650         "blurCplx",
651         NULL
652     };
653     static double (*func1[])(void *, double)={
654 //      (void *)bits2qscale,
655         (void *)qscale2bits,
656         NULL
657     };
658     static const char *func1_names[]={
659 //      "bits2qp",
660         "qp2bits",
661         NULL
662     };
663
664     q = x264_eval((char*)h->param.rc.psz_rc_eq, const_values, const_names, func1, func1_names, NULL, NULL, rce);
665
666     // avoid NaN's in the rc_eq
667     if(q != q || rce->i_tex_bits + rce->p_tex_bits + rce->mv_bits == 0)
668         q = rcc->last_qscale;
669     else {
670         rcc->last_rceq = q;
671         q /= rate_factor;
672         rcc->last_qscale = q;
673     }
674
675     for( i = rcc->i_zones-1; i >= 0; i-- )
676     {
677         x264_zone_t *z = &rcc->zones[i];
678         if( frame_num >= z->i_start && frame_num <= z->i_end )
679         {
680             if( z->b_force_qp )
681                 q = qp2qscale(z->i_qp);
682             else
683                 q /= z->f_bitrate_factor;
684             break;
685         }
686     }
687
688     return q;
689 }
690
691 static double get_diff_limited_q(x264_t *h, ratecontrol_entry_t *rce, double q)
692 {
693     x264_ratecontrol_t *rcc = h->rc;
694     const int pict_type = rce->pict_type;
695
696     // force I/B quants as a function of P quants
697     const double last_p_q    = rcc->last_qscale_for[SLICE_TYPE_P];
698     const double last_non_b_q= rcc->last_qscale_for[rcc->last_non_b_pict_type];
699     if( pict_type == SLICE_TYPE_I )
700     {
701         double iq = q;
702         double pq = qp2qscale( rcc->accum_p_qp / rcc->accum_p_norm );
703         double ip_factor = fabs( h->param.rc.f_ip_factor );
704         /* don't apply ip_factor if the following frame is also I */
705         if( rcc->accum_p_norm <= 0 )
706             q = iq;
707         else if( h->param.rc.f_ip_factor < 0 )
708             q = iq / ip_factor;
709         else if( rcc->accum_p_norm >= 1 )
710             q = pq / ip_factor;
711         else
712             q = rcc->accum_p_norm * pq / ip_factor + (1 - rcc->accum_p_norm) * iq;
713     }
714     else if( pict_type == SLICE_TYPE_B )
715     {
716         if( h->param.rc.f_pb_factor > 0 )
717             q = last_non_b_q;
718         if( !rce->kept_as_ref )
719             q *= fabs( h->param.rc.f_pb_factor );
720     }
721     else if( pict_type == SLICE_TYPE_P
722              && rcc->last_non_b_pict_type == SLICE_TYPE_P
723              && rce->i_tex_bits + rce->p_tex_bits == 0 )
724     {
725         q = last_p_q;
726     }
727
728     /* last qscale / qdiff stuff */
729     if(rcc->last_non_b_pict_type==pict_type
730        && (pict_type!=SLICE_TYPE_I || rcc->last_accum_p_norm < 1))
731     {
732         double last_q = rcc->last_qscale_for[pict_type];
733         double max_qscale = last_q * rcc->lstep;
734         double min_qscale = last_q / rcc->lstep;
735
736         if     (q > max_qscale) q = max_qscale;
737         else if(q < min_qscale) q = min_qscale;
738     }
739
740     rcc->last_qscale_for[pict_type] = q;
741     if(pict_type!=SLICE_TYPE_B)
742         rcc->last_non_b_pict_type = pict_type;
743     if(pict_type==SLICE_TYPE_I)
744     {
745         rcc->last_accum_p_norm = rcc->accum_p_norm;
746         rcc->accum_p_norm = 0;
747         rcc->accum_p_qp = 0;
748     }
749     if(pict_type==SLICE_TYPE_P)
750     {
751         float mask = 1 - pow( (float)rce->i_count / rcc->nmb, 2 );
752         rcc->accum_p_qp   = mask * (qscale2qp(q) + rcc->accum_p_qp);
753         rcc->accum_p_norm = mask * (1 + rcc->accum_p_norm);
754     }
755     return q;
756 }
757
758 static double predict_size( predictor_t *p, double q, double var )
759 {
760      return p->coeff*var / (q*p->count);
761 }
762
763 static void update_predictor( predictor_t *p, double q, double var, double bits )
764 {
765     p->count *= p->decay;
766     p->coeff *= p->decay;
767     p->count ++;
768     p->coeff += bits*q / var;
769 }
770
771 static void update_vbv( x264_t *h, int bits )
772 {
773     x264_ratecontrol_t *rcc = h->rc;
774     if( !rcc->buffer_size )
775         return;
776
777     rcc->buffer_fill += rcc->buffer_rate - bits;
778     if( rcc->buffer_fill < 0 && !rcc->b_2pass )
779         x264_log( h, X264_LOG_WARNING, "VBV underflow (%.0f bits)\n", rcc->buffer_fill );
780     rcc->buffer_fill = x264_clip3( rcc->buffer_fill, 0, rcc->buffer_size );
781
782     if(rcc->last_satd > 100)
783         update_predictor( &rcc->pred[rcc->slice_type], qp2qscale(rcc->qpa), rcc->last_satd, bits );
784 }
785
786 // apply VBV constraints and clip qscale to between lmin and lmax
787 static double clip_qscale( x264_t *h, int pict_type, double q )
788 {
789     x264_ratecontrol_t *rcc = h->rc;
790     double lmin = rcc->lmin[pict_type];
791     double lmax = rcc->lmax[pict_type];
792     double q0 = q;
793
794     /* B-frames are not directly subject to VBV,
795      * since they are controlled by the P-frames' QPs.
796      * FIXME: in 2pass we could modify previous frames' QP too,
797      *        instead of waiting for the buffer to fill */
798     if( rcc->buffer_size &&
799         ( pict_type == SLICE_TYPE_P ||
800           ( pict_type == SLICE_TYPE_I && rcc->last_non_b_pict_type == SLICE_TYPE_I ) ) )
801     {
802         if( rcc->buffer_fill/rcc->buffer_size < 0.5 )
803             q /= x264_clip3f( 2.0*rcc->buffer_fill/rcc->buffer_size, 0.5, 1.0 );
804     }
805     /* Now a hard threshold to make sure the frame fits in VBV.
806      * This one is mostly for I-frames. */
807     if( rcc->buffer_size && rcc->last_satd > 0 )
808     {
809         double bits = predict_size( &rcc->pred[rcc->slice_type], q, rcc->last_satd );
810         double qf = 1.0;
811         if( bits > rcc->buffer_fill/2 )
812             qf = x264_clip3f( rcc->buffer_fill/(2*bits), 0.2, 1.0 );
813         q /= qf;
814         bits *= qf;
815         if( bits < rcc->buffer_rate/2 )
816             q *= bits*2/rcc->buffer_rate;
817         q = X264_MAX( q0, q );
818     }
819
820     if(lmin==lmax)
821         return lmin;
822     else if(rcc->b_2pass)
823     {
824         double min2 = log(lmin);
825         double max2 = log(lmax);
826         q = (log(q) - min2)/(max2-min2) - 0.5;
827         q = 1.0/(1.0 + exp(-4*q));
828         q = q*(max2-min2) + min2;
829         return exp(q);
830     }
831     else
832         return x264_clip3f(q, lmin, lmax);
833 }
834
835 // update qscale for 1 frame based on actual bits used so far
836 static float rate_estimate_qscale(x264_t *h, int pict_type)
837 {
838     float q;
839     x264_ratecontrol_t *rcc = h->rc;
840     ratecontrol_entry_t rce;
841     double lmin = rcc->lmin[pict_type];
842     double lmax = rcc->lmax[pict_type];
843     int64_t total_bits = 8*(h->stat.i_slice_size[SLICE_TYPE_I]
844                           + h->stat.i_slice_size[SLICE_TYPE_P]
845                           + h->stat.i_slice_size[SLICE_TYPE_B]);
846
847     if( rcc->b_2pass )
848     {
849         rce = *rcc->rce;
850         if(pict_type != rce.pict_type)
851         {
852             x264_log(h, X264_LOG_ERROR, "slice=%c but 2pass stats say %c\n",
853                      slice_type_to_char[pict_type], slice_type_to_char[rce.pict_type]);
854         }
855     }
856
857     if( pict_type == SLICE_TYPE_B )
858     {
859         rcc->last_satd = 0;
860         if(h->fenc->b_kept_as_ref)
861             q = rcc->last_qscale * sqrtf(h->param.rc.f_pb_factor);
862         else
863             q = rcc->last_qscale * h->param.rc.f_pb_factor;
864         return x264_clip3f(q, lmin, lmax);
865     }
866     else
867     {
868         double abr_buffer = 2 * rcc->rate_tolerance * rcc->bitrate;
869         if( rcc->b_2pass )
870         {
871             //FIXME adjust abr_buffer based on distance to the end of the video
872             int64_t diff = total_bits - (int64_t)rce.expected_bits;
873             q = rce.new_qscale;
874             q /= x264_clip3f((double)(abr_buffer - diff) / abr_buffer, .5, 2);
875             if( h->fenc->i_frame > 30 )
876             {
877                 /* Adjust quant based on the difference between
878                  * achieved and expected bitrate so far */
879                 double time = (double)h->fenc->i_frame / rcc->num_entries;
880                 double w = x264_clip3f( time*100, 0.0, 1.0 );
881                 q *= pow( (double)total_bits / rcc->expected_bits_sum, w );
882             }
883             q = x264_clip3f( q, lmin, lmax );
884         }
885         else /* 1pass ABR */
886         {
887             /* Calculate the quantizer which would have produced the desired
888              * average bitrate if it had been applied to all frames so far.
889              * Then modulate that quant based on the current frame's complexity
890              * relative to the average complexity so far (using the 2pass RCEQ).
891              * Then bias the quant up or down if total size so far was far from
892              * the target.
893              * Result: Depending on the value of rate_tolerance, there is a
894              * tradeoff between quality and bitrate precision. But at large
895              * tolerances, the bit distribution approaches that of 2pass. */
896
897             double wanted_bits, overflow, lmin, lmax;
898
899             rcc->last_satd = x264_rc_analyse_slice( h );
900             rcc->short_term_cplxsum *= 0.5;
901             rcc->short_term_cplxcount *= 0.5;
902             rcc->short_term_cplxsum += rcc->last_satd;
903             rcc->short_term_cplxcount ++;
904
905             rce.p_tex_bits = rcc->last_satd;
906             rce.blurred_complexity = rcc->short_term_cplxsum / rcc->short_term_cplxcount;
907             rce.i_tex_bits = 0;
908             rce.mv_bits = 0;
909             rce.p_count = rcc->nmb;
910             rce.i_count = 0;
911             rce.s_count = 0;
912             rce.qscale = 1;
913             rce.pict_type = pict_type;
914             q = get_qscale(h, &rce, rcc->wanted_bits_window / rcc->cplxr_sum, h->fenc->i_frame);
915
916             wanted_bits = h->fenc->i_frame * rcc->bitrate / rcc->fps;
917             abr_buffer *= X264_MAX( 1, sqrt(h->fenc->i_frame/25) );
918             overflow = x264_clip3f( 1.0 + (total_bits - wanted_bits) / abr_buffer, .5, 2 );
919             q *= overflow;
920
921             if( pict_type == SLICE_TYPE_I
922                 /* should test _next_ pict type, but that isn't decided yet */
923                 && rcc->last_non_b_pict_type != SLICE_TYPE_I )
924             {
925                 q = qp2qscale( rcc->accum_p_qp / rcc->accum_p_norm );
926                 q /= fabs( h->param.rc.f_ip_factor );
927                 q = clip_qscale( h, pict_type, q );
928             }
929             else
930             {
931                 if( h->stat.i_slice_count[SLICE_TYPE_P] < 5 )
932                 {
933                     float w = h->stat.i_slice_count[SLICE_TYPE_P] / 5.;
934                     float q2 = qp2qscale(ABR_INIT_QP);
935                     q = q*w + q2*(1-w);
936                 }
937
938                 /* Asymmetric clipping, because symmetric would prevent
939                  * overflow control in areas of rapidly oscillating complexity */
940                 lmin = rcc->last_qscale_for[pict_type] / rcc->lstep;
941                 lmax = rcc->last_qscale_for[pict_type] * rcc->lstep;
942                 if( overflow > 1.1 )
943                     lmax *= rcc->lstep;
944                 else if( overflow < 0.9 )
945                     lmin /= rcc->lstep;
946
947                 q = x264_clip3f(q, lmin, lmax);
948                 q = clip_qscale(h, pict_type, q);
949                 //FIXME use get_diff_limited_q() ?
950             }
951         }
952
953         rcc->last_qscale_for[pict_type] =
954         rcc->last_qscale = q;
955
956         return q;
957     }
958 }
959
960 static int init_pass2( x264_t *h )
961 {
962     x264_ratecontrol_t *rcc = h->rc;
963     uint64_t all_const_bits = 0;
964     uint64_t all_available_bits = (uint64_t)(h->param.rc.i_bitrate * 1000 * (double)rcc->num_entries / rcc->fps);
965     double rate_factor, step, step_mult;
966     double qblur = h->param.rc.f_qblur;
967     double cplxblur = h->param.rc.f_complexity_blur;
968     const int filter_size = (int)(qblur*4) | 1;
969     double expected_bits;
970     double *qscale, *blurred_qscale;
971     int i;
972
973     /* find total/average complexity & const_bits */
974     for(i=0; i<rcc->num_entries; i++){
975         ratecontrol_entry_t *rce = &rcc->entry[i];
976         all_const_bits += rce->misc_bits;
977         rcc->i_cplx_sum[rce->pict_type] += rce->i_tex_bits * rce->qscale;
978         rcc->p_cplx_sum[rce->pict_type] += rce->p_tex_bits * rce->qscale;
979         rcc->mv_bits_sum[rce->pict_type] += rce->mv_bits * rce->qscale;
980         rcc->frame_count[rce->pict_type] ++;
981     }
982
983     if( all_available_bits < all_const_bits)
984     {
985         x264_log(h, X264_LOG_ERROR, "requested bitrate is too low. estimated minimum is %d kbps\n",
986                  (int)(all_const_bits * rcc->fps / (rcc->num_entries * 1000)));
987         return -1;
988     }
989
990     /* Blur complexities, to reduce local fluctuation of QP.
991      * We don't blur the QPs directly, because then one very simple frame
992      * could drag down the QP of a nearby complex frame and give it more
993      * bits than intended. */
994     for(i=0; i<rcc->num_entries; i++){
995         ratecontrol_entry_t *rce = &rcc->entry[i];
996         double weight_sum = 0;
997         double cplx_sum = 0;
998         double weight = 1.0;
999         int j;
1000         /* weighted average of cplx of future frames */
1001         for(j=1; j<cplxblur*2 && j<rcc->num_entries-i; j++){
1002             ratecontrol_entry_t *rcj = &rcc->entry[i+j];
1003             weight *= 1 - pow( (float)rcj->i_count / rcc->nmb, 2 );
1004             if(weight < .0001)
1005                 break;
1006             weight_sum += weight;
1007             cplx_sum += weight * qscale2bits(rcj, 1);
1008         }
1009         /* weighted average of cplx of past frames */
1010         weight = 1.0;
1011         for(j=0; j<=cplxblur*2 && j<=i; j++){
1012             ratecontrol_entry_t *rcj = &rcc->entry[i-j];
1013             weight_sum += weight;
1014             cplx_sum += weight * qscale2bits(rcj, 1);
1015             weight *= 1 - pow( (float)rcj->i_count / rcc->nmb, 2 );
1016             if(weight < .0001)
1017                 break;
1018         }
1019         rce->blurred_complexity = cplx_sum / weight_sum;
1020     }
1021
1022     qscale = x264_malloc(sizeof(double)*rcc->num_entries);
1023     if(filter_size > 1)
1024         blurred_qscale = x264_malloc(sizeof(double)*rcc->num_entries);
1025     else
1026         blurred_qscale = qscale;
1027
1028     /* Search for a factor which, when multiplied by the RCEQ values from
1029      * each frame, adds up to the desired total size.
1030      * There is no exact closed-form solution because of VBV constraints and
1031      * because qscale2bits is not invertible, but we can start with the simple
1032      * approximation of scaling the 1st pass by the ratio of bitrates.
1033      * The search range is probably overkill, but speed doesn't matter here. */
1034
1035     expected_bits = 1;
1036     for(i=0; i<rcc->num_entries; i++)
1037         expected_bits += qscale2bits(&rcc->entry[i], get_qscale(h, &rcc->entry[i], 1.0, i));
1038     step_mult = all_available_bits / expected_bits;
1039
1040     rate_factor = 0;
1041     for(step = 1E4 * step_mult; step > 1E-7 * step_mult; step *= 0.5){
1042         expected_bits = 0;
1043         rate_factor += step;
1044
1045         rcc->last_non_b_pict_type = -1;
1046         rcc->last_accum_p_norm = 1;
1047         rcc->accum_p_norm = 0;
1048         rcc->buffer_fill = rcc->buffer_size * h->param.rc.f_vbv_buffer_init;
1049
1050         /* find qscale */
1051         for(i=0; i<rcc->num_entries; i++){
1052             qscale[i] = get_qscale(h, &rcc->entry[i], rate_factor, i);
1053         }
1054
1055         /* fixed I/B qscale relative to P */
1056         for(i=rcc->num_entries-1; i>=0; i--){
1057             qscale[i] = get_diff_limited_q(h, &rcc->entry[i], qscale[i]);
1058             assert(qscale[i] >= 0);
1059         }
1060
1061         /* smooth curve */
1062         if(filter_size > 1){
1063             assert(filter_size%2==1);
1064             for(i=0; i<rcc->num_entries; i++){
1065                 ratecontrol_entry_t *rce = &rcc->entry[i];
1066                 int j;
1067                 double q=0.0, sum=0.0;
1068
1069                 for(j=0; j<filter_size; j++){
1070                     int index = i+j-filter_size/2;
1071                     double d = index-i;
1072                     double coeff = qblur==0 ? 1.0 : exp(-d*d/(qblur*qblur));
1073                     if(index < 0 || index >= rcc->num_entries) continue;
1074                     if(rce->pict_type != rcc->entry[index].pict_type) continue;
1075                     q += qscale[index] * coeff;
1076                     sum += coeff;
1077                 }
1078                 blurred_qscale[i] = q/sum;
1079             }
1080         }
1081
1082         /* find expected bits */
1083         for(i=0; i<rcc->num_entries; i++){
1084             ratecontrol_entry_t *rce = &rcc->entry[i];
1085             double bits;
1086             rce->new_qscale = clip_qscale(h, rce->pict_type, blurred_qscale[i]);
1087             assert(rce->new_qscale >= 0);
1088             bits = qscale2bits(rce, rce->new_qscale) + rce->misc_bits;
1089
1090             rce->expected_bits = expected_bits;
1091             expected_bits += bits;
1092             update_vbv(h, bits);
1093         }
1094
1095 //printf("expected:%llu available:%llu factor:%lf avgQ:%lf\n", (uint64_t)expected_bits, all_available_bits, rate_factor);
1096         if(expected_bits > all_available_bits) rate_factor -= step;
1097     }
1098
1099     x264_free(qscale);
1100     if(filter_size > 1)
1101         x264_free(blurred_qscale);
1102
1103     if(fabs(expected_bits/all_available_bits - 1.0) > 0.01)
1104     {
1105         double avgq = 0;
1106         for(i=0; i<rcc->num_entries; i++)
1107             avgq += rcc->entry[i].new_qscale;
1108         avgq = qscale2qp(avgq / rcc->num_entries);
1109
1110         x264_log(h, X264_LOG_ERROR, "Error: 2pass curve failed to converge\n");
1111         x264_log(h, X264_LOG_ERROR, "target: %.2f kbit/s, expected: %.2f kbit/s, avg QP: %.4f\n",
1112                  (float)h->param.rc.i_bitrate,
1113                  expected_bits * rcc->fps / (rcc->num_entries * 1000.),
1114                  avgq);
1115         if(expected_bits < all_available_bits && avgq < h->param.rc.i_qp_min + 2)
1116         {
1117             if(h->param.rc.i_qp_min > 0)
1118                 x264_log(h, X264_LOG_ERROR, "try reducing target bitrate or reducing qp_min (currently %d)\n", h->param.rc.i_qp_min);
1119             else
1120                 x264_log(h, X264_LOG_ERROR, "try reducing target bitrate\n");
1121         }
1122         else if(expected_bits > all_available_bits && avgq > h->param.rc.i_qp_max - 2)
1123         {
1124             if(h->param.rc.i_qp_max < 51)
1125                 x264_log(h, X264_LOG_ERROR, "try increasing target bitrate or increasing qp_max (currently %d)\n", h->param.rc.i_qp_max);
1126             else
1127                 x264_log(h, X264_LOG_ERROR, "try increasing target bitrate\n");
1128         }
1129         else
1130             x264_log(h, X264_LOG_ERROR, "internal error\n");
1131     }
1132
1133     return 0;
1134 }
1135
1136