Richard W.M. Jones
2023-May-16 12:12 UTC
[Libguestfs] [PATCH nbdkit 3/5] common/include: Add next_power_of_2 function
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));
+}
+
#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);
+ 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
2023-May-16 12:29 UTC
[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 >-- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org