/*

 * 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 <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;

}

static AOM_INLINE SEARCH_METHODS

get_faster_search_method(SEARCH_METHODS search_method) {

  // Note on search method's accuracy:

  //  1. NSTEP

  //  2. DIAMOND

  //  3. BIGDIA \approx SQUARE

  //  4. HEX.

  //  5. FAST_HEX \approx FAST_DIAMOND

  switch (search_method) {

    case NSTEP: return DIAMOND;

    case NSTEP_8PT: return DIAMOND;

    case DIAMOND: return BIGDIA;

    case CLAMPED_DIAMOND: return BIGDIA;

    case BIGDIA: return HEX;

    case SQUARE: return HEX;

    case HEX: return FAST_HEX;

    case FAST_HEX: return FAST_HEX;

    case FAST_DIAMOND: return FAST_DIAMOND;

    case FAST_BIGDIA: return FAST_BIGDIA;

    default: assert(0 && "Invalid search method!"); return DIAMOND;

  }

}

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,

    const MACROBLOCK *x, BLOCK_SIZE bsize, const MV *ref_mv,

    const search_site_config search_sites[NUM_DISTINCT_SEARCH_METHODS],

    int fine_search_interval) {

  const MV_SPEED_FEATURES *mv_sf = &cpi->sf.mv_sf;

  // High level params

  ms_params->bsize = bsize;

  ms_params->vfp = &cpi->ppi->fn_ptr[bsize];

  init_ms_buffers(&ms_params->ms_buffers, x);

  SEARCH_METHODS search_method = mv_sf->search_method;

  if (mv_sf->use_bsize_dependent_search_method) {

    const int min_dim = AOMMIN(block_size_wide[bsize], block_size_high[bsize]);

    if (min_dim >= 32) {

      search_method = get_faster_search_method(search_method);

    }

  }

  av1_set_mv_search_method(ms_params, search_sites, search_method);

  const int use_downsampled_sad =

      mv_sf->use_downsampled_sad && block_size_high[bsize] >= 16;

  if (use_downsampled_sad) {

    ms_params->sdf = ms_params->vfp->sdsf;

    ms_params->sdx4df = ms_params->vfp->sdsx4df;

  } else {

    ms_params->sdf = ms_params->vfp->sdf;

    ms_params->sdx4df = ms_params->vfp->sdx4df;

  }

  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);

}

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);

}

static INLINE int get_offset_from_fullmv(const FULLPEL_MV *mv, int stride) {

  return mv->row * stride + mv->col;

}

static INLINE const uint8_t *get_buf_from_fullmv(const struct buf_2d *buf,

                                                 const FULLPEL_MV *mv) {

  return &buf->buf[get_offset_from_fullmv(mv, buf->stride)];

}

void av1_set_mv_search_range(FullMvLimits *mv_limits, const MV *mv) {

  int col_min =

      GET_MV_RAWPEL(mv->col) - MAX_FULL_PEL_VAL + (mv->col & 7 ? 1 : 0);

  int row_min =

      GET_MV_RAWPEL(mv->row) - MAX_FULL_PEL_VAL + (mv->row & 7 ? 1 : 0);

  int col_max = GET_MV_RAWPEL(mv->col) + MAX_FULL_PEL_VAL;

  int row_max = GET_MV_RAWPEL(mv->row) + MAX_FULL_PEL_VAL;

  col_min = AOMMAX(col_min, GET_MV_RAWPEL(MV_LOW) + 1);

  row_min = AOMMAX(row_min, GET_MV_RAWPEL(MV_LOW) + 1);

  col_max = AOMMIN(col_max, GET_MV_RAWPEL(MV_UPP) - 1);

  row_max = AOMMIN(row_max, GET_MV_RAWPEL(MV_UPP) - 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;

}

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.

void av1_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.

void av1_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.

void av1_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.

void av1_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.

void av1_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;

}

// 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) {

  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;

  unsigned unused;

  int bestsme;

  bestsme = vfp->vf(src_buf, src_stride, get_buf_from_fullmv(ref, this_mv),

                    ref_stride, &unused);

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

  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) {

  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;

  unsigned unused;

  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, &unused);

  } else if (second_pred) {

    bestsme = vfp->svaf(get_buf_from_fullmv(ref, this_mv), ref_stride, 0, 0,

                        src_buf, src_stride, &unused, second_pred);

  } else {

    bestsme = vfp->vf(src_buf, src_stride, get_buf_from_fullmv(ref, this_mv),

                      ref_stride, &unused);

  }

  const MV sub_this_mv = get_mv_from_fullmv(this_mv);

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

  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) {

    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;

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

  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);

    }

  } 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);

      }

    }

  }

}

// 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 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 void calc_sad4_update_bestmv(

    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,

    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,

    FULLPEL_MV *temp_best_mv, unsigned int *bestsad, unsigned int *raw_bestsad,

    int search_step, int *best_site, int cand_start) {

  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[4];

  const uint8_t *best_address;

  const uint8_t *src_buf = src->buf;

  const int src_stride = src->stride;

  best_address = get_buf_from_fullmv(ref, temp_best_mv);

  // Loop over number of candidates.

  for (int j = 0; j < 4; j++)

    block_offset[j] = site[cand_start + j].offset + best_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 = {

      temp_best_mv->row + site[cand_start + j].mv.row,

      temp_best_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;

  }

}

// Calculate sad and update the bestmv information

// in FAST_DIAMOND search method.

static void calc_sad_update_bestmv(

    const FULLPEL_MOTION_SEARCH_PARAMS *ms_params,

    const MV_COST_PARAMS *mv_cost_params, FULLPEL_MV *best_mv,

    FULLPEL_MV *temp_best_mv, unsigned int *bestsad, unsigned int *raw_bestsad,

    int search_step, int *best_site, const int num_candidates, int cand_start) {

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

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