[Mesa-dev] [prefix=PATCH v3 1/3] util: Add a bitcount.h file and move stuff from both mesa and gallium to it

[Ian Romanick]

A couple bikesheds and nits below...

On 10/29/2014 05:25 PM, Jason Ekstrand wrote:
> diff --git a/src/util/bitcount.h b/src/util/bitcount.h
> new file mode 100644
> index 0000000..87d92d5
> --- /dev/null
> +++ b/src/util/bitcount.h
> @@ -0,0 +1,196 @@
> +/*
> + * Mesa 3-D graphics library
> + *
> + * Copyright (C) 1999-2007  Brian Paul   All Rights Reserved.
> + * Copyright (C) 2014 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice shall be included
> + * in all copies or substantial portions of the Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
> + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> + * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
> + * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
> + * OTHER DEALINGS IN THE SOFTWARE.
> + */
> +
> +/**
> + * Various utilities for counting bits.
> + */
> +
> +#ifndef UTIL_BITCOUNT_H
> +#define UTIL_BITCOUNT_H
> +
> +#include <assert.h>
> +#include <string.h>
> +#include <stdint.h>
> +#ifndef _MSC_VER
> +#include <strings.h>
> +#endif
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +
> +/**
> + * Find first bit set in word.  Least significant bit is 1.
> + * Return 0 if no bits set.
> + */
> +#if _SVID_SOURCE || _BSD_SOURCE || _POSIX_C_SOURCE >= 200809L || _XOPEN_SOURCE >= 700 

It seems like we should convert this to HAVE_FFS (and HAVE_FFSL below)
via configure.  Also...

> +/* We get ffs for free */
> +#elif defined(_MSC_VER) && _MSC_VER >= 1300 && (_M_IX86 || _M_AMD64 || _M_IA64)
> +unsigned char _BitScanForward(unsigned long* Index, unsigned long Mask);
> +#pragma intrinsic(_BitScanForward)
> +static inline
> +unsigned long ffs( unsigned long u )
> +{
> +   unsigned long i;
> +   if (_BitScanForward(&i, u))
> +      return i + 1;
> +   else
> +      return 0;
> +}
> +#elif defined(HAVE___BUILTIN_FFS)

...are there any platforms that hit this case but not the previous "ffs
for free" case?

> +#  define ffs __builtin_ffs
> +#else
> +static inline int
> +ffs(int i)
> +{
> +   int bit = 0;
> +   if (i != 0) {
> +      if ((i & 0xffff) == 0) {
> +         bit += 16;
> +         i >>= 16;
> +      }
> +      if ((i & 0xff) == 0) {
> +         bit += 8;
> +         i >>= 8;
> +      }
> +      if ((i & 0xf) == 0) {
> +         bit += 4;
> +         i >>= 4;
> +      }
> +      while ((i & 1) == 0) {
> +         bit++;
> +         i >>= 1;
> +      }
> +      bit++;
> +   }
> +   return bit;
> +}
> +#endif
> +
> +
> +#if defined(_GNU_SOURCE)
> +/* We get ffsll for free */
> +#elif defined(HAVE___BUILTIN_FFSLL)
> +#  define ffsll __builtin_ffsll
> +#else
> +static inline int
> +ffsll(long long int val)
> +{
> +   int bit;
> +
> +   assert(sizeof(val) == 8);
> +
> +   bit = ffs((int) val);
> +   if (bit != 0)
> +      return bit;
> +
> +   bit = ffs((int) (val >> 32));
> +   if (bit != 0)
> +      return 32 + bit;
> +
> +   return 0;
> +}
> +#endif
> +
> +
> +/**
> + * Find the last (most significant) bit set in a word.
> + *
> + * Essentially ffs() in the reverse direction.
> + */
> +static inline unsigned
> +util_last_bit(unsigned n)

fls, please.  At least FreeBSD has fls and flsl in it's C library:

http://www.manpagez.com/man/3/fls/

> +{
> +#ifdef HAVE___BUILTIN_CLZ
> +   return n == 0 ? 0 : 32 - __builtin_clz(n);
> +#else
> +   unsigned int v = 1;
> +
> +   if (n == 0)
> +      return 0;
> +
> +   while (n >>= 1)
> +       v++;
> +
> +   return v;
> +#endif
> +}
> +
> +
> +/**
> + * Find last bit in a word that does not match the sign bit. The least
> + * significant bit is 1.
> + * Return 0 if no bits are set.
> + */
> +static inline unsigned
> +util_last_bit_signed(int i)
> +{
> +#if HAVE___BUILTIN_CLRSB
> +   return 31 - __builtin_clrsb(i);
> +#else
> +   if (i >= 0)
> +      return util_last_bit(i);
> +   else
> +      return util_last_bit(~(unsigned)i);
> +#endif
> +}
> +
> +
> +static inline unsigned
> +util_bitcount(unsigned n)

popcount, please.  At least NetBSD has popcount and popcountll.  OpenCL
also has popcount.

http://www.polarhome.com/service/man/generic.php?qf=popcount&tf=2&of=NetBSD&sf=

https://www.khronos.org/registry/cl/sdk/1.2/docs/man/xhtml/popcount.html

> +{
> +#ifdef HAVE___BUILTIN_POPCOUNT
> +   return __builtin_popcount(n);
> +#else
> +   unsigned bits = 0;
> +   for (; n; bits++) {
> +      n &= n - 1;
> +   }
> +   return bits;
> +#endif
> +}
> +
> +
> +static inline unsigned
> +util_bitcount_64(uint64_t n)
> +{
> +#ifdef HAVE___BUILTIN_POPCOUNTLL
> +   return __builtin_popcountll(n);
> +#define util_bitcount_64(i) __builtin_popcountll(i)
> +   unsigned bits = 0;
> +   for (; n; bits++) {
> +      n &= n - 1;
> +   }
> +   return bits;
> +#endif
> +}
> +
> +
> +#ifdef __cplusplus
> +} /* extern "C" */
> +#endif
> +
> +#endif /* UTIL_BITCOUNT_H */
>