Source file src/math/big/arith_test.go

Documentation: math/big

		 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  	// compute 10^n via 5^n << n.
	 372  	const n = 165
	 373  	p := nat(nil).expNN(nat{5}, nat{n}, nil)
	 374  	p = p.shl(p, n)
	 375  	got := string(p.utoa(10))
	 376  	want := "1" + strings.Repeat("0", n)
	 377  	if got != want {
	 378  		t.Errorf("shl(%v, %v)\n\tgot	%s\n\twant %s", p, n, got, want)
	 379  	}
	 380  }
	 381  
	 382  const issue42838Value = "159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625"
	 383  
	 384  func TestIssue42838(t *testing.T) {
	 385  	const s = 192
	 386  	z, _, _, _ := nat(nil).scan(strings.NewReader(issue42838Value), 0, false)
	 387  	z = z.shl(z, s)
	 388  	got := string(z.utoa(10))
	 389  	want := "1" + strings.Repeat("0", s)
	 390  	if got != want {
	 391  		t.Errorf("shl(%v, %v)\n\tgot	%s\n\twant %s", z, s, got, want)
	 392  	}
	 393  }
	 394  
	 395  func BenchmarkAddVW(b *testing.B) {
	 396  	for _, n := range benchSizes {
	 397  		if isRaceBuilder && n > 1e3 {
	 398  			continue
	 399  		}
	 400  		x := rndV(n)
	 401  		y := rndW()
	 402  		z := make([]Word, n)
	 403  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 404  			b.SetBytes(int64(n * _S))
	 405  			for i := 0; i < b.N; i++ {
	 406  				addVW(z, x, y)
	 407  			}
	 408  		})
	 409  	}
	 410  }
	 411  
	 412  // Benchmarking addVW using vector of maximum uint to force carry flag set
	 413  func BenchmarkAddVWext(b *testing.B) {
	 414  	for _, n := range benchSizes {
	 415  		if isRaceBuilder && n > 1e3 {
	 416  			continue
	 417  		}
	 418  		y := ^Word(0)
	 419  		x := makeWordVec(y, n)
	 420  		z := make([]Word, n)
	 421  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 422  			b.SetBytes(int64(n * _S))
	 423  			for i := 0; i < b.N; i++ {
	 424  				addVW(z, x, y)
	 425  			}
	 426  		})
	 427  	}
	 428  }
	 429  
	 430  func BenchmarkSubVW(b *testing.B) {
	 431  	for _, n := range benchSizes {
	 432  		if isRaceBuilder && n > 1e3 {
	 433  			continue
	 434  		}
	 435  		x := rndV(n)
	 436  		y := rndW()
	 437  		z := make([]Word, n)
	 438  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 439  			b.SetBytes(int64(n * _S))
	 440  			for i := 0; i < b.N; i++ {
	 441  				subVW(z, x, y)
	 442  			}
	 443  		})
	 444  	}
	 445  }
	 446  
	 447  // Benchmarking subVW using vector of zero to force carry flag set
	 448  func BenchmarkSubVWext(b *testing.B) {
	 449  	for _, n := range benchSizes {
	 450  		if isRaceBuilder && n > 1e3 {
	 451  			continue
	 452  		}
	 453  		x := makeWordVec(0, n)
	 454  		y := Word(1)
	 455  		z := make([]Word, n)
	 456  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 457  			b.SetBytes(int64(n * _S))
	 458  			for i := 0; i < b.N; i++ {
	 459  				subVW(z, x, y)
	 460  			}
	 461  		})
	 462  	}
	 463  }
	 464  
	 465  type funVWW func(z, x []Word, y, r Word) (c Word)
	 466  type argVWW struct {
	 467  	z, x nat
	 468  	y, r Word
	 469  	c		Word
	 470  }
	 471  
	 472  var prodVWW = []argVWW{
	 473  	{},
	 474  	{nat{0}, nat{0}, 0, 0, 0},
	 475  	{nat{991}, nat{0}, 0, 991, 0},
	 476  	{nat{0}, nat{_M}, 0, 0, 0},
	 477  	{nat{991}, nat{_M}, 0, 991, 0},
	 478  	{nat{0}, nat{0}, _M, 0, 0},
	 479  	{nat{991}, nat{0}, _M, 991, 0},
	 480  	{nat{1}, nat{1}, 1, 0, 0},
	 481  	{nat{992}, nat{1}, 1, 991, 0},
	 482  	{nat{22793}, nat{991}, 23, 0, 0},
	 483  	{nat{22800}, nat{991}, 23, 7, 0},
	 484  	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
	 485  	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
	 486  	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
	 487  	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
	 488  	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
	 489  	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
	 490  	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
	 491  	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
	 492  	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
	 493  	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
	 494  	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
	 495  	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
	 496  }
	 497  
	 498  func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
	 499  	z := make(nat, len(a.z))
	 500  	c := f(z, a.x, a.y, a.r)
	 501  	for i, zi := range z {
	 502  		if zi != a.z[i] {
	 503  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
	 504  			break
	 505  		}
	 506  	}
	 507  	if c != a.c {
	 508  		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
	 509  	}
	 510  }
	 511  
	 512  // TODO(gri) mulAddVWW and divWVW are symmetric operations but
	 513  //					 their signature is not symmetric. Try to unify.
	 514  
	 515  type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
	 516  type argWVW struct {
	 517  	z	nat
	 518  	xn Word
	 519  	x	nat
	 520  	y	Word
	 521  	r	Word
	 522  }
	 523  
	 524  func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
	 525  	z := make(nat, len(a.z))
	 526  	r := f(z, a.xn, a.x, a.y)
	 527  	for i, zi := range z {
	 528  		if zi != a.z[i] {
	 529  			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
	 530  			break
	 531  		}
	 532  	}
	 533  	if r != a.r {
	 534  		t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
	 535  	}
	 536  }
	 537  
	 538  func TestFunVWW(t *testing.T) {
	 539  	for _, a := range prodVWW {
	 540  		arg := a
	 541  		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
	 542  		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
	 543  
	 544  		if a.y != 0 && a.r < a.y {
	 545  			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
	 546  			testFunWVW(t, "divWVW", divWVW, arg)
	 547  		}
	 548  	}
	 549  }
	 550  
	 551  var mulWWTests = []struct {
	 552  	x, y Word
	 553  	q, r Word
	 554  }{
	 555  	{_M, _M, _M - 1, 1},
	 556  	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
	 557  }
	 558  
	 559  func TestMulWW(t *testing.T) {
	 560  	for i, test := range mulWWTests {
	 561  		q, r := mulWW_g(test.x, test.y)
	 562  		if q != test.q || r != test.r {
	 563  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
	 564  		}
	 565  	}
	 566  }
	 567  
	 568  var mulAddWWWTests = []struct {
	 569  	x, y, c Word
	 570  	q, r		Word
	 571  }{
	 572  	// TODO(agl): These will only work on 64-bit platforms.
	 573  	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
	 574  	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
	 575  	{_M, _M, 0, _M - 1, 1},
	 576  	{_M, _M, _M, _M, 0},
	 577  }
	 578  
	 579  func TestMulAddWWW(t *testing.T) {
	 580  	for i, test := range mulAddWWWTests {
	 581  		q, r := mulAddWWW_g(test.x, test.y, test.c)
	 582  		if q != test.q || r != test.r {
	 583  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
	 584  		}
	 585  	}
	 586  }
	 587  
	 588  var divWWTests = []struct {
	 589  	x1, x0, y Word
	 590  	q, r			Word
	 591  }{
	 592  	{_M >> 1, 0, _M, _M >> 1, _M >> 1},
	 593  	{_M - (1 << (_W - 2)), _M, 3 << (_W - 2), _M, _M - (1 << (_W - 2))},
	 594  }
	 595  
	 596  const testsNumber = 1 << 16
	 597  
	 598  func TestDivWW(t *testing.T) {
	 599  	i := 0
	 600  	for i, test := range divWWTests {
	 601  		rec := reciprocalWord(test.y)
	 602  		q, r := divWW(test.x1, test.x0, test.y, rec)
	 603  		if q != test.q || r != test.r {
	 604  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
	 605  		}
	 606  	}
	 607  	//random tests
	 608  	for ; i < testsNumber; i++ {
	 609  		x1 := rndW()
	 610  		x0 := rndW()
	 611  		y := rndW()
	 612  		if x1 >= y {
	 613  			continue
	 614  		}
	 615  		rec := reciprocalWord(y)
	 616  		qGot, rGot := divWW(x1, x0, y, rec)
	 617  		qWant, rWant := bits.Div(uint(x1), uint(x0), uint(y))
	 618  		if uint(qGot) != qWant || uint(rGot) != rWant {
	 619  			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, qGot, rGot, qWant, rWant)
	 620  		}
	 621  	}
	 622  }
	 623  
	 624  func BenchmarkMulAddVWW(b *testing.B) {
	 625  	for _, n := range benchSizes {
	 626  		if isRaceBuilder && n > 1e3 {
	 627  			continue
	 628  		}
	 629  		z := make([]Word, n+1)
	 630  		x := rndV(n)
	 631  		y := rndW()
	 632  		r := rndW()
	 633  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 634  			b.SetBytes(int64(n * _W))
	 635  			for i := 0; i < b.N; i++ {
	 636  				mulAddVWW(z, x, y, r)
	 637  			}
	 638  		})
	 639  	}
	 640  }
	 641  
	 642  func BenchmarkAddMulVVW(b *testing.B) {
	 643  	for _, n := range benchSizes {
	 644  		if isRaceBuilder && n > 1e3 {
	 645  			continue
	 646  		}
	 647  		x := rndV(n)
	 648  		y := rndW()
	 649  		z := make([]Word, n)
	 650  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 651  			b.SetBytes(int64(n * _W))
	 652  			for i := 0; i < b.N; i++ {
	 653  				addMulVVW(z, x, y)
	 654  			}
	 655  		})
	 656  	}
	 657  }
	 658  func BenchmarkDivWVW(b *testing.B) {
	 659  	for _, n := range benchSizes {
	 660  		if isRaceBuilder && n > 1e3 {
	 661  			continue
	 662  		}
	 663  		x := rndV(n)
	 664  		y := rndW()
	 665  		z := make([]Word, n)
	 666  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 667  			b.SetBytes(int64(n * _W))
	 668  			for i := 0; i < b.N; i++ {
	 669  				divWVW(z, 0, x, y)
	 670  			}
	 671  		})
	 672  	}
	 673  }
	 674  
	 675  func BenchmarkNonZeroShifts(b *testing.B) {
	 676  	for _, n := range benchSizes {
	 677  		if isRaceBuilder && n > 1e3 {
	 678  			continue
	 679  		}
	 680  		x := rndV(n)
	 681  		s := uint(rand.Int63n(_W-2)) + 1 // avoid 0 and over-large shifts
	 682  		z := make([]Word, n)
	 683  		b.Run(fmt.Sprint(n), func(b *testing.B) {
	 684  			b.SetBytes(int64(n * _W))
	 685  			b.Run("shrVU", func(b *testing.B) {
	 686  				for i := 0; i < b.N; i++ {
	 687  					_ = shrVU(z, x, s)
	 688  				}
	 689  			})
	 690  			b.Run("shlVU", func(b *testing.B) {
	 691  				for i := 0; i < b.N; i++ {
	 692  					_ = shlVU(z, x, s)
	 693  				}
	 694  			})
	 695  		})
	 696  	}
	 697  }
	 698  

View as plain text