Re: [Qemu-devel] [PATCH v3] bitops: unify bitops_ffsl with the one in host-utils.h, call it bitops_ctzl

[Blue Swirl]

Thanks, applied.

On Fri, Feb 1, 2013 at 10:03 PM, Paolo Bonzini <address@hidden> wrote:
> We had two copies of a ffs function for longs with subtly different
> semantics and, for the one in bitops.h, a confusing name: the result
> was off-by-one compared to the library function ffsl.
>
> Unify the functions into one, and solve the name problem by calling
> the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively.
>
> This also fixes the build on platforms with ffsl, including Mac OS X
> and Windows.
>
> Signed-off-by: Paolo Bonzini <address@hidden>
> ---
>  include/qemu/bitops.h     | 55 
> +++++++++++++++++++----------------------------
>  include/qemu/hbitmap.h    |  2 +-
>  include/qemu/host-utils.h | 26 ----------------------
>  memory.c                  |  4 ++--
>  util/bitops.c             |  4 ++--
>  util/hbitmap.c            |  2 +-
>  6 files changed, 28 insertions(+), 65 deletions(-)
>
> diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h
> index 74e14e5..8b88791 100644
> --- a/include/qemu/bitops.h
> +++ b/include/qemu/bitops.h
> @@ -13,6 +13,7 @@
>  #define BITOPS_H
>
>  #include "qemu-common.h"
> +#include "host-utils.h"
>
>  #define BITS_PER_BYTE           CHAR_BIT
>  #define BITS_PER_LONG           (sizeof (unsigned long) * BITS_PER_BYTE)
> @@ -23,41 +24,29 @@
>  #define BITS_TO_LONGS(nr)      DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
>
>  /**
> - * bitops_ffs - find first bit in word.
> + * bitops_ctzl - count trailing zeroes in word.
>   * @word: The word to search
>   *
> - * Undefined if no bit exists, so code should check against 0 first.
> + * Returns -1 if no bit exists.  Note that compared to the C library
> + * routine ffsl, this one returns one less.
>   */
> -static unsigned long bitops_ffsl(unsigned long word)
> +static unsigned long bitops_ctzl(unsigned long word)
>  {
> -       int num = 0;
> +#if QEMU_GNUC_PREREQ(3, 4)
> +    return __builtin_ffsl(word) - 1;
> +#else
> +    if (!word) {
> +        return -1;
> +    }
>
> -#if LONG_MAX > 0x7FFFFFFF
> -       if ((word & 0xffffffff) == 0) {
> -               num += 32;
> -               word >>= 32;
> -       }
> +    if (sizeof(long) == 4) {
> +        return ctz32(word);
> +    } else if (sizeof(long) == 8) {
> +        return ctz64(word);
> +    } else {
> +        abort();
> +    }
>  #endif
> -       if ((word & 0xffff) == 0) {
> -               num += 16;
> -               word >>= 16;
> -       }
> -       if ((word & 0xff) == 0) {
> -               num += 8;
> -               word >>= 8;
> -       }
> -       if ((word & 0xf) == 0) {
> -               num += 4;
> -               word >>= 4;
> -       }
> -       if ((word & 0x3) == 0) {
> -               num += 2;
> -               word >>= 2;
> -       }
> -       if ((word & 0x1) == 0) {
> -               num += 1;
> -        }
> -       return num;
>  }
>
>  /**
> @@ -99,14 +88,14 @@ static inline unsigned long bitops_flsl(unsigned long 
> word)
>  }
>
>  /**
> - * ffz - find first zero in word.
> + * cto - count trailing ones in word.
>   * @word: The word to search
>   *
> - * Undefined if no zero exists, so code should check against ~0UL first.
> + * Returns -1 if all bit are set.
>   */
> -static inline unsigned long ffz(unsigned long word)
> +static inline unsigned long bitops_ctol(unsigned long word)
>  {
> -    return bitops_ffsl(~word);
> +    return bitops_ctzl(~word);
>  }
>
>  /**
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index 73f5d1d..250de03 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -170,7 +170,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
>
>      /* The next call will resume work from the next bit.  */
>      hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> -    item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ffsl(cur) - 1;
> +    item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + bitops_ctzl(cur);
>
>      return item << hbi->granularity;
>  }
> diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h
> index 2a32be4..81c9a75 100644
> --- a/include/qemu/host-utils.h
> +++ b/include/qemu/host-utils.h
> @@ -26,7 +26,6 @@
>  #define HOST_UTILS_H 1
>
>  #include "qemu/compiler.h"   /* QEMU_GNUC_PREREQ */
> -#include <string.h>     /* ffsl */
>
>  #if defined(__x86_64__)
>  #define __HAVE_FAST_MULU64__
> @@ -238,29 +237,4 @@ static inline int ctpop64(uint64_t val)
>  #endif
>  }
>
> -/* glibc does not provide an inline version of ffsl, so always define
> - * ours.  We need to give it a different name, however.
> - */
> -#ifdef __GLIBC__
> -#define ffsl qemu_ffsl
> -#endif
> -static inline int ffsl(long val)
> -{
> -    if (!val) {
> -        return 0;
> -    }
> -
> -#if QEMU_GNUC_PREREQ(3, 4)
> -    return __builtin_ctzl(val) + 1;
> -#else
> -    if (sizeof(long) == 4) {
> -        return ctz32(val) + 1;
> -    } else if (sizeof(long) == 8) {
> -        return ctz64(val) + 1;
> -    } else {
> -        abort();
> -    }
> -#endif
> -}
> -
>  #endif
> diff --git a/memory.c b/memory.c
> index 410c5f8..cd7d5e0 100644
> --- a/memory.c
> +++ b/memory.c
> @@ -855,7 +855,7 @@ static uint64_t memory_region_dispatch_read1(MemoryRegion 
> *mr,
>      }
>
>      if (!mr->ops->read) {
> -        return mr->ops->old_mmio.read[bitops_ffsl(size)](mr->opaque, addr);
> +        return mr->ops->old_mmio.read[bitops_ctzl(size)](mr->opaque, addr);
>      }
>
>      /* FIXME: support unaligned access */
> @@ -908,7 +908,7 @@ static void memory_region_dispatch_write(MemoryRegion *mr,
>      adjust_endianness(mr, &data, size);
>
>      if (!mr->ops->write) {
> -        mr->ops->old_mmio.write[bitops_ffsl(size)](mr->opaque, addr, data);
> +        mr->ops->old_mmio.write[bitops_ctzl(size)](mr->opaque, addr, data);
>          return;
>      }
>
> diff --git a/util/bitops.c b/util/bitops.c
> index 4c3a836..7b853cf 100644
> --- a/util/bitops.c
> +++ b/util/bitops.c
> @@ -60,7 +60,7 @@ found_first:
>          return result + size;  /* Nope. */
>      }
>  found_middle:
> -    return result + bitops_ffsl(tmp);
> +    return result + bitops_ctzl(tmp);
>  }
>
>  /*
> @@ -109,7 +109,7 @@ found_first:
>          return result + size;  /* Nope. */
>      }
>  found_middle:
> -    return result + ffz(tmp);
> +    return result + bitops_ctol(tmp);
>  }
>
>  unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 2aa487d..a0df5d3 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -126,7 +126,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
>           * The index of this word's least significant set bit provides
>           * the low-order bits.
>           */
> -        pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1;
> +        pos = (pos << BITS_PER_LEVEL) + bitops_ctzl(cur);
>          hbi->cur[i] = cur & (cur - 1);
>
>          /* Set up next level for iteration.  */
> --
> 1.8.1
>