Re: power of 2 revisited

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=144321527600004&r=1&w=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 -0000 1.135
+++ sys/sys/param.h 31 Dec 2021 00:33:45 -0000
@@ -186,7 +186,17 @@
#define howmany(x, y) (((x)+((y)-1))/(y))