tests/bit-test.c

   1 #include <glib.h>
   2
   3 #if defined(__GNUC__) && (__GNUC__ >= 4)
   4 # define TEST_BUILTINS 1
   5 #else
   6 # define TEST_BUILTINS 0
   7 #endif
   8
   9 #if TEST_BUILTINS
  10 static gint
  11 builtin_bit_nth_lsf1 (gulong mask, gint nth_bit)
  12 {
  13   if (nth_bit >= 0)
  14     {
  15       if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1))
  16         mask &= -(1UL<<(nth_bit+1));
  17       else
  18         mask = 0;
  19     }
  20   return __builtin_ffsl(mask) - 1;
  21 }
  22
  23 static gint
  24 builtin_bit_nth_lsf2 (gulong mask, gint nth_bit)
  25 {
  26   if (nth_bit >= 0)
  27     {
  28       if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1))
  29         mask &= -(1UL<<(nth_bit+1));
  30       else
  31         mask = 0;
  32     }
  33   return mask ? __builtin_ctzl(mask) : -1;
  34 }
  35
  36 static gint
  37 builtin_bit_nth_msf (gulong mask, gint nth_bit)
  38 {
  39   if (nth_bit >= 0 && nth_bit < GLIB_SIZEOF_LONG * 8)
  40     mask &= (1UL<<nth_bit)-1;
  41   return mask ? GLIB_SIZEOF_LONG * 8 - 1 - __builtin_clzl(mask) : -1;
  42 }
  43
  44
  45 static guint
  46 builtin_bit_storage (gulong number)
  47 {
  48   return number ? GLIB_SIZEOF_LONG * 8 - __builtin_clzl(number) : 1;
  49 }
  50 #endif
  51
  52
  53 static gint
  54 naive_bit_nth_lsf (gulong mask, gint   nth_bit)
  55 {
  56   if (G_UNLIKELY (nth_bit < -1))
  57     nth_bit = -1;
  58   while (nth_bit < ((GLIB_SIZEOF_LONG * 8) - 1))
  59     {
  60       nth_bit++;
  61       if (mask & (1UL << nth_bit))
  62         return nth_bit;
  63     }
  64   return -1;
  65 }
  66
  67 static gint
  68 naive_bit_nth_msf (gulong mask, gint   nth_bit)
  69 {
  70   if (nth_bit < 0 || G_UNLIKELY (nth_bit > GLIB_SIZEOF_LONG * 8))
  71     nth_bit = GLIB_SIZEOF_LONG * 8;
  72   while (nth_bit > 0)
  73     {
  74       nth_bit--;
  75       if (mask & (1UL << nth_bit))
  76         return nth_bit;
  77     }
  78   return -1;
  79 }
  80
  81 static guint
  82 naive_bit_storage (gulong number)
  83 {
  84   guint n_bits = 0;
  85
  86   do
  87     {
  88       n_bits++;
  89       number >>= 1;
  90     }
  91   while (number);
  92   return n_bits;
  93 }
  94
  95
  96
  97 #define TEST(f1, f2, i) \
  98         if (f1 (i) != f2 (i)) { \
  99                 g_error (G_STRINGIFY (f1) " (%lu) = %d; " \
 100                          G_STRINGIFY (f2) " (%lu) = %d; ", \
 101                          i, f1 (i), \
 102                          i, f2 (i)); \
 103                 return 1; \
 104         }
 105 #define TEST2(f1, f2, i, n) \
 106         if (f1 (i, n) != f2 (i, n)) { \
 107                 g_error (G_STRINGIFY (f1) " (%lu, %d) = %d; " \
 108                          G_STRINGIFY (f2) " (%lu, %d) = %d; ", \
 109                          i, n, f1 (i, n), \
 110                          i, n, f2 (i, n)); \
 111                 return 1; \
 112         }
 113
 114 int
 115 main (void)
 116 {
 117   gulong i;
 118   gint nth_bit;
 119
 120   /* we loop like this: 0, -1, 1, -2, 2, -3, 3, ... */
 121   for (i = 0; (glong)i < 1500 ; i = -(i+((glong)i>=0))) {
 122
 123 #if TEST_BUILTINS
 124     TEST (naive_bit_storage, builtin_bit_storage, i);
 125 #endif
 126     TEST (naive_bit_storage, g_bit_storage, i);
 127
 128     for (nth_bit = -3; nth_bit <= 2 + GLIB_SIZEOF_LONG * 8; nth_bit++) {
 129
 130 #if TEST_BUILTINS
 131       TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf1, i, nth_bit);
 132       TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf2, i, nth_bit);
 133 #endif
 134       TEST2 (naive_bit_nth_lsf, g_bit_nth_lsf, i, nth_bit);
 135
 136 #if TEST_BUILTINS
 137       TEST2 (naive_bit_nth_msf, builtin_bit_nth_msf, i, nth_bit);
 138 #endif
 139       TEST2 (naive_bit_nth_msf, g_bit_nth_msf, i, nth_bit);
 140
 141     }
 142   }
 143
 144   return 0;
 145 }