From e4015779cec51757b48977760375f3947d0201bd Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sat, 15 Oct 2011 02:15:31 +0200 Subject: [PATCH] New module 'integer_length_l'. * lib/integer_length_l.c: New file. * modules/integer_length_l: New file. --- ChangeLog | 6 +++ lib/integer_length_l.c | 81 ++++++++++++++++++++++++++++++++++++++++ modules/integer_length_l | 25 +++++++++++++ 3 files changed, 112 insertions(+) create mode 100644 lib/integer_length_l.c create mode 100644 modules/integer_length_l diff --git a/ChangeLog b/ChangeLog index 5366cd3939..c45d764737 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2011-10-14 Bruno Haible + + New module 'integer_length_l'. + * lib/integer_length_l.c: New file. + * modules/integer_length_l: New file. + 2011-10-14 Bruno Haible Tests for module 'integer_length'. diff --git a/lib/integer_length_l.c b/lib/integer_length_l.c new file mode 100644 index 0000000000..483e02338e --- /dev/null +++ b/lib/integer_length_l.c @@ -0,0 +1,81 @@ +/* integer_length_l - find most significant bit in an 'unsigned long'. + 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 + +#undef MIN +#define MIN(a,b) ((a) < (b) ? (a) : (b)) + +#ifdef USE_LONG_LONG +# define FUNC integer_length_ll +# define TYPE unsigned long long +# define GCC_BUILTIN __builtin_clzll +#else +# define FUNC integer_length_l +# define TYPE unsigned long +# define GCC_BUILTIN __builtin_clzl +#endif + +#define NBITS (sizeof (TYPE) * CHAR_BIT) + +/* Modify shift count to be in bounds, even in dead code, otherwise GCC + emits warnings "right shift count >= width of type". */ +#define MSC(i) MIN (i, NBITS - 1) + +int +FUNC (TYPE x) +{ +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + if (x == 0) + return 0; + else + return NBITS - GCC_BUILTIN (x); +#else + /* Split x into chunks, and look at one chunk after the other. */ + if (sizeof (TYPE) > 2 * sizeof (unsigned int)) + { + /* Generic loop. */ + size_t i; + + for (i = (sizeof (TYPE) - 1) / sizeof (unsigned int); i >= 2; i--) + { + unsigned int y = x >> (i * sizeof (unsigned int) * CHAR_BIT); + if (y != 0) + return i * sizeof (unsigned int) * CHAR_BIT + integer_length (y); + } + } + + /* Unrolled the last 2 loop rounds. */ + /* i = 1 */ + if (sizeof (TYPE) > 1 * sizeof (unsigned int)) + { + unsigned int y = x >> MSC (1 * sizeof (unsigned int) * CHAR_BIT); + if (y != 0) + return 1 * sizeof (unsigned int) * CHAR_BIT + integer_length (y); + } + + /* i = 0 */ + return integer_length ((unsigned int) x); +#endif +} diff --git a/modules/integer_length_l b/modules/integer_length_l new file mode 100644 index 0000000000..93a423cc91 --- /dev/null +++ b/modules/integer_length_l @@ -0,0 +1,25 @@ +Description: +Finds the most significant bit in an 'unsigned long'. + +Files: +lib/integer_length.h +lib/integer_length_l.c +m4/longlong.m4 + +Depends-on: +integer_length + +configure.ac: +AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) + +Makefile.am: +lib_SOURCES += integer_length_l.c + +Include: +"integer_length.h" + +License: +LGPLv2+ + +Maintainer: +Bruno Haible -- 2.39.5