Optimise get_horver_correlation_full, SSE4 & AVX2 I have optimised the pure C get_horver_correlation_full in rdopt.c and also developed SSE4.1 and AVX2 implementations for further speed-up. I have also added functional equivalence unit tests for these. Optimised C speed-up over un-optimised C at the unit test level: 4x4 : 2.7x 32x32 : 6.2x 128x128: 7.4x SSE4.1 speed-up over un-optimised C at the unit test level: 4x4 : 2.7x 32x32 : 13.7x 128x128: 18.6x AVX2 speed-up over un-optimised C at the unit test level: 4x4 : 2.2x 32x32 : 15.6x 128x128: 26.4x Speed-ups for other block sizes, including rectangular blocks, are similar. Change-Id: Idc75006d5682e5cbf336d0427038e855da607097
diff --git a/av1/av1.cmake b/av1/av1.cmake index b84b83b..7976746 100644 --- a/av1/av1.cmake +++ b/av1/av1.cmake
@@ -274,6 +274,7 @@ "${AOM_ROOT}/av1/encoder/x86/corner_match_sse4.c" "${AOM_ROOT}/av1/encoder/x86/encodetxb_sse4.c" "${AOM_ROOT}/av1/encoder/x86/highbd_fwd_txfm_sse4.c" + "${AOM_ROOT}/av1/encoder/x86/rdopt_sse4.c" "${AOM_ROOT}/av1/encoder/x86/pickrst_sse4.c") list(APPEND AOM_AV1_ENCODER_INTRIN_AVX2 @@ -284,6 +285,7 @@ "${AOM_ROOT}/av1/encoder/x86/av1_fwd_txfm2d_avx2.c" "${AOM_ROOT}/av1/encoder/x86/wedge_utils_avx2.c" "${AOM_ROOT}/av1/encoder/x86/encodetxb_avx2.c" + "${AOM_ROOT}/av1/encoder/x86/rdopt_avx2.c" "${AOM_ROOT}/av1/encoder/x86/pickrst_avx2.c") list(APPEND AOM_AV1_ENCODER_INTRIN_NEON
diff --git a/av1/common/av1_rtcd_defs.pl b/av1/common/av1_rtcd_defs.pl index aabb001..f2a043c 100755 --- a/av1/common/av1_rtcd_defs.pl +++ b/av1/common/av1_rtcd_defs.pl
@@ -305,6 +305,9 @@ add_proto qw/int64_t av1_highbd_pixel_proj_error/, " const uint8_t *src8, int width, int height, int src_stride, const uint8_t *dat8, int dat_stride, int32_t *flt0, int flt0_stride, int32_t *flt1, int flt1_stride, int xq[2], const sgr_params_type *params"; specialize qw/av1_highbd_pixel_proj_error sse4_1 avx2/; + + add_proto qw/void av1_get_horver_correlation_full/, " const int16_t *diff, int stride, int w, int h, float *hcorr, float *vcorr"; + specialize qw/av1_get_horver_correlation_full sse4_1 avx2/; } # end encoder functions
diff --git a/av1/encoder/rdopt.c b/av1/encoder/rdopt.c index 970260e..e27a713 100644 --- a/av1/encoder/rdopt.c +++ b/av1/encoder/rdopt.c
@@ -1669,69 +1669,100 @@ // Similar to get_horver_correlation, but also takes into account first // row/column, when computing horizontal/vertical correlation. -static void get_horver_correlation_full(const int16_t *diff, int stride, int w, - int h, float *hcorr, float *vcorr) { - const float num_hor = (float)(h * (w - 1)); - const float num_ver = (float)((h - 1) * w); - int i, j; - +void av1_get_horver_correlation_full_c(const int16_t *diff, int stride, + int width, int height, float *hcorr, + float *vcorr) { // The following notation is used: // x - current pixel // y - left neighbor pixel // z - top neighbor pixel - int64_t xy_sum = 0, xz_sum = 0; - int64_t xhor_sum = 0, xver_sum = 0, y_sum = 0, z_sum = 0; - int64_t x2hor_sum = 0, x2ver_sum = 0, y2_sum = 0, z2_sum = 0; + int64_t x_sum = 0, x2_sum = 0, xy_sum = 0, xz_sum = 0; + int64_t x_firstrow = 0, x_finalrow = 0, x_firstcol = 0, x_finalcol = 0; + int64_t x2_firstrow = 0, x2_finalrow = 0, x2_firstcol = 0, x2_finalcol = 0; - int16_t x, y, z; - for (j = 1; j < w; ++j) { - x = diff[j]; - y = diff[j - 1]; + // First, process horizontal correlation on just the first row + x_sum += diff[0]; + x2_sum += diff[0] * diff[0]; + x_firstrow += diff[0]; + x2_firstrow += diff[0] * diff[0]; + for (int j = 1; j < width; ++j) { + const int16_t x = diff[j]; + const int16_t y = diff[j - 1]; + x_sum += x; + x_firstrow += x; + x2_sum += x * x; + x2_firstrow += x * x; xy_sum += x * y; - xhor_sum += x; - y_sum += y; - x2hor_sum += x * x; - y2_sum += y * y; } - for (i = 1; i < h; ++i) { - x = diff[i * stride]; - z = diff[(i - 1) * stride]; + + // Process vertical correlation in the first column + x_firstcol += diff[0]; + x2_firstcol += diff[0] * diff[0]; + for (int i = 1; i < height; ++i) { + const int16_t x = diff[i * stride]; + const int16_t z = diff[(i - 1) * stride]; + x_sum += x; + x_firstcol += x; + x2_sum += x * x; + x2_firstcol += x * x; xz_sum += x * z; - xver_sum += x; - z_sum += z; - x2ver_sum += x * x; - z2_sum += z * z; - for (j = 1; j < w; ++j) { - x = diff[i * stride + j]; - y = diff[i * stride + j - 1]; - z = diff[(i - 1) * stride + j]; + } + + // Now process horiz and vert correlation through the rest unit + for (int i = 1; i < height; ++i) { + for (int j = 1; j < width; ++j) { + const int16_t x = diff[i * stride + j]; + const int16_t y = diff[i * stride + j - 1]; + const int16_t z = diff[(i - 1) * stride + j]; + x_sum += x; + x2_sum += x * x; xy_sum += x * y; xz_sum += x * z; - xhor_sum += x; - xver_sum += x; - y_sum += y; - z_sum += z; - x2hor_sum += x * x; - x2ver_sum += x * x; - y2_sum += y * y; - z2_sum += z * z; } } + + for (int j = 0; j < width; ++j) { + x_finalrow += diff[(height - 1) * stride + j]; + x2_finalrow += + diff[(height - 1) * stride + j] * diff[(height - 1) * stride + j]; + } + for (int i = 0; i < height; ++i) { + x_finalcol += diff[i * stride + width - 1]; + x2_finalcol += diff[i * stride + width - 1] * diff[i * stride + width - 1]; + } + + int64_t xhor_sum = x_sum - x_finalcol; + int64_t xver_sum = x_sum - x_finalrow; + int64_t y_sum = x_sum - x_firstcol; + int64_t z_sum = x_sum - x_firstrow; + int64_t x2hor_sum = x2_sum - x2_finalcol; + int64_t x2ver_sum = x2_sum - x2_finalrow; + int64_t y2_sum = x2_sum - x2_firstcol; + int64_t z2_sum = x2_sum - x2_firstrow; + + const float num_hor = (float)(height * (width - 1)); + const float num_ver = (float)((height - 1) * width); + const float xhor_var_n = x2hor_sum - (xhor_sum * xhor_sum) / num_hor; - const float y_var_n = y2_sum - (y_sum * y_sum) / num_hor; - const float xy_var_n = xy_sum - (xhor_sum * y_sum) / num_hor; const float xver_var_n = x2ver_sum - (xver_sum * xver_sum) / num_ver; + + const float y_var_n = y2_sum - (y_sum * y_sum) / num_hor; const float z_var_n = z2_sum - (z_sum * z_sum) / num_ver; + + const float xy_var_n = xy_sum - (xhor_sum * y_sum) / num_hor; const float xz_var_n = xz_sum - (xver_sum * z_sum) / num_ver; - *hcorr = *vcorr = 1; if (xhor_var_n > 0 && y_var_n > 0) { *hcorr = xy_var_n / sqrtf(xhor_var_n * y_var_n); *hcorr = *hcorr < 0 ? 0 : *hcorr; + } else { + *hcorr = 1.0; } if (xver_var_n > 0 && z_var_n > 0) { *vcorr = xz_var_n / sqrtf(xver_var_n * z_var_n); *vcorr = *vcorr < 0 ? 0 : *vcorr; + } else { + *vcorr = 1.0; } } @@ -1844,9 +1875,9 @@ const int16_t *diff = p->src_diff + 4 * blk_row * diff_stride + 4 * blk_col; get_energy_distribution_finer(diff, diff_stride, bw, bh, hfeatures, vfeatures); - get_horver_correlation_full(diff, diff_stride, bw, bh, - &hfeatures[hfeatures_num - 1], - &vfeatures[vfeatures_num - 1]); + av1_get_horver_correlation_full(diff, diff_stride, bw, bh, + &hfeatures[hfeatures_num - 1], + &vfeatures[vfeatures_num - 1]); av1_nn_predict(hfeatures, nn_config_hor, hscores); av1_nn_predict(vfeatures, nn_config_ver, vscores);
diff --git a/av1/encoder/x86/rdopt_avx2.c b/av1/encoder/x86/rdopt_avx2.c new file mode 100644 index 0000000..a94c076 --- /dev/null +++ b/av1/encoder/x86/rdopt_avx2.c
@@ -0,0 +1,253 @@ +/* + * Copyright (c) 2018, 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 <immintrin.h> +#include "aom_dsp/x86/synonyms_avx2.h" + +#include "config/av1_rtcd.h" +#include "av1/encoder/rdopt.h" + +// Process horizontal and vertical correlations in a 4x4 block of pixels. +// We actually use the 4x4 pixels to calculate correlations corresponding to +// the top-left 3x3 pixels, so this function must be called with 1x1 overlap, +// moving the window along/down by 3 pixels at a time. +INLINE static void horver_correlation_4x4(const int16_t *diff, int stride, + __m256i *xy_sum_32, + __m256i *xz_sum_32, __m256i *x_sum_32, + __m256i *x2_sum_32) { + // Pixels in this 4x4 [ a b c d ] + // are referred to as: [ e f g h ] + // [ i j k l ] + // [ m n o p ] + + const __m256i pixels = _mm256_set_epi64x( + *(uint64_t *)&diff[0 * stride], *(uint64_t *)&diff[1 * stride], + *(uint64_t *)&diff[2 * stride], *(uint64_t *)&diff[3 * stride]); + // pixels = [d c b a h g f e] [l k j i p o n m] as i16 + + const __m256i slli = _mm256_slli_epi64(pixels, 16); + // slli = [c b a 0 g f e 0] [k j i 0 o n m 0] as i16 + + const __m256i madd_xy = _mm256_madd_epi16(pixels, slli); + // madd_xy = [bc+cd ab fg+gh ef] [jk+kl ij no+op mn] as i32 + *xy_sum_32 = _mm256_add_epi32(*xy_sum_32, madd_xy); + + // Permute control [3 2] [1 0] => [2 1] [0 0], 0b10010000 = 0x90 + const __m256i perm = _mm256_permute4x64_epi64(slli, 0x90); + // perm = [g f e 0 k j i 0] [o n m 0 o n m 0] as i16 + + const __m256i madd_xz = _mm256_madd_epi16(slli, perm); + // madd_xz = [cg+bf ae gk+fj ei] [ko+jn im oo+nn mm] as i32 + *xz_sum_32 = _mm256_add_epi32(*xz_sum_32, madd_xz); + + // Sum every element in slli (and then also their squares) + const __m256i madd1_slli = _mm256_madd_epi16(slli, _mm256_set1_epi16(1)); + // madd1_slli = [c+b a g+f e] [k+j i o+n m] as i32 + *x_sum_32 = _mm256_add_epi32(*x_sum_32, madd1_slli); + + const __m256i madd_slli = _mm256_madd_epi16(slli, slli); + // madd_slli = [cc+bb aa gg+ff ee] [kk+jj ii oo+nn mm] as i32 + *x2_sum_32 = _mm256_add_epi32(*x2_sum_32, madd_slli); +} + +void av1_get_horver_correlation_full_avx2(const int16_t *diff, int stride, + int width, int height, float *hcorr, + float *vcorr) { + // The following notation is used: + // x - current pixel + // y - right neighbour pixel + // z - below neighbour pixel + // w - down-right neighbour pixel + int64_t xy_sum = 0, xz_sum = 0; + int64_t x_sum = 0, x2_sum = 0; + + // Process horizontal and vertical correlations through the body in 4x4 + // blocks. This excludes the final row and column and possibly one extra + // column depending how 3 divides into width and height + int32_t xy_xz_tmp[8] = { 0 }, x_x2_tmp[8] = { 0 }; + __m256i xy_sum_32 = _mm256_setzero_si256(); + __m256i xz_sum_32 = _mm256_setzero_si256(); + __m256i x_sum_32 = _mm256_setzero_si256(); + __m256i x2_sum_32 = _mm256_setzero_si256(); + for (int i = 0; i <= height - 4; i += 3) { + for (int j = 0; j <= width - 4; j += 3) { + horver_correlation_4x4(&diff[i * stride + j], stride, &xy_sum_32, + &xz_sum_32, &x_sum_32, &x2_sum_32); + } + const __m256i hadd_xy_xz = _mm256_hadd_epi32(xy_sum_32, xz_sum_32); + // hadd_xy_xz = [ae+bf+cg ei+fj+gk ab+bc+cd ef+fg+gh] + // [im+jn+ko mm+nn+oo ij+jk+kl mn+no+op] as i32 + yy_storeu_256(xy_xz_tmp, hadd_xy_xz); + xy_sum += (int64_t)xy_xz_tmp[5] + xy_xz_tmp[4] + xy_xz_tmp[1]; + xz_sum += (int64_t)xy_xz_tmp[7] + xy_xz_tmp[6] + xy_xz_tmp[3]; + + const __m256i hadd_x_x2 = _mm256_hadd_epi32(x_sum_32, x2_sum_32); + // hadd_x_x2 = [aa+bb+cc ee+ff+gg a+b+c e+f+g] + // [ii+jj+kk mm+nn+oo i+j+k m+n+o] as i32 + yy_storeu_256(x_x2_tmp, hadd_x_x2); + x_sum += (int64_t)x_x2_tmp[5] + x_x2_tmp[4] + x_x2_tmp[1]; + x2_sum += (int64_t)x_x2_tmp[7] + x_x2_tmp[6] + x_x2_tmp[3]; + + xy_sum_32 = _mm256_setzero_si256(); + xz_sum_32 = _mm256_setzero_si256(); + x_sum_32 = _mm256_setzero_si256(); + x2_sum_32 = _mm256_setzero_si256(); + } + + // x_sum now covers every pixel except the final 1-2 rows and 1-2 cols + int64_t x_finalrow = 0, x_finalcol = 0, x2_finalrow = 0, x2_finalcol = 0; + + // Do we have 2 rows remaining or just the one? Note that width and height + // are powers of 2, so each modulo 3 must be 1 or 2. + if (height % 3 == 1) { // Just horiz corrs on the final row + const int16_t x0 = diff[(height - 1) * stride]; + x_sum += x0; + x_finalrow += x0; + x2_sum += x0 * x0; + x2_finalrow += x0 * x0; + for (int j = 0; j < width - 1; ++j) { + const int16_t x = diff[(height - 1) * stride + j]; + const int16_t y = diff[(height - 1) * stride + j + 1]; + xy_sum += x * y; + x_sum += y; + x2_sum += y * y; + x_finalrow += y; + x2_finalrow += y * y; + } + } else { // Two rows remaining to do + const int16_t x0 = diff[(height - 2) * stride]; + const int16_t z0 = diff[(height - 1) * stride]; + x_sum += x0 + z0; + x2_sum += x0 * x0 + z0 * z0; + x_finalrow += z0; + x2_finalrow += z0 * z0; + for (int j = 0; j < width - 1; ++j) { + const int16_t x = diff[(height - 2) * stride + j]; + const int16_t y = diff[(height - 2) * stride + j + 1]; + const int16_t z = diff[(height - 1) * stride + j]; + const int16_t w = diff[(height - 1) * stride + j + 1]; + + // Horizontal and vertical correlations for the penultimate row: + xy_sum += x * y; + xz_sum += x * z; + + // Now just horizontal correlations for the final row: + xy_sum += z * w; + + x_sum += y + w; + x2_sum += y * y + w * w; + x_finalrow += w; + x2_finalrow += w * w; + } + } + + // Do we have 2 columns remaining or just the one? + if (width % 3 == 1) { // Just vert corrs on the final col + const int16_t x0 = diff[width - 1]; + x_sum += x0; + x_finalcol += x0; + x2_sum += x0 * x0; + x2_finalcol += x0 * x0; + for (int i = 0; i < height - 1; ++i) { + const int16_t x = diff[i * stride + width - 1]; + const int16_t z = diff[(i + 1) * stride + width - 1]; + xz_sum += x * z; + x_finalcol += z; + x2_finalcol += z * z; + // So the bottom-right elements don't get counted twice: + if (i < height - (height % 3 == 1 ? 2 : 3)) { + x_sum += z; + x2_sum += z * z; + } + } + } else { // Two cols remaining + const int16_t x0 = diff[width - 2]; + const int16_t y0 = diff[width - 1]; + x_sum += x0 + y0; + x2_sum += x0 * x0 + y0 * y0; + x_finalcol += y0; + x2_finalcol += y0 * y0; + for (int i = 0; i < height - 1; ++i) { + const int16_t x = diff[i * stride + width - 2]; + const int16_t y = diff[i * stride + width - 1]; + const int16_t z = diff[(i + 1) * stride + width - 2]; + const int16_t w = diff[(i + 1) * stride + width - 1]; + + // Horizontal and vertical correlations for the penultimate col: + // Skip these on the last iteration of this loop if we also had two + // rows remaining, otherwise the final horizontal and vertical correlation + // get erroneously processed twice + if (i < height - 2 || height % 3 == 1) { + xy_sum += x * y; + xz_sum += x * z; + } + + x_finalcol += w; + x2_finalcol += w * w; + // So the bottom-right elements don't get counted twice: + if (i < height - (height % 3 == 1 ? 2 : 3)) { + x_sum += z + w; + x2_sum += z * z + w * w; + } + + // Now just vertical correlations for the final column: + xz_sum += y * w; + } + } + + // Calculate the simple sums and squared-sums + int64_t x_firstrow = 0, x_firstcol = 0; + int64_t x2_firstrow = 0, x2_firstcol = 0; + + for (int j = 0; j < width; ++j) { + x_firstrow += diff[j]; + x2_firstrow += diff[j] * diff[j]; + } + for (int i = 0; i < height; ++i) { + x_firstcol += diff[i * stride]; + x2_firstcol += diff[i * stride] * diff[i * stride]; + } + + int64_t xhor_sum = x_sum - x_finalcol; + int64_t xver_sum = x_sum - x_finalrow; + int64_t y_sum = x_sum - x_firstcol; + int64_t z_sum = x_sum - x_firstrow; + int64_t x2hor_sum = x2_sum - x2_finalcol; + int64_t x2ver_sum = x2_sum - x2_finalrow; + int64_t y2_sum = x2_sum - x2_firstcol; + int64_t z2_sum = x2_sum - x2_firstrow; + + const float num_hor = (float)(height * (width - 1)); + const float num_ver = (float)((height - 1) * width); + + const float xhor_var_n = x2hor_sum - (xhor_sum * xhor_sum) / num_hor; + const float xver_var_n = x2ver_sum - (xver_sum * xver_sum) / num_ver; + + const float y_var_n = y2_sum - (y_sum * y_sum) / num_hor; + const float z_var_n = z2_sum - (z_sum * z_sum) / num_ver; + + const float xy_var_n = xy_sum - (xhor_sum * y_sum) / num_hor; + const float xz_var_n = xz_sum - (xver_sum * z_sum) / num_ver; + + if (xhor_var_n > 0 && y_var_n > 0) { + *hcorr = xy_var_n / sqrtf(xhor_var_n * y_var_n); + *hcorr = *hcorr < 0 ? 0 : *hcorr; + } else { + *hcorr = 1.0; + } + if (xver_var_n > 0 && z_var_n > 0) { + *vcorr = xz_var_n / sqrtf(xver_var_n * z_var_n); + *vcorr = *vcorr < 0 ? 0 : *vcorr; + } else { + *vcorr = 1.0; + } +}
diff --git a/av1/encoder/x86/rdopt_sse4.c b/av1/encoder/x86/rdopt_sse4.c new file mode 100644 index 0000000..f5ffae7 --- /dev/null +++ b/av1/encoder/x86/rdopt_sse4.c
@@ -0,0 +1,272 @@ +/* + * Copyright (c) 2018, 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 <emmintrin.h> +#include "aom_dsp/x86/synonyms.h" + +#include "config/av1_rtcd.h" +#include "av1/encoder/rdopt.h" + +// Process horizontal and vertical correlations in a 4x4 block of pixels. +// We actually use the 4x4 pixels to calculate correlations corresponding to +// the top-left 3x3 pixels, so this function must be called with 1x1 overlap, +// moving the window along/down by 3 pixels at a time. +INLINE static void horver_correlation_4x4(const int16_t *diff, int stride, + __m128i *xy_sum_32, + __m128i *xz_sum_32, __m128i *x_sum_32, + __m128i *x2_sum_32) { + // Pixels in this 4x4 [ a b c d ] + // are referred to as: [ e f g h ] + // [ i j k l ] + // [ m n o p ] + + const __m128i pixelsa = _mm_set_epi64x(*(uint64_t *)&diff[0 * stride], + *(uint64_t *)&diff[2 * stride]); + const __m128i pixelsb = _mm_set_epi64x(*(uint64_t *)&diff[1 * stride], + *(uint64_t *)&diff[3 * stride]); + // pixelsa = [d c b a l k j i] as i16 + // pixelsb = [h g f e p o n m] as i16 + + const __m128i slli_a = _mm_slli_epi64(pixelsa, 16); + const __m128i slli_b = _mm_slli_epi64(pixelsb, 16); + // slli_a = [c b a 0 k j i 0] as i16 + // slli_b = [g f e 0 o n m 0] as i16 + + const __m128i xy_madd_a = _mm_madd_epi16(pixelsa, slli_a); + const __m128i xy_madd_b = _mm_madd_epi16(pixelsb, slli_b); + // xy_madd_a = [bc+cd ab jk+kl ij] as i32 + // xy_madd_b = [fg+gh ef no+op mn] as i32 + + const __m128i xy32 = _mm_hadd_epi32(xy_madd_b, xy_madd_a); + // xy32 = [ab+bc+cd ij+jk+kl ef+fg+gh mn+no+op] as i32 + *xy_sum_32 = _mm_add_epi32(*xy_sum_32, xy32); + + const __m128i xz_madd_a = _mm_madd_epi16(slli_a, slli_b); + // xz_madd_a = [bf+cg ae jn+ko im] i32 + + const __m128i swap_b = _mm_srli_si128(slli_b, 8); + // swap_b = [0 0 0 0 g f e 0] as i16 + const __m128i xz_madd_b = _mm_madd_epi16(slli_a, swap_b); + // xz_madd_b = [0 0 gk+fj ei] i32 + + const __m128i xz32 = _mm_hadd_epi32(xz_madd_b, xz_madd_a); + // xz32 = [ae+bf+cg im+jn+ko 0 ei+fj+gk] i32 + *xz_sum_32 = _mm_add_epi32(*xz_sum_32, xz32); + + // Now calculate the straight sums, x_sum += a+b+c+e+f+g+i+j+k + // (sum up every element in slli_a and swap_b) + const __m128i sum_slli_a = _mm_hadd_epi16(slli_a, slli_a); + const __m128i sum_slli_a32 = _mm_cvtepi16_epi32(sum_slli_a); + // sum_slli_a32 = [c+b a k+j i] as i32 + const __m128i swap_b32 = _mm_cvtepu16_epi32(swap_b); + // swap_b32 = [g f e 0] as i32 + *x_sum_32 = _mm_add_epi32(*x_sum_32, sum_slli_a32); + *x_sum_32 = _mm_add_epi32(*x_sum_32, swap_b32); + // sum = [c+b+g a+f k+j+e i] as i32 + + // Also sum their squares + const __m128i slli_a_2 = _mm_madd_epi16(slli_a, slli_a); + const __m128i swap_b_2 = _mm_madd_epi16(swap_b, swap_b); + // slli_a_2 = [c2+b2 a2 k2+j2 i2] + // swap_b_2 = [0 0 g2+f2 e2] + const __m128i sum2 = _mm_hadd_epi32(slli_a_2, swap_b_2); + // sum2 = [0 g2+f2+e2 c2+b2+a2 k2+j2+i2] + *x2_sum_32 = _mm_add_epi32(*x2_sum_32, sum2); +} + +void av1_get_horver_correlation_full_sse4_1(const int16_t *diff, int stride, + int width, int height, float *hcorr, + float *vcorr) { + // The following notation is used: + // x - current pixel + // y - right neighbour pixel + // z - below neighbour pixel + // w - down-right neighbour pixel + int64_t xy_sum = 0, xz_sum = 0; + int64_t x_sum = 0, x2_sum = 0; + + // Process horizontal and vertical correlations through the body in 4x4 + // blocks. This excludes the final row and column and possibly one extra + // column depending how 3 divides into width and height + int32_t xy_tmp[4] = { 0 }, xz_tmp[4] = { 0 }; + int32_t x_tmp[4] = { 0 }, x2_tmp[4] = { 0 }; + __m128i xy_sum_32 = _mm_setzero_si128(); + __m128i xz_sum_32 = _mm_setzero_si128(); + __m128i x_sum_32 = _mm_setzero_si128(); + __m128i x2_sum_32 = _mm_setzero_si128(); + for (int i = 0; i <= height - 4; i += 3) { + for (int j = 0; j <= width - 4; j += 3) { + horver_correlation_4x4(&diff[i * stride + j], stride, &xy_sum_32, + &xz_sum_32, &x_sum_32, &x2_sum_32); + } + xx_storeu_128(xy_tmp, xy_sum_32); + xx_storeu_128(xz_tmp, xz_sum_32); + xx_storeu_128(x_tmp, x_sum_32); + xx_storeu_128(x2_tmp, x2_sum_32); + xy_sum += (int64_t)xy_tmp[3] + xy_tmp[2] + xy_tmp[1]; + xz_sum += (int64_t)xz_tmp[3] + xz_tmp[2] + xz_tmp[0]; + x_sum += (int64_t)x_tmp[3] + x_tmp[2] + x_tmp[1] + x_tmp[0]; + x2_sum += (int64_t)x2_tmp[2] + x2_tmp[1] + x2_tmp[0]; + xy_sum_32 = _mm_setzero_si128(); + xz_sum_32 = _mm_setzero_si128(); + x_sum_32 = _mm_setzero_si128(); + x2_sum_32 = _mm_setzero_si128(); + } + + // x_sum now covers every pixel except the final 1-2 rows and 1-2 cols + int64_t x_finalrow = 0, x_finalcol = 0, x2_finalrow = 0, x2_finalcol = 0; + + // Do we have 2 rows remaining or just the one? Note that width and height + // are powers of 2, so each modulo 3 must be 1 or 2. + if (height % 3 == 1) { // Just horiz corrs on the final row + const int16_t x0 = diff[(height - 1) * stride]; + x_sum += x0; + x_finalrow += x0; + x2_sum += x0 * x0; + x2_finalrow += x0 * x0; + for (int j = 0; j < width - 1; ++j) { + const int16_t x = diff[(height - 1) * stride + j]; + const int16_t y = diff[(height - 1) * stride + j + 1]; + xy_sum += x * y; + x_sum += y; + x2_sum += y * y; + x_finalrow += y; + x2_finalrow += y * y; + } + } else { // Two rows remaining to do + const int16_t x0 = diff[(height - 2) * stride]; + const int16_t z0 = diff[(height - 1) * stride]; + x_sum += x0 + z0; + x2_sum += x0 * x0 + z0 * z0; + x_finalrow += z0; + x2_finalrow += z0 * z0; + for (int j = 0; j < width - 1; ++j) { + const int16_t x = diff[(height - 2) * stride + j]; + const int16_t y = diff[(height - 2) * stride + j + 1]; + const int16_t z = diff[(height - 1) * stride + j]; + const int16_t w = diff[(height - 1) * stride + j + 1]; + + // Horizontal and vertical correlations for the penultimate row: + xy_sum += x * y; + xz_sum += x * z; + + // Now just horizontal correlations for the final row: + xy_sum += z * w; + + x_sum += y + w; + x2_sum += y * y + w * w; + x_finalrow += w; + x2_finalrow += w * w; + } + } + + // Do we have 2 columns remaining or just the one? + if (width % 3 == 1) { // Just vert corrs on the final col + const int16_t x0 = diff[width - 1]; + x_sum += x0; + x_finalcol += x0; + x2_sum += x0 * x0; + x2_finalcol += x0 * x0; + for (int i = 0; i < height - 1; ++i) { + const int16_t x = diff[i * stride + width - 1]; + const int16_t z = diff[(i + 1) * stride + width - 1]; + xz_sum += x * z; + x_finalcol += z; + x2_finalcol += z * z; + // So the bottom-right elements don't get counted twice: + if (i < height - (height % 3 == 1 ? 2 : 3)) { + x_sum += z; + x2_sum += z * z; + } + } + } else { // Two cols remaining + const int16_t x0 = diff[width - 2]; + const int16_t y0 = diff[width - 1]; + x_sum += x0 + y0; + x2_sum += x0 * x0 + y0 * y0; + x_finalcol += y0; + x2_finalcol += y0 * y0; + for (int i = 0; i < height - 1; ++i) { + const int16_t x = diff[i * stride + width - 2]; + const int16_t y = diff[i * stride + width - 1]; + const int16_t z = diff[(i + 1) * stride + width - 2]; + const int16_t w = diff[(i + 1) * stride + width - 1]; + + // Horizontal and vertical correlations for the penultimate col: + // Skip these on the last iteration of this loop if we also had two + // rows remaining, otherwise the final horizontal and vertical correlation + // get erroneously processed twice + if (i < height - 2 || height % 3 == 1) { + xy_sum += x * y; + xz_sum += x * z; + } + + x_finalcol += w; + x2_finalcol += w * w; + // So the bottom-right elements don't get counted twice: + if (i < height - (height % 3 == 1 ? 2 : 3)) { + x_sum += z + w; + x2_sum += z * z + w * w; + } + + // Now just vertical correlations for the final column: + xz_sum += y * w; + } + } + + // Calculate the simple sums and squared-sums + int64_t x_firstrow = 0, x_firstcol = 0; + int64_t x2_firstrow = 0, x2_firstcol = 0; + + for (int j = 0; j < width; ++j) { + x_firstrow += diff[j]; + x2_firstrow += diff[j] * diff[j]; + } + for (int i = 0; i < height; ++i) { + x_firstcol += diff[i * stride]; + x2_firstcol += diff[i * stride] * diff[i * stride]; + } + + int64_t xhor_sum = x_sum - x_finalcol; + int64_t xver_sum = x_sum - x_finalrow; + int64_t y_sum = x_sum - x_firstcol; + int64_t z_sum = x_sum - x_firstrow; + int64_t x2hor_sum = x2_sum - x2_finalcol; + int64_t x2ver_sum = x2_sum - x2_finalrow; + int64_t y2_sum = x2_sum - x2_firstcol; + int64_t z2_sum = x2_sum - x2_firstrow; + + const float num_hor = (float)(height * (width - 1)); + const float num_ver = (float)((height - 1) * width); + + const float xhor_var_n = x2hor_sum - (xhor_sum * xhor_sum) / num_hor; + const float xver_var_n = x2ver_sum - (xver_sum * xver_sum) / num_ver; + + const float y_var_n = y2_sum - (y_sum * y_sum) / num_hor; + const float z_var_n = z2_sum - (z_sum * z_sum) / num_ver; + + const float xy_var_n = xy_sum - (xhor_sum * y_sum) / num_hor; + const float xz_var_n = xz_sum - (xver_sum * z_sum) / num_ver; + + if (xhor_var_n > 0 && y_var_n > 0) { + *hcorr = xy_var_n / sqrtf(xhor_var_n * y_var_n); + *hcorr = *hcorr < 0 ? 0 : *hcorr; + } else { + *hcorr = 1.0; + } + if (xver_var_n > 0 && z_var_n > 0) { + *vcorr = xz_var_n / sqrtf(xver_var_n * z_var_n); + *vcorr = *vcorr < 0 ? 0 : *vcorr; + } else { + *vcorr = 1.0; + } +}
diff --git a/test/horver_correlation_test.cc b/test/horver_correlation_test.cc new file mode 100644 index 0000000..5fca4b6 --- /dev/null +++ b/test/horver_correlation_test.cc
@@ -0,0 +1,149 @@ +/* + * Copyright (c) 2018, 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 <vector> + +#include "third_party/googletest/src/googletest/include/gtest/gtest.h" + +#include "test/function_equivalence_test.h" +#include "test/register_state_check.h" + +#include "config/aom_config.h" +#include "config/aom_dsp_rtcd.h" +#include "config/av1_rtcd.h" + +#include "aom/aom_integer.h" +#include "av1/encoder/rdopt.h" + +using libaom_test::FunctionEquivalenceTest; + +namespace { +typedef void (*horver_Func)(const int16_t *diff, int stride, int w, int h, + float *hcorr, float *vcorr); + +typedef libaom_test::FuncParam<horver_Func> TestFuncs; + +typedef ::testing::tuple<const horver_Func> HorverTestParam; + +class HorverTest : public ::testing::TestWithParam<HorverTestParam> { + public: + virtual void SetUp() { + data_buf = (int16_t *)aom_malloc(MAX_SB_SQUARE * sizeof(int16_t)); + target_func_ = GET_PARAM(0); + } + virtual void TearDown() { aom_free(data_buf); } + void runHorverTest(void); + void runHorverTest_ExtremeValues(void); + void runHorverSpeedTest(int run_times); + + private: + horver_Func target_func_; + ACMRandom rng_; + int16_t *data_buf; +}; + +void HorverTest::runHorverTest(void) { + for (int block_size = 0; block_size < BLOCK_SIZES_ALL; block_size++) { + const int w = block_size_wide[block_size]; + const int h = block_size_high[block_size]; + for (int iter = 0; iter < 1000 && !HasFatalFailure(); ++iter) { + float hcorr_ref = 0.0, vcorr_ref = 0.0; + float hcorr_test = 0.0, vcorr_test = 0.0; + + for (int i = 0; i < MAX_SB_SQUARE; ++i) { + data_buf[i] = rng_.Rand16() % (1 << 12); + } + + av1_get_horver_correlation_full_c(data_buf, MAX_SB_SIZE, w, h, &hcorr_ref, + &vcorr_ref); + + target_func_(data_buf, MAX_SB_SIZE, w, h, &hcorr_test, &vcorr_test); + + ASSERT_LE(fabs(hcorr_ref - hcorr_test), 1e-6) + << "hcorr incorrect (" << w << "x" << h << ")"; + ASSERT_LE(fabs(vcorr_ref - vcorr_test), 1e-6) + << "vcorr incorrect (" << w << "x" << h << ")"; + } + // printf("(%3dx%-3d) passed\n", w, h); + } +} + +void HorverTest::runHorverSpeedTest(int run_times) { + for (int i = 0; i < MAX_SB_SQUARE; ++i) { + data_buf[i] = rng_.Rand16() % (1 << 12); + } + + for (int block_size = 0; block_size < BLOCK_SIZES_ALL; block_size++) { + const int w = block_size_wide[block_size]; + const int h = block_size_high[block_size]; + float hcorr_ref = 0.0, vcorr_ref = 0.0; + float hcorr_test = 0.0, vcorr_test = 0.0; + + aom_usec_timer timer; + aom_usec_timer_start(&timer); + for (int i = 0; i < run_times; ++i) { + av1_get_horver_correlation_full_c(data_buf, MAX_SB_SIZE, w, h, &hcorr_ref, + &vcorr_ref); + } + aom_usec_timer_mark(&timer); + const double time1 = static_cast<double>(aom_usec_timer_elapsed(&timer)); + aom_usec_timer_start(&timer); + for (int i = 0; i < run_times; ++i) { + target_func_(data_buf, MAX_SB_SIZE, w, h, &hcorr_test, &vcorr_test); + } + aom_usec_timer_mark(&timer); + const double time2 = static_cast<double>(aom_usec_timer_elapsed(&timer)); + + printf("%3dx%-3d:%7.2f/%7.2fns (%3.2f)\n", w, h, time1, time2, + time1 / time2); + } +} + +void HorverTest::runHorverTest_ExtremeValues(void) { + for (int i = 0; i < MAX_SB_SQUARE; ++i) { + // Most of get_horver_test is squaring and summing, so simply saturating + // the whole buffer is mostly likely to cause an overflow. + data_buf[i] = (1 << 12) - 1; + } + + for (int block_size = 0; block_size < BLOCK_SIZES_ALL; block_size++) { + const int w = block_size_wide[block_size]; + const int h = block_size_high[block_size]; + float hcorr_ref = 0.0, vcorr_ref = 0.0; + float hcorr_test = 0.0, vcorr_test = 0.0; + + av1_get_horver_correlation_full_c(data_buf, MAX_SB_SIZE, w, h, &hcorr_ref, + &vcorr_ref); + target_func_(data_buf, MAX_SB_SIZE, w, h, &hcorr_test, &vcorr_test); + + ASSERT_LE(fabs(hcorr_ref - hcorr_test), 1e-6) << "hcorr incorrect"; + ASSERT_LE(fabs(vcorr_ref - vcorr_test), 1e-6) << "vcorr incorrect"; + } +} + +TEST_P(HorverTest, RandomValues) { runHorverTest(); } + +TEST_P(HorverTest, ExtremeValues) { runHorverTest_ExtremeValues(); } + +TEST_P(HorverTest, DISABLED_Speed) { runHorverSpeedTest(100000); } + +#if HAVE_SSE4_1 +INSTANTIATE_TEST_CASE_P( + SSE4_1, HorverTest, + ::testing::Values(av1_get_horver_correlation_full_sse4_1)); +#endif // HAVE_SSE4_1 + +#if HAVE_AVX2 +INSTANTIATE_TEST_CASE_P( + AVX2, HorverTest, ::testing::Values(av1_get_horver_correlation_full_avx2)); +#endif // HAVE_AVX2 + +} // namespace
diff --git a/test/test.cmake b/test/test.cmake index 513a0f1..d15e580 100644 --- a/test/test.cmake +++ b/test/test.cmake
@@ -184,6 +184,7 @@ "${AOM_ROOT}/test/error_block_test.cc" "${AOM_ROOT}/test/fft_test.cc" "${AOM_ROOT}/test/fwht4x4_test.cc" + "${AOM_ROOT}/test/horver_correlation_test.cc" "${AOM_ROOT}/test/masked_sad_test.cc" "${AOM_ROOT}/test/masked_variance_test.cc" "${AOM_ROOT}/test/motion_vector_test.cc"