git.sesse.net Git - x264/blob - 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 <math.h>
  29 #include <limits.h>
  30 #include <assert.h>
  31
  32 #include "common/common.h"
  33 #include "common/cpu.h"
  34 #include "ratecontrol.h"
  35
  36 typedef struct
  37 {
  38     int pict_type;
  39     int kept_as_ref;
  40     float qscale;
  41     int mv_bits;
  42     int i_tex_bits;
  43     int p_tex_bits;
  44     int misc_bits;
  45     uint64_t expected_bits;
  46     float new_qscale;
  47     int new_qp;
  48     int i_count;
  49     int p_count;
  50     int s_count;
  51     float blurred_complexity;
  52     char direct_mode;
  53 } ratecontrol_entry_t;
  54
  55 typedef struct
  56 {
  57     double coeff;
  58     double count;
  59     double decay;
  60 } predictor_t;
  61
  62 struct x264_ratecontrol_t
  63 {
  64     /* constants */
  65     int b_abr;
  66     int b_2pass;
  67     int b_vbv;
  68     int b_vbv_min_rate;
  69     double fps;
  70     double bitrate;
  71     double rate_tolerance;
  72     int nmb;                    /* number of macroblocks in a frame */
  73     int qp_constant[5];
  74
  75     /* current frame */
  76     ratecontrol_entry_t *rce;
  77     int qp;                     /* qp for current frame */
  78     int qpm;                    /* qp for current macroblock */
  79     float qpa_rc;               /* average of macroblocks' qp before aq */
  80     float qpa_aq;               /* average of macroblocks' qp after aq */
  81     int qp_force;
  82
  83     /* VBV stuff */
  84     double buffer_size;
  85     double buffer_fill_final;   /* real buffer as of the last finished frame */
  86     double buffer_fill;         /* planned buffer, if all in-progress frames hit their bit budget */
  87     double buffer_rate;         /* # of bits added to buffer_fill after each frame */
  88     predictor_t *pred;          /* predict frame size from satd */
  89
  90     /* ABR stuff */
  91     int    last_satd;
  92     double last_rceq;
  93     double cplxr_sum;           /* sum of bits*qscale/rceq */
  94     double expected_bits_sum;   /* sum of qscale2bits after rceq, ratefactor, and overflow */
  95     double wanted_bits_window;  /* target bitrate * window */
  96     double cbr_decay;
  97     double short_term_cplxsum;
  98     double short_term_cplxcount;
  99     double rate_factor_constant;
 100     double ip_offset;
 101     double pb_offset;
 102
 103     /* 2pass stuff */
 104     FILE *p_stat_file_out;
 105     char *psz_stat_file_tmpname;
 106
 107     int num_entries;            /* number of ratecontrol_entry_ts */
 108     ratecontrol_entry_t *entry; /* FIXME: copy needed data and free this once init is done */
 109     double last_qscale;
 110     double last_qscale_for[5];  /* last qscale for a specific pict type, used for max_diff & ipb factor stuff  */
 111     int last_non_b_pict_type;
 112     double accum_p_qp;          /* for determining I-frame quant */
 113     double accum_p_norm;
 114     double last_accum_p_norm;
 115     double lmin[5];             /* min qscale by frame type */
 116     double lmax[5];
 117     double lstep;               /* max change (multiply) in qscale per frame */
 118     double i_cplx_sum[5];       /* estimated total texture bits in intra MBs at qscale=1 */
 119     double p_cplx_sum[5];
 120     double mv_bits_sum[5];
 121     int frame_count[5];         /* number of frames of each type */
 122
 123     /* MBRC stuff */
 124     double frame_size_planned;
 125     predictor_t *row_pred;
 126     predictor_t row_preds[5];
 127     predictor_t *pred_b_from_p; /* predict B-frame size from P-frame satd */
 128     int bframes;                /* # consecutive B-frames before this P-frame */
 129     int bframe_bits;            /* total cost of those frames */
 130
 131     int i_zones;
 132     x264_zone_t *zones;
 133     x264_zone_t *prev_zone;
 134 };
 135
 136
 137 static int parse_zones( x264_t *h );
 138 static int init_pass2(x264_t *);
 139 static float rate_estimate_qscale( x264_t *h );
 140 static void update_vbv( x264_t *h, int bits );
 141 static void update_vbv_plan( x264_t *h );
 142 static double predict_size( predictor_t *p, double q, double var );
 143 static void update_predictor( predictor_t *p, double q, double var, double bits );
 144 int  x264_rc_analyse_slice( x264_t *h );
 145
 146 /* Terminology:
 147  * qp = h.264's quantizer
 148  * qscale = linearized quantizer = Lagrange multiplier
 149  */
 150 static inline double qp2qscale(double qp)
 151 {
 152     return 0.85 * pow(2.0, ( qp - 12.0 ) / 6.0);
 153 }
 154 static inline double qscale2qp(double qscale)
 155 {
 156     return 12.0 + 6.0 * log(qscale/0.85) / log(2.0);
 157 }
 158
 159 /* Texture bitrate is not quite inversely proportional to qscale,
 160  * probably due the the changing number of SKIP blocks.
 161  * MV bits level off at about qp<=12, because the lambda used
 162  * for motion estimation is constant there. */
 163 static inline double qscale2bits(ratecontrol_entry_t *rce, double qscale)
 164 {
 165     if(qscale<0.1)
 166         qscale = 0.1;
 167     return (rce->i_tex_bits + rce->p_tex_bits + .1) * pow( rce->qscale / qscale, 1.1 )
 168            + rce->mv_bits * pow( X264_MAX(rce->qscale, 1) / X264_MAX(qscale, 1), 0.5 )
 169            + rce->misc_bits;
 170 }
 171
 172
 173 int x264_ratecontrol_new( x264_t *h )
 174 {
 175     x264_ratecontrol_t *rc;
 176     int i;
 177
 178     x264_cpu_restore( h->param.cpu );
 179
 180     rc = h->rc = x264_malloc( h->param.i_threads * sizeof(x264_ratecontrol_t) );
 181     memset( rc, 0, h->param.i_threads * sizeof(x264_ratecontrol_t) );
 182
 183     rc->b_abr = h->param.rc.i_rc_method != X264_RC_CQP && !h->param.rc.b_stat_read;
 184     rc->b_2pass = h->param.rc.i_rc_method == X264_RC_ABR && h->param.rc.b_stat_read;
 185
 186     /* FIXME: use integers */
 187     if(h->param.i_fps_num > 0 && h->param.i_fps_den > 0)
 188         rc->fps = (float) h->param.i_fps_num / h->param.i_fps_den;
 189     else
 190         rc->fps = 25.0;
 191
 192     rc->bitrate = h->param.rc.i_bitrate * 1000.;
 193     rc->rate_tolerance = h->param.rc.f_rate_tolerance;
 194     rc->nmb = h->mb.i_mb_count;
 195     rc->last_non_b_pict_type = -1;
 196     rc->cbr_decay = 1.0;
 197
 198     if( h->param.rc.i_rc_method == X264_RC_CRF && h->param.rc.b_stat_read )
 199     {
 200         x264_log(h, X264_LOG_ERROR, "constant rate-factor is incompatible with 2pass.\n");
 201         return -1;
 202     }
 203     if( h->param.rc.i_vbv_buffer_size )
 204     {
 205         if( h->param.rc.i_rc_method == X264_RC_CQP )
 206             x264_log(h, X264_LOG_WARNING, "VBV is incompatible with constant QP, ignored.\n");
 207         else if( h->param.rc.i_vbv_max_bitrate == 0 )
 208         {
 209             x264_log( h, X264_LOG_DEBUG, "VBV maxrate unspecified, assuming CBR\n" );
 210             h->param.rc.i_vbv_max_bitrate = h->param.rc.i_bitrate;
 211         }
 212     }
 213     if( h->param.rc.i_vbv_max_bitrate < h->param.rc.i_bitrate &&
 214         h->param.rc.i_vbv_max_bitrate > 0)
 215         x264_log(h, X264_LOG_WARNING, "max bitrate less than average bitrate, ignored.\n");
 216     else if( h->param.rc.i_vbv_max_bitrate > 0 &&
 217              h->param.rc.i_vbv_buffer_size > 0 )
 218     {
 219         if( h->param.rc.i_vbv_buffer_size < 3 * h->param.rc.i_vbv_max_bitrate / rc->fps )
 220         {
 221             h->param.rc.i_vbv_buffer_size = 3 * h->param.rc.i_vbv_max_bitrate / rc->fps;
 222             x264_log( h, X264_LOG_WARNING, "VBV buffer size too small, using %d kbit\n",
 223                       h->param.rc.i_vbv_buffer_size );
 224         }
 225         if( h->param.rc.f_vbv_buffer_init > 1. )
 226             h->param.rc.f_vbv_buffer_init = x264_clip3f( h->param.rc.f_vbv_buffer_init / h->param.rc.i_vbv_buffer_size, 0, 1 );
 227         rc->buffer_rate = h->param.rc.i_vbv_max_bitrate * 1000. / rc->fps;
 228         rc->buffer_size = h->param.rc.i_vbv_buffer_size * 1000.;
 229         rc->buffer_fill_final = rc->buffer_size * h->param.rc.f_vbv_buffer_init;
 230         rc->cbr_decay = 1.0 - rc->buffer_rate / rc->buffer_size
 231                       * 0.5 * X264_MAX(0, 1.5 - rc->buffer_rate * rc->fps / rc->bitrate);
 232         rc->b_vbv = 1;
 233         rc->b_vbv_min_rate = !rc->b_2pass
 234                           && h->param.rc.i_rc_method == X264_RC_ABR
 235                           && h->param.rc.i_vbv_max_bitrate <= h->param.rc.i_bitrate;
 236     }
 237     else if( h->param.rc.i_vbv_max_bitrate )
 238     {
 239         x264_log(h, X264_LOG_WARNING, "VBV maxrate specified, but no bufsize.\n");
 240         h->param.rc.i_vbv_max_bitrate = 0;
 241     }
 242     if(rc->rate_tolerance < 0.01) {
 243         x264_log(h, X264_LOG_WARNING, "bitrate tolerance too small, using .01\n");
 244         rc->rate_tolerance = 0.01;
 245     }
 246
 247     h->mb.b_variable_qp = rc->b_vbv && !rc->b_2pass;
 248
 249     if( rc->b_abr )
 250     {
 251         /* FIXME ABR_INIT_QP is actually used only in CRF */
 252 #define ABR_INIT_QP ( h->param.rc.i_rc_method == X264_RC_CRF ? h->param.rc.f_rf_constant : 24 )
 253         rc->accum_p_norm = .01;
 254         rc->accum_p_qp = ABR_INIT_QP * rc->accum_p_norm;
 255         /* estimated ratio that produces a reasonable QP for the first I-frame */
 256         rc->cplxr_sum = .01 * pow( 7.0e5, h->param.rc.f_qcompress ) * pow( h->mb.i_mb_count, 0.5 );
 257         rc->wanted_bits_window = 1.0 * rc->bitrate / rc->fps;
 258         rc->last_non_b_pict_type = SLICE_TYPE_I;
 259     }
 260
 261     if( h->param.rc.i_rc_method == X264_RC_CRF )
 262     {
 263         /* arbitrary rescaling to make CRF somewhat similar to QP */
 264         double base_cplx = h->mb.i_mb_count * (h->param.i_bframe ? 120 : 80);
 265         rc->rate_factor_constant = pow( base_cplx, 1 - h->param.rc.f_qcompress )
 266                                  / qp2qscale( h->param.rc.f_rf_constant );
 267     }
 268
 269     rc->ip_offset = 6.0 * log(h->param.rc.f_ip_factor) / log(2.0);
 270     rc->pb_offset = 6.0 * log(h->param.rc.f_pb_factor) / log(2.0);
 271     rc->qp_constant[SLICE_TYPE_P] = h->param.rc.i_qp_constant;
 272     rc->qp_constant[SLICE_TYPE_I] = x264_clip3( h->param.rc.i_qp_constant - rc->ip_offset + 0.5, 0, 51 );
 273     rc->qp_constant[SLICE_TYPE_B] = x264_clip3( h->param.rc.i_qp_constant + rc->pb_offset + 0.5, 0, 51 );
 274
 275     rc->lstep = pow( 2, h->param.rc.i_qp_step / 6.0 );
 276     rc->last_qscale = qp2qscale(26);
 277     rc->pred = x264_malloc( 5*sizeof(predictor_t) );
 278     rc->pred_b_from_p = x264_malloc( sizeof(predictor_t) );
 279     for( i = 0; i < 5; i++ )
 280     {
 281         rc->last_qscale_for[i] = qp2qscale( ABR_INIT_QP );
 282         rc->lmin[i] = qp2qscale( h->param.rc.i_qp_min );
 283         rc->lmax[i] = qp2qscale( h->param.rc.i_qp_max );
 284         rc->pred[i].coeff= 2.0;
 285         rc->pred[i].count= 1.0;
 286         rc->pred[i].decay= 0.5;
 287         rc->row_preds[i].coeff= .25;
 288         rc->row_preds[i].count= 1.0;
 289         rc->row_preds[i].decay= 0.5;
 290     }
 291     *rc->pred_b_from_p = rc->pred[0];
 292
 293     if( parse_zones( h ) < 0 )
 294     {
 295         x264_log( h, X264_LOG_ERROR, "failed to parse zones\n" );
 296         return -1;
 297     }
 298
 299     /* Load stat file and init 2pass algo */
 300     if( h->param.rc.b_stat_read )
 301     {
 302         char *p, *stats_in, *stats_buf;
 303
 304         /* read 1st pass stats */
 305         assert( h->param.rc.psz_stat_in );
 306         stats_buf = stats_in = x264_slurp_file( h->param.rc.psz_stat_in );
 307         if( !stats_buf )
 308         {
 309             x264_log(h, X264_LOG_ERROR, "ratecontrol_init: can't open stats file\n");
 310             return -1;
 311         }
 312
 313         /* check whether 1st pass options were compatible with current options */
 314         if( !strncmp( stats_buf, "#options:", 9 ) )
 315         {
 316             int i;
 317             char *opts = stats_buf;
 318             stats_in = strchr( stats_buf, '\n' );
 319             if( !stats_in )
 320                 return -1;
 321             *stats_in = '\0';
 322             stats_in++;
 323
 324             if( ( p = strstr( opts, "bframes=" ) ) && sscanf( p, "bframes=%d", &i )
 325                 && h->param.i_bframe != i )
 326             {
 327                 x264_log( h, X264_LOG_ERROR, "different number of B-frames than 1st pass (%d vs %d)\n",
 328                           h->param.i_bframe, i );
 329                 return -1;
 330             }
 331
 332             /* since B-adapt doesn't (yet) take into account B-pyramid,
 333              * the converse is not a problem */
 334             if( strstr( opts, "b_pyramid=1" ) && !h->param.b_bframe_pyramid )
 335                 x264_log( h, X264_LOG_WARNING, "1st pass used B-pyramid, 2nd doesn't\n" );
 336
 337             if( ( p = strstr( opts, "keyint=" ) ) && sscanf( p, "keyint=%d", &i )
 338                 && h->param.i_keyint_max != i )
 339                 x264_log( h, X264_LOG_WARNING, "different keyint than 1st pass (%d vs %d)\n",
 340                           h->param.i_keyint_max, i );
 341
 342             if( strstr( opts, "qp=0" ) && h->param.rc.i_rc_method == X264_RC_ABR )
 343                 x264_log( h, X264_LOG_WARNING, "1st pass was lossless, bitrate prediction will be inaccurate\n" );
 344         }
 345
 346         /* find number of pics */
 347         p = stats_in;
 348         for(i=-1; p; i++)
 349             p = strchr(p+1, ';');
 350         if(i==0)
 351         {
 352             x264_log(h, X264_LOG_ERROR, "empty stats file\n");
 353             return -1;
 354         }
 355         rc->num_entries = i;
 356
 357         if( h->param.i_frame_total < rc->num_entries && h->param.i_frame_total > 0 )
 358         {
 359             x264_log( h, X264_LOG_WARNING, "2nd pass has fewer frames than 1st pass (%d vs %d)\n",
 360                       h->param.i_frame_total, rc->num_entries );
 361         }
 362         if( h->param.i_frame_total > rc->num_entries + h->param.i_bframe )
 363         {
 364             x264_log( h, X264_LOG_ERROR, "2nd pass has more frames than 1st pass (%d vs %d)\n",
 365                       h->param.i_frame_total, rc->num_entries );
 366             return -1;
 367         }
 368
 369         /* FIXME: ugly padding because VfW drops delayed B-frames */
 370         rc->num_entries += h->param.i_bframe;
 371
 372         rc->entry = (ratecontrol_entry_t*) x264_malloc(rc->num_entries * sizeof(ratecontrol_entry_t));
 373         memset(rc->entry, 0, rc->num_entries * sizeof(ratecontrol_entry_t));
 374
 375         /* init all to skipped p frames */
 376         for(i=0; i<rc->num_entries; i++){
 377             ratecontrol_entry_t *rce = &rc->entry[i];
 378             rce->pict_type = SLICE_TYPE_P;
 379             rce->qscale = rce->new_qscale = qp2qscale(20);
 380             rce->misc_bits = rc->nmb + 10;
 381             rce->new_qp = 0;
 382         }
 383
 384         /* read stats */
 385         p = stats_in;
 386         for(i=0; i < rc->num_entries - h->param.i_bframe; i++){
 387             ratecontrol_entry_t *rce;
 388             int frame_number;
 389             char pict_type;
 390             int e;
 391             char *next;
 392             float qp;
 393
 394             next= strchr(p, ';');
 395             if(next){
 396                 (*next)=0; //sscanf is unbelievably slow on looong strings
 397                 next++;
 398             }
 399             e = sscanf(p, " in:%d ", &frame_number);
 400
 401             if(frame_number < 0 || frame_number >= rc->num_entries)
 402             {
 403                 x264_log(h, X264_LOG_ERROR, "bad frame number (%d) at stats line %d\n", frame_number, i);
 404                 return -1;
 405             }
 406             rce = &rc->entry[frame_number];
 407             rce->direct_mode = 0;
 408
 409             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 d:%c",
 410                    &pict_type, &qp, &rce->i_tex_bits, &rce->p_tex_bits,
 411                    &rce->mv_bits, &rce->misc_bits, &rce->i_count, &rce->p_count,
 412                    &rce->s_count, &rce->direct_mode);
 413
 414             switch(pict_type){
 415                 case 'I': rce->kept_as_ref = 1;
 416                 case 'i': rce->pict_type = SLICE_TYPE_I; break;
 417                 case 'P': rce->pict_type = SLICE_TYPE_P; break;
 418                 case 'B': rce->kept_as_ref = 1;
 419                 case 'b': rce->pict_type = SLICE_TYPE_B; break;
 420                 default:  e = -1; break;
 421             }
 422             if(e < 10){
 423                 x264_log(h, X264_LOG_ERROR, "statistics are damaged at line %d, parser out=%d\n", i, e);
 424                 return -1;
 425             }
 426             rce->qscale = qp2qscale(qp);
 427             p = next;
 428         }
 429
 430         x264_free(stats_buf);
 431
 432         if(h->param.rc.i_rc_method == X264_RC_ABR)
 433         {
 434             if(init_pass2(h) < 0) return -1;
 435         } /* else we're using constant quant, so no need to run the bitrate allocation */
 436     }
 437
 438     /* Open output file */
 439     /* If input and output files are the same, output to a temp file
 440      * and move it to the real name only when it's complete */
 441     if( h->param.rc.b_stat_write )
 442     {
 443         char *p;
 444
 445         rc->psz_stat_file_tmpname = x264_malloc( strlen(h->param.rc.psz_stat_out) + 6 );
 446         strcpy( rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out );
 447         strcat( rc->psz_stat_file_tmpname, ".temp" );
 448
 449         rc->p_stat_file_out = fopen( rc->psz_stat_file_tmpname, "wb" );
 450         if( rc->p_stat_file_out == NULL )
 451         {
 452             x264_log(h, X264_LOG_ERROR, "ratecontrol_init: can't open stats file\n");
 453             return -1;
 454         }
 455
 456         p = x264_param2string( &h->param, 1 );
 457         fprintf( rc->p_stat_file_out, "#options: %s\n", p );
 458         x264_free( p );
 459     }
 460
 461     for( i=1; i<h->param.i_threads; i++ )
 462     {
 463         h->thread[i]->rc = rc+i;
 464         rc[i] = rc[0];
 465     }
 466
 467     return 0;
 468 }
 469
 470 static int parse_zone( x264_t *h, x264_zone_t *z, char *p )
 471 {
 472     int len = 0;
 473     char *tok, *saveptr;
 474     z->param = NULL;
 475     z->f_bitrate_factor = 1;
 476     if( 3 <= sscanf(p, "%u,%u,q=%u%n", &z->i_start, &z->i_end, &z->i_qp, &len) )
 477         z->b_force_qp = 1;
 478     else if( 3 <= sscanf(p, "%u,%u,b=%f%n", &z->i_start, &z->i_end, &z->f_bitrate_factor, &len) )
 479         z->b_force_qp = 0;
 480     else if( 2 <= sscanf(p, "%u,%u%n", &z->i_start, &z->i_end, &len) )
 481         z->b_force_qp = 0;
 482     else
 483     {
 484         x264_log( h, X264_LOG_ERROR, "invalid zone: \"%s\"\n", p );
 485         return -1;
 486     }
 487     p += len;
 488     if( !*p )
 489         return 0;
 490     z->param = malloc( sizeof(x264_param_t) );
 491     memcpy( z->param, &h->param, sizeof(x264_param_t) );
 492     while( (tok = strtok_r( p, ",", &saveptr )) )
 493     {
 494         char *val = strchr( tok, '=' );
 495         if( val )
 496         {
 497             *val = '\0';
 498             val++;
 499         }
 500         if( x264_param_parse( z->param, tok, val ) )
 501         {
 502             x264_log( h, X264_LOG_ERROR, "invalid zone param: %s = %s\n", tok, val );
 503             return -1;
 504         }
 505         p = NULL;
 506     }
 507     return 0;
 508 }
 509
 510 static int parse_zones( x264_t *h )
 511 {
 512     x264_ratecontrol_t *rc = h->rc;
 513     int i;
 514     if( h->param.rc.psz_zones && !h->param.rc.i_zones )
 515     {
 516         char *p, *tok, *saveptr;
 517         char *psz_zones = x264_malloc( strlen(h->param.rc.psz_zones)+1 );
 518         strcpy( psz_zones, h->param.rc.psz_zones );
 519         h->param.rc.i_zones = 1;
 520         for( p = psz_zones; *p; p++ )
 521             h->param.rc.i_zones += (*p == '/');
 522         h->param.rc.zones = x264_malloc( h->param.rc.i_zones * sizeof(x264_zone_t) );
 523         p = psz_zones;
 524         for( i = 0; i < h->param.rc.i_zones; i++ )
 525         {
 526             tok = strtok_r( p, "/", &saveptr );
 527             if( !tok || parse_zone( h, &h->param.rc.zones[i], tok ) )
 528                 return -1;
 529             p = NULL;
 530         }
 531         x264_free( psz_zones );
 532     }
 533
 534     if( h->param.rc.i_zones > 0 )
 535     {
 536         for( i = 0; i < h->param.rc.i_zones; i++ )
 537         {
 538             x264_zone_t z = h->param.rc.zones[i];
 539             if( z.i_start < 0 || z.i_start > z.i_end )
 540             {
 541                 x264_log( h, X264_LOG_ERROR, "invalid zone: start=%d end=%d\n",
 542                           z.i_start, z.i_end );
 543                 return -1;
 544             }
 545             else if( !z.b_force_qp && z.f_bitrate_factor <= 0 )
 546             {
 547                 x264_log( h, X264_LOG_ERROR, "invalid zone: bitrate_factor=%f\n",
 548                           z.f_bitrate_factor );
 549                 return -1;
 550             }
 551         }
 552
 553         rc->i_zones = h->param.rc.i_zones + 1;
 554         rc->zones = x264_malloc( rc->i_zones * sizeof(x264_zone_t) );
 555         memcpy( rc->zones+1, h->param.rc.zones, (rc->i_zones-1) * sizeof(x264_zone_t) );
 556
 557         // default zone to fall back to if none of the others match
 558         rc->zones[0].i_start = 0;
 559         rc->zones[0].i_end = INT_MAX;
 560         rc->zones[0].b_force_qp = 0;
 561         rc->zones[0].f_bitrate_factor = 1;
 562         rc->zones[0].param = x264_malloc( sizeof(x264_param_t) );
 563         memcpy( rc->zones[0].param, &h->param, sizeof(x264_param_t) );
 564         for( i = 1; i < rc->i_zones; i++ )
 565         {
 566             if( !rc->zones[i].param )
 567                 rc->zones[i].param = rc->zones[0].param;
 568         }
 569     }
 570
 571     return 0;
 572 }
 573
 574 x264_zone_t *get_zone( x264_t *h, int frame_num )
 575 {
 576     int i;
 577     for( i = h->rc->i_zones-1; i >= 0; i-- )
 578     {
 579         x264_zone_t *z = &h->rc->zones[i];
 580         if( frame_num >= z->i_start && frame_num <= z->i_end )
 581             return z;
 582     }
 583     return NULL;
 584 }
 585
 586 void x264_ratecontrol_summary( x264_t *h )
 587 {
 588     x264_ratecontrol_t *rc = h->rc;
 589     if( rc->b_abr && h->param.rc.i_rc_method == X264_RC_ABR && rc->cbr_decay > .9999 )
 590     {
 591         double base_cplx = h->mb.i_mb_count * (h->param.i_bframe ? 120 : 80);
 592         x264_log( h, X264_LOG_INFO, "final ratefactor: %.2f\n",
 593                   qscale2qp( pow( base_cplx, 1 - h->param.rc.f_qcompress )
 594                              * rc->cplxr_sum / rc->wanted_bits_window ) );
 595     }
 596 }
 597
 598 void x264_ratecontrol_delete( x264_t *h )
 599 {
 600     x264_ratecontrol_t *rc = h->rc;
 601     int i;
 602
 603     if( rc->p_stat_file_out )
 604     {
 605         fclose( rc->p_stat_file_out );
 606         if( h->i_frame >= rc->num_entries - h->param.i_bframe )
 607             if( rename( rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out ) != 0 )
 608             {
 609                 x264_log( h, X264_LOG_ERROR, "failed to rename \"%s\" to \"%s\"\n",
 610                           rc->psz_stat_file_tmpname, h->param.rc.psz_stat_out );
 611             }
 612         x264_free( rc->psz_stat_file_tmpname );
 613     }
 614     x264_free( rc->pred );
 615     x264_free( rc->pred_b_from_p );
 616     x264_free( rc->entry );
 617     if( rc->zones )
 618     {
 619         x264_free( rc->zones[0].param );
 620         if( h->param.rc.psz_zones )
 621             for( i=1; i<rc->i_zones; i++ )
 622                 if( rc->zones[i].param != rc->zones[0].param )
 623                     x264_free( rc->zones[i].param );
 624         x264_free( rc->zones );
 625     }
 626     x264_free( rc );
 627 }
 628
 629 static void accum_p_qp_update( x264_t *h, float qp )
 630 {
 631     x264_ratecontrol_t *rc = h->rc;
 632     rc->accum_p_qp   *= .95;
 633     rc->accum_p_norm *= .95;
 634     rc->accum_p_norm += 1;
 635     if( h->sh.i_type == SLICE_TYPE_I )
 636         rc->accum_p_qp += qp + rc->ip_offset;
 637     else
 638         rc->accum_p_qp += qp;
 639 }
 640
 641 /* Before encoding a frame, choose a QP for it */
 642 void x264_ratecontrol_start( x264_t *h, int i_force_qp )
 643 {
 644     x264_ratecontrol_t *rc = h->rc;
 645     ratecontrol_entry_t *rce = NULL;
 646     x264_zone_t *zone = get_zone( h, h->fenc->i_frame );
 647     float q;
 648
 649     x264_cpu_restore( h->param.cpu );
 650
 651     if( zone && (!rc->prev_zone || zone->param != rc->prev_zone->param) )
 652         x264_encoder_reconfig( h, zone->param );
 653     rc->prev_zone = zone;
 654
 655     rc->qp_force = i_force_qp;
 656
 657     if( h->param.rc.b_stat_read )
 658     {
 659         int frame = h->fenc->i_frame;
 660         assert( frame >= 0 && frame < rc->num_entries );
 661         rce = h->rc->rce = &h->rc->entry[frame];
 662
 663         if( h->sh.i_type == SLICE_TYPE_B
 664             && h->param.analyse.i_direct_mv_pred == X264_DIRECT_PRED_AUTO )
 665         {
 666             h->sh.b_direct_spatial_mv_pred = ( rce->direct_mode == 's' );
 667             h->mb.b_direct_auto_read = ( rce->direct_mode == 's' || rce->direct_mode == 't' );
 668         }
 669     }
 670
 671     if( rc->b_vbv )
 672     {
 673         memset( h->fdec->i_row_bits, 0, h->sps->i_mb_height * sizeof(int) );
 674         rc->row_pred = &rc->row_preds[h->sh.i_type];
 675         update_vbv_plan( h );
 676     }
 677
 678     if( h->sh.i_type != SLICE_TYPE_B )
 679     {
 680         rc->bframes = 0;
 681         while( h->frames.current[rc->bframes] && IS_X264_TYPE_B(h->frames.current[rc->bframes]->i_type) )
 682             rc->bframes++;
 683     }
 684
 685     if( i_force_qp )
 686     {
 687         q = i_force_qp - 1;
 688     }
 689     else if( rc->b_abr )
 690     {
 691         q = qscale2qp( rate_estimate_qscale( h ) );
 692     }
 693     else if( rc->b_2pass )
 694     {
 695         rce->new_qscale = rate_estimate_qscale( h );
 696         q = qscale2qp( rce->new_qscale );
 697     }
 698     else /* CQP */
 699     {
 700         if( h->sh.i_type == SLICE_TYPE_B && h->fdec->b_kept_as_ref )
 701             q = ( rc->qp_constant[ SLICE_TYPE_B ] + rc->qp_constant[ SLICE_TYPE_P ] ) / 2;
 702         else
 703             q = rc->qp_constant[ h->sh.i_type ];
 704
 705         if( zone )
 706         {
 707             if( zone->b_force_qp )
 708                 q += zone->i_qp - rc->qp_constant[SLICE_TYPE_P];
 709             else
 710                 q -= 6*log(zone->f_bitrate_factor)/log(2);
 711         }
 712     }
 713
 714     rc->qpa_rc =
 715     rc->qpa_aq = 0;
 716     h->fdec->f_qp_avg_rc =
 717     h->fdec->f_qp_avg_aq =
 718     rc->qpm =
 719     rc->qp = x264_clip3( (int)(q + 0.5), 0, 51 );
 720     if( rce )
 721         rce->new_qp = rc->qp;
 722
 723     /* accum_p_qp needs to be here so that future frames can benefit from the
 724      * data before this frame is done. but this only works because threading
 725      * guarantees to not re-encode any frames. so the non-threaded case does
 726      * accum_p_qp later. */
 727     if( h->param.i_threads > 1 )
 728         accum_p_qp_update( h, rc->qp );
 729
 730     if( h->sh.i_type != SLICE_TYPE_B )
 731         rc->last_non_b_pict_type = h->sh.i_type;
 732 }
 733
 734 double predict_row_size( x264_t *h, int y, int qp )
 735 {
 736     /* average between two predictors:
 737      * absolute SATD, and scaled bit cost of the colocated row in the previous frame */
 738     x264_ratecontrol_t *rc = h->rc;
 739     double pred_s = predict_size( rc->row_pred, qp2qscale(qp), h->fdec->i_row_satd[y] );
 740     double pred_t = 0;
 741     if( h->sh.i_type != SLICE_TYPE_I
 742         && h->fref0[0]->i_type == h->fdec->i_type
 743         && h->fref0[0]->i_row_satd[y] > 0 )
 744     {
 745         pred_t = h->fref0[0]->i_row_bits[y] * h->fdec->i_row_satd[y] / h->fref0[0]->i_row_satd[y]
 746                  * qp2qscale(h->fref0[0]->i_row_qp[y]) / qp2qscale(qp);
 747     }
 748     if( pred_t == 0 )
 749         pred_t = pred_s;
 750
 751     return (pred_s + pred_t) / 2;
 752 }
 753
 754 double predict_row_size_sum( x264_t *h, int y, int qp )
 755 {
 756     int i;
 757     double bits = 0;
 758     for( i = 0; i <= y; i++ )
 759         bits += h->fdec->i_row_bits[i];
 760     for( i = y+1; i < h->sps->i_mb_height; i++ )
 761         bits += predict_row_size( h, i, qp );
 762     return bits;
 763 }
 764
 765 void x264_ratecontrol_mb( x264_t *h, int bits )
 766 {
 767     x264_ratecontrol_t *rc = h->rc;
 768     const int y = h->mb.i_mb_y;
 769
 770     x264_cpu_restore( h->param.cpu );
 771
 772     h->fdec->i_row_bits[y] += bits;
 773     rc->qpa_rc += rc->qpm;
 774     rc->qpa_aq += h->mb.i_qp;
 775
 776     if( h->mb.i_mb_x != h->sps->i_mb_width - 1 || !rc->b_vbv || rc->b_2pass )
 777         return;
 778
 779     h->fdec->i_row_qp[y] = rc->qpm;
 780
 781     if( h->sh.i_type == SLICE_TYPE_B )
 782     {
 783         /* B-frames shouldn't use lower QP than their reference frames */
 784         if( y < h->sps->i_mb_height-1 )
 785         {
 786             rc->qpm = X264_MAX( rc->qp,
 787                       X264_MIN( h->fref0[0]->i_row_qp[y+1],
 788                                 h->fref1[0]->i_row_qp[y+1] ));
 789         }
 790     }
 791     else
 792     {
 793         update_predictor( rc->row_pred, qp2qscale(rc->qpm), h->fdec->i_row_satd[y], h->fdec->i_row_bits[y] );
 794
 795         /* tweak quality based on difference from predicted size */
 796         if( y < h->sps->i_mb_height-1 && h->stat.i_slice_count[h->sh.i_type] > 0 )
 797         {
 798             int prev_row_qp = h->fdec->i_row_qp[y];
 799             int b0 = predict_row_size_sum( h, y, rc->qpm );
 800             int b1 = b0;
 801             int i_qp_max = X264_MIN( prev_row_qp + h->param.rc.i_qp_step, h->param.rc.i_qp_max );
 802             int i_qp_min = X264_MAX( prev_row_qp - h->param.rc.i_qp_step, h->param.rc.i_qp_min );
 803             float buffer_left_planned = rc->buffer_fill - rc->frame_size_planned;
 804
 805             if( !rc->b_vbv_min_rate )
 806                 i_qp_min = X264_MAX( i_qp_min, h->sh.i_qp );
 807
 808             while( rc->qpm < i_qp_max
 809                    && (b1 > rc->frame_size_planned * 1.15
 810                     || (rc->buffer_fill - b1 < buffer_left_planned * 0.5)))
 811             {
 812                 rc->qpm ++;
 813                 b1 = predict_row_size_sum( h, y, rc->qpm );
 814             }
 815
 816             while( rc->qpm > i_qp_min
 817                    && buffer_left_planned > rc->buffer_size * 0.4
 818                    && ((b1 < rc->frame_size_planned * 0.8 && rc->qpm <= prev_row_qp)
 819                      || b1 < (rc->buffer_fill - rc->buffer_size + rc->buffer_rate) * 1.1) )
 820             {
 821                 rc->qpm --;
 822                 b1 = predict_row_size_sum( h, y, rc->qpm );
 823             }
 824         }
 825     }
 826 }
 827
 828 int x264_ratecontrol_qp( x264_t *h )
 829 {
 830     return h->rc->qpm;
 831 }
 832
 833 /* In 2pass, force the same frame types as in the 1st pass */
 834 int x264_ratecontrol_slice_type( x264_t *h, int frame_num )
 835 {
 836     x264_ratecontrol_t *rc = h->rc;
 837     if( h->param.rc.b_stat_read )
 838     {
 839         if( frame_num >= rc->num_entries )
 840         {
 841             /* We could try to initialize everything required for ABR and
 842              * adaptive B-frames, but that would be complicated.
 843              * So just calculate the average QP used so far. */
 844
 845             h->param.rc.i_qp_constant = (h->stat.i_slice_count[SLICE_TYPE_P] == 0) ? 24
 846                                       : 1 + h->stat.f_slice_qp[SLICE_TYPE_P] / h->stat.i_slice_count[SLICE_TYPE_P];
 847             rc->qp_constant[SLICE_TYPE_P] = x264_clip3( h->param.rc.i_qp_constant, 0, 51 );
 848             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 );
 849             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 );
 850
 851             x264_log(h, X264_LOG_ERROR, "2nd pass has more frames than 1st pass (%d)\n", rc->num_entries);
 852             x264_log(h, X264_LOG_ERROR, "continuing anyway, at constant QP=%d\n", h->param.rc.i_qp_constant);
 853             if( h->param.b_bframe_adaptive )
 854                 x264_log(h, X264_LOG_ERROR, "disabling adaptive B-frames\n");
 855
 856             rc->b_abr = 0;
 857             rc->b_2pass = 0;
 858             h->param.rc.i_rc_method = X264_RC_CQP;
 859             h->param.rc.b_stat_read = 0;
 860             h->param.b_bframe_adaptive = 0;
 861             if( h->param.i_bframe > 1 )
 862                 h->param.i_bframe = 1;
 863             return X264_TYPE_P;
 864         }
 865         switch( rc->entry[frame_num].pict_type )
 866         {
 867             case SLICE_TYPE_I:
 868                 return rc->entry[frame_num].kept_as_ref ? X264_TYPE_IDR : X264_TYPE_I;
 869
 870             case SLICE_TYPE_B:
 871                 return rc->entry[frame_num].kept_as_ref ? X264_TYPE_BREF : X264_TYPE_B;
 872
 873             case SLICE_TYPE_P:
 874             default:
 875                 return X264_TYPE_P;
 876         }
 877     }
 878     else
 879     {
 880         return X264_TYPE_AUTO;
 881     }
 882 }
 883
 884 /* After encoding one frame, save stats and update ratecontrol state */
 885 void x264_ratecontrol_end( x264_t *h, int bits )
 886 {
 887     x264_ratecontrol_t *rc = h->rc;
 888     const int *mbs = h->stat.frame.i_mb_count;
 889     int i;
 890
 891     x264_cpu_restore( h->param.cpu );
 892
 893     h->stat.frame.i_mb_count_skip = mbs[P_SKIP] + mbs[B_SKIP];
 894     h->stat.frame.i_mb_count_i = mbs[I_16x16] + mbs[I_8x8] + mbs[I_4x4];
 895     h->stat.frame.i_mb_count_p = mbs[P_L0] + mbs[P_8x8];
 896     for( i = B_DIRECT; i < B_8x8; i++ )
 897         h->stat.frame.i_mb_count_p += mbs[i];
 898
 899     h->fdec->f_qp_avg_rc = rc->qpa_rc /= h->mb.i_mb_count;
 900     h->fdec->f_qp_avg_aq = rc->qpa_aq /= h->mb.i_mb_count;
 901
 902     if( h->param.rc.b_stat_write )
 903     {
 904         char c_type = h->sh.i_type==SLICE_TYPE_I ? (h->fenc->i_poc==0 ? 'I' : 'i')
 905                     : h->sh.i_type==SLICE_TYPE_P ? 'P'
 906                     : h->fenc->b_kept_as_ref ? 'B' : 'b';
 907         int dir_frame = h->stat.frame.i_direct_score[1] - h->stat.frame.i_direct_score[0];
 908         int dir_avg = h->stat.i_direct_score[1] - h->stat.i_direct_score[0];
 909         char c_direct = h->mb.b_direct_auto_write ?
 910                         ( dir_frame>0 ? 's' : dir_frame<0 ? 't' :
 911                           dir_avg>0 ? 's' : dir_avg<0 ? 't' : '-' )
 912                         : '-';
 913         fprintf( rc->p_stat_file_out,
 914                  "in:%d out:%d type:%c q:%.2f itex:%d ptex:%d mv:%d misc:%d imb:%d pmb:%d smb:%d d:%c;\n",
 915                  h->fenc->i_frame, h->i_frame,
 916                  c_type, rc->qpa_rc,
 917                  h->stat.frame.i_itex_bits, h->stat.frame.i_ptex_bits,
 918                  h->stat.frame.i_hdr_bits, h->stat.frame.i_misc_bits,
 919                  h->stat.frame.i_mb_count_i,
 920                  h->stat.frame.i_mb_count_p,
 921                  h->stat.frame.i_mb_count_skip,
 922                  c_direct);
 923     }
 924
 925     if( rc->b_abr )
 926     {
 927         if( h->sh.i_type != SLICE_TYPE_B )
 928             rc->cplxr_sum += bits * qp2qscale(rc->qpa_rc) / rc->last_rceq;
 929         else
 930         {
 931             /* Depends on the fact that B-frame's QP is an offset from the following P-frame's.
 932              * Not perfectly accurate with B-refs, but good enough. */
 933             rc->cplxr_sum += bits * qp2qscale(rc->qpa_rc) / (rc->last_rceq * fabs(h->param.rc.f_pb_factor));
 934         }
 935         rc->cplxr_sum *= rc->cbr_decay;
 936         rc->wanted_bits_window += rc->bitrate / rc->fps;
 937         rc->wanted_bits_window *= rc->cbr_decay;
 938
 939         if( h->param.i_threads == 1 )
 940             accum_p_qp_update( h, rc->qpa_rc );
 941     }
 942
 943     if( rc->b_2pass )
 944     {
 945         rc->expected_bits_sum += qscale2bits( rc->rce, qp2qscale(rc->rce->new_qp) );
 946     }
 947
 948     if( h->mb.b_variable_qp )
 949     {
 950         if( h->sh.i_type == SLICE_TYPE_B )
 951         {
 952             rc->bframe_bits += bits;
 953             if( !h->frames.current[0] || !IS_X264_TYPE_B(h->frames.current[0]->i_type) )
 954             {
 955                 update_predictor( rc->pred_b_from_p, qp2qscale(rc->qpa_rc),
 956                                   h->fref1[h->i_ref1-1]->i_satd, rc->bframe_bits / rc->bframes );
 957                 rc->bframe_bits = 0;
 958             }
 959         }
 960     }
 961
 962     update_vbv( h, bits );
 963 }
 964
 965 /****************************************************************************
 966  * 2 pass functions
 967  ***************************************************************************/
 968
 969 double x264_eval( char *s, double *const_value, const char **const_name,
 970                   double (**func1)(void *, double), const char **func1_name,
 971                   double (**func2)(void *, double, double), char **func2_name,
 972                   void *opaque );
 973
 974 /**
 975  * modify the bitrate curve from pass1 for one frame
 976  */
 977 static double get_qscale(x264_t *h, ratecontrol_entry_t *rce, double rate_factor, int frame_num)
 978 {
 979     x264_ratecontrol_t *rcc= h->rc;
 980     const int pict_type = rce->pict_type;
 981     double q;
 982     x264_zone_t *zone = get_zone( h, frame_num );
 983
 984     double const_values[]={
 985         rce->i_tex_bits * rce->qscale,
 986         rce->p_tex_bits * rce->qscale,
 987         (rce->i_tex_bits + rce->p_tex_bits) * rce->qscale,
 988         rce->mv_bits * rce->qscale,
 989         (double)rce->i_count / rcc->nmb,
 990         (double)rce->p_count / rcc->nmb,
 991         (double)rce->s_count / rcc->nmb,
 992         rce->pict_type == SLICE_TYPE_I,
 993         rce->pict_type == SLICE_TYPE_P,
 994         rce->pict_type == SLICE_TYPE_B,
 995         h->param.rc.f_qcompress,
 996         rcc->i_cplx_sum[SLICE_TYPE_I] / rcc->frame_count[SLICE_TYPE_I],
 997         rcc->i_cplx_sum[SLICE_TYPE_P] / rcc->frame_count[SLICE_TYPE_P],
 998         rcc->p_cplx_sum[SLICE_TYPE_P] / rcc->frame_count[SLICE_TYPE_P],
 999         rcc->p_cplx_sum[SLICE_TYPE_B] / rcc->frame_count[SLICE_TYPE_B],
1000         (rcc->i_cplx_sum[pict_type] + rcc->p_cplx_sum[pict_type]) / rcc->frame_count[pict_type],
1001         rce->blurred_complexity,
1002         0
1003     };
1004     static const char *const_names[]={
1005         "iTex",
1006         "pTex",
1007         "tex",
1008         "mv",
1009         "iCount",
1010         "pCount",
1011         "sCount",
1012         "isI",
1013         "isP",
1014         "isB",
1015         "qComp",
1016         "avgIITex",
1017         "avgPITex",
1018         "avgPPTex",
1019         "avgBPTex",
1020         "avgTex",
1021         "blurCplx",
1022         NULL
1023     };
1024     static double (*func1[])(void *, double)={
1025 //      (void *)bits2qscale,
1026         (void *)qscale2bits,
1027         NULL
1028     };
1029     static const char *func1_names[]={
1030 //      "bits2qp",
1031         "qp2bits",
1032         NULL
1033     };
1034
1035     q = x264_eval((char*)h->param.rc.psz_rc_eq, const_values, const_names, func1, func1_names, NULL, NULL, rce);
1036
1037     // avoid NaN's in the rc_eq
1038     if(!isfinite(q) || rce->i_tex_bits + rce->p_tex_bits + rce->mv_bits == 0)
1039         q = rcc->last_qscale;
1040     else {
1041         rcc->last_rceq = q;
1042         q /= rate_factor;
1043         rcc->last_qscale = q;
1044     }
1045
1046     if( zone )
1047     {
1048         if( zone->b_force_qp )
1049             q = qp2qscale(zone->i_qp);
1050         else
1051             q /= zone->f_bitrate_factor;
1052     }
1053
1054     return q;
1055 }
1056
1057 static double get_diff_limited_q(x264_t *h, ratecontrol_entry_t *rce, double q)
1058 {
1059     x264_ratecontrol_t *rcc = h->rc;
1060     const int pict_type = rce->pict_type;
1061
1062     // force I/B quants as a function of P quants
1063     const double last_p_q    = rcc->last_qscale_for[SLICE_TYPE_P];
1064     const double last_non_b_q= rcc->last_qscale_for[rcc->last_non_b_pict_type];
1065     if( pict_type == SLICE_TYPE_I )
1066     {
1067         double iq = q;
1068         double pq = qp2qscale( rcc->accum_p_qp / rcc->accum_p_norm );
1069         double ip_factor = fabs( h->param.rc.f_ip_factor );
1070         /* don't apply ip_factor if the following frame is also I */
1071         if( rcc->accum_p_norm <= 0 )
1072             q = iq;
1073         else if( h->param.rc.f_ip_factor < 0 )
1074             q = iq / ip_factor;
1075         else if( rcc->accum_p_norm >= 1 )
1076             q = pq / ip_factor;
1077         else
1078             q = rcc->accum_p_norm * pq / ip_factor + (1 - rcc->accum_p_norm) * iq;
1079     }
1080     else if( pict_type == SLICE_TYPE_B )
1081     {
1082         if( h->param.rc.f_pb_factor > 0 )
1083             q = last_non_b_q;
1084         if( !rce->kept_as_ref )
1085             q *= fabs( h->param.rc.f_pb_factor );
1086     }
1087     else if( pict_type == SLICE_TYPE_P
1088              && rcc->last_non_b_pict_type == SLICE_TYPE_P
1089              && rce->i_tex_bits + rce->p_tex_bits == 0 )
1090     {
1091         q = last_p_q;
1092     }
1093
1094     /* last qscale / qdiff stuff */
1095     if(rcc->last_non_b_pict_type==pict_type
1096        && (pict_type!=SLICE_TYPE_I || rcc->last_accum_p_norm < 1))
1097     {
1098         double last_q = rcc->last_qscale_for[pict_type];
1099         double max_qscale = last_q * rcc->lstep;
1100         double min_qscale = last_q / rcc->lstep;
1101
1102         if     (q > max_qscale) q = max_qscale;
1103         else if(q < min_qscale) q = min_qscale;
1104     }
1105
1106     rcc->last_qscale_for[pict_type] = q;
1107     if(pict_type!=SLICE_TYPE_B)
1108         rcc->last_non_b_pict_type = pict_type;
1109     if(pict_type==SLICE_TYPE_I)
1110     {
1111         rcc->last_accum_p_norm = rcc->accum_p_norm;
1112         rcc->accum_p_norm = 0;
1113         rcc->accum_p_qp = 0;
1114     }
1115     if(pict_type==SLICE_TYPE_P)
1116     {
1117         float mask = 1 - pow( (float)rce->i_count / rcc->nmb, 2 );
1118         rcc->accum_p_qp   = mask * (qscale2qp(q) + rcc->accum_p_qp);
1119         rcc->accum_p_norm = mask * (1 + rcc->accum_p_norm);
1120     }
1121     return q;
1122 }
1123
1124 static double predict_size( predictor_t *p, double q, double var )
1125 {
1126      return p->coeff*var / (q*p->count);
1127 }
1128
1129 static void update_predictor( predictor_t *p, double q, double var, double bits )
1130 {
1131     if( var < 10 )
1132         return;
1133     p->count *= p->decay;
1134     p->coeff *= p->decay;
1135     p->count ++;
1136     p->coeff += bits*q / var;
1137 }
1138
1139 // update VBV after encoding a frame
1140 static void update_vbv( x264_t *h, int bits )
1141 {
1142     x264_ratecontrol_t *rcc = h->rc;
1143     x264_ratecontrol_t *rct = h->thread[0]->rc;
1144
1145     if( rcc->last_satd >= h->mb.i_mb_count )
1146         update_predictor( &rct->pred[h->sh.i_type], qp2qscale(rcc->qpa_rc), rcc->last_satd, bits );
1147
1148     if( !rcc->b_vbv )
1149         return;
1150
1151     rct->buffer_fill_final += rct->buffer_rate - bits;
1152     if( rct->buffer_fill_final < 0 && !rct->b_2pass )
1153         x264_log( h, X264_LOG_WARNING, "VBV underflow (%.0f bits)\n", rct->buffer_fill_final );
1154     rct->buffer_fill_final = x264_clip3f( rct->buffer_fill_final, 0, rct->buffer_size );
1155 }
1156
1157 // provisionally update VBV according to the planned size of all frames currently in progress
1158 static void update_vbv_plan( x264_t *h )
1159 {
1160     x264_ratecontrol_t *rcc = h->rc;
1161     rcc->buffer_fill = h->thread[0]->rc->buffer_fill_final;
1162     if( h->param.i_threads > 1 )
1163     {
1164         int j = h->rc - h->thread[0]->rc;
1165         int i;
1166         for( i=1; i<h->param.i_threads; i++ )
1167         {
1168             x264_t *t = h->thread[ (j+i)%h->param.i_threads ];
1169             double bits = t->rc->frame_size_planned;
1170             if( !t->b_thread_active )
1171                 continue;
1172             rcc->buffer_fill += rcc->buffer_rate - bits;
1173             rcc->buffer_fill = x264_clip3( rcc->buffer_fill, 0, rcc->buffer_size );
1174         }
1175     }
1176 }
1177
1178 // apply VBV constraints and clip qscale to between lmin and lmax
1179 static double clip_qscale( x264_t *h, int pict_type, double q )
1180 {
1181     x264_ratecontrol_t *rcc = h->rc;
1182     double lmin = rcc->lmin[pict_type];
1183     double lmax = rcc->lmax[pict_type];
1184     double q0 = q;
1185
1186     /* B-frames are not directly subject to VBV,
1187      * since they are controlled by the P-frames' QPs.
1188      * FIXME: in 2pass we could modify previous frames' QP too,
1189      *        instead of waiting for the buffer to fill */
1190     if( rcc->b_vbv &&
1191         ( pict_type == SLICE_TYPE_P ||
1192           ( pict_type == SLICE_TYPE_I && rcc->last_non_b_pict_type == SLICE_TYPE_I ) ) )
1193     {
1194         if( rcc->buffer_fill/rcc->buffer_size < 0.5 )
1195             q /= x264_clip3f( 2.0*rcc->buffer_fill/rcc->buffer_size, 0.5, 1.0 );
1196     }
1197
1198     if( rcc->b_vbv && rcc->last_satd > 0 )
1199     {
1200         /* Now a hard threshold to make sure the frame fits in VBV.
1201          * This one is mostly for I-frames. */
1202         double bits = predict_size( &rcc->pred[h->sh.i_type], q, rcc->last_satd );
1203         double qf = 1.0;
1204         if( bits > rcc->buffer_fill/2 )
1205             qf = x264_clip3f( rcc->buffer_fill/(2*bits), 0.2, 1.0 );
1206         q /= qf;
1207         bits *= qf;
1208         if( bits < rcc->buffer_rate/2 )
1209             q *= bits*2/rcc->buffer_rate;
1210         q = X264_MAX( q0, q );
1211
1212         /* Check B-frame complexity, and use up any bits that would
1213          * overflow before the next P-frame. */
1214         if( h->sh.i_type == SLICE_TYPE_P )
1215         {
1216             int nb = rcc->bframes;
1217             double pbbits = bits;
1218             double bbits = predict_size( rcc->pred_b_from_p, q * h->param.rc.f_pb_factor, rcc->last_satd );
1219             double space;
1220
1221             if( bbits > rcc->buffer_rate )
1222                 nb = 0;
1223             pbbits += nb * bbits;
1224
1225             space = rcc->buffer_fill + (1+nb)*rcc->buffer_rate - rcc->buffer_size;
1226             if( pbbits < space )
1227             {
1228                 q *= X264_MAX( pbbits / space,
1229                                bits / (0.5 * rcc->buffer_size) );
1230             }
1231             q = X264_MAX( q0-5, q );
1232         }
1233
1234         if( !rcc->b_vbv_min_rate )
1235             q = X264_MAX( q0, q );
1236     }
1237
1238     if(lmin==lmax)
1239         return lmin;
1240     else if(rcc->b_2pass)
1241     {
1242         double min2 = log(lmin);
1243         double max2 = log(lmax);
1244         q = (log(q) - min2)/(max2-min2) - 0.5;
1245         q = 1.0/(1.0 + exp(-4*q));
1246         q = q*(max2-min2) + min2;
1247         return exp(q);
1248     }
1249     else
1250         return x264_clip3f(q, lmin, lmax);
1251 }
1252
1253 // update qscale for 1 frame based on actual bits used so far
1254 static float rate_estimate_qscale( x264_t *h )
1255 {
1256     float q;
1257     x264_ratecontrol_t *rcc = h->rc;
1258     ratecontrol_entry_t rce;
1259     int pict_type = h->sh.i_type;
1260     double lmin = rcc->lmin[pict_type];
1261     double lmax = rcc->lmax[pict_type];
1262     int64_t total_bits = 8*(h->stat.i_slice_size[SLICE_TYPE_I]
1263                           + h->stat.i_slice_size[SLICE_TYPE_P]
1264                           + h->stat.i_slice_size[SLICE_TYPE_B]);
1265
1266     if( rcc->b_2pass )
1267     {
1268         rce = *rcc->rce;
1269         if(pict_type != rce.pict_type)
1270         {
1271             x264_log(h, X264_LOG_ERROR, "slice=%c but 2pass stats say %c\n",
1272                      slice_type_to_char[pict_type], slice_type_to_char[rce.pict_type]);
1273         }
1274     }
1275
1276     if( pict_type == SLICE_TYPE_B )
1277     {
1278         /* B-frames don't have independent ratecontrol, but rather get the
1279          * average QP of the two adjacent P-frames + an offset */
1280
1281         int i0 = IS_X264_TYPE_I(h->fref0[0]->i_type);
1282         int i1 = IS_X264_TYPE_I(h->fref1[0]->i_type);
1283         int dt0 = abs(h->fenc->i_poc - h->fref0[0]->i_poc);
1284         int dt1 = abs(h->fenc->i_poc - h->fref1[0]->i_poc);
1285         float q0 = h->fref0[0]->f_qp_avg_rc;
1286         float q1 = h->fref1[0]->f_qp_avg_rc;
1287
1288         if( h->fref0[0]->i_type == X264_TYPE_BREF )
1289             q0 -= rcc->pb_offset/2;
1290         if( h->fref1[0]->i_type == X264_TYPE_BREF )
1291             q1 -= rcc->pb_offset/2;
1292
1293         if(i0 && i1)
1294             q = (q0 + q1) / 2 + rcc->ip_offset;
1295         else if(i0)
1296             q = q1;
1297         else if(i1)
1298             q = q0;
1299         else
1300             q = (q0*dt1 + q1*dt0) / (dt0 + dt1);
1301
1302         if(h->fenc->b_kept_as_ref)
1303             q += rcc->pb_offset/2;
1304         else
1305             q += rcc->pb_offset;
1306
1307         rcc->frame_size_planned = predict_size( rcc->pred_b_from_p, q, h->fref1[h->i_ref1-1]->i_satd );
1308         rcc->last_satd = 0;
1309         return qp2qscale(q);
1310     }
1311     else
1312     {
1313         double abr_buffer = 2 * rcc->rate_tolerance * rcc->bitrate;
1314         if( rcc->b_2pass )
1315         {
1316             //FIXME adjust abr_buffer based on distance to the end of the video
1317             int64_t diff = total_bits - (int64_t)rce.expected_bits;
1318             q = rce.new_qscale;
1319             q /= x264_clip3f((double)(abr_buffer - diff) / abr_buffer, .5, 2);
1320             if( h->fenc->i_frame > 30 )
1321             {
1322                 /* Adjust quant based on the difference between
1323                  * achieved and expected bitrate so far */
1324                 double time = (double)h->fenc->i_frame / rcc->num_entries;
1325                 double w = x264_clip3f( time*100, 0.0, 1.0 );
1326                 q *= pow( (double)total_bits / rcc->expected_bits_sum, w );
1327             }
1328             q = x264_clip3f( q, lmin, lmax );
1329         }
1330         else /* 1pass ABR */
1331         {
1332             /* Calculate the quantizer which would have produced the desired
1333              * average bitrate if it had been applied to all frames so far.
1334              * Then modulate that quant based on the current frame's complexity
1335              * relative to the average complexity so far (using the 2pass RCEQ).
1336              * Then bias the quant up or down if total size so far was far from
1337              * the target.
1338              * Result: Depending on the value of rate_tolerance, there is a
1339              * tradeoff between quality and bitrate precision. But at large
1340              * tolerances, the bit distribution approaches that of 2pass. */
1341
1342             double wanted_bits, overflow=1, lmin, lmax;
1343
1344             rcc->last_satd = x264_rc_analyse_slice( h );
1345             rcc->short_term_cplxsum *= 0.5;
1346             rcc->short_term_cplxcount *= 0.5;
1347             rcc->short_term_cplxsum += rcc->last_satd;
1348             rcc->short_term_cplxcount ++;
1349
1350             rce.p_tex_bits = rcc->last_satd;
1351             rce.blurred_complexity = rcc->short_term_cplxsum / rcc->short_term_cplxcount;
1352             rce.i_tex_bits = 0;
1353             rce.mv_bits = 0;
1354             rce.p_count = rcc->nmb;
1355             rce.i_count = 0;
1356             rce.s_count = 0;
1357             rce.qscale = 1;
1358             rce.pict_type = pict_type;
1359
1360             if( h->param.rc.i_rc_method == X264_RC_CRF )
1361             {
1362                 q = get_qscale( h, &rce, rcc->rate_factor_constant, h->fenc->i_frame );
1363             }
1364             else
1365             {
1366                 int i_frame_done = h->fenc->i_frame + 1 - h->param.i_threads;
1367
1368                 q = get_qscale( h, &rce, rcc->wanted_bits_window / rcc->cplxr_sum, h->fenc->i_frame );
1369
1370                 // FIXME is it simpler to keep track of wanted_bits in ratecontrol_end?
1371                 wanted_bits = i_frame_done * rcc->bitrate / rcc->fps;
1372                 if( wanted_bits > 0 )
1373                 {
1374                     abr_buffer *= X264_MAX( 1, sqrt(i_frame_done/25) );
1375                     overflow = x264_clip3f( 1.0 + (total_bits - wanted_bits) / abr_buffer, .5, 2 );
1376                     q *= overflow;
1377                 }
1378             }
1379
1380             if( pict_type == SLICE_TYPE_I && h->param.i_keyint_max > 1
1381                 /* should test _next_ pict type, but that isn't decided yet */
1382                 && rcc->last_non_b_pict_type != SLICE_TYPE_I )
1383             {
1384                 q = qp2qscale( rcc->accum_p_qp / rcc->accum_p_norm );
1385                 q /= fabs( h->param.rc.f_ip_factor );
1386             }
1387             else if( h->i_frame > 0 )
1388             {
1389                 /* Asymmetric clipping, because symmetric would prevent
1390                  * overflow control in areas of rapidly oscillating complexity */
1391                 lmin = rcc->last_qscale_for[pict_type] / rcc->lstep;
1392                 lmax = rcc->last_qscale_for[pict_type] * rcc->lstep;
1393                 if( overflow > 1.1 && h->i_frame > 3 )
1394                     lmax *= rcc->lstep;
1395                 else if( overflow < 0.9 )
1396                     lmin /= rcc->lstep;
1397
1398                 q = x264_clip3f(q, lmin, lmax);
1399             }
1400             else if( h->param.rc.i_rc_method == X264_RC_CRF )
1401             {
1402                 q = qp2qscale( ABR_INIT_QP ) / fabs( h->param.rc.f_ip_factor );
1403             }
1404
1405             //FIXME use get_diff_limited_q() ?
1406             q = clip_qscale( h, pict_type, q );
1407         }
1408
1409         rcc->last_qscale_for[pict_type] =
1410         rcc->last_qscale = q;
1411
1412         if( !rcc->b_2pass && h->fenc->i_frame == 0 )
1413             rcc->last_qscale_for[SLICE_TYPE_P] = q;
1414
1415         rcc->frame_size_planned = predict_size( &rcc->pred[h->sh.i_type], q, rcc->last_satd );
1416         return q;
1417     }
1418 }
1419
1420 void x264_thread_sync_ratecontrol( x264_t *cur, x264_t *prev, x264_t *next )
1421 {
1422     if( cur != prev )
1423     {
1424 #define COPY(var) memcpy(&cur->rc->var, &prev->rc->var, sizeof(cur->rc->var))
1425         /* these vars are updated in x264_ratecontrol_start()
1426          * so copy them from the context that most recently started (prev)
1427          * to the context that's about to start (cur).
1428          */
1429         COPY(accum_p_qp);
1430         COPY(accum_p_norm);
1431         COPY(last_satd);
1432         COPY(last_rceq);
1433         COPY(last_qscale_for);
1434         COPY(last_non_b_pict_type);
1435         COPY(short_term_cplxsum);
1436         COPY(short_term_cplxcount);
1437         COPY(bframes);
1438         COPY(prev_zone);
1439 #undef COPY
1440     }
1441     if( cur != next )
1442     {
1443 #define COPY(var) next->rc->var = cur->rc->var
1444         /* these vars are updated in x264_ratecontrol_end()
1445          * so copy them from the context that most recently ended (cur)
1446          * to the context that's about to end (next)
1447          */
1448         COPY(cplxr_sum);
1449         COPY(expected_bits_sum);
1450         COPY(wanted_bits_window);
1451         COPY(bframe_bits);
1452 #undef COPY
1453     }
1454     //FIXME row_preds[] (not strictly necessary, but would improve prediction)
1455     /* the rest of the variables are either constant or thread-local */
1456 }
1457
1458 static int init_pass2( x264_t *h )
1459 {
1460     x264_ratecontrol_t *rcc = h->rc;
1461     uint64_t all_const_bits = 0;
1462     uint64_t all_available_bits = (uint64_t)(h->param.rc.i_bitrate * 1000. * rcc->num_entries / rcc->fps);
1463     double rate_factor, step, step_mult;
1464     double qblur = h->param.rc.f_qblur;
1465     double cplxblur = h->param.rc.f_complexity_blur;
1466     const int filter_size = (int)(qblur*4) | 1;
1467     double expected_bits;
1468     double *qscale, *blurred_qscale;
1469     int i;
1470
1471     /* find total/average complexity & const_bits */
1472     for(i=0; i<rcc->num_entries; i++){
1473         ratecontrol_entry_t *rce = &rcc->entry[i];
1474         all_const_bits += rce->misc_bits;
1475         rcc->i_cplx_sum[rce->pict_type] += rce->i_tex_bits * rce->qscale;
1476         rcc->p_cplx_sum[rce->pict_type] += rce->p_tex_bits * rce->qscale;
1477         rcc->mv_bits_sum[rce->pict_type] += rce->mv_bits * rce->qscale;
1478         rcc->frame_count[rce->pict_type] ++;
1479     }
1480
1481     if( all_available_bits < all_const_bits)
1482     {
1483         x264_log(h, X264_LOG_ERROR, "requested bitrate is too low. estimated minimum is %d kbps\n",
1484                  (int)(all_const_bits * rcc->fps / (rcc->num_entries * 1000.)));
1485         return -1;
1486     }
1487
1488     /* Blur complexities, to reduce local fluctuation of QP.
1489      * We don't blur the QPs directly, because then one very simple frame
1490      * could drag down the QP of a nearby complex frame and give it more
1491      * bits than intended. */
1492     for(i=0; i<rcc->num_entries; i++){
1493         ratecontrol_entry_t *rce = &rcc->entry[i];
1494         double weight_sum = 0;
1495         double cplx_sum = 0;
1496         double weight = 1.0;
1497         int j;
1498         /* weighted average of cplx of future frames */
1499         for(j=1; j<cplxblur*2 && j<rcc->num_entries-i; j++){
1500             ratecontrol_entry_t *rcj = &rcc->entry[i+j];
1501             weight *= 1 - pow( (float)rcj->i_count / rcc->nmb, 2 );
1502             if(weight < .0001)
1503                 break;
1504             weight_sum += weight;
1505             cplx_sum += weight * (qscale2bits(rcj, 1) - rcj->misc_bits);
1506         }
1507         /* weighted average of cplx of past frames */
1508         weight = 1.0;
1509         for(j=0; j<=cplxblur*2 && j<=i; j++){
1510             ratecontrol_entry_t *rcj = &rcc->entry[i-j];
1511             weight_sum += weight;
1512             cplx_sum += weight * (qscale2bits(rcj, 1) - rcj->misc_bits);
1513             weight *= 1 - pow( (float)rcj->i_count / rcc->nmb, 2 );
1514             if(weight < .0001)
1515                 break;
1516         }
1517         rce->blurred_complexity = cplx_sum / weight_sum;
1518     }
1519
1520     qscale = x264_malloc(sizeof(double)*rcc->num_entries);
1521     if(filter_size > 1)
1522         blurred_qscale = x264_malloc(sizeof(double)*rcc->num_entries);
1523     else
1524         blurred_qscale = qscale;
1525
1526     /* Search for a factor which, when multiplied by the RCEQ values from
1527      * each frame, adds up to the desired total size.
1528      * There is no exact closed-form solution because of VBV constraints and
1529      * because qscale2bits is not invertible, but we can start with the simple
1530      * approximation of scaling the 1st pass by the ratio of bitrates.
1531      * The search range is probably overkill, but speed doesn't matter here. */
1532
1533     expected_bits = 1;
1534     for(i=0; i<rcc->num_entries; i++)
1535         expected_bits += qscale2bits(&rcc->entry[i], get_qscale(h, &rcc->entry[i], 1.0, i));
1536     step_mult = all_available_bits / expected_bits;
1537
1538     rate_factor = 0;
1539     for(step = 1E4 * step_mult; step > 1E-7 * step_mult; step *= 0.5){
1540         expected_bits = 0;
1541         rate_factor += step;
1542
1543         rcc->last_non_b_pict_type = -1;
1544         rcc->last_accum_p_norm = 1;
1545         rcc->accum_p_norm = 0;
1546         rcc->buffer_fill = rcc->buffer_size * h->param.rc.f_vbv_buffer_init;
1547
1548         /* find qscale */
1549         for(i=0; i<rcc->num_entries; i++){
1550             qscale[i] = get_qscale(h, &rcc->entry[i], rate_factor, i);
1551         }
1552
1553         /* fixed I/B qscale relative to P */
1554         for(i=rcc->num_entries-1; i>=0; i--){
1555             qscale[i] = get_diff_limited_q(h, &rcc->entry[i], qscale[i]);
1556             assert(qscale[i] >= 0);
1557         }
1558
1559         /* smooth curve */
1560         if(filter_size > 1){
1561             assert(filter_size%2==1);
1562             for(i=0; i<rcc->num_entries; i++){
1563                 ratecontrol_entry_t *rce = &rcc->entry[i];
1564                 int j;
1565                 double q=0.0, sum=0.0;
1566
1567                 for(j=0; j<filter_size; j++){
1568                     int index = i+j-filter_size/2;
1569                     double d = index-i;
1570                     double coeff = qblur==0 ? 1.0 : exp(-d*d/(qblur*qblur));
1571                     if(index < 0 || index >= rcc->num_entries) continue;
1572                     if(rce->pict_type != rcc->entry[index].pict_type) continue;
1573                     q += qscale[index] * coeff;
1574                     sum += coeff;
1575                 }
1576                 blurred_qscale[i] = q/sum;
1577             }
1578         }
1579
1580         /* find expected bits */
1581         for(i=0; i<rcc->num_entries; i++){
1582             ratecontrol_entry_t *rce = &rcc->entry[i];
1583             double bits;
1584             rce->new_qscale = clip_qscale(h, rce->pict_type, blurred_qscale[i]);
1585             assert(rce->new_qscale >= 0);
1586             bits = qscale2bits(rce, rce->new_qscale);
1587
1588             rce->expected_bits = expected_bits;
1589             expected_bits += bits;
1590             update_vbv(h, bits);
1591             rcc->buffer_fill = rcc->buffer_fill_final;
1592         }
1593
1594 //printf("expected:%llu available:%llu factor:%lf avgQ:%lf\n", (uint64_t)expected_bits, all_available_bits, rate_factor);
1595         if(expected_bits > all_available_bits) rate_factor -= step;
1596     }
1597
1598     x264_free(qscale);
1599     if(filter_size > 1)
1600         x264_free(blurred_qscale);
1601
1602     if(fabs(expected_bits/all_available_bits - 1.0) > 0.01)
1603     {
1604         double avgq = 0;
1605         for(i=0; i<rcc->num_entries; i++)
1606             avgq += rcc->entry[i].new_qscale;
1607         avgq = qscale2qp(avgq / rcc->num_entries);
1608
1609         x264_log(h, X264_LOG_WARNING, "Error: 2pass curve failed to converge\n");
1610         x264_log(h, X264_LOG_WARNING, "target: %.2f kbit/s, expected: %.2f kbit/s, avg QP: %.4f\n",
1611                  (float)h->param.rc.i_bitrate,
1612                  expected_bits * rcc->fps / (rcc->num_entries * 1000.),
1613                  avgq);
1614         if(expected_bits < all_available_bits && avgq < h->param.rc.i_qp_min + 2)
1615         {
1616             if(h->param.rc.i_qp_min > 0)
1617                 x264_log(h, X264_LOG_WARNING, "try reducing target bitrate or reducing qp_min (currently %d)\n", h->param.rc.i_qp_min);
1618             else
1619                 x264_log(h, X264_LOG_WARNING, "try reducing target bitrate\n");
1620         }
1621         else if(expected_bits > all_available_bits && avgq > h->param.rc.i_qp_max - 2)
1622         {
1623             if(h->param.rc.i_qp_max < 51)
1624                 x264_log(h, X264_LOG_WARNING, "try increasing target bitrate or increasing qp_max (currently %d)\n", h->param.rc.i_qp_max);
1625             else
1626                 x264_log(h, X264_LOG_WARNING, "try increasing target bitrate\n");
1627         }
1628         else
1629             x264_log(h, X264_LOG_WARNING, "internal error\n");
1630     }
1631
1632     return 0;
1633 }
1634
1635