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
5package big
6
7import (
8	"fmt"
9	"internal/testenv"
10	"math/bits"
11	"math/rand"
12	"strings"
13	"testing"
14)
15
16var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race")
17
18type funVV func(z, x, y []Word) (c Word)
19type argVV struct {
20	z, x, y nat
21	c       Word
22}
23
24var 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
36func 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
50func 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.
71var rnd = rand.New(rand.NewSource(0))
72
73func rndW() Word {
74	return Word(rnd.Int63()<<1 | rnd.Int63n(2))
75}
76
77func rndV(n int) []Word {
78	v := make([]Word, n)
79	for i := range v {
80		v[i] = rndW()
81	}
82	return v
83}
84
85var benchSizes = []int{1, 2, 3, 4, 5, 1e1, 1e2, 1e3, 1e4, 1e5}
86
87func 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
104func 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
121type funVW func(z, x []Word, y Word) (c Word)
122type argVW struct {
123	z, x nat
124	y    Word
125	c    Word
126}
127
128var 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
139var 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
154var 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
169func 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
183func 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
200func 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
206func 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'
235func 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.
246func 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
277type 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
288var argshlVUIn = []Word{1, 2, 4, 8, 16, 32, 64, 0, 0, 0}
289var argshlVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
290var argshlVUr1 = []Word{2, 4, 8, 16, 32, 64, 128}
291var argshlVUrWm1 = []Word{1 << (_W - 1), 0, 1, 2, 4, 8, 16}
292
293var 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
314var argshrVUIn = []Word{0, 0, 0, 1, 2, 4, 8, 16, 32, 64}
315var argshrVUr0 = []Word{1, 2, 4, 8, 16, 32, 64}
316var argshrVUr1 = []Word{0, 1, 2, 4, 8, 16, 32}
317var argshrVUrWm1 = []Word{4, 8, 16, 32, 64, 128, 0}
318
319var 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
340func 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
358func 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
370func 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, false)
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
382const issue42838Value = "159309191113245227702888039776771180559110455519261878607388585338616290151305816094308987472018268594098344692611135542392730712890625"
383
384func 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
395func 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
413func 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
430func 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
448func 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
465type funVWW func(z, x []Word, y, r Word) (c Word)
466type argVWW struct {
467	z, x nat
468	y, r Word
469	c    Word
470}
471
472var 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
498func 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
515type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
516type argWVW struct {
517	z  nat
518	xn Word
519	x  nat
520	y  Word
521	r  Word
522}
523
524func 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
538func 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
551var 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
559func TestMulWW(t *testing.T) {
560	for i, test := range mulWWTests {
561		q, r := mulWW(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
568var 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
579func 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
588var 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
596const testsNumber = 1 << 16
597
598func 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
624func 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
642func 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}
658func 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
675func 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