From c3b66566760dd44eaeed9e4df13687dc3ee69bd9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Mathias=20Fr=C3=B6hlich?= Date: Thu, 9 Jun 2016 06:35:34 +0200 Subject: [PATCH] mesa/gallium: Move u_bit_scan{,64} from gallium to util. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The functions are also useful for mesa. Introduce src/util/bitscan.{h,c}. Move ffs function implementations from src/mesa/main/imports.{h,c}. Move bit scan related functions from src/gallium/auxiliary/util/u_math.h. Merge platform handling with what is available from within mesa. v2: Try to fix MSVC compile. Reviewed-by: Brian Paul Tested-by: Brian Paul Signed-off-by: Mathias Fröhlich --- src/gallium/auxiliary/util/u_math.h | 149 +---------------------------------- src/mesa/main/imports.c | 58 -------------- src/mesa/main/imports.h | 17 +--- src/util/Makefile.sources | 2 + src/util/bitscan.c | 80 +++++++++++++++++++ src/util/bitscan.h | 153 ++++++++++++++++++++++++++++++++++++ 6 files changed, 237 insertions(+), 222 deletions(-) create mode 100644 src/util/bitscan.c create mode 100644 src/util/bitscan.h diff --git a/src/gallium/auxiliary/util/u_math.h b/src/gallium/auxiliary/util/u_math.h index ecb1d63..c94967e 100644 --- a/src/gallium/auxiliary/util/u_math.h +++ b/src/gallium/auxiliary/util/u_math.h @@ -46,14 +46,7 @@ #include #include -#ifdef PIPE_OS_UNIX -#include /* for ffs */ -#endif - -#if defined(_MSC_VER) -#include -#endif - +#include "util/bitscan.h" #ifdef __cplusplus extern "C" { @@ -354,80 +347,6 @@ util_half_inf_sign(int16_t x) /** - * 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) -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 - -#ifdef HAVE___BUILTIN_FFSLL -#define ffsll __builtin_ffsll -#else -static inline int -ffsll(long long int val) -{ - int bit; - - bit = ffs((unsigned) (val & 0xffffffff)); - if (bit != 0) - return bit; - - bit = ffs((unsigned) (val >> 32)); - if (bit != 0) - return 32 + bit; - - return 0; -} -#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. */ @@ -479,72 +398,6 @@ util_last_bit_signed(int i) 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 &= ~(1u << 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 - -/* For looping over a bitmask when you want to loop over consecutive bits - * manually, for example: - * - * while (mask) { - * int start, count, i; - * - * u_bit_scan_consecutive_range(&mask, &start, &count); - * - * for (i = 0; i < count; i++) - * ... process element (start+i) - * } - */ -static inline void -u_bit_scan_consecutive_range(unsigned *mask, int *start, int *count) -{ - if (*mask == 0xffffffff) { - *start = 0; - *count = 32; - *mask = 0; - return; - } - *start = ffs(*mask) - 1; - *count = ffs(~(*mask >> *start)) - 1; - *mask &= ~(((1u << *count) - 1) << *start); -} - -static inline void -u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count) -{ - if (*mask == ~0llu) { - *start = 0; - *count = 64; - *mask = 0; - return; - } - *start = ffsll(*mask) - 1; - *count = ffsll(~(*mask >> *start)) - 1; - *mask &= ~(((1llu << *count) - 1) << *start); -} - /* Returns a bitfield in which the first count bits starting at start are * set. */ diff --git a/src/mesa/main/imports.c b/src/mesa/main/imports.c index fe54109..808b8f6 100644 --- a/src/mesa/main/imports.c +++ b/src/mesa/main/imports.c @@ -219,64 +219,6 @@ _mesa_align_realloc(void *oldBuffer, size_t oldSize, size_t newSize, /*@{*/ -#ifndef HAVE___BUILTIN_FFS -/** - * Find the first bit set in a word. - */ -int -ffs(int i) -{ - register 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 - -#ifndef HAVE___BUILTIN_FFSLL -/** - * Find position of first bit set in given value. - * XXX Warning: this function can only be used on 64-bit systems! - * \return position of least-significant bit set, starting at 1, return zero - * if no bits set. - */ -int -ffsll(long long int val) -{ - int bit; - - STATIC_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 - - #ifndef HAVE___BUILTIN_POPCOUNT /** * Return number of bits set in given GLuint. diff --git a/src/mesa/main/imports.h b/src/mesa/main/imports.h index d96d666..4ff5941 100644 --- a/src/mesa/main/imports.h +++ b/src/mesa/main/imports.h @@ -42,6 +42,7 @@ #include "compiler.h" #include "glheader.h" #include "errors.h" +#include "util/bitscan.h" #ifdef __cplusplus extern "C" { @@ -324,22 +325,6 @@ extern void _mesa_exec_free( void *addr ); -#ifndef FFS_DEFINED -#define FFS_DEFINED 1 -#ifdef HAVE___BUILTIN_FFS -#define ffs __builtin_ffs -#else -extern int ffs(int i); -#endif - -#ifdef HAVE___BUILTIN_FFSLL -#define ffsll __builtin_ffsll -#else -extern int ffsll(long long int i); -#endif -#endif /* FFS_DEFINED */ - - #ifdef HAVE___BUILTIN_POPCOUNT #define _mesa_bitcount(i) __builtin_popcount(i) #else diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources index a871146..aec41c3 100644 --- a/src/util/Makefile.sources +++ b/src/util/Makefile.sources @@ -1,4 +1,6 @@ MESA_UTIL_FILES := \ + bitscan.c \ + bitscan.h \ bitset.h \ debug.c \ debug.h \ diff --git a/src/util/bitscan.c b/src/util/bitscan.c new file mode 100644 index 0000000..ceca59e --- /dev/null +++ b/src/util/bitscan.c @@ -0,0 +1,80 @@ +/************************************************************************** + * + * Copyright 2008 VMware, Inc. + * All Rights Reserved. + * + * 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, sub license, 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 (including the + * next paragraph) 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 NON-INFRINGEMENT. + * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS 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. + * + **************************************************************************/ + + +#include "bitscan.h" + +#ifdef HAVE___BUILTIN_FFS +#elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64) +#else +int +ffs(unsigned i) +{ + int bit = 0; + if (!i) + return bit; + if (!(i & 0xffff)) { + bit += 16; + i >>= 16; + } + if (!(i & 0xff)) { + bit += 8; + i >>= 8; + } + if (!(i & 0xf)) { + bit += 4; + i >>= 4; + } + if (!(i & 0x3)) { + bit += 2; + i >>= 2; + } + if (!(i & 0x1)) + bit += 1; + return bit + 1; +} +#endif + +#ifdef HAVE___BUILTIN_FFSLL +#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64) +#else +int +ffsll(uint64_t val) +{ + int bit; + + bit = ffs((unsigned) (val & 0xffffffff)); + if (bit != 0) + return bit; + + bit = ffs((unsigned) (val >> 32)); + if (bit != 0) + return 32 + bit; + + return 0; +} +#endif diff --git a/src/util/bitscan.h b/src/util/bitscan.h new file mode 100644 index 0000000..4999b74 --- /dev/null +++ b/src/util/bitscan.h @@ -0,0 +1,153 @@ +/************************************************************************** + * + * Copyright 2008 VMware, Inc. + * All Rights Reserved. + * + * 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, sub license, 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 (including the + * next paragraph) 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 NON-INFRINGEMENT. + * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS 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. + * + **************************************************************************/ + + +#ifndef BITSCAN_H +#define BITSCAN_H + +#include + +#if defined(_MSC_VER) +#include +#endif + +#include "c99_compat.h" + +#ifdef __cplusplus +extern "C" { +#endif + + +/** + * Find first bit set in word. Least significant bit is 1. + * Return 0 if no bits set. + */ +#ifdef HAVE___BUILTIN_FFS +#define ffs __builtin_ffs +#elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64) +static inline +int ffs(unsigned i) +{ + unsigned long index; + if (_BitScanForward(&index, i)) + return index + 1; + else + return 0; +} +#else +extern +int ffs(unsigned i); +#endif + +#ifdef HAVE___BUILTIN_FFSLL +#define ffsll __builtin_ffsll +#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64) +static inline int +ffsll(uint64_t i) +{ + unsigned long index; + if (_BitScanForward64(&index, i)) + return index + 1; + else + return 0; +} +#else +extern int +ffsll(uint64_t val); +#endif + + +/* 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) +{ + const int i = ffs(*mask) - 1; + *mask ^= (1u << i); + return i; +} + +static inline int +u_bit_scan64(uint64_t *mask) +{ + const int i = ffsll(*mask) - 1; + *mask ^= (((uint64_t)1) << i); + return i; +} + +/* For looping over a bitmask when you want to loop over consecutive bits + * manually, for example: + * + * while (mask) { + * int start, count, i; + * + * u_bit_scan_consecutive_range(&mask, &start, &count); + * + * for (i = 0; i < count; i++) + * ... process element (start+i) + * } + */ +static inline void +u_bit_scan_consecutive_range(unsigned *mask, int *start, int *count) +{ + if (*mask == 0xffffffff) { + *start = 0; + *count = 32; + *mask = 0; + return; + } + *start = ffs(*mask) - 1; + *count = ffs(~(*mask >> *start)) - 1; + *mask &= ~(((1u << *count) - 1) << *start); +} + +static inline void +u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count) +{ + if (*mask == ~0llu) { + *start = 0; + *count = 64; + *mask = 0; + return; + } + *start = ffsll(*mask) - 1; + *count = ffsll(~(*mask >> *start)) - 1; + *mask &= ~(((((uint64_t)1) << *count) - 1) << *start); +} + + +#ifdef __cplusplus +} +#endif + +#endif /* BITSCAN_H */ -- 2.7.4