granicus.if.org Git - libvpx/blob - vp9/encoder/vp9_mcomp.c

   1 /*
   2  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #include <limits.h>
  12 #include <math.h>
  13 #include <stdio.h>
  14
  15 #include "./vpx_config.h"
  16
  17 #include "vpx_mem/vpx_mem.h"
  18
  19 #include "vp9/common/vp9_common.h"
  20
  21 #include "vp9/encoder/vp9_encoder.h"
  22 #include "vp9/encoder/vp9_mcomp.h"
  23
  24 // #define NEW_DIAMOND_SEARCH
  25
  26 static INLINE const uint8_t *get_buf_from_mv(const struct buf_2d *buf,
  27                                              const MV *mv) {
  28   return &buf->buf[mv->row * buf->stride + mv->col];
  29 }
  30
  31 void vp9_set_mv_search_range(MACROBLOCK *x, const MV *mv) {
  32   int col_min = (mv->col >> 3) - MAX_FULL_PEL_VAL + (mv->col & 7 ? 1 : 0);
  33   int row_min = (mv->row >> 3) - MAX_FULL_PEL_VAL + (mv->row & 7 ? 1 : 0);
  34   int col_max = (mv->col >> 3) + MAX_FULL_PEL_VAL;
  35   int row_max = (mv->row >> 3) + MAX_FULL_PEL_VAL;
  36
  37   col_min = MAX(col_min, (MV_LOW >> 3) + 1);
  38   row_min = MAX(row_min, (MV_LOW >> 3) + 1);
  39   col_max = MIN(col_max, (MV_UPP >> 3) - 1);
  40   row_max = MIN(row_max, (MV_UPP >> 3) - 1);
  41
  42   // Get intersection of UMV window and valid MV window to reduce # of checks
  43   // in diamond search.
  44   if (x->mv_col_min < col_min)
  45     x->mv_col_min = col_min;
  46   if (x->mv_col_max > col_max)
  47     x->mv_col_max = col_max;
  48   if (x->mv_row_min < row_min)
  49     x->mv_row_min = row_min;
  50   if (x->mv_row_max > row_max)
  51     x->mv_row_max = row_max;
  52 }
  53
  54 int vp9_init_search_range(int size) {
  55   int sr = 0;
  56   // Minimum search size no matter what the passed in value.
  57   size = MAX(16, size);
  58
  59   while ((size << sr) < MAX_FULL_PEL_VAL)
  60     sr++;
  61
  62   sr = MIN(sr, MAX_MVSEARCH_STEPS - 2);
  63   return sr;
  64 }
  65
  66 static INLINE int mv_cost(const MV *mv,
  67                           const int *joint_cost, int *const comp_cost[2]) {
  68   return joint_cost[vp9_get_mv_joint(mv)] +
  69              comp_cost[0][mv->row] + comp_cost[1][mv->col];
  70 }
  71
  72 int vp9_mv_bit_cost(const MV *mv, const MV *ref,
  73                     const int *mvjcost, int *mvcost[2], int weight) {
  74   const MV diff = { mv->row - ref->row,
  75                     mv->col - ref->col };
  76   return ROUND_POWER_OF_TWO(mv_cost(&diff, mvjcost, mvcost) * weight, 7);
  77 }
  78
  79 static int mv_err_cost(const MV *mv, const MV *ref,
  80                        const int *mvjcost, int *mvcost[2],
  81                        int error_per_bit) {
  82   if (mvcost) {
  83     const MV diff = { mv->row - ref->row,
  84                       mv->col - ref->col };
  85     return ROUND_POWER_OF_TWO(mv_cost(&diff, mvjcost, mvcost) *
  86                                   error_per_bit, 13);
  87   }
  88   return 0;
  89 }
  90
  91 static int mvsad_err_cost(const MACROBLOCK *x, const MV *mv, const MV *ref,
  92                           int error_per_bit) {
  93   if (x->nmvsadcost) {
  94     const MV diff = { mv->row - ref->row,
  95                       mv->col - ref->col };
  96     return ROUND_POWER_OF_TWO(mv_cost(&diff, x->nmvjointsadcost,
  97                                       x->nmvsadcost) * error_per_bit, 8);
  98   }
  99   return 0;
 100 }
 101
 102 void vp9_init_dsmotion_compensation(search_site_config *cfg, int stride) {
 103   int len, ss_count = 1;
 104
 105   cfg->ss[0].mv.col = cfg->ss[0].mv.row = 0;
 106   cfg->ss[0].offset = 0;
 107
 108   for (len = MAX_FIRST_STEP; len > 0; len /= 2) {
 109     // Generate offsets for 4 search sites per step.
 110     const MV ss_mvs[] = {{-len, 0}, {len, 0}, {0, -len}, {0, len}};
 111     int i;
 112     for (i = 0; i < 4; ++i) {
 113       search_site *const ss = &cfg->ss[ss_count++];
 114       ss->mv = ss_mvs[i];
 115       ss->offset = ss->mv.row * stride + ss->mv.col;
 116     }
 117   }
 118
 119   cfg->ss_count = ss_count;
 120   cfg->searches_per_step = 4;
 121 }
 122
 123 void vp9_init3smotion_compensation(search_site_config *cfg, int stride) {
 124   int len, ss_count = 1;
 125
 126   cfg->ss[0].mv.col = cfg->ss[0].mv.row = 0;
 127   cfg->ss[0].offset = 0;
 128
 129   for (len = MAX_FIRST_STEP; len > 0; len /= 2) {
 130     // Generate offsets for 8 search sites per step.
 131     const MV ss_mvs[8] = {
 132       {-len,  0  }, {len,  0  }, { 0,   -len}, {0,    len},
 133       {-len, -len}, {-len, len}, {len,  -len}, {len,  len}
 134     };
 135     int i;
 136     for (i = 0; i < 8; ++i) {
 137       search_site *const ss = &cfg->ss[ss_count++];
 138       ss->mv = ss_mvs[i];
 139       ss->offset = ss->mv.row * stride + ss->mv.col;
 140     }
 141   }
 142
 143   cfg->ss_count = ss_count;
 144   cfg->searches_per_step = 8;
 145 }
 146
 147 /*
 148  * To avoid the penalty for crossing cache-line read, preload the reference
 149  * area in a small buffer, which is aligned to make sure there won't be crossing
 150  * cache-line read while reading from this buffer. This reduced the cpu
 151  * cycles spent on reading ref data in sub-pixel filter functions.
 152  * TODO: Currently, since sub-pixel search range here is -3 ~ 3, copy 22 rows x
 153  * 32 cols area that is enough for 16x16 macroblock. Later, for SPLITMV, we
 154  * could reduce the area.
 155  */
 156
 157 /* estimated cost of a motion vector (r,c) */
 158 #define MVC(r, c)                                       \
 159     (mvcost ?                                           \
 160      ((mvjcost[((r) != rr) * 2 + ((c) != rc)] +         \
 161        mvcost[0][((r) - rr)] + mvcost[1][((c) - rc)]) * \
 162       error_per_bit + 4096) >> 13 : 0)
 163
 164
 165 // convert motion vector component to offset for svf calc
 166 static INLINE int sp(int x) {
 167   return (x & 7) << 1;
 168 }
 169
 170 static INLINE const uint8_t *pre(const uint8_t *buf, int stride, int r, int c) {
 171   return &buf[(r >> 3) * stride + (c >> 3)];
 172 }
 173
 174 /* checks if (r, c) has better score than previous best */
 175 #define CHECK_BETTER(v, r, c) \
 176   if (c >= minc && c <= maxc && r >= minr && r <= maxr) {              \
 177     if (second_pred == NULL)                                           \
 178       thismse = vfp->svf(pre(y, y_stride, r, c), y_stride, sp(c), sp(r), z, \
 179                              src_stride, &sse);                        \
 180     else                                                               \
 181       thismse = vfp->svaf(pre(y, y_stride, r, c), y_stride, sp(c), sp(r), \
 182                               z, src_stride, &sse, second_pred);       \
 183     if ((v = MVC(r, c) + thismse) < besterr) {                         \
 184       besterr = v;                                                     \
 185       br = r;                                                          \
 186       bc = c;                                                          \
 187       *distortion = thismse;                                           \
 188       *sse1 = sse;                                                     \
 189     }                                                                  \
 190   } else {                                                             \
 191     v = INT_MAX;                                                       \
 192   }
 193
 194 #define FIRST_LEVEL_CHECKS                              \
 195   {                                                     \
 196     unsigned int left, right, up, down, diag;           \
 197     CHECK_BETTER(left, tr, tc - hstep);                 \
 198     CHECK_BETTER(right, tr, tc + hstep);                \
 199     CHECK_BETTER(up, tr - hstep, tc);                   \
 200     CHECK_BETTER(down, tr + hstep, tc);                 \
 201     whichdir = (left < right ? 0 : 1) +                 \
 202                (up < down ? 0 : 2);                     \
 203     switch (whichdir) {                                 \
 204       case 0:                                           \
 205         CHECK_BETTER(diag, tr - hstep, tc - hstep);     \
 206         break;                                          \
 207       case 1:                                           \
 208         CHECK_BETTER(diag, tr - hstep, tc + hstep);     \
 209         break;                                          \
 210       case 2:                                           \
 211         CHECK_BETTER(diag, tr + hstep, tc - hstep);     \
 212         break;                                          \
 213       case 3:                                           \
 214         CHECK_BETTER(diag, tr + hstep, tc + hstep);     \
 215         break;                                          \
 216     }                                                   \
 217   }
 218
 219 #define SECOND_LEVEL_CHECKS                             \
 220   {                                                     \
 221     int kr, kc;                                         \
 222     unsigned int second;                                \
 223     if (tr != br && tc != bc) {                         \
 224       kr = br - tr;                                     \
 225       kc = bc - tc;                                     \
 226       CHECK_BETTER(second, tr + kr, tc + 2 * kc);       \
 227       CHECK_BETTER(second, tr + 2 * kr, tc + kc);       \
 228     } else if (tr == br && tc != bc) {                  \
 229       kc = bc - tc;                                     \
 230       CHECK_BETTER(second, tr + hstep, tc + 2 * kc);    \
 231       CHECK_BETTER(second, tr - hstep, tc + 2 * kc);    \
 232       switch (whichdir) {                               \
 233         case 0:                                         \
 234         case 1:                                         \
 235           CHECK_BETTER(second, tr + hstep, tc + kc);    \
 236           break;                                        \
 237         case 2:                                         \
 238         case 3:                                         \
 239           CHECK_BETTER(second, tr - hstep, tc + kc);    \
 240           break;                                        \
 241       }                                                 \
 242     } else if (tr != br && tc == bc) {                  \
 243       kr = br - tr;                                     \
 244       CHECK_BETTER(second, tr + 2 * kr, tc + hstep);    \
 245       CHECK_BETTER(second, tr + 2 * kr, tc - hstep);    \
 246       switch (whichdir) {                               \
 247         case 0:                                         \
 248         case 2:                                         \
 249           CHECK_BETTER(second, tr + kr, tc + hstep);    \
 250           break;                                        \
 251         case 1:                                         \
 252         case 3:                                         \
 253           CHECK_BETTER(second, tr + kr, tc - hstep);    \
 254           break;                                        \
 255       }                                                 \
 256     }                                                   \
 257   }
 258
 259 #define SETUP_SUBPEL_SEARCH                                                \
 260   const uint8_t *const z = x->plane[0].src.buf;                            \
 261   const int src_stride = x->plane[0].src.stride;                           \
 262   const MACROBLOCKD *xd = &x->e_mbd;                                       \
 263   unsigned int besterr = INT_MAX;                                          \
 264   unsigned int sse;                                                        \
 265   unsigned int whichdir;                                                   \
 266   int thismse;                                                             \
 267   const unsigned int halfiters = iters_per_step;                           \
 268   const unsigned int quarteriters = iters_per_step;                        \
 269   const unsigned int eighthiters = iters_per_step;                         \
 270   const int y_stride = xd->plane[0].pre[0].stride;                         \
 271   const int offset = bestmv->row * y_stride + bestmv->col;                 \
 272   const uint8_t *const y = xd->plane[0].pre[0].buf;                        \
 273                                                                            \
 274   int rr = ref_mv->row;                                                    \
 275   int rc = ref_mv->col;                                                    \
 276   int br = bestmv->row * 8;                                                \
 277   int bc = bestmv->col * 8;                                                \
 278   int hstep = 4;                                                           \
 279   const int minc = MAX(x->mv_col_min * 8, ref_mv->col - MV_MAX);           \
 280   const int maxc = MIN(x->mv_col_max * 8, ref_mv->col + MV_MAX);           \
 281   const int minr = MAX(x->mv_row_min * 8, ref_mv->row - MV_MAX);           \
 282   const int maxr = MIN(x->mv_row_max * 8, ref_mv->row + MV_MAX);           \
 283   int tr = br;                                                             \
 284   int tc = bc;                                                             \
 285                                                                            \
 286   bestmv->row *= 8;                                                        \
 287   bestmv->col *= 8;                                                        \
 288   if (second_pred != NULL) {                                               \
 289     DECLARE_ALIGNED_ARRAY(16, uint8_t, comp_pred, 64 * 64);                \
 290     vp9_comp_avg_pred(comp_pred, second_pred, w, h, y + offset, y_stride); \
 291     besterr = vfp->vf(comp_pred, w, z, src_stride, sse1);                  \
 292   } else {                                                                 \
 293     besterr = vfp->vf(y + offset, y_stride, z, src_stride, sse1);          \
 294   }                                                                        \
 295   *distortion = besterr;                                                   \
 296   besterr += mv_err_cost(bestmv, ref_mv, mvjcost, mvcost, error_per_bit);
 297
 298 int vp9_find_best_sub_pixel_tree_pruned(const MACROBLOCK *x,
 299                                         MV *bestmv, const MV *ref_mv,
 300                                         int allow_hp,
 301                                         int error_per_bit,
 302                                         const vp9_variance_fn_ptr_t *vfp,
 303                                         int forced_stop,
 304                                         int iters_per_step,
 305                                         int *sad_list,
 306                                         int *mvjcost, int *mvcost[2],
 307                                         int *distortion,
 308                                         unsigned int *sse1,
 309                                         const uint8_t *second_pred,
 310                                         int w, int h) {
 311   SETUP_SUBPEL_SEARCH;
 312
 313   if (sad_list &&
 314       sad_list[0] != INT_MAX && sad_list[1] != INT_MAX &&
 315       sad_list[2] != INT_MAX && sad_list[3] != INT_MAX &&
 316       sad_list[4] != INT_MAX) {
 317     unsigned int left, right, up, down, diag;
 318     whichdir = (sad_list[1] < sad_list[3] ? 0 : 1) +
 319                (sad_list[2] < sad_list[4] ? 0 : 2);
 320     switch (whichdir) {
 321       case 0:
 322         CHECK_BETTER(left, tr, tc - hstep);
 323         CHECK_BETTER(down, tr + hstep, tc);
 324         CHECK_BETTER(diag, tr + hstep, tc - hstep);
 325         break;
 326       case 1:
 327         CHECK_BETTER(right, tr, tc + hstep);
 328         CHECK_BETTER(down, tr + hstep, tc);
 329         CHECK_BETTER(diag, tr + hstep, tc + hstep);
 330         break;
 331       case 2:
 332         CHECK_BETTER(left, tr, tc - hstep);
 333         CHECK_BETTER(up, tr - hstep, tc);
 334         CHECK_BETTER(diag, tr - hstep, tc - hstep);
 335         break;
 336       case 3:
 337         CHECK_BETTER(right, tr, tc + hstep);
 338         CHECK_BETTER(up, tr - hstep, tc);
 339         CHECK_BETTER(diag, tr - hstep, tc + hstep);
 340         break;
 341     }
 342   } else {
 343     FIRST_LEVEL_CHECKS;
 344     if (halfiters > 1) {
 345       SECOND_LEVEL_CHECKS;
 346     }
 347   }
 348
 349   tr = br;
 350   tc = bc;
 351
 352   // Each subsequent iteration checks at least one point in common with
 353   // the last iteration could be 2 ( if diag selected) 1/4 pel
 354
 355   // Note forced_stop: 0 - full, 1 - qtr only, 2 - half only
 356   if (forced_stop != 2) {
 357     hstep >>= 1;
 358     FIRST_LEVEL_CHECKS;
 359     if (quarteriters > 1) {
 360       SECOND_LEVEL_CHECKS;
 361     }
 362     tr = br;
 363     tc = bc;
 364   }
 365
 366   if (allow_hp && vp9_use_mv_hp(ref_mv) && forced_stop == 0) {
 367     hstep >>= 1;
 368     FIRST_LEVEL_CHECKS;
 369     if (eighthiters > 1) {
 370       SECOND_LEVEL_CHECKS;
 371     }
 372     tr = br;
 373     tc = bc;
 374   }
 375   // These lines insure static analysis doesn't warn that
 376   // tr and tc aren't used after the above point.
 377   (void) tr;
 378   (void) tc;
 379
 380   bestmv->row = br;
 381   bestmv->col = bc;
 382
 383   if ((abs(bestmv->col - ref_mv->col) > (MAX_FULL_PEL_VAL << 3)) ||
 384       (abs(bestmv->row - ref_mv->row) > (MAX_FULL_PEL_VAL << 3)))
 385     return INT_MAX;
 386
 387   return besterr;
 388 }
 389
 390 int vp9_find_best_sub_pixel_tree(const MACROBLOCK *x,
 391                                  MV *bestmv, const MV *ref_mv,
 392                                  int allow_hp,
 393                                  int error_per_bit,
 394                                  const vp9_variance_fn_ptr_t *vfp,
 395                                  int forced_stop,
 396                                  int iters_per_step,
 397                                  int *sad_list,
 398                                  int *mvjcost, int *mvcost[2],
 399                                  int *distortion,
 400                                  unsigned int *sse1,
 401                                  const uint8_t *second_pred,
 402                                  int w, int h) {
 403   SETUP_SUBPEL_SEARCH;
 404   (void) sad_list;  // to silence compiler warning
 405
 406   // Each subsequent iteration checks at least one point in
 407   // common with the last iteration could be 2 ( if diag selected)
 408   // 1/2 pel
 409   FIRST_LEVEL_CHECKS;
 410   if (halfiters > 1) {
 411     SECOND_LEVEL_CHECKS;
 412   }
 413   tr = br;
 414   tc = bc;
 415
 416   // Each subsequent iteration checks at least one point in common with
 417   // the last iteration could be 2 ( if diag selected) 1/4 pel
 418
 419   // Note forced_stop: 0 - full, 1 - qtr only, 2 - half only
 420   if (forced_stop != 2) {
 421     hstep >>= 1;
 422     FIRST_LEVEL_CHECKS;
 423     if (quarteriters > 1) {
 424       SECOND_LEVEL_CHECKS;
 425     }
 426     tr = br;
 427     tc = bc;
 428   }
 429
 430   if (allow_hp && vp9_use_mv_hp(ref_mv) && forced_stop == 0) {
 431     hstep >>= 1;
 432     FIRST_LEVEL_CHECKS;
 433     if (eighthiters > 1) {
 434       SECOND_LEVEL_CHECKS;
 435     }
 436     tr = br;
 437     tc = bc;
 438   }
 439   // These lines insure static analysis doesn't warn that
 440   // tr and tc aren't used after the above point.
 441   (void) tr;
 442   (void) tc;
 443
 444   bestmv->row = br;
 445   bestmv->col = bc;
 446
 447   if ((abs(bestmv->col - ref_mv->col) > (MAX_FULL_PEL_VAL << 3)) ||
 448       (abs(bestmv->row - ref_mv->row) > (MAX_FULL_PEL_VAL << 3)))
 449     return INT_MAX;
 450
 451   return besterr;
 452 }
 453
 454 #undef MVC
 455 #undef PRE
 456 #undef CHECK_BETTER
 457
 458 static INLINE int check_bounds(const MACROBLOCK *x, int row, int col,
 459                                int range) {
 460   return ((row - range) >= x->mv_row_min) &
 461          ((row + range) <= x->mv_row_max) &
 462          ((col - range) >= x->mv_col_min) &
 463          ((col + range) <= x->mv_col_max);
 464 }
 465
 466 static INLINE int is_mv_in(const MACROBLOCK *x, const MV *mv) {
 467   return (mv->col >= x->mv_col_min) && (mv->col <= x->mv_col_max) &&
 468          (mv->row >= x->mv_row_min) && (mv->row <= x->mv_row_max);
 469 }
 470
 471 #define CHECK_BETTER \
 472   {\
 473     if (thissad < bestsad) {\
 474       if (use_mvcost) \
 475         thissad += mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit);\
 476       if (thissad < bestsad) {\
 477         bestsad = thissad;\
 478         best_site = i;\
 479       }\
 480     }\
 481   }
 482
 483 #define MAX_PATTERN_SCALES         11
 484 #define MAX_PATTERN_CANDIDATES      8  // max number of canddiates per scale
 485 #define PATTERN_CANDIDATES_REF      3  // number of refinement candidates
 486
 487 // Generic pattern search function that searches over multiple scales.
 488 // Each scale can have a different number of candidates and shape of
 489 // candidates as indicated in the num_candidates and candidates arrays
 490 // passed into this function
 491 //
 492 static int vp9_pattern_search(const MACROBLOCK *x,
 493                               MV *ref_mv,
 494                               int search_param,
 495                               int sad_per_bit,
 496                               int do_init_search,
 497                               int *sad_list,
 498                               const vp9_variance_fn_ptr_t *vfp,
 499                               int use_mvcost,
 500                               const MV *center_mv,
 501                               MV *best_mv,
 502                               const int num_candidates[MAX_PATTERN_SCALES],
 503                               const MV candidates[MAX_PATTERN_SCALES]
 504                                                  [MAX_PATTERN_CANDIDATES]) {
 505   const MACROBLOCKD *const xd = &x->e_mbd;
 506   static const int search_param_to_steps[MAX_MVSEARCH_STEPS] = {
 507     10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
 508   };
 509   int i, s, t;
 510   const struct buf_2d *const what = &x->plane[0].src;
 511   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
 512   int br, bc;
 513   int bestsad = INT_MAX;
 514   int thissad;
 515   int k = -1;
 516   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
 517   int best_init_s = search_param_to_steps[search_param];
 518   // adjust ref_mv to make sure it is within MV range
 519   clamp_mv(ref_mv, x->mv_col_min, x->mv_col_max, x->mv_row_min, x->mv_row_max);
 520   br = ref_mv->row;
 521   bc = ref_mv->col;
 522
 523   // Work out the start point for the search
 524   bestsad = vfp->sdf(what->buf, what->stride,
 525                      get_buf_from_mv(in_what, ref_mv), in_what->stride) +
 526       mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
 527
 528   // Search all possible scales upto the search param around the center point
 529   // pick the scale of the point that is best as the starting scale of
 530   // further steps around it.
 531   if (do_init_search) {
 532     s = best_init_s;
 533     best_init_s = -1;
 534     for (t = 0; t <= s; ++t) {
 535       int best_site = -1;
 536       if (check_bounds(x, br, bc, 1 << t)) {
 537         for (i = 0; i < num_candidates[t]; i++) {
 538           const MV this_mv = {br + candidates[t][i].row,
 539                               bc + candidates[t][i].col};
 540           thissad = vfp->sdf(what->buf, what->stride,
 541                              get_buf_from_mv(in_what, &this_mv),
 542                              in_what->stride);
 543           CHECK_BETTER
 544         }
 545       } else {
 546         for (i = 0; i < num_candidates[t]; i++) {
 547           const MV this_mv = {br + candidates[t][i].row,
 548                               bc + candidates[t][i].col};
 549           if (!is_mv_in(x, &this_mv))
 550             continue;
 551           thissad = vfp->sdf(what->buf, what->stride,
 552                              get_buf_from_mv(in_what, &this_mv),
 553                              in_what->stride);
 554           CHECK_BETTER
 555         }
 556       }
 557       if (best_site == -1) {
 558         continue;
 559       } else {
 560         best_init_s = t;
 561         k = best_site;
 562       }
 563     }
 564     if (best_init_s != -1) {
 565       br += candidates[best_init_s][k].row;
 566       bc += candidates[best_init_s][k].col;
 567     }
 568   }
 569
 570   // If the center point is still the best, just skip this and move to
 571   // the refinement step.
 572   if (best_init_s != -1) {
 573     int best_site = -1;
 574     s = best_init_s;
 575
 576     do {
 577       // No need to search all 6 points the 1st time if initial search was used
 578       if (!do_init_search || s != best_init_s) {
 579         if (check_bounds(x, br, bc, 1 << s)) {
 580           for (i = 0; i < num_candidates[s]; i++) {
 581             const MV this_mv = {br + candidates[s][i].row,
 582                                 bc + candidates[s][i].col};
 583             thissad = vfp->sdf(what->buf, what->stride,
 584                                get_buf_from_mv(in_what, &this_mv),
 585                                in_what->stride);
 586             CHECK_BETTER
 587           }
 588         } else {
 589           for (i = 0; i < num_candidates[s]; i++) {
 590             const MV this_mv = {br + candidates[s][i].row,
 591                                 bc + candidates[s][i].col};
 592             if (!is_mv_in(x, &this_mv))
 593               continue;
 594             thissad = vfp->sdf(what->buf, what->stride,
 595                                get_buf_from_mv(in_what, &this_mv),
 596                                in_what->stride);
 597             CHECK_BETTER
 598           }
 599         }
 600
 601         if (best_site == -1) {
 602           continue;
 603         } else {
 604           br += candidates[s][best_site].row;
 605           bc += candidates[s][best_site].col;
 606           k = best_site;
 607         }
 608       }
 609
 610       do {
 611         int next_chkpts_indices[PATTERN_CANDIDATES_REF];
 612         best_site = -1;
 613         next_chkpts_indices[0] = (k == 0) ? num_candidates[s] - 1 : k - 1;
 614         next_chkpts_indices[1] = k;
 615         next_chkpts_indices[2] = (k == num_candidates[s] - 1) ? 0 : k + 1;
 616
 617         if (check_bounds(x, br, bc, 1 << s)) {
 618           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 619             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 620                                 bc + candidates[s][next_chkpts_indices[i]].col};
 621             thissad = vfp->sdf(what->buf, what->stride,
 622                                get_buf_from_mv(in_what, &this_mv),
 623                                in_what->stride);
 624             CHECK_BETTER
 625           }
 626         } else {
 627           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 628             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 629                                 bc + candidates[s][next_chkpts_indices[i]].col};
 630             if (!is_mv_in(x, &this_mv))
 631               continue;
 632             thissad = vfp->sdf(what->buf, what->stride,
 633                                get_buf_from_mv(in_what, &this_mv),
 634                                in_what->stride);
 635             CHECK_BETTER
 636           }
 637         }
 638
 639         if (best_site != -1) {
 640           k = next_chkpts_indices[best_site];
 641           br += candidates[s][k].row;
 642           bc += candidates[s][k].col;
 643         }
 644       } while (best_site != -1);
 645     } while (s--);
 646   }
 647
 648   // Returns the one-away integer pel sad values around the best as follows:
 649   // sad_list[0]: sad at the best integer pel
 650   // sad_list[1]: sad at delta {0, -1} (left)   from the best integer pel
 651   // sad_list[2]: sad at delta { 1, 0} (bottom) from the best integer pel
 652   // sad_list[3]: sad at delta { 0, 1} (right)  from the best integer pel
 653   // sad_list[4]: sad at delta {-1, 0} (top)    from the best integer pel
 654   if (sad_list) {
 655     static const MV neighbors[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
 656     sad_list[0] = bestsad;
 657     if (check_bounds(x, br, bc, 1)) {
 658       for (i = 0; i < 4; i++) {
 659         const MV this_mv = {br + neighbors[i].row,
 660                             bc + neighbors[i].col};
 661         sad_list[i + 1] = vfp->sdf(what->buf, what->stride,
 662                                    get_buf_from_mv(in_what, &this_mv),
 663                                    in_what->stride) +
 664             (use_mvcost ?
 665              mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit) :
 666              0);
 667       }
 668     } else {
 669       for (i = 0; i < 4; i++) {
 670         const MV this_mv = {br + neighbors[i].row,
 671                             bc + neighbors[i].col};
 672         if (!is_mv_in(x, &this_mv))
 673           sad_list[i + 1] = INT_MAX;
 674         else
 675           sad_list[i + 1] = vfp->sdf(what->buf, what->stride,
 676                                      get_buf_from_mv(in_what, &this_mv),
 677                                      in_what->stride) +
 678               (use_mvcost ?
 679                mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit) :
 680                0);
 681       }
 682     }
 683   }
 684   best_mv->row = br;
 685   best_mv->col = bc;
 686   return bestsad;
 687 }
 688
 689 // A specialized function where the smallest scale search candidates
 690 // are 4 1-away neighbors, and sad_list is non-null
 691 // TODO(debargha): Merge this function with the one above. Also remove
 692 // use_mvcost option since it is always 1, to save unnecessary branches.
 693 static int vp9_pattern_search_sad(const MACROBLOCK *x,
 694                                   MV *ref_mv,
 695                                   int search_param,
 696                                   int sad_per_bit,
 697                                   int do_init_search,
 698                                   int *sad_list,
 699                                   const vp9_variance_fn_ptr_t *vfp,
 700                                   int use_mvcost,
 701                                   const MV *center_mv,
 702                                   MV *best_mv,
 703                                   const int num_candidates[MAX_PATTERN_SCALES],
 704                                   const MV candidates[MAX_PATTERN_SCALES]
 705                                                      [MAX_PATTERN_CANDIDATES]) {
 706   const MACROBLOCKD *const xd = &x->e_mbd;
 707   static const int search_param_to_steps[MAX_MVSEARCH_STEPS] = {
 708     10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
 709   };
 710   int i, s, t;
 711   const struct buf_2d *const what = &x->plane[0].src;
 712   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
 713   int br, bc;
 714   int bestsad = INT_MAX;
 715   int thissad;
 716   int k = -1;
 717   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
 718   int best_init_s = search_param_to_steps[search_param];
 719   // adjust ref_mv to make sure it is within MV range
 720   clamp_mv(ref_mv, x->mv_col_min, x->mv_col_max, x->mv_row_min, x->mv_row_max);
 721   br = ref_mv->row;
 722   bc = ref_mv->col;
 723   if (sad_list != NULL) {
 724     sad_list[0] = sad_list[1] = sad_list[2] = sad_list[3] = sad_list[4] =
 725         INT_MAX;
 726   }
 727
 728   // Work out the start point for the search
 729   bestsad = vfp->sdf(what->buf, what->stride,
 730                      get_buf_from_mv(in_what, ref_mv), in_what->stride) +
 731       mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
 732
 733   // Search all possible scales upto the search param around the center point
 734   // pick the scale of the point that is best as the starting scale of
 735   // further steps around it.
 736   if (do_init_search) {
 737     s = best_init_s;
 738     best_init_s = -1;
 739     for (t = 0; t <= s; ++t) {
 740       int best_site = -1;
 741       if (check_bounds(x, br, bc, 1 << t)) {
 742         for (i = 0; i < num_candidates[t]; i++) {
 743           const MV this_mv = {br + candidates[t][i].row,
 744                               bc + candidates[t][i].col};
 745           thissad = vfp->sdf(what->buf, what->stride,
 746                              get_buf_from_mv(in_what, &this_mv),
 747                              in_what->stride);
 748           CHECK_BETTER
 749         }
 750       } else {
 751         for (i = 0; i < num_candidates[t]; i++) {
 752           const MV this_mv = {br + candidates[t][i].row,
 753                               bc + candidates[t][i].col};
 754           if (!is_mv_in(x, &this_mv))
 755             continue;
 756           thissad = vfp->sdf(what->buf, what->stride,
 757                              get_buf_from_mv(in_what, &this_mv),
 758                              in_what->stride);
 759           CHECK_BETTER
 760         }
 761       }
 762       if (best_site == -1) {
 763         continue;
 764       } else {
 765         best_init_s = t;
 766         k = best_site;
 767       }
 768     }
 769     if (best_init_s != -1) {
 770       br += candidates[best_init_s][k].row;
 771       bc += candidates[best_init_s][k].col;
 772     }
 773   }
 774
 775   // If the center point is still the best, just skip this and move to
 776   // the refinement step.
 777   if (best_init_s != -1) {
 778     int do_sad = (num_candidates[0] == 4 && sad_list != NULL);
 779     int best_site = -1;
 780     s = best_init_s;
 781
 782     for (; s >= do_sad; s--) {
 783       if (!do_init_search || s != best_init_s) {
 784         if (check_bounds(x, br, bc, 1 << s)) {
 785           for (i = 0; i < num_candidates[s]; i++) {
 786             const MV this_mv = {br + candidates[s][i].row,
 787                                 bc + candidates[s][i].col};
 788             thissad = vfp->sdf(what->buf, what->stride,
 789                                get_buf_from_mv(in_what, &this_mv),
 790                                in_what->stride);
 791             CHECK_BETTER
 792           }
 793         } else {
 794           for (i = 0; i < num_candidates[s]; i++) {
 795             const MV this_mv = {br + candidates[s][i].row,
 796                                 bc + candidates[s][i].col};
 797             if (!is_mv_in(x, &this_mv))
 798               continue;
 799             thissad = vfp->sdf(what->buf, what->stride,
 800                                get_buf_from_mv(in_what, &this_mv),
 801                                in_what->stride);
 802             CHECK_BETTER
 803           }
 804         }
 805
 806         if (best_site == -1) {
 807           continue;
 808         } else {
 809           br += candidates[s][best_site].row;
 810           bc += candidates[s][best_site].col;
 811           k = best_site;
 812         }
 813       }
 814
 815       do {
 816         int next_chkpts_indices[PATTERN_CANDIDATES_REF];
 817         best_site = -1;
 818         next_chkpts_indices[0] = (k == 0) ? num_candidates[s] - 1 : k - 1;
 819         next_chkpts_indices[1] = k;
 820         next_chkpts_indices[2] = (k == num_candidates[s] - 1) ? 0 : k + 1;
 821
 822         if (check_bounds(x, br, bc, 1 << s)) {
 823           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 824             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 825                                 bc + candidates[s][next_chkpts_indices[i]].col};
 826             thissad = vfp->sdf(what->buf, what->stride,
 827                                get_buf_from_mv(in_what, &this_mv),
 828                                in_what->stride);
 829             CHECK_BETTER
 830           }
 831         } else {
 832           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 833             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 834                                 bc + candidates[s][next_chkpts_indices[i]].col};
 835             if (!is_mv_in(x, &this_mv))
 836               continue;
 837             thissad = vfp->sdf(what->buf, what->stride,
 838                                get_buf_from_mv(in_what, &this_mv),
 839                                in_what->stride);
 840             CHECK_BETTER
 841           }
 842         }
 843
 844         if (best_site != -1) {
 845           k = next_chkpts_indices[best_site];
 846           br += candidates[s][k].row;
 847           bc += candidates[s][k].col;
 848         }
 849       } while (best_site != -1);
 850     }
 851
 852     // Note: If we enter the if below, then sad_list must be non-NULL.
 853     if (s == 0) {
 854       sad_list[0] = bestsad;
 855       if (!do_init_search || s != best_init_s) {
 856         if (check_bounds(x, br, bc, 1 << s)) {
 857           for (i = 0; i < num_candidates[s]; i++) {
 858             const MV this_mv = {br + candidates[s][i].row,
 859                                 bc + candidates[s][i].col};
 860             sad_list[i + 1] =
 861             thissad = vfp->sdf(what->buf, what->stride,
 862                                get_buf_from_mv(in_what, &this_mv),
 863                                in_what->stride);
 864             CHECK_BETTER
 865           }
 866         } else {
 867           for (i = 0; i < num_candidates[s]; i++) {
 868             const MV this_mv = {br + candidates[s][i].row,
 869                                 bc + candidates[s][i].col};
 870             if (!is_mv_in(x, &this_mv))
 871               continue;
 872             sad_list[i + 1] =
 873             thissad = vfp->sdf(what->buf, what->stride,
 874                                get_buf_from_mv(in_what, &this_mv),
 875                                in_what->stride);
 876             CHECK_BETTER
 877           }
 878         }
 879
 880         if (best_site != -1) {
 881           br += candidates[s][best_site].row;
 882           bc += candidates[s][best_site].col;
 883           k = best_site;
 884         }
 885       }
 886       while (best_site != -1) {
 887         int next_chkpts_indices[PATTERN_CANDIDATES_REF];
 888         best_site = -1;
 889         next_chkpts_indices[0] = (k == 0) ? num_candidates[s] - 1 : k - 1;
 890         next_chkpts_indices[1] = k;
 891         next_chkpts_indices[2] = (k == num_candidates[s] - 1) ? 0 : k + 1;
 892         sad_list[1] = sad_list[2] = sad_list[3] = sad_list[4] = INT_MAX;
 893         sad_list[((k + 2) % 4) + 1] = sad_list[0];
 894         sad_list[0] = bestsad;
 895
 896         if (check_bounds(x, br, bc, 1 << s)) {
 897           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 898             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 899                                 bc + candidates[s][next_chkpts_indices[i]].col};
 900             sad_list[next_chkpts_indices[i] + 1] =
 901             thissad = vfp->sdf(what->buf, what->stride,
 902                                get_buf_from_mv(in_what, &this_mv),
 903                                in_what->stride);
 904             CHECK_BETTER
 905           }
 906         } else {
 907           for (i = 0; i < PATTERN_CANDIDATES_REF; i++) {
 908             const MV this_mv = {br + candidates[s][next_chkpts_indices[i]].row,
 909                                 bc + candidates[s][next_chkpts_indices[i]].col};
 910             if (!is_mv_in(x, &this_mv)) {
 911               sad_list[next_chkpts_indices[i] + 1] = INT_MAX;
 912               continue;
 913             }
 914             sad_list[next_chkpts_indices[i] + 1] =
 915             thissad = vfp->sdf(what->buf, what->stride,
 916                                get_buf_from_mv(in_what, &this_mv),
 917                                in_what->stride);
 918             CHECK_BETTER
 919           }
 920         }
 921
 922         if (best_site != -1) {
 923           k = next_chkpts_indices[best_site];
 924           br += candidates[s][k].row;
 925           bc += candidates[s][k].col;
 926         }
 927       }
 928     }
 929   }
 930
 931   // Returns the one-away integer pel sad values around the best as follows:
 932   // sad_list[0]: sad at the best integer pel
 933   // sad_list[1]: sad at delta {0, -1} (left)   from the best integer pel
 934   // sad_list[2]: sad at delta { 1, 0} (bottom) from the best integer pel
 935   // sad_list[3]: sad at delta { 0, 1} (right)  from the best integer pel
 936   // sad_list[4]: sad at delta {-1, 0} (top)    from the best integer pel
 937   if (sad_list) {
 938     static const MV neighbors[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
 939     if (sad_list[0] == INT_MAX) {
 940       sad_list[0] = bestsad;
 941       if (check_bounds(x, br, bc, 1)) {
 942         for (i = 0; i < 4; i++) {
 943           const MV this_mv = {br + neighbors[i].row,
 944             bc + neighbors[i].col};
 945           sad_list[i + 1] = vfp->sdf(what->buf, what->stride,
 946                                      get_buf_from_mv(in_what, &this_mv),
 947                                      in_what->stride);
 948         }
 949       } else {
 950         for (i = 0; i < 4; i++) {
 951           const MV this_mv = {br + neighbors[i].row,
 952             bc + neighbors[i].col};
 953           if (!is_mv_in(x, &this_mv))
 954             sad_list[i + 1] = INT_MAX;
 955           else
 956             sad_list[i + 1] = vfp->sdf(what->buf, what->stride,
 957                                        get_buf_from_mv(in_what, &this_mv),
 958                                        in_what->stride);
 959         }
 960       }
 961     } else {
 962       if (use_mvcost) {
 963         for (i = 0; i < 4; i++) {
 964           const MV this_mv = {br + neighbors[i].row,
 965             bc + neighbors[i].col};
 966           if (sad_list[i + 1] != INT_MAX) {
 967             sad_list[i + 1] +=
 968                 mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit);
 969           }
 970         }
 971       }
 972     }
 973   }
 974   best_mv->row = br;
 975   best_mv->col = bc;
 976   return bestsad;
 977 }
 978
 979 int vp9_get_mvpred_var(const MACROBLOCK *x,
 980                        const MV *best_mv, const MV *center_mv,
 981                        const vp9_variance_fn_ptr_t *vfp,
 982                        int use_mvcost) {
 983   const MACROBLOCKD *const xd = &x->e_mbd;
 984   const struct buf_2d *const what = &x->plane[0].src;
 985   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
 986   const MV mv = {best_mv->row * 8, best_mv->col * 8};
 987   unsigned int unused;
 988
 989   return vfp->vf(what->buf, what->stride,
 990                  get_buf_from_mv(in_what, best_mv), in_what->stride, &unused) +
 991       (use_mvcost ?  mv_err_cost(&mv, center_mv, x->nmvjointcost,
 992                                  x->mvcost, x->errorperbit) : 0);
 993 }
 994
 995 int vp9_get_mvpred_av_var(const MACROBLOCK *x,
 996                           const MV *best_mv, const MV *center_mv,
 997                           const uint8_t *second_pred,
 998                           const vp9_variance_fn_ptr_t *vfp,
 999                           int use_mvcost) {
1000   const MACROBLOCKD *const xd = &x->e_mbd;
1001   const struct buf_2d *const what = &x->plane[0].src;
1002   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1003   const MV mv = {best_mv->row * 8, best_mv->col * 8};
1004   unsigned int unused;
1005
1006   return vfp->svaf(get_buf_from_mv(in_what, best_mv), in_what->stride, 0, 0,
1007                    what->buf, what->stride, &unused, second_pred) +
1008       (use_mvcost ?  mv_err_cost(&mv, center_mv, x->nmvjointcost,
1009                                  x->mvcost, x->errorperbit) : 0);
1010 }
1011
1012 int vp9_hex_search(const MACROBLOCK *x,
1013                    MV *ref_mv,
1014                    int search_param,
1015                    int sad_per_bit,
1016                    int do_init_search,
1017                    int *sad_list,
1018                    const vp9_variance_fn_ptr_t *vfp,
1019                    int use_mvcost,
1020                    const MV *center_mv, MV *best_mv) {
1021   // First scale has 8-closest points, the rest have 6 points in hex shape
1022   // at increasing scales
1023   static const int hex_num_candidates[MAX_PATTERN_SCALES] = {
1024     8, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6
1025   };
1026   // Note that the largest candidate step at each scale is 2^scale
1027   static const MV hex_candidates[MAX_PATTERN_SCALES][MAX_PATTERN_CANDIDATES] = {
1028     {{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, { 0, 1}, { -1, 1}, {-1, 0}},
1029     {{-1, -2}, {1, -2}, {2, 0}, {1, 2}, { -1, 2}, { -2, 0}},
1030     {{-2, -4}, {2, -4}, {4, 0}, {2, 4}, { -2, 4}, { -4, 0}},
1031     {{-4, -8}, {4, -8}, {8, 0}, {4, 8}, { -4, 8}, { -8, 0}},
1032     {{-8, -16}, {8, -16}, {16, 0}, {8, 16}, { -8, 16}, { -16, 0}},
1033     {{-16, -32}, {16, -32}, {32, 0}, {16, 32}, { -16, 32}, { -32, 0}},
1034     {{-32, -64}, {32, -64}, {64, 0}, {32, 64}, { -32, 64}, { -64, 0}},
1035     {{-64, -128}, {64, -128}, {128, 0}, {64, 128}, { -64, 128}, { -128, 0}},
1036     {{-128, -256}, {128, -256}, {256, 0}, {128, 256}, { -128, 256}, { -256, 0}},
1037     {{-256, -512}, {256, -512}, {512, 0}, {256, 512}, { -256, 512}, { -512, 0}},
1038     {{-512, -1024}, {512, -1024}, {1024, 0}, {512, 1024}, { -512, 1024},
1039       { -1024, 0}},
1040   };
1041   return vp9_pattern_search(x, ref_mv, search_param, sad_per_bit,
1042                             do_init_search, sad_list, vfp, use_mvcost,
1043                             center_mv, best_mv,
1044                             hex_num_candidates, hex_candidates);
1045 }
1046
1047 int vp9_bigdia_search(const MACROBLOCK *x,
1048                       MV *ref_mv,
1049                       int search_param,
1050                       int sad_per_bit,
1051                       int do_init_search,
1052                       int *sad_list,
1053                       const vp9_variance_fn_ptr_t *vfp,
1054                       int use_mvcost,
1055                       const MV *center_mv,
1056                       MV *best_mv) {
1057   // First scale has 4-closest points, the rest have 8 points in diamond
1058   // shape at increasing scales
1059   static const int bigdia_num_candidates[MAX_PATTERN_SCALES] = {
1060     4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1061   };
1062   // Note that the largest candidate step at each scale is 2^scale
1063   static const MV bigdia_candidates[MAX_PATTERN_SCALES]
1064                                    [MAX_PATTERN_CANDIDATES] = {
1065     {{0, -1}, {1, 0}, { 0, 1}, {-1, 0}},
1066     {{-1, -1}, {0, -2}, {1, -1}, {2, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}},
1067     {{-2, -2}, {0, -4}, {2, -2}, {4, 0}, {2, 2}, {0, 4}, {-2, 2}, {-4, 0}},
1068     {{-4, -4}, {0, -8}, {4, -4}, {8, 0}, {4, 4}, {0, 8}, {-4, 4}, {-8, 0}},
1069     {{-8, -8}, {0, -16}, {8, -8}, {16, 0}, {8, 8}, {0, 16}, {-8, 8}, {-16, 0}},
1070     {{-16, -16}, {0, -32}, {16, -16}, {32, 0}, {16, 16}, {0, 32},
1071       {-16, 16}, {-32, 0}},
1072     {{-32, -32}, {0, -64}, {32, -32}, {64, 0}, {32, 32}, {0, 64},
1073       {-32, 32}, {-64, 0}},
1074     {{-64, -64}, {0, -128}, {64, -64}, {128, 0}, {64, 64}, {0, 128},
1075       {-64, 64}, {-128, 0}},
1076     {{-128, -128}, {0, -256}, {128, -128}, {256, 0}, {128, 128}, {0, 256},
1077       {-128, 128}, {-256, 0}},
1078     {{-256, -256}, {0, -512}, {256, -256}, {512, 0}, {256, 256}, {0, 512},
1079       {-256, 256}, {-512, 0}},
1080     {{-512, -512}, {0, -1024}, {512, -512}, {1024, 0}, {512, 512}, {0, 1024},
1081       {-512, 512}, {-1024, 0}},
1082   };
1083   return vp9_pattern_search_sad(x, ref_mv, search_param, sad_per_bit,
1084                                 do_init_search, sad_list, vfp, use_mvcost,
1085                                 center_mv, best_mv,
1086                                 bigdia_num_candidates, bigdia_candidates);
1087 }
1088
1089 int vp9_square_search(const MACROBLOCK *x,
1090                       MV *ref_mv,
1091                       int search_param,
1092                       int sad_per_bit,
1093                       int do_init_search,
1094                       int *sad_list,
1095                       const vp9_variance_fn_ptr_t *vfp,
1096                       int use_mvcost,
1097                       const MV *center_mv,
1098                       MV *best_mv) {
1099   // All scales have 8 closest points in square shape
1100   static const int square_num_candidates[MAX_PATTERN_SCALES] = {
1101     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
1102   };
1103   // Note that the largest candidate step at each scale is 2^scale
1104   static const MV square_candidates[MAX_PATTERN_SCALES]
1105                                    [MAX_PATTERN_CANDIDATES] = {
1106     {{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}},
1107     {{-2, -2}, {0, -2}, {2, -2}, {2, 0}, {2, 2}, {0, 2}, {-2, 2}, {-2, 0}},
1108     {{-4, -4}, {0, -4}, {4, -4}, {4, 0}, {4, 4}, {0, 4}, {-4, 4}, {-4, 0}},
1109     {{-8, -8}, {0, -8}, {8, -8}, {8, 0}, {8, 8}, {0, 8}, {-8, 8}, {-8, 0}},
1110     {{-16, -16}, {0, -16}, {16, -16}, {16, 0}, {16, 16}, {0, 16},
1111       {-16, 16}, {-16, 0}},
1112     {{-32, -32}, {0, -32}, {32, -32}, {32, 0}, {32, 32}, {0, 32},
1113       {-32, 32}, {-32, 0}},
1114     {{-64, -64}, {0, -64}, {64, -64}, {64, 0}, {64, 64}, {0, 64},
1115       {-64, 64}, {-64, 0}},
1116     {{-128, -128}, {0, -128}, {128, -128}, {128, 0}, {128, 128}, {0, 128},
1117       {-128, 128}, {-128, 0}},
1118     {{-256, -256}, {0, -256}, {256, -256}, {256, 0}, {256, 256}, {0, 256},
1119       {-256, 256}, {-256, 0}},
1120     {{-512, -512}, {0, -512}, {512, -512}, {512, 0}, {512, 512}, {0, 512},
1121       {-512, 512}, {-512, 0}},
1122     {{-1024, -1024}, {0, -1024}, {1024, -1024}, {1024, 0}, {1024, 1024},
1123       {0, 1024}, {-1024, 1024}, {-1024, 0}},
1124   };
1125   return vp9_pattern_search(x, ref_mv, search_param, sad_per_bit,
1126                             do_init_search, sad_list, vfp, use_mvcost,
1127                             center_mv, best_mv,
1128                             square_num_candidates, square_candidates);
1129 }
1130
1131 int vp9_fast_hex_search(const MACROBLOCK *x,
1132                         MV *ref_mv,
1133                         int search_param,
1134                         int sad_per_bit,
1135                         int do_init_search,  // must be zero for fast_hex
1136                         int *sad_list,
1137                         const vp9_variance_fn_ptr_t *vfp,
1138                         int use_mvcost,
1139                         const MV *center_mv,
1140                         MV *best_mv) {
1141   return vp9_hex_search(x, ref_mv, MAX(MAX_MVSEARCH_STEPS - 2, search_param),
1142                         sad_per_bit, do_init_search, sad_list, vfp, use_mvcost,
1143                         center_mv, best_mv);
1144 }
1145
1146 int vp9_fast_dia_search(const MACROBLOCK *x,
1147                         MV *ref_mv,
1148                         int search_param,
1149                         int sad_per_bit,
1150                         int do_init_search,
1151                         int *sad_list,
1152                         const vp9_variance_fn_ptr_t *vfp,
1153                         int use_mvcost,
1154                         const MV *center_mv,
1155                         MV *best_mv) {
1156   return vp9_bigdia_search(x, ref_mv, MAX(MAX_MVSEARCH_STEPS - 2, search_param),
1157                            sad_per_bit, do_init_search, sad_list, vfp,
1158                            use_mvcost, center_mv, best_mv);
1159 }
1160
1161 #undef CHECK_BETTER
1162
1163 int vp9_full_range_search_c(const MACROBLOCK *x,
1164                             const search_site_config *cfg,
1165                             MV *ref_mv, MV *best_mv,
1166                             int search_param, int sad_per_bit, int *num00,
1167                             const vp9_variance_fn_ptr_t *fn_ptr,
1168                             const MV *center_mv) {
1169   const MACROBLOCKD *const xd = &x->e_mbd;
1170   const struct buf_2d *const what = &x->plane[0].src;
1171   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1172   const int range = 64;
1173   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1174   unsigned int best_sad = INT_MAX;
1175   int r, c, i;
1176   int start_col, end_col, start_row, end_row;
1177
1178   // The cfg and search_param parameters are not used in this search variant
1179   (void)cfg;
1180   (void)search_param;
1181
1182   clamp_mv(ref_mv, x->mv_col_min, x->mv_col_max, x->mv_row_min, x->mv_row_max);
1183   *best_mv = *ref_mv;
1184   *num00 = 11;
1185   best_sad = fn_ptr->sdf(what->buf, what->stride,
1186                          get_buf_from_mv(in_what, ref_mv), in_what->stride) +
1187                  mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
1188   start_row = MAX(-range, x->mv_row_min - ref_mv->row);
1189   start_col = MAX(-range, x->mv_col_min - ref_mv->col);
1190   end_row = MIN(range, x->mv_row_max - ref_mv->row);
1191   end_col = MIN(range, x->mv_col_max - ref_mv->col);
1192
1193   for (r = start_row; r <= end_row; ++r) {
1194     for (c = start_col; c <= end_col; c += 4) {
1195       if (c + 3 <= end_col) {
1196         unsigned int sads[4];
1197         const uint8_t *addrs[4];
1198         for (i = 0; i < 4; ++i) {
1199           const MV mv = {ref_mv->row + r, ref_mv->col + c + i};
1200           addrs[i] = get_buf_from_mv(in_what, &mv);
1201         }
1202
1203         fn_ptr->sdx4df(what->buf, what->stride, addrs, in_what->stride, sads);
1204
1205         for (i = 0; i < 4; ++i) {
1206           if (sads[i] < best_sad) {
1207             const MV mv = {ref_mv->row + r, ref_mv->col + c + i};
1208             const unsigned int sad = sads[i] +
1209                 mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1210             if (sad < best_sad) {
1211               best_sad = sad;
1212               *best_mv = mv;
1213             }
1214           }
1215         }
1216       } else {
1217         for (i = 0; i < end_col - c; ++i) {
1218           const MV mv = {ref_mv->row + r, ref_mv->col + c + i};
1219           unsigned int sad = fn_ptr->sdf(what->buf, what->stride,
1220               get_buf_from_mv(in_what, &mv), in_what->stride);
1221           if (sad < best_sad) {
1222             sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1223             if (sad < best_sad) {
1224               best_sad = sad;
1225               *best_mv = mv;
1226             }
1227           }
1228         }
1229       }
1230     }
1231   }
1232
1233   return best_sad;
1234 }
1235
1236 int vp9_diamond_search_sad_c(const MACROBLOCK *x,
1237                              const search_site_config *cfg,
1238                              MV *ref_mv, MV *best_mv, int search_param,
1239                              int sad_per_bit, int *num00,
1240                              const vp9_variance_fn_ptr_t *fn_ptr,
1241                              const MV *center_mv) {
1242   int i, j, step;
1243
1244   const MACROBLOCKD *const xd = &x->e_mbd;
1245   uint8_t *what = x->plane[0].src.buf;
1246   const int what_stride = x->plane[0].src.stride;
1247   const uint8_t *in_what;
1248   const int in_what_stride = xd->plane[0].pre[0].stride;
1249   const uint8_t *best_address;
1250
1251   unsigned int bestsad = INT_MAX;
1252   int best_site = 0;
1253   int last_site = 0;
1254
1255   int ref_row;
1256   int ref_col;
1257
1258   // search_param determines the length of the initial step and hence the number
1259   // of iterations.
1260   // 0 = initial step (MAX_FIRST_STEP) pel
1261   // 1 = (MAX_FIRST_STEP/2) pel,
1262   // 2 = (MAX_FIRST_STEP/4) pel...
1263   const search_site *ss = &cfg->ss[search_param * cfg->searches_per_step];
1264   const int tot_steps = (cfg->ss_count / cfg->searches_per_step) - search_param;
1265
1266   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1267   clamp_mv(ref_mv, x->mv_col_min, x->mv_col_max, x->mv_row_min, x->mv_row_max);
1268   ref_row = ref_mv->row;
1269   ref_col = ref_mv->col;
1270   *num00 = 0;
1271   best_mv->row = ref_row;
1272   best_mv->col = ref_col;
1273
1274   // Work out the start point for the search
1275   in_what = xd->plane[0].pre[0].buf + ref_row * in_what_stride + ref_col;
1276   best_address = in_what;
1277
1278   // Check the starting position
1279   bestsad = fn_ptr->sdf(what, what_stride, in_what, in_what_stride)
1280                 + mvsad_err_cost(x, best_mv, &fcenter_mv, sad_per_bit);
1281
1282   i = 1;
1283
1284   for (step = 0; step < tot_steps; step++) {
1285     int all_in = 1, t;
1286
1287     // All_in is true if every one of the points we are checking are within
1288     // the bounds of the image.
1289     all_in &= ((best_mv->row + ss[i].mv.row) > x->mv_row_min);
1290     all_in &= ((best_mv->row + ss[i + 1].mv.row) < x->mv_row_max);
1291     all_in &= ((best_mv->col + ss[i + 2].mv.col) > x->mv_col_min);
1292     all_in &= ((best_mv->col + ss[i + 3].mv.col) < x->mv_col_max);
1293
1294     // If all the pixels are within the bounds we don't check whether the
1295     // search point is valid in this loop,  otherwise we check each point
1296     // for validity..
1297     if (all_in) {
1298       unsigned int sad_array[4];
1299
1300       for (j = 0; j < cfg->searches_per_step; j += 4) {
1301         unsigned char const *block_offset[4];
1302
1303         for (t = 0; t < 4; t++)
1304           block_offset[t] = ss[i + t].offset + best_address;
1305
1306         fn_ptr->sdx4df(what, what_stride, block_offset, in_what_stride,
1307                        sad_array);
1308
1309         for (t = 0; t < 4; t++, i++) {
1310           if (sad_array[t] < bestsad) {
1311             const MV this_mv = {best_mv->row + ss[i].mv.row,
1312                                 best_mv->col + ss[i].mv.col};
1313             sad_array[t] += mvsad_err_cost(x, &this_mv, &fcenter_mv,
1314                                            sad_per_bit);
1315             if (sad_array[t] < bestsad) {
1316               bestsad = sad_array[t];
1317               best_site = i;
1318             }
1319           }
1320         }
1321       }
1322     } else {
1323       for (j = 0; j < cfg->searches_per_step; j++) {
1324         // Trap illegal vectors
1325         const MV this_mv = {best_mv->row + ss[i].mv.row,
1326                             best_mv->col + ss[i].mv.col};
1327
1328         if (is_mv_in(x, &this_mv)) {
1329           const uint8_t *const check_here = ss[i].offset + best_address;
1330           unsigned int thissad = fn_ptr->sdf(what, what_stride, check_here,
1331                                              in_what_stride);
1332
1333           if (thissad < bestsad) {
1334             thissad += mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit);
1335             if (thissad < bestsad) {
1336               bestsad = thissad;
1337               best_site = i;
1338             }
1339           }
1340         }
1341         i++;
1342       }
1343     }
1344     if (best_site != last_site) {
1345       best_mv->row += ss[best_site].mv.row;
1346       best_mv->col += ss[best_site].mv.col;
1347       best_address += ss[best_site].offset;
1348       last_site = best_site;
1349 #if defined(NEW_DIAMOND_SEARCH)
1350       while (1) {
1351         const MV this_mv = {best_mv->row + ss[best_site].mv.row,
1352                             best_mv->col + ss[best_site].mv.col};
1353         if (is_mv_in(x, &this_mv)) {
1354           const uint8_t *const check_here = ss[best_site].offset + best_address;
1355           unsigned int thissad = fn_ptr->sdf(what, what_stride, check_here,
1356                                              in_what_stride);
1357           if (thissad < bestsad) {
1358             thissad += mvsad_err_cost(x, &this_mv, &fcenter_mv, sad_per_bit);
1359             if (thissad < bestsad) {
1360               bestsad = thissad;
1361               best_mv->row += ss[best_site].mv.row;
1362               best_mv->col += ss[best_site].mv.col;
1363               best_address += ss[best_site].offset;
1364               continue;
1365             }
1366           }
1367         }
1368         break;
1369       };
1370 #endif
1371     } else if (best_address == in_what) {
1372       (*num00)++;
1373     }
1374   }
1375   return bestsad;
1376 }
1377
1378 /* do_refine: If last step (1-away) of n-step search doesn't pick the center
1379               point as the best match, we will do a final 1-away diamond
1380               refining search  */
1381
1382 int vp9_full_pixel_diamond(const VP9_COMP *cpi, MACROBLOCK *x,
1383                            MV *mvp_full, int step_param,
1384                            int sadpb, int further_steps, int do_refine,
1385                            const vp9_variance_fn_ptr_t *fn_ptr,
1386                            const MV *ref_mv, MV *dst_mv) {
1387   MV temp_mv;
1388   int thissme, n, num00 = 0;
1389   int bestsme = cpi->diamond_search_sad(x, &cpi->ss_cfg, mvp_full, &temp_mv,
1390                                         step_param, sadpb, &n,
1391                                         fn_ptr, ref_mv);
1392   if (bestsme < INT_MAX)
1393     bestsme = vp9_get_mvpred_var(x, &temp_mv, ref_mv, fn_ptr, 1);
1394   *dst_mv = temp_mv;
1395
1396   // If there won't be more n-step search, check to see if refining search is
1397   // needed.
1398   if (n > further_steps)
1399     do_refine = 0;
1400
1401   while (n < further_steps) {
1402     ++n;
1403
1404     if (num00) {
1405       num00--;
1406     } else {
1407       thissme = cpi->diamond_search_sad(x, &cpi->ss_cfg, mvp_full, &temp_mv,
1408                                         step_param + n, sadpb, &num00,
1409                                         fn_ptr, ref_mv);
1410       if (thissme < INT_MAX)
1411         thissme = vp9_get_mvpred_var(x, &temp_mv, ref_mv, fn_ptr, 1);
1412
1413       // check to see if refining search is needed.
1414       if (num00 > further_steps - n)
1415         do_refine = 0;
1416
1417       if (thissme < bestsme) {
1418         bestsme = thissme;
1419         *dst_mv = temp_mv;
1420       }
1421     }
1422   }
1423
1424   // final 1-away diamond refining search
1425   if (do_refine) {
1426     const int search_range = 8;
1427     MV best_mv = *dst_mv;
1428     thissme = cpi->refining_search_sad(x, &best_mv, sadpb, search_range,
1429                                        fn_ptr, ref_mv);
1430     if (thissme < INT_MAX)
1431       thissme = vp9_get_mvpred_var(x, &best_mv, ref_mv, fn_ptr, 1);
1432     if (thissme < bestsme) {
1433       bestsme = thissme;
1434       *dst_mv = best_mv;
1435     }
1436   }
1437   return bestsme;
1438 }
1439
1440 int vp9_full_search_sad_c(const MACROBLOCK *x, const MV *ref_mv,
1441                           int sad_per_bit, int distance,
1442                           const vp9_variance_fn_ptr_t *fn_ptr,
1443                           const MV *center_mv, MV *best_mv) {
1444   int r, c;
1445   const MACROBLOCKD *const xd = &x->e_mbd;
1446   const struct buf_2d *const what = &x->plane[0].src;
1447   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1448   const int row_min = MAX(ref_mv->row - distance, x->mv_row_min);
1449   const int row_max = MIN(ref_mv->row + distance, x->mv_row_max);
1450   const int col_min = MAX(ref_mv->col - distance, x->mv_col_min);
1451   const int col_max = MIN(ref_mv->col + distance, x->mv_col_max);
1452   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1453   int best_sad = fn_ptr->sdf(what->buf, what->stride,
1454       get_buf_from_mv(in_what, ref_mv), in_what->stride) +
1455       mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
1456   *best_mv = *ref_mv;
1457
1458   for (r = row_min; r < row_max; ++r) {
1459     for (c = col_min; c < col_max; ++c) {
1460       const MV mv = {r, c};
1461       const int sad = fn_ptr->sdf(what->buf, what->stride,
1462           get_buf_from_mv(in_what, &mv), in_what->stride) +
1463               mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1464       if (sad < best_sad) {
1465         best_sad = sad;
1466         *best_mv = mv;
1467       }
1468     }
1469   }
1470   return best_sad;
1471 }
1472
1473 int vp9_full_search_sadx3(const MACROBLOCK *x, const MV *ref_mv,
1474                           int sad_per_bit, int distance,
1475                           const vp9_variance_fn_ptr_t *fn_ptr,
1476                           const MV *center_mv, MV *best_mv) {
1477   int r;
1478   const MACROBLOCKD *const xd = &x->e_mbd;
1479   const struct buf_2d *const what = &x->plane[0].src;
1480   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1481   const int row_min = MAX(ref_mv->row - distance, x->mv_row_min);
1482   const int row_max = MIN(ref_mv->row + distance, x->mv_row_max);
1483   const int col_min = MAX(ref_mv->col - distance, x->mv_col_min);
1484   const int col_max = MIN(ref_mv->col + distance, x->mv_col_max);
1485   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1486   unsigned int best_sad = fn_ptr->sdf(what->buf, what->stride,
1487       get_buf_from_mv(in_what, ref_mv), in_what->stride) +
1488       mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
1489   *best_mv = *ref_mv;
1490
1491   for (r = row_min; r < row_max; ++r) {
1492     int c = col_min;
1493     const uint8_t *check_here = &in_what->buf[r * in_what->stride + c];
1494
1495     if (fn_ptr->sdx3f != NULL) {
1496       while ((c + 2) < col_max) {
1497         int i;
1498         unsigned int sads[3];
1499
1500         fn_ptr->sdx3f(what->buf, what->stride, check_here, in_what->stride,
1501                       sads);
1502
1503         for (i = 0; i < 3; ++i) {
1504           unsigned int sad = sads[i];
1505           if (sad < best_sad) {
1506             const MV mv = {r, c};
1507             sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1508             if (sad < best_sad) {
1509               best_sad = sad;
1510               *best_mv = mv;
1511             }
1512           }
1513           ++check_here;
1514           ++c;
1515         }
1516       }
1517     }
1518
1519     while (c < col_max) {
1520       unsigned int sad = fn_ptr->sdf(what->buf, what->stride,
1521                                      check_here, in_what->stride);
1522       if (sad < best_sad) {
1523         const MV mv = {r, c};
1524         sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1525         if (sad < best_sad) {
1526           best_sad = sad;
1527           *best_mv = mv;
1528         }
1529       }
1530       ++check_here;
1531       ++c;
1532     }
1533   }
1534
1535   return best_sad;
1536 }
1537
1538 int vp9_full_search_sadx8(const MACROBLOCK *x, const MV *ref_mv,
1539                           int sad_per_bit, int distance,
1540                           const vp9_variance_fn_ptr_t *fn_ptr,
1541                           const MV *center_mv, MV *best_mv) {
1542   int r;
1543   const MACROBLOCKD *const xd = &x->e_mbd;
1544   const struct buf_2d *const what = &x->plane[0].src;
1545   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1546   const int row_min = MAX(ref_mv->row - distance, x->mv_row_min);
1547   const int row_max = MIN(ref_mv->row + distance, x->mv_row_max);
1548   const int col_min = MAX(ref_mv->col - distance, x->mv_col_min);
1549   const int col_max = MIN(ref_mv->col + distance, x->mv_col_max);
1550   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1551   unsigned int best_sad = fn_ptr->sdf(what->buf, what->stride,
1552       get_buf_from_mv(in_what, ref_mv), in_what->stride) +
1553       mvsad_err_cost(x, ref_mv, &fcenter_mv, sad_per_bit);
1554   *best_mv = *ref_mv;
1555
1556   for (r = row_min; r < row_max; ++r) {
1557     int c = col_min;
1558     const uint8_t *check_here = &in_what->buf[r * in_what->stride + c];
1559
1560     if (fn_ptr->sdx8f != NULL) {
1561       while ((c + 7) < col_max) {
1562         int i;
1563         unsigned int sads[8];
1564
1565         fn_ptr->sdx8f(what->buf, what->stride, check_here, in_what->stride,
1566                       sads);
1567
1568         for (i = 0; i < 8; ++i) {
1569           unsigned int sad = sads[i];
1570           if (sad < best_sad) {
1571             const MV mv = {r, c};
1572             sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1573             if (sad < best_sad) {
1574               best_sad = sad;
1575               *best_mv = mv;
1576             }
1577           }
1578           ++check_here;
1579           ++c;
1580         }
1581       }
1582     }
1583
1584     if (fn_ptr->sdx3f != NULL) {
1585       while ((c + 2) < col_max) {
1586         int i;
1587         unsigned int sads[3];
1588
1589         fn_ptr->sdx3f(what->buf, what->stride, check_here, in_what->stride,
1590                       sads);
1591
1592         for (i = 0; i < 3; ++i) {
1593           unsigned int sad = sads[i];
1594           if (sad < best_sad) {
1595             const MV mv = {r, c};
1596             sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1597             if (sad < best_sad) {
1598               best_sad = sad;
1599               *best_mv = mv;
1600             }
1601           }
1602           ++check_here;
1603           ++c;
1604         }
1605       }
1606     }
1607
1608     while (c < col_max) {
1609       unsigned int sad = fn_ptr->sdf(what->buf, what->stride,
1610                                      check_here, in_what->stride);
1611       if (sad < best_sad) {
1612         const MV mv = {r, c};
1613         sad += mvsad_err_cost(x, &mv, &fcenter_mv, sad_per_bit);
1614         if (sad < best_sad) {
1615           best_sad = sad;
1616           *best_mv = mv;
1617         }
1618       }
1619       ++check_here;
1620       ++c;
1621     }
1622   }
1623
1624   return best_sad;
1625 }
1626
1627 int vp9_refining_search_sad_c(const MACROBLOCK *x,
1628                               MV *ref_mv, int error_per_bit,
1629                               int search_range,
1630                               const vp9_variance_fn_ptr_t *fn_ptr,
1631                               const MV *center_mv) {
1632   const MACROBLOCKD *const xd = &x->e_mbd;
1633   const MV neighbors[4] = {{ -1, 0}, {0, -1}, {0, 1}, {1, 0}};
1634   const struct buf_2d *const what = &x->plane[0].src;
1635   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1636   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1637   const uint8_t *best_address = get_buf_from_mv(in_what, ref_mv);
1638   unsigned int best_sad = fn_ptr->sdf(what->buf, what->stride, best_address,
1639                                     in_what->stride) +
1640       mvsad_err_cost(x, ref_mv, &fcenter_mv, error_per_bit);
1641   int i, j;
1642
1643   for (i = 0; i < search_range; i++) {
1644     int best_site = -1;
1645     const int all_in = ((ref_mv->row - 1) > x->mv_row_min) &
1646                        ((ref_mv->row + 1) < x->mv_row_max) &
1647                        ((ref_mv->col - 1) > x->mv_col_min) &
1648                        ((ref_mv->col + 1) < x->mv_col_max);
1649
1650     if (all_in) {
1651       unsigned int sads[4];
1652       const uint8_t *const positions[4] = {
1653         best_address - in_what->stride,
1654         best_address - 1,
1655         best_address + 1,
1656         best_address + in_what->stride
1657       };
1658
1659       fn_ptr->sdx4df(what->buf, what->stride, positions, in_what->stride, sads);
1660
1661       for (j = 0; j < 4; ++j) {
1662         if (sads[j] < best_sad) {
1663           const MV mv = {ref_mv->row + neighbors[j].row,
1664                          ref_mv->col + neighbors[j].col};
1665           sads[j] += mvsad_err_cost(x, &mv, &fcenter_mv, error_per_bit);
1666           if (sads[j] < best_sad) {
1667             best_sad = sads[j];
1668             best_site = j;
1669           }
1670         }
1671       }
1672     } else {
1673       for (j = 0; j < 4; ++j) {
1674         const MV mv = {ref_mv->row + neighbors[j].row,
1675                        ref_mv->col + neighbors[j].col};
1676
1677         if (is_mv_in(x, &mv)) {
1678           unsigned int sad = fn_ptr->sdf(what->buf, what->stride,
1679                                          get_buf_from_mv(in_what, &mv),
1680                                          in_what->stride);
1681           if (sad < best_sad) {
1682             sad += mvsad_err_cost(x, &mv, &fcenter_mv, error_per_bit);
1683             if (sad < best_sad) {
1684               best_sad = sad;
1685               best_site = j;
1686             }
1687           }
1688         }
1689       }
1690     }
1691
1692     if (best_site == -1) {
1693       break;
1694     } else {
1695       ref_mv->row += neighbors[best_site].row;
1696       ref_mv->col += neighbors[best_site].col;
1697       best_address = get_buf_from_mv(in_what, ref_mv);
1698     }
1699   }
1700
1701   return best_sad;
1702 }
1703
1704 // This function is called when we do joint motion search in comp_inter_inter
1705 // mode.
1706 int vp9_refining_search_8p_c(const MACROBLOCK *x,
1707                              MV *ref_mv, int error_per_bit,
1708                              int search_range,
1709                              const vp9_variance_fn_ptr_t *fn_ptr,
1710                              const MV *center_mv,
1711                              const uint8_t *second_pred) {
1712   const MV neighbors[8] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0},
1713                            {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
1714   const MACROBLOCKD *const xd = &x->e_mbd;
1715   const struct buf_2d *const what = &x->plane[0].src;
1716   const struct buf_2d *const in_what = &xd->plane[0].pre[0];
1717   const MV fcenter_mv = {center_mv->row >> 3, center_mv->col >> 3};
1718   unsigned int best_sad = fn_ptr->sdaf(what->buf, what->stride,
1719       get_buf_from_mv(in_what, ref_mv), in_what->stride, second_pred) +
1720       mvsad_err_cost(x, ref_mv, &fcenter_mv, error_per_bit);
1721   int i, j;
1722
1723   for (i = 0; i < search_range; ++i) {
1724     int best_site = -1;
1725
1726     for (j = 0; j < 8; ++j) {
1727       const MV mv = {ref_mv->row + neighbors[j].row,
1728                      ref_mv->col + neighbors[j].col};
1729
1730       if (is_mv_in(x, &mv)) {
1731         unsigned int sad = fn_ptr->sdaf(what->buf, what->stride,
1732             get_buf_from_mv(in_what, &mv), in_what->stride, second_pred);
1733         if (sad < best_sad) {
1734           sad += mvsad_err_cost(x, &mv, &fcenter_mv, error_per_bit);
1735           if (sad < best_sad) {
1736             best_sad = sad;
1737             best_site = j;
1738           }
1739         }
1740       }
1741     }
1742
1743     if (best_site == -1) {
1744       break;
1745     } else {
1746       ref_mv->row += neighbors[best_site].row;
1747       ref_mv->col += neighbors[best_site].col;
1748     }
1749   }
1750   return best_sad;
1751 }
1752
1753 int vp9_full_pixel_search(VP9_COMP *cpi, MACROBLOCK *x,
1754                           BLOCK_SIZE bsize, MV *mvp_full,
1755                           int step_param, int error_per_bit,
1756                           int *sad_list,
1757                           const MV *ref_mv, MV *tmp_mv,
1758                           int var_max, int rd) {
1759   const SPEED_FEATURES *const sf = &cpi->sf;
1760   const SEARCH_METHODS method = sf->mv.search_method;
1761   vp9_variance_fn_ptr_t *fn_ptr = &cpi->fn_ptr[bsize];
1762   int var = 0;
1763   if (sad_list) {
1764     sad_list[0] = INT_MAX;
1765     sad_list[1] = INT_MAX;
1766     sad_list[2] = INT_MAX;
1767     sad_list[3] = INT_MAX;
1768     sad_list[4] = INT_MAX;
1769   }
1770
1771   switch (method) {
1772     case FAST_DIAMOND:
1773       var = vp9_fast_dia_search(x, mvp_full, step_param, error_per_bit, 0,
1774                                 sad_list, fn_ptr, 1, ref_mv, tmp_mv);
1775       break;
1776     case FAST_HEX:
1777       var = vp9_fast_hex_search(x, mvp_full, step_param, error_per_bit, 0,
1778                                 sad_list, fn_ptr, 1, ref_mv, tmp_mv);
1779       break;
1780     case HEX:
1781       var = vp9_hex_search(x, mvp_full, step_param, error_per_bit, 1,
1782                            sad_list, fn_ptr, 1, ref_mv, tmp_mv);
1783       break;
1784     case SQUARE:
1785       var = vp9_square_search(x, mvp_full, step_param, error_per_bit, 1,
1786                               sad_list, fn_ptr, 1, ref_mv, tmp_mv);
1787       break;
1788     case BIGDIA:
1789       var = vp9_bigdia_search(x, mvp_full, step_param, error_per_bit, 1,
1790                               sad_list, fn_ptr, 1, ref_mv, tmp_mv);
1791       break;
1792     case NSTEP:
1793       var = vp9_full_pixel_diamond(cpi, x, mvp_full, step_param, error_per_bit,
1794                                    MAX_MVSEARCH_STEPS - 1 - step_param,
1795                                    1, fn_ptr, ref_mv, tmp_mv);
1796       break;
1797     default:
1798       assert(!"Invalid search method.");
1799   }
1800
1801   if (method != NSTEP && rd && var < var_max)
1802     var = vp9_get_mvpred_var(x, tmp_mv, ref_mv, fn_ptr, 1);
1803
1804   return var;
1805 }