[PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[David Howells]

Provide count_leading/trailing_zeros() macros based on extant arch bit scanning
functions rather than reimplementing from scratch in MPILIB.

Whilst we're at it, turn count_foo_zeros(n, x) into n = count_foo_zeros(x).

Also move the definition to asm-generic as other people may be interested in
using it.

Signed-off-by: David Howells <dhowells@redhat.com>
Cc: David S. Miller <davem@davemloft.net>
Cc: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
Cc: Arnd Bergmann <arnd@arndb.com>
---

 include/asm-generic/bitops/count_zeros.h |   57 ++++++++++++
 lib/mpi/longlong.h                       |  138 ------------------------------
 lib/mpi/mpi-bit.c                        |    2 
 lib/mpi/mpi-div.c                        |    2 
 lib/mpi/mpi-pow.c                        |    4 -
 lib/mpi/mpi-scan.c                       |    2 
 lib/mpi/mpih-div.c                       |    8 +-
 7 files changed, 68 insertions(+), 145 deletions(-)
 create mode 100644 include/asm-generic/bitops/count_zeros.h


diff --git a/include/asm-generic/bitops/count_zeros.h b/include/asm-generic/bitops/count_zeros.h
new file mode 100644
index 0000000..97520d2
--- /dev/null
+++ b/include/asm-generic/bitops/count_zeros.h
@@ -0,0 +1,57 @@
+/* Count leading and trailing zeros functions
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+#define _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+
+#include <asm/bitops.h>
+
+/**
+ * count_leading_zeros - Count the number of zeros from the MSB back
+ * @x: The value
+ *
+ * Count the number of leading zeros from the MSB going towards the LSB in @x.
+ *
+ * If the MSB of @x is set, the result is 0.
+ * If only the LSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_LEADING_ZEROS_0.
+ */
+static inline int count_leading_zeros(unsigned long x)
+{
+	if (sizeof(x) == 4)
+		return BITS_PER_LONG - fls(x);
+	else
+		return BITS_PER_LONG - fls64(x);
+}
+
+#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG
+
+/**
+ * count_trailing_zeros - Count the number of zeros from the LSB forwards
+ * @x: The value
+ *
+ * Count the number of trailing zeros from the LSB going towards the MSB in @x.
+ *
+ * If the LSB of @x is set, the result is 0.
+ * If only the MSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_TRAILING_ZEROS_0.
+ */
+static inline int count_trailing_zeros(unsigned long x)
+{
+#define COUNT_TRAILING_ZEROS_0 (-1)
+
+	if (sizeof(x) == 4)
+		return ffs(x);
+	else
+		return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0;
+}
+
+#endif /* _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ */
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
index 29f9862..678ce4f 100644
--- a/lib/mpi/longlong.h
+++ b/lib/mpi/longlong.h
@@ -19,6 +19,8 @@
  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA. */
 
+#include <asm-generic/bitops/count_zeros.h>
+
 /* You have to define the following before including this file:
  *
  * UWtype -- An unsigned type, default type for operations (typically a "word")
@@ -146,12 +148,6 @@ do { \
 	: "1" ((USItype)(n1)), \
 		"r" ((USItype)(n0)), \
 		"r" ((USItype)(d)))
-
-#define count_leading_zeros(count, x) \
-	__asm__ ("clz %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #endif /* __a29k__ */
 
 #if defined(__alpha) && W_TYPE_SIZE == 64
@@ -298,11 +294,6 @@ extern UDItype __udiv_qrnnd();
 	: "1" ((USItype)(nh)), \
 		"0" ((USItype)(nl)), \
 		"g" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bsch/1 %1,%0" \
-	: "=g" (count) \
-	: "g" ((USItype)(x)), \
-	     "0" ((USItype)0))
 #endif
 
 /***************************************
@@ -354,27 +345,6 @@ do { USItype __r; \
 } while (0)
 extern USItype __udiv_qrnnd();
 #endif /* LONGLONG_STANDALONE */
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __tmp; \
-	__asm__ ( \
-	"ldi             1,%0\n" \
-	"extru,=	%1,15,16,%%r0  ; Bits 31..16 zero?\n" \
-	"extru,tr	%1,15,16,%1    ; No.  Shift down, skip add.\n" \
-	"ldo		16(%0),%0      ; Yes.	Perform add.\n" \
-	"extru,=	%1,23,8,%%r0   ; Bits 15..8 zero?\n" \
-	"extru,tr	%1,23,8,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		8(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,27,4,%%r0   ; Bits 7..4 zero?\n" \
-	"extru,tr	%1,27,4,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		4(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,29,2,%%r0   ; Bits 3..2 zero?\n" \
-	"extru,tr	%1,29,2,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		2(%0),%0       ; Yes.	Perform add.\n" \
-	"extru		%1,30,1,%1     ; Extract bit 1.\n" \
-	"sub		%0,%1,%0       ; Subtract it.              " \
-	: "=r" (count), "=r" (__tmp) : "1" (x)); \
-} while (0)
 #endif /* hppa */
 
 /***************************************
@@ -457,15 +427,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "rm" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("bsrl %1,%0" \
-	: "=r" (__cbtmp) : "rm" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define count_trailing_zeros(count, x) \
-	__asm__ ("bsfl %1,%0" : "=r" (count) : "rm" ((USItype)(x)))
 #ifndef UMUL_TIME
 #define UMUL_TIME 40
 #endif
@@ -536,15 +497,6 @@ do { \
 	     "dI" ((USItype)(d))); \
 	(r) = __rq.__i.__l; (q) = __rq.__i.__h; \
 } while (0)
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("scanbit %1,%0" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 (-32)	/* sic */
 #if defined(__i960mx)		/* what is the proper symbol to test??? */
 #define rshift_rhlc(r, h, l, c) \
 do { \
@@ -603,11 +555,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "dmi" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bfffo %1{%b2:%b2},%0" \
-	: "=d" ((USItype)(count)) \
-	: "od" ((USItype)(x)), "n" (0))
-#define COUNT_LEADING_ZEROS_0 32
 #else /* not mc68020 */
 #define umul_ppmm(xh, xl, a, b) \
 do { USItype __umul_tmp1, __umul_tmp2; \
@@ -664,15 +611,6 @@ do { USItype __umul_tmp1, __umul_tmp2; \
 	     "rJ" ((USItype)(bh)), \
 	     "rJ" ((USItype)(al)), \
 	     "rJ" ((USItype)(bl)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("ff1 %0,%1" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 63	/* sic */
 #if defined(__m88110__)
 #define umul_ppmm(wh, wl, u, v) \
 do { \
@@ -779,12 +717,6 @@ do { \
 	: "0" (__xx.__ll), \
 	     "g" ((USItype)(d))); \
 	(r) = __xx.__i.__l; (q) = __xx.__i.__h; })
-#define count_trailing_zeros(count, x) \
-do { \
-	__asm__("ffsd      %2,%0" \
-	: "=r"((USItype) (count)) \
-	: "0"((USItype) 0), "r"((USItype) (x))); \
-	} while (0)
 #endif /* __ns32000__ */
 
 /***************************************
@@ -855,11 +787,6 @@ do { \
 		"rI" ((USItype)(al)), \
 		"r" ((USItype)(bl))); \
 } while (0)
-#define count_leading_zeros(count, x) \
-	__asm__ ("{cntlz|cntlzw} %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #if defined(_ARCH_PPC)
 #define umul_ppmm(ph, pl, m0, m1) \
 do { \
@@ -1001,19 +928,6 @@ do { \
 } while (0)
 #define UMUL_TIME 20
 #define UDIV_TIME 200
-#define count_leading_zeros(count, x) \
-do { \
-	if ((x) >= 0x10000) \
-		__asm__ ("clz     %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x) >> 16)); \
-	else { \
-		__asm__ ("clz   %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x))); \
-		(count) += 16; \
-	} \
-} while (0)
 #endif /* RT/ROMP */
 
 /***************************************
@@ -1142,13 +1056,6 @@ do { \
 	"rI" ((USItype)(d)) \
 	: "%g1" __AND_CLOBBER_CC)
 #define UDIV_TIME 37
-#define count_leading_zeros(count, x) \
-	__asm__ ("scan %1,0,%0" \
-	: "=r" ((USItype)(x)) \
-	: "r" ((USItype)(count)))
-/* Early sparclites return 63 for an argument of 0, but they warn that future
-	implementations might change this.  Therefore, leave COUNT_LEADING_ZEROS_0
-	undefined.  */
 #endif /* __sparclite__ */
 #endif /* __sparc_v8__ */
 	/* Default to sparc v7 versions of umul_ppmm and udiv_qrnnd.  */
@@ -1454,47 +1361,6 @@ do { \
 #define udiv_qrnnd __udiv_qrnnd_c
 #endif
 
-#undef count_leading_zeros
-#if !defined(count_leading_zeros)
-	extern
-#ifdef __STDC__
-			const
-#endif
-			unsigned char __clz_tab[];
-#define count_leading_zeros(count, x) \
-do { \
-	UWtype __xr = (x); \
-	UWtype __a; \
-	\
-	if (W_TYPE_SIZE <= 32) { \
-		__a = __xr < ((UWtype) 1 << 2*__BITS4) \
-		? (__xr < ((UWtype) 1 << __BITS4) ? 0 : __BITS4) \
-		: (__xr < ((UWtype) 1 << 3*__BITS4) ?  2*__BITS4 : 3*__BITS4); \
-	} \
-	else { \
-		for (__a = W_TYPE_SIZE - 8; __a > 0; __a -= 8) \
-			if (((__xr >> __a) & 0xff) != 0) \
-				break; \
-	} \
-	\
-	(count) = W_TYPE_SIZE - (__clz_tab[__xr >> __a] + __a); \
-} while (0)
-	/* This version gives a well-defined value for zero. */
-#define COUNT_LEADING_ZEROS_0 W_TYPE_SIZE
-#endif
-
-#if !defined(count_trailing_zeros)
-/* Define count_trailing_zeros using count_leading_zeros.  The latter might be
-	defined in asm, but if it is not, the C version above is good enough.  */
-#define count_trailing_zeros(count, x) \
-do { \
-	UWtype __ctz_x = (x); \
-	UWtype __ctz_c; \
-	count_leading_zeros(__ctz_c, __ctz_x & -__ctz_x); \
-	(count) = W_TYPE_SIZE - 1 - __ctz_c; \
-} while (0)
-#endif
-
 #ifndef UDIV_NEEDS_NORMALIZATION
 #define UDIV_NEEDS_NORMALIZATION 0
 #endif
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
index 0c50536..3fc00bf 100644
--- a/lib/mpi/mpi-bit.c
+++ b/lib/mpi/mpi-bit.c
@@ -45,7 +45,7 @@ unsigned mpi_get_nbits(MPI a)
 	if (a->nlimbs) {
 		mpi_limb_t alimb = a->d[a->nlimbs - 1];
 		if (alimb)
-			count_leading_zeros(n, alimb);
+			n = count_leading_zeros(alimb);
 		else
 			n = BITS_PER_MPI_LIMB;
 		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
diff --git a/lib/mpi/mpi-div.c b/lib/mpi/mpi-div.c
index f68cbbb..51f105c 100644
--- a/lib/mpi/mpi-div.c
+++ b/lib/mpi/mpi-div.c
@@ -217,7 +217,7 @@ int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den)
 	} else			/* Put quotient at top of remainder. */
 		qp = rp + dsize;
 
-	count_leading_zeros(normalization_steps, dp[dsize - 1]);
+	normalization_steps = count_leading_zeros(dp[dsize - 1]);
 
 	/* Normalize the denominator, i.e. make its most significant bit set by
 	 * shifting it NORMALIZATION_STEPS bits to the left.  Also shift the
diff --git a/lib/mpi/mpi-pow.c b/lib/mpi/mpi-pow.c
index 67f3e79..5464c87 100644
--- a/lib/mpi/mpi-pow.c
+++ b/lib/mpi/mpi-pow.c
@@ -77,7 +77,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 	mp = mp_marker = mpi_alloc_limb_space(msize);
 	if (!mp)
 		goto enomem;
-	count_leading_zeros(mod_shift_cnt, mod->d[msize - 1]);
+	mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
 	if (mod_shift_cnt)
 		mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
 	else
@@ -169,7 +169,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 
 		i = esize - 1;
 		e = ep[i];
-		count_leading_zeros(c, e);
+		c = count_leading_zeros(e);
 		e = (e << c) << 1;	/* shift the exp bits to the left, lose msb */
 		c = BITS_PER_MPI_LIMB - 1 - c;
 
diff --git a/lib/mpi/mpi-scan.c b/lib/mpi/mpi-scan.c
index b2da5ad..58556b5 100644
--- a/lib/mpi/mpi-scan.c
+++ b/lib/mpi/mpi-scan.c
@@ -125,7 +125,7 @@ unsigned mpi_trailing_zeros(const MPI a)
 			unsigned nn;
 			mpi_limb_t alimb = a->d[n];
 
-			count_trailing_zeros(nn, alimb);
+			nn = count_trailing_zeros(alimb);
 			count += nn;
 			break;
 		}
diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c
index cde1aae..d6483792 100644
--- a/lib/mpi/mpih-div.c
+++ b/lib/mpi/mpih-div.c
@@ -65,7 +65,7 @@ mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
 	    && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
 		int normalization_steps;
 
-		count_leading_zeros(normalization_steps, divisor_limb);
+		normalization_steps = count_leading_zeros(divisor_limb);
 		if (normalization_steps) {
 			mpi_limb_t divisor_limb_inverted;
 
@@ -142,7 +142,7 @@ mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
 		if (UDIV_NEEDS_NORMALIZATION) {
 			int normalization_steps;
 
-			count_leading_zeros(normalization_steps, divisor_limb);
+			normalization_steps = count_leading_zeros(divisor_limb);
 			if (normalization_steps) {
 				divisor_limb <<= normalization_steps;
 
@@ -421,7 +421,7 @@ mpihelp_divmod_1(mpi_ptr_t quot_ptr,
 	    && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
 		int normalization_steps;
 
-		count_leading_zeros(normalization_steps, divisor_limb);
+		normalization_steps = count_leading_zeros(divisor_limb);
 		if (normalization_steps) {
 			mpi_limb_t divisor_limb_inverted;
 
@@ -496,7 +496,7 @@ mpihelp_divmod_1(mpi_ptr_t quot_ptr,
 		if (UDIV_NEEDS_NORMALIZATION) {
 			int normalization_steps;
 
-			count_leading_zeros(normalization_steps, divisor_limb);
+			normalization_steps = count_leading_zeros(divisor_limb);
 			if (normalization_steps) {
 				divisor_limb <<= normalization_steps;
 

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[James Morris]

On Fri, 6 Jul 2012, David Howells wrote:

> Provide count_leading/trailing_zeros() macros based on extant arch bit scanning
> functions rather than reimplementing from scratch in MPILIB.
> 
> Whilst we're at it, turn count_foo_zeros(n, x) into n = count_foo_zeros(x).
> 
> Also move the definition to asm-generic as other people may be interested in
> using it.

Please rebase this against
git://git.kernel.org/pub/scm/linux/kernel/git/jmorris/linux-security.git next


-- 
James Morris
<jmorris@namei.org>

[PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[David Howells]

Provide count_leading/trailing_zeros() macros based on extant arch bit scanning
functions rather than reimplementing from scratch in MPILIB.

Whilst we're at it, turn count_foo_zeros(n, x) into n = count_foo_zeros(x).

Also move the definition to asm-generic as other people may be interested in
using it.

Signed-off-by: David Howells <dhowells@redhat.com>
Cc: David S. Miller <davem@davemloft.net>
Cc: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
Cc: Arnd Bergmann <arnd@arndb.de>
---

 include/asm-generic/bitops/count_zeros.h |   57 ++++++++++++
 lib/mpi/longlong.h                       |  142 +-----------------------------
 lib/mpi/mpi-bit.c                        |    2 
 lib/mpi/mpi-pow.c                        |    4 -
 4 files changed, 64 insertions(+), 141 deletions(-)
 create mode 100644 include/asm-generic/bitops/count_zeros.h

diff --git a/include/asm-generic/bitops/count_zeros.h b/include/asm-generic/bitops/count_zeros.h
new file mode 100644
index 0000000..7f8e1d0
--- /dev/null
+++ b/include/asm-generic/bitops/count_zeros.h
@@ -0,0 +1,57 @@
+/* Count leading and trailing zeros functions
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+#define _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+
+#include <linux/bitops.h>
+
+/**
+ * count_leading_zeros - Count the number of zeros from the MSB back
+ * @x: The value
+ *
+ * Count the number of leading zeros from the MSB going towards the LSB in @x.
+ *
+ * If the MSB of @x is set, the result is 0.
+ * If only the LSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_LEADING_ZEROS_0.
+ */
+static inline int count_leading_zeros(unsigned long x)
+{
+	if (sizeof(x) == 4)
+		return BITS_PER_LONG - fls(x);
+	else
+		return BITS_PER_LONG - fls64(x);
+}
+
+#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG
+
+/**
+ * count_trailing_zeros - Count the number of zeros from the LSB forwards
+ * @x: The value
+ *
+ * Count the number of trailing zeros from the LSB going towards the MSB in @x.
+ *
+ * If the LSB of @x is set, the result is 0.
+ * If only the MSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_TRAILING_ZEROS_0.
+ */
+static inline int count_trailing_zeros(unsigned long x)
+{
+#define COUNT_TRAILING_ZEROS_0 (-1)
+
+	if (sizeof(x) == 4)
+		return ffs(x);
+	else
+		return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0;
+}
+
+#endif /* _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ */
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
index 29f9862..18b528f 100644
--- a/lib/mpi/longlong.h
+++ b/lib/mpi/longlong.h
@@ -19,6 +19,8 @@
  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA. */
 
+#include <asm-generic/bitops/count_zeros.h>
+
 /* You have to define the following before including this file:
  *
  * UWtype -- An unsigned type, default type for operations (typically a "word")
@@ -64,12 +66,12 @@
  * denominator).  Like udiv_qrnnd but the numbers are signed.  The quotient
  * is rounded towards 0.
  *
- * 5) count_leading_zeros(count, x) counts the number of zero-bits from the
+ * 5) count = count_leading_zeros(x) counts the number of zero-bits from the
  * msb to the first non-zero bit in the UWtype X.  This is the number of
  * steps X needs to be shifted left to set the msb.  Undefined for X == 0,
  * unless the symbol COUNT_LEADING_ZEROS_0 is defined to some value.
  *
- * 6) count_trailing_zeros(count, x) like count_leading_zeros, but counts
+ * 6) count = count_trailing_zeros(x) like count_leading_zeros, but counts
  * from the least significant end.
  *
  * 7) add_ssaaaa(high_sum, low_sum, high_addend_1, low_addend_1,
@@ -146,12 +148,6 @@ do { \
 	: "1" ((USItype)(n1)), \
 		"r" ((USItype)(n0)), \
 		"r" ((USItype)(d)))
-
-#define count_leading_zeros(count, x) \
-	__asm__ ("clz %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #endif /* __a29k__ */
 
 #if defined(__alpha) && W_TYPE_SIZE == 64
@@ -298,11 +294,6 @@ extern UDItype __udiv_qrnnd();
 	: "1" ((USItype)(nh)), \
 		"0" ((USItype)(nl)), \
 		"g" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bsch/1 %1,%0" \
-	: "=g" (count) \
-	: "g" ((USItype)(x)), \
-	     "0" ((USItype)0))
 #endif
 
 /***************************************
@@ -354,27 +345,6 @@ do { USItype __r; \
 } while (0)
 extern USItype __udiv_qrnnd();
 #endif /* LONGLONG_STANDALONE */
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __tmp; \
-	__asm__ ( \
-	"ldi             1,%0\n" \
-	"extru,=	%1,15,16,%%r0  ; Bits 31..16 zero?\n" \
-	"extru,tr	%1,15,16,%1    ; No.  Shift down, skip add.\n" \
-	"ldo		16(%0),%0      ; Yes.	Perform add.\n" \
-	"extru,=	%1,23,8,%%r0   ; Bits 15..8 zero?\n" \
-	"extru,tr	%1,23,8,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		8(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,27,4,%%r0   ; Bits 7..4 zero?\n" \
-	"extru,tr	%1,27,4,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		4(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,29,2,%%r0   ; Bits 3..2 zero?\n" \
-	"extru,tr	%1,29,2,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		2(%0),%0       ; Yes.	Perform add.\n" \
-	"extru		%1,30,1,%1     ; Extract bit 1.\n" \
-	"sub		%0,%1,%0       ; Subtract it.              " \
-	: "=r" (count), "=r" (__tmp) : "1" (x)); \
-} while (0)
 #endif /* hppa */
 
 /***************************************
@@ -457,15 +427,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "rm" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("bsrl %1,%0" \
-	: "=r" (__cbtmp) : "rm" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define count_trailing_zeros(count, x) \
-	__asm__ ("bsfl %1,%0" : "=r" (count) : "rm" ((USItype)(x)))
 #ifndef UMUL_TIME
 #define UMUL_TIME 40
 #endif
@@ -536,15 +497,6 @@ do { \
 	     "dI" ((USItype)(d))); \
 	(r) = __rq.__i.__l; (q) = __rq.__i.__h; \
 } while (0)
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("scanbit %1,%0" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 (-32)	/* sic */
 #if defined(__i960mx)		/* what is the proper symbol to test??? */
 #define rshift_rhlc(r, h, l, c) \
 do { \
@@ -603,11 +555,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "dmi" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bfffo %1{%b2:%b2},%0" \
-	: "=d" ((USItype)(count)) \
-	: "od" ((USItype)(x)), "n" (0))
-#define COUNT_LEADING_ZEROS_0 32
 #else /* not mc68020 */
 #define umul_ppmm(xh, xl, a, b) \
 do { USItype __umul_tmp1, __umul_tmp2; \
@@ -664,15 +611,6 @@ do { USItype __umul_tmp1, __umul_tmp2; \
 	     "rJ" ((USItype)(bh)), \
 	     "rJ" ((USItype)(al)), \
 	     "rJ" ((USItype)(bl)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("ff1 %0,%1" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 63	/* sic */
 #if defined(__m88110__)
 #define umul_ppmm(wh, wl, u, v) \
 do { \
@@ -779,12 +717,6 @@ do { \
 	: "0" (__xx.__ll), \
 	     "g" ((USItype)(d))); \
 	(r) = __xx.__i.__l; (q) = __xx.__i.__h; })
-#define count_trailing_zeros(count, x) \
-do { \
-	__asm__("ffsd      %2,%0" \
-	: "=r"((USItype) (count)) \
-	: "0"((USItype) 0), "r"((USItype) (x))); \
-	} while (0)
 #endif /* __ns32000__ */
 
 /***************************************
@@ -855,11 +787,6 @@ do { \
 		"rI" ((USItype)(al)), \
 		"r" ((USItype)(bl))); \
 } while (0)
-#define count_leading_zeros(count, x) \
-	__asm__ ("{cntlz|cntlzw} %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #if defined(_ARCH_PPC)
 #define umul_ppmm(ph, pl, m0, m1) \
 do { \
@@ -1001,19 +928,6 @@ do { \
 } while (0)
 #define UMUL_TIME 20
 #define UDIV_TIME 200
-#define count_leading_zeros(count, x) \
-do { \
-	if ((x) >= 0x10000) \
-		__asm__ ("clz     %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x) >> 16)); \
-	else { \
-		__asm__ ("clz   %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x))); \
-		(count) += 16; \
-	} \
-} while (0)
 #endif /* RT/ROMP */
 
 /***************************************
@@ -1142,13 +1056,6 @@ do { \
 	"rI" ((USItype)(d)) \
 	: "%g1" __AND_CLOBBER_CC)
 #define UDIV_TIME 37
-#define count_leading_zeros(count, x) \
-	__asm__ ("scan %1,0,%0" \
-	: "=r" ((USItype)(x)) \
-	: "r" ((USItype)(count)))
-/* Early sparclites return 63 for an argument of 0, but they warn that future
-	implementations might change this.  Therefore, leave COUNT_LEADING_ZEROS_0
-	undefined.  */
 #endif /* __sparclite__ */
 #endif /* __sparc_v8__ */
 	/* Default to sparc v7 versions of umul_ppmm and udiv_qrnnd.  */
@@ -1454,47 +1361,6 @@ do { \
 #define udiv_qrnnd __udiv_qrnnd_c
 #endif
 
-#undef count_leading_zeros
-#if !defined(count_leading_zeros)
-	extern
-#ifdef __STDC__
-			const
-#endif
-			unsigned char __clz_tab[];
-#define count_leading_zeros(count, x) \
-do { \
-	UWtype __xr = (x); \
-	UWtype __a; \
-	\
-	if (W_TYPE_SIZE <= 32) { \
-		__a = __xr < ((UWtype) 1 << 2*__BITS4) \
-		? (__xr < ((UWtype) 1 << __BITS4) ? 0 : __BITS4) \
-		: (__xr < ((UWtype) 1 << 3*__BITS4) ?  2*__BITS4 : 3*__BITS4); \
-	} \
-	else { \
-		for (__a = W_TYPE_SIZE - 8; __a > 0; __a -= 8) \
-			if (((__xr >> __a) & 0xff) != 0) \
-				break; \
-	} \
-	\
-	(count) = W_TYPE_SIZE - (__clz_tab[__xr >> __a] + __a); \
-} while (0)
-	/* This version gives a well-defined value for zero. */
-#define COUNT_LEADING_ZEROS_0 W_TYPE_SIZE
-#endif
-
-#if !defined(count_trailing_zeros)
-/* Define count_trailing_zeros using count_leading_zeros.  The latter might be
-	defined in asm, but if it is not, the C version above is good enough.  */
-#define count_trailing_zeros(count, x) \
-do { \
-	UWtype __ctz_x = (x); \
-	UWtype __ctz_c; \
-	count_leading_zeros(__ctz_c, __ctz_x & -__ctz_x); \
-	(count) = W_TYPE_SIZE - 1 - __ctz_c; \
-} while (0)
-#endif
-
 #ifndef UDIV_NEEDS_NORMALIZATION
 #define UDIV_NEEDS_NORMALIZATION 0
 #endif
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
index 5687248..503537e 100644
--- a/lib/mpi/mpi-bit.c
+++ b/lib/mpi/mpi-bit.c
@@ -45,7 +45,7 @@ unsigned mpi_get_nbits(MPI a)
 	if (a->nlimbs) {
 		mpi_limb_t alimb = a->d[a->nlimbs - 1];
 		if (alimb)
-			count_leading_zeros(n, alimb);
+			n = count_leading_zeros(alimb);
 		else
 			n = BITS_PER_MPI_LIMB;
 		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
diff --git a/lib/mpi/mpi-pow.c b/lib/mpi/mpi-pow.c
index 67f3e79..5464c87 100644
--- a/lib/mpi/mpi-pow.c
+++ b/lib/mpi/mpi-pow.c
@@ -77,7 +77,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 	mp = mp_marker = mpi_alloc_limb_space(msize);
 	if (!mp)
 		goto enomem;
-	count_leading_zeros(mod_shift_cnt, mod->d[msize - 1]);
+	mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
 	if (mod_shift_cnt)
 		mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
 	else
@@ -169,7 +169,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 
 		i = esize - 1;
 		e = ep[i];
-		count_leading_zeros(c, e);
+		c = count_leading_zeros(e);
 		e = (e << c) << 1;	/* shift the exp bits to the left, lose msb */
 		c = BITS_PER_MPI_LIMB - 1 - c;
 

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[Arnd Bergmann]

On Friday 20 July 2012, David Howells wrote:
> Provide count_leading/trailing_zeros() macros based on extant arch bit scanning
> functions rather than reimplementing from scratch in MPILIB.
> 
> Whilst we're at it, turn count_foo_zeros(n, x) into n = count_foo_zeros(x).
> 
> Also move the definition to asm-generic as other people may be interested in
> using it.
> 
> Signed-off-by: David Howells <dhowells@redhat.com>
> Cc: David S. Miller <davem@davemloft.net>
> Cc: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
> Cc: Arnd Bergmann <arnd@arndb.de>

I don't generally like to put stuff into asm-generic when it's unlikely
to be overridden by architectures. It would really belong into
include/linux, but then again we have all the other bitops in asm-generic
as well, so whatever...

Acked-by: Arnd Bergmann <arnd@arndb.de>

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[David Howells]

Arnd Bergmann <arnd@arndb.de> wrote:

> I don't generally like to put stuff into asm-generic when it's unlikely
> to be overridden by architectures. It would really belong into
> include/linux, but then again we have all the other bitops in asm-generic
> as well, so whatever...

Some arches (such as Sparc, I think) have count-leading-zero instructions.

David

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[Arnd Bergmann]

On Friday 20 July 2012, David Howells wrote:
> 
> Arnd Bergmann <arnd@arndb.de> wrote:
> 
> > I don't generally like to put stuff into asm-generic when it's unlikely
> > to be overridden by architectures. It would really belong into
> > include/linux, but then again we have all the other bitops in asm-generic
> > as well, so whatever...
> 
> Some arches (such as Sparc, I think) have count-leading-zero instructions.

But I guess they would still use the same definition of

+static inline int count_leading_zeros(unsigned long x)
+{
+       if (sizeof(x) == 4)
+               return BITS_PER_LONG - fls(x);
+       else
+               return BITS_PER_LONG - fls64(x);
+}

and just provide their own fls().

	Arnd

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[David Miller]

From: David Howells <dhowells@redhat.com>
Date: Fri, 20 Jul 2012 15:21:39 +0100

> Arnd Bergmann <arnd@arndb.de> wrote:
> 
>> I don't generally like to put stuff into asm-generic when it's unlikely
>> to be overridden by architectures. It would really belong into
>> include/linux, but then again we have all the other bitops in asm-generic
>> as well, so whatever...
> 
> Some arches (such as Sparc, I think) have count-leading-zero instructions.

Yes, newer sparc64 chips have leading-zero-detect, and I was pretty
sure that powerpc had something similar.  It's called count-leading-
zeros or something like that.

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[Jan Engelhardt]

On Saturday 2012-07-21 02:46, David Miller wrote:
>> Arnd Bergmann <arnd@arndb.de> wrote:
>> 
>>> I don't generally like to put stuff into asm-generic when it's unlikely
>>> to be overridden by architectures. It would really belong into
>>> include/linux, but then again we have all the other bitops in asm-generic
>>> as well, so whatever...
>> 
>> Some arches (such as Sparc, I think) have count-leading-zero instructions.
>
>Yes, newer sparc64 chips have leading-zero-detect, and I was pretty
>sure that powerpc had something similar.  It's called count-leading-
>zeros or something like that.

And gcc has a __builtin_clz.

Re: [PATCH] MPILIB: Provide count_leading/trailing_zeros() based on arch functions

[David Miller]

From: Jan Engelhardt <jengelh@inai.de>
Date: Fri, 10 Aug 2012 14:51:49 +0200 (CEST)

> 
> On Saturday 2012-07-21 02:46, David Miller wrote:
>>> Arnd Bergmann <arnd@arndb.de> wrote:
>>> 
>>>> I don't generally like to put stuff into asm-generic when it's unlikely
>>>> to be overridden by architectures. It would really belong into
>>>> include/linux, but then again we have all the other bitops in asm-generic
>>>> as well, so whatever...
>>> 
>>> Some arches (such as Sparc, I think) have count-leading-zero instructions.
>>
>>Yes, newer sparc64 chips have leading-zero-detect, and I was pretty
>>sure that powerpc had something similar.  It's called count-leading-
>>zeros or something like that.
> 
> And gcc has a __builtin_clz.

Which I can't use.  I have to patch the code at run time based upon
whether the cpu has the 'lzd' instruction or not.