git.sesse.net Git - x264/blob - 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 <stdio.h>
  26 #include <string.h>
  27
  28 #include "common/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 static const int subpel_iterations[][4] =
  36    {{1,0,0,0},
  37     {1,1,0,0},
  38     {0,1,1,0},
  39     {0,2,1,0},
  40     {0,2,1,1},
  41     {0,2,1,2},
  42     {0,0,2,2},
  43     {0,0,2,2}};
  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 BITS_MVD( mx, my )\
  48     (p_cost_mvx[(mx)<<2] + p_cost_mvy[(my)<<2])
  49
  50 #define COST_MV( mx, my )\
  51 {\
  52     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], FENC_STRIDE,\
  53                    &p_fref[(my)*m->i_stride[0]+(mx)], m->i_stride[0] )\
  54              + BITS_MVD(mx,my);\
  55     COPY3_IF_LT( bcost, cost, bmx, mx, bmy, my );\
  56 }
  57
  58 #define COST_MV_PRED( mx, my ) \
  59 { \
  60     int stride = 16; \
  61     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix, &stride, mx, my, bw, bh ); \
  62     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
  63              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
  64     COPY3_IF_LT( bpred_cost, cost, bpred_mx, mx, bpred_my, my ); \
  65 }
  66
  67 #define COST_MV_X3_DIR( m0x, m0y, m1x, m1y, m2x, m2y, costs )\
  68 {\
  69     uint8_t *pix_base = p_fref + bmx + bmy*m->i_stride[0];\
  70     h->pixf.sad_x3[i_pixel]( m->p_fenc[0],\
  71         pix_base + (m0x) + (m0y)*m->i_stride[0],\
  72         pix_base + (m1x) + (m1y)*m->i_stride[0],\
  73         pix_base + (m2x) + (m2y)*m->i_stride[0],\
  74         m->i_stride[0], costs );\
  75     (costs)[0] += BITS_MVD( bmx+(m0x), bmy+(m0y) );\
  76     (costs)[1] += BITS_MVD( bmx+(m1x), bmy+(m1y) );\
  77     (costs)[2] += BITS_MVD( bmx+(m2x), bmy+(m2y) );\
  78 }
  79
  80 #define COST_MV_X4( m0x, m0y, m1x, m1y, m2x, m2y, m3x, m3y )\
  81 {\
  82     uint8_t *pix_base = p_fref + omx + omy*m->i_stride[0];\
  83     h->pixf.sad_x4[i_pixel]( m->p_fenc[0],\
  84         pix_base + (m0x) + (m0y)*m->i_stride[0],\
  85         pix_base + (m1x) + (m1y)*m->i_stride[0],\
  86         pix_base + (m2x) + (m2y)*m->i_stride[0],\
  87         pix_base + (m3x) + (m3y)*m->i_stride[0],\
  88         m->i_stride[0], costs );\
  89     costs[0] += BITS_MVD( omx+(m0x), omy+(m0y) );\
  90     costs[1] += BITS_MVD( omx+(m1x), omy+(m1y) );\
  91     costs[2] += BITS_MVD( omx+(m2x), omy+(m2y) );\
  92     costs[3] += BITS_MVD( omx+(m3x), omy+(m3y) );\
  93     COPY3_IF_LT( bcost, costs[0], bmx, omx+(m0x), bmy, omy+(m0y) );\
  94     COPY3_IF_LT( bcost, costs[1], bmx, omx+(m1x), bmy, omy+(m1y) );\
  95     COPY3_IF_LT( bcost, costs[2], bmx, omx+(m2x), bmy, omy+(m2y) );\
  96     COPY3_IF_LT( bcost, costs[3], bmx, omx+(m3x), bmy, omy+(m3y) );\
  97 }
  98
  99 #define COST_MV_X4_ABS( m0x, m0y, m1x, m1y, m2x, m2y, m3x, m3y )\
 100 {\
 101     h->pixf.sad_x4[i_pixel]( m->p_fenc[0],\
 102         p_fref + (m0x) + (m0y)*m->i_stride[0],\
 103         p_fref + (m1x) + (m1y)*m->i_stride[0],\
 104         p_fref + (m2x) + (m2y)*m->i_stride[0],\
 105         p_fref + (m3x) + (m3y)*m->i_stride[0],\
 106         m->i_stride[0], costs );\
 107     costs[0] += p_cost_mvx[m0x<<2]; /* no cost_mvy */\
 108     costs[1] += p_cost_mvx[m1x<<2];\
 109     costs[2] += p_cost_mvx[m2x<<2];\
 110     costs[3] += p_cost_mvx[m3x<<2];\
 111     COPY3_IF_LT( bcost, costs[0], bmx, m0x, bmy, m0y );\
 112     COPY3_IF_LT( bcost, costs[1], bmx, m1x, bmy, m1y );\
 113     COPY3_IF_LT( bcost, costs[2], bmx, m2x, bmy, m2y );\
 114     COPY3_IF_LT( bcost, costs[3], bmx, m3x, bmy, m3y );\
 115 }
 116
 117 /*  1  */
 118 /* 101 */
 119 /*  1  */
 120 #define DIA1_ITER( mx, my )\
 121 {\
 122     omx = mx; omy = my;\
 123     COST_MV_X4( 0,-1, 0,1, -1,0, 1,0 );\
 124 }
 125
 126 #define CROSS( start, x_max, y_max )\
 127 {\
 128     i = start;\
 129     if( x_max <= X264_MIN(mv_x_max-omx, omx-mv_x_min) )\
 130         for( ; i < x_max-2; i+=4 )\
 131             COST_MV_X4( i,0, -i,0, i+2,0, -i-2,0 );\
 132     for( ; i < x_max; i+=2 )\
 133     {\
 134         if( omx+i <= mv_x_max )\
 135             COST_MV( omx+i, omy );\
 136         if( omx-i >= mv_x_min )\
 137             COST_MV( omx-i, omy );\
 138     }\
 139     i = start;\
 140     if( y_max <= X264_MIN(mv_y_max-omy, omy-mv_y_min) )\
 141         for( ; i < y_max-2; i+=4 )\
 142             COST_MV_X4( 0,i, 0,-i, 0,i+2, 0,-i-2 );\
 143     for( ; i < y_max; i+=2 )\
 144     {\
 145         if( omy+i <= mv_y_max )\
 146             COST_MV( omx, omy+i );\
 147         if( omy-i >= mv_y_min )\
 148             COST_MV( omx, omy-i );\
 149     }\
 150 }
 151
 152 void x264_me_search_ref( x264_t *h, x264_me_t *m, int (*mvc)[2], int i_mvc, int *p_halfpel_thresh )
 153 {
 154     const int bw = x264_pixel_size[m->i_pixel].w;
 155     const int bh = x264_pixel_size[m->i_pixel].h;
 156     const int i_pixel = m->i_pixel;
 157     int i_me_range = h->param.analyse.i_me_range;
 158     int bmx, bmy, bcost;
 159     int bpred_mx = 0, bpred_my = 0, bpred_cost = COST_MAX;
 160     int omx, omy, pmx, pmy;
 161     uint8_t *p_fref = m->p_fref[0];
 162     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
 163
 164     int i, j;
 165     int dir;
 166     int costs[6];
 167
 168     int mv_x_min = h->mb.mv_min_fpel[0];
 169     int mv_y_min = h->mb.mv_min_fpel[1];
 170     int mv_x_max = h->mb.mv_max_fpel[0];
 171     int mv_y_max = h->mb.mv_max_fpel[1];
 172
 173     const int16_t *p_cost_mvx = m->p_cost_mv - m->mvp[0];
 174     const int16_t *p_cost_mvy = m->p_cost_mv - m->mvp[1];
 175
 176     if( h->mb.i_me_method == X264_ME_UMH )
 177     {
 178         /* clamp mvp to inside frame+padding, so that we don't have to check it each iteration */
 179         p_cost_mvx = m->p_cost_mv - x264_clip3( m->mvp[0], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 180         p_cost_mvy = m->p_cost_mv - x264_clip3( m->mvp[1], h->mb.mv_min_spel[1], h->mb.mv_max_spel[1] );
 181     }
 182
 183     bmx = x264_clip3( m->mvp[0], mv_x_min*4, mv_x_max*4 );
 184     bmy = x264_clip3( m->mvp[1], mv_y_min*4, mv_y_max*4 );
 185     pmx = ( bmx + 2 ) >> 2;
 186     pmy = ( bmy + 2 ) >> 2;
 187     bcost = COST_MAX;
 188
 189     /* try extra predictors if provided */
 190     if( h->mb.i_subpel_refine >= 3 )
 191     {
 192         COST_MV_PRED( bmx, bmy );
 193         for( i = 0; i < i_mvc; i++ )
 194         {
 195              const int mx = x264_clip3( mvc[i][0], mv_x_min*4, mv_x_max*4 );
 196              const int my = x264_clip3( mvc[i][1], mv_y_min*4, mv_y_max*4 );
 197              if( mx != bpred_mx || my != bpred_my )
 198                  COST_MV_PRED( mx, my );
 199         }
 200         bmx = ( bpred_mx + 2 ) >> 2;
 201         bmy = ( bpred_my + 2 ) >> 2;
 202         COST_MV( bmx, bmy );
 203     }
 204     else
 205     {
 206         /* check the MVP */
 207         COST_MV( pmx, pmy );
 208         /* I don't know why this helps */
 209         bcost -= BITS_MVD(bmx,bmy);
 210
 211         for( i = 0; i < i_mvc; i++ )
 212         {
 213              const int mx = x264_clip3( ( mvc[i][0] + 2 ) >> 2, mv_x_min, mv_x_max );
 214              const int my = x264_clip3( ( mvc[i][1] + 2 ) >> 2, mv_y_min, mv_y_max );
 215              if( mx != bmx || my != bmy )
 216                  COST_MV( mx, my );
 217         }
 218     }
 219
 220     COST_MV( 0, 0 );
 221
 222     mv_x_max += 8;
 223     mv_y_max += 8;
 224     mv_x_min -= 8;
 225     mv_y_min -= 8;
 226
 227     switch( h->mb.i_me_method )
 228     {
 229     case X264_ME_DIA:
 230         /* diamond search, radius 1 */
 231         for( i = 0; i < i_me_range; i++ )
 232         {
 233             DIA1_ITER( bmx, bmy );
 234             if( bmx == omx && bmy == omy )
 235                 break;
 236         }
 237         break;
 238
 239     case X264_ME_HEX:
 240 me_hex2:
 241         /* hexagon search, radius 2 */
 242 #if 0
 243         for( i = 0; i < i_me_range/2; i++ )
 244         {
 245             omx = bmx; omy = bmy;
 246             COST_MV( omx-2, omy   );
 247             COST_MV( omx-1, omy+2 );
 248             COST_MV( omx+1, omy+2 );
 249             COST_MV( omx+2, omy   );
 250             COST_MV( omx+1, omy-2 );
 251             COST_MV( omx-1, omy-2 );
 252             if( bmx == omx && bmy == omy )
 253                 break;
 254         }
 255 #else
 256         /* equivalent to the above, but eliminates duplicate candidates */
 257         dir = -2;
 258
 259         /* hexagon */
 260         COST_MV_X3_DIR( -2,0, -1, 2,  1, 2, costs   );
 261         COST_MV_X3_DIR(  2,0,  1,-2, -1,-2, costs+3 );
 262         COPY2_IF_LT( bcost, costs[0], dir, 0 );
 263         COPY2_IF_LT( bcost, costs[1], dir, 1 );
 264         COPY2_IF_LT( bcost, costs[2], dir, 2 );
 265         COPY2_IF_LT( bcost, costs[3], dir, 3 );
 266         COPY2_IF_LT( bcost, costs[4], dir, 4 );
 267         COPY2_IF_LT( bcost, costs[5], dir, 5 );
 268
 269         if( dir != -2 )
 270         {
 271             static const int hex2[8][2] = {{-1,-2}, {-2,0}, {-1,2}, {1,2}, {2,0}, {1,-2}, {-1,-2}, {-2,0}};
 272             bmx += hex2[dir+1][0];
 273             bmy += hex2[dir+1][1];
 274             /* half hexagon, not overlapping the previous iteration */
 275             for( i = 1; i < i_me_range/2; i++ )
 276             {
 277                 static const int mod6[8] = {5,0,1,2,3,4,5,0};
 278                 const int odir = mod6[dir+1];
 279                 COST_MV_X3_DIR( hex2[odir+0][0], hex2[odir+0][1],
 280                                 hex2[odir+1][0], hex2[odir+1][1],
 281                                 hex2[odir+2][0], hex2[odir+2][1],
 282                                 costs );
 283                 dir = -2;
 284                 COPY2_IF_LT( bcost, costs[0], dir, odir-1 );
 285                 COPY2_IF_LT( bcost, costs[1], dir, odir   );
 286                 COPY2_IF_LT( bcost, costs[2], dir, odir+1 );
 287                 if( dir == -2 )
 288                     break;
 289                 bmx += hex2[dir+1][0];
 290                 bmy += hex2[dir+1][1];
 291             }
 292         }
 293 #endif
 294         /* square refine */
 295         omx = bmx; omy = bmy;
 296         COST_MV_X4(  0,-1,  0,1, -1,0, 1,0 );
 297         COST_MV_X4( -1,-1, -1,1, 1,-1, 1,1 );
 298         break;
 299
 300     case X264_ME_UMH:
 301         {
 302             /* Uneven-cross Multi-Hexagon-grid Search
 303              * as in JM, except with different early termination */
 304
 305             static const int x264_pixel_size_shift[7] = { 0, 1, 1, 2, 3, 3, 4 };
 306
 307             int ucost1, ucost2;
 308             int cross_start = 1;
 309
 310             /* refine predictors */
 311             ucost1 = bcost;
 312             DIA1_ITER( pmx, pmy );
 313             if( pmx || pmy )
 314                 DIA1_ITER( 0, 0 );
 315
 316             if(i_pixel == PIXEL_4x4)
 317                 goto me_hex2;
 318
 319             ucost2 = bcost;
 320             if( (bmx || bmy) && (bmx!=pmx || bmy!=pmy) )
 321                 DIA1_ITER( bmx, bmy );
 322             if( bcost == ucost2 )
 323                 cross_start = 3;
 324             omx = bmx; omy = bmy;
 325
 326             /* early termination */
 327 #define SAD_THRESH(v) ( bcost < ( v >> x264_pixel_size_shift[i_pixel] ) )
 328             if( bcost == ucost2 && SAD_THRESH(2000) )
 329             {
 330                 COST_MV_X4( 0,-2, -1,-1, 1,-1, -2,0 );
 331                 COST_MV_X4( 2, 0, -1, 1, 1, 1,  0,2 );
 332                 if( bcost == ucost1 && SAD_THRESH(500) )
 333                     break;
 334                 if( bcost == ucost2 )
 335                 {
 336                     int range = (i_me_range>>1) | 1;
 337                     CROSS( 3, range, range );
 338                     COST_MV_X4( -1,-2, 1,-2, -2,-1, 2,-1 );
 339                     COST_MV_X4( -2, 1, 2, 1, -1, 2, 1, 2 );
 340                     if( bcost == ucost2 )
 341                         break;
 342                     cross_start = range + 2;
 343                 }
 344             }
 345
 346             /* adaptive search range */
 347             if( i_mvc )
 348             {
 349                 /* range multipliers based on casual inspection of some statistics of
 350                  * average distance between current predictor and final mv found by ESA.
 351                  * these have not been tuned much by actual encoding. */
 352                 static const int range_mul[4][4] =
 353                 {
 354                     { 3, 3, 4, 4 },
 355                     { 3, 4, 4, 4 },
 356                     { 4, 4, 4, 5 },
 357                     { 4, 4, 5, 6 },
 358                 };
 359                 int mvd;
 360                 int sad_ctx, mvd_ctx;
 361
 362                 if( i_mvc == 1 )
 363                 {
 364                     if( i_pixel == PIXEL_16x16 )
 365                         /* mvc is probably the same as mvp, so the difference isn't meaningful.
 366                          * but prediction usually isn't too bad, so just use medium range */
 367                         mvd = 25;
 368                     else
 369                         mvd = abs( m->mvp[0] - mvc[0][0] )
 370                             + abs( m->mvp[1] - mvc[0][1] );
 371                 }
 372                 else
 373                 {
 374                     /* calculate the degree of agreement between predictors. */
 375                     /* in 16x16, mvc includes all the neighbors used to make mvp,
 376                      * so don't count mvp separately. */
 377                     int i_denom = i_mvc - 1;
 378                     mvd = 0;
 379                     if( i_pixel != PIXEL_16x16 )
 380                     {
 381                         mvd = abs( m->mvp[0] - mvc[0][0] )
 382                             + abs( m->mvp[1] - mvc[0][1] );
 383                         i_denom++;
 384                     }
 385                     for( i = 0; i < i_mvc-1; i++ )
 386                         mvd += abs( mvc[i][0] - mvc[i+1][0] )
 387                              + abs( mvc[i][1] - mvc[i+1][1] );
 388                     mvd /= i_denom; //FIXME idiv
 389                 }
 390
 391                 sad_ctx = SAD_THRESH(1000) ? 0
 392                         : SAD_THRESH(2000) ? 1
 393                         : SAD_THRESH(4000) ? 2 : 3;
 394                 mvd_ctx = mvd < 10 ? 0
 395                         : mvd < 20 ? 1
 396                         : mvd < 40 ? 2 : 3;
 397
 398                 i_me_range = i_me_range * range_mul[mvd_ctx][sad_ctx] / 4;
 399             }
 400
 401             /* FIXME if the above DIA2/OCT2/CROSS found a new mv, it has not updated omx/omy.
 402              * we are still centered on the same place as the DIA2. is this desirable? */
 403             CROSS( cross_start, i_me_range, i_me_range/2 );
 404
 405             /* 5x5 ESA */
 406             omx = bmx; omy = bmy;
 407             if( bcost != ucost2 )
 408                 COST_MV_X4(  1, 0,  0, 1, -1, 0,  0,-1 );
 409             COST_MV_X4(  1, 1, -1, 1, -1,-1,  1,-1 );
 410             COST_MV_X4(  2,-1,  2, 0,  2, 1,  2, 2 );
 411             COST_MV_X4(  1, 2,  0, 2, -1, 2, -2, 2 );
 412             COST_MV_X4( -2, 1, -2, 0, -2,-1, -2,-2 );
 413             COST_MV_X4( -1,-2,  0,-2,  1,-2,  2,-2 );
 414
 415             /* hexagon grid */
 416             omx = bmx; omy = bmy;
 417             for( i = 1; i <= i_me_range/4; i++ )
 418             {
 419                 static const int hex4[16][2] = {
 420                     {-4, 2}, {-4, 1}, {-4, 0}, {-4,-1}, {-4,-2},
 421                     { 4,-2}, { 4,-1}, { 4, 0}, { 4, 1}, { 4, 2},
 422                     { 2, 3}, { 0, 4}, {-2, 3},
 423                     {-2,-3}, { 0,-4}, { 2,-3},
 424                 };
 425
 426                 if( 4*i > X264_MIN4( mv_x_max-omx, omx-mv_x_min,
 427                                      mv_y_max-omy, omy-mv_y_min ) )
 428                 {
 429                     for( j = 0; j < 16; j++ )
 430                     {
 431                         int mx = omx + hex4[j][0]*i;
 432                         int my = omy + hex4[j][1]*i;
 433                         if(    mx >= mv_x_min && mx <= mv_x_max
 434                             && my >= mv_y_min && my <= mv_y_max )
 435                             COST_MV( mx, my );
 436                     }
 437                 }
 438                 else
 439                 {
 440                     COST_MV_X4( -4*i, 2*i, -4*i, 1*i, -4*i, 0*i, -4*i,-1*i );
 441                     COST_MV_X4( -4*i,-2*i,  4*i,-2*i,  4*i,-1*i,  4*i, 0*i );
 442                     COST_MV_X4(  4*i, 1*i,  4*i, 2*i,  2*i, 3*i,  0*i, 4*i );
 443                     COST_MV_X4( -2*i, 3*i, -2*i,-3*i,  0*i,-4*i,  2*i,-3*i );
 444                 }
 445             }
 446             goto me_hex2;
 447         }
 448
 449     case X264_ME_ESA:
 450         {
 451             const int min_x = X264_MAX( bmx - i_me_range, mv_x_min);
 452             const int min_y = X264_MAX( bmy - i_me_range, mv_y_min);
 453             const int max_x = X264_MIN( bmx + i_me_range, mv_x_max);
 454             const int max_y = X264_MIN( bmy + i_me_range, mv_y_max);
 455             int mx, my;
 456 #if 0
 457             /* plain old exhaustive search */
 458             for( my = min_y; my <= max_y; my++ )
 459                 for( mx = min_x; mx <= max_x; mx++ )
 460                     COST_MV( mx, my );
 461 #else
 462             /* successive elimination by comparing DC before a full SAD,
 463              * because sum(abs(diff)) >= abs(diff(sum)). */
 464             const int stride = m->i_stride[0];
 465             static uint8_t zero[16*16] = {0,};
 466             uint16_t *sums_base = m->integral;
 467             int enc_dc[4];
 468             int sad_size = i_pixel <= PIXEL_8x8 ? PIXEL_8x8 : PIXEL_4x4;
 469             int delta = x264_pixel_size[sad_size].w;
 470             uint16_t *ads = alloca((max_x-min_x+8) * sizeof(uint16_t));
 471
 472             h->pixf.sad_x4[sad_size]( zero, m->p_fenc[0], m->p_fenc[0]+delta,
 473                 m->p_fenc[0]+delta*FENC_STRIDE, m->p_fenc[0]+delta+delta*FENC_STRIDE,
 474                 FENC_STRIDE, enc_dc );
 475             if( delta == 4 )
 476                 sums_base += stride * (h->fenc->i_lines[0] + 64);
 477             if( i_pixel == PIXEL_16x16 || i_pixel == PIXEL_8x16 || i_pixel == PIXEL_4x8 )
 478                 delta *= stride;
 479             if( i_pixel == PIXEL_8x16 || i_pixel == PIXEL_4x8 )
 480                 enc_dc[1] = enc_dc[2];
 481
 482             for( my = min_y; my <= max_y; my++ )
 483             {
 484                 int mvs[3], i_mvs=0;
 485                 bcost -= p_cost_mvy[my<<2];
 486                 h->pixf.ads[i_pixel]( enc_dc, sums_base + min_x + my * stride, delta,
 487                                       ads, max_x-min_x+1 );
 488                 for( mx = min_x; mx <= max_x; mx++ )
 489                 {
 490                     if( ads[mx-min_x] < bcost - p_cost_mvx[mx<<2] )
 491                     {
 492                         if( i_mvs == 3 )
 493                         {
 494                             COST_MV_X4_ABS( mvs[0],my, mvs[1],my, mvs[2],my, mx,my );
 495                             i_mvs = 0;
 496                         }
 497                         else
 498                             mvs[i_mvs++] = mx;
 499                     }
 500                 }
 501                 bcost += p_cost_mvy[my<<2];
 502                 for( i=0; i<i_mvs; i++ )
 503                     COST_MV( mvs[i], my );
 504             }
 505 #endif
 506         }
 507         break;
 508     }
 509
 510     /* -> qpel mv */
 511     if( bpred_cost < bcost )
 512     {
 513         m->mv[0] = bpred_mx;
 514         m->mv[1] = bpred_my;
 515         m->cost = bpred_cost;
 516     }
 517     else
 518     {
 519         m->mv[0] = bmx << 2;
 520         m->mv[1] = bmy << 2;
 521         m->cost = bcost;
 522     }
 523
 524     /* compute the real cost */
 525     m->cost_mv = p_cost_mvx[ m->mv[0] ] + p_cost_mvy[ m->mv[1] ];
 526     if( bmx == pmx && bmy == pmy && h->mb.i_subpel_refine < 3 )
 527         m->cost += m->cost_mv;
 528
 529     /* subpel refine */
 530     if( h->mb.i_subpel_refine >= 2 )
 531     {
 532         int hpel = subpel_iterations[h->mb.i_subpel_refine][2];
 533         int qpel = subpel_iterations[h->mb.i_subpel_refine][3];
 534         refine_subpel( h, m, hpel, qpel, p_halfpel_thresh, 0 );
 535     }
 536 }
 537 #undef COST_MV
 538
 539 void x264_me_refine_qpel( x264_t *h, x264_me_t *m )
 540 {
 541     int hpel = subpel_iterations[h->mb.i_subpel_refine][0];
 542     int qpel = subpel_iterations[h->mb.i_subpel_refine][1];
 543
 544     if( m->i_pixel <= PIXEL_8x8 && h->sh.i_type == SLICE_TYPE_P )
 545         m->cost -= m->i_ref_cost;
 546
 547     refine_subpel( h, m, hpel, qpel, NULL, 1 );
 548 }
 549
 550 #define COST_MV_SAD( mx, my ) \
 551 { \
 552     int stride = 16; \
 553     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, mx, my, bw, bh ); \
 554     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 555              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
 556     COPY3_IF_LT( bcost, cost, bmx, mx, bmy, my ); \
 557 }
 558
 559 #define COST_MV_SATD( mx, my, dir ) \
 560 if( b_refine_qpel || (dir^1) != odir ) \
 561 { \
 562     int stride = 16; \
 563     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, mx, my, bw, bh ); \
 564     int cost = h->pixf.mbcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 565              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
 566     if( b_chroma_me && cost < bcost ) \
 567     { \
 568         h->mc.mc_chroma( m->p_fref[4], m->i_stride[1], pix[0], 8, mx, my, bw/2, bh/2 ); \
 569         cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[1], FENC_STRIDE, pix[0], 8 ); \
 570         if( cost < bcost ) \
 571         { \
 572             h->mc.mc_chroma( m->p_fref[5], m->i_stride[1], pix[0], 8, mx, my, bw/2, bh/2 ); \
 573             cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[2], FENC_STRIDE, pix[0], 8 ); \
 574         } \
 575     } \
 576     if( cost < bcost ) \
 577     {                  \
 578         bcost = cost;  \
 579         bmx = mx;      \
 580         bmy = my;      \
 581         bdir = dir;    \
 582     } \
 583 }
 584
 585 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 )
 586 {
 587     const int bw = x264_pixel_size[m->i_pixel].w;
 588     const int bh = x264_pixel_size[m->i_pixel].h;
 589     const int16_t *p_cost_mvx = m->p_cost_mv - m->mvp[0];
 590     const int16_t *p_cost_mvy = m->p_cost_mv - m->mvp[1];
 591     const int i_pixel = m->i_pixel;
 592     const int b_chroma_me = h->mb.b_chroma_me && i_pixel <= PIXEL_8x8;
 593
 594     DECLARE_ALIGNED( uint8_t, pix[4][16*16], 16 );
 595     int omx, omy;
 596     int i;
 597
 598     int bmx = m->mv[0];
 599     int bmy = m->mv[1];
 600     int bcost = m->cost;
 601     int odir = -1, bdir;
 602
 603
 604     /* try the subpel component of the predicted mv */
 605     if( hpel_iters && h->mb.i_subpel_refine < 3 )
 606     {
 607         int mx = x264_clip3( m->mvp[0], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 608         int my = x264_clip3( m->mvp[1], h->mb.mv_min_spel[1], h->mb.mv_max_spel[1] );
 609         if( mx != bmx || my != bmy )
 610             COST_MV_SAD( mx, my );
 611     }
 612
 613     /* halfpel diamond search */
 614     for( i = hpel_iters; i > 0; i-- )
 615     {
 616         int omx = bmx, omy = bmy;
 617         int costs[4];
 618         int stride = 16; // candidates are either all hpel or all qpel, so one stride is enough
 619         uint8_t *src0, *src1, *src2, *src3;
 620         src0 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, omx, omy-2, bw, bh );
 621         src2 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[2], &stride, omx-2, omy, bw, bh );
 622         if( (omx|omy)&1 )
 623         {
 624             src1 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[1], &stride, omx, omy+2, bw, bh );
 625             src3 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[3], &stride, omx+2, omy, bw, bh );
 626         }
 627         else
 628         {
 629             src1 = src0 + stride;
 630             src3 = src2 + 1;
 631         }
 632         h->pixf.sad_x4[i_pixel]( m->p_fenc[0], src0, src1, src2, src3, stride, costs );
 633         COPY2_IF_LT( bcost, costs[0] + p_cost_mvx[omx  ] + p_cost_mvy[omy-2], bmy, omy-2 );
 634         COPY2_IF_LT( bcost, costs[1] + p_cost_mvx[omx  ] + p_cost_mvy[omy+2], bmy, omy+2 );
 635         COPY3_IF_LT( bcost, costs[2] + p_cost_mvx[omx-2] + p_cost_mvy[omy  ], bmx, omx-2, bmy, omy );
 636         COPY3_IF_LT( bcost, costs[3] + p_cost_mvx[omx+2] + p_cost_mvy[omy  ], bmx, omx+2, bmy, omy );
 637         if( bmx == omx && bmy == omy )
 638             break;
 639     }
 640
 641     if( !b_refine_qpel )
 642     {
 643         bcost = COST_MAX;
 644         COST_MV_SATD( bmx, bmy, -1 );
 645     }
 646
 647     /* early termination when examining multiple reference frames */
 648     if( p_halfpel_thresh )
 649     {
 650         if( (bcost*7)>>3 > *p_halfpel_thresh )
 651         {
 652             m->cost = bcost;
 653             m->mv[0] = bmx;
 654             m->mv[1] = bmy;
 655             // don't need cost_mv
 656             return;
 657         }
 658         else if( bcost < *p_halfpel_thresh )
 659             *p_halfpel_thresh = bcost;
 660     }
 661
 662     /* quarterpel diamond search */
 663     bdir = -1;
 664     for( i = qpel_iters; i > 0; i-- )
 665     {
 666         odir = bdir;
 667         omx = bmx;
 668         omy = bmy;
 669         COST_MV_SATD( omx, omy - 1, 0 );
 670         COST_MV_SATD( omx, omy + 1, 1 );
 671         COST_MV_SATD( omx - 1, omy, 2 );
 672         COST_MV_SATD( omx + 1, omy, 3 );
 673         if( bmx == omx && bmy == omy )
 674             break;
 675     }
 676
 677     m->cost = bcost;
 678     m->mv[0] = bmx;
 679     m->mv[1] = bmy;
 680     m->cost_mv = p_cost_mvx[ bmx ] + p_cost_mvy[ bmy ];
 681 }
 682
 683 #define BIME_CACHE( dx, dy ) \
 684 { \
 685     int i = 4 + 3*dx + dy; \
 686     h->mc.mc_luma( m0->p_fref, m0->i_stride[0], pix0[i], bw, om0x+dx, om0y+dy, bw, bh ); \
 687     h->mc.mc_luma( m1->p_fref, m1->i_stride[0], pix1[i], bw, om1x+dx, om1y+dy, bw, bh ); \
 688 }
 689
 690 #define BIME_CACHE2(a,b) \
 691     BIME_CACHE(a,b) \
 692     BIME_CACHE(-(a),-(b))
 693
 694 #define COST_BIMV_SATD( m0x, m0y, m1x, m1y ) \
 695 if( pass == 0 || !visited[(m0x)&7][(m0y)&7][(m1x)&7][(m1y)&7] ) \
 696 { \
 697     int cost; \
 698     int i0 = 4 + 3*(m0x-om0x) + (m0y-om0y); \
 699     int i1 = 4 + 3*(m1x-om1x) + (m1y-om1y); \
 700     visited[(m0x)&7][(m0y)&7][(m1x)&7][(m1y)&7] = 1; \
 701     memcpy( pix, pix0[i0], bs ); \
 702     if( i_weight == 32 ) \
 703         h->mc.avg[i_pixel]( pix, bw, pix1[i1], bw ); \
 704     else \
 705         h->mc.avg_weight[i_pixel]( pix, bw, pix1[i1], bw, i_weight ); \
 706     cost = h->pixf.mbcmp[i_pixel]( m0->p_fenc[0], FENC_STRIDE, pix, bw ) \
 707          + p_cost_m0x[ m0x ] + p_cost_m0y[ m0y ] \
 708          + p_cost_m1x[ m1x ] + p_cost_m1y[ m1y ]; \
 709     if( cost < bcost ) \
 710     {                  \
 711         bcost = cost;  \
 712         bm0x = m0x;    \
 713         bm0y = m0y;    \
 714         bm1x = m1x;    \
 715         bm1y = m1y;    \
 716     } \
 717 }
 718
 719 #define CHECK_BIDIR(a,b,c,d) \
 720     COST_BIMV_SATD(om0x+a, om0y+b, om1x+c, om1y+d)
 721
 722 #define CHECK_BIDIR2(a,b,c,d) \
 723     CHECK_BIDIR(a,b,c,d) \
 724     CHECK_BIDIR(-(a),-(b),-(c),-(d))
 725
 726 #define CHECK_BIDIR8(a,b,c,d) \
 727     CHECK_BIDIR2(a,b,c,d) \
 728     CHECK_BIDIR2(b,c,d,a) \
 729     CHECK_BIDIR2(c,d,a,b) \
 730     CHECK_BIDIR2(d,a,b,c)
 731
 732 int x264_me_refine_bidir( x264_t *h, x264_me_t *m0, x264_me_t *m1, int i_weight )
 733 {
 734     const int i_pixel = m0->i_pixel;
 735     const int bw = x264_pixel_size[i_pixel].w;
 736     const int bh = x264_pixel_size[i_pixel].h;
 737     const int bs = bw*bh;
 738     const int16_t *p_cost_m0x = m0->p_cost_mv - x264_clip3( m0->mvp[0], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 739     const int16_t *p_cost_m0y = m0->p_cost_mv - x264_clip3( m0->mvp[1], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 740     const int16_t *p_cost_m1x = m1->p_cost_mv - x264_clip3( m1->mvp[0], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 741     const int16_t *p_cost_m1y = m1->p_cost_mv - x264_clip3( m1->mvp[1], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 742     DECLARE_ALIGNED( uint8_t, pix0[9][16*16], 16 );
 743     DECLARE_ALIGNED( uint8_t, pix1[9][16*16], 16 );
 744     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
 745     int bm0x = m0->mv[0], om0x = bm0x;
 746     int bm0y = m0->mv[1], om0y = bm0y;
 747     int bm1x = m1->mv[0], om1x = bm1x;
 748     int bm1y = m1->mv[1], om1y = bm1y;
 749     int bcost = COST_MAX;
 750     int pass = 0;
 751     uint8_t visited[8][8][8][8];
 752     memset( visited, 0, sizeof(visited) );
 753
 754     BIME_CACHE( 0, 0 );
 755     CHECK_BIDIR( 0, 0, 0, 0 );
 756
 757     for( pass = 0; pass < 8; pass++ )
 758     {
 759         /* check all mv pairs that differ in at most 2 components from the current mvs. */
 760         /* doesn't do chroma ME. this probably doesn't matter, as the gains
 761          * from bidir ME are the same with and without chroma ME. */
 762
 763         BIME_CACHE2( 1, 0 );
 764         BIME_CACHE2( 0, 1 );
 765         BIME_CACHE2( 1, 1 );
 766         BIME_CACHE2( 1,-1 );
 767
 768         CHECK_BIDIR8( 0, 0, 0, 1 );
 769         CHECK_BIDIR8( 0, 0, 1, 1 );
 770         CHECK_BIDIR2( 0, 1, 0, 1 );
 771         CHECK_BIDIR2( 1, 0, 1, 0 );
 772         CHECK_BIDIR8( 0, 0,-1, 1 );
 773         CHECK_BIDIR2( 0,-1, 0, 1 );
 774         CHECK_BIDIR2(-1, 0, 1, 0 );
 775
 776         if( om0x == bm0x && om0y == bm0y && om1x == bm1x && om1y == bm1y )
 777             break;
 778
 779         om0x = bm0x;
 780         om0y = bm0y;
 781         om1x = bm1x;
 782         om1y = bm1y;
 783         BIME_CACHE( 0, 0 );
 784     }
 785
 786     m0->mv[0] = bm0x;
 787     m0->mv[1] = bm0y;
 788     m1->mv[0] = bm1x;
 789     m1->mv[1] = bm1y;
 790     return bcost;
 791 }
 792
 793 #undef COST_MV_SATD
 794 #define COST_MV_SATD( mx, my, dst ) \
 795 { \
 796     int stride = 16; \
 797     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix, &stride, mx, my, bw*4, bh*4 ); \
 798     dst = h->pixf.mbcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 799         + p_cost_mvx[mx] + p_cost_mvy[my]; \
 800     COPY1_IF_LT( bsatd, dst ); \
 801 }
 802
 803 #define COST_MV_RD( mx, my, satd, dir ) \
 804 { \
 805     if( satd <= bsatd * SATD_THRESH \
 806         && (dir^1) != odir \
 807         && (dir<0 || !p_visited[(mx)+(my)*16]) ) \
 808     { \
 809         int cost; \
 810         cache_mv[0] = cache_mv2[0] = mx; \
 811         cache_mv[1] = cache_mv2[1] = my; \
 812         cost = x264_rd_cost_part( h, i_lambda2, i8, m->i_pixel ); \
 813         COPY3_IF_LT( bcost, cost, bmx, mx, bmy, my ); \
 814         if(dir>=0) p_visited[(mx)+(my)*16] = 1; \
 815     } \
 816 }
 817
 818 #define SATD_THRESH 17/16
 819
 820 void x264_me_refine_qpel_rd( x264_t *h, x264_me_t *m, int i_lambda2, int i8 )
 821 {
 822     // don't have to fill the whole mv cache rectangle
 823     static const int pixel_mv_offs[] = { 0, 4, 4*8, 0 };
 824     int16_t *cache_mv = h->mb.cache.mv[0][x264_scan8[i8*4]];
 825     int16_t *cache_mv2 = cache_mv + pixel_mv_offs[m->i_pixel];
 826     const int16_t *p_cost_mvx, *p_cost_mvy;
 827     const int bw = x264_pixel_size[m->i_pixel].w>>2;
 828     const int bh = x264_pixel_size[m->i_pixel].h>>2;
 829     const int i_pixel = m->i_pixel;
 830
 831     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
 832     int bcost = m->i_pixel == PIXEL_16x16 ? m->cost : COST_MAX;
 833     int bmx = m->mv[0];
 834     int bmy = m->mv[1];
 835     int pmx, pmy, omx, omy, i;
 836     int odir = -1, bdir;
 837     unsigned bsatd, satds[4];
 838
 839     int visited[16*13] = {0}; // only need 13x13, but 16 is more convenient
 840     int *p_visited = &visited[6+6*16];
 841
 842     if( m->i_pixel != PIXEL_16x16 && i8 != 0 )
 843         x264_mb_predict_mv( h, 0, i8*4, bw, m->mvp );
 844     pmx = m->mvp[0];
 845     pmy = m->mvp[1];
 846     p_cost_mvx = m->p_cost_mv - pmx;
 847     p_cost_mvy = m->p_cost_mv - pmy;
 848     COST_MV_SATD( bmx, bmy, bsatd );
 849     if( m->i_pixel != PIXEL_16x16 )
 850         COST_MV_RD( bmx, bmy, 0, -1 );
 851
 852     /* check the predicted mv */
 853     if( (bmx != pmx || bmy != pmy)
 854         && pmx >= h->mb.mv_min_spel[0] && pmx <= h->mb.mv_max_spel[0]
 855         && pmy >= h->mb.mv_min_spel[1] && pmy <= h->mb.mv_max_spel[1] )
 856     {
 857         int satd;
 858         COST_MV_SATD( pmx, pmy, satd );
 859         COST_MV_RD( pmx, pmy, satd, -1 );
 860     }
 861
 862     /* mark mv and mvp as visited */
 863     p_visited[0] = 1;
 864     p_visited -= bmx + bmy*16;
 865     {
 866         int mx = bmx ^ m->mv[0] ^ pmx;
 867         int my = bmy ^ m->mv[1] ^ pmy;
 868         if( abs(mx-bmx) < 7 && abs(my-bmy) < 7 )
 869             p_visited[mx + my*16] = 1;
 870     }
 871
 872     /* hpel diamond */
 873     bdir = -1;
 874     for( i = 0; i < 2; i++ )
 875     {
 876          omx = bmx;
 877          omy = bmy;
 878          odir = bdir;
 879          COST_MV_SATD( omx, omy - 2, satds[0] );
 880          COST_MV_SATD( omx, omy + 2, satds[1] );
 881          COST_MV_SATD( omx - 2, omy, satds[2] );
 882          COST_MV_SATD( omx + 2, omy, satds[3] );
 883          COST_MV_RD( omx, omy - 2, satds[0], 0 );
 884          COST_MV_RD( omx, omy + 2, satds[1], 1 );
 885          COST_MV_RD( omx - 2, omy, satds[2], 2 );
 886          COST_MV_RD( omx + 2, omy, satds[3], 3 );
 887          if( bmx == omx && bmy == omy )
 888             break;
 889     }
 890
 891     /* qpel diamond */
 892     bdir = -1;
 893     for( i = 0; i < 2; i++ )
 894     {
 895          omx = bmx;
 896          omy = bmy;
 897          odir = bdir;
 898          COST_MV_SATD( omx, omy - 1, satds[0] );
 899          COST_MV_SATD( omx, omy + 1, satds[1] );
 900          COST_MV_SATD( omx - 1, omy, satds[2] );
 901          COST_MV_SATD( omx + 1, omy, satds[3] );
 902          COST_MV_RD( omx, omy - 1, satds[0], 0 );
 903          COST_MV_RD( omx, omy + 1, satds[1], 1 );
 904          COST_MV_RD( omx - 1, omy, satds[2], 2 );
 905          COST_MV_RD( omx + 1, omy, satds[3], 3 );
 906          if( bmx == omx && bmy == omy )
 907             break;
 908     }
 909
 910     m->cost = bcost;
 911     m->mv[0] = bmx;
 912     m->mv[1] = bmy;
 913
 914     x264_macroblock_cache_mv ( h, 2*(i8&1), i8&2, bw, bh, 0, bmx, bmy );
 915     x264_macroblock_cache_mvd( h, 2*(i8&1), i8&2, bw, bh, 0, bmx - pmx, bmy - pmy );
 916 }
 917