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 | } |
146 | |