bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

new module 'integer_length'


From: Bruno Haible
Subject: new module 'integer_length'
Date: Fri, 14 Oct 2011 04:16:21 +0200
User-agent: KMail/1.13.6 (Linux/2.6.37.6-0.5-desktop; KDE/4.6.0; x86_64; ; )

Hi,

The code in vasnprintf.c around line 560, which determines the most
significant set bit in an 'unsigned int' word, is not optimally
efficient.

ffs() is a nice primitive, but integer_length() is more powerful,
because ffs(x) == integer_length(x & -x).

This primitive is usally called integer_length() (heritage from Common Lisp).
In GMP you get it through mpz_sizeinbase(x,2).

Here's a proposed module to this effect. Similar modules for the
'unsigned long' and 'unsigned long long' variants will follow.

Comments? Objections?


============================ lib/integer_length.h ============================
/* 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 <address@hidden>, 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 */
============================ lib/integer_length.c ============================
/* 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 <address@hidden>, 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
}
=========================== modules/integer_length ===========================
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
==============================================================================
-- 
In memoriam Bekir Çoban-zade <http://en.wikipedia.org/wiki/Bekir_Çoban-zade>



reply via email to

[Prev in Thread] Current Thread [Next in Thread]