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