diff options
| -rw-r--r-- | configure.ac | 1 | ||||
| -rw-r--r-- | src/util/meson.build | 1 | ||||
| -rw-r--r-- | src/util/tests/fast_idiv_by_const/Makefile.am | 43 | ||||
| -rw-r--r-- | src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp | 472 | ||||
| -rw-r--r-- | src/util/tests/fast_idiv_by_const/meson.build | 30 |
5 files changed, 547 insertions, 0 deletions
diff --git a/configure.ac b/configure.ac index 34689826c98..520948b0518 100644 --- a/configure.ac +++ b/configure.ac @@ -3195,6 +3195,7 @@ AC_CONFIG_FILES([Makefile src/mesa/main/tests/Makefile src/mesa/state_tracker/tests/Makefile src/util/Makefile + src/util/tests/fast_idiv_by_const/Makefile src/util/tests/hash_table/Makefile src/util/tests/set/Makefile src/util/tests/string_buffer/Makefile diff --git a/src/util/meson.build b/src/util/meson.build index cdbad98e7cb..49d84c16ebe 100644 --- a/src/util/meson.build +++ b/src/util/meson.build @@ -170,6 +170,7 @@ if with_tests ) ) + subdir('tests/fast_idiv_by_const') subdir('tests/hash_table') subdir('tests/string_buffer') subdir('tests/vma') diff --git a/src/util/tests/fast_idiv_by_const/Makefile.am b/src/util/tests/fast_idiv_by_const/Makefile.am new file mode 100644 index 00000000000..1ebee09f59b --- /dev/null +++ b/src/util/tests/fast_idiv_by_const/Makefile.am @@ -0,0 +1,43 @@ +# Copyright © 2018 Intel +# +# Permission is hereby granted, free of charge, to any person obtaining a +# copy of this software and associated documentation files (the "Software"), +# to deal in the Software without restriction, including without limitation +# the rights to use, copy, modify, merge, publish, distribute, sublicense, +# and/or sell copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice (including the next +# paragraph) shall be included in all copies or substantial portions of the +# Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +# IN THE SOFTWARE. + +AM_CPPFLAGS = \ + -I$(top_srcdir)/src \ + -I$(top_srcdir)/include \ + -I$(top_srcdir)/src/gallium/include \ + -I$(top_srcdir)/src/gtest/include \ + $(PTHREAD_CFLAGS) \ + $(DEFINES) + +TESTS = fast_idiv_by_const_test + +check_PROGRAMS = $(TESTS) + +fast_idiv_by_const_test_SOURCES = \ + fast_idiv_by_const_test.cpp + +fast_idiv_by_const_test_LDADD = \ + $(top_builddir)/src/gtest/libgtest.la \ + $(top_builddir)/src/util/libmesautil.la \ + $(PTHREAD_LIBS) \ + $(DLOPEN_LIBS) + +EXTRA_DIST = meson.build diff --git a/src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp b/src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp new file mode 100644 index 00000000000..3983a39edda --- /dev/null +++ b/src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp @@ -0,0 +1,472 @@ +/* + * Copyright © 2018 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include <gtest/gtest.h> +#include "util/bigmath.h" +#include "util/fast_idiv_by_const.h" +#include "util/u_math.h" + +#define RAND_TEST_ITERATIONS 100000 + +#define MAX_UINT(bits) \ + (((bits) == 64) ? UINT64_MAX : ((1ull << (bits)) - 1)) + +static inline uint64_t +utrunc(uint64_t x, unsigned num_bits) +{ + if (num_bits == 64) + return x; + + return (x << (64 - num_bits)) >> (64 - num_bits); +} + +static inline int64_t +strunc(int64_t x, unsigned num_bits) +{ + if (num_bits == 64) + return x; + + return (x << (64 - num_bits)) >> (64 - num_bits); +} + +static inline bool +uint_is_in_range(uint64_t x, unsigned num_bits) +{ + if (num_bits == 64) + return true; + + return x < (1ull << num_bits); +} + +static inline bool +sint_is_in_range(int64_t x, unsigned num_bits) +{ + if (num_bits == 64) + return true; + + return x >= -(1ll << (num_bits - 1)) && + x < (1ll << (num_bits - 1)); +} + +static inline uint64_t +uadd_sat(uint64_t a, uint64_t b, unsigned num_bits) +{ + assert(uint_is_in_range(a, num_bits)); + assert(uint_is_in_range(b, num_bits)); + + uint64_t sum = a + b; + if (num_bits == 64) { + /* Standard overflow check */ + return sum < a ? UINT64_MAX : sum; + } else { + /* Check if sum is more than num_bits */ + return (sum >> num_bits) ? MAX_UINT(num_bits) : sum; + } +} + +static inline uint64_t +umul_add_high(uint64_t a, uint64_t b, uint64_t c, unsigned num_bits) +{ + assert(uint_is_in_range(a, num_bits)); + assert(uint_is_in_range(b, num_bits)); + assert(uint_is_in_range(c, num_bits)); + + if (num_bits == 64) { + uint32_t a32[2] = { (uint32_t)a, (uint32_t)(a >> 32) }; + uint32_t b32[2] = { (uint32_t)b, (uint32_t)(b >> 32) }; + uint32_t c32[2] = { (uint32_t)c, (uint32_t)(c >> 32) }; + + uint32_t ab32[4]; + ubm_mul_u32arr(ab32, a32, b32); + + uint32_t abc32[4]; + ubm_add_u32arr(abc32, ab32, c32); + + return abc32[2] | ((uint64_t)abc32[3] << 32); + } else { + assert(num_bits <= 32); + return utrunc(((a * b) + c) >> num_bits, num_bits); + } +} + +static inline int64_t +smul_high(int64_t a, int64_t b, unsigned num_bits) +{ + assert(sint_is_in_range(a, num_bits)); + assert(sint_is_in_range(b, num_bits)); + + if (num_bits == 64) { + uint32_t a32[4] = { + (uint32_t)a, + (uint32_t)(a >> 32), + (uint32_t)(a >> 63), /* sign extend */ + (uint32_t)(a >> 63), /* sign extend */ + }; + uint32_t b32[4] = { + (uint32_t)b, + (uint32_t)(b >> 32), + (uint32_t)(b >> 63), /* sign extend */ + (uint32_t)(b >> 63), /* sign extend */ + }; + + uint32_t ab32[4]; + ubm_mul_u32arr(ab32, a32, b32); + + return ab32[2] | ((uint64_t)ab32[3] << 32); + } else { + assert(num_bits <= 32); + return strunc((a * b) >> num_bits, num_bits); + } +} + +static inline uint64_t +fast_udiv_add_sat(uint64_t n, struct util_fast_udiv_info m, unsigned num_bits) +{ + assert(uint_is_in_range(n, num_bits)); + assert(uint_is_in_range(m.multiplier, num_bits)); + + n = n >> m.pre_shift; + n = uadd_sat(n, m.increment, num_bits); + n = umul_add_high(n, m.multiplier, 0, num_bits); + n = n >> m.post_shift; + + return n; +} + +static inline uint64_t +fast_udiv_mul_add(uint64_t n, struct util_fast_udiv_info m, unsigned num_bits) +{ + assert(uint_is_in_range(n, num_bits)); + assert(uint_is_in_range(m.multiplier, num_bits)); + + n = n >> m.pre_shift; + n = umul_add_high(n, m.multiplier, + m.increment ? m.multiplier : 0, + num_bits); + n = n >> m.post_shift; + + return n; +} + +static inline uint64_t +fast_sdiv(int64_t n, int64_t d, struct util_fast_sdiv_info m, unsigned num_bits) +{ + assert(sint_is_in_range(n, num_bits)); + assert(sint_is_in_range(d, num_bits)); + assert(sint_is_in_range(m.multiplier, num_bits)); + + int64_t res; + res = smul_high(n, m.multiplier, num_bits); + if (d > 0 && m.multiplier < 0) + res = strunc(res + n, num_bits); + if (d < 0 && m.multiplier > 0) + res = strunc(res - n, num_bits); + res = res >> m.shift; + res = res - (res >> (num_bits - 1)); + + return res; +} + +static uint64_t +rand_uint(unsigned bits, unsigned min) +{ + assert(bits >= 4); + + /* Make sure we get some small and large numbers and powers of two every + * once in a while + */ + int k = rand() % 64; + if (k == 17) { + return min + (rand() % 16); + } else if (k == 42) { + return MAX_UINT(bits) - (rand() % 16); + } else if (k == 9) { + uint64_t r; + do { + r = 1ull << (rand() % bits); + } while (r < min); + return r; + } + + if (min == 0) { + assert(bits <= 64); + uint64_t r = 0; + for (unsigned i = 0; i < 8; i++) + r |= ((uint64_t)rand() & 0xf) << i * 8; + return r >> (63 - (rand() % bits)); + } else { + uint64_t r; + do { + r = rand_uint(bits, 0); + } while (r < min); + return r; + } +} + +static int64_t +rand_sint(unsigned bits, unsigned min_abs) +{ + /* Make sure we hit MIN_INT every once in a while */ + if (rand() % 64 == 37) + return -(1 << (bits - 1)); + + int64_t s = rand_uint(bits - 1, min_abs); + return rand() & 1 ? s : -s; +} + +static uint64_t +udiv(uint64_t a, uint64_t b, unsigned bit_size) +{ + switch (bit_size) { + case 64: return (uint64_t)a / (uint64_t)b; + case 32: return (uint32_t)a / (uint32_t)b; + case 16: return (uint16_t)a / (uint16_t)b; + case 8: return (uint8_t)a / (uint8_t)b; + default: + assert(!"Invalid bit size"); + return 0; + } +} + +static int64_t +sdiv(int64_t a, int64_t b, unsigned bit_size) +{ + switch (bit_size) { + case 64: return (int64_t)a / (int64_t)b; + case 32: return (int32_t)a / (int32_t)b; + case 16: return (int16_t)a / (int16_t)b; + case 8: return (int8_t)a / (int8_t)b; + default: + assert(!"Invalid bit size"); + return 0; + } +} + +static void +random_udiv_add_sat_test(unsigned bits, bool bounded) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + uint64_t n = rand_uint(bits, 0); + uint64_t d = rand_uint(bits, 2); + assert(uint_is_in_range(n, bits)); + assert(uint_is_in_range(d, bits) && d >= 2); + + unsigned n_bits = bounded ? util_logbase2_64(MAX2(n, 1)) + 1 : bits; + + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, n_bits, bits); + EXPECT_EQ(fast_udiv_add_sat(n, m, bits), udiv(n, d, bits)); + } +} + +static void +random_udiv_mul_add_test(unsigned bits, bool bounded) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + uint64_t n = rand_uint(bits, 0); + uint64_t d = rand_uint(bits, 1); + assert(uint_is_in_range(n, bits)); + assert(uint_is_in_range(d, bits) && d >= 1); + + unsigned n_bits = bounded ? util_logbase2_64(MAX2(n, 1)) + 1: bits; + + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, n_bits, bits); + EXPECT_EQ(fast_udiv_mul_add(n, m, bits), udiv(n, d, bits)); + } +} + +static void +random_sdiv_test(unsigned bits) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + int64_t n = rand_sint(bits, 0); + int64_t d; + do { + d = rand_sint(bits, 2); + } while (util_is_power_of_two_or_zero64(llabs(d))); + + assert(sint_is_in_range(n, bits)); + assert(sint_is_in_range(d, bits) && llabs(d) >= 2); + + struct util_fast_sdiv_info m = + util_compute_fast_sdiv_info(d, bits); + EXPECT_EQ(fast_sdiv(n, d, m, bits), sdiv(n, d, bits)); + } +} + +TEST(fast_idiv_by_const, uint8_add_sat) +{ + /* 8-bit is small enough we can brute-force the entire space */ + for (unsigned d = 2; d < 256; d++) { + for (unsigned n_bits = 1; n_bits <= 8; n_bits++) { + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, n_bits, 8); + + for (unsigned n = 0; n < (1u << n_bits); n++) + EXPECT_EQ(fast_udiv_add_sat(n, m, 8), udiv(n, d, 8)); + } + } +} + +TEST(fast_idiv_by_const, uint8_mul_add) +{ + /* 8-bit is small enough we can brute-force the entire space */ + for (unsigned d = 2; d < 256; d++) { + for (unsigned n_bits = 1; n_bits <= 8; n_bits++) { + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, n_bits, 8); + + for (unsigned n = 0; n < (1u << n_bits); n++) + EXPECT_EQ(fast_udiv_mul_add(n, m, 8), udiv(n, d, 8)); + } + } +} + +TEST(fast_idiv_by_const, int8) +{ + /* 8-bit is small enough we can brute-force the entire space */ + for (int n = -128; n < 128; n++) { + for (int d = -128; d < 128; d++) { + if (util_is_power_of_two_or_zero(abs(d))) + continue; + + struct util_fast_sdiv_info m = + util_compute_fast_sdiv_info(d, 8); + EXPECT_EQ(fast_sdiv(n, d, m, 8), sdiv(n, d, 8)); + } + } +} + +TEST(fast_idiv_by_const, uint16_add_sat_bounded) +{ + random_udiv_add_sat_test(16, true); +} + +TEST(fast_idiv_by_const, uint16_add_sat_full) +{ + random_udiv_add_sat_test(16, false); +} + +TEST(fast_idiv_by_const, uint16_mul_add_bounded) +{ + random_udiv_mul_add_test(16, true); +} + +TEST(fast_idiv_by_const, uint16_mul_add_full) +{ + random_udiv_mul_add_test(16, false); +} + +TEST(fast_idiv_by_const, int16) +{ + random_sdiv_test(16); +} + +TEST(fast_idiv_by_const, uint32_add_sat_bounded) +{ + random_udiv_add_sat_test(32, true); +} + +TEST(fast_idiv_by_const, uint32_add_sat_full) +{ + random_udiv_add_sat_test(32, false); +} + +TEST(fast_idiv_by_const, uint32_mul_add_bounded) +{ + random_udiv_mul_add_test(32, true); +} + +TEST(fast_idiv_by_const, uint32_mul_add_full) +{ + random_udiv_mul_add_test(32, false); +} + +TEST(fast_idiv_by_const, int32) +{ + random_sdiv_test(32); +} + +TEST(fast_idiv_by_const, util_fast_udiv32) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + uint32_t n = rand_uint(32, 0); + uint32_t d = rand_uint(32, 1); + + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, 32, 32); + EXPECT_EQ(util_fast_udiv32(n, m), n / d); + } +} + +TEST(fast_idiv_by_const, util_fast_udiv32_nuw) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + uint32_t n = rand_uint(32, 0); + if (n == UINT32_MAX) + continue; + uint32_t d = rand_uint(32, 1); + + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, 32, 32); + EXPECT_EQ(util_fast_udiv32_nuw(n, m), n / d); + } +} + +TEST(fast_idiv_by_const, util_fast_udiv32_u31_d_not_one) +{ + for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) { + uint32_t n = rand_uint(31, 0); + uint32_t d = rand_uint(31, 2); + + struct util_fast_udiv_info m = + util_compute_fast_udiv_info(d, 31, 32); + EXPECT_EQ(util_fast_udiv32_u31_d_not_one(n, m), n / d); + } +} + +TEST(fast_idiv_by_const, uint64_add_sat_bounded) +{ + random_udiv_add_sat_test(64, true); +} + +TEST(fast_idiv_by_const, uint64_add_sat_full) +{ + random_udiv_add_sat_test(64, false); +} + +TEST(fast_idiv_by_const, uint64_mul_add_bounded) +{ + random_udiv_mul_add_test(64, true); +} + +TEST(fast_idiv_by_const, uint64_mul_add_full) +{ + random_udiv_mul_add_test(64, false); +} + +TEST(fast_idiv_by_const, int64) +{ + random_sdiv_test(64); +} diff --git a/src/util/tests/fast_idiv_by_const/meson.build b/src/util/tests/fast_idiv_by_const/meson.build new file mode 100644 index 00000000000..8c3b79493ff --- /dev/null +++ b/src/util/tests/fast_idiv_by_const/meson.build @@ -0,0 +1,30 @@ +# Copyright © 2018 Intel Corporation + +# Permission is hereby granted, free of charge, to any person obtaining a copy +# of this software and associated documentation files (the "Software"), to deal +# in the Software without restriction, including without limitation the rights +# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the Software is +# furnished to do so, subject to the following conditions: + +# The above copyright notice and this permission notice shall be included in +# all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +# SOFTWARE. + +test( + 'fast_idiv_by_const', + executable( + 'fast_idiv_by_const_test', + 'fast_idiv_by_const_test.cpp', + dependencies : [dep_thread, dep_dl, idep_gtest], + include_directories : inc_common, + link_with : [libmesa_util], + ) +) |