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
builtin_bit_nth_lsf1(gulong mask,gint nth_bit)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
builtin_bit_nth_lsf2(gulong mask,gint nth_bit)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
builtin_bit_nth_msf(gulong mask,gint nth_bit)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
builtin_bit_storage(gulong number)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
naive_bit_nth_lsf(gulong mask,gint nth_bit)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
naive_bit_nth_msf(gulong mask,gint nth_bit)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
naive_bit_storage(gulong number)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
main(void)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