File: bit-test.c

package info (click to toggle)
glib2.0 2.58.3-2
  • links: PTS, VCS
  • area: main
  • in suites: buster, buster-proposed-updates
  • size: 48,744 kB
  • sloc: ansic: 452,196; xml: 16,781; python: 6,149; makefile: 3,776; sh: 1,499; perl: 1,140; cpp: 9
file content (145 lines) | stat: -rw-r--r-- 2,865 bytes parent folder | download | duplicates (8)
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;
}