[Mesa-dev] [PATCH 1/2] util/u_math: Implement a logbase2 function for unsigned long

[Pierre Moreau]

On 2018-05-23 — 12:12, Eric Engestrom wrote:
> On Tuesday, 2018-05-22 23:06:16 +0200, Karol Herbst wrote:
> > From: Pierre Moreau <pierre.morrow at free.fr>
> > 
> > Signed-off-by: Karol Herbst <kherbst at redhat.com>
> > ---
> >  src/gallium/auxiliary/util/u_math.h | 55 +++++++++++++++++++++++++++++
> >  src/util/bitscan.h                  | 11 ++++++
> >  2 files changed, 66 insertions(+)
> > 
> > diff --git a/src/gallium/auxiliary/util/u_math.h b/src/gallium/auxiliary/util/u_math.h
> > index 46d02978fd6..504d67664b2 100644
> > --- a/src/gallium/auxiliary/util/u_math.h
> > +++ b/src/gallium/auxiliary/util/u_math.h
> > @@ -421,6 +421,23 @@ util_logbase2(unsigned n)
> >  #endif
> >  }
> >  
> > +static inline uint64_t
> > +util_logbase2_64(uint64_t n)
> > +{
> > +#if defined(HAVE___BUILTIN_CLZLL)
> > +   return ((sizeof(uint64_t) * 8ll - 1ll) - __builtin_clzll(n | 1ll));
> > +#else
> > +   uint64_t pos = 0ll;
> > +   if (n >= 1ll<<32ll) { n >>= 32ll; pos += 32ll; }
> > +   if (n >= 1ll<<16ll) { n >>= 16ll; pos += 16ll; }
> > +   if (n >= 1ll<< 8ll) { n >>=  8ll; pos +=  8ll; }
> > +   if (n >= 1ll<< 4ll) { n >>=  4ll; pos +=  4ll; }
> > +   if (n >= 1ll<< 2ll) { n >>=  2ll; pos +=  2ll; }
> > +   if (n >= 1ll<< 1ll) {             pos +=  1ll; }
>                 ^^
> `ll` is being added a bit too much (although it's harmless); for
> instance, in this function I believe this one is the only one that does
> anything, and technically only on the first line (`1ll<<32`).
> 
> They should be unsigned though, ie. `ull`; with that:

You’re right. And it looks like I made that same mistake for the whole patch;
at least I was consistent.

> Reviewed-by: Eric Engestrom <eric.engestrom at intel.com>
> 
> > +   return pos;
> > +#endif
> > +}
> > +
> >  /**
> >   * Returns the ceiling of log n base 2, and 0 when n == 0. Equivalently,
> >   * returns the smallest x such that n <= 2**x.
> > @@ -434,6 +451,15 @@ util_logbase2_ceil(unsigned n)
> >     return 1 + util_logbase2(n - 1);
> >  }
> >  
> > +static inline uint64_t
> > +util_logbase2_ceil64(uint64_t n)
> > +{
> > +   if (n <= 1ll)
> > +      return 0ll;
> > +
> > +   return 1ll + util_logbase2_64(n - 1ll);
> > +}
> > +
> >  /**
> >   * Returns the smallest power of two >= x
> >   */
> > @@ -465,6 +491,35 @@ util_next_power_of_two(unsigned x)
> >  #endif
> >  }
> >  
> > +static inline uint64_t
> > +util_next_power_of_two64(uint64_t x)
> > +{
> > +#if defined(HAVE___BUILTIN_CLZLL)
> > +   if (x <= 1ll)
> > +       return 1ll;
> > +
> > +   return (1ll << ((sizeof(uint64_t) * 8ll) - __builtin_clzll(x - 1ll)));
> > +#else
> > +   uint64_t val = x;
> > +
> > +   if (x <= 1ll)
> > +      return 1ll;
> > +
> > +   if (util_is_power_of_two_or_zero64(x))
> > +      return x;
> > +
> > +   val--;
> > +   val = (val >> 1ll)  | val;
> > +   val = (val >> 2ll)  | val;
> > +   val = (val >> 4ll)  | val;
> > +   val = (val >> 8ll)  | val;
> > +   val = (val >> 16ll) | val;
> > +   val = (val >> 32ll) | val;
> > +   val++;
> > +   return val;
> > +#endif
> > +}
> > +
> >  
> >  /**
> >   * Return number of bits set in n.
> > diff --git a/src/util/bitscan.h b/src/util/bitscan.h
> > index 5cc75f0beba..310b4ed2e37 100644
> > --- a/src/util/bitscan.h
> > +++ b/src/util/bitscan.h
> > @@ -123,6 +123,17 @@ util_is_power_of_two_or_zero(unsigned v)
> >     return (v & (v - 1)) == 0;
> >  }
> >  
> > +/* Determine if an uint64_t value is a power of two.
> > + *
> > + * \note
> > + * Zero is treated as a power of two.
> > + */
> > +static inline bool
> > +util_is_power_of_two_or_zero64(uint64_t v)
> > +{
> > +   return (v & (v - 1ll)) == 0ll;
> > +}
> > +
> >  /* Determine if an unsigned value is a power of two.
> >   *
> >   * \note
> > -- 
> > 2.17.0
> > 
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20180523/f9c0ec85/attachment.sig>