1 /*****************************************************************************
2 * rdo.c: rate-distortion optimization
3 *****************************************************************************
4 * Copyright (C) 2005-2011 x264 project
6 * Authors: Loren Merritt <lorenm@u.washington.edu>
7 * Fiona Glaser <fiona@x264.com>
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.
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.
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.
23 * This program is also available under a commercial proprietary license.
24 * For more information, contact us at licensing@x264.com.
25 *****************************************************************************/
27 /* duplicate all the writer functions, just calculating bit cost
28 * instead of writing the bitstream.
29 * TODO: use these for fast 1st pass too. */
33 /* Transition and size tables for abs<9 MVD and residual coding */
34 /* Consist of i_prefix-2 1s, one zero, and a bypass sign bit */
35 static uint8_t cabac_transition_unary[15][128];
36 static uint16_t cabac_size_unary[15][128];
37 /* Transition and size tables for abs>9 MVD */
38 /* Consist of 5 1s and a bypass sign bit */
39 static uint8_t cabac_transition_5ones[128];
40 static uint16_t cabac_size_5ones[128];
42 /* CAVLC: produces exactly the same bit count as a normal encode */
43 /* this probably still leaves some unnecessary computations */
44 #define bs_write1(s,v) ((s)->i_bits_encoded += 1)
45 #define bs_write(s,n,v) ((s)->i_bits_encoded += (n))
46 #define bs_write_ue(s,v) ((s)->i_bits_encoded += bs_size_ue(v))
47 #define bs_write_se(s,v) ((s)->i_bits_encoded += bs_size_se(v))
48 #define bs_write_te(s,v,l) ((s)->i_bits_encoded += bs_size_te(v,l))
49 #define x264_macroblock_write_cavlc static x264_macroblock_size_cavlc
52 /* CABAC: not exactly the same. x264_cabac_size_decision() keeps track of
53 * fractional bits, but only finite precision. */
54 #undef x264_cabac_encode_decision
55 #undef x264_cabac_encode_decision_noup
56 #undef x264_cabac_encode_bypass
57 #undef x264_cabac_encode_terminal
58 #define x264_cabac_encode_decision(c,x,v) x264_cabac_size_decision(c,x,v)
59 #define x264_cabac_encode_decision_noup(c,x,v) x264_cabac_size_decision_noup(c,x,v)
60 #define x264_cabac_encode_terminal(c) ((c)->f8_bits_encoded += 7)
61 #define x264_cabac_encode_bypass(c,v) ((c)->f8_bits_encoded += 256)
62 #define x264_cabac_encode_ue_bypass(c,e,v) ((c)->f8_bits_encoded += (bs_size_ue_big(v+(1<<e)-1)-e)<<8)
63 #define x264_macroblock_write_cabac static x264_macroblock_size_cabac
66 #define COPY_CABAC h->mc.memcpy_aligned( &cabac_tmp.f8_bits_encoded, &h->cabac.f8_bits_encoded, \
67 sizeof(x264_cabac_t) - offsetof(x264_cabac_t,f8_bits_encoded) - (CHROMA444 ? 0 : (1024+12)-460) )
68 #define COPY_CABAC_PART( pos, size )\
69 memcpy( &cb->state[pos], &h->cabac.state[pos], size )
71 static ALWAYS_INLINE uint64_t cached_hadamard( x264_t *h, int size, int x, int y )
73 static const uint8_t hadamard_shift_x[4] = {4, 4, 3, 3};
74 static const uint8_t hadamard_shift_y[4] = {4-0, 3-0, 4-1, 3-1};
75 static const uint8_t hadamard_offset[4] = {0, 1, 3, 5};
76 int cache_index = (x >> hadamard_shift_x[size]) + (y >> hadamard_shift_y[size])
77 + hadamard_offset[size];
78 uint64_t res = h->mb.pic.fenc_hadamard_cache[cache_index];
83 pixel *fenc = h->mb.pic.p_fenc[0] + x + y*FENC_STRIDE;
84 res = h->pixf.hadamard_ac[size]( fenc, FENC_STRIDE );
85 h->mb.pic.fenc_hadamard_cache[cache_index] = res + 1;
90 static ALWAYS_INLINE int cached_satd( x264_t *h, int size, int x, int y )
92 static const uint8_t satd_shift_x[3] = {3, 2, 2};
93 static const uint8_t satd_shift_y[3] = {2-1, 3-2, 2-2};
94 static const uint8_t satd_offset[3] = {0, 8, 16};
95 ALIGNED_16( static pixel zero[16] ) = {0};
96 int cache_index = (x >> satd_shift_x[size - PIXEL_8x4]) + (y >> satd_shift_y[size - PIXEL_8x4])
97 + satd_offset[size - PIXEL_8x4];
98 int res = h->mb.pic.fenc_satd_cache[cache_index];
103 pixel *fenc = h->mb.pic.p_fenc[0] + x + y*FENC_STRIDE;
104 int dc = h->pixf.sad[size]( fenc, FENC_STRIDE, zero, 0 ) >> 1;
105 res = h->pixf.satd[size]( fenc, FENC_STRIDE, zero, 0 ) - dc;
106 h->mb.pic.fenc_satd_cache[cache_index] = res + 1;
111 /* Psy RD distortion metric: SSD plus "Absolute Difference of Complexities" */
112 /* SATD and SA8D are used to measure block complexity. */
113 /* The difference between SATD and SA8D scores are both used to avoid bias from the DCT size. Using SATD */
114 /* only, for example, results in overusage of 8x8dct, while the opposite occurs when using SA8D. */
116 /* FIXME: Is there a better metric than averaged SATD/SA8D difference for complexity difference? */
117 /* Hadamard transform is recursive, so a SATD+SA8D can be done faster by taking advantage of this fact. */
118 /* This optimization can also be used in non-RD transform decision. */
120 static inline int ssd_plane( x264_t *h, int size, int p, int x, int y )
122 ALIGNED_16( static pixel zero[16] ) = {0};
124 pixel *fdec = h->mb.pic.p_fdec[p] + x + y*FDEC_STRIDE;
125 pixel *fenc = h->mb.pic.p_fenc[p] + x + y*FENC_STRIDE;
126 if( p == 0 && h->mb.i_psy_rd )
128 /* If the plane is smaller than 8x8, we can't do an SA8D; this probably isn't a big problem. */
129 if( size <= PIXEL_8x8 )
131 uint64_t fdec_acs = h->pixf.hadamard_ac[size]( fdec, FDEC_STRIDE );
132 uint64_t fenc_acs = cached_hadamard( h, size, x, y );
133 satd = abs((int32_t)fdec_acs - (int32_t)fenc_acs)
134 + abs((int32_t)(fdec_acs>>32) - (int32_t)(fenc_acs>>32));
139 int dc = h->pixf.sad[size]( fdec, FDEC_STRIDE, zero, 0 ) >> 1;
140 satd = abs(h->pixf.satd[size]( fdec, FDEC_STRIDE, zero, 0 ) - dc - cached_satd( h, size, x, y ));
142 satd = (satd * h->mb.i_psy_rd * h->mb.i_psy_rd_lambda + 128) >> 8;
144 return h->pixf.ssd[size](fenc, FENC_STRIDE, fdec, FDEC_STRIDE) + satd;
147 static inline int ssd_mb( x264_t *h )
149 int chroma_size = CHROMA444 ? PIXEL_16x16 : PIXEL_8x8;
150 int chroma_ssd = ssd_plane(h, chroma_size, 1, 0, 0) + ssd_plane(h, chroma_size, 2, 0, 0);
151 chroma_ssd = ((uint64_t)chroma_ssd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
152 return ssd_plane(h, PIXEL_16x16, 0, 0, 0) + chroma_ssd;
155 static int x264_rd_cost_mb( x264_t *h, int i_lambda2 )
157 int b_transform_bak = h->mb.b_transform_8x8;
160 int type_bak = h->mb.i_type;
162 x264_macroblock_encode( h );
164 if( h->mb.b_deblock_rdo )
165 x264_macroblock_deblock( h );
169 if( IS_SKIP( h->mb.i_type ) )
171 i_bits = (1 * i_lambda2 + 128) >> 8;
173 else if( h->param.b_cabac )
175 x264_cabac_t cabac_tmp;
177 x264_macroblock_size_cabac( h, &cabac_tmp );
178 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 32768 ) >> 16;
182 x264_macroblock_size_cavlc( h );
183 i_bits = ( h->out.bs.i_bits_encoded * i_lambda2 + 128 ) >> 8;
186 h->mb.b_transform_8x8 = b_transform_bak;
187 h->mb.i_type = type_bak;
189 return i_ssd + i_bits;
192 /* partition RD functions use 8 bits more precision to avoid large rounding errors at low QPs */
194 static uint64_t x264_rd_cost_subpart( x264_t *h, int i_lambda2, int i4, int i_pixel )
196 uint64_t i_ssd, i_bits;
198 x264_macroblock_encode_p4x4( h, i4 );
199 if( i_pixel == PIXEL_8x4 )
200 x264_macroblock_encode_p4x4( h, i4+1 );
201 if( i_pixel == PIXEL_4x8 )
202 x264_macroblock_encode_p4x4( h, i4+2 );
204 i_ssd = ssd_plane( h, i_pixel, 0, block_idx_x[i4]*4, block_idx_y[i4]*4 );
207 int chromassd = ssd_plane( h, i_pixel, 1, block_idx_x[i4]*4, block_idx_y[i4]*4 )
208 + ssd_plane( h, i_pixel, 2, block_idx_x[i4]*4, block_idx_y[i4]*4 );
209 chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
213 if( h->param.b_cabac )
215 x264_cabac_t cabac_tmp;
217 x264_subpartition_size_cabac( h, &cabac_tmp, i4, i_pixel );
218 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
221 i_bits = x264_subpartition_size_cavlc( h, i4, i_pixel );
223 return (i_ssd<<8) + i_bits;
226 uint64_t x264_rd_cost_part( x264_t *h, int i_lambda2, int i4, int i_pixel )
228 uint64_t i_ssd, i_bits;
232 if( i_pixel == PIXEL_16x16 )
234 int i_cost = x264_rd_cost_mb( h, i_lambda2 );
238 if( i_pixel > PIXEL_8x8 )
239 return x264_rd_cost_subpart( h, i_lambda2, i4, i_pixel );
241 h->mb.i_cbp_luma = 0;
243 x264_macroblock_encode_p8x8( h, i8 );
244 if( i_pixel == PIXEL_16x8 )
245 x264_macroblock_encode_p8x8( h, i8+1 );
246 if( i_pixel == PIXEL_8x16 )
247 x264_macroblock_encode_p8x8( h, i8+2 );
249 i_ssd = ssd_plane( h, i_pixel, 0, (i8&1)*8, (i8>>1)*8 );
252 chromassd = ssd_plane( h, i_pixel, 1, (i8&1)*8, (i8>>1)*8 )
253 + ssd_plane( h, i_pixel, 2, (i8&1)*8, (i8>>1)*8 );
257 chromassd = ssd_plane( h, i_pixel+3, 1, (i8&1)*4, (i8>>1)*4 )
258 + ssd_plane( h, i_pixel+3, 2, (i8&1)*4, (i8>>1)*4 );
260 chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
263 if( h->param.b_cabac )
265 x264_cabac_t cabac_tmp;
267 x264_partition_size_cabac( h, &cabac_tmp, i8, i_pixel );
268 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
271 i_bits = x264_partition_size_cavlc( h, i8, i_pixel ) * i_lambda2;
273 return (i_ssd<<8) + i_bits;
276 static uint64_t x264_rd_cost_i8x8( x264_t *h, int i_lambda2, int i8, int i_mode, pixel edge[4][32] )
278 uint64_t i_ssd, i_bits;
279 int plane_count = CHROMA444 ? 3 : 1;
280 int i_qp = h->mb.i_qp;
281 h->mb.i_cbp_luma &= ~(1<<i8);
282 h->mb.b_transform_8x8 = 1;
284 for( int p = 0; p < plane_count; p++ )
286 x264_mb_encode_i8x8( h, p, i8, i_qp, i_mode, edge[p] );
287 i_qp = h->mb.i_chroma_qp;
290 i_ssd = ssd_plane( h, PIXEL_8x8, 0, (i8&1)*8, (i8>>1)*8 );
293 int chromassd = ssd_plane( h, PIXEL_8x8, 1, (i8&1)*8, (i8>>1)*8 )
294 + ssd_plane( h, PIXEL_8x8, 2, (i8&1)*8, (i8>>1)*8 );
295 chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
299 if( h->param.b_cabac )
301 x264_cabac_t cabac_tmp;
303 x264_partition_i8x8_size_cabac( h, &cabac_tmp, i8, i_mode );
304 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
307 i_bits = x264_partition_i8x8_size_cavlc( h, i8, i_mode ) * i_lambda2;
309 return (i_ssd<<8) + i_bits;
312 static uint64_t x264_rd_cost_i4x4( x264_t *h, int i_lambda2, int i4, int i_mode )
314 uint64_t i_ssd, i_bits;
315 int plane_count = CHROMA444 ? 3 : 1;
316 int i_qp = h->mb.i_qp;
318 for( int p = 0; p < plane_count; p++ )
320 x264_mb_encode_i4x4( h, p, i4, i_qp, i_mode );
321 i_qp = h->mb.i_chroma_qp;
324 i_ssd = ssd_plane( h, PIXEL_4x4, 0, block_idx_x[i4]*4, block_idx_y[i4]*4 );
327 int chromassd = ssd_plane( h, PIXEL_4x4, 1, block_idx_x[i4]*4, block_idx_y[i4]*4 )
328 + ssd_plane( h, PIXEL_4x4, 2, block_idx_x[i4]*4, block_idx_y[i4]*4 );
329 chromassd = ((uint64_t)chromassd * h->mb.i_chroma_lambda2_offset + 128) >> 8;
333 if( h->param.b_cabac )
335 x264_cabac_t cabac_tmp;
337 x264_partition_i4x4_size_cabac( h, &cabac_tmp, i4, i_mode );
338 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
341 i_bits = x264_partition_i4x4_size_cavlc( h, i4, i_mode ) * i_lambda2;
343 return (i_ssd<<8) + i_bits;
346 static uint64_t x264_rd_cost_i8x8_chroma( x264_t *h, int i_lambda2, int i_mode, int b_dct )
348 uint64_t i_ssd, i_bits;
351 x264_mb_encode_8x8_chroma( h, 0, h->mb.i_chroma_qp );
352 i_ssd = ssd_plane( h, PIXEL_8x8, 1, 0, 0 ) +
353 ssd_plane( h, PIXEL_8x8, 2, 0, 0 );
355 h->mb.i_chroma_pred_mode = i_mode;
357 if( h->param.b_cabac )
359 x264_cabac_t cabac_tmp;
361 x264_i8x8_chroma_size_cabac( h, &cabac_tmp );
362 i_bits = ( (uint64_t)cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
365 i_bits = x264_i8x8_chroma_size_cavlc( h ) * i_lambda2;
367 return (i_ssd<<8) + i_bits;
369 /****************************************************************************
370 * Trellis RD quantization
371 ****************************************************************************/
373 #define TRELLIS_SCORE_MAX ((uint64_t)1<<50)
374 #define CABAC_SIZE_BITS 8
375 #define SSD_WEIGHT_BITS 5
376 #define LAMBDA_BITS 4
378 /* precalculate the cost of coding various combinations of bits in a single context */
379 void x264_rdo_init( void )
381 for( int i_prefix = 0; i_prefix < 15; i_prefix++ )
383 for( int i_ctx = 0; i_ctx < 128; i_ctx++ )
388 for( int i = 1; i < i_prefix; i++ )
389 f8_bits += x264_cabac_size_decision2( &ctx, 1 );
390 if( i_prefix > 0 && i_prefix < 14 )
391 f8_bits += x264_cabac_size_decision2( &ctx, 0 );
392 f8_bits += 1 << CABAC_SIZE_BITS; //sign
394 cabac_size_unary[i_prefix][i_ctx] = f8_bits;
395 cabac_transition_unary[i_prefix][i_ctx] = ctx;
398 for( int i_ctx = 0; i_ctx < 128; i_ctx++ )
403 for( int i = 0; i < 5; i++ )
404 f8_bits += x264_cabac_size_decision2( &ctx, 1 );
405 f8_bits += 1 << CABAC_SIZE_BITS; //sign
407 cabac_size_5ones[i_ctx] = f8_bits;
408 cabac_transition_5ones[i_ctx] = ctx;
415 int level_idx; // index into level_tree[]
416 uint8_t cabac_state[10]; //just the contexts relevant to coding abs_level_m1
420 // save cabac state between blocks?
421 // use trellis' RD score instead of x264_mb_decimate_score?
422 // code 8x8 sig/last flags forwards with deadzone and save the contexts at
424 // change weights when using CQMs?
426 // possible optimizations:
427 // make scores fit in 32bit
428 // save quantized coefs during rd, to avoid a duplicate trellis in the final encode
429 // if trellissing all MBRD modes, finish SSD calculation so we can skip all of
430 // the normal dequant/idct/ssd/cabac
432 // the unquant_mf here is not the same as dequant_mf:
433 // in normal operation (dct->quant->dequant->idct) the dct and idct are not
434 // normalized. quant/dequant absorb those scaling factors.
435 // in this function, we just do (quant->unquant) and want the output to be
436 // comparable to the input. so unquant is the direct inverse of quant,
437 // and uses the dct scaling factors, not the idct ones.
440 int quant_trellis_cabac( x264_t *h, dctcoef *dct,
441 const udctcoef *quant_mf, const int *unquant_mf,
442 const uint16_t *coef_weight, const uint8_t *zigzag,
443 int ctx_block_cat, int i_lambda2, int b_ac,
444 int b_chroma, int dc, int i_coefs, int idx )
446 int abs_coefs[64], signs[64];
447 trellis_node_t nodes[2][8];
448 trellis_node_t *nodes_cur = nodes[0];
449 trellis_node_t *nodes_prev = nodes[1];
450 trellis_node_t *bnode;
451 const int b_interlaced = MB_INTERLACED;
452 uint8_t *cabac_state_sig = &h->cabac.state[ significant_coeff_flag_offset[b_interlaced][ctx_block_cat] ];
453 uint8_t *cabac_state_last = &h->cabac.state[ last_coeff_flag_offset[b_interlaced][ctx_block_cat] ];
454 const int f = 1 << 15; // no deadzone
458 // (# of coefs) * (# of ctx) * (# of levels tried) = 1024
459 // we don't need to keep all of those: (# of coefs) * (# of ctx) would be enough,
460 // but it takes more time to remove dead states than you gain in reduced memory.
465 } level_tree[64*8*2];
466 int i_levels_used = 1;
469 for( i = i_coefs-1; i >= b_ac; i-- )
470 if( (unsigned)(dct[zigzag[i]] * (dc?quant_mf[0]>>1:quant_mf[zigzag[i]]) + f-1) >= 2*f )
475 /* We only need to zero an empty 4x4 block. 8x8 can be
476 implicitly emptied via zero nnz, as can dc. */
477 if( i_coefs == 16 && !dc )
478 memset( dct, 0, 16 * sizeof(dctcoef) );
483 idx &= i_coefs == 64 ? 3 : 15;
485 for( ; i >= b_ac; i-- )
487 int coef = dct[zigzag[i]];
488 abs_coefs[i] = abs(coef);
489 signs[i] = coef < 0 ? -1 : 1;
493 for( int j = 1; j < 8; j++ )
494 nodes_cur[j].score = TRELLIS_SCORE_MAX;
495 nodes_cur[0].score = 0;
496 nodes_cur[0].level_idx = 0;
497 level_tree[0].abs_level = 0;
498 level_tree[0].next = 0;
500 // coefs are processed in reverse order, because that's how the abs value is coded.
501 // last_coef and significant_coef flags are normally coded in forward order, but
502 // we have to reverse them to match the levels.
503 // in 4x4 blocks, last_coef and significant_coef use a separate context for each
504 // position, so the order doesn't matter, and we don't even have to update their contexts.
505 // in 8x8 blocks, some positions share contexts, so we'll just have to hope that
506 // cabac isn't too sensitive.
508 memcpy( nodes_cur[0].cabac_state, &h->cabac.state[ coeff_abs_level_m1_offset[ctx_block_cat] ], 10 );
510 for( i = i_last_nnz; i >= b_ac; i-- )
512 int i_coef = abs_coefs[i];
513 int q = ( f + i_coef * (dc?quant_mf[0]>>1:quant_mf[zigzag[i]]) ) >> 16;
514 int cost_sig[2], cost_last[2];
517 // skip 0s: this doesn't affect the output, but saves some unnecessary computation.
520 // no need to calculate ssd of 0s: it's the same in all nodes.
521 // no need to modify level_tree for ctx=0: it starts with an infinite loop of 0s.
522 int sigindex = i_coefs == 64 ? significant_coeff_flag_offset_8x8[b_interlaced][i] : i;
523 const uint32_t cost_sig0 = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 0 )
524 * (uint64_t)i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
525 for( int j = 1; j < 8; j++ )
527 if( nodes_cur[j].score != TRELLIS_SCORE_MAX )
529 #define SET_LEVEL(n,l) \
530 level_tree[i_levels_used].abs_level = l; \
531 level_tree[i_levels_used].next = n.level_idx; \
532 n.level_idx = i_levels_used; \
535 SET_LEVEL( nodes_cur[j], 0 );
536 nodes_cur[j].score += cost_sig0;
542 XCHG( trellis_node_t*, nodes_cur, nodes_prev );
544 for( int j = 0; j < 8; j++ )
545 nodes_cur[j].score = TRELLIS_SCORE_MAX;
549 int sigindex = i_coefs == 64 ? significant_coeff_flag_offset_8x8[b_interlaced][i] : i;
550 int lastindex = i_coefs == 64 ? last_coeff_flag_offset_8x8[i] : i;
551 cost_sig[0] = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 0 );
552 cost_sig[1] = x264_cabac_size_decision_noup2( &cabac_state_sig[sigindex], 1 );
553 cost_last[0] = x264_cabac_size_decision_noup2( &cabac_state_last[lastindex], 0 );
554 cost_last[1] = x264_cabac_size_decision_noup2( &cabac_state_last[lastindex], 1 );
558 cost_sig[0] = cost_sig[1] = 0;
559 cost_last[0] = cost_last[1] = 0;
562 // there are a few cases where increasing the coeff magnitude helps,
563 // but it's only around .003 dB, and skipping them ~doubles the speed of trellis.
564 // could also try q-2: that sometimes helps, but also sometimes decimates blocks
565 // that are better left coded, especially at QP > 40.
566 for( int abs_level = q; abs_level >= q-1; abs_level-- )
568 int unquant_abs_level = (((dc?unquant_mf[0]<<1:unquant_mf[zigzag[i]]) * abs_level + 128) >> 8);
569 int d = i_coef - unquant_abs_level;
571 /* Psy trellis: bias in favor of higher AC coefficients in the reconstructed frame. */
572 if( h->mb.i_psy_trellis && i && !dc && !b_chroma )
574 int orig_coef = (i_coefs == 64) ? h->mb.pic.fenc_dct8[idx][zigzag[i]] : h->mb.pic.fenc_dct4[idx][zigzag[i]];
575 int predicted_coef = orig_coef - i_coef * signs[i];
576 int psy_value = h->mb.i_psy_trellis * abs(predicted_coef + unquant_abs_level * signs[i]);
577 int psy_weight = (i_coefs == 64) ? x264_dct8_weight_tab[zigzag[i]] : x264_dct4_weight_tab[zigzag[i]];
578 ssd = (int64_t)d*d * coef_weight[i] - psy_weight * psy_value;
581 /* FIXME: for i16x16 dc is this weight optimal? */
582 ssd = (int64_t)d*d * (dc?256:coef_weight[i]);
584 for( int j = 0; j < 8; j++ )
587 if( nodes_prev[j].score == TRELLIS_SCORE_MAX )
591 /* code the proposed level, and count how much entropy it would take */
592 if( abs_level || node_ctx )
594 unsigned f8_bits = cost_sig[ abs_level != 0 ];
597 const int i_prefix = X264_MIN( abs_level - 1, 14 );
598 f8_bits += cost_last[ node_ctx == 0 ];
599 f8_bits += x264_cabac_size_decision2( &n.cabac_state[coeff_abs_level1_ctx[node_ctx]], i_prefix > 0 );
602 uint8_t *ctx = &n.cabac_state[coeff_abs_levelgt1_ctx[node_ctx]];
603 f8_bits += cabac_size_unary[i_prefix][*ctx];
604 *ctx = cabac_transition_unary[i_prefix][*ctx];
605 if( abs_level >= 15 )
606 f8_bits += bs_size_ue_big( abs_level - 15 ) << CABAC_SIZE_BITS;
607 node_ctx = coeff_abs_level_transition[1][node_ctx];
611 f8_bits += 1 << CABAC_SIZE_BITS;
612 node_ctx = coeff_abs_level_transition[0][node_ctx];
615 n.score += (uint64_t)f8_bits * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
620 /* Optimize rounding for DC coefficients in DC-only luma 4x4/8x8 blocks. */
623 d = i_coef * signs[0] - ((unquant_abs_level * signs[0] + 8)&~15);
624 n.score += (int64_t)d*d * coef_weight[i];
627 /* save the node if it's better than any existing node with the same cabac ctx */
628 if( n.score < nodes_cur[node_ctx].score )
630 SET_LEVEL( n, abs_level );
631 nodes_cur[node_ctx] = n;
637 /* output levels from the best path through the trellis */
638 bnode = &nodes_cur[0];
639 for( int j = 1; j < 8; j++ )
640 if( nodes_cur[j].score < bnode->score )
641 bnode = &nodes_cur[j];
643 if( bnode == &nodes_cur[0] )
645 if( i_coefs == 16 && !dc )
646 memset( dct, 0, 16 * sizeof(dctcoef) );
650 int level = bnode->level_idx;
651 for( i = b_ac; level; i++ )
653 dct[zigzag[i]] = level_tree[level].abs_level * signs[i];
654 level = level_tree[level].next;
656 for( ; i < i_coefs; i++ )
662 /* FIXME: This is a gigantic hack. See below.
664 * CAVLC is much more difficult to trellis than CABAC.
666 * CABAC has only three states to track: significance map, last, and the
667 * level state machine.
668 * CAVLC, by comparison, has five: coeff_token (trailing + total),
669 * total_zeroes, zero_run, and the level state machine.
671 * I know of no paper that has managed to design a close-to-optimal trellis
672 * that covers all five of these and isn't exponential-time. As a result, this
673 * "trellis" isn't: it's just a QNS search. Patches welcome for something better.
674 * It's actually surprisingly fast, albeit not quite optimal. It's pretty close
675 * though; since CAVLC only has 2^16 possible rounding modes (assuming only two
676 * roundings as options), a bruteforce search is feasible. Testing shows
677 * that this QNS is reasonably close to optimal in terms of compression.
680 * Don't bother changing large coefficients when it wouldn't affect bit cost
681 * (e.g. only affecting bypassed suffix bits).
682 * Don't re-run all parts of CAVLC bit cost calculation when not necessary.
683 * e.g. when changing a coefficient from one non-zero value to another in
684 * such a way that trailing ones and suffix length isn't affected. */
686 int quant_trellis_cavlc( x264_t *h, dctcoef *dct,
687 const udctcoef *quant_mf, const int *unquant_mf,
688 const uint16_t *coef_weight, const uint8_t *zigzag,
689 int ctx_block_cat, int i_lambda2, int b_ac,
690 int b_chroma, int dc, int i_coefs, int idx, int b_8x8 )
692 ALIGNED_16( dctcoef quant_coefs[2][16] );
693 ALIGNED_16( dctcoef coefs[16] ) = {0};
694 int delta_distortion[16];
695 int64_t score = 1ULL<<62;
698 int nC = ctx_block_cat == DCT_CHROMA_DC ? 4 : ct_index[x264_mb_predict_non_zero_code( h, ctx_block_cat == DCT_LUMA_DC ? (idx - LUMA_DC)*16 : idx )];
700 /* Code for handling 8x8dct -> 4x4dct CAVLC munging. Input/output use a different
701 * step/start/end than internal processing. */
704 int end = i_coefs - 1;
713 i_lambda2 <<= LAMBDA_BITS;
715 /* Find last non-zero coefficient. */
716 for( i = end; i >= start; i -= step )
717 if( (unsigned)(dct[zigzag[i]] * (dc?quant_mf[0]>>1:quant_mf[zigzag[i]]) + f-1) >= 2*f )
723 /* Prepare for QNS search: calculate distortion caused by each DCT coefficient
724 * rounding to be searched.
726 * We only search two roundings (nearest and nearest-1) like in CABAC trellis,
727 * so we just store the difference in distortion between them. */
728 int i_last_nnz = b_8x8 ? i >> 2 : i;
731 for( i = b_ac, j = start; i <= i_last_nnz; i++, j += step )
733 int coef = dct[zigzag[j]];
734 int abs_coef = abs(coef);
735 int sign = coef < 0 ? -1 : 1;
736 int nearest_quant = ( f + abs_coef * (dc?quant_mf[0]>>1:quant_mf[zigzag[j]]) ) >> 16;
737 quant_coefs[1][i] = quant_coefs[0][i] = sign * nearest_quant;
738 coefs[i] = quant_coefs[1][i];
741 /* We initialize the trellis with a deadzone halfway between nearest rounding
742 * and always-round-down. This gives much better results than initializing to either
744 * FIXME: should we initialize to the deadzones used by deadzone quant? */
745 int deadzone_quant = ( f/2 + abs_coef * (dc?quant_mf[0]>>1:quant_mf[zigzag[j]]) ) >> 16;
746 int unquant1 = (((dc?unquant_mf[0]<<1:unquant_mf[zigzag[j]]) * (nearest_quant-0) + 128) >> 8);
747 int unquant0 = (((dc?unquant_mf[0]<<1:unquant_mf[zigzag[j]]) * (nearest_quant-1) + 128) >> 8);
748 int d1 = abs_coef - unquant1;
749 int d0 = abs_coef - unquant0;
750 delta_distortion[i] = (d0*d0 - d1*d1) * (dc?256:coef_weight[j]);
752 /* Psy trellis: bias in favor of higher AC coefficients in the reconstructed frame. */
753 if( h->mb.i_psy_trellis && j && !dc && !b_chroma )
755 int orig_coef = b_8x8 ? h->mb.pic.fenc_dct8[idx>>2][zigzag[j]] : h->mb.pic.fenc_dct4[idx][zigzag[j]];
756 int predicted_coef = orig_coef - coef;
757 int psy_weight = b_8x8 ? x264_dct8_weight_tab[zigzag[j]] : x264_dct4_weight_tab[zigzag[j]];
758 int psy_value0 = h->mb.i_psy_trellis * abs(predicted_coef + unquant0 * sign);
759 int psy_value1 = h->mb.i_psy_trellis * abs(predicted_coef + unquant1 * sign);
760 delta_distortion[i] += (psy_value0 - psy_value1) * psy_weight;
763 quant_coefs[0][i] = sign * (nearest_quant-1);
764 if( deadzone_quant != nearest_quant )
765 coefs[i] = quant_coefs[0][i];
767 round_mask |= 1 << i;
770 delta_distortion[i] = 0;
771 coef_mask |= (!!coefs[i]) << i;
774 /* Calculate the cost of the starting state. */
775 h->out.bs.i_bits_encoded = 0;
777 bs_write_vlc( &h->out.bs, x264_coeff0_token[nC] );
779 block_residual_write_cavlc_internal( h, ctx_block_cat, coefs + b_ac, nC );
780 score = (int64_t)h->out.bs.i_bits_encoded * i_lambda2;
782 /* QNS loop: pick the change that improves RD the most, apply it, repeat.
783 * coef_mask and round_mask are used to simplify tracking of nonzeroness
784 * and rounding modes chosen. */
787 int64_t iter_score = score;
788 int iter_distortion_delta = 0;
790 int iter_mask = coef_mask;
791 int iter_round = round_mask;
792 for( i = b_ac; i <= i_last_nnz; i++ )
794 if( !delta_distortion[i] )
797 /* Set up all the variables for this iteration. */
798 int cur_round = round_mask ^ (1 << i);
799 int round_change = (cur_round >> i)&1;
800 int old_coef = coefs[i];
801 int new_coef = quant_coefs[round_change][i];
802 int cur_mask = (coef_mask&~(1 << i))|(!!new_coef << i);
803 int cur_distortion_delta = delta_distortion[i] * (round_change ? -1 : 1);
804 int64_t cur_score = cur_distortion_delta;
808 h->out.bs.i_bits_encoded = 0;
810 bs_write_vlc( &h->out.bs, x264_coeff0_token[nC] );
812 block_residual_write_cavlc_internal( h, ctx_block_cat, coefs + b_ac, nC );
813 cur_score += (int64_t)h->out.bs.i_bits_encoded * i_lambda2;
816 if( cur_score < iter_score )
818 iter_score = cur_score;
820 iter_mask = cur_mask;
821 iter_round = cur_round;
822 iter_distortion_delta = cur_distortion_delta;
827 score = iter_score - iter_distortion_delta;
828 coef_mask = iter_mask;
829 round_mask = iter_round;
830 coefs[iter_coef] = quant_coefs[((round_mask >> iter_coef)&1)][iter_coef];
831 /* Don't try adjusting coefficients we've already adjusted.
832 * Testing suggests this doesn't hurt results -- and sometimes actually helps. */
833 delta_distortion[iter_coef] = 0;
841 for( i = b_ac, j = start; i <= i_last_nnz; i++, j += step )
842 dct[zigzag[j]] = coefs[i];
843 for( ; j <= end; j += step )
852 for( i = start; i <= end; i+=step )
855 memset( dct, 0, 16*sizeof(dctcoef) );
860 const static uint8_t x264_zigzag_scan2[4] = {0,1,2,3};
862 int x264_quant_dc_trellis( x264_t *h, dctcoef *dct, int i_quant_cat,
863 int i_qp, int ctx_block_cat, int b_intra, int b_chroma, int idx )
865 if( h->param.b_cabac )
866 return quant_trellis_cabac( h, dct,
867 h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
868 NULL, ctx_block_cat==DCT_CHROMA_DC ? x264_zigzag_scan2 : x264_zigzag_scan4[MB_INTERLACED],
869 ctx_block_cat, h->mb.i_trellis_lambda2[b_chroma][b_intra], 0, b_chroma, 1, ctx_block_cat==DCT_CHROMA_DC ? 4 : 16, idx );
871 if( ctx_block_cat != DCT_CHROMA_DC )
872 ctx_block_cat = DCT_LUMA_DC;
874 return quant_trellis_cavlc( h, dct,
875 h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
876 NULL, ctx_block_cat==DCT_CHROMA_DC ? x264_zigzag_scan2 : x264_zigzag_scan4[MB_INTERLACED],
877 ctx_block_cat, h->mb.i_trellis_lambda2[b_chroma][b_intra], 0, b_chroma, 1, ctx_block_cat==DCT_CHROMA_DC ? 4 : 16, idx, 0 );
880 int x264_quant_4x4_trellis( x264_t *h, dctcoef *dct, int i_quant_cat,
881 int i_qp, int ctx_block_cat, int b_intra, int b_chroma, int idx )
883 static const uint8_t ctx_ac[14] = {0,1,0,0,1,0,0,1,0,0,0,1,0,0};
884 int b_ac = ctx_ac[ctx_block_cat];
885 if( h->param.b_cabac )
886 return quant_trellis_cabac( h, dct,
887 h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
888 x264_dct4_weight2_zigzag[MB_INTERLACED],
889 x264_zigzag_scan4[MB_INTERLACED],
890 ctx_block_cat, h->mb.i_trellis_lambda2[b_chroma][b_intra], b_ac, b_chroma, 0, 16, idx );
892 return quant_trellis_cavlc( h, dct,
893 h->quant4_mf[i_quant_cat][i_qp], h->unquant4_mf[i_quant_cat][i_qp],
894 x264_dct4_weight2_zigzag[MB_INTERLACED],
895 x264_zigzag_scan4[MB_INTERLACED],
896 ctx_block_cat, h->mb.i_trellis_lambda2[b_chroma][b_intra], b_ac, b_chroma, 0, 16, idx, 0 );
899 int x264_quant_8x8_trellis( x264_t *h, dctcoef *dct, int i_quant_cat,
900 int i_qp, int ctx_block_cat, int b_intra, int b_chroma, int idx )
902 if( h->param.b_cabac )
904 return quant_trellis_cabac( h, dct,
905 h->quant8_mf[i_quant_cat][i_qp], h->unquant8_mf[i_quant_cat][i_qp],
906 x264_dct8_weight2_zigzag[MB_INTERLACED],
907 x264_zigzag_scan8[MB_INTERLACED],
908 ctx_block_cat, h->mb.i_trellis_lambda2[b_chroma][b_intra], 0, b_chroma, 0, 64, idx );
911 /* 8x8 CAVLC is split into 4 4x4 blocks */
913 for( int i = 0; i < 4; i++ )
915 int nz = quant_trellis_cavlc( h, dct,
916 h->quant8_mf[i_quant_cat][i_qp], h->unquant8_mf[i_quant_cat][i_qp],
917 x264_dct8_weight2_zigzag[MB_INTERLACED],
918 x264_zigzag_scan8[MB_INTERLACED],
919 DCT_LUMA_4x4, h->mb.i_trellis_lambda2[b_chroma][b_intra], 0, b_chroma, 0, 16, idx*4+i, 1 );
920 /* Set up nonzero count for future calls */
921 h->mb.cache.non_zero_count[x264_scan8[idx*4+i]] = nz;