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

   1 /*
   2  *  Copyright (c) 2015 The WebM project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #if defined(_MSC_VER)
  12 # include <intrin.h>
  13 #endif
  14 #include <emmintrin.h>
  15 #include <smmintrin.h>
  16
  17 #include "vpx_dsp/vpx_dsp_common.h"
  18 #include "vp9/encoder/vp9_encoder.h"
  19 #include "vpx_ports/mem.h"
  20
  21 #ifdef __GNUC__
  22 # define __likely__(v)    __builtin_expect(v, 1)
  23 # define __unlikely__(v)  __builtin_expect(v, 0)
  24 #else
  25 # define __likely__(v)    (v)
  26 # define __unlikely__(v)  (v)
  27 #endif
  28
  29 static INLINE int_mv pack_int_mv(int16_t row, int16_t col) {
  30   int_mv result;
  31   result.as_mv.row = row;
  32   result.as_mv.col = col;
  33   return result;
  34 }
  35
  36 static INLINE MV_JOINT_TYPE get_mv_joint(const int_mv mv) {
  37   // This is simplified from the C implementation to utilise that
  38   //  x->nmvjointsadcost[1] == x->nmvjointsadcost[2]  and
  39   //  x->nmvjointsadcost[1] == x->nmvjointsadcost[3]
  40   return mv.as_int == 0 ? 0 : 1;
  41 }
  42
  43 static INLINE int mv_cost(const int_mv mv,
  44                           const int *joint_cost, int *const comp_cost[2]) {
  45   return joint_cost[get_mv_joint(mv)] +
  46          comp_cost[0][mv.as_mv.row] + comp_cost[1][mv.as_mv.col];
  47 }
  48
  49 static int mvsad_err_cost(const MACROBLOCK *x, const int_mv mv, const MV *ref,
  50                           int error_per_bit) {
  51   const int_mv diff = pack_int_mv(mv.as_mv.row - ref->row,
  52                                   mv.as_mv.col - ref->col);
  53   return ROUND_POWER_OF_TWO((unsigned)mv_cost(diff, x->nmvjointsadcost,
  54                                               x->nmvsadcost) *
  55                                               error_per_bit, 8);
  56 }
  57
  58 /*****************************************************************************
  59  * This function utilises 3 properties of the cost function lookup tables,   *
  60  * constructed in using 'cal_nmvjointsadcost' and 'cal_nmvsadcosts' in       *
  61  * vp9_encoder.c.                                                            *
  62  * For the joint cost:                                                       *
  63  *   - mvjointsadcost[1] == mvjointsadcost[2] == mvjointsadcost[3]           *
  64  * For the component costs:                                                  *
  65  *   - For all i: mvsadcost[0][i] == mvsadcost[1][i]                         *
  66  *         (Equal costs for both components)                                 *
  67  *   - For all i: mvsadcost[0][i] == mvsadcost[0][-i]                        *
  68  *         (Cost function is even)                                           *
  69  * If these do not hold, then this function cannot be used without           *
  70  * modification, in which case you can revert to using the C implementation, *
  71  * which does not rely on these properties.                                  *
  72  *****************************************************************************/
  73 int vp9_diamond_search_sad_avx(const MACROBLOCK *x,
  74                                const search_site_config *cfg,
  75                                MV *ref_mv, MV *best_mv, int search_param,
  76                                int sad_per_bit, int *num00,
  77                                const vp9_variance_fn_ptr_t *fn_ptr,
  78                                const MV *center_mv) {
  79   const int_mv maxmv = pack_int_mv(x->mv_row_max, x->mv_col_max);
  80   const __m128i v_max_mv_w = _mm_set1_epi32(maxmv.as_int);
  81   const int_mv minmv = pack_int_mv(x->mv_row_min, x->mv_col_min);
  82   const __m128i v_min_mv_w = _mm_set1_epi32(minmv.as_int);
  83
  84   const __m128i v_spb_d = _mm_set1_epi32(sad_per_bit);
  85
  86   const __m128i v_joint_cost_0_d = _mm_set1_epi32(x->nmvjointsadcost[0]);
  87   const __m128i v_joint_cost_1_d = _mm_set1_epi32(x->nmvjointsadcost[1]);
  88
  89   // search_param determines the length of the initial step and hence the number
  90   // of iterations.
  91   // 0 = initial step (MAX_FIRST_STEP) pel
  92   // 1 = (MAX_FIRST_STEP/2) pel,
  93   // 2 = (MAX_FIRST_STEP/4) pel...
  94   const       MV *ss_mv = &cfg->ss_mv[cfg->searches_per_step * search_param];
  95   const intptr_t *ss_os = &cfg->ss_os[cfg->searches_per_step * search_param];
  96   const int tot_steps = cfg->total_steps - search_param;
  97
  98   const int_mv fcenter_mv = pack_int_mv(center_mv->row >> 3,
  99                                         center_mv->col >> 3);
 100   const __m128i vfcmv = _mm_set1_epi32(fcenter_mv.as_int);
 101
 102   const int ref_row = clamp(ref_mv->row, minmv.as_mv.row, maxmv.as_mv.row);
 103   const int ref_col = clamp(ref_mv->col, minmv.as_mv.col, maxmv.as_mv.col);
 104
 105   int_mv bmv = pack_int_mv(ref_row, ref_col);
 106   int_mv new_bmv = bmv;
 107   __m128i v_bmv_w = _mm_set1_epi32(bmv.as_int);
 108
 109   const int what_stride = x->plane[0].src.stride;
 110   const int in_what_stride = x->e_mbd.plane[0].pre[0].stride;
 111   const uint8_t *const what = x->plane[0].src.buf;
 112   const uint8_t *const in_what = x->e_mbd.plane[0].pre[0].buf +
 113                                  ref_row * in_what_stride + ref_col;
 114
 115   // Work out the start point for the search
 116   const uint8_t *best_address = in_what;
 117   const uint8_t *new_best_address = best_address;
 118 #if ARCH_X86_64
 119   __m128i v_ba_q = _mm_set1_epi64x((intptr_t)best_address);
 120 #else
 121   __m128i v_ba_d = _mm_set1_epi32((intptr_t)best_address);
 122 #endif
 123
 124   unsigned int best_sad;
 125
 126   int i;
 127   int j;
 128   int step;
 129
 130   // Check the prerequisite cost function properties that are easy to check
 131   // in an assert. See the function-level documentation for details on all
 132   // prerequisites.
 133   assert(x->nmvjointsadcost[1] == x->nmvjointsadcost[2]);
 134   assert(x->nmvjointsadcost[1] == x->nmvjointsadcost[3]);
 135
 136   // Check the starting position
 137   best_sad = fn_ptr->sdf(what, what_stride, in_what, in_what_stride);
 138   best_sad += mvsad_err_cost(x, bmv, &fcenter_mv.as_mv, sad_per_bit);
 139
 140   *num00 = 0;
 141
 142   for (i = 0, step = 0; step < tot_steps; step++) {
 143     for (j = 0; j < cfg->searches_per_step; j += 4, i += 4) {
 144       __m128i v_sad_d;
 145       __m128i v_cost_d;
 146       __m128i v_outside_d;
 147       __m128i v_inside_d;
 148       __m128i v_diff_mv_w;
 149 #if ARCH_X86_64
 150       __m128i v_blocka[2];
 151 #else
 152       __m128i v_blocka[1];
 153 #endif
 154
 155       // Compute the candidate motion vectors
 156       const __m128i v_ss_mv_w = _mm_loadu_si128((const __m128i*)&ss_mv[i]);
 157       const __m128i v_these_mv_w = _mm_add_epi16(v_bmv_w, v_ss_mv_w);
 158       // Clamp them to the search bounds
 159       __m128i v_these_mv_clamp_w = v_these_mv_w;
 160       v_these_mv_clamp_w = _mm_min_epi16(v_these_mv_clamp_w, v_max_mv_w);
 161       v_these_mv_clamp_w = _mm_max_epi16(v_these_mv_clamp_w, v_min_mv_w);
 162       // The ones that did not change are inside the search area
 163       v_inside_d = _mm_cmpeq_epi32(v_these_mv_clamp_w, v_these_mv_w);
 164
 165       // If none of them are inside, then move on
 166       if (__likely__(_mm_test_all_zeros(v_inside_d, v_inside_d))) {
 167         continue;
 168       }
 169
 170       // The inverse mask indicates which of the MVs are outside
 171       v_outside_d = _mm_xor_si128(v_inside_d, _mm_set1_epi8(0xff));
 172       // Shift right to keep the sign bit clear, we will use this later
 173       // to set the cost to the maximum value.
 174       v_outside_d = _mm_srli_epi32(v_outside_d, 1);
 175
 176       // Compute the difference MV
 177       v_diff_mv_w = _mm_sub_epi16(v_these_mv_clamp_w, vfcmv);
 178       // We utilise the fact that the cost function is even, and use the
 179       // absolute difference. This allows us to use unsigned indexes later
 180       // and reduces cache pressure somewhat as only a half of the table
 181       // is ever referenced.
 182       v_diff_mv_w = _mm_abs_epi16(v_diff_mv_w);
 183
 184       // Compute the SIMD pointer offsets.
 185       {
 186 #if ARCH_X86_64  //  sizeof(intptr_t) == 8
 187         // Load the offsets
 188         __m128i v_bo10_q = _mm_loadu_si128((const __m128i*)&ss_os[i+0]);
 189         __m128i v_bo32_q = _mm_loadu_si128((const __m128i*)&ss_os[i+2]);
 190         // Set the ones falling outside to zero
 191         v_bo10_q = _mm_and_si128(v_bo10_q,
 192                                  _mm_cvtepi32_epi64(v_inside_d));
 193         v_bo32_q = _mm_and_si128(v_bo32_q,
 194                                  _mm_unpackhi_epi32(v_inside_d, v_inside_d));
 195         // Compute the candidate addresses
 196         v_blocka[0] = _mm_add_epi64(v_ba_q, v_bo10_q);
 197         v_blocka[1] = _mm_add_epi64(v_ba_q, v_bo32_q);
 198 #else  // ARCH_X86 //  sizeof(intptr_t) == 4
 199         __m128i v_bo_d = _mm_loadu_si128((const __m128i*)&ss_os[i]);
 200         v_bo_d = _mm_and_si128(v_bo_d, v_inside_d);
 201         v_blocka[0] = _mm_add_epi32(v_ba_d, v_bo_d);
 202 #endif
 203       }
 204
 205       fn_ptr->sdx4df(what, what_stride,
 206                      (const uint8_t **)&v_blocka[0], in_what_stride,
 207                      (uint32_t*)&v_sad_d);
 208
 209       // Look up the component cost of the residual motion vector
 210       {
 211         const int32_t row0 = _mm_extract_epi16(v_diff_mv_w, 0);
 212         const int32_t col0 = _mm_extract_epi16(v_diff_mv_w, 1);
 213         const int32_t row1 = _mm_extract_epi16(v_diff_mv_w, 2);
 214         const int32_t col1 = _mm_extract_epi16(v_diff_mv_w, 3);
 215         const int32_t row2 = _mm_extract_epi16(v_diff_mv_w, 4);
 216         const int32_t col2 = _mm_extract_epi16(v_diff_mv_w, 5);
 217         const int32_t row3 = _mm_extract_epi16(v_diff_mv_w, 6);
 218         const int32_t col3 = _mm_extract_epi16(v_diff_mv_w, 7);
 219
 220         // Note: This is a use case for vpgather in AVX2
 221         const uint32_t cost0 = x->nmvsadcost[0][row0] + x->nmvsadcost[0][col0];
 222         const uint32_t cost1 = x->nmvsadcost[0][row1] + x->nmvsadcost[0][col1];
 223         const uint32_t cost2 = x->nmvsadcost[0][row2] + x->nmvsadcost[0][col2];
 224         const uint32_t cost3 = x->nmvsadcost[0][row3] + x->nmvsadcost[0][col3];
 225
 226         __m128i v_cost_10_d, v_cost_32_d;
 227
 228         v_cost_10_d = _mm_cvtsi32_si128(cost0);
 229         v_cost_10_d = _mm_insert_epi32(v_cost_10_d, cost1, 1);
 230
 231         v_cost_32_d = _mm_cvtsi32_si128(cost2);
 232         v_cost_32_d = _mm_insert_epi32(v_cost_32_d, cost3, 1);
 233
 234         v_cost_d = _mm_unpacklo_epi64(v_cost_10_d, v_cost_32_d);
 235       }
 236
 237       // Now add in the joint cost
 238       {
 239         const __m128i v_sel_d = _mm_cmpeq_epi32(v_diff_mv_w,
 240                                                 _mm_setzero_si128());
 241         const __m128i v_joint_cost_d = _mm_blendv_epi8(v_joint_cost_1_d,
 242                                                        v_joint_cost_0_d,
 243                                                        v_sel_d);
 244         v_cost_d = _mm_add_epi32(v_cost_d, v_joint_cost_d);
 245       }
 246
 247       // Multiply by sad_per_bit
 248       v_cost_d = _mm_mullo_epi32(v_cost_d, v_spb_d);
 249       // ROUND_POWER_OF_TWO(v_cost_d, 8)
 250       v_cost_d = _mm_add_epi32(v_cost_d, _mm_set1_epi32(0x80));
 251       v_cost_d = _mm_srai_epi32(v_cost_d, 8);
 252       // Add the cost to the sad
 253       v_sad_d = _mm_add_epi32(v_sad_d, v_cost_d);
 254
 255       // Make the motion vectors outside the search area have max cost
 256       // by or'ing in the comparison mask, this way the minimum search won't
 257       // pick them.
 258       v_sad_d = _mm_or_si128(v_sad_d, v_outside_d);
 259
 260       // Find the minimum value and index horizontally in v_sad_d
 261       {
 262         // Try speculatively on 16 bits, so we can use the minpos intrinsic
 263         const __m128i v_sad_w = _mm_packus_epi32(v_sad_d, v_sad_d);
 264         const __m128i v_minp_w = _mm_minpos_epu16(v_sad_w);
 265
 266         uint32_t local_best_sad = _mm_extract_epi16(v_minp_w, 0);
 267         uint32_t local_best_idx = _mm_extract_epi16(v_minp_w, 1);
 268
 269         // If the local best value is not saturated, just use it, otherwise
 270         // find the horizontal minimum again the hard way on 32 bits.
 271         // This is executed rarely.
 272         if (__unlikely__(local_best_sad == 0xffff)) {
 273           __m128i v_loval_d, v_hival_d, v_loidx_d, v_hiidx_d, v_sel_d;
 274
 275           v_loval_d = v_sad_d;
 276           v_loidx_d = _mm_set_epi32(3, 2, 1, 0);
 277           v_hival_d = _mm_srli_si128(v_loval_d, 8);
 278           v_hiidx_d = _mm_srli_si128(v_loidx_d, 8);
 279
 280           v_sel_d = _mm_cmplt_epi32(v_hival_d, v_loval_d);
 281
 282           v_loval_d = _mm_blendv_epi8(v_loval_d, v_hival_d, v_sel_d);
 283           v_loidx_d = _mm_blendv_epi8(v_loidx_d, v_hiidx_d, v_sel_d);
 284           v_hival_d = _mm_srli_si128(v_loval_d, 4);
 285           v_hiidx_d = _mm_srli_si128(v_loidx_d, 4);
 286
 287           v_sel_d = _mm_cmplt_epi32(v_hival_d, v_loval_d);
 288
 289           v_loval_d = _mm_blendv_epi8(v_loval_d, v_hival_d, v_sel_d);
 290           v_loidx_d = _mm_blendv_epi8(v_loidx_d, v_hiidx_d, v_sel_d);
 291
 292           local_best_sad = _mm_extract_epi32(v_loval_d, 0);
 293           local_best_idx = _mm_extract_epi32(v_loidx_d, 0);
 294         }
 295
 296         // Update the global minimum if the local minimum is smaller
 297         if (__likely__(local_best_sad < best_sad)) {
 298           new_bmv = ((const int_mv *)&v_these_mv_w)[local_best_idx];
 299           new_best_address = ((const uint8_t **)v_blocka)[local_best_idx];
 300
 301           best_sad = local_best_sad;
 302         }
 303       }
 304     }
 305
 306     bmv = new_bmv;
 307     best_address = new_best_address;
 308
 309     v_bmv_w = _mm_set1_epi32(bmv.as_int);
 310 #if ARCH_X86_64
 311     v_ba_q = _mm_set1_epi64x((intptr_t)best_address);
 312 #else
 313     v_ba_d = _mm_set1_epi32((intptr_t)best_address);
 314 #endif
 315
 316     if (__unlikely__(best_address == in_what)) {
 317       (*num00)++;
 318     }
 319   }
 320
 321   *best_mv = bmv.as_mv;
 322   return best_sad;
 323 }