* all: Patches by Loren Merritt:
[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  *
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., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
22  *****************************************************************************/
23
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27
28 #include "../core/common.h"
29 #include "me.h"
30
31 /* presets selected from good points on the speed-vs-quality curve of several test videos
32  * subpel_iters[i_subpel_refine] = { refine_hpel, refine_qpel, me_hpel, me_qpel }
33  * where me_* are the number of EPZS iterations run on all candidate block types,
34  * and refine_* are run only on the winner. */
35 const static int subpel_iterations[][4] = 
36    {{1,0,0,0},
37     {1,1,0,0},
38     {1,2,0,0},
39     {0,2,1,0},
40     {0,2,1,1},
41     {0,2,1,2}};
42
43 static void refine_subpel( x264_t *h, x264_me_t *m, int hpel_iters, int qpel_iters );
44
45 void x264_me_search( x264_t *h, x264_me_t *m )
46 {
47     const int i_pixel = m->i_pixel;
48     int bcost;
49     int bmx, bmy;
50     uint8_t *p_fref = m->p_fref;
51     int i_iter;
52     int hpel, qpel;
53
54
55     /* init with mvp */
56     /* XXX: We don't need to clamp because the way diamond work, we will
57      * never go outside padded picture, and predict mv won't compute vector
58      * with componant magnitude greater.
59      * XXX: if some vector can go outside, (accelerator, ....) you need to clip
60      * them yourself */
61     bmx = x264_clip3( ( m->mvp[0] + 2 ) >> 2, -m->i_mv_range, m->i_mv_range );
62     bmy = x264_clip3( ( m->mvp[1] + 2 ) >> 2, -m->i_mv_range, m->i_mv_range );
63
64     p_fref = &m->p_fref[bmy * m->i_stride + bmx];
65     bcost = h->pixf.sad[i_pixel]( m->p_fenc, m->i_stride, p_fref, m->i_stride );
66
67
68     /* try a candidate if provided */
69     if( m->b_mvc )
70     {
71         const int mx = x264_clip3( ( m->mvc[0] + 2 ) >> 2, -m->i_mv_range, m->i_mv_range );
72         const int my = x264_clip3( ( m->mvc[1] + 2 ) >> 2, -m->i_mv_range, m->i_mv_range );
73         uint8_t *p_fref2 = &m->p_fref[my*m->i_stride+mx];
74         int cost = h->pixf.sad[i_pixel]( m->p_fenc, m->i_stride, p_fref2, m->i_stride ) +
75                    m->lm * ( bs_size_se( m->mvc[0] - m->mvp[0] ) + bs_size_se( m->mvc[1] - m->mvp[1] ) );
76         if( cost < bcost )
77         {
78             bmx = mx;
79             bmy = my;
80             bcost = cost;
81             p_fref = p_fref2;
82         }
83     }
84
85     /* Don't need to test mv_range each time, we won't go outside picture+padding */
86     /* diamond */
87     for( i_iter = 0; i_iter < 16; i_iter++ )
88     {
89         int best = 0;
90         int cost[4];
91
92 #define COST_MV( c, dx, dy ) \
93         (c) = h->pixf.sad[i_pixel]( m->p_fenc, m->i_stride,                    \
94                                &p_fref[(dy)*m->i_stride+(dx)], m->i_stride ) + \
95               m->lm * ( bs_size_se(((bmx+(dx))<<2) - m->mvp[0] ) +         \
96                         bs_size_se(((bmy+(dy))<<2) - m->mvp[1] ) )
97
98         COST_MV( cost[0],  0, -1 );
99         COST_MV( cost[1],  0,  1 );
100         COST_MV( cost[2], -1,  0 );
101         COST_MV( cost[3],  1,  0 );
102 #undef COST_MV
103
104         if( cost[1] < cost[0] )    best = 1;
105         if( cost[2] < cost[best] ) best = 2;
106         if( cost[3] < cost[best] ) best = 3;
107
108         if( bcost <= cost[best] )
109             break;
110
111         bcost = cost[best];
112
113         if( best == 0 ) {
114             bmy--;
115             p_fref -= m->i_stride;
116         } else if( best == 1 ) {
117             bmy++;
118             p_fref += m->i_stride;
119         } else if( best == 2 ) {
120             bmx--;
121             p_fref--;
122         } else if( best == 3 ) {
123             bmx++;
124             p_fref++;
125         }
126     }
127
128     /* -> qpel mv */
129     m->mv[0] = bmx << 2;
130     m->mv[1] = bmy << 2;
131
132     /* compute the real cost */
133     m->cost = h->pixf.satd[i_pixel]( m->p_fenc, m->i_stride, p_fref, m->i_stride ) +
134                 m->lm * ( bs_size_se( m->mv[0] - m->mvp[0] ) +
135                           bs_size_se( m->mv[1] - m->mvp[1] ) );
136
137     hpel = subpel_iterations[h->param.analyse.i_subpel_refine][2];
138     qpel = subpel_iterations[h->param.analyse.i_subpel_refine][3];
139     if( hpel || qpel )
140         refine_subpel( h, m, hpel, qpel );
141 }
142
143 void x264_me_refine_qpel( x264_t *h, x264_me_t *m )
144 {
145     int hpel = subpel_iterations[h->param.analyse.i_subpel_refine][0];
146     int qpel = subpel_iterations[h->param.analyse.i_subpel_refine][1];
147     if( hpel || qpel )
148         refine_subpel( h, m, hpel, qpel );
149 }
150
151 static void refine_subpel( x264_t *h, x264_me_t *m, int hpel_iters, int qpel_iters )
152 {
153     const int bw = x264_pixel_size[m->i_pixel].w;
154     const int bh = x264_pixel_size[m->i_pixel].h;
155
156     DECLARE_ALIGNED( uint8_t, pix[4][16*16], 16 );
157     int cost[4];
158     int best;
159     int step, i;
160
161     int bmx = m->mv[0];
162     int bmy = m->mv[1];
163
164     for( step = 2; step >= 1; step-- )
165     {
166         for( i = step>1 ? hpel_iters : qpel_iters; i > 0; i-- )
167         {
168             h->mc[MC_LUMA]( m->p_fref, m->i_stride, pix[0], 16, bmx + 0, bmy - step, bw, bh );
169             h->mc[MC_LUMA]( m->p_fref, m->i_stride, pix[1], 16, bmx + 0, bmy + step, bw, bh );
170             h->mc[MC_LUMA]( m->p_fref, m->i_stride, pix[2], 16, bmx - step, bmy + 0, bw, bh );
171             h->mc[MC_LUMA]( m->p_fref, m->i_stride, pix[3], 16, bmx + step, bmy + 0, bw, bh );
172     
173             cost[0] = h->pixf.satd[m->i_pixel]( m->p_fenc, m->i_stride, pix[0], 16 ) +
174                       m->lm * ( bs_size_se( bmx + 0 - m->mvp[0] ) + bs_size_se( bmy - step - m->mvp[1] ) );
175             cost[1] = h->pixf.satd[m->i_pixel]( m->p_fenc, m->i_stride, pix[1], 16 ) +
176                       m->lm * ( bs_size_se( bmx + 0 - m->mvp[0] ) + bs_size_se( bmy + step - m->mvp[1] ) );
177             cost[2] = h->pixf.satd[m->i_pixel]( m->p_fenc, m->i_stride, pix[2], 16 ) +
178                       m->lm * ( bs_size_se( bmx - step - m->mvp[0] ) + bs_size_se( bmy + 0 - m->mvp[1] ) );
179             cost[3] = h->pixf.satd[m->i_pixel]( m->p_fenc, m->i_stride, pix[3], 16 ) +
180                       m->lm * ( bs_size_se( bmx + step - m->mvp[0] ) + bs_size_se( bmy + 0 - m->mvp[1] ) );
181     
182             best = 0;
183             if( cost[1] < cost[0] )    best = 1;
184             if( cost[2] < cost[best] ) best = 2;
185             if( cost[3] < cost[best] ) best = 3;
186     
187             if( cost[best] < m->cost )
188             {
189                 m->cost = cost[best];
190                 if( best == 0 )      bmy -= step;
191                 else if( best == 1 ) bmy += step;
192                 else if( best == 2 ) bmx -= step;
193                 else if( best == 3 ) bmx += step;
194             }
195             else break;
196         }
197     }
198
199     m->mv[0] = bmx;
200     m->mv[1] = bmy;
201 }
202