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  package big
     6  
     7  import (
     8  	"fmt"
     9  	"internal/testenv"
    10  	"math/bits"
    11  	"math/rand"
    12  	"strings"
    13  	"testing"
    14  )
    15  
    16  var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
    17  
    18  type funVV func(z, x, y []Word) (c Word)
    19  type argVV struct {
    20  	z, x, y nat
    21  	c       Word
    22  }
    23  
    24  var sumVV = []argVV{
    25  	{},
    26  	{nat{0}, nat{0}, nat{0}, 0},
    27  	{nat{1}, nat{1}, nat{0}, 0},
    28  	{nat{0}, nat{_M}, nat{1}, 1},
    29  	{nat{80235}, nat{12345}, nat{67890}, 0},
    30  	{nat{_M - 1}, nat{_M}, nat{_M}, 1},
    31  	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
    32  	{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
    33  	{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
    34  }
    35  
    36  func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
    37  	z := make(nat, len(a.z))
    38  	c := f(z, a.x, a.y)
    39  	for i, zi := range z {
    40  		if zi != a.z[i] {
    41  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
    42  			break
    43  		}
    44  	}
    45  	if c != a.c {
    46  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
    47  	}
    48  }
    49  
    50  func TestFunVV(t *testing.T) {
    51  	for _, a := range sumVV {
    52  		arg := a
    53  		testFunVV(t, "addVV_g", addVV_g, arg)
    54  		testFunVV(t, "addVV", addVV, arg)
    55  
    56  		arg = argVV{a.z, a.y, a.x, a.c}
    57  		testFunVV(t, "addVV_g symmetric", addVV_g, arg)
    58  		testFunVV(t, "addVV symmetric", addVV, arg)
    59  
    60  		arg = argVV{a.x, a.z, a.y, a.c}
    61  		testFunVV(t, "subVV_g", subVV_g, arg)
    62  		testFunVV(t, "subVV", subVV, arg)
    63  
    64  		arg = argVV{a.y, a.z, a.x, a.c}
    65  		testFunVV(t, "subVV_g symmetric", subVV_g, arg)
    66  		testFunVV(t, "subVV symmetric", subVV, arg)
    67  	}
    68  }
    69  
    70  // Always the same seed for reproducible results.
    71  var rnd = rand.New(rand.NewSource(0))
    72  
    73  func rndW() Word {
    74  	return Word(rnd.Int63()<<1 | rnd.Int63n(2))
    75  }
    76  
    77  func rndV(n int) []Word {
    78  	v := make([]Word, n)
    79  	for i := range v {
    80  		v[i] = rndW()
    81  	}
    82  	return v
    83  }
    84  
    85  var benchSizes = []int{1, 2, 3, 4, 5, 1e1, 1e2, 1e3, 1e4, 1e5}
    86  
    87  func BenchmarkAddVV(b *testing.B) {
    88  	for _, n := range benchSizes {
    89  		if isRaceBuilder && n > 1e3 {
    90  			continue
    91  		}
    92  		x := rndV(n)
    93  		y := rndV(n)
    94  		z := make([]Word, n)
    95  		b.Run(fmt.Sprint(n), func(b *testing.B) {
    96  			b.SetBytes(int64(n * _W))
    97  			for i := 0; i < b.N; i++ {
    98  				addVV(z, x, y)
    99  			}
   100  		})
   101  	}
   102  }
   103  
   104  func BenchmarkSubVV(b *testing.B) {
   105  	for _, n := range benchSizes {
   106  		if isRaceBuilder && n > 1e3 {
   107  			continue
   108  		}
   109  		x := rndV(n)
   110  		y := rndV(n)
   111  		z := make([]Word, n)
   112  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   113  			b.SetBytes(int64(n * _W))
   114  			for i := 0; i < b.N; i++ {
   115  				subVV(z, x, y)
   116  			}
   117  		})
   118  	}
   119  }
   120  
   121  type funVW func(z, x []Word, y Word) (c Word)
   122  type argVW struct {
   123  	z, x nat
   124  	y    Word
   125  	c    Word
   126  }
   127  
   128  var sumVW = []argVW{
   129  	{},
   130  	{nil, nil, 2, 2},
   131  	{nat{0}, nat{0}, 0, 0},
   132  	{nat{1}, nat{0}, 1, 0},
   133  	{nat{1}, nat{1}, 0, 0},
   134  	{nat{0}, nat{_M}, 1, 1},
   135  	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
   136  	{nat{585}, nat{314}, 271, 0},
   137  }
   138  
   139  var lshVW = []argVW{
   140  	{},
   141  	{nat{0}, nat{0}, 0, 0},
   142  	{nat{0}, nat{0}, 1, 0},
   143  	{nat{0}, nat{0}, 20, 0},
   144  
   145  	{nat{_M}, nat{_M}, 0, 0},
   146  	{nat{_M << 1 & _M}, nat{_M}, 1, 1},
   147  	{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
   148  
   149  	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   150  	{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
   151  	{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
   152  }
   153  
   154  var rshVW = []argVW{
   155  	{},
   156  	{nat{0}, nat{0}, 0, 0},
   157  	{nat{0}, nat{0}, 1, 0},
   158  	{nat{0}, nat{0}, 20, 0},
   159  
   160  	{nat{_M}, nat{_M}, 0, 0},
   161  	{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
   162  	{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
   163  
   164  	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   165  	{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
   166  	{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
   167  }
   168  
   169  func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
   170  	z := make(nat, len(a.z))
   171  	c := f(z, a.x, a.y)
   172  	for i, zi := range z {
   173  		if zi != a.z[i] {
   174  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   175  			break
   176  		}
   177  	}
   178  	if c != a.c {
   179  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   180  	}
   181  }
   182  
   183  func testFunVWext(t *testing.T, msg string, f funVW, f_g funVW, a argVW) {
   184  	// using the result of addVW_g/subVW_g as golden
   185  	z_g := make(nat, len(a.z))
   186  	c_g := f_g(z_g, a.x, a.y)
   187  	c := f(a.z, a.x, a.y)
   188  
   189  	for i, zi := range a.z {
   190  		if zi != z_g[i] {
   191  			t.Errorf("%s\n\tgot z[%d] = %#x; want %#x", msg, i, zi, z_g[i])
   192  			break
   193  		}
   194  	}
   195  	if c != c_g {
   196  		t.Errorf("%s\n\tgot c = %#x; want %#x", msg, c, c_g)
   197  	}
   198  }
   199  
   200  func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
   201  	return func(z, x []Word, s Word) (c Word) {
   202  		return f(z, x, uint(s))
   203  	}
   204  }
   205  
   206  func TestFunVW(t *testing.T) {
   207  	for _, a := range sumVW {
   208  		arg := a
   209  		testFunVW(t, "addVW_g", addVW_g, arg)
   210  		testFunVW(t, "addVW", addVW, arg)
   211  
   212  		arg = argVW{a.x, a.z, a.y, a.c}
   213  		testFunVW(t, "subVW_g", subVW_g, arg)
   214  		testFunVW(t, "subVW", subVW, arg)
   215  	}
   216  
   217  	shlVW_g := makeFunVW(shlVU_g)
   218  	shlVW := makeFunVW(shlVU)
   219  	for _, a := range lshVW {
   220  		arg := a
   221  		testFunVW(t, "shlVU_g", shlVW_g, arg)
   222  		testFunVW(t, "shlVU", shlVW, arg)
   223  	}
   224  
   225  	shrVW_g := makeFunVW(shrVU_g)
   226  	shrVW := makeFunVW(shrVU)
   227  	for _, a := range rshVW {
   228  		arg := a
   229  		testFunVW(t, "shrVU_g", shrVW_g, arg)
   230  		testFunVW(t, "shrVU", shrVW, arg)
   231  	}
   232  }
   233  
   234  // Construct a vector comprising the same word, usually '0' or 'maximum uint'
   235  func makeWordVec(e Word, n int) []Word {
   236  	v := make([]Word, n)
   237  	for i := range v {
   238  		v[i] = e
   239  	}
   240  	return v
   241  }
   242  
   243  // Extended testing to addVW and subVW using various kinds of input data.
   244  // We utilize the results of addVW_g and subVW_g as golden reference to check
   245  // correctness.
   246  func TestFunVWExt(t *testing.T) {
   247  	// 32 is the current threshold that triggers an optimized version of
   248  	// calculation for large-sized vector, ensure we have sizes around it tested.
   249  	var vwSizes = []int{0, 1, 3, 4, 5, 8, 9, 23, 31, 32, 33, 34, 35, 36, 50, 120}
   250  	for _, n := range vwSizes {
   251  		// vector of random numbers, using the result of addVW_g/subVW_g as golden
   252  		x := rndV(n)
   253  		y := rndW()
   254  		z := make(nat, n)
   255  		arg := argVW{z, x, y, 0}
   256  		testFunVWext(t, "addVW, random inputs", addVW, addVW_g, arg)
   257  		testFunVWext(t, "subVW, random inputs", subVW, subVW_g, arg)
   258  
   259  		// vector of random numbers, but make 'x' and 'z' share storage
   260  		arg = argVW{x, x, y, 0}
   261  		testFunVWext(t, "addVW, random inputs, sharing storage", addVW, addVW_g, arg)
   262  		testFunVWext(t, "subVW, random inputs, sharing storage", subVW, subVW_g, arg)
   263  
   264  		// vector of maximum uint, to force carry flag set in each 'add'
   265  		y = ^Word(0)
   266  		x = makeWordVec(y, n)
   267  		arg = argVW{z, x, y, 0}
   268  		testFunVWext(t, "addVW, vector of max uint", addVW, addVW_g, arg)
   269  
   270  		// vector of '0', to force carry flag set in each 'sub'
   271  		x = makeWordVec(0, n)
   272  		arg = argVW{z, x, 1, 0}
   273  		testFunVWext(t, "subVW, vector of zero", subVW, subVW_g, arg)
   274  	}
   275  }
   276  
   277  type argVU struct {
   278  	d  []Word // d is a Word slice, the input parameters x and z come from this array.
   279  	l  uint   // l is the length of the input parameters x and z.
   280  	xp uint   // xp is the starting position of the input parameter x, x := d[xp:xp+l].
   281  	zp uint   // zp is the starting position of the input parameter z, z := d[zp:zp+l].
   282  	s  uint   // s is the shift number.
   283  	r  []Word // r is the expected output result z.
   284  	c  Word   // c is the expected return value.
   285  	m  string // message.
   286  }
   287  
   288  var argshlVUIn = []Word{1, 2, 4, 8, 16, 32, 64, 0, 0, 0}
   289  var argshlVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
   290  var argshlVUr1 = []Word{2, 4, 8, 16, 32, 64, 128}
   291  var argshlVUrWm1 = []Word{1 << (_W - 1), 0, 1, 2, 4, 8, 16}
   292  
   293  var argshlVU = []argVU{
   294  	// test cases for shlVU
   295  	{[]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 shlVU"},
   296  	{[]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 shlVU"},
   297  	{[]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 shlVU"},
   298  	{[]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 shlVU"},
   299  	// additional test cases with shift values of 0, 1 and (_W-1)
   300  	{argshlVUIn, 7, 0, 0, 0, argshlVUr0, 0, "complete overlap of shlVU and shift of 0"},
   301  	{argshlVUIn, 7, 0, 0, 1, argshlVUr1, 0, "complete overlap of shlVU and shift of 1"},
   302  	{argshlVUIn, 7, 0, 0, _W - 1, argshlVUrWm1, 32, "complete overlap of shlVU and shift of _W - 1"},
   303  	{argshlVUIn, 7, 0, 1, 0, argshlVUr0, 0, "partial overlap by 6 Words of shlVU and shift of 0"},
   304  	{argshlVUIn, 7, 0, 1, 1, argshlVUr1, 0, "partial overlap by 6 Words of shlVU and shift of 1"},
   305  	{argshlVUIn, 7, 0, 1, _W - 1, argshlVUrWm1, 32, "partial overlap by 6 Words of shlVU and shift of _W - 1"},
   306  	{argshlVUIn, 7, 0, 2, 0, argshlVUr0, 0, "partial overlap by 5 Words of shlVU and shift of 0"},
   307  	{argshlVUIn, 7, 0, 2, 1, argshlVUr1, 0, "partial overlap by 5 Words of shlVU and shift of 1"},
   308  	{argshlVUIn, 7, 0, 2, _W - 1, argshlVUrWm1, 32, "partial overlap by 5 Words of shlVU abd shift of _W - 1"},
   309  	{argshlVUIn, 7, 0, 3, 0, argshlVUr0, 0, "partial overlap by 4 Words of shlVU and shift of 0"},
   310  	{argshlVUIn, 7, 0, 3, 1, argshlVUr1, 0, "partial overlap by 4 Words of shlVU and shift of 1"},
   311  	{argshlVUIn, 7, 0, 3, _W - 1, argshlVUrWm1, 32, "partial overlap by 4 Words of shlVU and shift of _W - 1"},
   312  }
   313  
   314  var argshrVUIn = []Word{0, 0, 0, 1, 2, 4, 8, 16, 32, 64}
   315  var argshrVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
   316  var argshrVUr1 = []Word{0, 1, 2, 4, 8, 16, 32}
   317  var argshrVUrWm1 = []Word{4, 8, 16, 32, 64, 128, 0}
   318  
   319  var argshrVU = []argVU{
   320  	// test cases for shrVU
   321  	{[]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 shrVU"},
   322  	{[]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 shrVU"},
   323  	{[]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 shrVU"},
   324  	{[]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 shrVU"},
   325  	// additional test cases with shift values of 0, 1 and (_W-1)
   326  	{argshrVUIn, 7, 3, 3, 0, argshrVUr0, 0, "complete overlap of shrVU and shift of 0"},
   327  	{argshrVUIn, 7, 3, 3, 1, argshrVUr1, 1 << (_W - 1), "complete overlap of shrVU and shift of 1"},
   328  	{argshrVUIn, 7, 3, 3, _W - 1, argshrVUrWm1, 2, "complete overlap of shrVU and shift of _W - 1"},
   329  	{argshrVUIn, 7, 3, 2, 0, argshrVUr0, 0, "partial overlap by 6 Words of shrVU and shift of 0"},
   330  	{argshrVUIn, 7, 3, 2, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 6 Words of shrVU and shift of 1"},
   331  	{argshrVUIn, 7, 3, 2, _W - 1, argshrVUrWm1, 2, "partial overlap by 6 Words of shrVU and shift of _W - 1"},
   332  	{argshrVUIn, 7, 3, 1, 0, argshrVUr0, 0, "partial overlap by 5 Words of shrVU and shift of 0"},
   333  	{argshrVUIn, 7, 3, 1, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 5 Words of shrVU and shift of 1"},
   334  	{argshrVUIn, 7, 3, 1, _W - 1, argshrVUrWm1, 2, "partial overlap by 5 Words of shrVU and shift of _W - 1"},
   335  	{argshrVUIn, 7, 3, 0, 0, argshrVUr0, 0, "partial overlap by 4 Words of shrVU and shift of 0"},
   336  	{argshrVUIn, 7, 3, 0, 1, argshrVUr1, 1 << (_W - 1), "partial overlap by 4 Words of shrVU and shift of 1"},
   337  	{argshrVUIn, 7, 3, 0, _W - 1, argshrVUrWm1, 2, "partial overlap by 4 Words of shrVU and shift of _W - 1"},
   338  }
   339  
   340  func testShiftFunc(t *testing.T, f func(z, x []Word, s uint) Word, a argVU) {
   341  	// work on copy of a.d to preserve the original data.
   342  	b := make([]Word, len(a.d))
   343  	copy(b, a.d)
   344  	z := b[a.zp : a.zp+a.l]
   345  	x := b[a.xp : a.xp+a.l]
   346  	c := f(z, x, a.s)
   347  	for i, zi := range z {
   348  		if zi != a.r[i] {
   349  			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])
   350  			break
   351  		}
   352  	}
   353  	if c != a.c {
   354  		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)
   355  	}
   356  }
   357  
   358  func TestShiftOverlap(t *testing.T) {
   359  	for _, a := range argshlVU {
   360  		arg := a
   361  		testShiftFunc(t, shlVU, arg)
   362  	}
   363  
   364  	for _, a := range argshrVU {
   365  		arg := a
   366  		testShiftFunc(t, shrVU, arg)
   367  	}
   368  }
   369  
   370  func TestIssue31084(t *testing.T) {
   371  	stk := getStack()
   372  	defer stk.free()
   373  
   374  	// compute 10^n via 5^n << n.
   375  	const n = 165
   376  	p := nat(nil).expNN(stk, nat{5}, nat{n}, nil, false)
   377  	p = p.shl(p, n)
   378  	got := string(p.utoa(10))
   379  	want := "1" + strings.Repeat("0", n)
   380  	if got != want {
   381  		t.Errorf("shl(%v, %v)\n\tgot  %s\n\twant %s", p, n, got, want)
   382  	}
   383  }
   384  
   385  const issue42838Value = "159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625"
   386  
   387  func TestIssue42838(t *testing.T) {
   388  	const s = 192
   389  	z, _, _, _ := nat(nil).scan(strings.NewReader(issue42838Value), 0, false)
   390  	z = z.shl(z, s)
   391  	got := string(z.utoa(10))
   392  	want := "1" + strings.Repeat("0", s)
   393  	if got != want {
   394  		t.Errorf("shl(%v, %v)\n\tgot  %s\n\twant %s", z, s, got, want)
   395  	}
   396  }
   397  
   398  func BenchmarkAddVW(b *testing.B) {
   399  	for _, n := range benchSizes {
   400  		if isRaceBuilder && n > 1e3 {
   401  			continue
   402  		}
   403  		x := rndV(n)
   404  		y := rndW()
   405  		z := make([]Word, n)
   406  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   407  			b.SetBytes(int64(n * _S))
   408  			for i := 0; i < b.N; i++ {
   409  				addVW(z, x, y)
   410  			}
   411  		})
   412  	}
   413  }
   414  
   415  // Benchmarking addVW using vector of maximum uint to force carry flag set
   416  func BenchmarkAddVWext(b *testing.B) {
   417  	for _, n := range benchSizes {
   418  		if isRaceBuilder && n > 1e3 {
   419  			continue
   420  		}
   421  		y := ^Word(0)
   422  		x := makeWordVec(y, n)
   423  		z := make([]Word, n)
   424  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   425  			b.SetBytes(int64(n * _S))
   426  			for i := 0; i < b.N; i++ {
   427  				addVW(z, x, y)
   428  			}
   429  		})
   430  	}
   431  }
   432  
   433  func BenchmarkSubVW(b *testing.B) {
   434  	for _, n := range benchSizes {
   435  		if isRaceBuilder && n > 1e3 {
   436  			continue
   437  		}
   438  		x := rndV(n)
   439  		y := rndW()
   440  		z := make([]Word, n)
   441  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   442  			b.SetBytes(int64(n * _S))
   443  			for i := 0; i < b.N; i++ {
   444  				subVW(z, x, y)
   445  			}
   446  		})
   447  	}
   448  }
   449  
   450  // Benchmarking subVW using vector of zero to force carry flag set
   451  func BenchmarkSubVWext(b *testing.B) {
   452  	for _, n := range benchSizes {
   453  		if isRaceBuilder && n > 1e3 {
   454  			continue
   455  		}
   456  		x := makeWordVec(0, n)
   457  		y := Word(1)
   458  		z := make([]Word, n)
   459  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   460  			b.SetBytes(int64(n * _S))
   461  			for i := 0; i < b.N; i++ {
   462  				subVW(z, x, y)
   463  			}
   464  		})
   465  	}
   466  }
   467  
   468  type funVWW func(z, x []Word, y, r Word) (c Word)
   469  type argVWW struct {
   470  	z, x nat
   471  	y, r Word
   472  	c    Word
   473  }
   474  
   475  var prodVWW = []argVWW{
   476  	{},
   477  	{nat{0}, nat{0}, 0, 0, 0},
   478  	{nat{991}, nat{0}, 0, 991, 0},
   479  	{nat{0}, nat{_M}, 0, 0, 0},
   480  	{nat{991}, nat{_M}, 0, 991, 0},
   481  	{nat{0}, nat{0}, _M, 0, 0},
   482  	{nat{991}, nat{0}, _M, 991, 0},
   483  	{nat{1}, nat{1}, 1, 0, 0},
   484  	{nat{992}, nat{1}, 1, 991, 0},
   485  	{nat{22793}, nat{991}, 23, 0, 0},
   486  	{nat{22800}, nat{991}, 23, 7, 0},
   487  	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
   488  	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
   489  	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
   490  	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
   491  	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
   492  	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
   493  	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
   494  	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
   495  	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
   496  	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   497  	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
   498  	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   499  }
   500  
   501  func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
   502  	z := make(nat, len(a.z))
   503  	c := f(z, a.x, a.y, a.r)
   504  	for i, zi := range z {
   505  		if zi != a.z[i] {
   506  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   507  			break
   508  		}
   509  	}
   510  	if c != a.c {
   511  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   512  	}
   513  }
   514  
   515  // TODO(gri) mulAddVWW and divWVW are symmetric operations but
   516  // their signature is not symmetric. Try to unify.
   517  
   518  type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
   519  type argWVW struct {
   520  	z  nat
   521  	xn Word
   522  	x  nat
   523  	y  Word
   524  	r  Word
   525  }
   526  
   527  func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
   528  	z := make(nat, len(a.z))
   529  	r := f(z, a.xn, a.x, a.y)
   530  	for i, zi := range z {
   531  		if zi != a.z[i] {
   532  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   533  			break
   534  		}
   535  	}
   536  	if r != a.r {
   537  		t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
   538  	}
   539  }
   540  
   541  func TestFunVWW(t *testing.T) {
   542  	for _, a := range prodVWW {
   543  		arg := a
   544  		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
   545  		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
   546  
   547  		if a.y != 0 && a.r < a.y {
   548  			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
   549  			testFunWVW(t, "divWVW", divWVW, arg)
   550  		}
   551  	}
   552  }
   553  
   554  var mulWWTests = []struct {
   555  	x, y Word
   556  	q, r Word
   557  }{
   558  	{_M, _M, _M - 1, 1},
   559  	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
   560  }
   561  
   562  func TestMulWW(t *testing.T) {
   563  	for i, test := range mulWWTests {
   564  		q, r := mulWW(test.x, test.y)
   565  		if q != test.q || r != test.r {
   566  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   567  		}
   568  	}
   569  }
   570  
   571  var mulAddWWWTests = []struct {
   572  	x, y, c Word
   573  	q, r    Word
   574  }{
   575  	// TODO(agl): These will only work on 64-bit platforms.
   576  	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
   577  	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
   578  	{_M, _M, 0, _M - 1, 1},
   579  	{_M, _M, _M, _M, 0},
   580  }
   581  
   582  func TestMulAddWWW(t *testing.T) {
   583  	for i, test := range mulAddWWWTests {
   584  		q, r := mulAddWWW_g(test.x, test.y, test.c)
   585  		if q != test.q || r != test.r {
   586  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   587  		}
   588  	}
   589  }
   590  
   591  var divWWTests = []struct {
   592  	x1, x0, y Word
   593  	q, r      Word
   594  }{
   595  	{_M >> 1, 0, _M, _M >> 1, _M >> 1},
   596  	{_M - (1 << (_W - 2)), _M, 3 << (_W - 2), _M, _M - (1 << (_W - 2))},
   597  }
   598  
   599  const testsNumber = 1 << 16
   600  
   601  func TestDivWW(t *testing.T) {
   602  	i := 0
   603  	for i, test := range divWWTests {
   604  		rec := reciprocalWord(test.y)
   605  		q, r := divWW(test.x1, test.x0, test.y, rec)
   606  		if q != test.q || r != test.r {
   607  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   608  		}
   609  	}
   610  	//random tests
   611  	for ; i < testsNumber; i++ {
   612  		x1 := rndW()
   613  		x0 := rndW()
   614  		y := rndW()
   615  		if x1 >= y {
   616  			continue
   617  		}
   618  		rec := reciprocalWord(y)
   619  		qGot, rGot := divWW(x1, x0, y, rec)
   620  		qWant, rWant := bits.Div(uint(x1), uint(x0), uint(y))
   621  		if uint(qGot) != qWant || uint(rGot) != rWant {
   622  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, qGot, rGot, qWant, rWant)
   623  		}
   624  	}
   625  }
   626  
   627  func BenchmarkMulAddVWW(b *testing.B) {
   628  	for _, n := range benchSizes {
   629  		if isRaceBuilder && n > 1e3 {
   630  			continue
   631  		}
   632  		z := make([]Word, n+1)
   633  		x := rndV(n)
   634  		y := rndW()
   635  		r := rndW()
   636  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   637  			b.SetBytes(int64(n * _W))
   638  			for i := 0; i < b.N; i++ {
   639  				mulAddVWW(z, x, y, r)
   640  			}
   641  		})
   642  	}
   643  }
   644  
   645  func BenchmarkAddMulVVW(b *testing.B) {
   646  	for _, n := range benchSizes {
   647  		if isRaceBuilder && n > 1e3 {
   648  			continue
   649  		}
   650  		x := rndV(n)
   651  		y := rndW()
   652  		z := make([]Word, n)
   653  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   654  			b.SetBytes(int64(n * _W))
   655  			for i := 0; i < b.N; i++ {
   656  				addMulVVW(z, x, y)
   657  			}
   658  		})
   659  	}
   660  }
   661  func BenchmarkDivWVW(b *testing.B) {
   662  	for _, n := range benchSizes {
   663  		if isRaceBuilder && n > 1e3 {
   664  			continue
   665  		}
   666  		x := rndV(n)
   667  		y := rndW()
   668  		z := make([]Word, n)
   669  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   670  			b.SetBytes(int64(n * _W))
   671  			for i := 0; i < b.N; i++ {
   672  				divWVW(z, 0, x, y)
   673  			}
   674  		})
   675  	}
   676  }
   677  
   678  func BenchmarkNonZeroShifts(b *testing.B) {
   679  	for _, n := range benchSizes {
   680  		if isRaceBuilder && n > 1e3 {
   681  			continue
   682  		}
   683  		x := rndV(n)
   684  		s := uint(rand.Int63n(_W-2)) + 1 // avoid 0 and over-large shifts
   685  		z := make([]Word, n)
   686  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   687  			b.SetBytes(int64(n * _W))
   688  			b.Run("shrVU", func(b *testing.B) {
   689  				for i := 0; i < b.N; i++ {
   690  					_ = shrVU(z, x, s)
   691  				}
   692  			})
   693  			b.Run("shlVU", func(b *testing.B) {
   694  				for i := 0; i < b.N; i++ {
   695  					_ = shlVU(z, x, s)
   696  				}
   697  			})
   698  		})
   699  	}
   700  }
   701
View as plain text