forked from hcs0/Hackers-Delight
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sagLE.c.txt
143 lines (115 loc) · 3.78 KB
/
sagLE.c.txt
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
/* Little-endian version of code from GLS, 10/12/02. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
char * binary(unsigned k); // These are below.
unsigned compress(unsigned x, unsigned m);
unsigned compress_left(unsigned x, unsigned m);
unsigned SAG(unsigned x, unsigned m) {
return compress_left(x, m) | compress(x, ~m);
}
int main(void)
{
unsigned x0, x;
static unsigned p[5] = {0xAAAAAAAA, /* This is for rotate left, */
0xCCCCCCCC, /* LE version of SAG, */
0x0F0F0F0F, /* LE bit numbering. */
0x0FF00FF0,
0x0FFFF000};
static unsigned q[5] = {0xAAAAAAAA, /* This is for rotate left, */
0xCCCCCCCC, /* LE version of SAG, */
0x0F0F0F0F, /* LE bit numbering. */
0x0FF00FF0,
0x0FFFF000};
x0 = 0x01234567;
x = SAG(x0, p[0]);
p[1] = SAG(p[1], p[0]);
p[2] = SAG(p[2], p[0]);
p[3] = SAG(p[3], p[0]);
p[4] = SAG(p[4], p[0]);
x = SAG(x, p[1]);
p[2] = SAG(p[2], p[1]);
p[3] = SAG(p[3], p[1]);
p[4] = SAG(p[4], p[1]);
x = SAG(x, p[2]);
p[3] = SAG(p[3], p[2]);
p[4] = SAG(p[4], p[2]);
x = SAG(x, p[3]);
p[4] = SAG(p[4], p[3]);
x = SAG(x, p[4]);
printf("x0 = %s\n", binary(x0));
printf("x = %s\n", binary(x));
if (x != 0x12345670) printf("Error\n");
else printf("OK\n");
// Now check out the version with constants moved out of a loop.
q[1] = SAG(q[1], q[0]);
q[2] = SAG(SAG(q[2], q[0]), q[1]);
q[3] = SAG(SAG(SAG(q[3], q[0]), q[1]), q[2]);
q[4] = SAG(SAG(SAG(SAG(q[4], q[0]), q[1]), q[2]), q[3]);
x = SAG(x0, q[0]);
x = SAG( x, q[1]);
x = SAG( x, q[2]);
x = SAG( x, q[3]);
x = SAG( x, q[4]);
printf("x0 = %s\n", binary(x0));
printf("x = %s\n", binary(x));
if (x != 0x12345670) printf("Error\n");
else printf("OK\n");
return 0;
}
/* Converts the unsigned integer k to binary character form with a blank
after every fourth digit. Result is in string s of length 39. Caution:
If you want to save the string, you must move it. This is intended for
use with printf, and you can have only one reference to this in each
printf statement. */
char * binary(unsigned k) {
int i, j;
static char s[40] = "0000 0000 0000 0000 0000 0000 0000 0000";
j = 38;
for (i = 31; i >= 0; i--) {
if (k & 1) s[j] = '1';
else s[j] = '0';
j = j - 1;
k = k >> 1;
if ((i & 3) == 0) j = j - 1;
}
return s;
}
unsigned compress(unsigned x, unsigned m) {
unsigned mk, mp, mv, t;
int i;
x = x & m; // Clear irrelevant bits.
mk = ~m << 1; // We will count 0's to right.
for (i = 0; i < 5; i++) {
mp = mk ^ (mk << 1); // Parallel suffix.
mp = mp ^ (mp << 2);
mp = mp ^ (mp << 4);
mp = mp ^ (mp << 8);
mp = mp ^ (mp << 16);
mv = mp & m; // Bits to move.
m = m ^ mv | (mv >> (1 << i)); // Compress m.
t = x & mv;
x = x ^ t | (t >> (1 << i)); // Compress x.
mk = mk & ~mp;
}
return x;
}
unsigned compress_left(unsigned x, unsigned m) {
unsigned mk, mp, mv, t;
int i;
x = x & m; // Clear irrelevant bits.
mk = ~m >> 1; // We will count 0's to left.
for (i = 0; i < 5; i++) {
mp = mk ^ (mk >> 1); // Parallel prefix.
mp = mp ^ (mp >> 2);
mp = mp ^ (mp >> 4);
mp = mp ^ (mp >> 8);
mp = mp ^ (mp >> 16);
mv = mp & m; // Bits to move.
m = m ^ mv | (mv << (1 << i)); // Compress m.
t = x & mv;
x = x ^ t | (t << (1 << i)); // Compress x.
mk = mk & ~mp;
}
return x;
}