diff options
author | Werner Koch <wk@gnupg.org> | 2015-01-15 10:04:43 +0100 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2015-01-15 10:37:53 +0100 |
commit | 9d2a22c94ae99f9301321082c4fb8d73f4085fda (patch) | |
tree | bd06e3f0b580cf0676e4eca798620414f61e1240 /cipher/bithelp.h | |
parent | 27a91a93d101ef080f71e5d7e50c3cbf3dbb2e39 (diff) | |
download | libgcrypt-9d2a22c94ae99f9301321082c4fb8d73f4085fda.tar.gz |
Add functions to count trailing zero bits in a word.
* cipher/bithelp.h (_gcry_ctz, _gcry_ctz64): New.
* configure.ac (HAVE_BUILTIN_CTZ): Add new test.
--
Note that these functions return the number of bits in the word when
passing 0.
Signed-off-by: Werner Koch <wk@gnupg.org>
Diffstat (limited to 'cipher/bithelp.h')
-rw-r--r-- | cipher/bithelp.h | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/cipher/bithelp.h b/cipher/bithelp.h index 6e59c53f..2220bc87 100644 --- a/cipher/bithelp.h +++ b/cipher/bithelp.h @@ -77,4 +77,49 @@ _gcry_bswap64(u64 x) # endif #endif + +/* Count trailing zero bits in an unsigend int. We return an int + because that is what gcc's builtin does. Returns the number of + bits in X if X is 0. */ +static inline int +_gcry_ctz (unsigned int x) +{ +#if defined (HAVE_BUILTIN_CTZ) + return x? __builtin_ctz (x) : 8 * sizeof (x); +#else + /* See + * http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup + */ + static const unsigned char mod37[] = + { + sizeof (unsigned int)*8, + 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, + 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, + 5, 20, 8, 19, 18 + }; + return (int)mod37[(-x & x) % 37]; +#endif +} + + +/* Count trailing zero bits in an u64. We return an int because that + is what gcc's builtin does. Returns the number of bits in X if X + is 0. */ +#ifdef HAVE_U64_TYPEDEF +static inline int +_gcry_ctz64(u64 x) +{ +#if defined (HAVE_BUILTIN_CTZ) && SIZEOF_UNSIGNED_INT >= 8 +#warning hello + return x? __builtin_ctz (x) : 8 * sizeof (x); +#else + if ((x & 0xffffffff)) + return _gcry_ctz (x); + else + return 32 + _gcry_ctz (x >> 32); +#endif +} +#endif /*HAVE_U64_TYPEDEF*/ + + #endif /*G10_BITHELP_H*/ |