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