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