[1/2] util: Add util_is_power_of_two_minus_one

Submitted by Alyssa Rosenzweig on June 14, 2019, 4:42 p.m.

Details

Message ID 20190614164236.9267-1-alyssa.rosenzweig@collabora.com
State New
Headers show
Series "Series without cover letter" ( rev: 1 ) in Mesa

Not browsing as part of any series.

Commit Message

Alyssa Rosenzweig June 14, 2019, 4:42 p.m.
Checks if a number is one less than a power of two. Equivalently, this
checks if a number is all ones in binary. The latter definition is
helpful in the context of masks.

The function is trivial; this is *the* canonical check and is
arguably no less clean than calling util_is_power_of_two(x + 1) (the
latter function implemented similarly). Still, it's worth having a
dedicated check for this; semantically, in the context of masks, this
check is meaningful standalone, justifying an independent implementation
from the existing util_is_power_of_two* utilites.

Signed-off-by: Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
Cc: Ian Romanick <ian.d.romanick@intel.com>
Cc: Eduardo Lima Mitev <elima@igalia.com>
---
 src/util/bitscan.h | 9 +++++++++
 1 file changed, 9 insertions(+)

Patch hide | download patch | download mbox

diff --git a/src/util/bitscan.h b/src/util/bitscan.h
index dc89ac93f28..632f7dd2e67 100644
--- a/src/util/bitscan.h
+++ b/src/util/bitscan.h
@@ -158,6 +158,15 @@  util_is_power_of_two_nonzero(unsigned v)
 #endif
 }
 
+/* Determine if an unsigned value is one less than a power-of-two
+ */
+
+static inline bool
+util_is_power_of_two_minus_one(unsigned v)
+{
+   return (v & (v + 1)) == 0;
+}
+
 /* For looping over a bitmask when you want to loop over consecutive bits
  * manually, for example:
  *

Comments

On 6/14/19 9:42 AM, Alyssa Rosenzweig wrote:
> Checks if a number is one less than a power of two. Equivalently, this
> checks if a number is all ones in binary. The latter definition is
> helpful in the context of masks.
> 
> The function is trivial; this is *the* canonical check and is
> arguably no less clean than calling util_is_power_of_two(x + 1) (the

Except it would have to be util_is_power_of_two_or_zero because
util_is_power_of_two(0xffffffff + 1) is false. :)

Is there actually a 2/2 for this?  We usually wouldn't land something
like this without a caller.

> latter function implemented similarly). Still, it's worth having a
> dedicated check for this; semantically, in the context of masks, this
> check is meaningful standalone, justifying an independent implementation
> from the existing util_is_power_of_two* utilites.
> 
> Signed-off-by: Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
> Cc: Ian Romanick <ian.d.romanick@intel.com>
> Cc: Eduardo Lima Mitev <elima@igalia.com>
> ---
>  src/util/bitscan.h | 9 +++++++++
>  1 file changed, 9 insertions(+)
> 
> diff --git a/src/util/bitscan.h b/src/util/bitscan.h
> index dc89ac93f28..632f7dd2e67 100644
> --- a/src/util/bitscan.h
> +++ b/src/util/bitscan.h
> @@ -158,6 +158,15 @@ util_is_power_of_two_nonzero(unsigned v)
>  #endif
>  }
>  
> +/* Determine if an unsigned value is one less than a power-of-two
> + */
> +
> +static inline bool
> +util_is_power_of_two_minus_one(unsigned v)
> +{
> +   return (v & (v + 1)) == 0;

This will return true for v == 0.  Is that the desired behavior?  I
mean, that is 2**0 - 1, but it is not "all ones in binary."  I think the
result may surprise people wanting to use this to detect a mask.  This
is also how we ended up with util_is_power_of_two_nonzero and
util_is_power_of_two_or_zero.

> +}
> +
>  /* For looping over a bitmask when you want to loop over consecutive bits
>   * manually, for example:
>   *
>