On Wed, May 17, 2023 at 11:06:56AM +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. > > Thanks: Eric Blake > --- > common/include/ispowerof2.h | 9 +++++++++ > common/include/test-ispowerof2.c | 15 +++++++++++++++ > 2 files changed, 24 insertions(+) > > diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h > index f067caf07..a4cb52de3 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)); > +}
Still mishandles anything >= INT64_MAX+1ULL. __builtin_clzll(0xffffffffffffffffULL - 1) gives 0, but UINT64_C(1) << (64-0) is undefined behavior. We've already declared elsewhere that the maximum size that nbdkit will handle is 2^63-1 (ie. INT64_MAX), not 2^64-1 (UINT64_MAX); this is because off_t is a signed value, and it gets really hard to work with anything larger than what off_t can hold. But it's still probably worth documenting what we want to do for out-of-range values, rather than blindly assuming that plugins will only use this function on values that are already appropriate as sizes. Maybe adjust the signature to: static inline uint64_t next_power_of_2 (int64_t x) where all negative input values map to (uint64_t)(-1) as an out-of-range indicator? > + > #endif /* NBDKIT_ISPOWEROF2_H */ > diff --git a/common/include/test-ispowerof2.c > b/common/include/test-ispowerof2.c > index 9620192f0..1221ac09c 100644 > --- a/common/include/test-ispowerof2.c > +++ b/common/include/test-ispowerof2.c > @@ -68,5 +68,20 @@ main (void) > assert (log_2_bits (0x8000000000000000) == 63); > #endif > > + /* Test next power of 2. */ > + assert (next_power_of_2 (0) == 1); Do we want this to be 1 (your choice of 'x <= 1 ? 1 : ...') or 0 (my suggestion of 'x <= 1 ? x : ...')? > + assert (next_power_of_2 (1) == 1); > + 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); While this tests that you handle more than 32 bits, it still doesn't test what happens when the most-significant bit is set (there's the special case of 0x8000000000000000ULL returning itself; all other values goes back to my question of whether we should have some sentinel for out-of-range). -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org _______________________________________________ Libguestfs mailing list Libguestfs@redhat.com https://listman.redhat.com/mailman/listinfo/libguestfs