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

[Alexey Kardashevskiy <aik@ozlabs.ru>]

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

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


-- 
Alexey