Source file src/math/big/arith_test.go

     1  // Copyright 2009 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  // This file defines tests of consistent behavior between assembly and Go versions of basic operators,
     6  // as well as tests of pure Go implementations.
     7  
     8  package big
     9  
    10  import (
    11  	"fmt"
    12  	"internal/testenv"
    13  	"iter"
    14  	"math/bits"
    15  	"math/rand/v2"
    16  	"slices"
    17  	"strings"
    18  	"testing"
    19  )
    20  
    21  var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
    22  
    23  var words4 = []Word{0, 1, _M - 1, _M}
    24  var words2 = []Word{0, _M}
    25  var muls = []Word{0, 1, 2, 3, 4, 5, _M / 4, _M / 2, _M - 3, _M - 2, _M - 1, _M}
    26  var adds = []Word{0, 1, _M - 1, _M}
    27  var shifts = []uint{1, 2, 3, _W/4 - 1, _W / 4, _W/4 + 1, _W/2 - 1, _W / 2, _W/2 + 1, _W - 3, _W - 2, _W - 1}
    28  
    29  func TestAddVV(t *testing.T)      { testVV(t, "addVV", addVV, addVV_g) }
    30  func TestSubVV(t *testing.T)      { testVV(t, "subVV", subVV, subVV_g) }
    31  func TestAddVW(t *testing.T)      { testVW(t, "addVW", addVW, addVW_ref, words4) }
    32  func TestSubVW(t *testing.T)      { testVW(t, "subVW", subVW, subVW_ref, words4) }
    33  func TestLshVU(t *testing.T)      { testVU(t, "lshVU", lshVU, lshVU_g, shifts) }
    34  func TestRshVU(t *testing.T)      { testVU(t, "rshVU", rshVU, rshVU_g, shifts) }
    35  func TestMulAddVWW(t *testing.T)  { testVWW(t, "mulAddVWW", mulAddVWW, mulAddVWW_g, muls) }
    36  func TestAddMulVVWW(t *testing.T) { testVVWW(t, "addMulVVWW", addMulVVWW, addMulVVWW_g, muls, adds) }
    37  
    38  // Note: It would be nice to avoid all the duplication of these test variants,
    39  // but the only obvious way is to use reflection. These tests are already
    40  // pretty expensive, and hitting them with reflect call overhead would
    41  // reduce the amount of exhaustive testing it's reasonable to do, so instead
    42  // we put up with the duplication.
    43  
    44  func testVV(t *testing.T, name string, fn, ref func(z, x, y []Word) (c Word)) {
    45  	for size := range 100 {
    46  		xx := make([]Word, 1+size+1)
    47  		yy := make([]Word, 1+size+1)
    48  		zz := make([]Word, 1+size+1)
    49  		words := words4
    50  		if size > 5 {
    51  			words = words2
    52  		}
    53  		if size > 10 {
    54  			words = nil // random
    55  		}
    56  		for x := range nats(words, size) {
    57  			for y := range nats(words, size) {
    58  				wantZ := make([]Word, size)
    59  				wantC := ref(wantZ, x, y)
    60  
    61  				for _, inplace := range []bool{false, true} {
    62  					name := name
    63  					if inplace {
    64  						name = "in-place " + name
    65  					}
    66  					setSlice(xx, 1, x)
    67  					setSlice(yy, 2, y)
    68  					zz := zz
    69  					if inplace {
    70  						zz = xx
    71  					} else {
    72  						for i := range zz {
    73  							zz[i] = 0x9876
    74  						}
    75  					}
    76  					setSlice(zz, 3, nil)
    77  					c := fn(zz[1:1+size], xx[1:1+size], yy[1:1+size])
    78  					if !slices.Equal(zz[1:1+size], wantZ) || c != wantC {
    79  						t.Errorf("%s(%#x, %#x) = %#x, %#x, want %#x, %#x", name, x, y, zz[1:1+size], c, wantZ, wantC)
    80  					}
    81  					if !inplace {
    82  						checkSlice(t, name, "x", xx, 1, x)
    83  					}
    84  					checkSlice(t, name, "y", yy, 2, y)
    85  					checkSlice(t, name, "z", zz, 3, nil)
    86  					if t.Failed() {
    87  						t.FailNow()
    88  					}
    89  				}
    90  			}
    91  		}
    92  	}
    93  }
    94  
    95  func testVV2(t *testing.T, name string, fn, ref func(z1, z2, x, y []Word) (c1, c2 Word)) {
    96  	for size := range 100 {
    97  		xx := make([]Word, 1+size+1)
    98  		yy := make([]Word, 1+size+1)
    99  		zz1 := make([]Word, 1+size+1)
   100  		zz2 := make([]Word, 1+size+1)
   101  		words := words4
   102  		if size > 5 {
   103  			words = words2
   104  		}
   105  		if size > 10 {
   106  			words = nil // random
   107  		}
   108  		for x := range nats(words, size) {
   109  			for y := range nats(words, size) {
   110  				wantZ1 := make([]Word, size)
   111  				wantZ2 := make([]Word, size)
   112  				wantC1, wantC2 := ref(wantZ1, wantZ2, x, y)
   113  
   114  				for _, inplace := range []bool{false, true} {
   115  					name := name
   116  					if inplace {
   117  						name = "in-place " + name
   118  					}
   119  					setSlice(xx, 1, x)
   120  					setSlice(yy, 2, y)
   121  					zz1 := zz1
   122  					zz2 := zz2
   123  					if inplace {
   124  						zz1 = xx
   125  						zz2 = yy
   126  					} else {
   127  						for i := range zz1 {
   128  							zz1[i] = 0x9876
   129  						}
   130  						for i := range zz2 {
   131  							zz2[i] = 0x8765
   132  						}
   133  					}
   134  					setSlice(zz1, 3, nil)
   135  					setSlice(zz2, 4, nil)
   136  					c1, c2 := fn(zz1[1:1+size], zz2[1:1+size], xx[1:1+size], yy[1:1+size])
   137  					if !slices.Equal(zz1[1:1+size], wantZ1) || !slices.Equal(zz2[1:1+size], wantZ2) || c1 != wantC1 || c2 != wantC2 {
   138  						t.Errorf("%s(%#x, %#x) = %#x, %#x, %#x, %#x, want %#x, %#x, %#x, %#x", name, x, y, zz1[1:1+size], zz2[1:1+size], c1, c2, wantZ1, wantZ2, wantC1, wantC2)
   139  					}
   140  					if !inplace {
   141  						checkSlice(t, name, "x", xx, 1, x)
   142  						checkSlice(t, name, "y", yy, 2, y)
   143  					}
   144  					checkSlice(t, name, "z1", zz1, 3, nil)
   145  					checkSlice(t, name, "z2", zz2, 4, nil)
   146  					if t.Failed() {
   147  						t.FailNow()
   148  					}
   149  				}
   150  			}
   151  		}
   152  	}
   153  }
   154  
   155  func testVW(t *testing.T, name string, fn, ref func(z, x []Word, w Word) (c Word), ws []Word) {
   156  	const (
   157  		magic0 = 0x123450
   158  		magic1 = 0x543210
   159  	)
   160  
   161  	for size := range 100 {
   162  		xx := make([]Word, 1+size+1)
   163  		zz := make([]Word, 1+size+1)
   164  		words := words4
   165  		if size > 5 {
   166  			words = words2
   167  		}
   168  		if size > 10 {
   169  			words = nil // random
   170  		}
   171  		for x := range nats(words, size) {
   172  			for _, w := range ws {
   173  				wantZ := make([]Word, size)
   174  				wantC := ref(wantZ, x, w)
   175  
   176  				copy(xx[1:], x)
   177  				for _, inplace := range []bool{false, true} {
   178  					name := name
   179  					if inplace {
   180  						name = "in-place " + name
   181  					}
   182  					setSlice(xx, 1, x)
   183  					zz := zz
   184  					if inplace {
   185  						zz = xx
   186  					} else {
   187  						for i := range zz {
   188  							zz[i] = 0x9876
   189  						}
   190  					}
   191  					setSlice(zz, 2, nil)
   192  					c := fn(zz[1:1+size], xx[1:1+size], w)
   193  					if !slices.Equal(zz[1:1+size], wantZ) || c != wantC {
   194  						t.Errorf("%s(%#x, %#x) = %#x, %#x, want %#x, %#x", name, x, w, zz[1:1+size], c, wantZ, wantC)
   195  					}
   196  					if !inplace {
   197  						checkSlice(t, name, "x", xx, 1, x)
   198  					}
   199  					checkSlice(t, name, "z", zz, 2, nil)
   200  					if t.Failed() {
   201  						t.FailNow()
   202  					}
   203  				}
   204  			}
   205  		}
   206  	}
   207  }
   208  
   209  func testVU(t *testing.T, name string, fn, ref func(z, x []Word, y uint) (c Word), ys []uint) {
   210  	wys := make([]Word, len(ys))
   211  	for i, y := range ys {
   212  		wys[i] = Word(y)
   213  	}
   214  	testVW(t, name,
   215  		func(z, x []Word, y Word) Word { return fn(z, x, uint(y)) },
   216  		func(z, x []Word, y Word) Word { return ref(z, x, uint(y)) },
   217  		wys)
   218  }
   219  
   220  func testVWW(t *testing.T, name string, fn, ref func(z, x []Word, y, r Word) (c Word), ys []Word) {
   221  	const (
   222  		magic0 = 0x123450
   223  		magic1 = 0x543210
   224  	)
   225  
   226  	for size := range 100 {
   227  		xx := make([]Word, 1+size+1)
   228  		zz := make([]Word, 1+size+1)
   229  		words := words4
   230  		if size > 5 {
   231  			words = words2
   232  		}
   233  		if size > 10 {
   234  			words = nil // random
   235  		}
   236  		for x := range nats(words, size) {
   237  			for _, y := range ys {
   238  				for _, r := range ys {
   239  					wantZ := make([]Word, size)
   240  					wantC := ref(wantZ, x, y, r)
   241  
   242  					copy(xx[1:], x)
   243  					for _, inplace := range []bool{false, true} {
   244  						name := name
   245  						if inplace {
   246  							name = "in-place " + name
   247  						}
   248  						setSlice(xx, 1, x)
   249  						zz := zz
   250  						if inplace {
   251  							zz = xx
   252  						} else {
   253  							for i := range zz {
   254  								zz[i] = 0x9876
   255  							}
   256  						}
   257  						setSlice(zz, 2, nil)
   258  						c := fn(zz[1:1+size], xx[1:1+size], y, r)
   259  						if !slices.Equal(zz[1:1+size], wantZ) || c != wantC {
   260  							t.Errorf("%s(%#x, %#x, %#x) = %#x, %#x, want %#x, %#x", name, x, y, r, zz[1:1+size], c, wantZ, wantC)
   261  						}
   262  						if !inplace {
   263  							checkSlice(t, name, "x", xx, 1, x)
   264  						}
   265  						checkSlice(t, name, "z", zz, 2, nil)
   266  						if t.Failed() {
   267  							t.FailNow()
   268  						}
   269  					}
   270  				}
   271  			}
   272  		}
   273  	}
   274  }
   275  
   276  func testVVU(t *testing.T, name string, fn, ref func(z, x, y []Word, s uint) (c Word), shifts []uint) {
   277  	for size := range 100 {
   278  		xx := make([]Word, 1+size+1)
   279  		yy := make([]Word, 1+size+1)
   280  		zz := make([]Word, 1+size+1)
   281  		words := words4
   282  		if size > 5 {
   283  			words = words2
   284  		}
   285  		if size > 10 {
   286  			words = nil // random
   287  		}
   288  		for x := range nats(words, size) {
   289  			for y := range nats(words, size) {
   290  				for _, s := range shifts {
   291  					wantZ := make([]Word, size)
   292  					wantC := ref(wantZ, x, y, s)
   293  
   294  					for _, inplace := range []bool{false, true} {
   295  						name := name
   296  						if inplace {
   297  							name = "in-place " + name
   298  						}
   299  						setSlice(xx, 1, x)
   300  						setSlice(yy, 2, y)
   301  						zz := zz
   302  						if inplace {
   303  							zz = xx
   304  						} else {
   305  							for i := range zz {
   306  								zz[i] = 0x9876
   307  							}
   308  						}
   309  						setSlice(zz, 3, nil)
   310  						c := fn(zz[1:1+size], xx[1:1+size], yy[1:1+size], s)
   311  						if !slices.Equal(zz[1:1+size], wantZ) || c != wantC {
   312  							t.Errorf("%s(%#x, %#x, %#x) = %#x, %#x, want %#x, %#x", name, x, y, s, zz[1:1+size], c, wantZ, wantC)
   313  						}
   314  						if !inplace {
   315  							checkSlice(t, name, "x", xx, 1, x)
   316  						}
   317  						checkSlice(t, name, "y", yy, 2, y)
   318  						checkSlice(t, name, "z", zz, 3, nil)
   319  						if t.Failed() {
   320  							t.FailNow()
   321  						}
   322  					}
   323  				}
   324  			}
   325  		}
   326  	}
   327  }
   328  
   329  func testVVWW(t *testing.T, name string, fn, ref func(z, x, y []Word, m, a Word) (c Word), ms, as []Word) {
   330  	for size := range 100 {
   331  		zz := make([]Word, 1+size+1)
   332  		xx := make([]Word, 1+size+1)
   333  		yy := make([]Word, 1+size+1)
   334  		words := words4
   335  		if size > 3 {
   336  			words = words2
   337  		}
   338  		if size > 7 {
   339  			words = nil // random
   340  		}
   341  		for x := range nats(words, size) {
   342  			for y := range nats(words, size) {
   343  				for _, m := range ms {
   344  					for _, a := range as {
   345  						wantZ := make([]Word, size)
   346  						wantC := ref(wantZ, x, y, m, a)
   347  
   348  						for _, inplace := range []bool{false, true} {
   349  							name := name
   350  							if inplace {
   351  								name = "in-place " + name
   352  							}
   353  							setSlice(xx, 1, x)
   354  							setSlice(yy, 2, y)
   355  							zz := zz
   356  							if inplace {
   357  								zz = xx
   358  							} else {
   359  								for i := range zz {
   360  									zz[i] = 0x9876
   361  								}
   362  							}
   363  							setSlice(zz, 3, nil)
   364  							c := fn(zz[1:1+size], xx[1:1+size], yy[1:1+size], m, a)
   365  							if !slices.Equal(zz[1:1+size], wantZ) || c != wantC {
   366  								t.Errorf("%s(%#x, %#x, %#x, %#x) = %#x, %#x, want %#x, %#x", name, x, y, m, a, zz[1:1+size], c, wantZ, wantC)
   367  							}
   368  							if !inplace {
   369  								checkSlice(t, name, "x", xx, 1, x)
   370  							}
   371  							checkSlice(t, name, "y", yy, 2, y)
   372  							checkSlice(t, name, "z", zz, 3, nil)
   373  							if t.Failed() {
   374  								t.FailNow()
   375  							}
   376  						}
   377  					}
   378  				}
   379  			}
   380  		}
   381  	}
   382  }
   383  
   384  const (
   385  	magic0 = 0x123450
   386  	magic1 = 0x543210
   387  )
   388  
   389  // setSlice sets x[1:len(x)-1] to orig, leaving magic values in x[0] and x[len(x)-1]
   390  // so that we can tell if routines accidentally write before or after the data.
   391  func setSlice(x []Word, id Word, orig []Word) {
   392  	x[0] = magic0 + id
   393  	copy(x[1:len(x)-1], orig)
   394  	x[len(x)-1] = magic1 + id
   395  }
   396  
   397  // checkSlice checks that the magic values left by setSlices are still there.
   398  // If orig != nil, it also checks that the actual data in x is unmodified since setSlice.
   399  func checkSlice(t *testing.T, name, val string, x []Word, id Word, orig []Word) {
   400  	if x[0] != magic0+id {
   401  		t.Errorf("%s smashed %s[-1]", name, val)
   402  	}
   403  	if x[len(x)-1] != magic1+id {
   404  		t.Errorf("%s smashed %s[len(%s)]", name, val, val)
   405  	}
   406  	if orig != nil && !slices.Equal(x[1:len(x)-1], orig) {
   407  		t.Errorf("%s smashed %s: have %d, want %d", name, val, x[1:len(x)-1], orig)
   408  	}
   409  }
   410  
   411  // nats returns a sequence of interesting nats of the given size:
   412  //
   413  //   - all 0
   414  //   - all ^0
   415  //   - all possible combinations of words
   416  //   - ten random values
   417  func nats(words []Word, size int) iter.Seq[[]Word] {
   418  	return func(yield func([]Word) bool) {
   419  		if size == 0 {
   420  			yield(nil)
   421  			return
   422  		}
   423  		w := make([]Word, size)
   424  
   425  		// all 0
   426  		for i := range w {
   427  			w[i] = 0
   428  		}
   429  		if !yield(w) {
   430  			return
   431  		}
   432  
   433  		// all ^0
   434  		for i := range w {
   435  			w[i] = _M
   436  		}
   437  		if !yield(w) {
   438  			return
   439  		}
   440  
   441  		// all possible combinations of words
   442  		var generate func(int) bool
   443  		generate = func(i int) bool {
   444  			if i >= len(w) {
   445  				return yield(w)
   446  			}
   447  			for _, w[i] = range words {
   448  				if !generate(i + 1) {
   449  					return false
   450  				}
   451  			}
   452  			return true
   453  		}
   454  		if !generate(0) {
   455  			return
   456  		}
   457  
   458  		// ten random values
   459  		for range 10 {
   460  			for i := range w {
   461  				w[i] = Word(rnd.Uint())
   462  			}
   463  			if !yield(w) {
   464  				return
   465  			}
   466  		}
   467  	}
   468  }
   469  
   470  // Always the same seed for reproducible results.
   471  var rnd = rand.New(rand.NewPCG(1, 2))
   472  
   473  func rndW() Word {
   474  	return Word(rnd.Uint())
   475  }
   476  
   477  func rndV(n int) []Word {
   478  	v := make([]Word, n)
   479  	for i := range v {
   480  		v[i] = rndW()
   481  	}
   482  	return v
   483  }
   484  
   485  // Construct a vector comprising the same word, usually '0' or 'maximum uint'
   486  func makeWordVec(e Word, n int) []Word {
   487  	v := make([]Word, n)
   488  	for i := range v {
   489  		v[i] = e
   490  	}
   491  	return v
   492  }
   493  
   494  type argVU struct {
   495  	d  []Word // d is a Word slice, the input parameters x and z come from this array.
   496  	l  uint   // l is the length of the input parameters x and z.
   497  	xp uint   // xp is the starting position of the input parameter x, x := d[xp:xp+l].
   498  	zp uint   // zp is the starting position of the input parameter z, z := d[zp:zp+l].
   499  	s  uint   // s is the shift number.
   500  	r  []Word // r is the expected output result z.
   501  	c  Word   // c is the expected return value.
   502  	m  string // message.
   503  }
   504  
   505  var arglshVUIn = []Word{1, 2, 4, 8, 16, 32, 64, 0, 0, 0}
   506  var arglshVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
   507  var arglshVUr1 = []Word{2, 4, 8, 16, 32, 64, 128}
   508  var arglshVUrWm1 = []Word{1 << (_W - 1), 0, 1, 2, 4, 8, 16}
   509  
   510  var arglshVU = []argVU{
   511  	// test cases for lshVU
   512  	{[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0}, 7, 0, 0, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "complete overlap of lshVU"},
   513  	{[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0}, 7, 0, 3, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "partial overlap by half of lshVU"},
   514  	{[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0, 0, 0, 0}, 7, 0, 6, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "partial overlap by 1 Word of lshVU"},
   515  	{[]Word{1, _M, _M, _M, _M, _M, 3 << (_W - 2), 0, 0, 0, 0, 0, 0, 0, 0}, 7, 0, 7, 1, []Word{2, _M - 1, _M, _M, _M, _M, 1<<(_W-1) + 1}, 1, "no overlap of lshVU"},
   516  	// additional test cases with shift values of 1 and (_W-1)
   517  	{arglshVUIn, 7, 0, 0, 1, arglshVUr1, 0, "complete overlap of lshVU and shift of 1"},
   518  	{arglshVUIn, 7, 0, 0, _W - 1, arglshVUrWm1, 32, "complete overlap of lshVU and shift of _W - 1"},
   519  	{arglshVUIn, 7, 0, 1, 1, arglshVUr1, 0, "partial overlap by 6 Words of lshVU and shift of 1"},
   520  	{arglshVUIn, 7, 0, 1, _W - 1, arglshVUrWm1, 32, "partial overlap by 6 Words of lshVU and shift of _W - 1"},
   521  	{arglshVUIn, 7, 0, 2, 1, arglshVUr1, 0, "partial overlap by 5 Words of lshVU and shift of 1"},
   522  	{arglshVUIn, 7, 0, 2, _W - 1, arglshVUrWm1, 32, "partial overlap by 5 Words of lshVU abd shift of _W - 1"},
   523  	{arglshVUIn, 7, 0, 3, 1, arglshVUr1, 0, "partial overlap by 4 Words of lshVU and shift of 1"},
   524  	{arglshVUIn, 7, 0, 3, _W - 1, arglshVUrWm1, 32, "partial overlap by 4 Words of lshVU and shift of _W - 1"},
   525  }
   526  
   527  var argrshVUIn = []Word{0, 0, 0, 1, 2, 4, 8, 16, 32, 64}
   528  var argrshVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
   529  var argrshVUr1 = []Word{0, 1, 2, 4, 8, 16, 32}
   530  var argrshVUrWm1 = []Word{4, 8, 16, 32, 64, 128, 0}
   531  
   532  var argrshVU = []argVU{
   533  	// test cases for rshVU
   534  	{[]Word{0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 1, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "complete overlap of rshVU"},
   535  	{[]Word{0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 4, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "partial overlap by half of rshVU"},
   536  	{[]Word{0, 0, 0, 0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 7, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "partial overlap by 1 Word of rshVU"},
   537  	{[]Word{0, 0, 0, 0, 0, 0, 0, 0, 3, _M, _M, _M, _M, _M, 1 << (_W - 1)}, 7, 8, 1, 1, []Word{1<<(_W-1) + 1, _M, _M, _M, _M, _M >> 1, 1 << (_W - 2)}, 1 << (_W - 1), "no overlap of rshVU"},
   538  	// additional test cases with shift values of 0, 1 and (_W-1)
   539  	{argrshVUIn, 7, 3, 3, 1, argrshVUr1, 1 << (_W - 1), "complete overlap of rshVU and shift of 1"},
   540  	{argrshVUIn, 7, 3, 3, _W - 1, argrshVUrWm1, 2, "complete overlap of rshVU and shift of _W - 1"},
   541  	{argrshVUIn, 7, 3, 2, 1, argrshVUr1, 1 << (_W - 1), "partial overlap by 6 Words of rshVU and shift of 1"},
   542  	{argrshVUIn, 7, 3, 2, _W - 1, argrshVUrWm1, 2, "partial overlap by 6 Words of rshVU and shift of _W - 1"},
   543  	{argrshVUIn, 7, 3, 1, 1, argrshVUr1, 1 << (_W - 1), "partial overlap by 5 Words of rshVU and shift of 1"},
   544  	{argrshVUIn, 7, 3, 1, _W - 1, argrshVUrWm1, 2, "partial overlap by 5 Words of rshVU and shift of _W - 1"},
   545  	{argrshVUIn, 7, 3, 0, 1, argrshVUr1, 1 << (_W - 1), "partial overlap by 4 Words of rshVU and shift of 1"},
   546  	{argrshVUIn, 7, 3, 0, _W - 1, argrshVUrWm1, 2, "partial overlap by 4 Words of rshVU and shift of _W - 1"},
   547  }
   548  
   549  func testShiftFunc(t *testing.T, f func(z, x []Word, s uint) Word, a argVU) {
   550  	// work on copy of a.d to preserve the original data.
   551  	b := make([]Word, len(a.d))
   552  	copy(b, a.d)
   553  	z := b[a.zp : a.zp+a.l]
   554  	x := b[a.xp : a.xp+a.l]
   555  	c := f(z, x, a.s)
   556  	for i, zi := range z {
   557  		if zi != a.r[i] {
   558  			t.Errorf("d := %v, %s (d[%d:%d], d[%d:%d], %d)\n\tgot z[%d] = %#x; want %#x", a.d, a.m, a.zp, a.zp+a.l, a.xp, a.xp+a.l, a.s, i, zi, a.r[i])
   559  			break
   560  		}
   561  	}
   562  	if c != a.c {
   563  		t.Errorf("d := %v, %s (d[%d:%d], d[%d:%d], %d)\n\tgot c = %#x; want %#x", a.d, a.m, a.zp, a.zp+a.l, a.xp, a.xp+a.l, a.s, c, a.c)
   564  	}
   565  }
   566  
   567  func TestShiftOverlap(t *testing.T) {
   568  	for _, a := range arglshVU {
   569  		arg := a
   570  		testShiftFunc(t, lshVU, arg)
   571  	}
   572  
   573  	for _, a := range argrshVU {
   574  		arg := a
   575  		testShiftFunc(t, rshVU, arg)
   576  	}
   577  }
   578  
   579  func TestIssue31084(t *testing.T) {
   580  	stk := getStack()
   581  	defer stk.free()
   582  
   583  	// compute 10^n via 5^n << n.
   584  	const n = 165
   585  	p := nat(nil).expNN(stk, nat{5}, nat{n}, nil, false)
   586  	p = p.lsh(p, n)
   587  	got := string(p.utoa(10))
   588  	want := "1" + strings.Repeat("0", n)
   589  	if got != want {
   590  		t.Errorf("lsh(%v, %v)\n\tgot  %s\n\twant %s", p, n, got, want)
   591  	}
   592  }
   593  
   594  const issue42838Value = "159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625"
   595  
   596  func TestIssue42838(t *testing.T) {
   597  	const s = 192
   598  	z, _, _, _ := nat(nil).scan(strings.NewReader(issue42838Value), 0, false)
   599  	z = z.lsh(z, s)
   600  	got := string(z.utoa(10))
   601  	want := "1" + strings.Repeat("0", s)
   602  	if got != want {
   603  		t.Errorf("lsh(%v, %v)\n\tgot  %s\n\twant %s", z, s, got, want)
   604  	}
   605  }
   606  
   607  type funVWW func(z, x []Word, y, r Word) (c Word)
   608  type argVWW struct {
   609  	z, x nat
   610  	y, r Word
   611  	c    Word
   612  }
   613  
   614  var prodVWW = []argVWW{
   615  	{},
   616  	{nat{0}, nat{0}, 0, 0, 0},
   617  	{nat{991}, nat{0}, 0, 991, 0},
   618  	{nat{0}, nat{_M}, 0, 0, 0},
   619  	{nat{991}, nat{_M}, 0, 991, 0},
   620  	{nat{0}, nat{0}, _M, 0, 0},
   621  	{nat{991}, nat{0}, _M, 991, 0},
   622  	{nat{1}, nat{1}, 1, 0, 0},
   623  	{nat{992}, nat{1}, 1, 991, 0},
   624  	{nat{22793}, nat{991}, 23, 0, 0},
   625  	{nat{22800}, nat{991}, 23, 7, 0},
   626  	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
   627  	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
   628  	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
   629  	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
   630  	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
   631  	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
   632  	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
   633  	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
   634  	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
   635  	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   636  	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
   637  	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   638  }
   639  
   640  func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
   641  	z := make(nat, len(a.z))
   642  	c := f(z, a.x, a.y, a.r)
   643  	for i, zi := range z {
   644  		if zi != a.z[i] {
   645  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   646  			break
   647  		}
   648  	}
   649  	if c != a.c {
   650  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   651  	}
   652  }
   653  
   654  // TODO(gri) mulAddVWW and divWVW are symmetric operations but
   655  // their signature is not symmetric. Try to unify.
   656  
   657  type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
   658  type argWVW struct {
   659  	z  nat
   660  	xn Word
   661  	x  nat
   662  	y  Word
   663  	r  Word
   664  }
   665  
   666  func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
   667  	z := make(nat, len(a.z))
   668  	r := f(z, a.xn, a.x, a.y)
   669  	if !slices.Equal(z, a.z) || r != a.r {
   670  		t.Errorf("%s%+v\nhave %v, %v\nwant %v, %v", msg, a, z, r, a.z, a.r)
   671  	} else {
   672  		t.Logf("%s%+v\ngood %v, %v", msg, a, z, r)
   673  	}
   674  }
   675  
   676  func TestFunVWW(t *testing.T) {
   677  	for _, a := range prodVWW {
   678  		arg := a
   679  		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
   680  		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
   681  
   682  		if a.y != 0 && a.r < a.y {
   683  			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
   684  			testFunWVW(t, "divWVW", divWVW, arg)
   685  		}
   686  	}
   687  }
   688  
   689  var mulWWTests = []struct {
   690  	x, y Word
   691  	q, r Word
   692  }{
   693  	{_M, _M, _M - 1, 1},
   694  	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
   695  }
   696  
   697  func TestMulWW(t *testing.T) {
   698  	for i, test := range mulWWTests {
   699  		q, r := mulWW(test.x, test.y)
   700  		if q != test.q || r != test.r {
   701  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   702  		}
   703  	}
   704  }
   705  
   706  var mulAddWWWTests = []struct {
   707  	x, y, c Word
   708  	q, r    Word
   709  }{
   710  	// TODO(agl): These will only work on 64-bit platforms.
   711  	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
   712  	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
   713  	{_M, _M, 0, _M - 1, 1},
   714  	{_M, _M, _M, _M, 0},
   715  }
   716  
   717  func TestMulAddWWW(t *testing.T) {
   718  	for i, test := range mulAddWWWTests {
   719  		q, r := mulAddWWW_g(test.x, test.y, test.c)
   720  		if q != test.q || r != test.r {
   721  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   722  		}
   723  	}
   724  }
   725  
   726  var divWWTests = []struct {
   727  	x1, x0, y Word
   728  	q, r      Word
   729  }{
   730  	{_M >> 1, 0, _M, _M >> 1, _M >> 1},
   731  	{_M - (1 << (_W - 2)), _M, 3 << (_W - 2), _M, _M - (1 << (_W - 2))},
   732  }
   733  
   734  const testsNumber = 1 << 16
   735  
   736  func TestDivWW(t *testing.T) {
   737  	i := 0
   738  	for i, test := range divWWTests {
   739  		rec := reciprocalWord(test.y)
   740  		q, r := divWW(test.x1, test.x0, test.y, rec)
   741  		if q != test.q || r != test.r {
   742  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   743  		}
   744  	}
   745  	//random tests
   746  	for ; i < testsNumber; i++ {
   747  		x1 := rndW()
   748  		x0 := rndW()
   749  		y := rndW()
   750  		if x1 >= y {
   751  			continue
   752  		}
   753  		rec := reciprocalWord(y)
   754  		qGot, rGot := divWW(x1, x0, y, rec)
   755  		qWant, rWant := bits.Div(uint(x1), uint(x0), uint(y))
   756  		if uint(qGot) != qWant || uint(rGot) != rWant {
   757  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, qGot, rGot, qWant, rWant)
   758  		}
   759  	}
   760  }
   761  
   762  // benchSizes are the benchmark word sizes.
   763  var benchSizes = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 32, 64, 100, 1000, 10_000, 100_000}
   764  
   765  // A benchFunc is a function to be benchmarked.
   766  // It takes one output buffer and two input buffers,
   767  // but it does not have to use any of them.
   768  type benchFunc func(z, x, y []Word)
   769  
   770  // bench runs benchmarks of fn for a variety of word sizes.
   771  // It adds the given suffix (for example "/impl=go") to the benchmark names it creates,
   772  // after a "/words=N" parameter. Putting words first makes it easier to run
   773  // all benchmarks with a specific word size
   774  // (go test -run=NONE '-bench=V/words=100$')
   775  // even if different benchmarks have different numbers of other parameters.
   776  func bench(b *testing.B, suffix string, fn benchFunc) {
   777  	for _, n := range benchSizes {
   778  		if isRaceBuilder && n > 1e3 {
   779  			continue
   780  		}
   781  		var z, x, y []Word
   782  		b.Run(fmt.Sprintf("words=%d%s", n, suffix), func(b *testing.B) {
   783  			if z == nil {
   784  				z = make([]Word, n)
   785  				x = rndV(n)
   786  				y = rndV(n)
   787  			}
   788  			b.SetBytes(int64(n * _S))
   789  			for b.Loop() {
   790  				fn(z, x, y)
   791  			}
   792  		})
   793  	}
   794  }
   795  
   796  // Benchmark basic I/O and arithmetic processing speed,
   797  // to help estimate the upper bounds on other operations.
   798  
   799  func BenchmarkCopyVV(b *testing.B) { bench(b, "", benchVV(copyVV)) }
   800  
   801  func copyVV(z, x, y []Word) Word {
   802  	copy(z, x)
   803  	return 0
   804  }
   805  
   806  // Note: This benchmark consistently runs faster (even up to 2X faster on MB/s)
   807  // with words=10 and words=100 than larger amounts like words=1000 or words=10000.
   808  // The reason appears to that if you run 100-word addition loops repeatedly,
   809  // they are independent calculations, and the processor speculates/pipelines/whatever
   810  // to such a deep level that it can overlap the repeated loops.
   811  // In contrast, if you run 1000-word or 10000-word loops repeatedly,
   812  // the dependency chains are so long that the processor cannot overlap them.
   813  // If we change arithVV to take the starting value of s and pass in the result
   814  // from the previous arithVV, then even the 10-word or 100-loops become
   815  // a single long dependency chain and the 2X disappears. But since we are
   816  // using BenchmarkArithVV for a given word size to estimate the upper bound
   817  // of, say, BenchmarkAddVV for that same word size, we actually want the
   818  // dependency chain-length variation in BenchmarkArithVV too.
   819  // It's just mysterious to see until you understand what is causing it.
   820  
   821  func BenchmarkArithVV(b *testing.B) { bench(b, "", benchVV(arithVV)) }
   822  
   823  func arithVV(z, x, y []Word) Word {
   824  	var a, b, c, d, e, f, g, h, i, j Word
   825  	if len(z) >= 8 {
   826  		a, b, c, d, e, f, g, h, i, j = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
   827  	}
   828  	if len(z) < 10 {
   829  		// We don't really care about the speed here, but
   830  		// do something so that the small word counts aren't all the same.
   831  		s := Word(0)
   832  		for _, zi := range z {
   833  			s += zi
   834  		}
   835  		return s
   836  	}
   837  	s := Word(0)
   838  	for range len(z) / 10 {
   839  		s += a
   840  		s += b
   841  		s += c
   842  		s += d
   843  		s += e
   844  		s += f
   845  		s += g
   846  		s += h
   847  		s += i
   848  		s += j
   849  	}
   850  	return s
   851  }
   852  
   853  func BenchmarkAddVV(b *testing.B) {
   854  	bench(b, "/impl=asm", benchVV(addVV))
   855  	bench(b, "/impl=go", benchVV(addVV_g))
   856  }
   857  
   858  func BenchmarkSubVV(b *testing.B) {
   859  	bench(b, "/impl=asm", benchVV(subVV))
   860  	bench(b, "/impl=go", benchVV(subVV_g))
   861  }
   862  
   863  func benchVV(fn func(z, x, y []Word) Word) benchFunc {
   864  	return func(z, x, y []Word) { fn(z, x, y) }
   865  }
   866  
   867  func BenchmarkAddVW(b *testing.B) {
   868  	bench(b, "/data=random", benchVW(addVW, 123))
   869  	bench(b, "/data=carry", benchCarryVW(addVW, ^Word(0), 1))
   870  	bench(b, "/data=shortcut", benchShortVW(addVW, 123))
   871  }
   872  
   873  func BenchmarkSubVW(b *testing.B) {
   874  	bench(b, "/data=random", benchVW(subVW, 123))
   875  	bench(b, "/data=carry", benchCarryVW(subVW, 0, 1))
   876  	bench(b, "/data=shortcut", benchShortVW(subVW, 123))
   877  }
   878  
   879  func benchVW(fn func(z, x []Word, w Word) Word, w Word) benchFunc {
   880  	return func(z, x, y []Word) { fn(z, x, w) }
   881  }
   882  
   883  func benchCarryVW(fn func(z, x []Word, w Word) Word, xi, w Word) benchFunc {
   884  	return func(z, x, y []Word) {
   885  		// Fill x with xi the first time we are called with a given x.
   886  		// Otherwise x is random, so checking the first two elements is good enough.
   887  		// Assume this is the warmup, so we don't need to worry about it taking longer.
   888  		if x[0] != w || len(x) >= 2 && x[1] != w {
   889  			for i := range x {
   890  				x[i] = xi
   891  			}
   892  		}
   893  		fn(z, x, w)
   894  	}
   895  }
   896  
   897  func benchShortVW(fn func(z, x []Word, w Word) Word, w Word) benchFunc {
   898  	// Note: calling fn with x not z, to benchmark in-place overwriting.
   899  	return func(z, x, y []Word) { fn(x, x, w) }
   900  }
   901  
   902  func BenchmarkLshVU(b *testing.B) {
   903  	bench(b, "/impl=asm", benchVU(lshVU, 3))
   904  	bench(b, "/impl=go", benchVU(lshVU_g, 3))
   905  }
   906  
   907  func BenchmarkRshVU(b *testing.B) {
   908  	bench(b, "/impl=asm", benchVU(rshVU, 3))
   909  	bench(b, "/impl=go", benchVU(rshVU_g, 3))
   910  }
   911  
   912  func benchVU(fn func(z, x []Word, s uint) Word, s uint) benchFunc {
   913  	return func(z, x, y []Word) { fn(z, x, s) }
   914  }
   915  
   916  func BenchmarkMulAddVWW(b *testing.B) {
   917  	bench(b, "/impl=asm", benchVWW(mulAddVWW, 42, 100))
   918  	bench(b, "/impl=go", benchVWW(mulAddVWW_g, 42, 100))
   919  }
   920  
   921  func benchVWW(fn func(z, x []Word, w1, w2 Word) Word, w1, w2 Word) benchFunc {
   922  	return func(z, x, y []Word) { fn(z, x, w1, w2) }
   923  }
   924  
   925  func BenchmarkAddMulVVWW(b *testing.B) {
   926  	bench(b, "/impl=asm", benchVVWW(addMulVVWW, 42, 100))
   927  	bench(b, "/impl=go", benchVVWW(addMulVVWW_g, 42, 100))
   928  }
   929  
   930  func benchVVWW(fn func(z, x, y []Word, w1, w2 Word) Word, w1, w2 Word) benchFunc {
   931  	return func(z, x, y []Word) { fn(z, x, y, w1, w2) }
   932  }
   933  
   934  func BenchmarkDivWVW(b *testing.B) {
   935  	bench(b, "", benchWVW(divWVW, 100, 200))
   936  }
   937  
   938  func benchWVW(fn func(z []Word, w1 Word, x []Word, w2 Word) Word, w1, w2 Word) benchFunc {
   939  	return func(z, x, y []Word) { fn(z, w1, x, w2) }
   940  }
   941  

View as plain text