<div dir="ltr"><div>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.</div><div><br></div><div>--Jason<br></div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Oct 8, 2018 at 11:11 AM Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Sat, Oct 6, 2018 at 1:52 PM Marek Olšák <<a href="mailto:maraeo@gmail.com" target="_blank">maraeo@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">With my comments addressed, patches 2 - 6 are:<br>
<br>
Reviewed-by: Marek Olšák <<a href="mailto:marek.olsak@amd.com" target="_blank">marek.olsak@amd.com</a>><br></blockquote><div><br></div><div>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?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Since I will need to compute the division terms during draw calls, I<br>
may need to switch the math to uint32_t for my case (e.g. via a C++<br>
template).<br></blockquote><div><br></div><div>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.</div><div><br></div><div>--Jason<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Marek<br>
<br>
On Sat, Oct 6, 2018 at 12:11 AM Jason Ekstrand <<a href="mailto:jason@jlekstrand.net" target="_blank">jason@jlekstrand.net</a>> wrote:<br>
>> While I generally trust rediculousfish to have done his homework, we've<br>
> made some adjustments to suite the needs of mesa and it'd be good to<br>
> test those.  Also, there's no better place than unit tests to clearly<br>
> document the different edge cases of the different methods.<br>
> ---<br>
>  <a href="http://configure.ac" rel="noreferrer" target="_blank">configure.ac</a>                                  |   1 +<br>
>  src/util/Makefile.am                          |   3 +-<br>
>  src/util/meson.build                          |   1 +<br>
>  src/util/tests/fast_idiv_by_const/Makefile.am |  43 ++<br>
>  .../fast_idiv_by_const_test.cpp               | 472 ++++++++++++++++++<br>
>  src/util/tests/fast_idiv_by_const/meson.build |  30 ++<br>
>  6 files changed, 549 insertions(+), 1 deletion(-)<br>
>  create mode 100644 src/util/tests/fast_idiv_by_const/Makefile.am<br>
>  create mode 100644 src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp<br>
>  create mode 100644 src/util/tests/fast_idiv_by_const/meson.build<br>
><br>
> diff --git a/<a href="http://configure.ac" rel="noreferrer" target="_blank">configure.ac</a> b/<a href="http://configure.ac" rel="noreferrer" target="_blank">configure.ac</a><br>
> index 34689826c98..7b0b2b20ba2 100644<br>
> --- a/<a href="http://configure.ac" rel="noreferrer" target="_blank">configure.ac</a><br>
> +++ b/<a href="http://configure.ac" rel="noreferrer" target="_blank">configure.ac</a><br>
> @@ -3198,6 +3198,7 @@ AC_CONFIG_FILES([Makefile<br>
>                   src/util/tests/hash_table/Makefile<br>
>                   src/util/tests/set/Makefile<br>
>                   src/util/tests/string_buffer/Makefile<br>
> +                 src/util/tests/uint_inverse/Makefile<br>
>                   src/util/tests/vma/Makefile<br>
>                   src/util/xmlpool/Makefile<br>
>                   src/vulkan/Makefile])<br>
> diff --git a/src/util/Makefile.am b/src/util/Makefile.am<br>
> index d79f2b320be..9e633bf65d5 100644<br>
> --- a/src/util/Makefile.am<br>
> +++ b/src/util/Makefile.am<br>
> @@ -24,7 +24,8 @@ SUBDIRS = . \<br>
>         tests/fast_idiv_by_const \<br>
>         tests/hash_table \<br>
>         tests/string_buffer \<br>
> -       tests/set<br>
> +       tests/set \<br>
> +       tests/uint_inverse<br>
><br>
>  if HAVE_STD_CXX11<br>
>  SUBDIRS += tests/vma<br>
> diff --git a/src/util/meson.build b/src/util/meson.build<br>
> index cdbad98e7cb..49d84c16ebe 100644<br>
> --- a/src/util/meson.build<br>
> +++ b/src/util/meson.build<br>
> @@ -170,6 +170,7 @@ if with_tests<br>
>      )<br>
>    )<br>
><br>
> +  subdir('tests/fast_idiv_by_const')<br>
>    subdir('tests/hash_table')<br>
>    subdir('tests/string_buffer')<br>
>    subdir('tests/vma')<br>
> diff --git a/src/util/tests/fast_idiv_by_const/Makefile.am b/src/util/tests/fast_idiv_by_const/Makefile.am<br>
> new file mode 100644<br>
> index 00000000000..1ebee09f59b<br>
> --- /dev/null<br>
> +++ b/src/util/tests/fast_idiv_by_const/Makefile.am<br>
> @@ -0,0 +1,43 @@<br>
> +# Copyright © 2018 Intel<br>
> +#<br>
> +#  Permission is hereby granted, free of charge, to any person obtaining a<br>
> +#  copy of this software and associated documentation files (the "Software"),<br>
> +#  to deal in the Software without restriction, including without limitation<br>
> +#  the rights to use, copy, modify, merge, publish, distribute, sublicense,<br>
> +#  and/or sell copies of the Software, and to permit persons to whom the<br>
> +#  Software is furnished to do so, subject to the following conditions:<br>
> +#<br>
> +#  The above copyright notice and this permission notice (including the next<br>
> +#  paragraph) shall be included in all copies or substantial portions of the<br>
> +#  Software.<br>
> +#<br>
> +#  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
> +#  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
> +#  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL<br>
> +#  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
> +#  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING<br>
> +#  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS<br>
> +#  IN THE SOFTWARE.<br>
> +<br>
> +AM_CPPFLAGS = \<br>
> +       -I$(top_srcdir)/src \<br>
> +       -I$(top_srcdir)/include \<br>
> +       -I$(top_srcdir)/src/gallium/include \<br>
> +       -I$(top_srcdir)/src/gtest/include \<br>
> +       $(PTHREAD_CFLAGS) \<br>
> +       $(DEFINES)<br>
> +<br>
> +TESTS = fast_idiv_by_const_test<br>
> +<br>
> +check_PROGRAMS = $(TESTS)<br>
> +<br>
> +fast_idiv_by_const_test_SOURCES = \<br>
> +       fast_idiv_by_const_test.cpp<br>
> +<br>
> +fast_idiv_by_const_test_LDADD = \<br>
> +       $(top_builddir)/src/gtest/<a href="http://libgtest.la" rel="noreferrer" target="_blank">libgtest.la</a> \<br>
> +       $(top_builddir)/src/util/<a href="http://libmesautil.la" rel="noreferrer" target="_blank">libmesautil.la</a> \<br>
> +       $(PTHREAD_LIBS) \<br>
> +       $(DLOPEN_LIBS)<br>
> +<br>
> +EXTRA_DIST = meson.build<br>
> 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<br>
> new file mode 100644<br>
> index 00000000000..34b149e1c6f<br>
> --- /dev/null<br>
> +++ b/src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp<br>
> @@ -0,0 +1,472 @@<br>
> +/*<br>
> + * Copyright © 2018 Intel Corporation<br>
> + *<br>
> + * Permission is hereby granted, free of charge, to any person obtaining a<br>
> + * copy of this software and associated documentation files (the "Software"),<br>
> + * to deal in the Software without restriction, including without limitation<br>
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,<br>
> + * and/or sell copies of the Software, and to permit persons to whom the<br>
> + * Software is furnished to do so, subject to the following conditions:<br>
> + *<br>
> + * The above copyright notice and this permission notice (including the next<br>
> + * paragraph) shall be included in all copies or substantial portions of the<br>
> + * Software.<br>
> + *<br>
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL<br>
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING<br>
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS<br>
> + * IN THE SOFTWARE.<br>
> + */<br>
> +<br>
> +#include <gtest/gtest.h><br>
> +#include "util/bigmath.h"<br>
> +#include "util/fast_idiv_by_const.h"<br>
> +#include "util/u_math.h"<br>
> +<br>
> +#define RAND_TEST_ITERATIONS 100000<br>
> +<br>
> +#define MAX_UINT(bits) \<br>
> +   (((bits) == 64) ? UINT64_MAX : ((1ull << (bits)) - 1))<br>
> +<br>
> +static inline uint64_t<br>
> +utrunc(uint64_t x, unsigned num_bits)<br>
> +{<br>
> +   if (num_bits == 64)<br>
> +      return x;<br>
> +<br>
> +   return (x << (64 - num_bits)) >> (64 - num_bits);<br>
> +}<br>
> +<br>
> +static inline int64_t<br>
> +strunc(int64_t x, unsigned num_bits)<br>
> +{<br>
> +   if (num_bits == 64)<br>
> +      return x;<br>
> +<br>
> +   return (x << (64 - num_bits)) >> (64 - num_bits);<br>
> +}<br>
> +<br>
> +static inline bool<br>
> +uint_is_in_range(uint64_t x, unsigned num_bits)<br>
> +{<br>
> +   if (num_bits == 64)<br>
> +      return true;<br>
> +<br>
> +   return x < (1ull << num_bits);<br>
> +}<br>
> +<br>
> +static inline bool<br>
> +sint_is_in_range(int64_t x, unsigned num_bits)<br>
> +{<br>
> +   if (num_bits == 64)<br>
> +      return true;<br>
> +<br>
> +   return x >= -(1ll << (num_bits - 1)) &&<br>
> +          x < (1ll << (num_bits - 1));<br>
> +}<br>
> +<br>
> +static inline uint64_t<br>
> +uadd_sat(uint64_t a, uint64_t b, unsigned num_bits)<br>
> +{<br>
> +   assert(uint_is_in_range(a, num_bits));<br>
> +   assert(uint_is_in_range(b, num_bits));<br>
> +<br>
> +   uint64_t sum = a + b;<br>
> +   if (num_bits == 64) {<br>
> +      /* Standard overflow check */<br>
> +      return sum < a ? UINT64_MAX : sum;<br>
> +   } else {<br>
> +      /* Check if sum is more than num_bits */<br>
> +      return (sum >> num_bits) ? MAX_UINT(num_bits) : sum;<br>
> +   }<br>
> +}<br>
> +<br>
> +static inline uint64_t<br>
> +umul_add_high(uint64_t a, uint64_t b, uint64_t c, unsigned num_bits)<br>
> +{<br>
> +   assert(uint_is_in_range(a, num_bits));<br>
> +   assert(uint_is_in_range(b, num_bits));<br>
> +   assert(uint_is_in_range(c, num_bits));<br>
> +<br>
> +   if (num_bits == 64) {<br>
> +      uint32_t a32[2] = { (uint32_t)a, (uint32_t)(a >> 32) };<br>
> +      uint32_t b32[2] = { (uint32_t)b, (uint32_t)(b >> 32) };<br>
> +      uint32_t c32[2] = { (uint32_t)c, (uint32_t)(c >> 32) };<br>
> +<br>
> +      uint32_t ab32[4];<br>
> +      ubm_mul_u32arr(ab32, a32, b32);<br>
> +<br>
> +      uint32_t abc32[4];<br>
> +      ubm_add_u32arr(abc32, ab32, c32);<br>
> +<br>
> +      return abc32[2] | ((uint64_t)abc32[3] << 32);<br>
> +   } else {<br>
> +      assert(num_bits <= 32);<br>
> +      return utrunc(((a * b) + c) >> num_bits, num_bits);<br>
> +   }<br>
> +}<br>
> +<br>
> +static inline int64_t<br>
> +smul_high(int64_t a, int64_t b, unsigned num_bits)<br>
> +{<br>
> +   assert(sint_is_in_range(a, num_bits));<br>
> +   assert(sint_is_in_range(b, num_bits));<br>
> +<br>
> +   if (num_bits == 64) {<br>
> +      uint32_t a32[4] = {<br>
> +         (uint32_t)a,<br>
> +         (uint32_t)(a >> 32),<br>
> +         (uint32_t)(a >> 63), /* sign extend */<br>
> +         (uint32_t)(a >> 63), /* sign extend */<br>
> +      };<br>
> +      uint32_t b32[4] = {<br>
> +         (uint32_t)b,<br>
> +         (uint32_t)(b >> 32),<br>
> +         (uint32_t)(b >> 63), /* sign extend */<br>
> +         (uint32_t)(b >> 63), /* sign extend */<br>
> +      };<br>
> +<br>
> +      uint32_t ab32[4];<br>
> +      ubm_mul_u32arr(ab32, a32, b32);<br>
> +<br>
> +      return ab32[2] | ((uint64_t)ab32[3] << 32);<br>
> +   } else {<br>
> +      assert(num_bits <= 32);<br>
> +      return strunc((a * b) >> num_bits, num_bits);<br>
> +   }<br>
> +}<br>
> +<br>
> +static inline uint64_t<br>
> +fast_udiv_add_sat(uint64_t n, struct util_fast_udiv_info m, unsigned num_bits)<br>
> +{<br>
> +   assert(uint_is_in_range(n, num_bits));<br>
> +   assert(uint_is_in_range(m.multiplier, num_bits));<br>
> +<br>
> +   n = n >> m.pre_shift;<br>
> +   n = uadd_sat(n, m.increment, num_bits);<br>
> +   n = umul_add_high(n, m.multiplier, 0, num_bits);<br>
> +   n = n >> m.post_shift;<br>
> +<br>
> +   return n;<br>
> +}<br>
> +<br>
> +static inline uint64_t<br>
> +fast_udiv_mul_add(uint64_t n, struct util_fast_udiv_info m, unsigned num_bits)<br>
> +{<br>
> +   assert(uint_is_in_range(n, num_bits));<br>
> +   assert(uint_is_in_range(m.multiplier, num_bits));<br>
> +<br>
> +   n = n >> m.pre_shift;<br>
> +   n = umul_add_high(n, m.multiplier,<br>
> +                     m.increment ? m.multiplier : 0,<br>
> +                     num_bits);<br>
> +   n = n >> m.post_shift;<br>
> +<br>
> +   return n;<br>
> +}<br>
> +<br>
> +static inline uint64_t<br>
> +fast_sdiv(int64_t n, int64_t d, struct util_fast_sdiv_info m, unsigned num_bits)<br>
> +{<br>
> +   assert(sint_is_in_range(n, num_bits));<br>
> +   assert(sint_is_in_range(d, num_bits));<br>
> +   assert(sint_is_in_range(m.multiplier, num_bits));<br>
> +<br>
> +   int64_t res;<br>
> +   res = smul_high(n, m.multiplier, num_bits);<br>
> +   if (d > 0 && m.multiplier < 0)<br>
> +      res = strunc(res + n, num_bits);<br>
> +   if (d < 0 && m.multiplier > 0)<br>
> +      res = strunc(res - n, num_bits);<br>
> +   res = res >> m.shift;<br>
> +   res = res - (res >> (num_bits - 1));<br>
> +<br>
> +   return res;<br>
> +}<br>
> +<br>
> +static uint64_t<br>
> +rand_uint(unsigned bits, unsigned min)<br>
> +{<br>
> +   assert(bits >= 4);<br>
> +<br>
> +   /* Make sure we get some small and large numbers and powers of two every<br>
> +    * once in a while<br>
> +    */<br>
> +   int k = rand() % 64;<br>
> +   if (k == 17) {<br>
> +      return min + (rand() % 16);<br>
> +   } else if (k == 42) {<br>
> +      return MAX_UINT(bits) - (rand() % 16);<br>
> +   } else if (k == 9) {<br>
> +      uint64_t r;<br>
> +      do {<br>
> +         r = 1ull << (rand() % bits);<br>
> +      } while (r < min);<br>
> +      return r;<br>
> +   }<br>
> +<br>
> +   if (min == 0) {<br>
> +      assert(bits <= 64);<br>
> +      uint64_t r = 0;<br>
> +      for (unsigned i = 0; i < 8; i++)<br>
> +         r |= ((uint64_t)rand() & 0xf) << i * 8;<br>
> +      return r >> (63 - (rand() % bits));<br>
> +   } else {<br>
> +      uint64_t r;<br>
> +      do {<br>
> +         r = rand_uint(bits, 0);<br>
> +      } while (r < min);<br>
> +      return r;<br>
> +   }<br>
> +}<br>
> +<br>
> +static int64_t<br>
> +rand_sint(unsigned bits, unsigned min_abs)<br>
> +{<br>
> +   /* Make sure we hit MIN_INT every once in a while */<br>
> +   if (rand() % 64 == 37)<br>
> +      return -(1 << (bits - 1));<br>
> +<br>
> +   int64_t s = rand_uint(bits - 1, min_abs);<br>
> +   return rand() & 1 ? s : -s;<br>
> +}<br>
> +<br>
> +static uint64_t<br>
> +udiv(uint64_t a, uint64_t b, unsigned bit_size)<br>
> +{<br>
> +   switch (bit_size) {<br>
> +   case 64: return (uint64_t)a / (uint64_t)b;<br>
> +   case 32: return (uint32_t)a / (uint32_t)b;<br>
> +   case 16: return (uint16_t)a / (uint16_t)b;<br>
> +   case 8:  return  (uint8_t)a / (uint8_t)b;<br>
> +   default:<br>
> +      assert(!"Invalid bit size");<br>
> +      return 0;<br>
> +   }<br>
> +}<br>
> +<br>
> +static int64_t<br>
> +sdiv(int64_t a, int64_t b, unsigned bit_size)<br>
> +{<br>
> +   switch (bit_size) {<br>
> +   case 64: return (int64_t)a / (int64_t)b;<br>
> +   case 32: return (int32_t)a / (int32_t)b;<br>
> +   case 16: return (int16_t)a / (int16_t)b;<br>
> +   case 8:  return  (int8_t)a / (int8_t)b;<br>
> +   default:<br>
> +      assert(!"Invalid bit size");<br>
> +      return 0;<br>
> +   }<br>
> +}<br>
> +<br>
> +static void<br>
> +random_udiv_add_sat_test(unsigned bits, bool bounded)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      uint64_t n = rand_uint(bits, 0);<br>
> +      uint64_t d = rand_uint(bits, 2);<br>
> +      assert(uint_is_in_range(n, bits));<br>
> +      assert(uint_is_in_range(d, bits) && d >= 2);<br>
> +<br>
> +      unsigned n_bits = bounded ? util_logbase2_64(MAX2(n, 1)) + 1 : bits;<br>
> +<br>
> +      struct util_fast_udiv_info m =<br>
> +         util_compute_fast_udiv_info(d, n_bits, bits);<br>
> +      EXPECT_EQ(fast_udiv_add_sat(n, m, bits), udiv(n, d, bits));<br>
> +   }<br>
> +}<br>
> +<br>
> +static void<br>
> +random_udiv_mul_add_test(unsigned bits, bool bounded)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      uint64_t n = rand_uint(bits, 0);<br>
> +      uint64_t d = rand_uint(bits, 1);<br>
> +      assert(uint_is_in_range(n, bits));<br>
> +      assert(uint_is_in_range(d, bits) && d >= 1);<br>
> +<br>
> +      unsigned n_bits = bounded ? util_logbase2_64(MAX2(n, 1)) + 1: bits;<br>
> +<br>
> +      struct util_fast_udiv_info m =<br>
> +         util_compute_fast_udiv_info(d, n_bits, bits);<br>
> +      EXPECT_EQ(fast_udiv_mul_add(n, m, bits), udiv(n, d, bits));<br>
> +   }<br>
> +}<br>
> +<br>
> +static void<br>
> +random_sdiv_test(unsigned bits)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      int64_t n = rand_sint(bits, 0);<br>
> +      int64_t d;<br>
> +      do {<br>
> +         d = rand_sint(bits, 2);<br>
> +      } while (util_is_power_of_two_or_zero64(llabs(d)));<br>
> +<br>
> +      assert(sint_is_in_range(n, bits));<br>
> +      assert(sint_is_in_range(d, bits) && llabs(d) >= 2);<br>
> +<br>
> +      struct util_fast_sdiv_info m =<br>
> +         util_compute_fast_sdiv_info(d, bits);<br>
> +      EXPECT_EQ(fast_sdiv(n, d, m, bits), sdiv(n, d, bits));<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint8_add_sat)<br>
> +{<br>
> +   /* 8-bit is small enough we can brute-force the entire space */<br>
> +   for (unsigned d = 2; d < 256; d++) {<br>
> +      for (unsigned n_bits = 1; n_bits <= 8; n_bits++) {<br>
> +         struct util_fast_udiv_info m =<br>
> +            util_compute_fast_udiv_info(d, n_bits, 8);<br>
> +<br>
> +         for (unsigned n = 0; n < (1u << n_bits); n++)<br>
> +            EXPECT_EQ(fast_udiv_add_sat(n, m, 8), udiv(n, d, 8));<br>
> +      }<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint8_mul_add)<br>
> +{<br>
> +   /* 8-bit is small enough we can brute-force the entire space */<br>
> +   for (unsigned d = 2; d < 256; d++) {<br>
> +      for (unsigned n_bits = 1; n_bits <= 8; n_bits++) {<br>
> +         struct util_fast_udiv_info m =<br>
> +            util_compute_fast_udiv_info(d, n_bits, 8);<br>
> +<br>
> +         for (unsigned n = 0; n < (1u << n_bits); n++)<br>
> +            EXPECT_EQ(fast_udiv_mul_add(n, m, 8), udiv(n, d, 8));<br>
> +      }<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, int8)<br>
> +{<br>
> +   /* 8-bit is small enough we can brute-force the entire space */<br>
> +   for (int n = -128; n < 128; n++) {<br>
> +      for (int d = -128; d < 128; d++) {<br>
> +         if (util_is_power_of_two_or_zero(abs(d)))<br>
> +            continue;<br>
> +<br>
> +         struct util_fast_sdiv_info m =<br>
> +            util_compute_fast_sdiv_info(d, 8);<br>
> +         EXPECT_EQ(fast_sdiv(n, d, m, 8), sdiv(n, d, 8));<br>
> +      }<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint16_add_sat_bounded)<br>
> +{<br>
> +   random_udiv_add_sat_test(16, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint16_add_sat_full)<br>
> +{<br>
> +   random_udiv_add_sat_test(16, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint16_mul_add_bounded)<br>
> +{<br>
> +   random_udiv_mul_add_test(16, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint16_mul_add_full)<br>
> +{<br>
> +   random_udiv_mul_add_test(16, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, int16)<br>
> +{<br>
> +   random_sdiv_test(16);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint32_add_sat_bounded)<br>
> +{<br>
> +   random_udiv_add_sat_test(32, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint32_add_sat_full)<br>
> +{<br>
> +   random_udiv_add_sat_test(32, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint32_mul_add_bounded)<br>
> +{<br>
> +   random_udiv_mul_add_test(32, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint32_mul_add_full)<br>
> +{<br>
> +   random_udiv_mul_add_test(32, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, int32)<br>
> +{<br>
> +   random_sdiv_test(32);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, util_fast_udiv32)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      uint32_t n = rand_uint(32, 0);<br>
> +      uint32_t d = rand_uint(32, 1);<br>
> +<br>
> +      struct util_fast_udiv_info m =<br>
> +         util_compute_fast_udiv_info(d, 32, 32);<br>
> +      EXPECT_EQ(util_fast_udiv32(n, m), n / d);<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, util_fast_udiv32_nuw)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      uint32_t n = rand_uint(32, 0);<br>
> +      if (n == UINT32_MAX)<br>
> +         continue;<br>
> +      uint32_t d = rand_uint(32, 1);<br>
> +<br>
> +      struct util_fast_udiv_info m =<br>
> +         util_compute_fast_udiv_info(d, 32, 32);<br>
> +      EXPECT_EQ(util_fast_udiv32(n, m), n / d);<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, util_fast_udiv32_u31_d_not_one)<br>
> +{<br>
> +   for (unsigned i = 0; i < RAND_TEST_ITERATIONS; i++) {<br>
> +      uint32_t n = rand_uint(31, 0);<br>
> +      uint32_t d = rand_uint(31, 2);<br>
> +<br>
> +      struct util_fast_udiv_info m =<br>
> +         util_compute_fast_udiv_info(d, 31, 32);<br>
> +      EXPECT_EQ(util_fast_udiv32_u31_d_not_one(n, m), n / d);<br>
> +   }<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint64_add_sat_bounded)<br>
> +{<br>
> +   random_udiv_add_sat_test(64, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint64_add_sat_full)<br>
> +{<br>
> +   random_udiv_add_sat_test(64, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint64_mul_add_bounded)<br>
> +{<br>
> +   random_udiv_mul_add_test(64, true);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, uint64_mul_add_full)<br>
> +{<br>
> +   random_udiv_mul_add_test(64, false);<br>
> +}<br>
> +<br>
> +TEST(fast_idiv_by_const, int64)<br>
> +{<br>
> +   random_sdiv_test(64);<br>
> +}<br>
> diff --git a/src/util/tests/fast_idiv_by_const/meson.build b/src/util/tests/fast_idiv_by_const/meson.build<br>
> new file mode 100644<br>
> index 00000000000..8c3b79493ff<br>
> --- /dev/null<br>
> +++ b/src/util/tests/fast_idiv_by_const/meson.build<br>
> @@ -0,0 +1,30 @@<br>
> +# Copyright © 2018 Intel Corporation<br>
> +<br>
> +# Permission is hereby granted, free of charge, to any person obtaining a copy<br>
> +# of this software and associated documentation files (the "Software"), to deal<br>
> +# in the Software without restriction, including without limitation the rights<br>
> +# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell<br>
> +# copies of the Software, and to permit persons to whom the Software is<br>
> +# furnished to do so, subject to the following conditions:<br>
> +<br>
> +# The above copyright notice and this permission notice shall be included in<br>
> +# all copies or substantial portions of the Software.<br>
> +<br>
> +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
> +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
> +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE<br>
> +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
> +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,<br>
> +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE<br>
> +# SOFTWARE.<br>
> +<br>
> +test(<br>
> +  'fast_idiv_by_const',<br>
> +  executable(<br>
> +    'fast_idiv_by_const_test',<br>
> +    'fast_idiv_by_const_test.cpp',<br>
> +    dependencies : [dep_thread, dep_dl, idep_gtest],<br>
> +    include_directories : inc_common,<br>
> +    link_with : [libmesa_util],<br>
> +  )<br>
> +)<br>
> --<br>
> 2.19.0<br>
><br>
> _______________________________________________<br>
> mesa-dev mailing list<br>
> <a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a><br>
> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a><br>
</blockquote></div></div>
</blockquote></div>