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

[Eric Blake]

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
> 

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org