Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster <armbru@redhat.com>]

Alexey Kardashevskiy <aik@ozlabs.ru> writes:

> On 02/24/2015 12:59 AM, Markus Armbruster wrote:
>> Alexey Kardashevskiy <aik@ozlabs.ru> writes:
>>
>>> This adds a helper to get closest bigger power-of-two value.
>>>
>>> Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
>>> ---
>>> Changes:
>>> v2:
>>> * s/up_pow_of_two/pow2ceil/
>>> ---
>>>   include/qemu-common.h | 2 ++
>>>   util/cutils.c         | 9 +++++++++
>>>   2 files changed, 11 insertions(+)
>>>
>>> diff --git a/include/qemu-common.h b/include/qemu-common.h
>>> index 644b46d..ae29748 100644
>>> --- a/include/qemu-common.h
>>> +++ b/include/qemu-common.h
>>> @@ -417,6 +417,8 @@ static inline bool is_power_of_2(uint64_t value)
>>>
>>>   /* round down to the nearest power of 2*/
>>>   int64_t pow2floor(int64_t value);
>>> +/* round up to the nearest power of 2*/
>>> +int64_t pow2ceil(int64_t value);
>>>
>>>   #include "qemu/module.h"
>>>
>>> diff --git a/util/cutils.c b/util/cutils.c
>>> index dbe7412..ecaa440 100644
>>> --- a/util/cutils.c
>>> +++ b/util/cutils.c
>>> @@ -483,6 +483,15 @@ int64_t pow2floor(int64_t value)
>>>       return value;
>>>   }
>>>
>>> +/* round up to the nearest power of 2*/
>>> +int64_t pow2ceil(int64_t value)
>>> +{
>>> +    if (!is_power_of_2(value)) {
>>> +        value = 0x8000000000000000ULL >> (clz64(value) - 1);
>>> +    }
>>> +    return value;
>>> +}
>>> +
>>>   /*
>>>    * Implementation of  ULEB128 (http://en.wikipedia.org/wiki/LEB128)
>>>    * Input is limited to 14-bit numbers
>>
>> pow2ceil(INT64_MIN) = INT64_MIN.  Should be 1.
>>
>> pow2ceil(INT64_MAX) = INT64_MIN.  Garbage.
>>
>> Related: "round down to the nearest power of 2" is defined only for x >
>> 0, but our pow2floor(x) happily returns garbage then.
>>
>> In particular we return 0x8000000000000000ULL >> 64 when value is 0,.
>> Undefined behavior.
>>
>> Here's how I'd do these functions:
>>
>> int64_t pow2floor(int64_t value)
>> {
>>      assert(value > 0);
>>      return 0x8000000000000000u >> clz64(value);
>> }
>>
>> int64_t pow2ceil(int64_t value)
>> {
>>      assert(value <= 0x4000000000000000)
>>      if (value <= 1)
>> 	return 1;
>>      return 0x8000000000000000u >> (clz64(value - 1) - 1);
>> }
>>
>
>
> I've read the whole thread, that was cool :)

I indulged in a bit of language lawyering, glad you liked it.

> Do you want me to repost your versions as a patch? I do not feel I
> should since it is totally yours but I can :)

I'll post a patch fixing the existing pow2floor().  I prefer not to add
pow2ceil() without a user.  If you have one, I suggest you do your
patches on top of mine.