diff options
| author | Kevin Ryde <user42@zip.com.au> | 2001-09-08 01:03:57 +0200 |
|---|---|---|
| committer | Kevin Ryde <user42@zip.com.au> | 2001-09-08 01:03:57 +0200 |
| commit | 34e823937001e141447754df88759d94092b25f9 (patch) | |
| tree | d53a10d4e93ab8134516986ccd2defb3d12c7cf1 /gmp-impl.h | |
| parent | 2b9784cb7ed8b32e0b40deaf924ef22aa272ded1 (diff) | |
| download | gmp-34e823937001e141447754df88759d94092b25f9.tar.gz | |
* gmp-impl.h (popc_limb): New macro, adapted from mpn/generic/popham.c.
For 64-bits reuse 0x33...33 constant.
Diffstat (limited to 'gmp-impl.h')
| -rw-r--r-- | gmp-impl.h | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/gmp-impl.h b/gmp-impl.h index d0751c4e2..0e4a1f5b8 100644 --- a/gmp-impl.h +++ b/gmp-impl.h @@ -1703,6 +1703,84 @@ extern const unsigned char modlimb_invert_table[128]; #endif +/* No processor claiming to be SPARC v9 compliant seems to + implement the POPC instruction. Disable pattern for now. */ +#if 0 +#if defined __GNUC__ && defined __sparc_v9__ && BITS_PER_MP_LIMB == 64 +#define popc_limb(result, input) \ + do { \ + DItype __res; \ + asm ("popc %1,%0" : "=r" (result) : "rI" (input)); \ + } while (0) +#endif +#endif + +/* Cool population count of an mp_limb_t. + You have to figure out how this works, I won't tell you! + + The constants could also be expressed as: + 0xAA... = [2^(N+1) / 3] = [(2^N-1)/3*2] + 0x33... = [2^N / 5] = [(2^N-1)/5] + 0x0f... = [2^N / 17] = [(2^N-1)/17] + (N is BITS_PER_MP_LIMB, [] denotes truncation.) */ + +#if ! defined (popc_limb) && BITS_PER_MP_LIMB == 64 +#define popc_limb(result, input) \ + do { \ + mp_limb_t __x = (input); \ + __x -= (__x & CNST_LIMB(0xaaaaaaaaaaaaaaaa)) >> 1; \ + __x = ((__x >> 2) & CNST_LIMB(0x3333333333333333)) \ + + (__x & CNST_LIMB(0x3333333333333333)); \ + __x = ((__x >> 4) + __x) & CNST_LIMB(0x0f0f0f0f0f0f0f0f); \ + __x = ((__x >> 8) + __x); \ + __x = ((__x >> 16) + __x); \ + __x = ((__x >> 32) + __x) & 0xff; \ + (result) = __x; \ + } while (0) +#endif +#if ! defined (popc_limb) && BITS_PER_MP_LIMB == 32 +#define popc_limb(result, input) \ + do { \ + mp_limb_t __x = (input); \ + __x -= (__x & 0xaaaaaaaaL) >> 1; \ + __x = ((__x >> 2) & 0x33333333L) + (__x & 0x33333333L); \ + __x = ((__x >> 4) + __x) & 0x0f0f0f0fL; \ + __x = ((__x >> 8) + __x); \ + __x = ((__x >> 16) + __x) & 0xff; \ + (result) = __x; \ + } while (0) +#endif +#if ! defined (popc_limb) && BITS_PER_MP_LIMB == 16 +#define popc_limb(result, input) \ + do { \ + mp_limb_t __x = (input); \ + __x -= (__x & 0xaaaa) >> 1; \ + __x = ((__x >> 2) & 0x3333) + (__x & 0x3333); \ + __x = ((__x >> 4) + __x) & 0x0f0f; \ + __x = ((__x >> 8) + __x) & 0xff; \ + (result) = __x; \ + } while (0) +#endif +#if ! defined (popc_limb) && BITS_PER_MP_LIMB == 8 +#define popc_limb(result, input) \ + do { \ + mp_limb_t __x = (input); \ + __x -= (__x & 0xaa) >> 1; \ + __x = ((__x >> 2) & 0x33) + (__x & 0x33); \ + __x = ((__x >> 4) + __x) & 0xf; \ + (result) = __x; \ + } while (0) +#endif +#if ! defined (popc_limb) && BITS_PER_MP_LIMB == 4 +#define popc_limb(result, input) \ + do { \ + mp_limb_t __x = (input); \ + __x = (__x & 1) + ((__x >> 1) & 1) + ((__x >> 2) & 1) + ((__x >> 3) & 1); \ + (result) = __x; \ + } while (0) +#endif + + /* Define stuff for longlong.h. */ #if HAVE_ATTRIBUTE_MODE typedef unsigned int UQItype __attribute__ ((mode (QI))); |