diff options
Diffstat (limited to 'gnulib/lib/integer_length.c')
| m--------- | gnulib | 0 | ||||
| -rw-r--r-- | gnulib/lib/integer_length.c | 141 |
2 files changed, 141 insertions, 0 deletions
diff --git a/gnulib b/gnulib deleted file mode 160000 -Subproject 443bc5ffcf7429e557f4a371b0661abe98ddbc1 diff --git a/gnulib/lib/integer_length.c b/gnulib/lib/integer_length.c new file mode 100644 index 0000000..e5ab665 --- /dev/null +++ b/gnulib/lib/integer_length.c @@ -0,0 +1,141 @@ +/* integer_length - find most significant bit in an 'unsigned int'. + Copyright (C) 2011 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Written by Bruno Haible <bruno@clisp.org>, 2011. */ + +#include <config.h> + +/* Specification. */ +#include "integer_length.h" + +#include <limits.h> + +#include "float+.h" + +#define NBITS (sizeof (unsigned int) * CHAR_BIT) + +int +integer_length (unsigned int x) +{ +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + if (x == 0) + return 0; + else + return NBITS - __builtin_clz (x); +#else +# if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT + if (NBITS <= DBL_MANT_BIT) + { + /* Use 'double' operations. + Assumes an IEEE 754 'double' implementation. */ +# define DBL_EXP_MASK ((DBL_MAX_EXP - DBL_MIN_EXP) | 7) +# define DBL_EXP_BIAS (DBL_EXP_MASK / 2 - 1) +# define NWORDS \ + ((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int)) + typedef union { double value; unsigned int word[NWORDS]; } + memory_double; + + if (x == 0) + return 0; + else + { + memory_double m; + unsigned int exponent; + + if (1) + { + /* Use a single integer to floating-point conversion. */ + m.value = x; + } + else + { + /* Use a single floating-point subtraction. */ + /* 2^(DBL_MANT_DIG-1). */ + static const double TWO_DBL_MANT_DIG = + /* Assume DBL_MANT_DIG <= 5 * 31. + Use the identity + n = floor(n/5) + floor((n+1)/5) + ... + floor((n+4)/5). */ + (double) (1U << ((DBL_MANT_DIG - 1) / 5)) + * (double) (1U << ((DBL_MANT_DIG - 1 + 1) / 5)) + * (double) (1U << ((DBL_MANT_DIG - 1 + 2) / 5)) + * (double) (1U << ((DBL_MANT_DIG - 1 + 3) / 5)) + * (double) (1U << ((DBL_MANT_DIG - 1 + 4) / 5)); + + /* Construct 2^(DBL_MANT_DIG-1) + x by hand. */ + m.word[DBL_EXPBIT0_WORD] = + (DBL_MANT_DIG + DBL_EXP_BIAS) << DBL_EXPBIT0_BIT; + m.word[1 - DBL_EXPBIT0_WORD] = x; + + /* Subtract 2^(DBL_MANT_DIG-1). */ + m.value = m.value - TWO_DBL_MANT_DIG; + } + + exponent = + (m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & DBL_EXP_MASK; + return exponent - DBL_EXP_BIAS; + } + } + else +# endif + if (NBITS == 32) + { + /* 6 comparisons. */ + if (x != 0) + { + int result = 1; + if (x >= 0x10000) + { + x = x >> 16; + result += 16; + } + if (x >= 0x100) + { + x = x >> 8; + result += 8; + } + if (x >= 0x10) + { + x = x >> 4; + result += 4; + } + if (x >= 0x4) + { + x = x >> 2; + result += 2; + } + if (x >= 0x2) + { + x = x >> 1; + result += 1; + } + return result; + } + else + return 0; + } + else + { + /* Naive loop. + Works for any value of NBITS. */ + int j; + + for (j = NBITS - 1; j >= 0; j--) + if (x & (1U << j)) + return j + 1; + return 0; + } +#endif +} |