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

[Markus Armbruster]

Alexey Kardashevskiy <address@hidden> writes:

> This adds a helper to get closest bigger power-of-two value.
>
> Signed-off-by: Alexey Kardashevskiy <address@hidden>
> ---
> 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);
}