ba1397d61adb5c11104db73993deee41de6b3c0b
[x262.git] / encoder / rdo.c
1 /*****************************************************************************
2  * rdo.c: h264 encoder library (rate-distortion optimization)
3  *****************************************************************************
4  * Copyright (C) 2005 x264 project
5  *
6  * Authors: Loren Merritt <lorenm@u.washington.edu>
7  *
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.
12  *
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.
17  *
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  *****************************************************************************/
22
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. */
26
27 #define RDO_SKIP_BS
28
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
37 #include "cavlc.c"
38
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
47 #include "cabac.c"
48
49
50 static int ssd_mb( x264_t *h )
51 {
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 );
58 }
59
60 static int x264_rd_cost_mb( x264_t *h, int i_lambda2 )
61 {
62     int b_transform_bak = h->mb.b_transform_8x8;
63     int i_ssd;
64     int i_bits;
65
66     x264_macroblock_encode( h );
67
68     i_ssd = ssd_mb( h );
69
70     if( IS_SKIP( h->mb.i_type ) )
71     {
72         i_bits = 1 * i_lambda2;
73     }
74     else if( h->param.b_cabac )
75     {
76         x264_cabac_t cabac_tmp = h->cabac;
77         cabac_tmp.f8_bits_encoded = 0;
78         x264_macroblock_size_cabac( h, &cabac_tmp );
79         i_bits = ( cabac_tmp.f8_bits_encoded * i_lambda2 + 128 ) >> 8;
80     }
81     else
82     {
83         bs_t bs_tmp = h->out.bs;
84         bs_tmp.i_bits_encoded = 0;
85         x264_macroblock_size_cavlc( h, &bs_tmp );
86         i_bits = bs_tmp.i_bits_encoded * i_lambda2;
87     }
88
89     h->mb.b_transform_8x8 = b_transform_bak;
90
91     return i_ssd + i_bits;
92 }
93
94
95 /****************************************************************************
96  * Trellis RD quantization
97  ****************************************************************************/
98
99 #define TRELLIS_SCORE_MAX (1ULL<<50)
100 #define CABAC_SIZE_BITS 8
101 #define SSD_WEIGHT_BITS 5
102 #define LAMBDA_BITS 4
103
104 /* precalculate the cost of coding abs_level_m1 */
105 static int cabac_prefix_transition[15][128];
106 static int cabac_prefix_size[15][128];
107 void x264_rdo_init( )
108 {
109     int i_prefix;
110     int i_ctx;
111     for( i_prefix = 0; i_prefix < 15; i_prefix++ )
112     {
113         for( i_ctx = 0; i_ctx < 128; i_ctx++ )
114         {
115             int f8_bits = 0;
116             uint8_t ctx = i_ctx;
117             int i;
118
119             for( i = 1; i < i_prefix; i++ )
120                 f8_bits += x264_cabac_size_decision2( &ctx, 1 );
121             if( i_prefix > 0 && i_prefix < 14 )
122                 f8_bits += x264_cabac_size_decision2( &ctx, 0 );
123             f8_bits += 1 << CABAC_SIZE_BITS; //sign
124
125             cabac_prefix_size[i_prefix][i_ctx] = f8_bits;
126             cabac_prefix_transition[i_prefix][i_ctx] = ctx;
127         }
128     }
129 }
130
131 // node ctx: 0..3: abslevel1 (with abslevelgt1 == 0).
132 //           4..7: abslevelgt1 + 3 (and abslevel1 doesn't matter).
133 /* map node ctx => cabac ctx for level=1 */
134 static const int coeff_abs_level1_ctx[8] = { 1, 2, 3, 4, 0, 0, 0, 0 };
135 /* map node ctx => cabac ctx for level>1 */
136 static const int coeff_abs_levelgt1_ctx[8] = { 5, 5, 5, 5, 6, 7, 8, 9 };
137 static const int coeff_abs_level_transition[2][8] = {
138 /* update node.ctx after coding a level=1 */
139     { 1, 2, 3, 3, 4, 5, 6, 7 },
140 /* update node.ctx after coding a level>1 */
141     { 4, 4, 4, 4, 5, 6, 7, 7 }
142 };
143
144 static const int lambda2_tab[6] = { 1024, 1290, 1625, 2048, 2580, 3251 };
145
146 typedef struct {
147     uint64_t score;
148     int level_idx; // index into level_tree[]
149     uint8_t cabac_state[10]; //just the contexts relevant to coding abs_level_m1
150 } trellis_node_t;
151
152 // TODO:
153 // support chroma and i16x16 DC
154 // save cabac state between blocks?
155 // use trellis' RD score instead of x264_mb_decimate_score?
156 // code 8x8 sig/last flags forwards with deadzone and save the contexts at
157 //   each position?
158 // change weights when using CQMs?
159
160 // possible optimizations:
161 // make scores fit in 32bit
162 // save quantized coefs during rd, to avoid a duplicate trellis in the final encode
163 // if trellissing all MBRD modes, finish SSD calculation so we can skip all of
164 //   the normal dequant/idct/ssd/cabac
165
166 // the unquant_mf here is not the same as dequant_mf:
167 // in normal operation (dct->quant->dequant->idct) the dct and idct are not
168 // normalized. quant/dequant absorb those scaling factors.
169 // in this function, we just do (quant->unquant) and want the output to be
170 // comparable to the input. so unquant is the direct inverse of quant,
171 // and uses the dct scaling factors, not the idct ones.
172
173 static void quant_trellis_cabac( x264_t *h, int16_t *dct,
174                                  const int *quant_mf, const int *unquant_mf,
175                                  const int *coef_weight, const int *zigzag,
176                                  int i_ctxBlockCat, int i_qbits, int i_lambda2, int b_ac, int i_coefs )
177 {
178     int abs_coefs[64], signs[64];
179     trellis_node_t nodes[2][8];
180     trellis_node_t *nodes_cur = nodes[0];
181     trellis_node_t *nodes_prev = nodes[1];
182     trellis_node_t *bnode;
183     uint8_t cabac_state_sig[64];
184     uint8_t cabac_state_last[64];
185     const int f = 1 << (i_qbits-1); // no deadzone
186     int i_last_nnz = -1;
187     int i, j;
188
189     // (# of coefs) * (# of ctx) * (# of levels tried) = 1024
190     // we don't need to keep all of those: (# of coefs) * (# of ctx) would be enough,
191     // but it takes more time to remove dead states than you gain in reduced memory.
192     struct {
193         uint16_t abs_level;
194         uint16_t next;
195     } level_tree[64*8*2];
196     int i_levels_used = 1;
197
198     /* init coefs */
199     for( i = b_ac; i < i_coefs; i++ )
200     {
201         int coef = dct[zigzag[i]];
202         abs_coefs[i] = abs(coef);
203         signs[i] = coef < 0 ? -1 : 1;
204         if( f <= abs_coefs[i] * quant_mf[zigzag[i]] )
205             i_last_nnz = i;
206     }
207
208     if( i_last_nnz == -1 )
209     {
210         memset( dct, 0, i_coefs * sizeof(*dct) );
211         return;
212     }
213
214     /* init trellis */
215     for( i = 1; i < 8; i++ )
216         nodes_cur[i].score = TRELLIS_SCORE_MAX;
217     nodes_cur[0].score = 0;
218     nodes_cur[0].level_idx = 0;
219     level_tree[0].abs_level = 0;
220     level_tree[0].next = 0;
221
222     // coefs are processed in reverse order, because that's how the abs value is coded.
223     // last_coef and significant_coef flags are normally coded in forward order, but
224     // we have to reverse them to match the levels.
225     // in 4x4 blocks, last_coef and significant_coef use a separate context for each
226     // position, so the order doesn't matter, and we don't even have to update their contexts.
227     // in 8x8 blocks, some positions share contexts, so we'll just have to hope that
228     // cabac isn't too sensitive.
229
230     if( i_coefs == 64 )
231     {
232         const uint8_t *ctx_sig  = &h->cabac.state[ significant_coeff_flag_offset[i_ctxBlockCat] ];
233         const uint8_t *ctx_last = &h->cabac.state[ last_coeff_flag_offset[i_ctxBlockCat] ];
234         for( i = 0; i < 63; i++ )
235         {
236             cabac_state_sig[i]  = ctx_sig[ significant_coeff_flag_offset_8x8[i] ];
237             cabac_state_last[i] = ctx_last[ last_coeff_flag_offset_8x8[i] ];
238         }
239     }
240     else
241     {
242         memcpy( cabac_state_sig,  &h->cabac.state[ significant_coeff_flag_offset[i_ctxBlockCat] ], 15 );
243         memcpy( cabac_state_last, &h->cabac.state[ last_coeff_flag_offset[i_ctxBlockCat] ], 15 );
244     }
245     memcpy( nodes_cur[0].cabac_state, &h->cabac.state[ coeff_abs_level_m1_offset[i_ctxBlockCat] ], 10 );
246
247     for( i = i_last_nnz; i >= b_ac; i-- )
248     {
249         int i_coef = abs_coefs[i];
250         int q = ( f + i_coef * quant_mf[zigzag[i]] ) >> i_qbits;
251         int abs_level;
252         int cost_sig[2], cost_last[2];
253         trellis_node_t n;
254
255         // skip 0s: this doesn't affect the output, but saves some unnecessary computation.
256         if( q == 0 )
257         {
258             // no need to calculate ssd of 0s: it's the same in all nodes.
259             // no need to modify level_tree for ctx=0: it starts with an infinite loop of 0s.
260             const int cost_sig0 = x264_cabac_size_decision_noup( &cabac_state_sig[i], 0 )
261                                 * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
262             for( j = 1; j < 8; j++ )
263             {
264                 if( nodes_cur[j].score != TRELLIS_SCORE_MAX )
265                 {
266 #define SET_LEVEL(n,l) \
267                     level_tree[i_levels_used].abs_level = l; \
268                     level_tree[i_levels_used].next = n.level_idx; \
269                     n.level_idx = i_levels_used; \
270                     i_levels_used++;
271
272                     SET_LEVEL( nodes_cur[j], 0 );
273                     nodes_cur[j].score += cost_sig0;
274                 }
275             }
276             continue;
277         }
278
279         XCHG( trellis_node_t*, nodes_cur, nodes_prev );
280
281         for( j = 0; j < 8; j++ )
282             nodes_cur[j].score = TRELLIS_SCORE_MAX;
283
284         if( i < i_coefs-1 )
285         {
286             cost_sig[0] = x264_cabac_size_decision_noup( &cabac_state_sig[i], 0 );
287             cost_sig[1] = x264_cabac_size_decision_noup( &cabac_state_sig[i], 1 );
288             cost_last[0] = x264_cabac_size_decision_noup( &cabac_state_last[i], 0 );
289             cost_last[1] = x264_cabac_size_decision_noup( &cabac_state_last[i], 1 );
290         }
291         else
292         {
293             cost_sig[0] = cost_sig[1] = 0;
294             cost_last[0] = cost_last[1] = 0;
295         }
296
297         // there are a few cases where increasing the coeff magnitude helps,
298         // but it's only around .003 dB, and skipping them ~doubles the speed of trellis.
299         // could also try q-2: that sometimes helps, but also sometimes decimates blocks
300         // that are better left coded, especially at QP > 40.
301         for( abs_level = q; abs_level >= q-1; abs_level-- )
302         {
303             int d = i_coef - ((unquant_mf[zigzag[i]] * abs_level + 128) >> 8);
304             uint64_t ssd = (int64_t)d*d * coef_weight[i];
305
306             for( j = 0; j < 8; j++ )
307             {
308                 int node_ctx = j;
309                 if( nodes_prev[j].score == TRELLIS_SCORE_MAX )
310                     continue;
311                 n = nodes_prev[j];
312
313                 /* code the proposed level, and count how much entropy it would take */
314                 if( abs_level || node_ctx )
315                 {
316                     unsigned f8_bits = cost_sig[ abs_level != 0 ];
317                     if( abs_level )
318                     {
319                         const int i_prefix = X264_MIN( abs_level - 1, 14 );
320                         f8_bits += cost_last[ node_ctx == 0 ];
321                         f8_bits += x264_cabac_size_decision2( &n.cabac_state[coeff_abs_level1_ctx[node_ctx]], i_prefix > 0 );
322                         if( i_prefix > 0 )
323                         {
324                             uint8_t *ctx = &n.cabac_state[coeff_abs_levelgt1_ctx[node_ctx]];
325                             f8_bits += cabac_prefix_size[i_prefix][*ctx];
326                             *ctx = cabac_prefix_transition[i_prefix][*ctx];
327                             if( abs_level >= 15 )
328                                 f8_bits += bs_size_ue( abs_level - 15 ) << CABAC_SIZE_BITS;
329                             node_ctx = coeff_abs_level_transition[1][node_ctx];
330                         }
331                         else
332                         {
333                             f8_bits += 1 << CABAC_SIZE_BITS;
334                             node_ctx = coeff_abs_level_transition[0][node_ctx];
335                         }
336                     }
337                     n.score += (uint64_t)f8_bits * i_lambda2 >> ( CABAC_SIZE_BITS - LAMBDA_BITS );
338                 }
339
340                 n.score += ssd;
341
342                 /* save the node if it's better than any existing node with the same cabac ctx */
343                 if( n.score < nodes_cur[node_ctx].score )
344                 {
345                     SET_LEVEL( n, abs_level );
346                     nodes_cur[node_ctx] = n;
347                 }
348             }
349         }
350     }
351
352     /* output levels from the best path through the trellis */
353     bnode = &nodes_cur[0];
354     for( j = 1; j < 8; j++ )
355         if( nodes_cur[j].score < bnode->score )
356             bnode = &nodes_cur[j];
357
358     j = bnode->level_idx;
359     for( i = b_ac; i < i_coefs; i++ )
360     {
361         dct[zigzag[i]] = level_tree[j].abs_level * signs[i];
362         j = level_tree[j].next;
363     }
364 }
365
366
367 void x264_quant_4x4_trellis( x264_t *h, int16_t dct[4][4], int i_quant_cat,
368                              int i_qp, int i_ctxBlockCat, int b_intra )
369 {
370     const int i_qbits = i_qp / 6;
371     const int i_mf = i_qp % 6;
372     const int b_ac = (i_ctxBlockCat == DCT_LUMA_AC);
373     /* should the lambdas be different? I'm just matching the behaviour of deadzone quant. */
374     const int i_lambda_mult = b_intra ? 65 : 85;
375     const int i_lambda2 = ((lambda2_tab[i_mf] * i_lambda_mult*i_lambda_mult / 10000)
376                           << (2*i_qbits)) >> LAMBDA_BITS;
377
378     quant_trellis_cabac( h, (int16_t*)dct,
379         (int*)h->quant4_mf[i_quant_cat][i_mf], h->unquant4_mf[i_quant_cat][i_qp],
380         x264_dct4_weight2_zigzag, x264_zigzag_scan4,
381         i_ctxBlockCat, 15+i_qbits, i_lambda2, b_ac, 16 );
382 }
383
384
385 void x264_quant_8x8_trellis( x264_t *h, int16_t dct[8][8], int i_quant_cat,
386                              int i_qp, int b_intra )
387 {
388     const int i_qbits = i_qp / 6;
389     const int i_mf = i_qp % 6;
390     const int i_lambda_mult = b_intra ? 65 : 85;
391     const int i_lambda2 = ((lambda2_tab[i_mf] * i_lambda_mult*i_lambda_mult / 10000)
392                           << (2*i_qbits)) >> LAMBDA_BITS;
393
394     quant_trellis_cabac( h, (int16_t*)dct,
395         (int*)h->quant8_mf[i_quant_cat][i_mf], h->unquant8_mf[i_quant_cat][i_qp],
396         x264_dct8_weight2_zigzag, x264_zigzag_scan8,
397         DCT_LUMA_8x8, 16+i_qbits, i_lambda2, 0, 64 );
398 }
399