<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Mon, Sep 24, 2018 at 6:41 PM Marek Olšák <<a href="mailto:maraeo@gmail.com">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">Did you copy the code from the same author?<br></blockquote><div><br></div><div>No, I read a paper and implemented it myself.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Does your version also have an interface for dividing by a uniform<br>
instead of a compile time constant?<br></blockquote><div><br></div><div>I'm not sure what you mean by that.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Note that this algorithm was originally only written for<br>
non-power-of-two divisors and I extended it to support 1 and<br>
power-of-two divisors in order to support dividing by a uniform in a<br>
generic way. The other two generic variants that I added are also<br>
important. One of them assumes no unsigned wraparounds and the other<br>
one assumes operands have 31 bits and the divisor is >= 2.<br></blockquote><div><br></div><div>Right.  I can see those being useful.<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 Mon, Sep 24, 2018 at 10:00 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net" target="_blank">jason@jlekstrand.net</a>> wrote:<br>
> Very similar.... And mine handles 8, 16, and 64-bit types. :-D<br>
><br>
> --Jason<br>
><br>
> On Mon, Sep 24, 2018 at 8:53 AM Ian Romanick <<a href="mailto:idr@freedesktop.org" target="_blank">idr@freedesktop.org</a>> wrote:<br>
>><br>
>> I didn't look really closely at either set, but this seems really<br>
>> similar to something Jason sent out a week or two.  Perhaps you guys<br>
>> could unify these?<br>
>><br>
>> On 09/23/2018 09:57 AM, Marek Olšák wrote:<br>
>> > From: Marek Olšák <<a href="mailto:marek.olsak@amd.com" target="_blank">marek.olsak@amd.com</a>><br>
>> ><br>
>> > Compilers can use this to generate optimal code for integer division<br>
>> > by a constant.<br>
>> ><br>
>> > Additionally, an unsigned division by a uniform that is constant but not<br>
>> > known at compile time can still be optimized by passing 2-4 division<br>
>> > factors to the shader as uniforms and executing one of the fast_udiv*<br>
>> > variants. The signed division algorithm doesn't have this capability.<br>
>> > ---<br>
>> >  src/util/Makefile.sources     |   2 +<br>
>> >  src/util/fast_idiv_by_const.c | 245<br>
>> > ++++++++++++++++++++++++++++++++++++++++++<br>
>> >  src/util/fast_idiv_by_const.h | 173 +++++++++++++++++++++++++++++<br>
>> >  src/util/meson.build          |   2 +<br>
>> >  4 files changed, 422 insertions(+)<br>
>> >  create mode 100644 src/util/fast_idiv_by_const.c<br>
>> >  create mode 100644 src/util/fast_idiv_by_const.h<br>
>> ><br>
>> > diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources<br>
>> > index b562d6c..f741b2a 100644<br>
>> > --- a/src/util/Makefile.sources<br>
>> > +++ b/src/util/Makefile.sources<br>
>> > @@ -3,20 +3,22 @@ MESA_UTIL_FILES := \<br>
>> >       bitscan.h \<br>
>> >       bitset.h \<br>
>> >       build_id.c \<br>
>> >       build_id.h \<br>
>> >       crc32.c \<br>
>> >       crc32.h \<br>
>> >       debug.c \<br>
>> >       debug.h \<br>
>> >       disk_cache.c \<br>
>> >       disk_cache.h \<br>
>> > +     fast_idiv_by_const.c \<br>
>> > +     fast_idiv_by_const.h \<br>
>> >       format_r11g11b10f.h \<br>
>> >       format_rgb9e5.h \<br>
>> >       format_srgb.h \<br>
>> >       futex.h \<br>
>> >       half_float.c \<br>
>> >       half_float.h \<br>
>> >       hash_table.c \<br>
>> >       hash_table.h \<br>
>> >       list.h \<br>
>> >       macros.h \<br>
>> > diff --git a/src/util/fast_idiv_by_const.c<br>
>> > b/src/util/fast_idiv_by_const.c<br>
>> > new file mode 100644<br>
>> > index 0000000..f247b66<br>
>> > --- /dev/null<br>
>> > +++ b/src/util/fast_idiv_by_const.c<br>
>> > @@ -0,0 +1,245 @@<br>
>> > +/*<br>
>> > + * Copyright © 2018 Advanced Micro Devices, Inc.<br>
>> > + *<br>
>> > + * Permission is hereby granted, free of charge, to any person<br>
>> > obtaining a<br>
>> > + * copy of this software and associated documentation files (the<br>
>> > "Software"),<br>
>> > + * to deal in the Software without restriction, including without<br>
>> > limitation<br>
>> > + * the rights to use, copy, modify, merge, publish, distribute,<br>
>> > sublicense,<br>
>> > + * and/or sell copies of the Software, and to permit persons to whom<br>
>> > 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<br>
>> > next<br>
>> > + * paragraph) shall be included in all copies or substantial portions<br>
>> > of the<br>
>> > + * Software.<br>
>> > + *<br>
>> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,<br>
>> > EXPRESS OR<br>
>> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF<br>
>> > MERCHANTABILITY,<br>
>> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT<br>
>> > SHALL<br>
>> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR<br>
>> > OTHER<br>
>> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,<br>
>> > ARISING<br>
>> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER<br>
>> > DEALINGS<br>
>> > + * IN THE SOFTWARE.<br>
>> > + */<br>
>> > +<br>
>> > +/* Imported from:<br>
>> > + *<br>
>> > <a href="https://raw.githubusercontent.com/ridiculousfish/libdivide/master/divide_by_constants_codegen_reference.c" rel="noreferrer" target="_blank">https://raw.githubusercontent.com/ridiculousfish/libdivide/master/divide_by_constants_codegen_reference.c</a><br>
>> > + * Paper:<br>
>> > + *<br>
>> > <a href="http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf" rel="noreferrer" target="_blank">http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf</a><br>
>> > + *<br>
>> > + * The author, ridiculous_fish, wrote:<br>
>> > + *<br>
>> > + *  ''Reference implementations of computing and using the "magic<br>
>> > number"<br>
>> > + *    approach to dividing by constants, including codegen<br>
>> > instructions.<br>
>> > + *    The unsigned division incorporates the "round down" optimization<br>
>> > per<br>
>> > + *    ridiculous_fish.<br>
>> > + *<br>
>> > + *    This is free and unencumbered software. Any copyright is<br>
>> > dedicated<br>
>> > + *    to the Public Domain.''<br>
>> > + */<br>
>> > +<br>
>> > +#include "fast_idiv_by_const.h"<br>
>> > +#include "u_math.h"<br>
>> > +#include <limits.h><br>
>> > +#include <assert.h><br>
>> > +<br>
>> > +/* uint_t and sint_t can be replaced by different integer types and the<br>
>> > code<br>
>> > + * will work as-is. The only requirement is that sizeof(uintN) ==<br>
>> > sizeof(intN).<br>
>> > + */<br>
>> > +<br>
>> > +struct util_fast_udiv_info<br>
>> > +util_compute_fast_udiv_info(uint_t D, unsigned num_bits)<br>
>> > +{<br>
>> > +   /* The numerator must fit in a uint_t */<br>
>> > +   assert(num_bits > 0 && num_bits <= sizeof(uint_t) * CHAR_BIT);<br>
>> > +   assert(D != 0);<br>
>> > +<br>
>> > +   /* The eventual result */<br>
>> > +   struct util_fast_udiv_info result;<br>
>> > +<br>
>> > +   if (util_is_power_of_two_nonzero(D)) {<br>
>> > +      unsigned div_shift = util_logbase2(D);<br>
>> > +<br>
>> > +      if (div_shift) {<br>
>> > +         /* Dividing by a power of two. */<br>
>> > +         result.multiplier = 1 << 31;<br>
>> > +         result.pre_shift = 0;<br>
>> > +         result.post_shift = div_shift - 1;<br>
>> > +         result.increment = 0;<br>
>> > +         return result;<br>
>> > +      } else {<br>
>> > +         /* Dividing by 1. */<br>
>> > +         /* Assuming: floor((num + 1) * (2^32 - 1) / 2^32) = num */<br>
>> > +         result.multiplier = UINT_MAX;<br>
>> > +         result.pre_shift = 0;<br>
>> > +         result.post_shift = 0;<br>
>> > +         result.increment = 1;<br>
>> > +         return result;<br>
>> > +      }<br>
>> > +   }<br>
>> > +<br>
>> > +   /* Bits in a uint_t */<br>
>> > +   const unsigned UINT_BITS = sizeof(uint_t) * CHAR_BIT;<br>
>> > +<br>
>> > +   /* The extra shift implicit in the difference between UINT_BITS and<br>
>> > num_bits<br>
>> > +    */<br>
>> > +   const unsigned extra_shift = UINT_BITS - num_bits;<br>
>> > +<br>
>> > +   /* The initial power of 2 is one less than the first one that can<br>
>> > possibly<br>
>> > +    * work.<br>
>> > +    */<br>
>> > +   const uint_t initial_power_of_2 = (uint_t)1 << (UINT_BITS-1);<br>
>> > +<br>
>> > +   /* The remainder and quotient of our power of 2 divided by d */<br>
>> > +   uint_t quotient = initial_power_of_2 / D;<br>
>> > +   uint_t remainder = initial_power_of_2 % D;<br>
>> > +<br>
>> > +   /* ceil(log_2 D) */<br>
>> > +   unsigned ceil_log_2_D;<br>
>> > +<br>
>> > +   /* The magic info for the variant "round down" algorithm */<br>
>> > +   uint_t down_multiplier = 0;<br>
>> > +   unsigned down_exponent = 0;<br>
>> > +   int has_magic_down = 0;<br>
>> > +<br>
>> > +   /* Compute ceil(log_2 D) */<br>
>> > +   ceil_log_2_D = 0;<br>
>> > +   uint_t tmp;<br>
>> > +   for (tmp = D; tmp > 0; tmp >>= 1)<br>
>> > +      ceil_log_2_D += 1;<br>
>> > +<br>
>> > +<br>
>> > +   /* Begin a loop that increments the exponent, until we find a power<br>
>> > of 2<br>
>> > +    * that works.<br>
>> > +    */<br>
>> > +   unsigned exponent;<br>
>> > +   for (exponent = 0; ; exponent++) {<br>
>> > +      /* Quotient and remainder is from previous exponent; compute it<br>
>> > for this<br>
>> > +       * exponent.<br>
>> > +       */<br>
>> > +      if (remainder >= D - remainder) {<br>
>> > +         /* Doubling remainder will wrap around D */<br>
>> > +         quotient = quotient * 2 + 1;<br>
>> > +         remainder = remainder * 2 - D;<br>
>> > +      } else {<br>
>> > +         /* Remainder will not wrap */<br>
>> > +         quotient = quotient * 2;<br>
>> > +         remainder = remainder * 2;<br>
>> > +      }<br>
>> > +<br>
>> > +      /* We're done if this exponent works for the round_up algorithm.<br>
>> > +       * Note that exponent may be larger than the maximum shift<br>
>> > supported,<br>
>> > +       * so the check for >= ceil_log_2_D is critical.<br>
>> > +       */<br>
>> > +      if ((exponent + extra_shift >= ceil_log_2_D) ||<br>
>> > +          (D - remainder) <= ((uint_t)1 << (exponent + extra_shift)))<br>
>> > +         break;<br>
>> > +<br>
>> > +      /* Set magic_down if we have not set it yet and this exponent<br>
>> > works for<br>
>> > +       * the round_down algorithm<br>
>> > +       */<br>
>> > +      if (!has_magic_down &&<br>
>> > +          remainder <= ((uint_t)1 << (exponent + extra_shift))) {<br>
>> > +         has_magic_down = 1;<br>
>> > +         down_multiplier = quotient;<br>
>> > +         down_exponent = exponent;<br>
>> > +      }<br>
>> > +   }<br>
>> > +<br>
>> > +   if (exponent < ceil_log_2_D) {<br>
>> > +      /* magic_up is efficient */<br>
>> > +      result.multiplier = quotient + 1;<br>
>> > +      result.pre_shift = 0;<br>
>> > +      result.post_shift = exponent;<br>
>> > +      result.increment = 0;<br>
>> > +   } else if (D & 1) {<br>
>> > +      /* Odd divisor, so use magic_down, which must have been set */<br>
>> > +      assert(has_magic_down);<br>
>> > +      result.multiplier = down_multiplier;<br>
>> > +      result.pre_shift = 0;<br>
>> > +      result.post_shift = down_exponent;<br>
>> > +      result.increment = 1;<br>
>> > +   } else {<br>
>> > +      /* Even divisor, so use a prefix-shifted dividend */<br>
>> > +      unsigned pre_shift = 0;<br>
>> > +      uint_t shifted_D = D;<br>
>> > +      while ((shifted_D & 1) == 0) {<br>
>> > +         shifted_D >>= 1;<br>
>> > +         pre_shift += 1;<br>
>> > +      }<br>
>> > +      result = util_compute_fast_udiv_info(shifted_D, num_bits -<br>
>> > pre_shift);<br>
>> > +      /* expect no increment or pre_shift in this path */<br>
>> > +      assert(result.increment == 0 && result.pre_shift == 0);<br>
>> > +      result.pre_shift = pre_shift;<br>
>> > +   }<br>
>> > +   return result;<br>
>> > +}<br>
>> > +<br>
>> > +struct util_fast_sdiv_info<br>
>> > +util_compute_fast_sdiv_info(sint_t D)<br>
>> > +{<br>
>> > +   /* D must not be zero. */<br>
>> > +   assert(D != 0);<br>
>> > +   /* The result is not correct for these divisors. */<br>
>> > +   assert(D != 1 && D != -1);<br>
>> > +<br>
>> > +   /* Our result */<br>
>> > +   struct util_fast_sdiv_info result;<br>
>> > +<br>
>> > +   /* Bits in an sint_t */<br>
>> > +   const unsigned SINT_BITS = sizeof(sint_t) * CHAR_BIT;<br>
>> > +<br>
>> > +   /* Absolute value of D (we know D is not the most negative value<br>
>> > since<br>
>> > +    * that's a power of 2)<br>
>> > +    */<br>
>> > +   const uint_t abs_d = (D < 0 ? -D : D);<br>
>> > +<br>
>> > +   /* The initial power of 2 is one less than the first one that can<br>
>> > possibly<br>
>> > +    * work */<br>
>> > +   /* "two31" in Warren */<br>
>> > +   unsigned exponent = SINT_BITS - 1;<br>
>> > +   const uint_t initial_power_of_2 = (uint_t)1 << exponent;<br>
>> > +<br>
>> > +   /* Compute the absolute value of our "test numerator,"<br>
>> > +    * which is the largest dividend whose remainder with d is d-1.<br>
>> > +    * This is called anc in Warren.<br>
>> > +    */<br>
>> > +   const uint_t tmp = initial_power_of_2 + (D < 0);<br>
>> > +   const uint_t abs_test_numer = tmp - 1 - tmp % abs_d;<br>
>> > +<br>
>> > +   /* Initialize our quotients and remainders (q1, r1, q2, r2 in<br>
>> > Warren) */<br>
>> > +   uint_t quotient1 = initial_power_of_2 / abs_test_numer;<br>
>> > +   uint_t remainder1 = initial_power_of_2 % abs_test_numer;<br>
>> > +   uint_t quotient2 = initial_power_of_2 / abs_d;<br>
>> > +   uint_t remainder2 = initial_power_of_2 % abs_d;<br>
>> > +   uint_t delta;<br>
>> > +<br>
>> > +   /* Begin our loop */<br>
>> > +   do {<br>
>> > +      /* Update the exponent */<br>
>> > +      exponent++;<br>
>> > +<br>
>> > +      /* Update quotient1 and remainder1 */<br>
>> > +      quotient1 *= 2;<br>
>> > +      remainder1 *= 2;<br>
>> > +      if (remainder1 >= abs_test_numer) {<br>
>> > +         quotient1 += 1;<br>
>> > +         remainder1 -= abs_test_numer;<br>
>> > +      }<br>
>> > +<br>
>> > +      /* Update quotient2 and remainder2 */<br>
>> > +      quotient2 *= 2;<br>
>> > +      remainder2 *= 2;<br>
>> > +      if (remainder2 >= abs_d) {<br>
>> > +         quotient2 += 1;<br>
>> > +         remainder2 -= abs_d;<br>
>> > +      }<br>
>> > +<br>
>> > +      /* Keep going as long as (2**exponent) / abs_d <= delta */<br>
>> > +      delta = abs_d - remainder2;<br>
>> > +   } while (quotient1 < delta || (quotient1 == delta && remainder1 ==<br>
>> > 0));<br>
>> > +<br>
>> > +   result.multiplier = quotient2 + 1;<br>
>> > +   if (D < 0) result.multiplier = -result.multiplier;<br>
>> > +   result.shift = exponent - SINT_BITS;<br>
>> > +   return result;<br>
>> > +}<br>
>> > diff --git a/src/util/fast_idiv_by_const.h<br>
>> > b/src/util/fast_idiv_by_const.h<br>
>> > new file mode 100644<br>
>> > index 0000000..e8debbf<br>
>> > --- /dev/null<br>
>> > +++ b/src/util/fast_idiv_by_const.h<br>
>> > @@ -0,0 +1,173 @@<br>
>> > +/*<br>
>> > + * Copyright © 2018 Advanced Micro Devices, Inc.<br>
>> > + *<br>
>> > + * Permission is hereby granted, free of charge, to any person<br>
>> > obtaining a<br>
>> > + * copy of this software and associated documentation files (the<br>
>> > "Software"),<br>
>> > + * to deal in the Software without restriction, including without<br>
>> > limitation<br>
>> > + * the rights to use, copy, modify, merge, publish, distribute,<br>
>> > sublicense,<br>
>> > + * and/or sell copies of the Software, and to permit persons to whom<br>
>> > 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<br>
>> > next<br>
>> > + * paragraph) shall be included in all copies or substantial portions<br>
>> > of the<br>
>> > + * Software.<br>
>> > + *<br>
>> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,<br>
>> > EXPRESS OR<br>
>> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF<br>
>> > MERCHANTABILITY,<br>
>> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT<br>
>> > SHALL<br>
>> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR<br>
>> > OTHER<br>
>> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,<br>
>> > ARISING<br>
>> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER<br>
>> > DEALINGS<br>
>> > + * IN THE SOFTWARE.<br>
>> > + */<br>
>> > +<br>
>> > +#ifndef FAST_IDIV_BY_CONST_H<br>
>> > +#define FAST_IDIV_BY_CONST_H<br>
>> > +<br>
>> > +/* Imported from:<br>
>> > + *<br>
>> > <a href="https://raw.githubusercontent.com/ridiculousfish/libdivide/master/divide_by_constants_codegen_reference.c" rel="noreferrer" target="_blank">https://raw.githubusercontent.com/ridiculousfish/libdivide/master/divide_by_constants_codegen_reference.c</a><br>
>> > + */<br>
>> > +<br>
>> > +#include <inttypes.h><br>
>> > +#include <limits.h><br>
>> > +#include <assert.h><br>
>> > +<br>
>> > +/* You can set these to different types to get different precision. */<br>
>> > +typedef int32_t sint_t;<br>
>> > +typedef uint32_t uint_t;<br>
>> > +<br>
>> > +/* Computes "magic info" for performing signed division by a fixed<br>
>> > integer D.<br>
>> > + * The type 'sint_t' is assumed to be defined as a signed integer type<br>
>> > large<br>
>> > + * enough to hold both the dividend and the divisor.<br>
>> > + * Here >> is arithmetic (signed) shift, and >>> is logical shift.<br>
>> > + *<br>
>> > + * To emit code for n/d, rounding towards zero, use the following<br>
>> > sequence:<br>
>> > + *<br>
>> > + *   m = compute_signed_magic_info(D)<br>
>> > + *   emit("result = (m.multiplier * n) >> SINT_BITS");<br>
>> > + *   if d > 0 and m.multiplier < 0: emit("result += n")<br>
>> > + *   if d < 0 and m.multiplier > 0: emit("result -= n")<br>
>> > + *   if m.post_shift > 0: emit("result >>= m.shift")<br>
>> > + *   emit("result += (result < 0)")<br>
>> > + *<br>
>> > + * The shifts by SINT_BITS may be "free" if the high half of the full<br>
>> > multiply<br>
>> > + * is put in a separate register.<br>
>> > + *<br>
>> > + * The final add can of course be implemented via the sign bit, e.g.<br>
>> > + *    result += (result >>> (SINT_BITS - 1))<br>
>> > + * or<br>
>> > + *    result -= (result >> (SINT_BITS - 1))<br>
>> > + *<br>
>> > + * This code is heavily indebted to Hacker's Delight by Henry Warren.<br>
>> > + * See <a href="http://www.hackersdelight.org/HDcode/magic.c.txt" rel="noreferrer" target="_blank">http://www.hackersdelight.org/HDcode/magic.c.txt</a><br>
>> > + * Used with permission from<br>
>> > <a href="http://www.hackersdelight.org/permissions.htm" rel="noreferrer" target="_blank">http://www.hackersdelight.org/permissions.htm</a><br>
>> > + */<br>
>> > +<br>
>> > +struct util_fast_sdiv_info {<br>
>> > +   sint_t multiplier; /* the "magic number" multiplier */<br>
>> > +   unsigned shift; /* shift for the dividend after multiplying */<br>
>> > +};<br>
>> > +<br>
>> > +struct util_fast_sdiv_info<br>
>> > +util_compute_fast_sdiv_info(sint_t D);<br>
>> > +<br>
>> > +/* Computes "magic info" for performing unsigned division by a fixed<br>
>> > positive<br>
>> > + * integer D. The type 'uint_t' is assumed to be defined as an unsigned<br>
>> > + * integer type large enough to hold both the dividend and the divisor.<br>
>> > + * num_bits can be set appropriately if n is known to be smaller than<br>
>> > + * the largest uint_t; if this is not known then pass<br>
>> > + * "(sizeof(uint_t) * CHAR_BIT)" for num_bits.<br>
>> > + *<br>
>> > + * Assume we have a hardware register of width UINT_BITS, a known<br>
>> > constant D<br>
>> > + * which is  not zero and not a power of 2, and a variable n of width<br>
>> > num_bits<br>
>> > + * (which may be up to UINT_BITS). To emit code for n/d, use one of the<br>
>> > two<br>
>> > + * following sequences (here >>> refers to a logical bitshift):<br>
>> > + *<br>
>> > + *   m = compute_unsigned_magic_info(D, num_bits)<br>
>> > + *   if m.pre_shift > 0: emit("n >>>= m.pre_shift")<br>
>> > + *   if m.increment: emit("n = saturated_increment(n)")<br>
>> > + *   emit("result = (m.multiplier * n) >>> UINT_BITS")<br>
>> > + *   if m.post_shift > 0: emit("result >>>= m.post_shift")<br>
>> > + *<br>
>> > + * or<br>
>> > + *<br>
>> > + *   m = compute_unsigned_magic_info(D, num_bits)<br>
>> > + *   if m.pre_shift > 0: emit("n >>>= m.pre_shift")<br>
>> > + *   emit("result = m.multiplier * n")<br>
>> > + *   if m.increment: emit("result = result + m.multiplier")<br>
>> > + *   emit("result >>>= UINT_BITS")<br>
>> > + *   if m.post_shift > 0: emit("result >>>= m.post_shift")<br>
>> > + *<br>
>> > + * The shifts by UINT_BITS may be "free" if the high half of the full<br>
>> > multiply<br>
>> > + * is put in a separate register.<br>
>> > + *<br>
>> > + * saturated_increment(n) means "increment n unless it would wrap to<br>
>> > 0," i.e.<br>
>> > + *   if n == (1 << UINT_BITS)-1: result = n<br>
>> > + *   else: result = n+1<br>
>> > + * A common way to implement this is with the carry bit. For example,<br>
>> > on x86:<br>
>> > + *   add 1<br>
>> > + *   sbb 0<br>
>> > + *<br>
>> > + * Some invariants:<br>
>> > + *   1: At least one of pre_shift and increment is zero<br>
>> > + *   2: multiplier is never zero<br>
>> > + *<br>
>> > + * This code incorporates the "round down" optimization per<br>
>> > ridiculous_fish.<br>
>> > + */<br>
>> > +<br>
>> > +struct util_fast_udiv_info {<br>
>> > +   uint_t multiplier; /* the "magic number" multiplier */<br>
>> > +   unsigned pre_shift; /* shift for the dividend before multiplying */<br>
>> > +   unsigned post_shift; /* shift for the dividend after multiplying */<br>
>> > +   int increment; /* 0 or 1; if set then increment the numerator, using<br>
>> > one of<br>
>> > +                     the two strategies */<br>
>> > +};<br>
>> > +<br>
>> > +struct util_fast_udiv_info<br>
>> > +util_compute_fast_udiv_info(uint_t D, unsigned num_bits);<br>
>> > +<br>
>> > +/* Below are possible options for dividing by a uniform in a shader<br>
>> > where<br>
>> > + * the divisor is constant but not known at compile time.<br>
>> > + */<br>
>> > +<br>
>> > +/* Full version. */<br>
>> > +static inline unsigned<br>
>> > +fast_udiv(unsigned n, struct util_fast_udiv_info info)<br>
>> > +{<br>
>> > +    n = n >> info.pre_shift;<br>
>> > +    /* For non-power-of-two divisors, use a 32-bit ADD that clamps to<br>
>> > UINT_MAX. */<br>
>> > +    n = (((uint64_t)n + info.increment) * info.multiplier) >> 32;<br>
>> > +    n = n >> info.post_shift;<br>
>> > +    return n;<br>
>> > +}<br>
>> > +<br>
>> > +/* A little more efficient version if n != UINT_MAX, i.e. no unsigned<br>
>> > + * wraparound in the computation.<br>
>> > + */<br>
>> > +static inline unsigned<br>
>> > +fast_udiv_nuw(unsigned n, struct util_fast_udiv_info info)<br>
>> > +{<br>
>> > +    assert(n != UINT_MAX);<br>
>> > +    n = n >> info.pre_shift;<br>
>> > +    n = n + info.increment;<br>
>> > +    n = ((uint64_t)n * info.multiplier) >> 32;<br>
>> > +    n = n >> info.post_shift;<br>
>> > +    return n;<br>
>> > +}<br>
>> > +<br>
>> > +/* Even faster version but both operands must be 31-bit unsigned<br>
>> > integers<br>
>> > + * and the divisor must be greater than 1.<br>
>> > + *<br>
>> > + * info must be computed with num_bits == 31.<br>
>> > + */<br>
>> > +static inline unsigned<br>
>> > +fast_udiv_u31_d_not_one(unsigned n, struct util_fast_udiv_info info)<br>
>> > +{<br>
>> > +    assert(info.pre_shift == 0);<br>
>> > +    assert(info.increment == 0);<br>
>> > +    n = ((uint64_t)n * info.multiplier) >> 32;<br>
>> > +    n = n >> info.post_shift;<br>
>> > +    return n;<br>
>> > +}<br>
>> > +<br>
>> > +#endif<br>
>> > diff --git a/src/util/meson.build b/src/util/meson.build<br>
>> > index 027bc5b..ebaeb47 100644<br>
>> > --- a/src/util/meson.build<br>
>> > +++ b/src/util/meson.build<br>
>> > @@ -27,20 +27,22 @@ files_mesa_util = files(<br>
>> >    'bitscan.h',<br>
>> >    'bitset.h',<br>
>> >    'build_id.c',<br>
>> >    'build_id.h',<br>
>> >    'crc32.c',<br>
>> >    'crc32.h',<br>
>> >    'debug.c',<br>
>> >    'debug.h',<br>
>> >    'disk_cache.c',<br>
>> >    'disk_cache.h',<br>
>> > +  'fast_idiv_by_const.c',<br>
>> > +  'fast_idiv_by_const.h',<br>
>> >    'format_r11g11b10f.h',<br>
>> >    'format_rgb9e5.h',<br>
>> >    'format_srgb.h',<br>
>> >    'futex.h',<br>
>> >    'half_float.c',<br>
>> >    'half_float.h',<br>
>> >    'hash_table.c',<br>
>> >    'hash_table.h',<br>
>> >    'list.h',<br>
>> >    'macros.h',<br>
>> ><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>