Quelle  mcomp.c   Sprache: C

/*
 * Copyright (c) 2016, Alliance for Open Media. All rights reserved.
 *
 * This source code is subject to the terms of the BSD 2 Clause License and
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
 * was not distributed with this source code in the LICENSE file, you can
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
 * Media Patent License 1.0 was not distributed with this source code in the
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
 */

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>

#include "config/aom_config.h"
#include "config/aom_dsp_rtcd.h"

#include "aom_dsp/aom_dsp_common.h"
#include "aom_mem/aom_mem.h"
#include "aom_ports/mem.h"

#include "av1/common/av1_common_int.h"
#include "av1/common/common.h"
#include "av1/common/filter.h"
#include "av1/common/mvref_common.h"
#include "av1/common/reconinter.h"

#include "av1/encoder/encoder.h"
#include "av1/encoder/encodemv.h"
#include "av1/encoder/mcomp.h"
#include "av1/encoder/rdopt.h"
#include "av1/encoder/reconinter_enc.h"

static inline void init_mv_cost_params(MV_COST_PARAMS *mv_cost_params,
                                       const MvCosts *mv_costs,
                                       const MV *ref_mv, int errorperbit,
                                       int sadperbit) {
  mv_cost_params->ref_mv = ref_mv;
  mv_cost_params->full_ref_mv = get_fullmv_from_mv(ref_mv);
  mv_cost_params->mv_cost_type = MV_COST_ENTROPY;
  mv_cost_params->error_per_bit = errorperbit;
  mv_cost_params->sad_per_bit = sadperbit;
  // For allintra encoding mode, 'mv_costs' is not allocated. Hence, the
  // population of mvjcost and mvcost are avoided. In case of IntraBC, these
  // values are populated from 'dv_costs' in av1_set_ms_to_intra_mode().
  if (mv_costs != NULL) {
    mv_cost_params->mvjcost = mv_costs->nmv_joint_cost;
    mv_cost_params->mvcost[0] = mv_costs->mv_cost_stack[0];
    mv_cost_params->mvcost[1] = mv_costs->mv_cost_stack[1];
  }
}

static inline void init_ms_buffers(MSBuffers *ms_buffers, const MACROBLOCK *x) {
  ms_buffers->ref = &x->e_mbd.plane[0].pre[0];
  ms_buffers->src = &x->plane[0].src;

  av1_set_ms_compound_refs(ms_buffers, NULL, NULL, 0, 0);

  ms_buffers->wsrc = x->obmc_buffer.wsrc;
  ms_buffers->obmc_mask = x->obmc_buffer.mask;
}

void av1_init_obmc_buffer(OBMCBuffer *obmc_buffer) {
  obmc_buffer->wsrc = NULL;
  obmc_buffer->mask = NULL;
  obmc_buffer->above_pred = NULL;
  obmc_buffer->left_pred = NULL;
}

void av1_make_default_fullpel_ms_params(
    FULLPEL_MOTION_SEARCH_PARAMS *ms_params, const struct AV1_COMP *cpi,
    MACROBLOCK *x, BLOCK_SIZE bsize, const MV *ref_mv, FULLPEL_MV start_mv,
    const search_site_config search_sites[NUM_DISTINCT_SEARCH_METHODS],
    SEARCH_METHODS search_method, int fine_search_interval) {
  const MV_SPEED_FEATURES *mv_sf = &cpi->sf.mv_sf;
  const int is_key_frame =
      cpi->ppi->gf_group.update_type[cpi->gf_frame_index] == KF_UPDATE;

  // High level params
  ms_params->bsize = bsize;
  ms_params->vfp = &cpi->ppi->fn_ptr[bsize];

  init_ms_buffers(&ms_params->ms_buffers, x);

  av1_set_mv_search_method(ms_params, search_sites, search_method);

  ms_params->mesh_patterns[0] = mv_sf->mesh_patterns;
  ms_params->mesh_patterns[1] = mv_sf->intrabc_mesh_patterns;
  ms_params->force_mesh_thresh = mv_sf->exhaustive_searches_thresh;
  ms_params->prune_mesh_search =
      (cpi->sf.mv_sf.prune_mesh_search == PRUNE_MESH_SEARCH_LVL_2) ? 1 : 0;
  ms_params->mesh_search_mv_diff_threshold = 4;
  ms_params->run_mesh_search = 0;
  ms_params->fine_search_interval = fine_search_interval;

  ms_params->is_intra_mode = 0;

  ms_params->fast_obmc_search = mv_sf->obmc_full_pixel_search_level;

  ms_params->mv_limits = x->mv_limits;
  av1_set_mv_search_range(&ms_params->mv_limits, ref_mv);

  // Mvcost params
  init_mv_cost_params(&ms_params->mv_cost_params, x->mv_costs, ref_mv,
                      x->errorperbit, x->sadperbit);

  ms_params->sdf = ms_params->vfp->sdf;
  ms_params->sdx4df = ms_params->vfp->sdx4df;
  ms_params->sdx3df = ms_params->vfp->sdx3df;

  if (mv_sf->use_downsampled_sad == 2 && block_size_high[bsize] >= 16) {
    assert(ms_params->vfp->sdsf != NULL);
    ms_params->sdf = ms_params->vfp->sdsf;
    assert(ms_params->vfp->sdsx4df != NULL);
    ms_params->sdx4df = ms_params->vfp->sdsx4df;
    // Skip version of sadx3 is not available yet
    ms_params->sdx3df = ms_params->vfp->sdsx4df;
  } else if (mv_sf->use_downsampled_sad == 1 && block_size_high[bsize] >= 16 &&
             !is_key_frame) {
    FULLPEL_MV start_mv_clamped = start_mv;
    // adjust start_mv to make sure it is within MV range
    clamp_fullmv(&start_mv_clamped, &ms_params->mv_limits);

    const struct buf_2d *const ref = ms_params->ms_buffers.ref;
    const int ref_stride = ref->stride;
    const uint8_t *best_address = get_buf_from_fullmv(ref, &start_mv_clamped);
    const struct buf_2d *const src = ms_params->ms_buffers.src;
    const uint8_t *src_buf = src->buf;
    const int src_stride = src->stride;

    unsigned int start_mv_sad_even_rows, start_mv_sad_odd_rows;
    assert(ms_params->vfp->sdsf != NULL);
    start_mv_sad_even_rows =
        ms_params->vfp->sdsf(src_buf, src_stride, best_address, ref_stride);
    start_mv_sad_odd_rows =
        ms_params->vfp->sdsf(src_buf + src_stride, src_stride,
                             best_address + ref_stride, ref_stride);

    // If the absolute SAD difference computed between the pred-to-src of even
    // and odd rows is small, skip every other row in sad computation.
    const int odd_to_even_diff_sad =
        abs((int)start_mv_sad_even_rows - (int)start_mv_sad_odd_rows);
    const int mult_thresh = 4;
    if (odd_to_even_diff_sad * mult_thresh < (int)start_mv_sad_even_rows) {
      ms_params->sdf = ms_params->vfp->sdsf;
      assert(ms_params->vfp->sdsx4df != NULL);
      ms_params->sdx4df = ms_params->vfp->sdsx4df;
      ms_params->sdx3df = ms_params->vfp->sdsx4df;
    }
  }
}

void av1_set_ms_to_intra_mode(FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                              const IntraBCMVCosts *dv_costs) {
  ms_params->is_intra_mode = 1;

  MV_COST_PARAMS *mv_cost_params = &ms_params->mv_cost_params;

  mv_cost_params->mvjcost = dv_costs->joint_mv;
  mv_cost_params->mvcost[0] = dv_costs->dv_costs[0];
  mv_cost_params->mvcost[1] = dv_costs->dv_costs[1];
}

void av1_make_default_subpel_ms_params(SUBPEL_MOTION_SEARCH_PARAMS *ms_params,
                                       const struct AV1_COMP *cpi,
                                       const MACROBLOCK *x, BLOCK_SIZE bsize,
                                       const MV *ref_mv, const int *cost_list) {
  const AV1_COMMON *cm = &cpi->common;
  // High level params
  ms_params->allow_hp = cm->features.allow_high_precision_mv;
  ms_params->forced_stop = cpi->sf.mv_sf.subpel_force_stop;
  ms_params->iters_per_step = cpi->sf.mv_sf.subpel_iters_per_step;
  ms_params->cost_list = cond_cost_list_const(cpi, cost_list);

  av1_set_subpel_mv_search_range(&ms_params->mv_limits, &x->mv_limits, ref_mv);

  // Mvcost params
  init_mv_cost_params(&ms_params->mv_cost_params, x->mv_costs, ref_mv,
                      x->errorperbit, x->sadperbit);

  // Subpel variance params
  ms_params->var_params.vfp = &cpi->ppi->fn_ptr[bsize];
  ms_params->var_params.subpel_search_type =
      cpi->sf.mv_sf.use_accurate_subpel_search;
  ms_params->var_params.w = block_size_wide[bsize];
  ms_params->var_params.h = block_size_high[bsize];

  // Ref and src buffers
  MSBuffers *ms_buffers = &ms_params->var_params.ms_buffers;
  init_ms_buffers(ms_buffers, x);
}

void av1_set_mv_search_range(FullMvLimits *mv_limits, const MV *mv) {
  // Calculate the outermost full-pixel MVs which are inside the limits set by
  // av1_set_subpel_mv_search_range().
  //
  // The subpel limits are simply mv->col +/- 8*MAX_FULL_PEL_VAL, and similar
  // for mv->row. We can then divide by 8 to find the fullpel MV limits. But
  // we have to be careful about the rounding. We want these bounds to be
  // at least as tight as the subpel limits, which means that we must round
  // the minimum values up and the maximum values down when dividing.
  int col_min = ((mv->col + 7) >> 3) - MAX_FULL_PEL_VAL;
  int row_min = ((mv->row + 7) >> 3) - MAX_FULL_PEL_VAL;
  int col_max = (mv->col >> 3) + MAX_FULL_PEL_VAL;
  int row_max = (mv->row >> 3) + MAX_FULL_PEL_VAL;

  col_min = AOMMAX(col_min, (MV_LOW >> 3) + 1);
  row_min = AOMMAX(row_min, (MV_LOW >> 3) + 1);
  col_max = AOMMIN(col_max, (MV_UPP >> 3) - 1);
  row_max = AOMMIN(row_max, (MV_UPP >> 3) - 1);

  // Get intersection of UMV window and valid MV window to reduce # of checks
  // in diamond search.
  if (mv_limits->col_min < col_min) mv_limits->col_min = col_min;
  if (mv_limits->col_max > col_max) mv_limits->col_max = col_max;
  if (mv_limits->row_min < row_min) mv_limits->row_min = row_min;
  if (mv_limits->row_max > row_max) mv_limits->row_max = row_max;

  mv_limits->col_max = AOMMAX(mv_limits->col_min, mv_limits->col_max);
  mv_limits->row_max = AOMMAX(mv_limits->row_min, mv_limits->row_max);
}

int av1_init_search_range(int size) {
  int sr = 0;
  // Minimum search size no matter what the passed in value.
  size = AOMMAX(16, size);

  while ((size << sr) < MAX_FULL_PEL_VAL) sr++;

  sr = AOMMIN(sr, MAX_MVSEARCH_STEPS - 2);
  return sr;
}

// ============================================================================
//  Cost of motion vectors
// ============================================================================
// TODO(any): Adaptively adjust the regularization strength based on image size
// and motion activity instead of using hard-coded values. It seems like we
// roughly half the lambda for each increase in resolution
// These are multiplier used to perform regularization in motion compensation
// when x->mv_cost_type is set to MV_COST_L1.
// LOWRES
#define SSE_LAMBDA_LOWRES 2   // Used by mv_cost_err_fn
#define SAD_LAMBDA_LOWRES 32  // Used by mvsad_err_cost during full pixel search
// MIDRES
#define SSE_LAMBDA_MIDRES 0   // Used by mv_cost_err_fn
#define SAD_LAMBDA_MIDRES 15  // Used by mvsad_err_cost during full pixel search
// HDRES
#define SSE_LAMBDA_HDRES 1  // Used by mv_cost_err_fn
#define SAD_LAMBDA_HDRES 8  // Used by mvsad_err_cost during full pixel search

// Returns the rate of encoding the current motion vector based on the
// joint_cost and comp_cost. joint_costs covers the cost of transmitting
// JOINT_MV, and comp_cost covers the cost of transmitting the actual motion
// vector.
static inline int mv_cost(const MV *mv, const int *joint_cost,
                          const int *const comp_cost[2]) {
  return joint_cost[av1_get_mv_joint(mv)] + comp_cost[0][mv->row] +
         comp_cost[1][mv->col];
}

#define CONVERT_TO_CONST_MVCOST(ptr) ((const int *const *)(ptr))
// Returns the cost of encoding the motion vector diff := *mv - *ref. The cost
// is defined as the rate required to encode diff * weight, rounded to the
// nearest 2 ** 7.
// This is NOT used during motion compensation.
int av1_mv_bit_cost(const MV *mv, const MV *ref_mv, const int *mvjcost,
                    int *const mvcost[2], int weight) {
  const MV diff = { mv->row - ref_mv->row, mv->col - ref_mv->col };
  return ROUND_POWER_OF_TWO(
      mv_cost(&diff, mvjcost, CONVERT_TO_CONST_MVCOST(mvcost)) * weight, 7);
}

// Returns the cost of using the current mv during the motion search. This is
// used when var is used as the error metric.
#define PIXEL_TRANSFORM_ERROR_SCALE 4
static inline int mv_err_cost(const MV *mv, const MV *ref_mv,
                              const int *mvjcost, const int *const mvcost[2],
                              int error_per_bit, MV_COST_TYPE mv_cost_type) {
  const MV diff = { mv->row - ref_mv->row, mv->col - ref_mv->col };
  const MV abs_diff = { abs(diff.row), abs(diff.col) };

  switch (mv_cost_type) {
    case MV_COST_ENTROPY:
      if (mvcost) {
        return (int)ROUND_POWER_OF_TWO_64(
            (int64_t)mv_cost(&diff, mvjcost, mvcost) * error_per_bit,
            RDDIV_BITS + AV1_PROB_COST_SHIFT - RD_EPB_SHIFT +
                PIXEL_TRANSFORM_ERROR_SCALE);
      }
      return 0;
    case MV_COST_L1_LOWRES:
      return (SSE_LAMBDA_LOWRES * (abs_diff.row + abs_diff.col)) >> 3;
    case MV_COST_L1_MIDRES:
      return (SSE_LAMBDA_MIDRES * (abs_diff.row + abs_diff.col)) >> 3;
    case MV_COST_L1_HDRES:
      return (SSE_LAMBDA_HDRES * (abs_diff.row + abs_diff.col)) >> 3;
    case MV_COST_NONE: return 0;
    default: assert(0 && "Invalid rd_cost_type"); return 0;
  }
}

static inline int mv_err_cost_(const MV *mv,
                               const MV_COST_PARAMS *mv_cost_params) {
  if (mv_cost_params->mv_cost_type == MV_COST_NONE) {
    return 0;
  }
  return mv_err_cost(mv, mv_cost_params->ref_mv, mv_cost_params->mvjcost,
                     mv_cost_params->mvcost, mv_cost_params->error_per_bit,
                     mv_cost_params->mv_cost_type);
}

// Returns the cost of using the current mv during the motion search. This is
// only used during full pixel motion search when sad is used as the error
// metric
static inline int mvsad_err_cost(const FULLPEL_MV *mv, const FULLPEL_MV *ref_mv,
                                 const int *mvjcost, const int *const mvcost[2],
                                 int sad_per_bit, MV_COST_TYPE mv_cost_type) {
  const MV diff = { GET_MV_SUBPEL(mv->row - ref_mv->row),
                    GET_MV_SUBPEL(mv->col - ref_mv->col) };

  switch (mv_cost_type) {
    case MV_COST_ENTROPY:
      return ROUND_POWER_OF_TWO(
          (unsigned)mv_cost(&diff, mvjcost, CONVERT_TO_CONST_MVCOST(mvcost)) *
              sad_per_bit,
          AV1_PROB_COST_SHIFT);
    case MV_COST_L1_LOWRES:
      return (SAD_LAMBDA_LOWRES * (abs(diff.row) + abs(diff.col))) >> 3;
    case MV_COST_L1_MIDRES:
      return (SAD_LAMBDA_MIDRES * (abs(diff.row) + abs(diff.col))) >> 3;
    case MV_COST_L1_HDRES:
      return (SAD_LAMBDA_HDRES * (abs(diff.row) + abs(diff.col))) >> 3;
    case MV_COST_NONE: return 0;
    default: assert(0 && "Invalid rd_cost_type"); return 0;
  }
}

static inline int mvsad_err_cost_(const FULLPEL_MV *mv,
                                  const MV_COST_PARAMS *mv_cost_params) {
  return mvsad_err_cost(mv, &mv_cost_params->full_ref_mv,
                        mv_cost_params->mvjcost, mv_cost_params->mvcost,
                        mv_cost_params->sad_per_bit,
                        mv_cost_params->mv_cost_type);
}

// =============================================================================
//  Fullpixel Motion Search: Translational
// =============================================================================
#define MAX_PATTERN_SCALES 11
#define MAX_PATTERN_CANDIDATES 8  // max number of candidates per scale
#define PATTERN_CANDIDATES_REF 3  // number of refinement candidates

// Search site initialization for DIAMOND / CLAMPED_DIAMOND search methods.
// level = 0: DIAMOND, level = 1: CLAMPED_DIAMOND.
static void init_dsmotion_compensation(search_site_config *cfg, int stride,
                                       int level) {
  int num_search_steps = 0;
  int stage_index = MAX_MVSEARCH_STEPS - 1;

  cfg->site[stage_index][0].mv.col = cfg->site[stage_index][0].mv.row = 0;
  cfg->site[stage_index][0].offset = 0;
  cfg->stride = stride;

  // Choose the initial step size depending on level.
  const int first_step = (level > 0) ? (MAX_FIRST_STEP / 4) : MAX_FIRST_STEP;

  for (int radius = first_step; radius > 0;) {
    int num_search_pts = 8;

    const FULLPEL_MV search_site_mvs[13] = {
      { 0, 0 },           { -radius, 0 },      { radius, 0 },
      { 0, -radius },     { 0, radius },       { -radius, -radius },
      { radius, radius }, { -radius, radius }, { radius, -radius },
    };

    int i;
    for (i = 0; i <= num_search_pts; ++i) {
      search_site *const site = &cfg->site[stage_index][i];
      site->mv = search_site_mvs[i];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    cfg->searches_per_step[stage_index] = num_search_pts;
    cfg->radius[stage_index] = radius;
    // Update the search radius based on level.
    if (!level || ((stage_index < 9) && level)) radius /= 2;
    --stage_index;
    ++num_search_steps;
  }
  cfg->num_search_steps = num_search_steps;
}

void av1_init_motion_fpf(search_site_config *cfg, int stride) {
  int num_search_steps = 0;
  int stage_index = MAX_MVSEARCH_STEPS - 1;

  cfg->site[stage_index][0].mv.col = cfg->site[stage_index][0].mv.row = 0;
  cfg->site[stage_index][0].offset = 0;
  cfg->stride = stride;

  for (int radius = MAX_FIRST_STEP; radius > 0; radius /= 2) {
    // Generate offsets for 8 search sites per step.
    int tan_radius = AOMMAX((int)(0.41 * radius), 1);
    int num_search_pts = 12;
    if (radius == 1) num_search_pts = 8;

    const FULLPEL_MV search_site_mvs[13] = {
      { 0, 0 },
      { -radius, 0 },
      { radius, 0 },
      { 0, -radius },
      { 0, radius },
      { -radius, -tan_radius },
      { radius, tan_radius },
      { -tan_radius, radius },
      { tan_radius, -radius },
      { -radius, tan_radius },
      { radius, -tan_radius },
      { tan_radius, radius },
      { -tan_radius, -radius },
    };

    int i;
    for (i = 0; i <= num_search_pts; ++i) {
      search_site *const site = &cfg->site[stage_index][i];
      site->mv = search_site_mvs[i];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    cfg->searches_per_step[stage_index] = num_search_pts;
    cfg->radius[stage_index] = radius;
    --stage_index;
    ++num_search_steps;
  }
  cfg->num_search_steps = num_search_steps;
}

// Search site initialization for NSTEP / NSTEP_8PT search methods.
// level = 0: NSTEP, level = 1: NSTEP_8PT.
static void init_motion_compensation_nstep(search_site_config *cfg, int stride,
                                           int level) {
  int num_search_steps = 0;
  int stage_index = 0;
  cfg->stride = stride;
  int radius = 1;
  const int num_stages = (level > 0) ? 16 : 15;
  for (stage_index = 0; stage_index < num_stages; ++stage_index) {
    int tan_radius = AOMMAX((int)(0.41 * radius), 1);
    int num_search_pts = 12;
    if ((radius <= 5) || (level > 0)) {
      tan_radius = radius;
      num_search_pts = 8;
    }
    const FULLPEL_MV search_site_mvs[13] = {
      { 0, 0 },
      { -radius, 0 },
      { radius, 0 },
      { 0, -radius },
      { 0, radius },
      { -radius, -tan_radius },
      { radius, tan_radius },
      { -tan_radius, radius },
      { tan_radius, -radius },
      { -radius, tan_radius },
      { radius, -tan_radius },
      { tan_radius, radius },
      { -tan_radius, -radius },
    };

    for (int i = 0; i <= num_search_pts; ++i) {
      search_site *const site = &cfg->site[stage_index][i];
      site->mv = search_site_mvs[i];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    cfg->searches_per_step[stage_index] = num_search_pts;
    cfg->radius[stage_index] = radius;
    ++num_search_steps;
    if (stage_index < 12)
      radius = (int)AOMMAX((radius * 1.5 + 0.5), radius + 1);
  }
  cfg->num_search_steps = num_search_steps;
}

// Search site initialization for BIGDIA / FAST_BIGDIA / FAST_DIAMOND
// search methods.
static void init_motion_compensation_bigdia(search_site_config *cfg, int stride,
                                            int level) {
  (void)level;
  cfg->stride = stride;
  // First scale has 4-closest points, the rest have 8 points in diamond
  // shape at increasing scales
  static const int bigdia_num_candidates[MAX_PATTERN_SCALES] = {
    4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  };

  // BIGDIA search method candidates.
  // Note that the largest candidate step at each scale is 2^scale
  /* clang-format off */
  static const FULLPEL_MV
      site_candidates[MAX_PATTERN_SCALES][MAX_PATTERN_CANDIDATES] = {
          { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, 0 }, { 0, 0 },
            { 0, 0 }, { 0, 0 } },
          { { -1, -1 }, { 0, -2 }, { 1, -1 }, { 2, 0 }, { 1, 1 }, { 0, 2 },
            { -1, 1 }, { -2, 0 } },
          { { -2, -2 }, { 0, -4 }, { 2, -2 }, { 4, 0 }, { 2, 2 }, { 0, 4 },
            { -2, 2 }, { -4, 0 } },
          { { -4, -4 }, { 0, -8 }, { 4, -4 }, { 8, 0 }, { 4, 4 }, { 0, 8 },
            { -4, 4 }, { -8, 0 } },
          { { -8, -8 }, { 0, -16 }, { 8, -8 }, { 16, 0 }, { 8, 8 }, { 0, 16 },
            { -8, 8 }, { -16, 0 } },
          { { -16, -16 }, { 0, -32 }, { 16, -16 }, { 32, 0 }, { 16, 16 },
            { 0, 32 }, { -16, 16 }, { -32, 0 } },
          { { -32, -32 }, { 0, -64 }, { 32, -32 }, { 64, 0 }, { 32, 32 },
            { 0, 64 }, { -32, 32 }, { -64, 0 } },
          { { -64, -64 }, { 0, -128 }, { 64, -64 }, { 128, 0 }, { 64, 64 },
            { 0, 128 }, { -64, 64 }, { -128, 0 } },
          { { -128, -128 }, { 0, -256 }, { 128, -128 }, { 256, 0 },
            { 128, 128 }, { 0, 256 }, { -128, 128 }, { -256, 0 } },
          { { -256, -256 }, { 0, -512 }, { 256, -256 }, { 512, 0 },
            { 256, 256 }, { 0, 512 }, { -256, 256 }, { -512, 0 } },
          { { -512, -512 }, { 0, -1024 }, { 512, -512 }, { 1024, 0 },
            { 512, 512 }, { 0, 1024 }, { -512, 512 }, { -1024, 0 } },
        };

  /* clang-format on */
  int radius = 1;
  for (int i = 0; i < MAX_PATTERN_SCALES; ++i) {
    cfg->searches_per_step[i] = bigdia_num_candidates[i];
    cfg->radius[i] = radius;
    for (int j = 0; j < MAX_PATTERN_CANDIDATES; ++j) {
      search_site *const site = &cfg->site[i][j];
      site->mv = site_candidates[i][j];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    radius *= 2;
  }
  cfg->num_search_steps = MAX_PATTERN_SCALES;
}

// Search site initialization for SQUARE search method.
static void init_motion_compensation_square(search_site_config *cfg, int stride,
                                            int level) {
  (void)level;
  cfg->stride = stride;
  // All scales have 8 closest points in square shape.
  static const int square_num_candidates[MAX_PATTERN_SCALES] = {
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  };

  // Square search method candidates.
  // Note that the largest candidate step at each scale is 2^scale.
  /* clang-format off */
    static const FULLPEL_MV
        square_candidates[MAX_PATTERN_SCALES][MAX_PATTERN_CANDIDATES] = {
             { { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 },
               { -1, 1 }, { -1, 0 } },
             { { -2, -2 }, { 0, -2 }, { 2, -2 }, { 2, 0 }, { 2, 2 }, { 0, 2 },
               { -2, 2 }, { -2, 0 } },
             { { -4, -4 }, { 0, -4 }, { 4, -4 }, { 4, 0 }, { 4, 4 }, { 0, 4 },
               { -4, 4 }, { -4, 0 } },
             { { -8, -8 }, { 0, -8 }, { 8, -8 }, { 8, 0 }, { 8, 8 }, { 0, 8 },
               { -8, 8 }, { -8, 0 } },
             { { -16, -16 }, { 0, -16 }, { 16, -16 }, { 16, 0 }, { 16, 16 },
               { 0, 16 }, { -16, 16 }, { -16, 0 } },
             { { -32, -32 }, { 0, -32 }, { 32, -32 }, { 32, 0 }, { 32, 32 },
               { 0, 32 }, { -32, 32 }, { -32, 0 } },
             { { -64, -64 }, { 0, -64 }, { 64, -64 }, { 64, 0 }, { 64, 64 },
               { 0, 64 }, { -64, 64 }, { -64, 0 } },
             { { -128, -128 }, { 0, -128 }, { 128, -128 }, { 128, 0 },
               { 128, 128 }, { 0, 128 }, { -128, 128 }, { -128, 0 } },
             { { -256, -256 }, { 0, -256 }, { 256, -256 }, { 256, 0 },
               { 256, 256 }, { 0, 256 }, { -256, 256 }, { -256, 0 } },
             { { -512, -512 }, { 0, -512 }, { 512, -512 }, { 512, 0 },
               { 512, 512 }, { 0, 512 }, { -512, 512 }, { -512, 0 } },
             { { -1024, -1024 }, { 0, -1024 }, { 1024, -1024 }, { 1024, 0 },
               { 1024, 1024 }, { 0, 1024 }, { -1024, 1024 }, { -1024, 0 } },
    };

  /* clang-format on */
  int radius = 1;
  for (int i = 0; i < MAX_PATTERN_SCALES; ++i) {
    cfg->searches_per_step[i] = square_num_candidates[i];
    cfg->radius[i] = radius;
    for (int j = 0; j < MAX_PATTERN_CANDIDATES; ++j) {
      search_site *const site = &cfg->site[i][j];
      site->mv = square_candidates[i][j];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    radius *= 2;
  }
  cfg->num_search_steps = MAX_PATTERN_SCALES;
}

// Search site initialization for HEX / FAST_HEX search methods.
static void init_motion_compensation_hex(search_site_config *cfg, int stride,
                                         int level) {
  (void)level;
  cfg->stride = stride;
  // First scale has 8-closest points, the rest have 6 points in hex shape
  // at increasing scales.
  static const int hex_num_candidates[MAX_PATTERN_SCALES] = { 8, 6, 6, 6, 6, 6,
                                                              6, 6, 6, 6, 6 };
  // Note that the largest candidate step at each scale is 2^scale.
  /* clang-format off */
    static const FULLPEL_MV
        hex_candidates[MAX_PATTERN_SCALES][MAX_PATTERN_CANDIDATES] = {
        { { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 },
          { -1, 1 }, { -1, 0 } },
        { { -1, -2 }, { 1, -2 }, { 2, 0 }, { 1, 2 }, { -1, 2 }, { -2, 0 } },
        { { -2, -4 }, { 2, -4 }, { 4, 0 }, { 2, 4 }, { -2, 4 }, { -4, 0 } },
        { { -4, -8 }, { 4, -8 }, { 8, 0 }, { 4, 8 }, { -4, 8 }, { -8, 0 } },
        { { -8, -16 }, { 8, -16 }, { 16, 0 }, { 8, 16 },
          { -8, 16 }, { -16, 0 } },
        { { -16, -32 }, { 16, -32 }, { 32, 0 }, { 16, 32 }, { -16, 32 },
          { -32, 0 } },
        { { -32, -64 }, { 32, -64 }, { 64, 0 }, { 32, 64 }, { -32, 64 },
          { -64, 0 } },
        { { -64, -128 }, { 64, -128 }, { 128, 0 }, { 64, 128 },
          { -64, 128 }, { -128, 0 } },
        { { -128, -256 }, { 128, -256 }, { 256, 0 }, { 128, 256 },
          { -128, 256 }, { -256, 0 } },
        { { -256, -512 }, { 256, -512 }, { 512, 0 }, { 256, 512 },
          { -256, 512 }, { -512, 0 } },
        { { -512, -1024 }, { 512, -1024 }, { 1024, 0 }, { 512, 1024 },
          { -512, 1024 }, { -1024, 0 } },
    };

  /* clang-format on */
  int radius = 1;
  for (int i = 0; i < MAX_PATTERN_SCALES; ++i) {
    cfg->searches_per_step[i] = hex_num_candidates[i];
    cfg->radius[i] = radius;
    for (int j = 0; j < hex_num_candidates[i]; ++j) {
      search_site *const site = &cfg->site[i][j];
      site->mv = hex_candidates[i][j];
      site->offset = get_offset_from_fullmv(&site->mv, stride);
    }
    radius *= 2;
  }
  cfg->num_search_steps = MAX_PATTERN_SCALES;
}

const av1_init_search_site_config
    av1_init_motion_compensation[NUM_DISTINCT_SEARCH_METHODS] = {
      init_dsmotion_compensation,     init_motion_compensation_nstep,
      init_motion_compensation_nstep, init_dsmotion_compensation,
      init_motion_compensation_hex,   init_motion_compensation_bigdia,
      init_motion_compensation_square
    };

// Checks whether the mv is within range of the mv_limits
static inline int check_bounds(const FullMvLimits *mv_limits, int row, int col,
                               int range) {
  return ((row - range) >= mv_limits->row_min) &
         ((row + range) <= mv_limits->row_max) &
         ((col - range) >= mv_limits->col_min) &
         ((col + range) <= mv_limits->col_max);
}

static inline int get_mvpred_var_cost(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params, const FULLPEL_MV *this_mv,
    FULLPEL_MV_STATS *mv_stats) {
  const aom_variance_fn_ptr_t *vfp = ms_params->vfp;
  const MV sub_this_mv = get_mv_from_fullmv(this_mv);
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;
  const int ref_stride = ref->stride;

  int bestsme;

  bestsme = vfp->vf(src_buf, src_stride, get_buf_from_fullmv(ref, this_mv),
                    ref_stride, &mv_stats->sse);
  mv_stats->distortion = bestsme;

  mv_stats->err_cost = mv_err_cost_(&sub_this_mv, &ms_params->mv_cost_params);
  bestsme += mv_stats->err_cost;

  return bestsme;
}

static inline int get_mvpred_sad(const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                                 const struct buf_2d *const src,
                                 const uint8_t *const ref_address,
                                 const int ref_stride) {
  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;

  return ms_params->sdf(src_buf, src_stride, ref_address, ref_stride);
}

static inline int get_mvpred_compound_var_cost(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params, const FULLPEL_MV *this_mv,
    FULLPEL_MV_STATS *mv_stats) {
  const aom_variance_fn_ptr_t *vfp = ms_params->vfp;
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;
  const int ref_stride = ref->stride;

  const uint8_t *mask = ms_params->ms_buffers.mask;
  const uint8_t *second_pred = ms_params->ms_buffers.second_pred;
  const int mask_stride = ms_params->ms_buffers.mask_stride;
  const int invert_mask = ms_params->ms_buffers.inv_mask;
  int bestsme;

  if (mask) {
    bestsme = vfp->msvf(get_buf_from_fullmv(ref, this_mv), ref_stride, 0, 0,
                        src_buf, src_stride, second_pred, mask, mask_stride,
                        invert_mask, &mv_stats->sse);
  } else if (second_pred) {
    bestsme = vfp->svaf(get_buf_from_fullmv(ref, this_mv), ref_stride, 0, 0,
                        src_buf, src_stride, &mv_stats->sse, second_pred);
  } else {
    bestsme = vfp->vf(src_buf, src_stride, get_buf_from_fullmv(ref, this_mv),
                      ref_stride, &mv_stats->sse);
  }
  mv_stats->distortion = bestsme;

  const MV sub_this_mv = get_mv_from_fullmv(this_mv);
  mv_stats->err_cost = mv_err_cost_(&sub_this_mv, &ms_params->mv_cost_params);
  bestsme += mv_stats->err_cost;

  return bestsme;
}

static inline int get_mvpred_compound_sad(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    const struct buf_2d *const src, const uint8_t *const ref_address,
    const int ref_stride) {
  const aom_variance_fn_ptr_t *vfp = ms_params->vfp;
  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;

  const uint8_t *mask = ms_params->ms_buffers.mask;
  const uint8_t *second_pred = ms_params->ms_buffers.second_pred;
  const int mask_stride = ms_params->ms_buffers.mask_stride;
  const int invert_mask = ms_params->ms_buffers.inv_mask;

  if (mask) {
    return vfp->msdf(src_buf, src_stride, ref_address, ref_stride, second_pred,
                     mask, mask_stride, invert_mask);
  } else if (second_pred) {
    assert(vfp->sdaf != NULL);
    return vfp->sdaf(src_buf, src_stride, ref_address, ref_stride, second_pred);
  } else {
    return ms_params->sdf(src_buf, src_stride, ref_address, ref_stride);
  }
}

// Calculates and returns a sad+mvcost list around an integer best pel during
// fullpixel motion search. The resulting list can be used to speed up subpel
// motion search later.
#define USE_SAD_COSTLIST 1

// calc_int_cost_list uses var to populate the costlist, which is more accurate
// than sad but slightly slower.
static AOM_FORCE_INLINE void calc_int_cost_list(
    const FULLPEL_MV best_mv, const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    int *cost_list) {
  static const FULLPEL_MV neighbors[4] = {
    { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }
  };
  const int br = best_mv.row;
  const int bc = best_mv.col;

  FULLPEL_MV_STATS mv_stats;
  cost_list[0] = get_mvpred_var_cost(ms_params, &best_mv, &mv_stats);

  if (check_bounds(&ms_params->mv_limits, br, bc, 1)) {
    for (int i = 0; i < 4; i++) {
      const FULLPEL_MV neighbor_mv = { br + neighbors[i].row,
                                       bc + neighbors[i].col };
      cost_list[i + 1] =
          get_mvpred_var_cost(ms_params, &neighbor_mv, &mv_stats);
    }
  } else {
    for (int i = 0; i < 4; i++) {
      const FULLPEL_MV neighbor_mv = { br + neighbors[i].row,
                                       bc + neighbors[i].col };
      if (!av1_is_fullmv_in_range(&ms_params->mv_limits, neighbor_mv)) {
        cost_list[i + 1] = INT_MAX;
      } else {
        cost_list[i + 1] =
            get_mvpred_var_cost(ms_params, &neighbor_mv, &mv_stats);
      }
    }
  }
}

// calc_int_sad_list uses sad to populate the costlist, which is less accurate
// than var but faster.
static AOM_FORCE_INLINE void calc_int_sad_list(
    const FULLPEL_MV best_mv, const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    int *cost_list, int costlist_has_sad) {
  static const FULLPEL_MV neighbors[4] = {
    { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }
  };
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const int ref_stride = ref->stride;
  const int br = best_mv.row;
  const int bc = best_mv.col;

  assert(av1_is_fullmv_in_range(&ms_params->mv_limits, best_mv));

  // Refresh the costlist it does not contain valid sad
  if (!costlist_has_sad) {
    cost_list[0] = get_mvpred_sad(
        ms_params, src, get_buf_from_fullmv(ref, &best_mv), ref_stride);

    if (check_bounds(&ms_params->mv_limits, br, bc, 1)) {
      for (int i = 0; i < 4; i++) {
        const FULLPEL_MV this_mv = { br + neighbors[i].row,
                                     bc + neighbors[i].col };
        cost_list[i + 1] = get_mvpred_sad(
            ms_params, src, get_buf_from_fullmv(ref, &this_mv), ref_stride);
      }
    } else {
      for (int i = 0; i < 4; i++) {
        const FULLPEL_MV this_mv = { br + neighbors[i].row,
                                     bc + neighbors[i].col };
        if (!av1_is_fullmv_in_range(&ms_params->mv_limits, this_mv)) {
          cost_list[i + 1] = INT_MAX;
        } else {
          cost_list[i + 1] = get_mvpred_sad(
              ms_params, src, get_buf_from_fullmv(ref, &this_mv), ref_stride);
        }
      }
    }
  }

  const MV_COST_PARAMS *mv_cost_params = &ms_params->mv_cost_params;
  cost_list[0] += mvsad_err_cost_(&best_mv, mv_cost_params);

  for (int idx = 0; idx < 4; idx++) {
    if (cost_list[idx + 1] != INT_MAX) {
      const FULLPEL_MV this_mv = { br + neighbors[idx].row,
                                   bc + neighbors[idx].col };
      cost_list[idx + 1] += mvsad_err_cost_(&this_mv, mv_cost_params);
    }
  }
}

// Computes motion vector cost and adds to the sad cost.
// Then updates the best sad and motion vectors.
// Inputs:
//   this_sad: the sad to be evaluated.
//   mv: the current motion vector.
//   mv_cost_params: a structure containing information to compute mv cost.
//   best_sad: the current best sad.
//   raw_best_sad (optional): the current best sad without calculating mv cost.
//   best_mv: the current best motion vector.
//   second_best_mv (optional): the second best motion vector up to now.
// Modifies:
//   best_sad, raw_best_sad, best_mv, second_best_mv
//   If the current sad is lower than the current best sad.
// Returns:
//   Whether the input sad (mv) is better than the current best.
static inline int update_mvs_and_sad(const unsigned int this_sad,
                                     const FULLPEL_MV *mv,
                                     const MV_COST_PARAMS *mv_cost_params,
                                     unsigned int *best_sad,
                                     unsigned int *raw_best_sad,
                                     FULLPEL_MV *best_mv,
                                     FULLPEL_MV *second_best_mv) {
  if (this_sad >= *best_sad) return 0;

  // Add the motion vector cost.
  const unsigned int sad = this_sad + mvsad_err_cost_(mv, mv_cost_params);
  if (sad < *best_sad) {
    if (raw_best_sad) *raw_best_sad = this_sad;
    *best_sad = sad;
    if (second_best_mv) *second_best_mv = *best_mv;
    *best_mv = *mv;
    return 1;
  }
  return 0;
}

// Calculate sad4 and update the bestmv information
// in FAST_DIAMOND search method.
static inline void calc_sad4_update_bestmv(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,
    const FULLPEL_MV center_mv, const uint8_t *center_address,
    unsigned int *bestsad, unsigned int *raw_bestsad, int search_step,
    int *best_site, int cand_start, int *cost_list) {
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const search_site *site = ms_params->search_sites->site[search_step];

  unsigned char const *block_offset[4];
  unsigned int sads_buf[4];
  unsigned int *sads;
  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;
  if (cost_list) {
    sads = (unsigned int *)(cost_list + 1);
  } else {
    sads = sads_buf;
  }
  // Loop over number of candidates.
  for (int j = 0; j < 4; j++)
    block_offset[j] = site[cand_start + j].offset + center_address;

  // 4-point sad calculation.
  ms_params->sdx4df(src_buf, src_stride, block_offset, ref->stride, sads);

  for (int j = 0; j < 4; j++) {
    const FULLPEL_MV this_mv = { center_mv.row + site[cand_start + j].mv.row,
                                 center_mv.col + site[cand_start + j].mv.col };
    const int found_better_mv = update_mvs_and_sad(
        sads[j], &this_mv, mv_cost_params, bestsad, raw_bestsad, best_mv,
        /*second_best_mv=*/NULL);
    if (found_better_mv) *best_site = cand_start + j;
  }
}

static inline void calc_sad3_update_bestmv(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,
    FULLPEL_MV center_mv, const uint8_t *center_address, unsigned int *bestsad,
    unsigned int *raw_bestsad, int search_step, int *best_site,
    const int *chkpts_indices, int *cost_list) {
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const search_site *site = ms_params->search_sites->site[search_step];
  unsigned char const *block_offset[4] = {
    center_address + site[chkpts_indices[0]].offset,
    center_address + site[chkpts_indices[1]].offset,
    center_address + site[chkpts_indices[2]].offset,
    center_address,
  };
  unsigned int sads[4];
  ms_params->sdx3df(src->buf, src->stride, block_offset, ref->stride, sads);
  for (int j = 0; j < 3; j++) {
    const int index = chkpts_indices[j];
    const FULLPEL_MV this_mv = { center_mv.row + site[index].mv.row,
                                 center_mv.col + site[index].mv.col };
    const int found_better_mv = update_mvs_and_sad(
        sads[j], &this_mv, mv_cost_params, bestsad, raw_bestsad, best_mv,
        /*second_best_mv=*/NULL);
    if (found_better_mv) *best_site = j;
  }
  if (cost_list) {
    for (int j = 0; j < 3; j++) {
      int index = chkpts_indices[j];
      cost_list[index + 1] = sads[j];
    }
  }
}

// Calculate sad and update the bestmv information
// in FAST_DIAMOND search method.
static inline void calc_sad_update_bestmv(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,
    const FULLPEL_MV center_mv, const uint8_t *center_address,
    unsigned int *bestsad, unsigned int *raw_bestsad, int search_step,
    int *best_site, const int num_candidates, int cand_start, int *cost_list) {
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const search_site *site = ms_params->search_sites->site[search_step];
  // Loop over number of candidates.
  for (int i = cand_start; i < num_candidates; i++) {
    const FULLPEL_MV this_mv = { center_mv.row + site[i].mv.row,
                                 center_mv.col + site[i].mv.col };
    if (!av1_is_fullmv_in_range(&ms_params->mv_limits, this_mv)) continue;
    int thissad = get_mvpred_sad(ms_params, src,
                                 center_address + site[i].offset, ref->stride);
    if (cost_list) {
      cost_list[i + 1] = thissad;
    }
    const int found_better_mv = update_mvs_and_sad(
        thissad, &this_mv, mv_cost_params, bestsad, raw_bestsad, best_mv,
        /*second_best_mv=*/NULL);
    if (found_better_mv) *best_site = i;
  }
}

static inline void calc_sad_update_bestmv_with_indices(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,
    const FULLPEL_MV center_mv, const uint8_t *center_address,
    unsigned int *bestsad, unsigned int *raw_bestsad, int search_step,
    int *best_site, const int num_candidates, const int *chkpts_indices,
    int *cost_list) {
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const search_site *site = ms_params->search_sites->site[search_step];
  // Loop over number of candidates.
  for (int i = 0; i < num_candidates; i++) {
    int index = chkpts_indices[i];
    const FULLPEL_MV this_mv = { center_mv.row + site[index].mv.row,
                                 center_mv.col + site[index].mv.col };
    if (!av1_is_fullmv_in_range(&ms_params->mv_limits, this_mv)) {
      if (cost_list) {
        cost_list[index + 1] = INT_MAX;
      }
      continue;
    }
    const int thissad = get_mvpred_sad(
        ms_params, src, center_address + site[index].offset, ref->stride);
    if (cost_list) {
      cost_list[index + 1] = thissad;
    }
    const int found_better_mv = update_mvs_and_sad(
        thissad, &this_mv, mv_cost_params, bestsad, raw_bestsad, best_mv,
        /*second_best_mv=*/NULL);
    if (found_better_mv) *best_site = i;
  }
}

// Generic pattern search function that searches over multiple scales.
// Each scale can have a different number of candidates and shape of
// candidates as indicated in the num_candidates and candidates arrays
// passed into this function
static int pattern_search(FULLPEL_MV start_mv,
                          const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                          int search_step, const int do_init_search,
                          int *cost_list, FULLPEL_MV *best_mv,
                          FULLPEL_MV_STATS *best_mv_stats) {
  static const int search_steps[MAX_MVSEARCH_STEPS] = {
    10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
  };
  int i, s, t;

  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const search_site_config *search_sites = ms_params->search_sites;
  const int *num_candidates = search_sites->searches_per_step;
  const int ref_stride = ref->stride;
  const int last_is_4 = num_candidates[0] == 4;
  int br, bc;
  unsigned int bestsad = UINT_MAX, raw_bestsad = UINT_MAX;
  int k = -1;
  const MV_COST_PARAMS *mv_cost_params = &ms_params->mv_cost_params;
  search_step = AOMMIN(search_step, MAX_MVSEARCH_STEPS - 1);
  assert(search_step >= 0);
  int best_init_s = search_steps[search_step];
  // adjust ref_mv to make sure it is within MV range
  clamp_fullmv(&start_mv, &ms_params->mv_limits);
  br = start_mv.row;
  bc = start_mv.col;
  if (cost_list != NULL) {
    cost_list[0] = cost_list[1] = cost_list[2] = cost_list[3] = cost_list[4] =
        INT_MAX;
  }
  int costlist_has_sad = 0;

  // Work out the start point for the search
  raw_bestsad = get_mvpred_sad(ms_params, src,
                               get_buf_from_fullmv(ref, &start_mv), ref_stride);
  bestsad = raw_bestsad + mvsad_err_cost_(&start_mv, mv_cost_params);

  // Search all possible scales up to the search param around the center point
  // pick the scale of the point that is best as the starting scale of
  // further steps around it.
  const uint8_t *center_address = get_buf_from_fullmv(ref, &start_mv);
  if (do_init_search) {
    s = best_init_s;
    best_init_s = -1;
    for (t = 0; t <= s; ++t) {
      int best_site = -1;
      FULLPEL_MV center_mv = { br, bc };
      if (check_bounds(&ms_params->mv_limits, br, bc, 1 << t)) {
        // Call 4-point sad for multiples of 4 candidates.
        const int no_of_4_cand_loops = num_candidates[t] >> 2;
        for (i = 0; i < no_of_4_cand_loops; i++) {
          calc_sad4_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                  center_address, &bestsad, &raw_bestsad, t,
                                  &best_site, i * 4, /*cost_list=*/NULL);
        }
        // Rest of the candidates
        const int remaining_cand = num_candidates[t] % 4;
        calc_sad_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                               center_address, &bestsad, &raw_bestsad, t,
                               &best_site, remaining_cand,
                               no_of_4_cand_loops * 4, NULL);
      } else {
        calc_sad_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                               center_address, &bestsad, &raw_bestsad, t,
                               &best_site, num_candidates[t], 0, NULL);
      }
      if (best_site == -1) {
        continue;
      } else {
        best_init_s = t;
        k = best_site;
      }
    }
    if (best_init_s != -1) {
      br += search_sites->site[best_init_s][k].mv.row;
      bc += search_sites->site[best_init_s][k].mv.col;
      center_address += search_sites->site[best_init_s][k].offset;
    }
  }

  // If the center point is still the best, just skip this and move to
  // the refinement step.
  if (best_init_s != -1) {
    const int last_s = (last_is_4 && cost_list != NULL);
    int best_site = -1;
    s = best_init_s;

    for (; s >= last_s; s--) {
      // No need to search all points the 1st time if initial search was used
      if (!do_init_search || s != best_init_s) {
        FULLPEL_MV center_mv = { br, bc };
        if (check_bounds(&ms_params->mv_limits, br, bc, 1 << s)) {
          // Call 4-point sad for multiples of 4 candidates.
          const int no_of_4_cand_loops = num_candidates[s] >> 2;
          for (i = 0; i < no_of_4_cand_loops; i++) {
            calc_sad4_update_bestmv(ms_params, mv_cost_params, best_mv,
                                    center_mv, center_address, &bestsad,
                                    &raw_bestsad, s, &best_site, i * 4,
                                    /*cost_list=*/NULL);
          }
          // Rest of the candidates
          const int remaining_cand = num_candidates[s] % 4;
          calc_sad_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                 center_address, &bestsad, &raw_bestsad, s,
                                 &best_site, remaining_cand,
                                 no_of_4_cand_loops * 4, NULL);
        } else {
          calc_sad_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                 center_address, &bestsad, &raw_bestsad, s,
                                 &best_site, num_candidates[s], 0, NULL);
        }

        if (best_site == -1) {
          continue;
        } else {
          br += search_sites->site[s][best_site].mv.row;
          bc += search_sites->site[s][best_site].mv.col;
          center_address += search_sites->site[s][best_site].offset;
          k = best_site;
        }
      }

      do {
        int next_chkpts_indices[PATTERN_CANDIDATES_REF];
        best_site = -1;
        next_chkpts_indices[0] = (k == 0) ? num_candidates[s] - 1 : k - 1;
        next_chkpts_indices[1] = k;
        next_chkpts_indices[2] = (k == num_candidates[s] - 1) ? 0 : k + 1;

        FULLPEL_MV center_mv = { br, bc };
        if (check_bounds(&ms_params->mv_limits, br, bc, 1 << s)) {
          calc_sad3_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                  center_address, &bestsad, &raw_bestsad, s,
                                  &best_site, next_chkpts_indices, NULL);
        } else {
          calc_sad_update_bestmv_with_indices(
              ms_params, mv_cost_params, best_mv, center_mv, center_address,
              &bestsad, &raw_bestsad, s, &best_site, PATTERN_CANDIDATES_REF,
              next_chkpts_indices, NULL);
        }

        if (best_site != -1) {
          k = next_chkpts_indices[best_site];
          br += search_sites->site[s][k].mv.row;
          bc += search_sites->site[s][k].mv.col;
          center_address += search_sites->site[s][k].offset;
        }
      } while (best_site != -1);
    }
    // Note: If we enter the if below, then cost_list must be non-NULL.
    if (s == 0) {
      cost_list[0] = raw_bestsad;
      costlist_has_sad = 1;
      assert(num_candidates[s] == 4);
      if (!do_init_search || s != best_init_s) {
        FULLPEL_MV center_mv = { br, bc };
        if (check_bounds(&ms_params->mv_limits, br, bc, 1 << s)) {
          calc_sad4_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                  center_address, &bestsad, &raw_bestsad, s,
                                  &best_site, 0, cost_list);
        } else {
          calc_sad_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                 center_address, &bestsad, &raw_bestsad, s,
                                 &best_site, /*num_candidates=*/4,
                                 /*cand_start=*/0, cost_list);
        }

        if (best_site != -1) {
          br += search_sites->site[s][best_site].mv.row;
          bc += search_sites->site[s][best_site].mv.col;
          center_address += search_sites->site[s][best_site].offset;
          k = best_site;
        }
      }
      while (best_site != -1) {
        int next_chkpts_indices[PATTERN_CANDIDATES_REF];
        best_site = -1;
        next_chkpts_indices[0] = (k == 0) ? num_candidates[s] - 1 : k - 1;
        next_chkpts_indices[1] = k;
        next_chkpts_indices[2] = (k == num_candidates[s] - 1) ? 0 : k + 1;
        cost_list[1] = cost_list[2] = cost_list[3] = cost_list[4] = INT_MAX;
        cost_list[((k + 2) % 4) + 1] = cost_list[0];
        cost_list[0] = raw_bestsad;

        FULLPEL_MV center_mv = { br, bc };
        if (check_bounds(&ms_params->mv_limits, br, bc, 1 << s)) {
          assert(PATTERN_CANDIDATES_REF == 3);
          calc_sad3_update_bestmv(ms_params, mv_cost_params, best_mv, center_mv,
                                  center_address, &bestsad, &raw_bestsad, s,
                                  &best_site, next_chkpts_indices, cost_list);
        } else {
          calc_sad_update_bestmv_with_indices(
              ms_params, mv_cost_params, best_mv, center_mv, center_address,
              &bestsad, &raw_bestsad, s, &best_site, PATTERN_CANDIDATES_REF,
              next_chkpts_indices, cost_list);
        }

        if (best_site != -1) {
          k = next_chkpts_indices[best_site];
          br += search_sites->site[s][k].mv.row;
          bc += search_sites->site[s][k].mv.col;
          center_address += search_sites->site[s][k].offset;
        }
      }
    }
  }
  best_mv->row = br;
  best_mv->col = bc;

  assert(center_address == get_buf_from_fullmv(ref, best_mv) &&
         "center address is out of sync with best_mv!\n");

  // Returns the one-away integer pel cost/sad around the best as follows:
  // cost_list[0]: cost/sad at the best integer pel
  // cost_list[1]: cost/sad at delta {0, -1} (left)   from the best integer pel
  // cost_list[2]: cost/sad at delta { 1, 0} (bottom) from the best integer pel
  // cost_list[3]: cost/sad at delta { 0, 1} (right)  from the best integer pel
  // cost_list[4]: cost/sad at delta {-1, 0} (top)    from the best integer pel
  if (cost_list) {
    if (USE_SAD_COSTLIST) {
      calc_int_sad_list(*best_mv, ms_params, cost_list, costlist_has_sad);
    } else {
      calc_int_cost_list(*best_mv, ms_params, cost_list);
    }
  }

  const int var_cost = get_mvpred_var_cost(ms_params, best_mv, best_mv_stats);
  return var_cost;
}

// For the following foo_search, the input arguments are:
// start_mv: where we are starting our motion search
// ms_params: a collection of motion search parameters
// search_step: how many steps to skip in our motion search. For example,
//   a value 3 suggests that 3 search steps have already taken place prior to
//   this function call, so we jump directly to step 4 of the search process
// do_init_search: if on, do an initial search of all possible scales around the
//   start_mv, and then pick the best scale.
// cond_list: used to hold the cost around the best full mv so we can use it to
//   speed up subpel search later.
// best_mv: the best mv found in the motion search
static int hex_search(const FULLPEL_MV start_mv,
                      const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                      const int search_step, const int do_init_search,
                      int *cost_list, FULLPEL_MV *best_mv,
                      FULLPEL_MV_STATS *best_mv_stats) {
  return pattern_search(start_mv, ms_params, search_step, do_init_search,
                        cost_list, best_mv, best_mv_stats);
}

static int bigdia_search(const FULLPEL_MV start_mv,
                         const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                         const int search_step, const int do_init_search,
                         int *cost_list, FULLPEL_MV *best_mv,
                         FULLPEL_MV_STATS *best_mv_stats) {
  return pattern_search(start_mv, ms_params, search_step, do_init_search,
                        cost_list, best_mv, best_mv_stats);
}

static int square_search(const FULLPEL_MV start_mv,
                         const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                         const int search_step, const int do_init_search,
                         int *cost_list, FULLPEL_MV *best_mv,
                         FULLPEL_MV_STATS *best_mv_stats) {
  return pattern_search(start_mv, ms_params, search_step, do_init_search,
                        cost_list, best_mv, best_mv_stats);
}

static int fast_hex_search(const FULLPEL_MV start_mv,
                           const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                           const int search_step, const int do_init_search,
                           int *cost_list, FULLPEL_MV *best_mv,
                           FULLPEL_MV_STATS *best_mv_stats) {
  return hex_search(start_mv, ms_params,
                    AOMMAX(MAX_MVSEARCH_STEPS - 2, search_step), do_init_search,
                    cost_list, best_mv, best_mv_stats);
}

static int vfast_dia_search(const FULLPEL_MV start_mv,
                            const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                            const int search_step, const int do_init_search,
                            int *cost_list, FULLPEL_MV *best_mv,
                            FULLPEL_MV_STATS *best_mv_stats) {
  return bigdia_search(start_mv, ms_params,
                       AOMMAX(MAX_MVSEARCH_STEPS - 1, search_step),
                       do_init_search, cost_list, best_mv, best_mv_stats);
}

static int fast_dia_search(const FULLPEL_MV start_mv,
                           const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                           const int search_step, const int do_init_search,
                           int *cost_list, FULLPEL_MV *best_mv,
                           FULLPEL_MV_STATS *best_mv_stats) {
  return bigdia_search(start_mv, ms_params,
                       AOMMAX(MAX_MVSEARCH_STEPS - 2, search_step),
                       do_init_search, cost_list, best_mv, best_mv_stats);
}

static int fast_bigdia_search(const FULLPEL_MV start_mv,
                              const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                              const int search_step, const int do_init_search,
                              int *cost_list, FULLPEL_MV *best_mv,
                              FULLPEL_MV_STATS *best_mv_stats) {
  return bigdia_search(start_mv, ms_params,
                       AOMMAX(MAX_MVSEARCH_STEPS - 3, search_step),
                       do_init_search, cost_list, best_mv, best_mv_stats);
}

static int diamond_search_sad(FULLPEL_MV start_mv, unsigned int start_mv_sad,
                              const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                              const int search_step, int *num00,
                              FULLPEL_MV *best_mv, FULLPEL_MV *second_best_mv) {
#define UPDATE_SEARCH_STEP                                      \
  do {                                                          \
    if (best_site != 0) {                                       \
      tmp_second_best_mv = *best_mv;                            \
      best_mv->row += site[best_site].mv.row;                   \
      best_mv->col += site[best_site].mv.col;                   \
      best_address += site[best_site].offset;                   \
      is_off_center = 1;                                        \
    }                                                           \
                                                                \
    if (is_off_center == 0) num_center_steps++;                 \
                                                                \
    if (best_site == 0 && step > 2) {                           \
      int next_step_size = cfg->radius[step - 1];               \
      while (next_step_size == cfg->radius[step] && step > 2) { \
        num_center_steps++;                                     \
        --step;                                                 \
        next_step_size = cfg->radius[step - 1];                 \
      }                                                         \
    }                                                           \
  } while (0)

  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;

  const uint8_t *src_buf = src->buf;
  const int src_stride = src->stride;
  const int ref_stride = ref->stride;

  const MV_COST_PARAMS *mv_cost_params = &ms_params->mv_cost_params;

  const search_site_config *cfg = ms_params->search_sites;

  int is_off_center = 0;
  // Number of times that we have stayed in the middle. This is used to skip
  // search steps in the future if diamond_search_sad is called again.
  int num_center_steps = 0;

  // search_step determines the length of the initial step and hence the number
  // of iterations.
  const int tot_steps = cfg->num_search_steps - search_step;
  FULLPEL_MV tmp_second_best_mv;
  if (second_best_mv) {
    tmp_second_best_mv = *second_best_mv;
  }

  *best_mv = start_mv;

  // Check the starting position
  const uint8_t *best_address = get_buf_from_fullmv(ref, &start_mv);
  unsigned int bestsad = start_mv_sad;

  // TODO(chiyotsai@google.com): Implement 4 points search for msdf&sdaf
  if (ms_params->ms_buffers.second_pred) {
    for (int step = tot_steps - 1; step >= 0; --step) {
      const search_site *site = cfg->site[step];
      const int num_searches = cfg->searches_per_step[step];
      int best_site = 0;

      for (int idx = 1; idx <= num_searches; idx++) {
        const FULLPEL_MV this_mv = { best_mv->row + site[idx].mv.row,
                                     best_mv->col + site[idx].mv.col };

        if (av1_is_fullmv_in_range(&ms_params->mv_limits, this_mv)) {
          const uint8_t *const check_here = site[idx].offset + best_address;
          unsigned int thissad =
              get_mvpred_compound_sad(ms_params, src, check_here, ref_stride);

          if (thissad < bestsad) {
            thissad += mvsad_err_cost_(&this_mv, mv_cost_params);
            if (thissad < bestsad) {
              bestsad = thissad;
              best_site = idx;
            }
          }
        }
      }
      UPDATE_SEARCH_STEP;
    }
  } else {
    for (int step = tot_steps - 1; step >= 0; --step) {
      const search_site *site = cfg->site[step];
      const int num_searches = cfg->searches_per_step[step];
      int best_site = 0;

      int all_in = 1;
      // Trap illegal vectors
      all_in &= best_mv->row + site[1].mv.row >= ms_params->mv_limits.row_min;
      all_in &= best_mv->row + site[2].mv.row <= ms_params->mv_limits.row_max;
      all_in &= best_mv->col + site[3].mv.col >= ms_params->mv_limits.col_min;
      all_in &= best_mv->col + site[4].mv.col <= ms_params->mv_limits.col_max;

      if (all_in) {
        for (int idx = 1; idx <= num_searches; idx += 4) {
          unsigned char const *block_offset[4];
          unsigned int sads[4];

          for (int j = 0; j < 4; j++)
            block_offset[j] = site[idx + j].offset + best_address;

          ms_params->sdx4df(src_buf, src_stride, block_offset, ref_stride,
                            sads);
          for (int j = 0; j < 4; j++) {
            if (sads[j] < bestsad) {
              const FULLPEL_MV this_mv = { best_mv->row + site[idx + j].mv.row,
                                           best_mv->col +
                                               site[idx + j].mv.col };
              unsigned int thissad =
                  sads[j] + mvsad_err_cost_(&this_mv, mv_cost_params);
              if (thissad < bestsad) {
                bestsad = thissad;
                best_site = idx + j;
              }
            }
          }
        }
      } else {
        for (int idx = 1; idx <= num_searches; idx++) {
          const FULLPEL_MV this_mv = { best_mv->row + site[idx].mv.row,
                                       best_mv->col + site[idx].mv.col };

          if (av1_is_fullmv_in_range(&ms_params->mv_limits, this_mv)) {
            const uint8_t *const check_here = site[idx].offset + best_address;
            unsigned int thissad =
                get_mvpred_sad(ms_params, src, check_here, ref_stride);

            if (thissad < bestsad) {
              thissad += mvsad_err_cost_(&this_mv, mv_cost_params);
              if (thissad < bestsad) {
                bestsad = thissad;
                best_site = idx;
              }
            }
          }
        }
      }
      UPDATE_SEARCH_STEP;
    }
  }

  *num00 = num_center_steps;
  if (second_best_mv) {
    *second_best_mv = tmp_second_best_mv;
  }

  return bestsad;

#undef UPDATE_SEARCH_STEP
}

static inline unsigned int get_start_mvpred_sad_cost(
    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params, FULLPEL_MV start_mv) {
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const uint8_t *best_address = get_buf_from_fullmv(ref, &start_mv);

  unsigned int start_mv_sad =
      mvsad_err_cost_(&start_mv, &ms_params->mv_cost_params);

  if (ms_params->ms_buffers.second_pred)
    start_mv_sad +=
        get_mvpred_compound_sad(ms_params, src, best_address, ref->stride);
  else
    start_mv_sad += get_mvpred_sad(ms_params, src, best_address, ref->stride);

  return start_mv_sad;
}

static int full_pixel_diamond(FULLPEL_MV start_mv,
                              const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                              const int step_param, int *cost_list,
                              FULLPEL_MV *best_mv,
                              FULLPEL_MV_STATS *best_mv_stats,
                              FULLPEL_MV *second_best_mv) {
  const search_site_config *cfg = ms_params->search_sites;
  int thissme, n, num00 = 0;

  // Clamp start mv and calculate the cost
  clamp_fullmv(&start_mv, &ms_params->mv_limits);
  unsigned int start_mv_sad = get_start_mvpred_sad_cost(ms_params, start_mv);

  diamond_search_sad(start_mv, start_mv_sad, ms_params, step_param, &n, best_mv,
                     second_best_mv);

  int bestsme = get_mvpred_compound_var_cost(ms_params, best_mv, best_mv_stats);

  // If there won't be more n-step search, check to see if refining search is
  // needed.
  const int further_steps = cfg->num_search_steps - 1 - step_param;
  while (n < further_steps) {
    ++n;

    // TODO(chiyotsai@google.com): There is another bug here where the second
    // best mv gets incorrectly overwritten. Fix it later.
    FULLPEL_MV tmp_best_mv;
    FULLPEL_MV_STATS tmp_best_mv_stats;
    diamond_search_sad(start_mv, start_mv_sad, ms_params, step_param + n,
                       &num00, &tmp_best_mv, second_best_mv);

    thissme = get_mvpred_compound_var_cost(ms_params, &tmp_best_mv,
                                           &tmp_best_mv_stats);

    if (thissme < bestsme) {
      bestsme = thissme;
      *best_mv = tmp_best_mv;
      *best_mv_stats = tmp_best_mv_stats;
    }

    if (num00) {
      // Advance the loop by num00 steps
      n += num00;
      num00 = 0;
    }
  }

  // Return cost list.
  if (cost_list) {
    if (USE_SAD_COSTLIST) {
      const int costlist_has_sad = 0;
      calc_int_sad_list(*best_mv, ms_params, cost_list, costlist_has_sad);
    } else {
      calc_int_cost_list(*best_mv, ms_params, cost_list);
    }
  }
  return bestsme;
}

// Exhaustive motion search around a given centre position with a given
// step size.
static int exhaustive_mesh_search(FULLPEL_MV start_mv,
                                  const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,
                                  const int range, const int step,
                                  FULLPEL_MV *best_mv,
                                  FULLPEL_MV *second_best_mv) {
  const MV_COST_PARAMS *mv_cost_params = &ms_params->mv_cost_params;
  const struct buf_2d *const src = ms_params->ms_buffers.src;
  const struct buf_2d *const ref = ms_params->ms_buffers.ref;
  const int ref_stride = ref->stride;
  unsigned int best_sad = INT_MAX;
  int r, c, i;
  int start_col, end_col, start_row, end_row;
--> --------------------

--> maximum size reached

--> --------------------