diff options
-rw-r--r-- | lib/util/wordintclz.h | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/lib/util/wordintclz.h b/lib/util/wordintclz.h new file mode 100644 index 00000000..32e6ade8 --- /dev/null +++ b/lib/util/wordintclz.h @@ -0,0 +1,93 @@ +#ifndef WORDINTCLZ_H_INCLUDED +#define WORDINTCLZ_H_INCLUDED + +#if (!defined(WORDACCESS_GENERIC) && HAVE_GCC_BITCOUNT ) +/* + Compiler is GCC and has __builtin_clz() + wordint is long + + __builtin_clz is available on GCC 3.4 and above + + Note that the clz scheme does not work and requires adjustment + if long type does not make use of all bits for data storage. + + This is unlikely. According to GNU MP (http://www.swox.com/gmp/), + in rare cases such as Cray, there are smaller data types that take up + the same space as long, but leave the higher bits silent. + Currently, there are no known such cases for data type long. + */ + +static __inline__ unsigned int +wordintClz(wordint const x){ + + assert(sizeof(unsigned long int) == sizeof(wordint)); + + if (x == 0) + return sizeof(wordint) * 8; + else + return (__builtin_clzl( (unsigned long int) x )); +} + +#else + +/* wordint is uint32_t: exactly 32 bits wide */ + +static unsigned char const clz8[256]= { + 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + + + +static __inline__ unsigned int +clz16(wordint const x) { + + if (x >> 8 != 0) + return clz8[x >> 8]; + else + return clz8[x] + 8; +} + + + +static __inline__ unsigned int +clz32(wordint const x) { + + if (x >> 16 != 0) + return clz16(x >> 16); + else + return clz16(x) + 16; +} + + + +static __inline__ unsigned int +wordintClz(wordint const x) { + + assert(sizeof(wordint) == 4); + + return clz32(x); +} + +/* Another way to calculate leading zeros: + x == 0 ? 32 : 31 - floor(log(x)/log(2)) + (Beware: insufficient precision will cause errors) +*/ + +#endif + +#endif |