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

[Laszlo Ersek]

On 5/16/23 14:29, 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.

I think the mental gyrations stay with us, just in reverse:
__builtin_clzll() takes an "unsigned long long", but we're passing it a
uint64_t. :)

We might want to add:

STATIC_ASSERT (
  __builtin_types_compatible_p (unsigned long long, uint64_t),
  _ull_is_uint64
);

or something like that.

Laszlo

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