Home | History | Annotate | Download | only in tests 
      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   register 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 }
    146