1// Copyright 2019 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 big_test
6
7import (
8	cryptorand "crypto/rand"
9	"math/big"
10	"math/rand"
11	"reflect"
12	"testing"
13	"testing/quick"
14)
15
16func equal(z, x *big.Int) bool {
17	return z.Cmp(x) == 0
18}
19
20type bigInt struct {
21	*big.Int
22}
23
24func generatePositiveInt(rand *rand.Rand, size int) *big.Int {
25	n := big.NewInt(1)
26	n.Lsh(n, uint(rand.Intn(size*8)))
27	n.Rand(rand, n)
28	return n
29}
30
31func (bigInt) Generate(rand *rand.Rand, size int) reflect.Value {
32	n := generatePositiveInt(rand, size)
33	if rand.Intn(4) == 0 {
34		n.Neg(n)
35	}
36	return reflect.ValueOf(bigInt{n})
37}
38
39type notZeroInt struct {
40	*big.Int
41}
42
43func (notZeroInt) Generate(rand *rand.Rand, size int) reflect.Value {
44	n := generatePositiveInt(rand, size)
45	if rand.Intn(4) == 0 {
46		n.Neg(n)
47	}
48	if n.Sign() == 0 {
49		n.SetInt64(1)
50	}
51	return reflect.ValueOf(notZeroInt{n})
52}
53
54type positiveInt struct {
55	*big.Int
56}
57
58func (positiveInt) Generate(rand *rand.Rand, size int) reflect.Value {
59	n := generatePositiveInt(rand, size)
60	return reflect.ValueOf(positiveInt{n})
61}
62
63type prime struct {
64	*big.Int
65}
66
67func (prime) Generate(r *rand.Rand, size int) reflect.Value {
68	n, err := cryptorand.Prime(r, r.Intn(size*8-2)+2)
69	if err != nil {
70		panic(err)
71	}
72	return reflect.ValueOf(prime{n})
73}
74
75type zeroOrOne struct {
76	uint
77}
78
79func (zeroOrOne) Generate(rand *rand.Rand, size int) reflect.Value {
80	return reflect.ValueOf(zeroOrOne{uint(rand.Intn(2))})
81}
82
83type smallUint struct {
84	uint
85}
86
87func (smallUint) Generate(rand *rand.Rand, size int) reflect.Value {
88	return reflect.ValueOf(smallUint{uint(rand.Intn(1024))})
89}
90
91// checkAliasingOneArg checks if f returns a correct result when v and x alias.
92//
93// f is a function that takes x as an argument, doesn't modify it, sets v to the
94// result, and returns v. It is the function signature of unbound methods like
95//
96//	func (v *big.Int) m(x *big.Int) *big.Int
97//
98// v and x are two random Int values. v is randomized even if it will be
99// overwritten to test for improper buffer reuse.
100func checkAliasingOneArg(t *testing.T, f func(v, x *big.Int) *big.Int, v, x *big.Int) bool {
101	x1, v1 := new(big.Int).Set(x), new(big.Int).Set(x)
102
103	// Calculate a reference f(x) without aliasing.
104	if out := f(v, x); out != v {
105		return false
106	}
107
108	// Test aliasing the argument and the receiver.
109	if out := f(v1, v1); out != v1 || !equal(v1, v) {
110		t.Logf("f(v, x) != f(x, x)")
111		return false
112	}
113
114	// Ensure the arguments was not modified.
115	return equal(x, x1)
116}
117
118// checkAliasingTwoArgs checks if f returns a correct result when any
119// combination of v, x and y alias.
120//
121// f is a function that takes x and y as arguments, doesn't modify them, sets v
122// to the result, and returns v. It is the function signature of unbound methods
123// like
124//
125//	func (v *big.Int) m(x, y *big.Int) *big.Int
126//
127// v, x and y are random Int values. v is randomized even if it will be
128// overwritten to test for improper buffer reuse.
129func checkAliasingTwoArgs(t *testing.T, f func(v, x, y *big.Int) *big.Int, v, x, y *big.Int) bool {
130	x1, y1, v1 := new(big.Int).Set(x), new(big.Int).Set(y), new(big.Int).Set(v)
131
132	// Calculate a reference f(x, y) without aliasing.
133	if out := f(v, x, y); out == nil {
134		// Certain functions like ModInverse return nil for certain inputs.
135		// Check that receiver and arguments were unchanged and move on.
136		return equal(x, x1) && equal(y, y1) && equal(v, v1)
137	} else if out != v {
138		return false
139	}
140
141	// Test aliasing the first argument and the receiver.
142	v1.Set(x)
143	if out := f(v1, v1, y); out != v1 || !equal(v1, v) {
144		t.Logf("f(v, x, y) != f(x, x, y)")
145		return false
146	}
147	// Test aliasing the second argument and the receiver.
148	v1.Set(y)
149	if out := f(v1, x, v1); out != v1 || !equal(v1, v) {
150		t.Logf("f(v, x, y) != f(y, x, y)")
151		return false
152	}
153
154	// Calculate a reference f(y, y) without aliasing.
155	// We use y because it's the one that commonly has restrictions
156	// like being prime or non-zero.
157	v1.Set(v)
158	y2 := new(big.Int).Set(y)
159	if out := f(v, y, y2); out == nil {
160		return equal(y, y1) && equal(y2, y1) && equal(v, v1)
161	} else if out != v {
162		return false
163	}
164
165	// Test aliasing the two arguments.
166	if out := f(v1, y, y); out != v1 || !equal(v1, v) {
167		t.Logf("f(v, y1, y2) != f(v, y, y)")
168		return false
169	}
170	// Test aliasing the two arguments and the receiver.
171	v1.Set(y)
172	if out := f(v1, v1, v1); out != v1 || !equal(v1, v) {
173		t.Logf("f(v, y1, y2) != f(y, y, y)")
174		return false
175	}
176
177	// Ensure the arguments were not modified.
178	return equal(x, x1) && equal(y, y1)
179}
180
181func TestAliasing(t *testing.T) {
182	for name, f := range map[string]interface{}{
183		"Abs": func(v, x bigInt) bool {
184			return checkAliasingOneArg(t, (*big.Int).Abs, v.Int, x.Int)
185		},
186		"Add": func(v, x, y bigInt) bool {
187			return checkAliasingTwoArgs(t, (*big.Int).Add, v.Int, x.Int, y.Int)
188		},
189		"And": func(v, x, y bigInt) bool {
190			return checkAliasingTwoArgs(t, (*big.Int).And, v.Int, x.Int, y.Int)
191		},
192		"AndNot": func(v, x, y bigInt) bool {
193			return checkAliasingTwoArgs(t, (*big.Int).AndNot, v.Int, x.Int, y.Int)
194		},
195		"Div": func(v, x bigInt, y notZeroInt) bool {
196			return checkAliasingTwoArgs(t, (*big.Int).Div, v.Int, x.Int, y.Int)
197		},
198		"Exp-XY": func(v, x, y bigInt, z notZeroInt) bool {
199			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
200				return v.Exp(x, y, z.Int)
201			}, v.Int, x.Int, y.Int)
202		},
203		"Exp-XZ": func(v, x, y bigInt, z notZeroInt) bool {
204			return checkAliasingTwoArgs(t, func(v, x, z *big.Int) *big.Int {
205				return v.Exp(x, y.Int, z)
206			}, v.Int, x.Int, z.Int)
207		},
208		"Exp-YZ": func(v, x, y bigInt, z notZeroInt) bool {
209			return checkAliasingTwoArgs(t, func(v, y, z *big.Int) *big.Int {
210				return v.Exp(x.Int, y, z)
211			}, v.Int, y.Int, z.Int)
212		},
213		"GCD": func(v, x, y bigInt) bool {
214			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
215				return v.GCD(nil, nil, x, y)
216			}, v.Int, x.Int, y.Int)
217		},
218		"GCD-X": func(v, x, y bigInt) bool {
219			a, b := new(big.Int), new(big.Int)
220			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
221				a.GCD(v, b, x, y)
222				return v
223			}, v.Int, x.Int, y.Int)
224		},
225		"GCD-Y": func(v, x, y bigInt) bool {
226			a, b := new(big.Int), new(big.Int)
227			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
228				a.GCD(b, v, x, y)
229				return v
230			}, v.Int, x.Int, y.Int)
231		},
232		"Lsh": func(v, x bigInt, n smallUint) bool {
233			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
234				return v.Lsh(x, n.uint)
235			}, v.Int, x.Int)
236		},
237		"Mod": func(v, x bigInt, y notZeroInt) bool {
238			return checkAliasingTwoArgs(t, (*big.Int).Mod, v.Int, x.Int, y.Int)
239		},
240		"ModInverse": func(v, x bigInt, y notZeroInt) bool {
241			return checkAliasingTwoArgs(t, (*big.Int).ModInverse, v.Int, x.Int, y.Int)
242		},
243		"ModSqrt": func(v, x bigInt, p prime) bool {
244			return checkAliasingTwoArgs(t, (*big.Int).ModSqrt, v.Int, x.Int, p.Int)
245		},
246		"Mul": func(v, x, y bigInt) bool {
247			return checkAliasingTwoArgs(t, (*big.Int).Mul, v.Int, x.Int, y.Int)
248		},
249		"Neg": func(v, x bigInt) bool {
250			return checkAliasingOneArg(t, (*big.Int).Neg, v.Int, x.Int)
251		},
252		"Not": func(v, x bigInt) bool {
253			return checkAliasingOneArg(t, (*big.Int).Not, v.Int, x.Int)
254		},
255		"Or": func(v, x, y bigInt) bool {
256			return checkAliasingTwoArgs(t, (*big.Int).Or, v.Int, x.Int, y.Int)
257		},
258		"Quo": func(v, x bigInt, y notZeroInt) bool {
259			return checkAliasingTwoArgs(t, (*big.Int).Quo, v.Int, x.Int, y.Int)
260		},
261		"Rand": func(v, x bigInt, seed int64) bool {
262			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
263				rnd := rand.New(rand.NewSource(seed))
264				return v.Rand(rnd, x)
265			}, v.Int, x.Int)
266		},
267		"Rem": func(v, x bigInt, y notZeroInt) bool {
268			return checkAliasingTwoArgs(t, (*big.Int).Rem, v.Int, x.Int, y.Int)
269		},
270		"Rsh": func(v, x bigInt, n smallUint) bool {
271			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
272				return v.Rsh(x, n.uint)
273			}, v.Int, x.Int)
274		},
275		"Set": func(v, x bigInt) bool {
276			return checkAliasingOneArg(t, (*big.Int).Set, v.Int, x.Int)
277		},
278		"SetBit": func(v, x bigInt, i smallUint, b zeroOrOne) bool {
279			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
280				return v.SetBit(x, int(i.uint), b.uint)
281			}, v.Int, x.Int)
282		},
283		"Sqrt": func(v bigInt, x positiveInt) bool {
284			return checkAliasingOneArg(t, (*big.Int).Sqrt, v.Int, x.Int)
285		},
286		"Sub": func(v, x, y bigInt) bool {
287			return checkAliasingTwoArgs(t, (*big.Int).Sub, v.Int, x.Int, y.Int)
288		},
289		"Xor": func(v, x, y bigInt) bool {
290			return checkAliasingTwoArgs(t, (*big.Int).Xor, v.Int, x.Int, y.Int)
291		},
292	} {
293		t.Run(name, func(t *testing.T) {
294			scale := 1.0
295			switch name {
296			case "ModInverse", "GCD-Y", "GCD-X":
297				scale /= 5
298			case "Rand":
299				scale /= 10
300			case "Exp-XZ", "Exp-XY", "Exp-YZ":
301				scale /= 50
302			case "ModSqrt":
303				scale /= 500
304			}
305			if err := quick.Check(f, &quick.Config{
306				MaxCountScale: scale,
307			}); err != nil {
308				t.Error(err)
309			}
310		})
311	}
312}
313