#include <float.h>
#include <stdarg.h>
-#ifdef PIPE_OS_UNIX
-#include <strings.h> /* for ffs */
-#endif
-
+#include "util/bitscan.h"
#ifdef __cplusplus
extern "C" {
}
-/**
- * Find first bit set in word. Least significant bit is 1.
- * Return 0 if no bits set.
- */
-#ifndef FFS_DEFINED
-#define FFS_DEFINED 1
-
-#if defined(_MSC_VER) && (_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(PIPE_CC_MSVC) && defined(PIPE_ARCH_X86)
-static inline
-unsigned ffs( unsigned u )
-{
- unsigned i;
-
- if (u == 0) {
- return 0;
- }
-
- __asm bsf eax, [u]
- __asm inc eax
- __asm mov [i], eax
-
- return i;
-}
-#elif defined(__MINGW32__) || defined(PIPE_OS_ANDROID) || \
- defined(HAVE___BUILTIN_FFS)
-#define ffs __builtin_ffs
-#endif
-
-#endif /* FFS_DEFINED */
-
-/**
- * Find first bit set in long long. Least significant bit is 1.
- * Return 0 if no bits set.
- */
-#ifndef FFSLL_DEFINED
-#define FFSLL_DEFINED 1
-
-#if defined(__MINGW32__) || defined(PIPE_OS_ANDROID) || \
- defined(HAVE___BUILTIN_FFSLL)
-#define ffsll __builtin_ffsll
-#endif
-
-#endif /* FFSLL_DEFINED */
-
-/**
- * Find last bit set in a word. The least significant bit is 1.
- * Return 0 if no bits are set.
- */
-static inline unsigned
-util_last_bit(unsigned u)
-{
-#if defined(HAVE___BUILTIN_CLZ)
- return u == 0 ? 0 : 32 - __builtin_clz(u);
-#else
- unsigned r = 0;
- while (u) {
- r++;
- u >>= 1;
- }
- return r;
-#endif
-}
-
-/**
- * Find last bit set in a word. The least significant bit is 1.
- * Return 0 if no bits are set.
- */
-static inline unsigned
-util_last_bit64(uint64_t u)
-{
-#if defined(HAVE___BUILTIN_CLZLL)
- return u == 0 ? 0 : 64 - __builtin_clzll(u);
-#else
- unsigned r = 0;
- while (u) {
- r++;
- u >>= 1;
- }
- return r;
-#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 (i >= 0)
- return util_last_bit(i);
- else
- return util_last_bit(~(unsigned)i);
-}
-
-/* Destructively loop over all of the bits in a mask as in:
- *
- * while (mymask) {
- * int i = u_bit_scan(&mymask);
- * ... process element i
- * }
- *
- */
-static inline int
-u_bit_scan(unsigned *mask)
-{
- int i = ffs(*mask) - 1;
- *mask &= ~(1 << i);
- return i;
-}
-
-#ifndef _MSC_VER
-static inline int
-u_bit_scan64(uint64_t *mask)
-{
- int i = ffsll(*mask) - 1;
- *mask &= ~(1llu << i);
- return i;
-}
-#endif
-
/**
* Return float bits.
*/
#endif
}
+/**
+ * Returns the ceiling of log n base 2, and 0 when n == 0. Equivalently,
+ * returns the smallest x such that n <= 2**x.
+ */
+static inline unsigned
+util_logbase2_ceil(unsigned n)
+{
+ if (n <= 1)
+ return 0;
+
+ return 1 + util_logbase2(n - 1);
+}
/**
* Returns the smallest power of two >= x
return (value + alignment - 1) & ~(alignment - 1);
}
+static inline uint64_t
+align64(uint64_t value, unsigned alignment)
+{
+ return (value + alignment - 1) & ~((uint64_t)alignment - 1);
+}
+
/**
* Works like align but on npot alignments.
*/