alias_test.go

     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  
     5  package big_test
     6  
     7  import (
     8  	cryptorand "crypto/rand"
     9  	"math/big"
    10  	"math/rand"
    11  	"reflect"
    12  	"testing"
    13  	"testing/quick"
    14  )
    15  
    16  func equal(z, x *big.Int) bool {
    17  	return z.Cmp(x) == 0
    18  }
    19  
    20  type bigInt struct {
    21  	*big.Int
    22  }
    23  
    24  func 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  
    31  func (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  
    39  type notZeroInt struct {
    40  	*big.Int
    41  }
    42  
    43  func (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  
    54  type positiveInt struct {
    55  	*big.Int
    56  }
    57  
    58  func (positiveInt) Generate(rand *rand.Rand, size int) reflect.Value {
    59  	n := generatePositiveInt(rand, size)
    60  	return reflect.ValueOf(positiveInt{n})
    61  }
    62  
    63  type prime struct {
    64  	*big.Int
    65  }
    66  
    67  func (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  
    75  type zeroOrOne struct {
    76  	uint
    77  }
    78  
    79  func (zeroOrOne) Generate(rand *rand.Rand, size int) reflect.Value {
    80  	return reflect.ValueOf(zeroOrOne{uint(rand.Intn(2))})
    81  }
    82  
    83  type smallUint struct {
    84  	uint
    85  }
    86  
    87  func (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.
   100  func 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.
   129  func 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  
   181  // checkAliasingTwoResults checks if f returns correct results when any
   182  // combination of v, x, y and w alias.
   183  //
   184  // f is a function that takes x and y as arguments, doesn't modify them, sets v
   185  // and w to the two results, and returns them. It is the function signature of
   186  // unbound methods like
   187  //
   188  //	func (v *big.Int) m(x, y, w *big.Int) (*big.Int, *big.Int)
   189  //
   190  // v, x, y and w are random Int values. v and w are randomized even if they will
   191  // be overwritten to test for improper buffer reuse.
   192  func checkAliasingTwoResults(t *testing.T, f func(v, x, y, w *big.Int) (*big.Int, *big.Int), v, x, y, w *big.Int) bool {
   193  	x1, y1 := new(big.Int).Set(x), new(big.Int).Set(y)
   194  	v1, w1 := new(big.Int).Set(v), new(big.Int).Set(w)
   195  
   196  	// Calculate a reference f(x, y) without aliasing.
   197  	if out1, out2 := f(v, x, y, w); out1 != v || out2 != w {
   198  		return false
   199  	}
   200  
   201  	// Test aliasing the first argument and the receiver.
   202  	v1.Set(x)
   203  	if out1, out2 := f(v1, v1, y, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   204  		t.Logf("f(v, x, y, w) != f(x, x, y, w)")
   205  		return false
   206  	}
   207  	// Test aliasing the second argument and the receiver.
   208  	v1.Set(y)
   209  	if out1, out2 := f(v1, x, v1, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   210  		t.Logf("f(v, x, y, w) != f(y, x, y, w)")
   211  		return false
   212  	}
   213  	// Test aliasing the first argument and the second result.
   214  	w1.Set(x)
   215  	if out1, out2 := f(v1, w1, y, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   216  		t.Logf("f(v, x, y, w) != f(v, x, y, x)")
   217  		return false
   218  	}
   219  	// Test aliasing the second argument and the second result.
   220  	w1.Set(y)
   221  	if out1, out2 := f(v1, x, w1, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   222  		t.Logf("f(v, x, y, w) != f(v, x, y, y)")
   223  		return false
   224  	}
   225  	// Test aliasing both arguments with both results.
   226  	v1.Set(x)
   227  	w1.Set(y)
   228  	if out1, out2 := f(v1, v1, w1, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   229  		t.Logf("f(v, x, y, w) != f(x, x, y, y)")
   230  		return false
   231  	}
   232  	// Test aliasing both arguments with both results, crosswise.
   233  	v1.Set(y)
   234  	w1.Set(x)
   235  	if out1, out2 := f(v1, w1, v1, w1); out1 != v1 || out2 != w1 || !equal(v1, v) || !equal(w1, w) {
   236  		t.Logf("f(v, x, y, w) != f(y, x, y, x)")
   237  		return false
   238  	}
   239  
   240  	// Ensure the arguments were not modified.
   241  	return equal(x, x1) && equal(y, y1)
   242  }
   243  
   244  func TestAliasing(t *testing.T) {
   245  	for name, f := range map[string]any{
   246  		"Abs": func(v, x bigInt) bool {
   247  			return checkAliasingOneArg(t, (*big.Int).Abs, v.Int, x.Int)
   248  		},
   249  		"Add": func(v, x, y bigInt) bool {
   250  			return checkAliasingTwoArgs(t, (*big.Int).Add, v.Int, x.Int, y.Int)
   251  		},
   252  		"And": func(v, x, y bigInt) bool {
   253  			return checkAliasingTwoArgs(t, (*big.Int).And, v.Int, x.Int, y.Int)
   254  		},
   255  		"AndNot": func(v, x, y bigInt) bool {
   256  			return checkAliasingTwoArgs(t, (*big.Int).AndNot, v.Int, x.Int, y.Int)
   257  		},
   258  		"Div": func(v, x bigInt, y notZeroInt) bool {
   259  			return checkAliasingTwoArgs(t, (*big.Int).Div, v.Int, x.Int, y.Int)
   260  		},
   261  		"DivMod": func(v, w, x bigInt, y notZeroInt) bool {
   262  			return checkAliasingTwoResults(t, (*big.Int).DivMod, v.Int, x.Int, y.Int, w.Int)
   263  		},
   264  		"Exp-XY": func(v, x, y bigInt, z notZeroInt) bool {
   265  			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
   266  				return v.Exp(x, y, z.Int)
   267  			}, v.Int, x.Int, y.Int)
   268  		},
   269  		"Exp-XZ": func(v, x, y bigInt, z notZeroInt) bool {
   270  			return checkAliasingTwoArgs(t, func(v, x, z *big.Int) *big.Int {
   271  				return v.Exp(x, y.Int, z)
   272  			}, v.Int, x.Int, z.Int)
   273  		},
   274  		"Exp-YZ": func(v, x, y bigInt, z notZeroInt) bool {
   275  			return checkAliasingTwoArgs(t, func(v, y, z *big.Int) *big.Int {
   276  				return v.Exp(x.Int, y, z)
   277  			}, v.Int, y.Int, z.Int)
   278  		},
   279  		"GCD": func(v, x, y bigInt) bool {
   280  			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
   281  				return v.GCD(nil, nil, x, y)
   282  			}, v.Int, x.Int, y.Int)
   283  		},
   284  		"GCD-X": func(v, x, y bigInt) bool {
   285  			a, b := new(big.Int), new(big.Int)
   286  			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
   287  				a.GCD(v, b, x, y)
   288  				return v
   289  			}, v.Int, x.Int, y.Int)
   290  		},
   291  		"GCD-Y": func(v, x, y bigInt) bool {
   292  			a, b := new(big.Int), new(big.Int)
   293  			return checkAliasingTwoArgs(t, func(v, x, y *big.Int) *big.Int {
   294  				a.GCD(b, v, x, y)
   295  				return v
   296  			}, v.Int, x.Int, y.Int)
   297  		},
   298  		"Lsh": func(v, x bigInt, n smallUint) bool {
   299  			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
   300  				return v.Lsh(x, n.uint)
   301  			}, v.Int, x.Int)
   302  		},
   303  		"Mod": func(v, x bigInt, y notZeroInt) bool {
   304  			return checkAliasingTwoArgs(t, (*big.Int).Mod, v.Int, x.Int, y.Int)
   305  		},
   306  		"ModInverse": func(v, x bigInt, y notZeroInt) bool {
   307  			return checkAliasingTwoArgs(t, (*big.Int).ModInverse, v.Int, x.Int, y.Int)
   308  		},
   309  		"ModSqrt": func(v, x bigInt, p prime) bool {
   310  			return checkAliasingTwoArgs(t, (*big.Int).ModSqrt, v.Int, x.Int, p.Int)
   311  		},
   312  		"Mul": func(v, x, y bigInt) bool {
   313  			return checkAliasingTwoArgs(t, (*big.Int).Mul, v.Int, x.Int, y.Int)
   314  		},
   315  		"Neg": func(v, x bigInt) bool {
   316  			return checkAliasingOneArg(t, (*big.Int).Neg, v.Int, x.Int)
   317  		},
   318  		"Not": func(v, x bigInt) bool {
   319  			return checkAliasingOneArg(t, (*big.Int).Not, v.Int, x.Int)
   320  		},
   321  		"Or": func(v, x, y bigInt) bool {
   322  			return checkAliasingTwoArgs(t, (*big.Int).Or, v.Int, x.Int, y.Int)
   323  		},
   324  		"Quo": func(v, x bigInt, y notZeroInt) bool {
   325  			return checkAliasingTwoArgs(t, (*big.Int).Quo, v.Int, x.Int, y.Int)
   326  		},
   327  		"QuoRem": func(v, w, x bigInt, y notZeroInt) bool {
   328  			return checkAliasingTwoResults(t, (*big.Int).QuoRem, v.Int, x.Int, y.Int, w.Int)
   329  		},
   330  		"Rand": func(v, x bigInt, seed int64) bool {
   331  			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
   332  				rnd := rand.New(rand.NewSource(seed))
   333  				return v.Rand(rnd, x)
   334  			}, v.Int, x.Int)
   335  		},
   336  		"Rem": func(v, x bigInt, y notZeroInt) bool {
   337  			return checkAliasingTwoArgs(t, (*big.Int).Rem, v.Int, x.Int, y.Int)
   338  		},
   339  		"Rsh": func(v, x bigInt, n smallUint) bool {
   340  			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
   341  				return v.Rsh(x, n.uint)
   342  			}, v.Int, x.Int)
   343  		},
   344  		"Set": func(v, x bigInt) bool {
   345  			return checkAliasingOneArg(t, (*big.Int).Set, v.Int, x.Int)
   346  		},
   347  		"SetBit": func(v, x bigInt, i smallUint, b zeroOrOne) bool {
   348  			return checkAliasingOneArg(t, func(v, x *big.Int) *big.Int {
   349  				return v.SetBit(x, int(i.uint), b.uint)
   350  			}, v.Int, x.Int)
   351  		},
   352  		"Sqrt": func(v bigInt, x positiveInt) bool {
   353  			return checkAliasingOneArg(t, (*big.Int).Sqrt, v.Int, x.Int)
   354  		},
   355  		"Sub": func(v, x, y bigInt) bool {
   356  			return checkAliasingTwoArgs(t, (*big.Int).Sub, v.Int, x.Int, y.Int)
   357  		},
   358  		"Xor": func(v, x, y bigInt) bool {
   359  			return checkAliasingTwoArgs(t, (*big.Int).Xor, v.Int, x.Int, y.Int)
   360  		},
   361  	} {
   362  		t.Run(name, func(t *testing.T) {
   363  			scale := 1.0
   364  			switch name {
   365  			case "ModInverse", "GCD-Y", "GCD-X":
   366  				scale /= 5
   367  			case "Rand":
   368  				scale /= 10
   369  			case "Exp-XZ", "Exp-XY", "Exp-YZ":
   370  				scale /= 50
   371  			case "ModSqrt":
   372  				scale /= 500
   373  			}
   374  			if err := quick.Check(f, &quick.Config{
   375  				MaxCountScale: scale,
   376  			}); err != nil {
   377  				t.Error(err)
   378  			}
   379  		})
   380  	}
   381  
   382  	t.Run("Issue72043a", func(t *testing.T) {
   383  		v := new(big.Int).SetBytes([]byte{0x4b, 0xd2, 0x7a, 0x6c, 0xb3, 0x16, 0x5a, 0xf3, 0xa0, 0x45, 0x2b, 0xbe, 0x38, 0xba, 0x18, 0xb8, 0x70, 0xbb, 0xde, 0xd2, 0x20, 0xe9, 0xb9, 0x9d, 0x1d, 0xc6, 0x3e, 0xa, 0xa5, 0x60, 0x11, 0xcc, 0xb8, 0xff, 0x8e, 0x62})
   384  		x := new(big.Int).SetBytes([]byte{0xb, 0x40, 0x70, 0x8b, 0x64, 0x78, 0x29, 0x9e, 0xd0})
   385  		y := new(big.Int).SetBytes([]byte{0x1})
   386  		z := new(big.Int).SetBytes([]byte{0xe, 0x91, 0x4d, 0xaa, 0x69, 0x60, 0x51, 0x42, 0x9, 0xa1, 0xf6, 0xfa, 0x5, 0x97, 0x1c, 0x5e, 0x18, 0xaa, 0x91, 0x87, 0x1f, 0xe4, 0x70, 0x84, 0x54, 0x97, 0x3a, 0xc9, 0xe1, 0x92, 0xd4, 0xf3, 0xdf, 0x79, 0x90, 0x18, 0xdd, 0xdf, 0x19, 0x44, 0xf3, 0xf, 0x9d, 0xa6, 0xf, 0xd9})
   387  		v.Exp(x, y, z)
   388  	})
   389  
   390  	t.Run("Issue72043b", func(t *testing.T) {
   391  		v := new(big.Int).SetBytes([]byte{0x1, 0x6b, 0x8a, 0x26, 0x2, 0x1d, 0x3b, 0x4, 0x8d, 0x81, 0x85, 0xdb, 0x78, 0x4e, 0x81, 0xb7, 0xa7, 0xc0, 0x6e, 0xe7, 0xa0, 0xa, 0x54, 0x39, 0x3e, 0xa8, 0xb1, 0xe0, 0x0, 0xdb, 0x5a, 0x45, 0xde, 0xbf, 0xe2, 0xc8, 0x4d, 0x2b, 0x80, 0x65, 0x73, 0x5d, 0x6d, 0x65, 0x40, 0x50, 0xd4, 0x8})
   392  		x := new(big.Int).SetBytes([]byte{0x7, 0xd6, 0x79, 0xc5, 0x30, 0xc2, 0x1f, 0x39, 0x5e, 0x3d, 0xd2, 0x52, 0xc6, 0xfb, 0xa7, 0xe2, 0x8a, 0x37, 0xdd})
   393  		y := new(big.Int).SetBytes([]byte{0x1})
   394  		z := new(big.Int).SetBytes([]byte{0x1c, 0x44, 0xba, 0x75, 0xfa, 0xe5, 0x3a, 0x56, 0xc0, 0x94, 0xa, 0x1e, 0x8f, 0xbd, 0xad, 0xdb, 0x17, 0xb8, 0x2b, 0x46, 0xf8, 0x69, 0xc1, 0x54, 0x25, 0x68, 0x53, 0xb5, 0xd5, 0x89, 0x6c, 0x16, 0xef, 0xf2, 0x83, 0x3e, 0x55, 0xa7, 0x54, 0x32, 0xbd, 0xa7, 0x70, 0x13, 0xa4, 0xfa})
   395  		v.Exp(x, y, z)
   396  	})
   397  
   398  	t.Run("Issue72043c", func(t *testing.T) {
   399  		v := new(big.Int).SetBytes([]byte{0x2, 0x2a, 0xfc, 0x65, 0xc2, 0x66, 0xb1, 0x63, 0x56, 0xaf, 0x5c, 0x6, 0x4a, 0x19, 0x82, 0x6b, 0xaa, 0x90, 0x57, 0xd9, 0xd0, 0x3e, 0x83, 0xc8, 0x2a, 0x85, 0xe0})
   400  		x := new(big.Int).SetBytes([]byte{0x8, 0x6f, 0xc5, 0x74, 0x83, 0x56, 0xa5, 0x6e, 0xfe, 0x7b, 0x32, 0xfb, 0x69, 0x4, 0x3, 0x51, 0xf5, 0x2c, 0x41, 0x7, 0xf7, 0xbb, 0x89, 0x8e})
   401  		y := new(big.Int).SetBytes([]byte{0x1})
   402  		z := new(big.Int).SetBytes([]byte{0x34, 0xe1, 0x5f, 0xd0, 0xa7, 0xf8, 0x34, 0x7c, 0x3c, 0x63, 0x82, 0x1e, 0xc3, 0x84, 0x9f, 0xa, 0x70, 0x22, 0xd3, 0xc8, 0x24, 0x64, 0x2b, 0xd7, 0x59, 0x20, 0xf2, 0xdd, 0xb5, 0xb2, 0xfa, 0x11, 0x2e, 0x98, 0x95})
   403  		v.Exp(x, y, z)
   404  	})
   405  }
   406
View as plain text