Re: [Libguestfs] [PATCH nbdkit 3/5] common/include: Add next_power_of_2 function

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.

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... > +} > + > #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. > + assert (next_power_of_2 (3) == 4); > + assert (next_power_of_2 (8) == 8); > + assert (next_power_of_2 (9) == 16); > + assert (next_power_of_2 (0xffff) == 0x10000); > + assert (next_power_of_2 (0x10000) == 0x10000); > + assert (next_power_of_2 (UINT64_C ( 0xffffffff)) == 0x100000000); > + assert (next_power_of_2 (UINT64_C (0x100000000)) == 0x100000000); > + assert (next_power_of_2 (UINT64_C (0x200000001)) == 0x400000000); > + assert (next_power_of_2 (UINT64_C (0x6ffffffff)) == 0x800000000); > + assert (next_power_of_2 (UINT64_C (0x700000001)) == 0x800000000); > + assert (next_power_of_2 (UINT64_C (0x800000000)) == 0x800000000); > + > exit (EXIT_SUCCESS); > } > -- > 2.39.2 >