git.sesse.net Git - x264/blob - encoder/rdo.c

   1 /*****************************************************************************
   2  * rdo.c: h264 encoder library (rate-distortion optimization)
   3  *****************************************************************************
   4  * Copyright (C) 2005-2008 x264 project
   5  *
   6  * Authors: Loren Merritt <lorenm@u.washington.edu>
   7  *          Fiona Glaser <fiona@x264.com>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02111, USA.
  22  *****************************************************************************/
  23
  24 /* duplicate all the writer functions, just calculating bit cost
  25  * instead of writing the bitstream.
  26  * TODO: use these for fast 1st pass too. */
  27
  28 #define RDO_SKIP_BS 1
  29
  30 /* Transition and size tables for abs<9 MVD and residual coding */
  31 /* Consist of i_prefix-2 1s, one zero, and a bypass sign bit */
  32 static uint8_t cabac_transition_unary[15][128];
  33 static uint16_t cabac_size_unary[15][128];
  34 /* Transition and size tables for abs>9 MVD */
  35 /* Consist of 5 1s and a bypass sign bit */
  36 static uint8_t cabac_transition_5ones[128];
  37 static uint16_t cabac_size_5ones[128];
  38
  39 /* CAVLC: produces exactly the same bit count as a normal encode */
  40 /* this probably still leaves some unnecessary computations */
  41 #define bs_write1(s,v)     ((s)->i_bits_encoded += 1)
  42 #define bs_write(s,n,v)    ((s)->i_bits_encoded += (n))
  43 #define bs_write_ue(s,v)   ((s)->i_bits_encoded += bs_size_ue(v))
  44 #define bs_write_se(s,v)   ((s)->i_bits_encoded += bs_size_se(v))
  45 #define bs_write_te(s,v,l) ((s)->i_bits_encoded += bs_size_te(v,l))
  46 #define x264_macroblock_write_cavlc  static x264_macroblock_size_cavlc
  47 #include "cavlc.c"
  48
  49 /* CABAC: not exactly the same. x264_cabac_size_decision() keeps track of
  50  * fractional bits, but only finite precision. */
  51 #undef  x264_cabac_encode_decision
  52 #undef  x264_cabac_encode_decision_noup
  53 #define x264_cabac_encode_decision(c,x,v) x264_cabac_size_decision(c,x,v)
  54 #define x264_cabac_encode_decision_noup(c,x,v) x264_cabac_size_decision_noup(c,x,v)
  55 #define x264_cabac_encode_terminal(c)     ((c)->f8_bits_encoded += 7)
  56 #define x264_cabac_encode_bypass(c,v)     ((c)->f8_bits_encoded += 256)
  57 #define x264_cabac_encode_ue_bypass(c,e,v) ((c)->f8_bits_encoded += (bs_size_ue_big(v+(1<<e)-1)-e)<<8)
  58 #define x264_macroblock_write_cabac  static x264_macroblock_size_cabac
  59 #include "cabac.c"
  60
  61 #define COPY_CABAC h->mc.memcpy_aligned( &cabac_tmp.f8_bits_encoded, &h->cabac.f8_bits_encoded, \
  62         sizeof(x264_cabac_t) - offsetof(x264_cabac_t,f8_bits_encoded) )
  63
  64 static inline uint64_t cached_hadamard( x264_t *h, int pixel, int x, int y )
  65 {
  66     static const uint8_t hadamard_shift_x[4] = {4,   4,   3,   3};
  67     static const uint8_t hadamard_shift_y[4] = {4-0, 3-0, 4-1, 3-1};
  68     static const uint8_t  hadamard_offset[4] = {0,   1,   3,   5};
  69     int cache_index = (x >> hadamard_shift_x[pixel]) + (y >> hadamard_shift_y[pixel])
  70                     + hadamard_offset[pixel];
  71     uint64_t res = h->mb.pic.fenc_hadamard_cache[cache_index];
  72     if( res )
  73         return res - 1;
  74     else
  75     {
  76         uint8_t *fenc = h->mb.pic.p_fenc[0] + x + y*FENC_STRIDE;
  77         res = h->pixf.hadamard_ac[pixel]( fenc, FENC_STRIDE );
  78         h->mb.pic.fenc_hadamard_cache[cache_index] = res + 1;
  79         return res;
  80     }
  81 }
  82
  83 static inline int cached_satd( x264_t *h, int pixel, int x, int y )
  84 {
  85     static const uint8_t satd_shift_x[3] = {3,   2,   2};
  86     static const uint8_t satd_shift_y[3] = {2-1, 3-2, 2-2};
  87     static const uint8_t  satd_offset[3] = {0,   8,   16};
  88     ALIGNED_16( static uint8_t zero[16] );
  89     int cache_index = (x >> satd_shift_x[pixel - PIXEL_8x4]) + (y >> satd_shift_y[pixel - PIXEL_8x4])
  90                     + satd_offset[pixel - PIXEL_8x4];
  91     int res = h->mb.pic.fenc_satd_cache[cache_index];
  92     if( res )
  93         return res - 1;
  94     else
  95     {
  96         uint8_t *fenc = h->mb.pic.p_fenc[0] + x + y*FENC_STRIDE;
  97         int dc = h->pixf.sad[pixel]( fenc, FENC_STRIDE, zero, 0 ) >> 1;
  98         res = h->pixf.satd[pixel]( fenc, FENC_STRIDE, zero, 0 ) - dc;
  99         h->mb.pic.fenc_satd_cache[cache_index] = res + 1;
 100         return res;
 101     }
 102 }
 103
 104 /* Psy RD distortion metric: SSD plus "Absolute Difference of Complexities" */
 105 /* SATD and SA8D are used to measure block complexity. */
 106 /* The difference between SATD and SA8D scores are both used to avoid bias from the DCT size.  Using SATD */
 107 /* only, for example, results in overusage of 8x8dct, while the opposite occurs when using SA8D. */
 108
 109 /* FIXME:  Is there a better metric than averaged SATD/SA8D difference for complexity difference? */
 110 /* Hadamard transform is recursive, so a SATD+SA8D can be done faster by taking advantage of this fact. */
 111 /* This optimization can also be used in non-RD transform decision. */
 112
 113 static inline int ssd_plane( x264_t *h, int size, int p, int x, int y )
 114 {
 115     ALIGNED_16(static uint8_t zero[16]);
 116     int satd = 0;
 117     uint8_t *fdec = h->mb.pic.p_fdec[p] + x + y*FDEC_STRIDE;
 118     uint8_t *fenc = h->mb.pic.p_fenc[p] + x + y*FENC_STRIDE;
 119     if( p == 0 && h->mb.i_psy_rd )
 120     {
 121         /* If the plane is smaller than 8x8, we can't do an SA8D; this probably isn't a big problem. */
 122         if( size <= PIXEL_8x8 )
 123         {
 124             uint64_t fdec_acs = h->pixf.hadamard_ac[size]( fdec, FDEC_STRIDE );
 125             uint64_t fenc_acs = cached_hadamard( h, size, x, y );
 126             satd = abs((int32_t)fdec_acs - (int32_t)fenc_acs)
 127                  + abs((int32_t)(fdec_acs>>32) - (int32_t)(fenc_acs>>32));
 128             satd >>= 1;
 129         }
 130         else
 131         {
 132             int dc = h->pixf.sad[size]( fdec, FDEC_STRIDE, zero, 0 ) >> 1;
 133             satd = abs(h->pixf.satd[size]( fdec, FDEC_STRIDE, zero, 0 ) - dc - cached_satd( h, size, x, y ));
 134         }
 135         satd = (satd * h->mb.i_psy_rd * h->mb.i_psy_rd_lambda + 128) >> 8;
 136     }
 137     return h->pixf.ssd[size](fenc, FENC_STRIDE, fdec, FDEC_STRIDE) + satd;
 138 }
 139
 140 static inline int ssd_mb( x264_t *h )
 141 {
 142     int chromassd = ssd_plane(h, PIXEL_8x8, 1, 0, 0) + ssd_plane(h, PIXEL_8x8, 2, 0, 0);
 143     chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
 144     return ssd_plane(h, PIXEL_16x16, 0, 0, 0) + chromassd;
 145 }
 146
 147 static int x264_rd_cost_mb( x264_t *h, int i_lambda2 )
 148 {
 149     int b_transform_bak = h->mb.b_transform_8x8;
 150     int i_ssd;
 151     int i_bits;
 152     int type_bak = h->mb.i_type;
 153
 154     x264_macroblock_encode( h );
 155
 156     i_ssd = ssd_mb( h );
 157
 158     if( IS_SKIP( h->mb.i_type ) )
 159     {
 160         i_bits = (1 * i_lambda2 + 128) >> 8;
 161     }
 162     else if( h->param.b_cabac )
 163     {
 164         x264_cabac_t cabac_tmp;
 165         COPY_CABAC;
 166         x264_macroblock_size_cabac( h, &cabac_tmp );
 167         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 32768 ) >> 16;
 168     }
 169     else
 170     {
 171         x264_macroblock_size_cavlc( h );
 172         i_bits = ( h->out.bs.i_bits_encoded * i_lambda2 + 128 ) >> 8;
 173     }
 174
 175     h->mb.b_transform_8x8 = b_transform_bak;
 176     h->mb.i_type = type_bak;
 177
 178     return i_ssd + i_bits;
 179 }
 180
 181 /* partition RD functions use 8 bits more precision to avoid large rounding errors at low QPs */
 182
 183 static uint64_t x264_rd_cost_subpart( x264_t *h, int i_lambda2, int i4, int i_pixel )
 184 {
 185     uint64_t i_ssd, i_bits;
 186
 187     x264_macroblock_encode_p4x4( h, i4 );
 188     if( i_pixel == PIXEL_8x4 )
 189         x264_macroblock_encode_p4x4( h, i4+1 );
 190     if( i_pixel == PIXEL_4x8 )
 191         x264_macroblock_encode_p4x4( h, i4+2 );
 192
 193     i_ssd = ssd_plane( h, i_pixel, 0, block_idx_x[i4]*4, block_idx_y[i4]*4 );
 194
 195     if( h->param.b_cabac )
 196     {
 197         x264_cabac_t cabac_tmp;
 198         COPY_CABAC;
 199         x264_subpartition_size_cabac( h, &cabac_tmp, i4, i_pixel );
 200         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
 201     }
 202     else
 203     {
 204         i_bits = x264_subpartition_size_cavlc( h, i4, i_pixel );
 205     }
 206
 207     return (i_ssd<<8) + i_bits;
 208 }
 209
 210 uint64_t x264_rd_cost_part( x264_t *h, int i_lambda2, int i4, int i_pixel )
 211 {
 212     uint64_t i_ssd, i_bits;
 213     int i8 = i4 >> 2;
 214     int chromassd;
 215
 216     if( i_pixel == PIXEL_16x16 )
 217     {
 218         int i_cost = x264_rd_cost_mb( h, i_lambda2 );
 219         return i_cost;
 220     }
 221
 222     if( i_pixel > PIXEL_8x8 )
 223         return x264_rd_cost_subpart( h, i_lambda2, i4, i_pixel );
 224
 225     h->mb.i_cbp_luma = 0;
 226
 227     x264_macroblock_encode_p8x8( h, i8 );
 228     if( i_pixel == PIXEL_16x8 )
 229         x264_macroblock_encode_p8x8( h, i8+1 );
 230     if( i_pixel == PIXEL_8x16 )
 231         x264_macroblock_encode_p8x8( h, i8+2 );
 232
 233     chromassd = ssd_plane( h, i_pixel+3, 1, (i8&1)*4, (i8>>1)*4 )
 234               + ssd_plane( h, i_pixel+3, 2, (i8&1)*4, (i8>>1)*4 );
 235     chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
 236     i_ssd = ssd_plane( h, i_pixel,   0, (i8&1)*8, (i8>>1)*8 ) + chromassd;
 237
 238     if( h->param.b_cabac )
 239     {
 240         x264_cabac_t cabac_tmp;
 241         COPY_CABAC;
 242         x264_partition_size_cabac( h, &cabac_tmp, i8, i_pixel );
 243         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
 244     }
 245     else
 246     {
 247         i_bits = x264_partition_size_cavlc( h, i8, i_pixel ) * i_lambda2;
 248     }
 249
 250     return (i_ssd<<8) + i_bits;
 251 }
 252
 253 static uint64_t x264_rd_cost_i8x8( x264_t *h, int i_lambda2, int i8, int i_mode )
 254 {
 255     uint64_t i_ssd, i_bits;
 256     h->mb.i_cbp_luma &= ~(1<<i8);
 257     h->mb.b_transform_8x8 = 1;
 258
 259     x264_mb_encode_i8x8( h, i8, h->mb.i_qp );
 260     i_ssd = ssd_plane( h, PIXEL_8x8, 0, (i8&1)*8, (i8>>1)*8 );
 261
 262     if( h->param.b_cabac )
 263     {
 264         x264_cabac_t cabac_tmp;
 265         COPY_CABAC;
 266         x264_partition_i8x8_size_cabac( h, &cabac_tmp, i8, i_mode );
 267         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
 268     }
 269     else
 270     {
 271         i_bits = x264_partition_i8x8_size_cavlc( h, i8, i_mode ) * i_lambda2;
 272     }
 273
 274     return (i_ssd<<8) + i_bits;
 275 }
 276
 277 static uint64_t x264_rd_cost_i4x4( x264_t *h, int i_lambda2, int i4, int i_mode )
 278 {
 279     uint64_t i_ssd, i_bits;
 280
 281     x264_mb_encode_i4x4( h, i4, h->mb.i_qp );
 282     i_ssd = ssd_plane( h, PIXEL_4x4, 0, block_idx_x[i4]*4, block_idx_y[i4]*4 );
 283
 284     if( h->param.b_cabac )
 285     {
 286         x264_cabac_t cabac_tmp;
 287         COPY_CABAC;
 288         x264_partition_i4x4_size_cabac( h, &cabac_tmp, i4, i_mode );
 289         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
 290     }
 291     else
 292     {
 293         i_bits = x264_partition_i4x4_size_cavlc( h, i4, i_mode ) * i_lambda2;
 294     }
 295
 296     return (i_ssd<<8) + i_bits;
 297 }
 298
 299 static uint64_t x264_rd_cost_i8x8_chroma( x264_t *h, int i_lambda2, int i_mode, int b_dct )
 300 {
 301     uint64_t i_ssd, i_bits;
 302
 303     if( b_dct )
 304         x264_mb_encode_8x8_chroma( h, 0, h->mb.i_chroma_qp );
 305     i_ssd = ssd_plane( h, PIXEL_8x8, 1, 0, 0 ) +
 306             ssd_plane( h, PIXEL_8x8, 2, 0, 0 );
 307
 308     h->mb.i_chroma_pred_mode = i_mode;
 309
 310     if( h->param.b_cabac )
 311     {
 312         x264_cabac_t cabac_tmp;
 313         COPY_CABAC;
 314         x264_i8x8_chroma_size_cabac( h, &cabac_tmp );
 315         i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
 316     }
 317     else
 318     {
 319         i_bits = x264_i8x8_chroma_size_cavlc( h ) * i_lambda2;
 320     }
 321
 322     return (i_ssd<<8) + i_bits;
 323 }
 324 /****************************************************************************
 325  * Trellis RD quantization
 326  ****************************************************************************/
 327
 328 #define TRELLIS_SCORE_MAX ((uint64_t)1<<50)
 329 #define CABAC_SIZE_BITS 8
 330 #define SSD_WEIGHT_BITS 5
 331 #define LAMBDA_BITS 4
 332
 333 /* precalculate the cost of coding various combinations of bits in a single context */
 334 void x264_rdo_init( void )
 335 {
 336     int i_prefix, i_ctx, i;
 337     for( i_prefix = 0; i_prefix < 15; i_prefix++ )
 338     {
 339         for( i_ctx = 0; i_ctx < 128; i_ctx++ )
 340         {
 341             int f8_bits = 0;
 342             uint8_t ctx = i_ctx;
 343
 344             for( i = 1; i < i_prefix; i++ )
 345                 f8_bits += x264_cabac_size_decision2( &ctx, 1 );
 346             if( i_prefix > 0 && i_prefix < 14 )
 347                 f8_bits += x264_cabac_size_decision2( &ctx, 0 );
 348             f8_bits += 1 << CABAC_SIZE_BITS; //sign
 349
 350             cabac_size_unary[i_prefix][i_ctx] = f8_bits;
 351             cabac_transition_unary[i_prefix][i_ctx] = ctx;
 352         }
 353     }
 354     for( i_ctx = 0; i_ctx < 128; i_ctx++ )
 355     {
 356         int f8_bits = 0;
 357         uint8_t ctx = i_ctx;
 358
 359         for( i = 0; i < 5; i++ )
 360             f8_bits += x264_cabac_size_decision2( &ctx, 1 );
 361         f8_bits += 1 << CABAC_SIZE_BITS; //sign
 362
 363         cabac_size_5ones[i_ctx] = f8_bits;
 364         cabac_transition_5ones[i_ctx] = ctx;
 365     }
 366 }
 367
 368 typedef struct {
 369     int64_t score;
 370     int level_idx; // index into level_tree[]
 371     uint8_t cabac_state[10]; //just the contexts relevant to coding abs_level_m1
 372 } trellis_node_t;
 373
 374 // TODO:
 375 // save cabac state between blocks?
 376 // use trellis' RD score instead of x264_mb_decimate_score?
 377 // code 8x8 sig/last flags forwards with deadzone and save the contexts at
 378 //   each position?
 379 // change weights when using CQMs?
 380
 381 // possible optimizations:
 382 // make scores fit in 32bit
 383 // save quantized coefs during rd, to avoid a duplicate trellis in the final encode
 384 // if trellissing all MBRD modes, finish SSD calculation so we can skip all of
 385 //   the normal dequant/idct/ssd/cabac
 386
 387 // the unquant_mf here is not the same as dequant_mf:
 388 // in normal operation (dct->quant->dequant->idct) the dct and idct are not
 389 // normalized. quant/dequant absorb those scaling factors.
 390 // in this function, we just do (quant->unquant) and want the output to be
 391 // comparable to the input. so unquant is the direct inverse of quant,
 392 // and uses the dct scaling factors, not the idct ones.
 393
 394 static ALWAYS_INLINE int quant_trellis_cabac( x264_t *h, int16_t *dct,
 395                                  const uint16_t *quant_mf, const int *unquant_mf,
 396                                  const int *coef_weight, const uint8_t *zigzag,
 397                                  int i_ctxBlockCat, int i_lambda2, int b_ac, int dc, int i_coefs, int idx )
 398 {
 399     int abs_coefs[64], signs[64];
 400     trellis_node_t nodes[2][8];
 401     trellis_node_t *nodes_cur = nodes[0];
 402     trellis_node_t *nodes_prev = nodes[1];
 403     trellis_node_t *bnode;
 404     const int b_interlaced = h->mb.b_interlaced;
 405     uint8_t *cabac_state_sig = &h->cabac.state[ significant_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ];
 406     uint8_t *cabac_state_last = &h->cabac.state[ last_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ];
 407     const int f = 1 << 15; // no deadzone
 408     int i_last_nnz;
 409     int i, j;
 410
 411     // (# of coefs) * (# of ctx) * (# of levels tried) = 1024
 412     // we don't need to keep all of those: (# of coefs) * (# of ctx) would be enough,
 413     // but it takes more time to remove dead states than you gain in reduced memory.
 414     struct {
 415         uint16_t abs_level;
 416         uint16_t next;
 417     } level_tree[64*8*2];
 418     int i_levels_used = 1;
 419
 420     /* init coefs */
 421     for( i = i_coefs-1; i >= b_ac; i-- )
 422         if( (unsigned)(dct[zigzag[i]] * (dc?quant_mf[0]>>1:quant_mf[zigzag[i]]) + f-1) >= 2*f )
 423             break;
 424
 425     if( i < b_ac )
 426     {
 427         /* We only need to memset an empty 4x4 block.  8x8 can be
 428            implicitly emptied via zero nnz, as can dc. */
 429         if( i_coefs == 16 && !dc )
 430             memset( dct, 0, 16 * sizeof(int16_t) );
 431         return 0;
 432     }
 433
 434     i_last_nnz = i;
 435
 436     for( ; i >= b_ac; i-- )
 437     {
 438         int coef = dct[zigzag[i]];
 439         abs_coefs[i] = abs(coef);
 440         signs[i] = coef < 0 ? -1 : 1;
 441     }
 442
 443     /* init trellis */
 444     for( i = 1; i < 8; i++ )
 445         nodes_cur[i].score = TRELLIS_SCORE_MAX;
 446     nodes_cur[0].score = 0;
 447     nodes_cur[0].level_idx = 0;
 448     level_tree[0].abs_level = 0;
 449     level_tree[0].next = 0;
 450
 451     // coefs are processed in reverse order, because that's how the abs value is coded.
 452     // last_coef and significant_coef flags are normally coded in forward order, but
 453     // we have to reverse them to match the levels.
 454     // in 4x4 blocks, last_coef and significant_coef use a separate context for each
 455     // position, so the order doesn't matter, and we don't even have to update their contexts.
 456     // in 8x8 blocks, some positions share contexts, so we'll just have to hope that
 457     // cabac isn't too sensitive.
 458
 459     memcpy( nodes_cur[0].cabac_state, &h->cabac.state[ coeff_abs_level_m1_offset[i_ctxBlockCat] ], 10 );
 460
 461     for( i = i_last_nnz; i >= b_ac; i-- )
 462     {
 463         int i_coef = abs_coefs[i];
 464         int q = ( f + i_coef * (dc?quant_mf[0]>>1:quant_mf[zigzag[i]]) ) >> 16;
 465         int abs_level;
 466         int cost_sig[2], cost_last[2];
 467         trellis_node_t n;
 468
 469         // skip 0s: this doesn't affect the output, but saves some unnecessary computation.
 470         if( q == 0 )
 471         {
 472             // no need to calculate ssd of 0s: it's the same in all nodes.
 473             // no need to modify level_tree for ctx=0: it starts with an infinite loop of 0s.
 474             int sigindex = i_coefs == 64 ? significant_coeff_flag_offset_8x8[b_interlaced][i] : i;
 475             const uint32_t cost_sig0 = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 0 )
 476                                      * (uint64_t)i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
 477             for( j = 1; j < 8; j++ )
 478             {
 479                 if( nodes_cur[j].score != TRELLIS_SCORE_MAX )
 480                 {
 481 #define SET_LEVEL(n,l) \
 482                     level_tree[i_levels_used].abs_level = l; \
 483                     level_tree[i_levels_used].next = n.level_idx; \
 484                     n.level_idx = i_levels_used; \
 485                     i_levels_used++;
 486
 487                     SET_LEVEL( nodes_cur[j], 0 );
 488                     nodes_cur[j].score += cost_sig0;
 489                 }
 490             }
 491             continue;
 492         }
 493
 494         XCHG( trellis_node_t*, nodes_cur, nodes_prev );
 495
 496         for( j = 0; j < 8; j++ )
 497             nodes_cur[j].score = TRELLIS_SCORE_MAX;
 498
 499         if( i < i_coefs-1 )
 500         {
 501             int sigindex = i_coefs == 64 ? significant_coeff_flag_offset_8x8[b_interlaced][i] : i;
 502             int lastindex = i_coefs == 64 ? last_coeff_flag_offset_8x8[i] : i;
 503             cost_sig[0] = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 0 );
 504             cost_sig[1] = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 1 );
 505             cost_last[0] = x264_cabac_size_decision_noup2( &cabac_state_last[lastindex], 0 );
 506             cost_last[1] = x264_cabac_size_decision_noup2( &cabac_state_last[lastindex], 1 );
 507         }
 508         else
 509         {
 510             cost_sig[0] = cost_sig[1] = 0;
 511             cost_last[0] = cost_last[1] = 0;
 512         }
 513
 514         // there are a few cases where increasing the coeff magnitude helps,
 515         // but it's only around .003 dB, and skipping them ~doubles the speed of trellis.
 516         // could also try q-2: that sometimes helps, but also sometimes decimates blocks
 517         // that are better left coded, especially at QP > 40.
 518         for( abs_level = q; abs_level >= q-1; abs_level-- )
 519         {
 520             int unquant_abs_level = (((dc?unquant_mf[0]<<1:unquant_mf[zigzag[i]]) * abs_level + 128) >> 8);
 521             int d = i_coef - unquant_abs_level;
 522             int64_t ssd;
 523             /* Psy trellis: bias in favor of higher AC coefficients in the reconstructed frame. */
 524             if( h->mb.i_psy_trellis && i && !dc && i_ctxBlockCat != DCT_CHROMA_AC )
 525             {
 526                 int orig_coef = (i_coefs == 64) ? h->mb.pic.fenc_dct8[idx][zigzag[i]] : h->mb.pic.fenc_dct4[idx][zigzag[i]];
 527                 int predicted_coef = orig_coef - i_coef * signs[i];
 528                 int psy_value = h->mb.i_psy_trellis * abs(predicted_coef + unquant_abs_level * signs[i]);
 529                 int psy_weight = (i_coefs == 64) ? x264_dct8_weight_tab[zigzag[i]] : x264_dct4_weight_tab[zigzag[i]];
 530                 ssd = (int64_t)d*d * coef_weight[i] - psy_weight * psy_value;
 531             }
 532             else
 533             /* FIXME: for i16x16 dc is this weight optimal? */
 534                 ssd = (int64_t)d*d * (dc?256:coef_weight[i]);
 535
 536             for( j = 0; j < 8; j++ )
 537             {
 538                 int node_ctx = j;
 539                 if( nodes_prev[j].score == TRELLIS_SCORE_MAX )
 540                     continue;
 541                 n = nodes_prev[j];
 542
 543                 /* code the proposed level, and count how much entropy it would take */
 544                 if( abs_level || node_ctx )
 545                 {
 546                     unsigned f8_bits = cost_sig[ abs_level != 0 ];
 547                     if( abs_level )
 548                     {
 549                         const int i_prefix = X264_MIN( abs_level - 1, 14 );
 550                         f8_bits += cost_last[ node_ctx == 0 ];
 551                         f8_bits += x264_cabac_size_decision2( &n.cabac_state[coeff_abs_level1_ctx[node_ctx]], i_prefix > 0 );
 552                         if( i_prefix > 0 )
 553                         {
 554                             uint8_t *ctx = &n.cabac_state[coeff_abs_levelgt1_ctx[node_ctx]];
 555                             f8_bits += cabac_size_unary[i_prefix][*ctx];
 556                             *ctx = cabac_transition_unary[i_prefix][*ctx];
 557                             if( abs_level >= 15 )
 558                                 f8_bits += bs_size_ue_big( abs_level - 15 ) << CABAC_SIZE_BITS;
 559                             node_ctx = coeff_abs_level_transition[1][node_ctx];
 560                         }
 561                         else
 562                         {
 563                             f8_bits += 1 << CABAC_SIZE_BITS;
 564                             node_ctx = coeff_abs_level_transition[0][node_ctx];
 565                         }
 566                     }
 567                     n.score += (uint64_t)f8_bits * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
 568                 }
 569
 570                 if( j || i || dc )
 571                     n.score += ssd;
 572                 /* Optimize rounding for DC coefficients in DC-only luma 4x4/8x8 blocks. */
 573                 else
 574                 {
 575                     d = i_coef * signs[0] - ((unquant_abs_level * signs[0] + 8)&~15);
 576                     n.score += (int64_t)d*d * coef_weight[i];
 577                 }
 578
 579                 /* save the node if it's better than any existing node with the same cabac ctx */
 580                 if( n.score < nodes_cur[node_ctx].score )
 581                 {
 582                     SET_LEVEL( n, abs_level );
 583                     nodes_cur[node_ctx] = n;
 584                 }
 585             }
 586         }
 587     }
 588
 589     /* output levels from the best path through the trellis */
 590     bnode = &nodes_cur[0];
 591     for( j = 1; j < 8; j++ )
 592         if( nodes_cur[j].score < bnode->score )
 593             bnode = &nodes_cur[j];
 594
 595     if( bnode == &nodes_cur[0] )
 596     {
 597         if( i_coefs == 16 && !dc )
 598             memset( dct, 0, 16 * sizeof(int16_t) );
 599         return 0;
 600     }
 601
 602     j = bnode->level_idx;
 603     for( i = b_ac; j; i++ )
 604     {
 605         dct[zigzag[i]] = level_tree[j].abs_level * signs[i];
 606         j = level_tree[j].next;
 607     }
 608     for( ; i < i_coefs; i++ )
 609         dct[zigzag[i]] = 0;
 610
 611     return 1;
 612 }
 613
 614 const static uint8_t x264_zigzag_scan2[4] = {0,1,2,3};
 615
 616 int x264_quant_dc_trellis( x264_t *h, int16_t *dct, int i_quant_cat,
 617                             int i_qp, int i_ctxBlockCat, int b_intra, int b_chroma )
 618 {
 619     return quant_trellis_cabac( h, dct,
 620         h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
 621         NULL, i_ctxBlockCat==DCT_CHROMA_DC ? x264_zigzag_scan2 : x264_zigzag_scan4[h->mb.b_interlaced],
 622         i_ctxBlockCat, h->mb.i_trellis_lambda2[b_chroma][b_intra], 0, 1, i_ctxBlockCat==DCT_CHROMA_DC ? 4 : 16, 0 );
 623 }
 624
 625 int x264_quant_4x4_trellis( x264_t *h, int16_t *dct, int i_quant_cat,
 626                              int i_qp, int i_ctxBlockCat, int b_intra, int b_chroma, int idx )
 627 {
 628     int b_ac = (i_ctxBlockCat == DCT_LUMA_AC || i_ctxBlockCat == DCT_CHROMA_AC);
 629     return quant_trellis_cabac( h, dct,
 630         h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
 631         x264_dct4_weight2_zigzag[h->mb.b_interlaced],
 632         x264_zigzag_scan4[h->mb.b_interlaced],
 633         i_ctxBlockCat, h->mb.i_trellis_lambda2[b_chroma][b_intra], b_ac, 0, 16, idx );
 634 }
 635
 636 int x264_quant_8x8_trellis( x264_t *h, int16_t *dct, int i_quant_cat,
 637                              int i_qp, int b_intra, int idx )
 638 {
 639     return quant_trellis_cabac( h, dct,
 640         h->quant8_mf[i_quant_cat][i_qp], h->unquant8_mf[i_quant_cat][i_qp],
 641         x264_dct8_weight2_zigzag[h->mb.b_interlaced],
 642         x264_zigzag_scan8[h->mb.b_interlaced],
 643         DCT_LUMA_8x8, h->mb.i_trellis_lambda2[0][b_intra], 0, 0, 64, idx );
 644 }
 645