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