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             const uint16_t *integral_base = m->integral;
 466             static uint8_t zero[16*16] = {0,};
 467             int enc_dc[4];
 468             int sad_size = i_pixel <= PIXEL_8x8 ? PIXEL_8x8 : PIXEL_4x4;
 469             int sad_w = x264_pixel_size[sad_size].w;
 470             h->pixf.sad_x4[sad_size]( zero, m->p_fenc[0], m->p_fenc[0]+sad_w,
 471                 m->p_fenc[0]+sad_w*FENC_STRIDE, m->p_fenc[0]+sad_w+sad_w*FENC_STRIDE,
 472                 FENC_STRIDE, enc_dc );
 473             if( sad_w == 4 )
 474                 integral_base += stride * (h->fenc->i_lines[0] + 64);
 475
 476 #define ESA(ADS) \
 477             for( my = min_y; my <= max_y; my++ )\
 478             {\
 479                 int mvs[3], i_mvs=0;\
 480                 bcost -= p_cost_mvy[my<<2];\
 481                 for( mx = min_x; mx <= max_x; mx++ )\
 482                 {\
 483                     const uint16_t *integral = &integral_base[ mx + my * stride ];\
 484                     if( ADS < bcost - p_cost_mvx[mx<<2] )\
 485                     {\
 486                         if( i_mvs == 3 )\
 487                         {\
 488                             COST_MV_X4_ABS( mvs[0],my, mvs[1],my, mvs[2],my, mx,my );\
 489                             i_mvs = 0;\
 490                         }\
 491                         else\
 492                             mvs[i_mvs++] = mx;\
 493                     }\
 494                 }\
 495                 bcost += p_cost_mvy[my<<2];\
 496                 for( i=0; i<i_mvs; i++ )\
 497                     COST_MV( mvs[i], my );\
 498             }
 499
 500             if( i_pixel == PIXEL_16x16 )
 501             {
 502                 ESA( abs( enc_dc[0] - integral[0] )
 503                    + abs( enc_dc[1] - integral[8] )
 504                    + abs( enc_dc[2] - integral[8*stride] )
 505                    + abs( enc_dc[3] - integral[8*stride+8] ) );
 506             }
 507             else if( i_pixel == PIXEL_8x8 || i_pixel == PIXEL_4x4 )
 508             {
 509                 ESA( abs( enc_dc[0] - integral[0] ) );
 510             }
 511             else
 512             {
 513                 int dw = i_pixel < PIXEL_8x8 ? 8 : 4;
 514                 if( i_pixel == PIXEL_8x16 || i_pixel == PIXEL_4x8 )
 515                 {
 516                     dw *= stride;
 517                     enc_dc[1] = enc_dc[2];
 518                 }
 519                 ESA( abs( enc_dc[0] - integral[0] )
 520                    + abs( enc_dc[1] - integral[dw] ) );
 521             }
 522 #undef ESA
 523 #endif
 524         }
 525         break;
 526     }
 527
 528     /* -> qpel mv */
 529     if( bpred_cost < bcost )
 530     {
 531         m->mv[0] = bpred_mx;
 532         m->mv[1] = bpred_my;
 533         m->cost = bpred_cost;
 534     }
 535     else
 536     {
 537         m->mv[0] = bmx << 2;
 538         m->mv[1] = bmy << 2;
 539         m->cost = bcost;
 540     }
 541
 542     /* compute the real cost */
 543     m->cost_mv = p_cost_mvx[ m->mv[0] ] + p_cost_mvy[ m->mv[1] ];
 544     if( bmx == pmx && bmy == pmy && h->mb.i_subpel_refine < 3 )
 545         m->cost += m->cost_mv;
 546
 547     /* subpel refine */
 548     if( h->mb.i_subpel_refine >= 2 )
 549     {
 550         int hpel = subpel_iterations[h->mb.i_subpel_refine][2];
 551         int qpel = subpel_iterations[h->mb.i_subpel_refine][3];
 552         refine_subpel( h, m, hpel, qpel, p_halfpel_thresh, 0 );
 553     }
 554 }
 555 #undef COST_MV
 556
 557 void x264_me_refine_qpel( x264_t *h, x264_me_t *m )
 558 {
 559     int hpel = subpel_iterations[h->mb.i_subpel_refine][0];
 560     int qpel = subpel_iterations[h->mb.i_subpel_refine][1];
 561
 562     if( m->i_pixel <= PIXEL_8x8 && h->sh.i_type == SLICE_TYPE_P )
 563         m->cost -= m->i_ref_cost;
 564
 565     refine_subpel( h, m, hpel, qpel, NULL, 1 );
 566 }
 567
 568 #define COST_MV_SAD( mx, my ) \
 569 { \
 570     int stride = 16; \
 571     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, mx, my, bw, bh ); \
 572     int cost = h->pixf.sad[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 573              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
 574     COPY3_IF_LT( bcost, cost, bmx, mx, bmy, my ); \
 575 }
 576
 577 #define COST_MV_SATD( mx, my, dir ) \
 578 if( b_refine_qpel || (dir^1) != odir ) \
 579 { \
 580     int stride = 16; \
 581     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, mx, my, bw, bh ); \
 582     int cost = h->pixf.mbcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 583              + p_cost_mvx[ mx ] + p_cost_mvy[ my ]; \
 584     if( b_chroma_me && cost < bcost ) \
 585     { \
 586         h->mc.mc_chroma( m->p_fref[4], m->i_stride[1], pix[0], 8, mx, my, bw/2, bh/2 ); \
 587         cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[1], FENC_STRIDE, pix[0], 8 ); \
 588         if( cost < bcost ) \
 589         { \
 590             h->mc.mc_chroma( m->p_fref[5], m->i_stride[1], pix[0], 8, mx, my, bw/2, bh/2 ); \
 591             cost += h->pixf.mbcmp[i_pixel+3]( m->p_fenc[2], FENC_STRIDE, pix[0], 8 ); \
 592         } \
 593     } \
 594     if( cost < bcost ) \
 595     {                  \
 596         bcost = cost;  \
 597         bmx = mx;      \
 598         bmy = my;      \
 599         bdir = dir;    \
 600     } \
 601 }
 602
 603 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 )
 604 {
 605     const int bw = x264_pixel_size[m->i_pixel].w;
 606     const int bh = x264_pixel_size[m->i_pixel].h;
 607     const int16_t *p_cost_mvx = m->p_cost_mv - m->mvp[0];
 608     const int16_t *p_cost_mvy = m->p_cost_mv - m->mvp[1];
 609     const int i_pixel = m->i_pixel;
 610     const int b_chroma_me = h->mb.b_chroma_me && i_pixel <= PIXEL_8x8;
 611
 612     DECLARE_ALIGNED( uint8_t, pix[4][16*16], 16 );
 613     int omx, omy;
 614     int i;
 615
 616     int bmx = m->mv[0];
 617     int bmy = m->mv[1];
 618     int bcost = m->cost;
 619     int odir = -1, bdir;
 620
 621
 622     /* try the subpel component of the predicted mv */
 623     if( hpel_iters && h->mb.i_subpel_refine < 3 )
 624     {
 625         int mx = x264_clip3( m->mvp[0], h->mb.mv_min_spel[0], h->mb.mv_max_spel[0] );
 626         int my = x264_clip3( m->mvp[1], h->mb.mv_min_spel[1], h->mb.mv_max_spel[1] );
 627         if( mx != bmx || my != bmy )
 628             COST_MV_SAD( mx, my );
 629     }
 630
 631     /* halfpel diamond search */
 632     for( i = hpel_iters; i > 0; i-- )
 633     {
 634         int omx = bmx, omy = bmy;
 635         int costs[4];
 636         int stride = 16; // candidates are either all hpel or all qpel, so one stride is enough
 637         uint8_t *src0, *src1, *src2, *src3;
 638         src0 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[0], &stride, omx, omy-2, bw, bh );
 639         src2 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[2], &stride, omx-2, omy, bw, bh );
 640         if( (omx|omy)&1 )
 641         {
 642             src1 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[1], &stride, omx, omy+2, bw, bh );
 643             src3 = h->mc.get_ref( m->p_fref, m->i_stride[0], pix[3], &stride, omx+2, omy, bw, bh );
 644         }
 645         else
 646         {
 647             src1 = src0 + stride;
 648             src3 = src2 + 1;
 649         }
 650         h->pixf.sad_x4[i_pixel]( m->p_fenc[0], src0, src1, src2, src3, stride, costs );
 651         COPY2_IF_LT( bcost, costs[0] + p_cost_mvx[omx  ] + p_cost_mvy[omy-2], bmy, omy-2 );
 652         COPY2_IF_LT( bcost, costs[1] + p_cost_mvx[omx  ] + p_cost_mvy[omy+2], bmy, omy+2 );
 653         COPY3_IF_LT( bcost, costs[2] + p_cost_mvx[omx-2] + p_cost_mvy[omy  ], bmx, omx-2, bmy, omy );
 654         COPY3_IF_LT( bcost, costs[3] + p_cost_mvx[omx+2] + p_cost_mvy[omy  ], bmx, omx+2, bmy, omy );
 655         if( bmx == omx && bmy == omy )
 656             break;
 657     }
 658
 659     if( !b_refine_qpel )
 660     {
 661         bcost = COST_MAX;
 662         COST_MV_SATD( bmx, bmy, -1 );
 663     }
 664
 665     /* early termination when examining multiple reference frames */
 666     if( p_halfpel_thresh )
 667     {
 668         if( (bcost*7)>>3 > *p_halfpel_thresh )
 669         {
 670             m->cost = bcost;
 671             m->mv[0] = bmx;
 672             m->mv[1] = bmy;
 673             // don't need cost_mv
 674             return;
 675         }
 676         else if( bcost < *p_halfpel_thresh )
 677             *p_halfpel_thresh = bcost;
 678     }
 679
 680     /* quarterpel diamond search */
 681     bdir = -1;
 682     for( i = qpel_iters; i > 0; i-- )
 683     {
 684         odir = bdir;
 685         omx = bmx;
 686         omy = bmy;
 687         COST_MV_SATD( omx, omy - 1, 0 );
 688         COST_MV_SATD( omx, omy + 1, 1 );
 689         COST_MV_SATD( omx - 1, omy, 2 );
 690         COST_MV_SATD( omx + 1, omy, 3 );
 691         if( bmx == omx && bmy == omy )
 692             break;
 693     }
 694
 695     m->cost = bcost;
 696     m->mv[0] = bmx;
 697     m->mv[1] = bmy;
 698     m->cost_mv = p_cost_mvx[ bmx ] + p_cost_mvy[ bmy ];
 699 }
 700
 701 #define BIME_CACHE( dx, dy ) \
 702 { \
 703     int i = 4 + 3*dx + dy; \
 704     h->mc.mc_luma( m0->p_fref, m0->i_stride[0], pix0[i], bw, om0x+dx, om0y+dy, bw, bh ); \
 705     h->mc.mc_luma( m1->p_fref, m1->i_stride[0], pix1[i], bw, om1x+dx, om1y+dy, bw, bh ); \
 706 }
 707
 708 #define BIME_CACHE2(a,b) \
 709     BIME_CACHE(a,b) \
 710     BIME_CACHE(-(a),-(b))
 711
 712 #define COST_BIMV_SATD( m0x, m0y, m1x, m1y ) \
 713 if( pass == 0 || !visited[(m0x)&7][(m0y)&7][(m1x)&7][(m1y)&7] ) \
 714 { \
 715     int cost; \
 716     int i0 = 4 + 3*(m0x-om0x) + (m0y-om0y); \
 717     int i1 = 4 + 3*(m1x-om1x) + (m1y-om1y); \
 718     visited[(m0x)&7][(m0y)&7][(m1x)&7][(m1y)&7] = 1; \
 719     memcpy( pix, pix0[i0], bs ); \
 720     if( i_weight == 32 ) \
 721         h->mc.avg[i_pixel]( pix, bw, pix1[i1], bw ); \
 722     else \
 723         h->mc.avg_weight[i_pixel]( pix, bw, pix1[i1], bw, i_weight ); \
 724     cost = h->pixf.mbcmp[i_pixel]( m0->p_fenc[0], FENC_STRIDE, pix, bw ) \
 725          + p_cost_m0x[ m0x ] + p_cost_m0y[ m0y ] \
 726          + p_cost_m1x[ m1x ] + p_cost_m1y[ m1y ]; \
 727     if( cost < bcost ) \
 728     {                  \
 729         bcost = cost;  \
 730         bm0x = m0x;    \
 731         bm0y = m0y;    \
 732         bm1x = m1x;    \
 733         bm1y = m1y;    \
 734     } \
 735 }
 736
 737 #define CHECK_BIDIR(a,b,c,d) \
 738     COST_BIMV_SATD(om0x+a, om0y+b, om1x+c, om1y+d)
 739
 740 #define CHECK_BIDIR2(a,b,c,d) \
 741     CHECK_BIDIR(a,b,c,d) \
 742     CHECK_BIDIR(-(a),-(b),-(c),-(d))
 743
 744 #define CHECK_BIDIR8(a,b,c,d) \
 745     CHECK_BIDIR2(a,b,c,d) \
 746     CHECK_BIDIR2(b,c,d,a) \
 747     CHECK_BIDIR2(c,d,a,b) \
 748     CHECK_BIDIR2(d,a,b,c)
 749
 750 int x264_me_refine_bidir( x264_t *h, x264_me_t *m0, x264_me_t *m1, int i_weight )
 751 {
 752     const int i_pixel = m0->i_pixel;
 753     const int bw = x264_pixel_size[i_pixel].w;
 754     const int bh = x264_pixel_size[i_pixel].h;
 755     const int bs = bw*bh;
 756     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] );
 757     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] );
 758     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] );
 759     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] );
 760     DECLARE_ALIGNED( uint8_t, pix0[9][16*16], 16 );
 761     DECLARE_ALIGNED( uint8_t, pix1[9][16*16], 16 );
 762     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
 763     int bm0x = m0->mv[0], om0x = bm0x;
 764     int bm0y = m0->mv[1], om0y = bm0y;
 765     int bm1x = m1->mv[0], om1x = bm1x;
 766     int bm1y = m1->mv[1], om1y = bm1y;
 767     int bcost = COST_MAX;
 768     int pass = 0;
 769     uint8_t visited[8][8][8][8];
 770     memset( visited, 0, sizeof(visited) );
 771
 772     BIME_CACHE( 0, 0 );
 773     CHECK_BIDIR( 0, 0, 0, 0 );
 774
 775     for( pass = 0; pass < 8; pass++ )
 776     {
 777         /* check all mv pairs that differ in at most 2 components from the current mvs. */
 778         /* doesn't do chroma ME. this probably doesn't matter, as the gains
 779          * from bidir ME are the same with and without chroma ME. */
 780
 781         BIME_CACHE2( 1, 0 );
 782         BIME_CACHE2( 0, 1 );
 783         BIME_CACHE2( 1, 1 );
 784         BIME_CACHE2( 1,-1 );
 785
 786         CHECK_BIDIR8( 0, 0, 0, 1 );
 787         CHECK_BIDIR8( 0, 0, 1, 1 );
 788         CHECK_BIDIR2( 0, 1, 0, 1 );
 789         CHECK_BIDIR2( 1, 0, 1, 0 );
 790         CHECK_BIDIR8( 0, 0,-1, 1 );
 791         CHECK_BIDIR2( 0,-1, 0, 1 );
 792         CHECK_BIDIR2(-1, 0, 1, 0 );
 793
 794         if( om0x == bm0x && om0y == bm0y && om1x == bm1x && om1y == bm1y )
 795             break;
 796
 797         om0x = bm0x;
 798         om0y = bm0y;
 799         om1x = bm1x;
 800         om1y = bm1y;
 801         BIME_CACHE( 0, 0 );
 802     }
 803
 804     m0->mv[0] = bm0x;
 805     m0->mv[1] = bm0y;
 806     m1->mv[0] = bm1x;
 807     m1->mv[1] = bm1y;
 808     return bcost;
 809 }
 810
 811 #undef COST_MV_SATD
 812 #define COST_MV_SATD( mx, my, dst ) \
 813 { \
 814     int stride = 16; \
 815     uint8_t *src = h->mc.get_ref( m->p_fref, m->i_stride[0], pix, &stride, mx, my, bw*4, bh*4 ); \
 816     dst = h->pixf.mbcmp[i_pixel]( m->p_fenc[0], FENC_STRIDE, src, stride ) \
 817         + p_cost_mvx[mx] + p_cost_mvy[my]; \
 818     COPY1_IF_LT( bsatd, dst ); \
 819 }
 820
 821 #define COST_MV_RD( mx, my, satd, dir ) \
 822 { \
 823     if( satd <= bsatd * SATD_THRESH \
 824         && (dir^1) != odir \
 825         && (dir<0 || !p_visited[(mx)+(my)*16]) ) \
 826     { \
 827         int cost; \
 828         cache_mv[0] = cache_mv2[0] = mx; \
 829         cache_mv[1] = cache_mv2[1] = my; \
 830         cost = x264_rd_cost_part( h, i_lambda2, i8, m->i_pixel ); \
 831         COPY3_IF_LT( bcost, cost, bmx, mx, bmy, my ); \
 832         if(dir>=0) p_visited[(mx)+(my)*16] = 1; \
 833     } \
 834 }
 835
 836 #define SATD_THRESH 17/16
 837
 838 void x264_me_refine_qpel_rd( x264_t *h, x264_me_t *m, int i_lambda2, int i8 )
 839 {
 840     // don't have to fill the whole mv cache rectangle
 841     static const int pixel_mv_offs[] = { 0, 4, 4*8, 0 };
 842     int16_t *cache_mv = h->mb.cache.mv[0][x264_scan8[i8*4]];
 843     int16_t *cache_mv2 = cache_mv + pixel_mv_offs[m->i_pixel];
 844     const int16_t *p_cost_mvx, *p_cost_mvy;
 845     const int bw = x264_pixel_size[m->i_pixel].w>>2;
 846     const int bh = x264_pixel_size[m->i_pixel].h>>2;
 847     const int i_pixel = m->i_pixel;
 848
 849     DECLARE_ALIGNED( uint8_t, pix[16*16], 16 );
 850     int bcost = m->i_pixel == PIXEL_16x16 ? m->cost : COST_MAX;
 851     int bmx = m->mv[0];
 852     int bmy = m->mv[1];
 853     int pmx, pmy, omx, omy, i;
 854     int odir = -1, bdir;
 855     unsigned bsatd, satds[4];
 856
 857     int visited[16*13] = {0}; // only need 13x13, but 16 is more convenient
 858     int *p_visited = &visited[6+6*16];
 859
 860     if( m->i_pixel != PIXEL_16x16 && i8 != 0 )
 861         x264_mb_predict_mv( h, 0, i8*4, bw, m->mvp );
 862     pmx = m->mvp[0];
 863     pmy = m->mvp[1];
 864     p_cost_mvx = m->p_cost_mv - pmx;
 865     p_cost_mvy = m->p_cost_mv - pmy;
 866     COST_MV_SATD( bmx, bmy, bsatd );
 867     if( m->i_pixel != PIXEL_16x16 )
 868         COST_MV_RD( bmx, bmy, 0, -1 );
 869
 870     /* check the predicted mv */
 871     if( (bmx != pmx || bmy != pmy)
 872         && pmx >= h->mb.mv_min_spel[0] && pmx <= h->mb.mv_max_spel[0]
 873         && pmy >= h->mb.mv_min_spel[1] && pmy <= h->mb.mv_max_spel[1] )
 874     {
 875         int satd;
 876         COST_MV_SATD( pmx, pmy, satd );
 877         COST_MV_RD( pmx, pmy, satd, -1 );
 878     }
 879
 880     /* mark mv and mvp as visited */
 881     p_visited[0] = 1;
 882     p_visited -= bmx + bmy*16;
 883     {
 884         int mx = bmx ^ m->mv[0] ^ pmx;
 885         int my = bmy ^ m->mv[1] ^ pmy;
 886         if( abs(mx-bmx) < 7 && abs(my-bmy) < 7 )
 887             p_visited[mx + my*16] = 1;
 888     }
 889
 890     /* hpel diamond */
 891     bdir = -1;
 892     for( i = 0; i < 2; i++ )
 893     {
 894          omx = bmx;
 895          omy = bmy;
 896          odir = bdir;
 897          COST_MV_SATD( omx, omy - 2, satds[0] );
 898          COST_MV_SATD( omx, omy + 2, satds[1] );
 899          COST_MV_SATD( omx - 2, omy, satds[2] );
 900          COST_MV_SATD( omx + 2, omy, satds[3] );
 901          COST_MV_RD( omx, omy - 2, satds[0], 0 );
 902          COST_MV_RD( omx, omy + 2, satds[1], 1 );
 903          COST_MV_RD( omx - 2, omy, satds[2], 2 );
 904          COST_MV_RD( omx + 2, omy, satds[3], 3 );
 905          if( bmx == omx && bmy == omy )
 906             break;
 907     }
 908
 909     /* qpel diamond */
 910     bdir = -1;
 911     for( i = 0; i < 2; i++ )
 912     {
 913          omx = bmx;
 914          omy = bmy;
 915          odir = bdir;
 916          COST_MV_SATD( omx, omy - 1, satds[0] );
 917          COST_MV_SATD( omx, omy + 1, satds[1] );
 918          COST_MV_SATD( omx - 1, omy, satds[2] );
 919          COST_MV_SATD( omx + 1, omy, satds[3] );
 920          COST_MV_RD( omx, omy - 1, satds[0], 0 );
 921          COST_MV_RD( omx, omy + 1, satds[1], 1 );
 922          COST_MV_RD( omx - 1, omy, satds[2], 2 );
 923          COST_MV_RD( omx + 1, omy, satds[3], 3 );
 924          if( bmx == omx && bmy == omy )
 925             break;
 926     }
 927
 928     m->cost = bcost;
 929     m->mv[0] = bmx;
 930     m->mv[1] = bmy;
 931
 932     x264_macroblock_cache_mv ( h, 2*(i8&1), i8&2, bw, bh, 0, bmx, bmy );
 933     x264_macroblock_cache_mvd( h, 2*(i8&1), i8&2, bw, bh, 0, bmx - pmx, bmy - pmy );
 934 }
 935