#include <glib.h>
#include <stdio.h>



gint
builtin_bit_nth_lsf1 (gulong mask, gint nth_bit)
{
  if (nth_bit >= 0)
    {
      if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1))
	mask &= -(1<<(nth_bit+1));
      else
	mask = 0;
    }
  return __builtin_ffsl(mask) - 1;
}

gint
builtin_bit_nth_lsf2 (gulong mask, gint nth_bit)
{
  if (nth_bit >= 0)
    {
      if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1))
	mask &= -(1<<(nth_bit+1));
      else
	mask = 0;
    }
  return mask ? __builtin_ctzl(mask) : -1;
}

gint
builtin_bit_nth_msf (gulong mask, gint nth_bit)
{
  if (nth_bit >= 0 && nth_bit < GLIB_SIZEOF_LONG * 8)
    mask &= (1<<nth_bit)-1;
  return mask ? GLIB_SIZEOF_LONG * 8 - 1 - __builtin_clzl(mask) : -1;
}


guint
builtin_bit_storage (gulong number)
{
  return number ? GLIB_SIZEOF_LONG * 8 - __builtin_clzl(number) : 1;
}



gint
naive_bit_nth_lsf (gulong mask, gint   nth_bit)
{
  if (G_UNLIKELY (nth_bit < -1))
    nth_bit = -1;
  while (nth_bit < ((GLIB_SIZEOF_LONG * 8) - 1))
    {
      nth_bit++;
      if (mask & (1UL << nth_bit))
	return nth_bit;
    }
  return -1;
}

gint
naive_bit_nth_msf (gulong mask, gint   nth_bit)
{
  if (nth_bit < 0 || G_UNLIKELY (nth_bit > GLIB_SIZEOF_LONG * 8))
    nth_bit = GLIB_SIZEOF_LONG * 8;
  while (nth_bit > 0)
    {
      nth_bit--;
      if (mask & (1UL << nth_bit))
	return nth_bit;
    }
  return -1;
}

guint
naive_bit_storage (gulong number)
{
  register guint n_bits = 0;
  
  do
    {
      n_bits++;
      number >>= 1;
    }
  while (number);
  return n_bits;
}



/* glib's version is buggy (bug #371631) and doesn't accept out-of-range
 * nth_bit.  wrap it.
 */
gint
gg_bit_nth_lsf (gulong mask,
		gint   nth_bit)
{
  int r = g_bit_nth_lsf (mask, MAX (nth_bit, -1));

  return r < GLIB_SIZEOF_LONG * 8 ? r : -1;
}

gint
gg_bit_nth_msf (gulong mask,
		gint   nth_bit)
{
  return g_bit_nth_msf (mask, MIN (nth_bit, GLIB_SIZEOF_LONG * 8));
}



#define TEST(f1, f2, i) \
	if (f1 (i) != f2 (i)) \
		g_error (G_STRINGIFY (f1) " (%lu) = %d; " \
			 G_STRINGIFY (f2) " (%lu) = %d; ", \
			 i, f1 (i), \
			 i, f2 (i));
#define TEST2(f1, f2, i, n) \
	if (f1 (i, n) != f2 (i, n)) \
		g_error (G_STRINGIFY (f1) " (%lu, %d) = %d; " \
			 G_STRINGIFY (f2) " (%lu, %d) = %d; ", \
			 i, n, f1 (i, n), \
			 i, n, f2 (i, n));

int
main (void)
{
  gulong i;
  gint nth_bit;

  /* we loop like this: 0, -1, 1, -2, 2, -3, 3, ... */
  for (i = 0; (glong)i < 0x11111 ; i = -(i+((glong)i>=0))) {
    if (!(i % 1000))
      {
        putchar ('.');
	fflush (stdout);
      }

    TEST (naive_bit_storage, builtin_bit_storage, i);
    TEST (naive_bit_storage, g_bit_storage, i);

    for (nth_bit = -3; nth_bit <= 2 + GLIB_SIZEOF_LONG * 8; nth_bit++) {

      TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf1, i, nth_bit);
      TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf2, i, nth_bit);
      TEST2 (naive_bit_nth_lsf, gg_bit_nth_lsf, i, nth_bit);

      TEST2 (naive_bit_nth_msf, builtin_bit_nth_msf, i, nth_bit);
      TEST2 (naive_bit_nth_msf, gg_bit_nth_msf, i, nth_bit);

    }
  }
  putchar ('\n');

  return 0;
}
