From 8d7da1803b272963476166a4d88a309b81430bbd Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 15 Oct 2011 02:12:09 +0200 Subject: [PATCH] New module 'integer_length'. * lib/integer_length.h: New file. * lib/integer_length.c: New file. * modules/integer_length: New file. --- ChangeLog | 7 ++ lib/integer_length.c | 141 +++++++++++++++++++++++++++++++++++++++++ lib/integer_length.h | 49 ++++++++++++++ modules/integer_length | 28 ++++++++ 4 files changed, 225 insertions(+) create mode 100644 lib/integer_length.c create mode 100644 lib/integer_length.h create mode 100644 modules/integer_length diff --git a/ChangeLog b/ChangeLog index 7530b73efe..03a78f7860 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2011-10-14 Bruno Haible + + 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. (tiny change) popen: Fix dependency conditions. diff --git a/lib/integer_length.c b/lib/integer_length.c new file mode 100644 index 0000000000..e5ab6650da --- /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 . */ + +/* Written by Bruno Haible , 2011. */ + +#include + +/* Specification. */ +#include "integer_length.h" + +#include + +#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 +} diff --git a/lib/integer_length.h b/lib/integer_length.h new file mode 100644 index 0000000000..d51130f95e --- /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 . */ + +/* Written by Bruno Haible , 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 */ diff --git a/modules/integer_length b/modules/integer_length new file mode 100644 index 0000000000..e757772831 --- /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 -- 2.39.5