summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/arch/i386/include/bits/strings.h46
-rw-r--r--src/arch/x86_64/include/bits/strings.h38
-rw-r--r--src/include/strings.h81
-rw-r--r--src/tests/math_test.c74
4 files changed, 233 insertions, 6 deletions
diff --git a/src/arch/i386/include/bits/strings.h b/src/arch/i386/include/bits/strings.h
index 1961a1f9..453545f0 100644
--- a/src/arch/i386/include/bits/strings.h
+++ b/src/arch/i386/include/bits/strings.h
@@ -4,6 +4,50 @@
FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int __ffsl ( long value ) {
+ long lsb_minus_one;
+
+ /* If the input value is zero, the BSF instruction returns
+ * ZF=0 and leaves an undefined value in the output register.
+ * Perform this check in C rather than asm so that it can be
+ * omitted in cases where the compiler is able to prove that
+ * the input is non-zero.
+ */
+ if ( value ) {
+ __asm__ ( "bsfl %1, %0"
+ : "=r" ( lsb_minus_one )
+ : "rm" ( value ) );
+ return ( lsb_minus_one + 1 );
+ } else {
+ return 0;
+ }
+}
+
+/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int __ffsll ( long long value ){
+ unsigned long high = ( value >> 32 );
+ unsigned long low = ( value >> 0 );
+
+ if ( low ) {
+ return ( __ffsl ( low ) );
+ } else if ( high ) {
+ return ( 32 + __ffsl ( high ) );
+ } else {
+ return 0;
+ }
+}
+
+/**
* Find last (i.e. most significant) set bit
*
* @v value Value
@@ -13,7 +57,7 @@ static inline __attribute__ (( always_inline )) int __flsl ( long value ) {
long msb_minus_one;
/* If the input value is zero, the BSR instruction returns
- * ZF=1 and leaves an undefined value in the output register.
+ * ZF=0 and leaves an undefined value in the output register.
* Perform this check in C rather than asm so that it can be
* omitted in cases where the compiler is able to prove that
* the input is non-zero.
diff --git a/src/arch/x86_64/include/bits/strings.h b/src/arch/x86_64/include/bits/strings.h
index a56a911d..3b7911f3 100644
--- a/src/arch/x86_64/include/bits/strings.h
+++ b/src/arch/x86_64/include/bits/strings.h
@@ -4,6 +4,42 @@
FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int __ffsll ( long long value ){
+ long long lsb_minus_one;
+
+ /* If the input value is zero, the BSF instruction returns
+ * ZF=0 and leaves an undefined value in the output register.
+ * Perform this check in C rather than asm so that it can be
+ * omitted in cases where the compiler is able to prove that
+ * the input is non-zero.
+ */
+ if ( value ) {
+ __asm__ ( "bsfq %1, %0"
+ : "=r" ( lsb_minus_one )
+ : "rm" ( value ) );
+ return ( lsb_minus_one + 1 );
+ } else {
+ return 0;
+ }
+}
+
+/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int __ffsl ( long value ) {
+
+ return __ffsll ( value );
+}
+
+/**
* Find last (i.e. most significant) set bit
*
* @v value Value
@@ -13,7 +49,7 @@ static inline __attribute__ (( always_inline )) int __flsll ( long long value ){
long long msb_minus_one;
/* If the input value is zero, the BSR instruction returns
- * ZF=1 and leaves an undefined value in the output register.
+ * ZF=0 and leaves an undefined value in the output register.
* Perform this check in C rather than asm so that it can be
* omitted in cases where the compiler is able to prove that
* the input is non-zero.
diff --git a/src/include/strings.h b/src/include/strings.h
index dec756fe..fab26dc2 100644
--- a/src/include/strings.h
+++ b/src/include/strings.h
@@ -13,6 +13,54 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
#include <bits/strings.h>
/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v x Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int
+__constant_ffsll ( unsigned long long x ) {
+ int r = 0;
+
+ if ( ! ( x & 0x00000000ffffffffULL ) ) {
+ x >>= 32;
+ r += 32;
+ }
+ if ( ! ( x & 0x0000ffffUL ) ) {
+ x >>= 16;
+ r += 16;
+ }
+ if ( ! ( x & 0x00ff ) ) {
+ x >>= 8;
+ r += 8;
+ }
+ if ( ! ( x & 0x0f ) ) {
+ x >>= 4;
+ r += 4;
+ }
+ if ( ! ( x & 0x3 ) ) {
+ x >>= 2;
+ r += 2;
+ }
+ if ( ! ( x & 0x1 ) ) {
+ x >>= 1;
+ r += 1;
+ }
+ return ( x ? ( r + 1 ) : 0 );
+}
+
+/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v x Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+static inline __attribute__ (( always_inline )) int
+__constant_ffsl ( unsigned long x ) {
+ return __constant_ffsll ( x );
+}
+
+/**
* Find last (i.e. most significant) set bit
*
* @v x Value
@@ -46,10 +94,7 @@ __constant_flsll ( unsigned long long x ) {
x >>= 1;
r += 1;
}
- if ( x & 0x1 ) {
- r += 1;
- }
- return r;
+ return ( x ? ( r + 1 ) : 0 );
}
/**
@@ -63,10 +108,38 @@ __constant_flsl ( unsigned long x ) {
return __constant_flsll ( x );
}
+int __ffsll ( long long x );
+int __ffsl ( long x );
int __flsll ( long long x );
int __flsl ( long x );
/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v x Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+#define ffsll( x ) \
+ ( __builtin_constant_p ( x ) ? __constant_ffsll ( x ) : __ffsll ( x ) )
+
+/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v x Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+#define ffsl( x ) \
+ ( __builtin_constant_p ( x ) ? __constant_ffsl ( x ) : __ffsl ( x ) )
+
+/**
+ * Find first (i.e. least significant) set bit
+ *
+ * @v x Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+#define ffs( x ) ffsl ( x )
+
+/**
* Find last (i.e. most significant) set bit
*
* @v x Value
diff --git a/src/tests/math_test.c b/src/tests/math_test.c
index 19af9f6a..1a244f1e 100644
--- a/src/tests/math_test.c
+++ b/src/tests/math_test.c
@@ -39,6 +39,26 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
#include <ipxe/isqrt.h>
/**
+ * Force a call to the non-constant implementation of ffsl()
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+__attribute__ (( noinline )) int ffsl_var ( long value ) {
+ return ffsl ( value );
+}
+
+/**
+ * Force a call to the non-constant implementation of ffsll()
+ *
+ * @v value Value
+ * @ret lsb Least significant bit set in value (LSB=1), or zero
+ */
+__attribute__ (( noinline )) int ffsll_var ( long long value ) {
+ return ffsll ( value );
+}
+
+/**
* Force a call to the non-constant implementation of flsl()
*
* @v value Value
@@ -177,6 +197,44 @@ __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend,
}
/**
+ * Report a ffsl() test result
+ *
+ * @v value Value
+ * @v lsb Expected LSB
+ * @v file Test code file
+ * @v line Test code line
+ */
+static inline __attribute__ (( always_inline )) void
+ffsl_okx ( long value, int lsb, const char *file, unsigned int line ) {
+
+ /* Verify as a constant (requires to be inlined) */
+ okx ( ffsl ( value ) == lsb, file, line );
+
+ /* Verify as a non-constant */
+ okx ( ffsl_var ( value ) == lsb, file, line );
+}
+#define ffsl_ok( value, lsb ) ffsl_okx ( value, lsb, __FILE__, __LINE__ )
+
+/**
+ * Report a ffsll() test result
+ *
+ * @v value Value
+ * @v lsb Expected LSB
+ * @v file Test code file
+ * @v line Test code line
+ */
+static inline __attribute__ (( always_inline )) void
+ffsll_okx ( long long value, int lsb, const char *file, unsigned int line ) {
+
+ /* Verify as a constant (requires to be inlined) */
+ okx ( ffsll ( value ) == lsb, file, line );
+
+ /* Verify as a non-constant */
+ okx ( ffsll_var ( value ) == lsb, file, line );
+}
+#define ffsll_ok( value, lsb ) ffsll_okx ( value, lsb, __FILE__, __LINE__ )
+
+/**
* Report a flsl() test result
*
* @v value Value
@@ -274,6 +332,22 @@ static void s64divmod_okx ( int64_t dividend, int64_t divisor,
*/
static void math_test_exec ( void ) {
+ /* Test ffsl() */
+ ffsl_ok ( 0, 0 );
+ ffsl_ok ( 1, 1 );
+ ffsl_ok ( 255, 1 );
+ ffsl_ok ( 256, 9 );
+ ffsl_ok ( 257, 1 );
+ ffsl_ok ( 0x54850596, 2 );
+ ffsl_ok ( 0x80000000, 32 );
+
+ /* Test ffsll() */
+ ffsll_ok ( 0, 0 );
+ ffsll_ok ( 1, 1 );
+ ffsll_ok ( 0x6d63623330ULL, 5 );
+ ffsll_ok ( 0x80000000UL, 32 );
+ ffsll_ok ( 0x8000000000000000ULL, 64 );
+
/* Test flsl() */
flsl_ok ( 0, 0 );
flsl_ok ( 1, 1 );
generated by cgit v1.2.3-55-g7522 (git 2.39.0) at 2024-05-28 21:31:54 +0200