remove unused adaptive cabac_idc code
[x262.git] / encoder / me.c
1 /*****************************************************************************
2  * me.c: h264 encoder library (Motion Estimation)
3  *****************************************************************************
4  * Copyright (C) 2003 Laurent Aimar
5  * $Id: me.c,v 1.1 2004/06/03 19:27:08 fenrir Exp $
6  *
7  * Authors: Laurent Aimar <fenrir@via.ecp.fr>
8  *          Loren Merritt <lorenm@u.washington.edu>
9  *
10  * This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software
22  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
23  *****************************************************************************/
24
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <string.h>
28
29 #include "common/common.h"
30 #include "me.h"
31
32 /* presets selected from good points on the speed-vs-quality curve of several test videos
33  * subpel_iters[i_subpel_refine] = { refine_hpel, refine_qpel, me_hpel, me_qpel }
34  * where me_* are the number of EPZS iterations run on all candidate block types,
35  * and refine_* are run only on the winner. */
36 static const int subpel_iterations[][4] = 
37    {{1,0,0,0},
38     {1,1,0,0},
39     {0,1,1,0},
40     {0,2,1,0},
41     {0,2,1,1},
42     {0,2,1,2},
43     {0,0,2,3}};
44
45 static void refine_subpel( x264_t *h, x264_me_t *m, int hpel_iters, int qpel_iters, int *p_halfpel_thresh, int b_refine_qpel );
46
47 #define COST_MV( mx, my ) \
48 { \
49     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], m->i_stride[0],     \
50                    &p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] ) \
51              + p_cost_mvx[ (mx)<<2 ]  \
52              + p_cost_mvy[ (my)<<2 ]; \
53     if( cost < bcost ) \
54     {                  \
55         bcost = cost;  \
56         bmx = mx;      \
57         bmy = my;      \
58     } \
59 }
60
61 void x264_me_search_ref( x264_t *h, x264_me_t *m, int (*mvc)[2], int i_mvc, int *p_halfpel_thresh )
62 {
63     const int i_pixel = m->i_pixel;
64     const int i_me_range = h->param.analyse.i_me_range;
65     int bmx, bmy, bcost;
66     int omx, omy, pmx, pmy;
67     uint8_t *p_fref = m->p_fref[0];
68     int i, j;
69
70     int mv_x_min = h->mb.mv_min_fpel[0];
71     int mv_y_min = h->mb.mv_min_fpel[1];
72     int mv_x_max = h->mb.mv_max_fpel[0];
73     int mv_y_max = h->mb.mv_max_fpel[1];
74
75     const int16_t *p_cost_mvx = m->p_cost_mv - m->mvp[0];
76     const int16_t *p_cost_mvy = m->p_cost_mv - m->mvp[1];
77
78     if( h->mb.i_me_method == X264_ME_UMH )
79     {
80         /* clamp mvp to inside frame+padding, so that we don't have to check it each iteration */
81         p_cost_mvx = m->p_cost_mv - x264_clip3( m->mvp[0], h->mb.mv_min[0], h->mb.mv_max[0] );
82         p_cost_mvy = m->p_cost_mv - x264_clip3( m->mvp[1], h->mb.mv_min[1], h->mb.mv_max[1] );
83     }
84
85     bmx = pmx = x264_clip3( ( m->mvp[0] + 2 ) >> 2, mv_x_min, mv_x_max );
86     bmy = pmy = x264_clip3( ( m->mvp[1] + 2 ) >> 2, mv_y_min, mv_y_max );
87     bcost = COST_MAX;
88     COST_MV( pmx, pmy );
89     /* I don't know why this helps */
90     bcost -= p_cost_mvx[ bmx<<2 ] + p_cost_mvy[ bmy<<2 ];
91
92     /* try extra predictors if provided */
93     for( i = 0; i < i_mvc; i++ )
94     {
95         const int mx = x264_clip3( ( mvc[i][0] + 2 ) >> 2, mv_x_min, mv_x_max );
96         const int my = x264_clip3( ( mvc[i][1] + 2 ) >> 2, mv_y_min, mv_y_max );
97         if( mx != bmx || my != bmy )
98             COST_MV( mx, my );
99     }
100     
101     COST_MV( 0, 0 );
102
103     mv_x_max += 8;
104     mv_y_max += 8;
105     mv_x_min -= 8;
106     mv_y_min -= 8;
107
108     switch( h->mb.i_me_method )
109     {
110     case X264_ME_DIA:
111         /* diamond search, radius 1 */
112 #define DIA1_ITER(mx, my)\
113         {\
114             omx = mx;\
115             omy = my;\
116             COST_MV( omx  , omy-1 );\
117             COST_MV( omx  , omy+1 );\
118             COST_MV( omx-1, omy   );\
119             COST_MV( omx+1, omy   );\
120         }
121
122         for( i = 0; i < i_me_range; i++ )
123         {
124             DIA1_ITER( bmx, bmy );
125             if( bmx == omx && bmy == omy )
126                 break;
127         }
128         break;
129
130     case X264_ME_HEX:
131         /* hexagon search, radius 2 */
132 #define HEX2_ITER(mx, my)\
133         {\
134             omx = mx;\
135             omy = my;\
136             COST_MV( omx-2, omy   );\
137             COST_MV( omx-1, omy+2 );\
138             COST_MV( omx+1, omy+2 );\
139             COST_MV( omx+2, omy   );\
140             COST_MV( omx+1, omy-2 );\
141             COST_MV( omx-1, omy-2 );\
142         }
143
144         for( i = 0; i < i_me_range/2; i++ )
145         {
146             HEX2_ITER( bmx, bmy );
147             if( bmx == omx && bmy == omy )
148                 break;
149         }
150         /* square refine */
151         DIA1_ITER( bmx, bmy );
152         COST_MV( omx-1, omy-1 );
153         COST_MV( omx-1, omy+1 );
154         COST_MV( omx+1, omy-1 );
155         COST_MV( omx+1, omy+1 );
156         break;
157
158     case X264_ME_UMH:
159         /* Uneven-cross Multi-Hexagon-grid Search
160          * as in JM, except without early termination */
161
162         DIA1_ITER( pmx, pmy );
163         if( pmx || pmy )
164             DIA1_ITER( 0, 0 );
165         DIA1_ITER( bmx, bmy );
166
167         if(i_pixel == PIXEL_4x4)
168             goto umh_small_hex;
169
170         /* cross */
171         omx = bmx; omy = bmy;
172         for( i = 1; i < i_me_range; i+=2 )
173         {
174             if( omx + i <= mv_x_max )
175                 COST_MV( omx + i, omy );
176             if( omx - i >= mv_x_min )
177                 COST_MV( omx - i, omy );
178         }
179         for( i = 1; i < i_me_range/2; i+=2 )
180         {
181             if( omy + i <= mv_y_max )
182                 COST_MV( omx, omy + i );
183             if( omy - i >= mv_y_min )
184                 COST_MV( omx, omy - i );
185         }
186
187         /* 5x5 ESA */
188         omx = bmx; omy = bmy;
189         for( i = 0; i < 24; i++ )
190         {
191             static const int square2_x[24] = {1,1,0,-1,-1,-1, 0, 1, 2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1, 0, 1, 2};
192             static const int square2_y[24] = {0,1,1, 1, 0,-1,-1,-1,-1,0,1,2,2,2, 2, 2, 1, 0,-1,-2,-2,-2,-2,-2};
193             COST_MV( omx + square2_x[i], omy + square2_y[i] );
194         }
195         /* hexagon grid */
196         omx = bmx; omy = bmy;
197         for( i = 1; i <= i_me_range/4; i++ )
198         {
199             int bounds_check = 4*i > X264_MIN4( mv_x_max-omx, mv_y_max-omy, omx-mv_x_min, omy-mv_y_min );
200             for( j = 0; j < 16; j++ )
201             {
202                 static const int hex4_x[16] = {0,-2,-4,-4,-4,-4,-4,-2, 0, 2, 4, 4,4,4,4,2};
203                 static const int hex4_y[16] = {4, 3, 2, 1, 0,-1,-2,-3,-4,-3,-2,-1,0,1,2,3};
204                 int mx = omx + hex4_x[j]*i;
205                 int my = omy + hex4_y[j]*i;
206                 if( !bounds_check || ( mx >= mv_x_min && mx <= mv_x_max
207                                     && my >= mv_y_min && my <= mv_y_max ) )
208                     COST_MV( mx, my );
209             }
210         }
211 umh_small_hex:
212         /* iterative search */
213         for( i = 0; i < i_me_range; i++ )
214         {
215             HEX2_ITER( bmx, bmy );
216             if( bmx == omx && bmy == omy )
217                 break;
218         }
219         for( i = 0; i < i_me_range; i++ )
220         {
221             DIA1_ITER( bmx, bmy );
222             if( bmx == omx && bmy == omy )
223                 break;
224         }
225         break;
226
227     case X264_ME_ESA:
228         {
229             const int min_x = X264_MAX( bmx - i_me_range, mv_x_min);
230             const int min_y = X264_MAX( bmy - i_me_range, mv_y_min);
231             const int max_x = X264_MIN( bmx + i_me_range, mv_x_max);
232             const int max_y = X264_MIN( bmy + i_me_range, mv_y_max);
233             for( omy = min_y; omy <= max_y; omy++ )
234                 for( omx = min_x; omx <= max_x; omx++ )
235                 {
236                     COST_MV( omx, omy );
237                 }
238         }
239         break;
240     }
241
242     /* -> qpel mv */
243     m->mv[0] = bmx << 2;
244     m->mv[1] = bmy << 2;
245
246     /* compute the real cost */
247     m->cost_mv = p_cost_mvx[ m->mv[0] ] + p_cost_mvy[ m->mv[1] ];
248     m->cost = bcost;
249     if( bmx == pmx && bmy == pmy )
250         m->cost += m->cost_mv;
251     
252     /* subpel refine */
253     if( h->mb.i_subpel_refine >= 2 )
254     {
255         int hpel = subpel_iterations[h->mb.i_subpel_refine][2];
256         int qpel = subpel_iterations[h->mb.i_subpel_refine][3];
257         refine_subpel( h, m, hpel, qpel, p_halfpel_thresh, 0 );
258     }
259 }
260 #undef COST_MV
261
262 void x264_me_refine_qpel( x264_t *h, x264_me_t *m )
263 {
264     int hpel = subpel_iterations[h->mb.i_subpel_refine][0];
265     int qpel = subpel_iterations[h->mb.i_subpel_refine][1];
266
267     if( m->i_pixel <= PIXEL_8x8 && h->sh.i_type == SLICE_TYPE_P )
268         m->cost -= m->i_ref_cost;
269         
270     refine_subpel( h, m, hpel, qpel, NULL, 1 );
271 }
272
273 #define COST_MV_SAD( mx, my ) \
274 { \
275     int stride = 16; \
276     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix, &stride, mx, my, bw, bh ); \
277     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], m->i_stride[0], src, stride ) \
278              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
279     if( cost < bcost ) \
280     {                  \
281         bcost = cost;  \
282         bmx = mx;      \
283         bmy = my;      \
284     } \
285 }
286
287 #define COST_MV_SATD( mx, my ) \
288 { \
289     int stride = 16; \
290     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix, &stride, mx, my, bw, bh ); \
291     int cost = h->pixf.mbcmp[i_pixel]( m->p_fenc[0], m->i_stride[0], src, stride ) \
292              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
293     if( b_chroma_me && cost < bcost ) \
294     { \
295         h->mc.mc_chroma( m->p_fref[4], m->i_stride[1], pix, 8, mx, my, bw/2, bh/2 ); \
296         cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[1], m->i_stride[1], pix, 8 ); \
297         if( cost < bcost ) \
298         { \
299             h->mc.mc_chroma( m->p_fref[5], m->i_stride[1], pix, 8, mx, my, bw/2, bh/2 ); \
300             cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[2], m->i_stride[1], pix, 8 ); \
301         } \
302     } \
303     if( cost < bcost ) \
304     {                  \
305         bcost = cost;  \
306         bmx = mx;      \
307         bmy = my;      \
308     } \
309 }
310
311 static void refine_subpel( x264_t *h, x264_me_t *m, int hpel_iters, int qpel_iters, int *p_halfpel_thresh, int b_refine_qpel )
312 {
313     const int bw = x264_pixel_size[m->i_pixel].w;
314     const int bh = x264_pixel_size[m->i_pixel].h;
315     const int16_t *p_cost_mvx = m->p_cost_mv - m->mvp[0];
316     const int16_t *p_cost_mvy = m->p_cost_mv - m->mvp[1];
317     const int i_pixel = m->i_pixel;
318     const int b_chroma_me = h->mb.b_chroma_me && i_pixel <= PIXEL_8x8;
319
320     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
321     int omx, omy;
322     int i;
323
324     int bmx = m->mv[0];
325     int bmy = m->mv[1];
326     int bcost = m->cost;
327
328
329     /* try the subpel component of the predicted mv if it's close to
330      * the result of the fullpel search */
331     if( hpel_iters )
332     {
333         int mx = X264_ABS(bmx - m->mvp[0]) < 4 ? m->mvp[0] : bmx;
334         int my = X264_ABS(bmy - m->mvp[1]) < 4 ? m->mvp[1] : bmy;
335         if( mx != bmx || my != bmy )
336             COST_MV_SAD( mx, my );
337     }
338     
339     /* hpel search */
340     for( i = hpel_iters; i > 0; i-- )
341     {
342         omx = bmx;
343         omy = bmy;
344         COST_MV_SAD( omx, omy - 2 );
345         COST_MV_SAD( omx, omy + 2 );
346         COST_MV_SAD( omx - 2, omy );
347         COST_MV_SAD( omx + 2, omy );
348         if( bmx == omx && bmy == omy )
349             break;
350     }
351     
352     if( !b_refine_qpel )
353     {
354         bcost = COST_MAX;
355         COST_MV_SATD( bmx, bmy );
356     }
357     
358     /* early termination when examining multiple reference frames */
359     if( p_halfpel_thresh )
360     {
361         if( (bcost*7)>>3 > *p_halfpel_thresh )
362         {
363             m->cost = bcost;
364             m->mv[0] = bmx;
365             m->mv[1] = bmy;
366             // don't need cost_mv
367             return;
368         }
369         else if( bcost < *p_halfpel_thresh )
370             *p_halfpel_thresh = bcost;
371     }
372
373     /* qpel search */
374     for( i = qpel_iters; i > 0; i-- )
375     {
376         omx = bmx;
377         omy = bmy;
378         COST_MV_SATD( omx, omy - 1 );
379         COST_MV_SATD( omx, omy + 1 );
380         COST_MV_SATD( omx - 1, omy );
381         COST_MV_SATD( omx + 1, omy );
382         if( bmx == omx && bmy == omy )
383             break;
384     }
385
386     m->cost = bcost;
387     m->mv[0] = bmx;
388     m->mv[1] = bmy;
389     m->cost_mv = p_cost_mvx[ bmx ] + p_cost_mvy[ bmy ];
390 }
391