[Libguestfs] [PATCH nbdkit v2 3/6] common/include: Add next_power_of_2 function

[Eric Blake]

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