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

[Richard W.M. Jones]

On Tue, May 16, 2023 at 07:29:45AM -0500, Eric Blake wrote:
> 
> 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.

Just a note here that the original code being copied [see link above]
does not cast the 1 constant, and in fact does not work past 32 bits.
I think it may be that the original code was tested on Windows which
IIRC has 64 bit 'int'.

> 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...

Good point, will fix.

> >  #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.

Ditto.

Thanks,

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-p2v converts physical machines to virtual machines.  Boot with a
live CD or over the network (PXE) and turn machines into KVM guests.
http://libguestfs.org/virt-v2v