I just landed the first 6 patches as well as a fix for one intel compiler
bug uncovered by the series. You can go ahead and rebase your former
series. If you feel the need for a separate 32-bit version of
compute_fast_udiv_info, I'll happily reivew the patch.
--Jason
On Mon, Oct 8, 2018 at 11:11 AM Jason Ekstrand <ja...@jlekstrand.net> wrote:
> On Sat, Oct 6, 2018 at 1:52 PM Marek Olšák <mar...@gmail.com> wrote:
>
>> With my comments addressed, patches 2 - 6 are:
>>
>> Reviewed-by: Marek Olšák <marek.ol...@amd.com>
>>
>
> Thanks! Unfortunately, the tests require patch 1 so it'd be nice if that
> got review by someone. I'd also be happy to pull in someone else's more
> vetted code for large integer multiplication but I had trouble finding any
> that was liberally lisenced. Maybe I just didn't look hard enough?
>
>
>> Since I will need to compute the division terms during draw calls, I
>> may need to switch the math to uint32_t for my case (e.g. via a C++
>> template).
>>
>
> There's very little change in the 32 vs. 64-bit versions but if you're
> worried about the 64-bit arithmetic, it'd be easy enough to have a version
> that does 32-bit arithmetic and only use the 64-bit version when actually
> needed.
>
> --Jason
>
>
>> Marek
>>
>> On Sat, Oct 6, 2018 at 12:11 AM Jason Ekstrand <ja...@jlekstrand.net>
>> wrote:
>> >> While I generally trust rediculousfish to have done his homework, we've
>> > made some adjustments to suite the needs of mesa and it'd be good to
>> > test those. Also, there's no better place than unit tests to clearly
>> > document the different edge cases of the different methods.
>> > ---
>> > configure.ac | 1 +
>> > src/util/Makefile.am | 3 +-
>> > src/util/meson.build | 1 +
>> > src/util/tests/fast_idiv_by_const/Makefile.am | 43 ++
>> > .../fast_idiv_by_const_test.cpp | 472 ++++++++++++++++++
>> > src/util/tests/fast_idiv_by_const/meson.build | 30 ++
>> > 6 files changed, 549 insertions(+), 1 deletion(-)
>> > create mode 100644 src/util/tests/fast_idiv_by_const/Makefile.am
>> > create mode 100644
>> src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp
>> > create mode 100644 src/util/tests/fast_idiv_by_const/meson.build
>> >
>> > diff --git a/configure.ac b/configure.ac
>> > index 34689826c98..7b0b2b20ba2 100644
>> > --- a/configure.ac
>> > +++ b/configure.ac
>> > @@ -3198,6 +3198,7 @@ AC_CONFIG_FILES([Makefile
>> > src/util/tests/hash_table/Makefile
>> > src/util/tests/set/Makefile
>> > src/util/tests/string_buffer/Makefile
>> > + src/util/tests/uint_inverse/Makefile
>> > src/util/tests/vma/Makefile
>> > src/util/xmlpool/Makefile
>> > src/vulkan/Makefile])
>> > diff --git a/src/util/Makefile.am b/src/util/Makefile.am
>> > index d79f2b320be..9e633bf65d5 100644
>> > --- a/src/util/Makefile.am
>> > +++ b/src/util/Makefile.am
>> > @@ -24,7 +24,8 @@ SUBDIRS = . \
>> > tests/fast_idiv_by_const \
>> > tests/hash_table \
>> > tests/string_buffer \
>> > - tests/set
>> > + tests/set \
>> > + tests/uint_inverse
>> >
>> > if HAVE_STD_CXX11
>> > SUBDIRS += tests/vma
>> > 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..34b149e1c6f
>> > --- /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(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],
>> > + )
>> > +)
>> > --
>> > 2.19.0
>> >
>> > _______________________________________________
>> > mesa-dev mailing list
>> > mesa-dev@lists.freedesktop.org
>> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
>>
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
