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