Mercurial > hg > octave-lyh > gnulib-hg
changeset 15952:10da83926c24
New module 'integer_length'.
* lib/integer_length.h: New file.
* lib/integer_length.c: New file.
* modules/integer_length: New file.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Sat, 15 Oct 2011 02:12:09 +0200 |
parents | cf6263b60cda |
children | 3d1d9a55be68 |
files | ChangeLog lib/integer_length.c lib/integer_length.h modules/integer_length |
diffstat | 4 files changed, 225 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2011-10-14 Bruno Haible <bruno@clisp.org> + + New module 'integer_length'. + * lib/integer_length.h: New file. + * lib/integer_length.c: New file. + * modules/integer_length: New file. + 2011-10-14 Daniel Richard G. <skunk@iskunk.org> (tiny change) popen: Fix dependency conditions.
new file mode 100644 --- /dev/null +++ b/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 +}
new file mode 100644 --- /dev/null +++ b/lib/integer_length.h @@ -0,0 +1,49 @@ +/* integer_length - find most significant bit in an unsigned integer. + 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. */ + +#ifndef _INTEGER_LENGTH_H +#define _INTEGER_LENGTH_H + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions return the minimum number of bits required to represent + the given unsigned integer. + For non-zero values, this is the position of the most significant bit + that is set, plus one. For zero, it is 0. */ + +/* Returns the integer length of x. + The result is >= 0, <= sizeof (unsigned int) * CHAR_BIT. */ +extern int integer_length (unsigned int x); + +/* Returns the integer length of x. + The result is >= 0, <= sizeof (unsigned long) * CHAR_BIT. */ +extern int integer_length_l (unsigned long x); + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Returns the integer length of x. + The result is >= 0, <= sizeof (unsigned long long) * CHAR_BIT. */ +extern int integer_length_ll (unsigned long long x); +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* _INTEGER_LENGTH_H */
new file mode 100644 --- /dev/null +++ b/modules/integer_length @@ -0,0 +1,28 @@ +Description: +Finds the most significant bit in an 'unsigned int'. + +Files: +lib/integer_length.h +lib/integer_length.c +lib/float+.h +m4/longlong.m4 +m4/exponentd.m4 + +Depends-on: +float + +configure.ac: +AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) +AC_REQUIRE([gl_DOUBLE_EXPONENT_LOCATION]) + +Makefile.am: +lib_SOURCES += integer_length.c + +Include: +"integer_length.h" + +License: +LGPLv2+ + +Maintainer: +Bruno Haible