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
|
/* these first three reference functions were taken from
* http://www.hackersdelight.org/HDcode/nlz.cc and
* http://www.hackersdelight.org/HDcode/ntz.cc
*/
#include <stdio.h>
#include <string.h>
#include <strings.h>
#if defined(__XS1B__)
#include "xcoretestsuite.h"
#endif
#define u 99
int nlz10b(unsigned x) {
static char table[64] =
{32,20,19, u, u,18, u, 7, 10,17, u, u,14, u, 6, u,
u, 9, u,16, u, u, 1,26, u,13, u, u,24, 5, u, u,
u,21, u, 8,11, u,15, u, u, u, u, 2,27, 0,25, u,
22, u,12, u, u, 3,28, u, 23, u, 4,29, u, u,30,31};
x = x | (x >> 1); // Propagate leftmost
x = x | (x >> 2); // 1-bit to the right.
x = x | (x >> 4);
x = x | (x >> 8);
x = x & ~(x >> 16);
x = (x << 9) - x; // Multiply by 511.
x = (x << 11) - x; // Multiply by 2047.
x = (x << 14) - x; // Multiply by 16383.
return table[x >> 26];
}
int nlzll(unsigned long long x) {
if ((x >> 32) == 0)
return nlz10b(x)+32;
return nlz10b(x>>32);
}
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x << 8);
x = x + (x << 16);
return x >> 24;
}
int popll(unsigned long long x) {
return pop(x) + pop(x >> 32);
}
int ntz8(unsigned x) {
static char table[64] =
{32, 0, 1,12, 2, 6, u,13, 3, u, 7, u, u, u, u,14,
10, 4, u, u, 8, u, u,25, u, u, u, u, u,21,27,15,
31,11, 5, u, u, u, u, u, 9, u, u,24, u, u,20,26,
30, u, u, u, u,23, u,19, 29, u,22,18,28,17,16, u};
x = (x & -x)*0x0450FBAF;
return table[x >> 26];
}
/* Work with non-gcc compilers and GCC before 4.0 */
#if !defined(__GNUC__) || __GNUC__ < 4
#define __builtin_clz nlz10b
#define __builtin_popcount pop
#define __builtin_ctz ntz8
#define __builtin_clzll nlzll
#define __builtin_popcountll popll
#define __builtin_ffsl __builtin_ffs
#define ffsl ffs
#endif
int i;
int main(void) {
long long l;
/* note: we don't test zero, because the _native_ test will get it
* wrong (GCC returns garbage for ctz/clz of 0), and the nightly tester
* will wrongly conclude that LLC is failing.
*/
for(i=10; i<139045193; i*=-3) {
printf("LLVM: n: %d, clz(n): %d, popcount(n): %d, ctz(n): %d\n",
i, __builtin_clz(i), __builtin_popcount(i), __builtin_ctz(i));
printf("REF : n: %d, clz(n): %d, popcount(n): %d, ctz(n): %d\n",
i, nlz10b(i), pop(i), ntz8(i));
printf(" *** \n");
i++;
}
for(l=-10000; l<139045193*10000LL; l*=-3) {
printf("LLVM: n: %lld, clz(n): %d, popcount(n): %d, ctz(n): %d\n",
l, __builtin_clzll(l), __builtin_popcountll(l), __builtin_ctz(l));
printf("REF LO BITS : n: %lld, clz(n): %d, popcount(n): %d, ctz(n): %d\n",
l, nlzll(l), popll(l), ntz8(l));
printf(" *** \n");
l++;
}
// Check some boundary and other cases for FFS call
printf("FFS: 0:%d, 1:%d, 2:%d, 7:%d, 1024:%d, 1234:%d i:%d, l:%d\n",
ffs(0), ffs(1), ffs(2), ffs(7), ffs(1024), ffs(1234), ffs(i), ffsl(l));
printf("__builtin_ffs: 0:%d, 1:%d, 2:%d, 7:%d, 1024:%d, 1234:%d i:%d l:%d\n",
__builtin_ffs(0), __builtin_ffs(1), __builtin_ffs(2), __builtin_ffs(7),
__builtin_ffs(1024), __builtin_ffs(1234), __builtin_ffs(i), __builtin_ffsl(l));
return(0);
}
|
