On Tue, May 16, 2023 at 07:29:45AM -0500, Eric Blake wrote:
On Tue, May 16, 2023 at 01:12:17PM +0100, Richard W.M. Jones wrote:
It takes a 64 bit integer and finds the next power of 2, eg. next_power_of_2 (510) => 512 (2^9)
Taken from https://jameshfisher.com/2018/03/30/round-up-power-2/ with some fixes. --- common/include/ispowerof2.h | 9 +++++++++ common/include/test-ispowerof2.c | 14 ++++++++++++++ 2 files changed, 23 insertions(+)
diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h index f067caf07..57ebcc4fd 100644 --- a/common/include/ispowerof2.h +++ b/common/include/ispowerof2.h @@ -59,4 +59,13 @@ log_2_bits (unsigned long v) return SIZEOF_LONG*8 - __builtin_clzl (v) - 1; }
+/* Round up to next power of 2. + * https://jameshfisher.com/2018/03/30/round-up-power-2/ + */ +static inline uint64_t +next_power_of_2 (uint64_t x) +{ + return x == 1 ? 1 : UINT64_C(1) << (64 - __builtin_clzll (x-1));
1ULL is generally shorter spelling for a 64-bit unsigned '1' than UINT64_C(1). On the other hand, it is not necessarily the same type, as some 64-bit platforms ahave uint64_t as 'unsigned long' instead of 'unsigned long long'; so being explicit avoids mental gyrations on deciphering whether the compiler has unexpected type promotion gotchas, so I like your spelling.
Just a note here that the original code being copied [see link above] does not cast the 1 constant, and in fact does not work past 32 bits. I think it may be that the original code was tested on Windows which IIRC has 64 bit 'int'.
next_power_of_2 (0) results in:
1ULL << (64 - __builtin_clzll (-1) 1ULL << (64 - 0) 1ULL << 64
which is undefined behavior. I'd prefer 'x <= 1 ? x : ...' to give us well-defined behavior...
Good point, will fix.
#endif /* NBDKIT_ISPOWEROF2_H */ diff --git a/common/include/test-ispowerof2.c b/common/include/test-ispowerof2.c index 9620192f0..fe37c4a32 100644 --- a/common/include/test-ispowerof2.c +++ b/common/include/test-ispowerof2.c @@ -68,5 +68,19 @@ main (void) assert (log_2_bits (0x8000000000000000) == 63); #endif
+ /* Test next power of 2. */ + assert (next_power_of_2 (1) == 1);
...as well as coverage of an input of 0.
Ditto. Thanks, Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-p2v converts physical machines to virtual machines. Boot with a live CD or over the network (PXE) and turn machines into KVM guests. http://libguestfs.org/virt-v2v