Black Lives Matter. Support the Equal Justice Initiative.

# 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
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
55
56  		arg = argVV{a.z, a.y, a.x, a.c}
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
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++ {
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
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}
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}
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}
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
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++ {
407  			}
408  		})
409  	}
410  }
411
412  // Benchmarking addVW using vector of maximum uint to force carry flag set
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++ {
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
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
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
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++ {
637  			}
638  		})
639  	}
640  }
641
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++ {
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