From 1096537bdc1c23affc5eedfba311d37c7bf647bf Mon Sep 17 00:00:00 2001 From: Scott Wood Date: Mon, 25 Dec 2006 18:58:40 -0600 Subject: [PATCH] Use GCC builtins for bit scanning. The minor benefit is that it is non-arch-specific; the major benefit is that it can be done at compile-time when the argument is a constant. --- include/c/lowlevel/arch-x64/bitops.h | 46 +------------------- include/c/lowlevel/arch-x86-common/bitops.h | 19 ++++++++ include/c/lowlevel/arch-x86/bitops.h | 48 +-------------------- include/c/lowlevel/bitops.h | 32 +++++++++++++- 4 files changed, 52 insertions(+), 93 deletions(-) create mode 100644 include/c/lowlevel/arch-x86-common/bitops.h diff --git a/include/c/lowlevel/arch-x64/bitops.h b/include/c/lowlevel/arch-x64/bitops.h index e165c6d..c92b2cd 100644 --- a/include/c/lowlevel/arch-x64/bitops.h +++ b/include/c/lowlevel/arch-x64/bitops.h @@ -1,50 +1,6 @@ -// Bit manipulation functions. These functions are not privileged. - #ifndef _LL_ARCH_BITOPS_H #define _LL_ARCH_BITOPS_H -// Find First (least-significant) Set, counting from 0, -// undefined if no bits set - -static inline int ll_ffs(unsigned long val) -{ - unsigned long ret; - asm("bsfq %1, %0" : "=r" (ret) : "r" (val)); - return ret; -} - -// Find Last (most-significant) Set, counting from 0, -// undefined if no bits set - -static inline int ll_fls(unsigned long val) -{ - unsigned long ret; - asm("bsrq %1, %0" : "=r" (ret) : "r" (val)); - return ret; -} - -// As above, but on 64-bit values, regardless of sizeof(long) -static inline int ll_ffs64(uint64_t val) -{ - return ll_ffs(val); -} - -static inline int ll_fls64(uint64_t val) -{ - return ll_fls(val); -} - -// Set/Clear the nth bit in a multiword bitmap. These functions -// are endian and word-size dependent. - -static inline void ll_multiword_set_bit(unsigned long *bitmap, int bit) -{ - asm("bts %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); -} - -static inline void ll_multiword_clear_bit(unsigned long *bitmap, int bit) -{ - asm("btr %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); -} +#include #endif diff --git a/include/c/lowlevel/arch-x86-common/bitops.h b/include/c/lowlevel/arch-x86-common/bitops.h new file mode 100644 index 0000000..beca262 --- /dev/null +++ b/include/c/lowlevel/arch-x86-common/bitops.h @@ -0,0 +1,19 @@ +// Bit manipulation functions. These functions are not privileged. + +#ifndef _LL_ARCH_X86C_BITOPS_H +#define _LL_ARCH_X86C_BITOPS_H + +// Set/Clear the nth bit in a multiword bitmap. These functions +// are endian and word-size dependent. + +static inline void ll_multiword_set_bit(unsigned long *bitmap, int bit) +{ + asm("bts %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); +} + +static inline void ll_multiword_clear_bit(unsigned long *bitmap, int bit) +{ + asm("btr %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); +} + +#endif diff --git a/include/c/lowlevel/arch-x86/bitops.h b/include/c/lowlevel/arch-x86/bitops.h index aa60841..c92b2cd 100644 --- a/include/c/lowlevel/arch-x86/bitops.h +++ b/include/c/lowlevel/arch-x86/bitops.h @@ -1,52 +1,6 @@ -// Bit manipulation functions. These functions are not privileged. - #ifndef _LL_ARCH_BITOPS_H #define _LL_ARCH_BITOPS_H -// Find First Set, counting from 0, undefined if no bits set -static inline int ll_ffs(unsigned long val) -{ - unsigned long ret; - asm("bsfl %1, %0" : "=r" (ret) : "r" (val)); - return ret; -} - -// Find Last Set, counting from 0, undefined if no bits set -static inline int ll_fls(unsigned long val) -{ - unsigned long ret; - asm("bsrl %1, %0" : "=r" (ret) : "r" (val)); - return ret; -} - -// As above, but on 64-bit values, regardless of sizeof(long) -static inline int ll_ffs64(uint64_t val) -{ - if ((uint32_t)val) - return ll_ffs((uint32_t)val); - else - return ll_ffs((uint32_t)(val >> 32)); -} - -static inline int ll_fls64(uint64_t val) -{ - if ((uint32_t)(val >> 32)) - return ll_ffs((uint32_t)(val >> 32)); - else - return ll_ffs((uint32_t)val); -} - -// Set/Clear the nth bit in a multiword bitmap. These functions -// are endian and word-size dependent. - -static inline void ll_multiword_set_bit(unsigned long *bitmap, int bit) -{ - asm("bts %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); -} - -static inline void ll_multiword_clear_bit(unsigned long *bitmap, int bit) -{ - asm("btr %1, %0" : "=m" (bitmap[0]) : "r" (bit) : "memory"); -} +#include #endif diff --git a/include/c/lowlevel/bitops.h b/include/c/lowlevel/bitops.h index 9c3ce7e..6aa9029 100644 --- a/include/c/lowlevel/bitops.h +++ b/include/c/lowlevel/bitops.h @@ -7,9 +7,39 @@ #include #include _LL_INC(bitops.h) +// Find First (least-significant) Set, counting from 0, +// undefined if no bits set + +static inline int ll_ffs(unsigned long val) +{ + return __builtin_ctzl(val); +} + +// Find Last (most-significant) Set, counting from 0, +// undefined if no bits set + +static inline int ll_fls(unsigned long val) +{ + return (sizeof(unsigned long)*8 - 1) ^ __builtin_clzl(val); +} + +// As above, except on 64-bit values regardless of sizeof(long). +static inline int ll_ffs64(uint64_t val) +{ + return __builtin_ctzll(val); +} + +// Find Last (most-significant) Set, counting from 0, +// undefined if no bits set + +static inline int ll_fls64(unsigned long val) +{ + return (sizeof(unsigned long long)*8 - 1) ^ __builtin_clzll(val); +} + static inline int ll_get_order_round_up(unsigned long val) { - return val != 1 ? ll_fls(val - 1) + 1 : 0; + return val > 1 ? ll_fls(val - 1) + 1 : 0; } static inline int ll_get_order_round_down(unsigned long val) -- 2.39.2