1 /*****************************************************************************
2 * rdo.c: h264 encoder library (rate-distortion optimization)
3 *****************************************************************************
4 * Copyright (C) 2005 x264 project
6 * Authors: Loren Merritt <lorenm@u.washington.edu>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA.
21 *****************************************************************************/
23 /* duplicate all the writer functions, just calculating bit cost
24 * instead of writing the bitstream.
25 * TODO: use these for fast 1st pass too. */
29 /* CAVLC: produces exactly the same bit count as a normal encode */
30 /* this probably still leaves some unnecessary computations */
31 #define bs_write1(s,v) ((s)->i_bits_encoded += 1)
32 #define bs_write(s,n,v) ((s)->i_bits_encoded += (n))
33 #define bs_write_ue(s,v) ((s)->i_bits_encoded += bs_size_ue(v))
34 #define bs_write_se(s,v) ((s)->i_bits_encoded += bs_size_se(v))
35 #define bs_write_te(s,v,l) ((s)->i_bits_encoded += bs_size_te(v,l))
36 #define x264_macroblock_write_cavlc x264_macroblock_size_cavlc
39 /* CABAC: not exactly the same. x264_cabac_size_decision() keeps track of
40 * fractional bits, but only finite precision. */
41 #define x264_cabac_encode_decision(c,x,v) x264_cabac_size_decision(c,x,v)
42 #define x264_cabac_encode_terminal(c,v) x264_cabac_size_decision(c,276,v)
43 #define x264_cabac_encode_bypass(c,v) ((c)->f8_bits_encoded += 256)
44 #define x264_cabac_encode_flush(c)
45 #define x264_macroblock_write_cabac x264_macroblock_size_cabac
46 #define x264_cabac_mb_skip x264_cabac_mb_size_skip_unused
50 static int ssd_mb( x264_t *h )
52 return h->pixf.ssd[PIXEL_16x16]( h->mb.pic.p_fenc[0], FENC_STRIDE,
53 h->mb.pic.p_fdec[0], FDEC_STRIDE )
54 + h->pixf.ssd[PIXEL_8x8]( h->mb.pic.p_fenc[1], FENC_STRIDE,
55 h->mb.pic.p_fdec[1], FDEC_STRIDE )
56 + h->pixf.ssd[PIXEL_8x8]( h->mb.pic.p_fenc[2], FENC_STRIDE,
57 h->mb.pic.p_fdec[2], FDEC_STRIDE );
60 static int ssd_plane( x264_t *h, int size, int p, int x, int y )
62 return h->pixf.ssd[size]( h->mb.pic.p_fenc[p] + x+y*FENC_STRIDE, FENC_STRIDE,
63 h->mb.pic.p_fdec[p] + x+y*FDEC_STRIDE, FDEC_STRIDE );
66 static int x264_rd_cost_mb( x264_t *h, int i_lambda2 )
68 int b_transform_bak = h->mb.b_transform_8x8;
72 x264_macroblock_encode( h );
76 if( IS_SKIP( h->mb.i_type ) )
78 i_bits = 1 * i_lambda2;
80 else if( h->param.b_cabac )
82 x264_cabac_t cabac_tmp = h->cabac;
83 cabac_tmp.f8_bits_encoded = 0;
84 x264_macroblock_size_cabac( h, &cabac_tmp );
85 i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
89 bs_t bs_tmp = h->out.bs;
90 bs_tmp.i_bits_encoded = 0;
91 x264_macroblock_size_cavlc( h, &bs_tmp );
92 i_bits = bs_tmp.i_bits_encoded * i_lambda2;
95 h->mb.b_transform_8x8 = b_transform_bak;
97 return i_ssd + i_bits;
100 int x264_rd_cost_part( x264_t *h, int i_lambda2, int i8, int i_pixel )
104 if( i_pixel == PIXEL_16x16 )
106 int type_bak = h->mb.i_type;
107 int i_cost = x264_rd_cost_mb( h, i_lambda2 );
108 h->mb.i_type = type_bak;
112 x264_macroblock_encode_p8x8( h, i8 );
113 if( i_pixel == PIXEL_16x8 )
114 x264_macroblock_encode_p8x8( h, i8+1 );
115 if( i_pixel == PIXEL_8x16 )
116 x264_macroblock_encode_p8x8( h, i8+2 );
118 i_ssd = ssd_plane( h, i_pixel, 0, (i8&1)*8, (i8>>1)*8 )
119 + ssd_plane( h, i_pixel+3, 1, (i8&1)*4, (i8>>1)*4 )
120 + ssd_plane( h, i_pixel+3, 2, (i8&1)*4, (i8>>1)*4 );
122 if( h->param.b_cabac )
124 x264_cabac_t cabac_tmp = h->cabac;
125 cabac_tmp.f8_bits_encoded = 0;
126 x264_partition_size_cabac( h, &cabac_tmp, i8, i_pixel );
127 i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
131 i_bits = x264_partition_size_cavlc( h, i8, i_pixel ) * i_lambda2;
134 return i_ssd + i_bits;
137 int x264_rd_cost_i8x8( x264_t *h, int i_lambda2, int i8, int i_mode )
141 x264_mb_encode_i8x8( h, i8, h->mb.i_qp );
142 i_ssd = ssd_plane( h, PIXEL_8x8, 0, (i8&1)*8, (i8>>1)*8 );
144 if( h->param.b_cabac )
146 x264_cabac_t cabac_tmp = h->cabac;
147 cabac_tmp.f8_bits_encoded = 0;
148 x264_partition_i8x8_size_cabac( h, &cabac_tmp, i8, i_mode );
149 i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
153 i_bits = x264_partition_i8x8_size_cavlc( h, i8, i_mode ) * i_lambda2;
156 return i_ssd + i_bits;
159 int x264_rd_cost_i4x4( x264_t *h, int i_lambda2, int i4, int i_mode )
163 x264_mb_encode_i4x4( h, i4, h->mb.i_qp );
164 i_ssd = ssd_plane( h, PIXEL_4x4, 0, block_idx_x[i4]*4, block_idx_y[i4]*4 );
166 if( h->param.b_cabac )
168 x264_cabac_t cabac_tmp = h->cabac;
169 cabac_tmp.f8_bits_encoded = 0;
170 x264_partition_i4x4_size_cabac( h, &cabac_tmp, i4, i_mode );
171 i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
175 i_bits = x264_partition_i4x4_size_cavlc( h, i4, i_mode ) * i_lambda2;
178 return i_ssd + i_bits;
181 int x264_rd_cost_i8x8_chroma( x264_t *h, int i_lambda2, int i_mode, int b_dct )
186 x264_mb_encode_8x8_chroma( h, 0, h->mb.i_chroma_qp );
187 i_ssd = ssd_plane( h, PIXEL_8x8, 1, 0, 0 ) +
188 ssd_plane( h, PIXEL_8x8, 2, 0, 0 );
190 h->mb.i_chroma_pred_mode = i_mode;
192 if( h->param.b_cabac )
194 x264_cabac_t cabac_tmp = h->cabac;
195 cabac_tmp.f8_bits_encoded = 0;
196 x264_i8x8_chroma_size_cabac( h, &cabac_tmp );
197 i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
201 i_bits = x264_i8x8_chroma_size_cavlc( h ) * i_lambda2;
204 return i_ssd + i_bits;
206 /****************************************************************************
207 * Trellis RD quantization
208 ****************************************************************************/
210 #define TRELLIS_SCORE_MAX ((uint64_t)1<<50)
211 #define CABAC_SIZE_BITS 8
212 #define SSD_WEIGHT_BITS 5
213 #define LAMBDA_BITS 4
215 /* precalculate the cost of coding abs_level_m1 */
216 static int cabac_prefix_transition[15][128];
217 static int cabac_prefix_size[15][128];
218 void x264_rdo_init( )
222 for( i_prefix = 0; i_prefix < 15; i_prefix++ )
224 for( i_ctx = 0; i_ctx < 128; i_ctx++ )
230 for( i = 1; i < i_prefix; i++ )
231 f8_bits += x264_cabac_size_decision2( &ctx, 1 );
232 if( i_prefix > 0 && i_prefix < 14 )
233 f8_bits += x264_cabac_size_decision2( &ctx, 0 );
234 f8_bits += 1 << CABAC_SIZE_BITS; //sign
236 cabac_prefix_size[i_prefix][i_ctx] = f8_bits;
237 cabac_prefix_transition[i_prefix][i_ctx] = ctx;
242 // node ctx: 0..3: abslevel1 (with abslevelgt1 == 0).
243 // 4..7: abslevelgt1 + 3 (and abslevel1 doesn't matter).
244 /* map node ctx => cabac ctx for level=1 */
245 static const int coeff_abs_level1_ctx[8] = { 1, 2, 3, 4, 0, 0, 0, 0 };
246 /* map node ctx => cabac ctx for level>1 */
247 static const int coeff_abs_levelgt1_ctx[8] = { 5, 5, 5, 5, 6, 7, 8, 9 };
248 static const int coeff_abs_level_transition[2][8] = {
249 /* update node.ctx after coding a level=1 */
250 { 1, 2, 3, 3, 4, 5, 6, 7 },
251 /* update node.ctx after coding a level>1 */
252 { 4, 4, 4, 4, 5, 6, 7, 7 }
255 static const int lambda2_tab[6] = { 1024, 1290, 1625, 2048, 2580, 3251 };
259 int level_idx; // index into level_tree[]
260 uint8_t cabac_state[10]; //just the contexts relevant to coding abs_level_m1
264 // support chroma and i16x16 DC
265 // save cabac state between blocks?
266 // use trellis' RD score instead of x264_mb_decimate_score?
267 // code 8x8 sig/last flags forwards with deadzone and save the contexts at
269 // change weights when using CQMs?
271 // possible optimizations:
272 // make scores fit in 32bit
273 // save quantized coefs during rd, to avoid a duplicate trellis in the final encode
274 // if trellissing all MBRD modes, finish SSD calculation so we can skip all of
275 // the normal dequant/idct/ssd/cabac
277 // the unquant_mf here is not the same as dequant_mf:
278 // in normal operation (dct->quant->dequant->idct) the dct and idct are not
279 // normalized. quant/dequant absorb those scaling factors.
280 // in this function, we just do (quant->unquant) and want the output to be
281 // comparable to the input. so unquant is the direct inverse of quant,
282 // and uses the dct scaling factors, not the idct ones.
284 static void quant_trellis_cabac( x264_t *h, int16_t *dct,
285 const int *quant_mf, const int *unquant_mf,
286 const int *coef_weight, const int *zigzag,
287 int i_ctxBlockCat, int i_qbits, int i_lambda2, int b_ac, int i_coefs )
289 int abs_coefs[64], signs[64];
290 trellis_node_t nodes[2][8];
291 trellis_node_t *nodes_cur = nodes[0];
292 trellis_node_t *nodes_prev = nodes[1];
293 trellis_node_t *bnode;
294 uint8_t cabac_state_sig[64];
295 uint8_t cabac_state_last[64];
296 const int b_interlaced = h->mb.b_interlaced;
297 const int f = 1 << (i_qbits-1); // no deadzone
301 // (# of coefs) * (# of ctx) * (# of levels tried) = 1024
302 // we don't need to keep all of those: (# of coefs) * (# of ctx) would be enough,
303 // but it takes more time to remove dead states than you gain in reduced memory.
307 } level_tree[64*8*2];
308 int i_levels_used = 1;
311 for( i = b_ac; i < i_coefs; i++ )
313 int coef = dct[zigzag[i]];
314 abs_coefs[i] = abs(coef);
315 signs[i] = coef < 0 ? -1 : 1;
316 if( f <= abs_coefs[i] * quant_mf[zigzag[i]] )
320 if( i_last_nnz == -1 )
322 memset( dct, 0, i_coefs * sizeof(*dct) );
327 for( i = 1; i < 8; i++ )
328 nodes_cur[i].score = TRELLIS_SCORE_MAX;
329 nodes_cur[0].score = 0;
330 nodes_cur[0].level_idx = 0;
331 level_tree[0].abs_level = 0;
332 level_tree[0].next = 0;
334 // coefs are processed in reverse order, because that's how the abs value is coded.
335 // last_coef and significant_coef flags are normally coded in forward order, but
336 // we have to reverse them to match the levels.
337 // in 4x4 blocks, last_coef and significant_coef use a separate context for each
338 // position, so the order doesn't matter, and we don't even have to update their contexts.
339 // in 8x8 blocks, some positions share contexts, so we'll just have to hope that
340 // cabac isn't too sensitive.
344 const uint8_t *ctx_sig = &h->cabac.state[ significant_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ];
345 const uint8_t *ctx_last = &h->cabac.state[ last_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ];
346 for( i = 0; i < 63; i++ )
348 cabac_state_sig[i] = ctx_sig[ significant_coeff_flag_offset_8x8[b_interlaced][i] ];
349 cabac_state_last[i] = ctx_last[ last_coeff_flag_offset_8x8[i] ];
354 memcpy( cabac_state_sig, &h->cabac.state[ significant_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ], 15 );
355 memcpy( cabac_state_last, &h->cabac.state[ last_coeff_flag_offset[b_interlaced][i_ctxBlockCat] ], 15 );
357 memcpy( nodes_cur[0].cabac_state, &h->cabac.state[ coeff_abs_level_m1_offset[i_ctxBlockCat] ], 10 );
359 for( i = i_last_nnz; i >= b_ac; i-- )
361 int i_coef = abs_coefs[i];
362 int q = ( f + i_coef * quant_mf[zigzag[i]] ) >> i_qbits;
364 int cost_sig[2], cost_last[2];
367 // skip 0s: this doesn't affect the output, but saves some unnecessary computation.
370 // no need to calculate ssd of 0s: it's the same in all nodes.
371 // no need to modify level_tree for ctx=0: it starts with an infinite loop of 0s.
372 const int cost_sig0 = x264_cabac_size_decision_noup( &cabac_state_sig[i], 0 )
373 * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
374 for( j = 1; j < 8; j++ )
376 if( nodes_cur[j].score != TRELLIS_SCORE_MAX )
378 #define SET_LEVEL(n,l) \
379 level_tree[i_levels_used].abs_level = l; \
380 level_tree[i_levels_used].next = n.level_idx; \
381 n.level_idx = i_levels_used; \
384 SET_LEVEL( nodes_cur[j], 0 );
385 nodes_cur[j].score += cost_sig0;
391 XCHG( trellis_node_t*, nodes_cur, nodes_prev );
393 for( j = 0; j < 8; j++ )
394 nodes_cur[j].score = TRELLIS_SCORE_MAX;
398 cost_sig[0] = x264_cabac_size_decision_noup( &cabac_state_sig[i], 0 );
399 cost_sig[1] = x264_cabac_size_decision_noup( &cabac_state_sig[i], 1 );
400 cost_last[0] = x264_cabac_size_decision_noup( &cabac_state_last[i], 0 );
401 cost_last[1] = x264_cabac_size_decision_noup( &cabac_state_last[i], 1 );
405 cost_sig[0] = cost_sig[1] = 0;
406 cost_last[0] = cost_last[1] = 0;
409 // there are a few cases where increasing the coeff magnitude helps,
410 // but it's only around .003 dB, and skipping them ~doubles the speed of trellis.
411 // could also try q-2: that sometimes helps, but also sometimes decimates blocks
412 // that are better left coded, especially at QP > 40.
413 for( abs_level = q; abs_level >= q-1; abs_level-- )
415 int d = i_coef - ((unquant_mf[zigzag[i]] * abs_level + 128) >> 8);
416 uint64_t ssd = (int64_t)d*d * coef_weight[i];
418 for( j = 0; j < 8; j++ )
421 if( nodes_prev[j].score == TRELLIS_SCORE_MAX )
425 /* code the proposed level, and count how much entropy it would take */
426 if( abs_level || node_ctx )
428 unsigned f8_bits = cost_sig[ abs_level != 0 ];
431 const int i_prefix = X264_MIN( abs_level - 1, 14 );
432 f8_bits += cost_last[ node_ctx == 0 ];
433 f8_bits += x264_cabac_size_decision2( &n.cabac_state[coeff_abs_level1_ctx[node_ctx]], i_prefix > 0 );
436 uint8_t *ctx = &n.cabac_state[coeff_abs_levelgt1_ctx[node_ctx]];
437 f8_bits += cabac_prefix_size[i_prefix][*ctx];
438 *ctx = cabac_prefix_transition[i_prefix][*ctx];
439 if( abs_level >= 15 )
440 f8_bits += bs_size_ue( abs_level - 15 ) << CABAC_SIZE_BITS;
441 node_ctx = coeff_abs_level_transition[1][node_ctx];
445 f8_bits += 1 << CABAC_SIZE_BITS;
446 node_ctx = coeff_abs_level_transition[0][node_ctx];
449 n.score += (uint64_t)f8_bits * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
454 /* save the node if it's better than any existing node with the same cabac ctx */
455 if( n.score < nodes_cur[node_ctx].score )
457 SET_LEVEL( n, abs_level );
458 nodes_cur[node_ctx] = n;
464 /* output levels from the best path through the trellis */
465 bnode = &nodes_cur[0];
466 for( j = 1; j < 8; j++ )
467 if( nodes_cur[j].score < bnode->score )
468 bnode = &nodes_cur[j];
470 j = bnode->level_idx;
471 for( i = b_ac; i < i_coefs; i++ )
473 dct[zigzag[i]] = level_tree[j].abs_level * signs[i];
474 j = level_tree[j].next;
479 void x264_quant_4x4_trellis( x264_t *h, int16_t dct[4][4], int i_quant_cat,
480 int i_qp, int i_ctxBlockCat, int b_intra )
482 const int i_qbits = i_qp / 6;
483 const int i_mf = i_qp % 6;
484 const int b_ac = (i_ctxBlockCat == DCT_LUMA_AC);
485 /* should the lambdas be different? I'm just matching the behaviour of deadzone quant. */
486 const int i_lambda_mult = b_intra ? 65 : 85;
487 const int i_lambda2 = ((lambda2_tab[i_mf] * i_lambda_mult*i_lambda_mult / 10000)
488 << (2*i_qbits)) >> LAMBDA_BITS;
490 quant_trellis_cabac( h, (int16_t*)dct,
491 (int*)h->quant4_mf[i_quant_cat][i_mf], h->unquant4_mf[i_quant_cat][i_qp],
492 x264_dct4_weight2_zigzag[h->mb.b_interlaced],
493 x264_zigzag_scan4[h->mb.b_interlaced],
494 i_ctxBlockCat, 15+i_qbits, i_lambda2, b_ac, 16 );
498 void x264_quant_8x8_trellis( x264_t *h, int16_t dct[8][8], int i_quant_cat,
499 int i_qp, int b_intra )
501 const int i_qbits = i_qp / 6;
502 const int i_mf = i_qp % 6;
503 const int i_lambda_mult = b_intra ? 65 : 85;
504 const int i_lambda2 = ((lambda2_tab[i_mf] * i_lambda_mult*i_lambda_mult / 10000)
505 << (2*i_qbits)) >> LAMBDA_BITS;
507 quant_trellis_cabac( h, (int16_t*)dct,
508 (int*)h->quant8_mf[i_quant_cat][i_mf], h->unquant8_mf[i_quant_cat][i_qp],
509 x264_dct8_weight2_zigzag[h->mb.b_interlaced],
510 x264_zigzag_scan8[h->mb.b_interlaced],
511 DCT_LUMA_8x8, 16+i_qbits, i_lambda2, 0, 64 );