From: "Kasatkin, Dmitry" <dmitry.kasatkin@intel.com>
To: David Howells <dhowells@redhat.com>, James Morris <jmorris@namei.org>
Cc: rusty@rustcorp.com.au, zohar@linux.vnet.ibm.com,
keyrings@linux-nfs.org, linux-security-module@vger.kernel.org,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH 02/25] MPILIB: Provide count_leading/trailing_zeros() based on arch functions
Date: Mon, 10 Sep 2012 10:13:02 +0300 [thread overview]
Message-ID: <CALLzPKbsp0EnZMTmfWtjfctsZn+YAurA_5W=hqzy1kHuxiCGng@mail.gmail.com> (raw)
In-Reply-To: <20120816013434.872.8115.stgit@warthog.procyon.org.uk>
On Thu, Aug 16, 2012 at 4:34 AM, David Howells <dhowells@redhat.com> 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.com>
Hi James,
Can you please apply this?
Acked-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
> ---
>
> include/asm-generic/bitops/count_zeros.h | 57 ++++++++++++
> lib/mpi/longlong.h | 138 ------------------------------
> lib/mpi/mpi-bit.c | 2
> lib/mpi/mpi-pow.c | 4 -
> 4 files changed, 62 insertions(+), 139 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 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;
>
>
next prev parent reply other threads:[~2012-09-10 7:13 UTC|newest]
Thread overview: 48+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-08-16 1:34 [PATCH 00/25] Crypto keys and module signing David Howells
2012-08-16 1:34 ` [PATCH 01/25] KEYS: Add payload preparsing opportunity prior to key instantiate or update David Howells
2012-08-16 1:34 ` [PATCH 02/25] MPILIB: Provide count_leading/trailing_zeros() based on arch functions David Howells
2012-09-10 7:13 ` Kasatkin, Dmitry [this message]
2012-09-13 5:14 ` James Morris
2012-09-13 14:09 ` Kasatkin, Dmitry
2012-08-16 1:34 ` [PATCH 03/25] KEYS: Create a key type that can be used for general cryptographic operations David Howells
2012-08-16 1:34 ` [PATCH 04/25] KEYS: Add signature verification facility David Howells
2012-08-16 1:35 ` [PATCH 05/25] KEYS: Asymmetric public-key algorithm crypto key subtype David Howells
2012-08-16 1:35 ` [PATCH 06/25] MPILIB: Reinstate mpi_cmp[_ui]() and export for RSA signature verification David Howells
2012-08-16 1:35 ` [PATCH 07/25] KEYS: RSA: Implement signature verification algorithm [PKCS#1 / RFC3447] David Howells
2012-08-16 1:35 ` [PATCH 08/25] KEYS: RSA: Fix signature verification for shorter signatures David Howells
2012-08-16 1:35 ` [PATCH 09/25] PGPLIB: PGP definitions (RFC 4880) David Howells
2012-08-16 1:36 ` [PATCH 10/25] PGPLIB: Basic packet parser David Howells
2012-08-16 1:36 ` [PATCH 11/25] PGPLIB: Signature parser David Howells
2012-08-16 1:36 ` [PATCH 12/25] KEYS: PGP data parser David Howells
2012-08-16 1:36 ` [PATCH 13/25] KEYS: PGP-based public key signature verification David Howells
2012-08-16 1:36 ` [PATCH 14/25] KEYS: PGP format signature parser David Howells
2012-08-16 1:36 ` [PATCH 15/25] KEYS: Provide PGP key description autogeneration David Howells
2012-08-16 1:37 ` [PATCH 16/25] KEYS: Provide a function to load keys from a PGP keyring blob David Howells
2012-08-16 1:37 ` [PATCH 17/25] MODSIGN: Provide gitignore and make clean rules for extra files David Howells
2012-08-16 1:37 ` [PATCH 18/25] MODSIGN: Provide Documentation and Kconfig options David Howells
2012-08-16 1:37 ` [PATCH 19/25] MODSIGN: Sign modules during the build process David Howells
2012-08-16 1:37 ` [PATCH 20/25] MODSIGN: Provide module signing public keys to the kernel David Howells
2012-08-31 14:33 ` Michal Marek
2012-08-16 1:38 ` [PATCH 21/25] MODSIGN: Module signature verification David Howells
2012-08-16 1:38 ` [PATCH 22/25] MODSIGN: Automatically generate module signing keys if missing David Howells
2012-08-16 1:38 ` [PATCH 23/25] MODSIGN: Panic the kernel if FIPS is enabled upon module signing failure David Howells
2012-08-16 1:38 ` [PATCH 24/25] MODSIGN: Allow modules to be signed with an unknown key unless enforcing David Howells
2012-08-16 1:38 ` [PATCH 25/25] MODSIGN: Fix documentation of signed-nokey behavior when not enforcing David Howells
2012-08-21 5:04 ` [PATCH 00/25] Crypto keys and module signing Rusty Russell
2012-08-22 10:50 ` David Howells
2012-08-22 11:52 ` Mimi Zohar
2012-08-22 16:07 ` Kasatkin, Dmitry
2012-09-04 5:55 ` [RFC] module: signature infrastructure Rusty Russell
2012-09-04 12:07 ` Kasatkin, Dmitry
2012-09-04 12:21 ` Kasatkin, Dmitry
2012-09-04 13:40 ` Mimi Zohar
2012-09-05 0:29 ` Rusty Russell
2012-09-05 13:34 ` Mimi Zohar
2012-09-06 2:05 ` Rusty Russell
2012-09-04 14:25 ` Lucas De Marchi
2012-09-04 15:04 ` Kasatkin, Dmitry
2012-09-05 0:19 ` Rusty Russell
2012-09-05 23:41 ` Lucas De Marchi
2012-09-06 7:55 ` Rusty Russell
2012-09-04 22:51 ` David Howells
2012-09-04 23:17 ` Kasatkin, Dmitry
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CALLzPKbsp0EnZMTmfWtjfctsZn+YAurA_5W=hqzy1kHuxiCGng@mail.gmail.com' \
--to=dmitry.kasatkin@intel.com \
--cc=dhowells@redhat.com \
--cc=jmorris@namei.org \
--cc=keyrings@linux-nfs.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-security-module@vger.kernel.org \
--cc=rusty@rustcorp.com.au \
--cc=zohar@linux.vnet.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).