1
2
3
4
5 package ssacompile
6
7 import (
8 "math/big"
9 "testing"
10
11 "cmd/compile/internal/ssa"
12 )
13
14 func TestMagicExhaustive8(t *testing.T) {
15 testMagicExhaustive(t, 8)
16 }
17 func TestMagicExhaustive8U(t *testing.T) {
18 testMagicExhaustiveU(t, 8)
19 }
20 func TestMagicExhaustive16(t *testing.T) {
21 if testing.Short() {
22 t.Skip("slow test; skipping")
23 }
24 testMagicExhaustive(t, 16)
25 }
26 func TestMagicExhaustive16U(t *testing.T) {
27 if testing.Short() {
28 t.Skip("slow test; skipping")
29 }
30 testMagicExhaustiveU(t, 16)
31 }
32
33
34 func testMagicExhaustive(t *testing.T, n uint) {
35 min := -int64(1) << (n - 1)
36 max := int64(1) << (n - 1)
37 for c := int64(1); c < max; c++ {
38 if !ssa.SmagicOK(n, c) {
39 continue
40 }
41 m := int64(ssa.Smagic(n, c).M)
42 s := ssa.Smagic(n, c).S
43 for i := min; i < max; i++ {
44 want := i / c
45 got := (i * m) >> (n + uint(s))
46 if i < 0 {
47 got++
48 }
49 if want != got {
50 t.Errorf("signed magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
51 }
52 }
53 }
54 }
55 func testMagicExhaustiveU(t *testing.T, n uint) {
56 max := uint64(1) << n
57 for c := uint64(1); c < max; c++ {
58 if !umagicOK(n, int64(c)) {
59 continue
60 }
61 m := ssa.Umagic(n, int64(c)).M
62 s := ssa.Umagic(n, int64(c)).S
63 for i := uint64(0); i < max; i++ {
64 want := i / c
65 got := (i * (max + m)) >> (n + uint(s))
66 if want != got {
67 t.Errorf("unsigned magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
68 }
69 }
70 }
71 }
72
73 func TestMagicUnsigned(t *testing.T) {
74 One := new(big.Int).SetUint64(1)
75 for _, n := range [...]uint{8, 16, 32, 64} {
76 TwoN := new(big.Int).Lsh(One, n)
77 Max := new(big.Int).Sub(TwoN, One)
78 for _, c := range [...]uint64{
79 3,
80 5,
81 6,
82 7,
83 9,
84 10,
85 11,
86 12,
87 13,
88 14,
89 15,
90 17,
91 1<<8 - 1,
92 1<<8 + 1,
93 1<<16 - 1,
94 1<<16 + 1,
95 1<<32 - 1,
96 1<<32 + 1,
97 1<<64 - 1,
98 } {
99 if c>>n != 0 {
100 continue
101 }
102 if !umagicOK(n, int64(c)) {
103 t.Errorf("expected n=%d c=%d to pass\n", n, c)
104 }
105 m := ssa.Umagic(n, int64(c)).M
106 s := ssa.Umagic(n, int64(c)).S
107
108 C := new(big.Int).SetUint64(c)
109 M := new(big.Int).SetUint64(m)
110 M.Add(M, TwoN)
111
112
113 Mul := new(big.Int).Div(Max, C)
114 Mul.Mul(Mul, C)
115 mul := Mul.Uint64()
116
117
118 for _, x := range [...]uint64{0, 1,
119 c - 1, c, c + 1,
120 2*c - 1, 2 * c, 2*c + 1,
121 mul - 1, mul, mul + 1,
122 uint64(1)<<n - 1,
123 } {
124 X := new(big.Int).SetUint64(x)
125 if X.Cmp(Max) > 0 {
126 continue
127 }
128 Want := new(big.Int).Quo(X, C)
129 Got := new(big.Int).Mul(X, M)
130 Got.Rsh(Got, n+uint(s))
131 if Want.Cmp(Got) != 0 {
132 t.Errorf("umagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
133 }
134 }
135 }
136 }
137 }
138
139 func TestMagicSigned(t *testing.T) {
140 One := new(big.Int).SetInt64(1)
141 for _, n := range [...]uint{8, 16, 32, 64} {
142 TwoNMinusOne := new(big.Int).Lsh(One, n-1)
143 Max := new(big.Int).Sub(TwoNMinusOne, One)
144 Min := new(big.Int).Neg(TwoNMinusOne)
145 for _, c := range [...]int64{
146 3,
147 5,
148 6,
149 7,
150 9,
151 10,
152 11,
153 12,
154 13,
155 14,
156 15,
157 17,
158 1<<7 - 1,
159 1<<7 + 1,
160 1<<15 - 1,
161 1<<15 + 1,
162 1<<31 - 1,
163 1<<31 + 1,
164 1<<63 - 1,
165 } {
166 if c>>(n-1) != 0 {
167 continue
168 }
169 if !ssa.SmagicOK(n, c) {
170 t.Errorf("expected n=%d c=%d to pass\n", n, c)
171 }
172 m := ssa.Smagic(n, c).M
173 s := ssa.Smagic(n, c).S
174
175 C := new(big.Int).SetInt64(c)
176 M := new(big.Int).SetUint64(m)
177
178
179 Mul := new(big.Int).Div(Max, C)
180 Mul.Mul(Mul, C)
181 mul := Mul.Int64()
182
183
184 for _, x := range [...]int64{
185 -1, 1,
186 -c - 1, -c, -c + 1, c - 1, c, c + 1,
187 -2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
188 -mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
189 int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
190 } {
191 X := new(big.Int).SetInt64(x)
192 if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
193 continue
194 }
195 Want := new(big.Int).Quo(X, C)
196 Got := new(big.Int).Mul(X, M)
197 Got.Rsh(Got, n+uint(s))
198 if x < 0 {
199 Got.Add(Got, One)
200 }
201 if Want.Cmp(Got) != 0 {
202 t.Errorf("smagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
203 }
204 }
205 }
206 }
207 }
208
209 func testDivisibleExhaustiveU(t *testing.T, n uint) {
210 maxU := uint64(1) << n
211 for c := uint64(1); c < maxU; c++ {
212 if !ssa.UdivisibleOK(n, int64(c)) {
213 continue
214 }
215 k := ssa.Udivisible(n, int64(c)).K
216 m := ssa.Udivisible(n, int64(c)).M
217 max := ssa.Udivisible(n, int64(c)).Max
218 mask := ^uint64(0) >> (64 - n)
219 for i := uint64(0); i < maxU; i++ {
220 want := i%c == 0
221 mul := (i * m) & mask
222 rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
223 got := rot <= max
224 if want != got {
225 t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", i, c, got, want, k, m, max)
226 }
227 }
228 }
229 }
230
231 func TestDivisibleExhaustive8U(t *testing.T) {
232 testDivisibleExhaustiveU(t, 8)
233 }
234
235 func TestDivisibleExhaustive16U(t *testing.T) {
236 if testing.Short() {
237 t.Skip("slow test; skipping")
238 }
239 testDivisibleExhaustiveU(t, 16)
240 }
241
242 func TestDivisibleUnsigned(t *testing.T) {
243 One := new(big.Int).SetUint64(1)
244 for _, n := range [...]uint{8, 16, 32, 64} {
245 TwoN := new(big.Int).Lsh(One, n)
246 Max := new(big.Int).Sub(TwoN, One)
247 for _, c := range [...]uint64{
248 3,
249 5,
250 6,
251 7,
252 9,
253 10,
254 11,
255 12,
256 13,
257 14,
258 15,
259 17,
260 1<<8 - 1,
261 1<<8 + 1,
262 1<<16 - 1,
263 1<<16 + 1,
264 1<<32 - 1,
265 1<<32 + 1,
266 1<<64 - 1,
267 } {
268 if c>>n != 0 {
269 continue
270 }
271 if !ssa.UdivisibleOK(n, int64(c)) {
272 t.Errorf("expected n=%d c=%d to pass\n", n, c)
273 }
274 k := ssa.Udivisible(n, int64(c)).K
275 m := ssa.Udivisible(n, int64(c)).M
276 max := ssa.Udivisible(n, int64(c)).Max
277 mask := ^uint64(0) >> (64 - n)
278
279 C := new(big.Int).SetUint64(c)
280
281
282 Mul := new(big.Int).Div(Max, C)
283 Mul.Mul(Mul, C)
284 mul := Mul.Uint64()
285
286
287 for _, x := range [...]uint64{0, 1,
288 c - 1, c, c + 1,
289 2*c - 1, 2 * c, 2*c + 1,
290 mul - 1, mul, mul + 1,
291 uint64(1)<<n - 1,
292 } {
293 X := new(big.Int).SetUint64(x)
294 if X.Cmp(Max) > 0 {
295 continue
296 }
297 want := x%c == 0
298 mul := (x * m) & mask
299 rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
300 got := rot <= max
301 if want != got {
302 t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", x, c, got, want, k, m, max)
303 }
304 }
305 }
306 }
307 }
308
309 func testDivisibleExhaustive(t *testing.T, n uint) {
310 minI := -int64(1) << (n - 1)
311 maxI := int64(1) << (n - 1)
312 for c := int64(1); c < maxI; c++ {
313 if !ssa.SdivisibleOK(n, c) {
314 continue
315 }
316 k := ssa.Sdivisible(n, c).K
317 m := ssa.Sdivisible(n, c).M
318 a := ssa.Sdivisible(n, c).A
319 max := ssa.Sdivisible(n, c).Max
320 mask := ^uint64(0) >> (64 - n)
321 for i := minI; i < maxI; i++ {
322 want := i%c == 0
323 mul := (uint64(i)*m + a) & mask
324 rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
325 got := rot <= max
326 if want != got {
327 t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", i, c, got, want, k, m, a, max)
328 }
329 }
330 }
331 }
332
333 func TestDivisibleExhaustive8(t *testing.T) {
334 testDivisibleExhaustive(t, 8)
335 }
336
337 func TestDivisibleExhaustive16(t *testing.T) {
338 if testing.Short() {
339 t.Skip("slow test; skipping")
340 }
341 testDivisibleExhaustive(t, 16)
342 }
343
344 func TestDivisibleSigned(t *testing.T) {
345 One := new(big.Int).SetInt64(1)
346 for _, n := range [...]uint{8, 16, 32, 64} {
347 TwoNMinusOne := new(big.Int).Lsh(One, n-1)
348 Max := new(big.Int).Sub(TwoNMinusOne, One)
349 Min := new(big.Int).Neg(TwoNMinusOne)
350 for _, c := range [...]int64{
351 3,
352 5,
353 6,
354 7,
355 9,
356 10,
357 11,
358 12,
359 13,
360 14,
361 15,
362 17,
363 1<<7 - 1,
364 1<<7 + 1,
365 1<<15 - 1,
366 1<<15 + 1,
367 1<<31 - 1,
368 1<<31 + 1,
369 1<<63 - 1,
370 } {
371 if c>>(n-1) != 0 {
372 continue
373 }
374 if !ssa.SdivisibleOK(n, c) {
375 t.Errorf("expected n=%d c=%d to pass\n", n, c)
376 }
377 k := ssa.Sdivisible(n, c).K
378 m := ssa.Sdivisible(n, c).M
379 a := ssa.Sdivisible(n, c).A
380 max := ssa.Sdivisible(n, c).Max
381 mask := ^uint64(0) >> (64 - n)
382
383 C := new(big.Int).SetInt64(c)
384
385
386 Mul := new(big.Int).Div(Max, C)
387 Mul.Mul(Mul, C)
388 mul := Mul.Int64()
389
390
391 for _, x := range [...]int64{
392 -1, 1,
393 -c - 1, -c, -c + 1, c - 1, c, c + 1,
394 -2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
395 -mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
396 int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
397 } {
398 X := new(big.Int).SetInt64(x)
399 if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
400 continue
401 }
402 want := x%c == 0
403 mul := (uint64(x)*m + a) & mask
404 rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
405 got := rot <= max
406 if want != got {
407 t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", x, c, got, want, k, m, a, max)
408 }
409 }
410 }
411 }
412 }
413
View as plain text