Re: [PATCH] ffs: new module

[Bruno Haible]

Hi Eric,

> Libvirt wants to use ffs() to avoid dragging in -lm for log2().

log2() is also much slower than any reasonably programmed ffs() function.

> +  /* 
> http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
> +     gives this deBruijn constant for a branch-less computation, although
> +     that table counted trailing zeros rather than bit position.  */
> +  static unsigned int table[] = {
> +    1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
> +    32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
> +  };
> +  unsigned int u = i;
> +  unsigned int bit = u & -u;
> +  return table[(bit * 0x077cb531U) >> 27] - !i;

Here I would add a verification:

  /* This code assumes that 'unsigned int' has exactly 32 bits.  */
  verify (sizeof (unsigned int) * CHAR_BIT == 32);

Just to make sure we notice the problem if there should be a 64-bit 'int' on
some platform, 10 years from now.

> +static int
> +naive (int i)
> +{
> +  int j;
> +  for (j = 0; j < CHAR_BIT * sizeof i; j++)
> +    if (i & (1 << j))
> +      return j + 1;
> +  return 0;
> +}
> +
> +int
> +main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = -128; i <= 128; i++)
> +    ASSERT (ffs (i) == naive (i));
> +  for (i = 0; i < CHAR_BIT * sizeof i; i++)
> +    {
> +      ASSERT (ffs (1 << i) == naive (1 << i));
> +      ASSERT (ffs (1 << i) == i + 1);
> +    }
> +  return 0;
> +}

Signed shifts like 1 << 31 yield "undefined behaviour", i.e. a crash when
using "gcc -ftrapv". See ISO C 99 section 6.5.7.(4).

The easiest fix is to change the type of i: 'int i' to 'unsigned int i',
both in naive() and in main().

Otherwise, very fine. Thanks, Eric!

Bruno
-- 
In memoriam Zahra Kazemi <http://en.wikipedia.org/wiki/Zahra_Kazemi>