On 2021-12-29 10:18 p.m., Jonathan Gray wrote:
> On Wed, Dec 29, 2021 at 09:27:34PM -0700, Ted Bullock wrote:
>> This is around documenting peculiar behaviour around power of 2 math in
>> the kernel.
>>
>> I'm wondering if it's worth documenting the peculiarities here, and
>> possibly putting an actually mathematically correct check somewhere in
>> the kernel or maybe userland? Perhaps hypothetical PEER REVIEWED
>> functions with prototypes like isnpotu(uint64_t n) or isnpot(int64_t n).
>>
>> Is this at all worthwhile? Maybe this would help stop people from
>> incorrectly reinventing the wheel?
>>
>> For instance in the kernel right now there is :
>> radeon_check_pot_argument
>> IS_POWER_OF_2
>> is_power_of_2
>> is_power_of_2_u64
>> powerof2
>> probably others too.
>
> IS_POWER_OF_2 and is_power_of_2_u64 are inteldrm specific
> is_power_of_2 is a linux interface.
>
> radeon_check_pot_argument should be replaced in linux by
> is_power_of_2.
> https://lists.freedesktop.org/archives/amd-gfx/2021-December/073108.html
>
> No code outside of drm should be using the linux interfaces and
> I don't think we should be documenting them.
I've taken some time to write what I believe is correct implementations
of the power of two tests for both signed and unsigned cases and written
a manual for both the original powerof2() macro and my functions. Unlike
the macro these actually give the correct response for 0 and INT_MIN. I
also performed a fairly extensive namespace collision search and didn't
find any function name collisions but this was not exhaustive.
The goal here is to provide a mathematically correct power of two test
and associated documentation. I put the new tests in sys/params.h
because the old (inaccurate) test from bsd 4.3 tahoe has the macro
there.
I deliberately did not correct the logic of the macro as per the thread
years ago here : https://marc.info/?t=14432152764=1=2
I used int for the return type though in the c99 era it could be bool I
suppose; maybe 23 years since that standard was published is too soon to
use bool. :P
I hope that people can use this. Please review.
I wrote a short test program to verify I'm not crazy as well. Here are
the results:
Calculating powers of two:
powerof2(INT_MIN): true
powerof2(-2): false
powerof2(0): true
powerof2(2): true
powerof2(4): true
powerof2(8): true
powerof2(16): true
powerof2(INT_MAX): false
isupow2(0): false
isupow2(2): true
isupow2(4): true
isupow2(8): true
isupow2(16): true
isupow2(77): false
isupow2(UINT_MAX): false
isnpow2(INT_MIN): false
isnpow2(-2): false
isnpow2(0): false
isnpow2(2): true
isnpow2(4): true
isnpow2(8): true
isnpow2(16): true
isnpow2(INT_MAX): false
Index: sys/sys/param.h
===
RCS file: /cvs/src/sys/sys/param.h,v
retrieving revision 1.135
diff -u -p -u -p -r1.135 param.h
--- sys/sys/param.h 19 Sep 2021 16:55:01 - 1.135
+++ sys/sys/param.h 31 Dec 2021 00:33:45 -
@@ -186,7 +186,17 @@
#definehowmany(x, y) (((x)+((y)-1))/(y))
#endif
#defineroundup(x, y) x)+((y)-1))/(y))*(y))
-#define powerof2(x)x)-1)&(x))==0)
+#definepowerof2(x) x)-1)&(x))==0)
+static inline int
+isupow2(uint64_t u)
+{
+ return ((u & (u - 1)) == 0) && (u != 0);
+}
+static inline int
+isnpow2(int64_t n)
+{
+ return ((n & (n - 1)) == 0) && (n > 0);
+}
/* Macros for min/max. */
#defineMIN(a,b) (((a)<(b))?(a):(b))
Also inline here is the complete text of the manual I wrote:
.\" Copyright (c) 2021 Ted Bullock
.\"
.\" Permission to use, copy, modify, and distribute this software for any
.\" purpose with or without fee is hereby granted, provided that the above
.\" copyright notice and this permission notice appear in all copies.
.\"
.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
.\"
.Dd $\Mdocdate$
.Dt powerof2 3
.Os
.Sh NAME
.Nm powerof2
.Nm isupow2
.Nm is2pow2
.Nd tests integer for power of two
.Sh SYNOPSIS
.In sys/params.h
.Fd #define powerof2(x) x)-1)&(x))==0)
.Ft int
.Fo isupow2
.Fa "uint64_t"
.Fc
.Ft int
.Fo isnpow2
.Fa "int64_t"
.Fc
.Sh DESCRIPTION
These tests check if an integer value is a power of two.
.Pp
The
.Fn powerof2
macro expands to a logical expression that relies on comparing the binary
complement of the
.Fa x
parameter. When
.Fa x
is an
.Vt integer
or
.Vt unsigned
power of two, the binary complement will be
.Fa x - 1
and the expression will evaluate as true. This test incorrectly identifies
zero and
.Dv INT_MIN
