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