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	"math/rand"
9	"testing"
10)
11
12type funWW func(x, y, c Word) (z1, z0 Word)
13type argWW struct {
14	x, y, c, z1, z0 Word
15}
16
17var sumWW = []argWW{
18	{0, 0, 0, 0, 0},
19	{0, 1, 0, 0, 1},
20	{0, 0, 1, 0, 1},
21	{0, 1, 1, 0, 2},
22	{12345, 67890, 0, 0, 80235},
23	{12345, 67890, 1, 0, 80236},
24	{_M, 1, 0, 1, 0},
25	{_M, 0, 1, 1, 0},
26	{_M, 1, 1, 1, 1},
27	{_M, _M, 0, 1, _M - 1},
28	{_M, _M, 1, 1, _M},
29}
30
31func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
32	z1, z0 := f(a.x, a.y, a.c)
33	if z1 != a.z1 || z0 != a.z0 {
34		t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0)
35	}
36}
37
38func TestFunWW(t *testing.T) {
39	for _, a := range sumWW {
40		arg := a
41		testFunWW(t, "addWW_g", addWW_g, arg)
42
43		arg = argWW{a.y, a.x, a.c, a.z1, a.z0}
44		testFunWW(t, "addWW_g symmetric", addWW_g, arg)
45
46		arg = argWW{a.z0, a.x, a.c, a.z1, a.y}
47		testFunWW(t, "subWW_g", subWW_g, arg)
48
49		arg = argWW{a.z0, a.y, a.c, a.z1, a.x}
50		testFunWW(t, "subWW_g symmetric", subWW_g, arg)
51	}
52}
53
54type funVV func(z, x, y []Word) (c Word)
55type argVV struct {
56	z, x, y nat
57	c       Word
58}
59
60var sumVV = []argVV{
61	{},
62	{nat{0}, nat{0}, nat{0}, 0},
63	{nat{1}, nat{1}, nat{0}, 0},
64	{nat{0}, nat{_M}, nat{1}, 1},
65	{nat{80235}, nat{12345}, nat{67890}, 0},
66	{nat{_M - 1}, nat{_M}, nat{_M}, 1},
67	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
68	{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
69	{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
70}
71
72func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
73	z := make(nat, len(a.z))
74	c := f(z, a.x, a.y)
75	for i, zi := range z {
76		if zi != a.z[i] {
77			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
78			break
79		}
80	}
81	if c != a.c {
82		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
83	}
84}
85
86func TestFunVV(t *testing.T) {
87	for _, a := range sumVV {
88		arg := a
89		testFunVV(t, "addVV_g", addVV_g, arg)
90		testFunVV(t, "addVV", addVV, arg)
91
92		arg = argVV{a.z, a.y, a.x, a.c}
93		testFunVV(t, "addVV_g symmetric", addVV_g, arg)
94		testFunVV(t, "addVV symmetric", addVV, arg)
95
96		arg = argVV{a.x, a.z, a.y, a.c}
97		testFunVV(t, "subVV_g", subVV_g, arg)
98		testFunVV(t, "subVV", subVV, arg)
99
100		arg = argVV{a.y, a.z, a.x, a.c}
101		testFunVV(t, "subVV_g symmetric", subVV_g, arg)
102		testFunVV(t, "subVV symmetric", subVV, arg)
103	}
104}
105
106// Always the same seed for reproducible results.
107var rnd = rand.New(rand.NewSource(0))
108
109func rndW() Word {
110	return Word(rnd.Int63()<<1 | rnd.Int63n(2))
111}
112
113func rndV(n int) []Word {
114	v := make([]Word, n)
115	for i := range v {
116		v[i] = rndW()
117	}
118	return v
119}
120
121func benchmarkFunVV(b *testing.B, f funVV, n int) {
122	x := rndV(n)
123	y := rndV(n)
124	z := make([]Word, n)
125	b.SetBytes(int64(n * _W))
126	b.ResetTimer()
127	for i := 0; i < b.N; i++ {
128		f(z, x, y)
129	}
130}
131
132func BenchmarkAddVV_1(b *testing.B)   { benchmarkFunVV(b, addVV, 1) }
133func BenchmarkAddVV_2(b *testing.B)   { benchmarkFunVV(b, addVV, 2) }
134func BenchmarkAddVV_3(b *testing.B)   { benchmarkFunVV(b, addVV, 3) }
135func BenchmarkAddVV_4(b *testing.B)   { benchmarkFunVV(b, addVV, 4) }
136func BenchmarkAddVV_5(b *testing.B)   { benchmarkFunVV(b, addVV, 5) }
137func BenchmarkAddVV_1e1(b *testing.B) { benchmarkFunVV(b, addVV, 1e1) }
138func BenchmarkAddVV_1e2(b *testing.B) { benchmarkFunVV(b, addVV, 1e2) }
139func BenchmarkAddVV_1e3(b *testing.B) { benchmarkFunVV(b, addVV, 1e3) }
140func BenchmarkAddVV_1e4(b *testing.B) { benchmarkFunVV(b, addVV, 1e4) }
141func BenchmarkAddVV_1e5(b *testing.B) { benchmarkFunVV(b, addVV, 1e5) }
142
143type funVW func(z, x []Word, y Word) (c Word)
144type argVW struct {
145	z, x nat
146	y    Word
147	c    Word
148}
149
150var sumVW = []argVW{
151	{},
152	{nil, nil, 2, 2},
153	{nat{0}, nat{0}, 0, 0},
154	{nat{1}, nat{0}, 1, 0},
155	{nat{1}, nat{1}, 0, 0},
156	{nat{0}, nat{_M}, 1, 1},
157	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
158}
159
160var prodVW = []argVW{
161	{},
162	{nat{0}, nat{0}, 0, 0},
163	{nat{0}, nat{_M}, 0, 0},
164	{nat{0}, nat{0}, _M, 0},
165	{nat{1}, nat{1}, 1, 0},
166	{nat{22793}, nat{991}, 23, 0},
167	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0},
168	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0},
169	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0},
170	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)},
171	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)},
172	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)},
173}
174
175var lshVW = []argVW{
176	{},
177	{nat{0}, nat{0}, 0, 0},
178	{nat{0}, nat{0}, 1, 0},
179	{nat{0}, nat{0}, 20, 0},
180
181	{nat{_M}, nat{_M}, 0, 0},
182	{nat{_M << 1 & _M}, nat{_M}, 1, 1},
183	{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
184
185	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
186	{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
187	{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
188}
189
190var rshVW = []argVW{
191	{},
192	{nat{0}, nat{0}, 0, 0},
193	{nat{0}, nat{0}, 1, 0},
194	{nat{0}, nat{0}, 20, 0},
195
196	{nat{_M}, nat{_M}, 0, 0},
197	{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
198	{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
199
200	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
201	{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
202	{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
203}
204
205func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
206	z := make(nat, len(a.z))
207	c := f(z, a.x, a.y)
208	for i, zi := range z {
209		if zi != a.z[i] {
210			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
211			break
212		}
213	}
214	if c != a.c {
215		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
216	}
217}
218
219func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
220	return func(z, x []Word, s Word) (c Word) {
221		return f(z, x, uint(s))
222	}
223}
224
225func TestFunVW(t *testing.T) {
226	for _, a := range sumVW {
227		arg := a
228		testFunVW(t, "addVW_g", addVW_g, arg)
229		testFunVW(t, "addVW", addVW, arg)
230
231		arg = argVW{a.x, a.z, a.y, a.c}
232		testFunVW(t, "subVW_g", subVW_g, arg)
233		testFunVW(t, "subVW", subVW, arg)
234	}
235
236	shlVW_g := makeFunVW(shlVU_g)
237	shlVW := makeFunVW(shlVU)
238	for _, a := range lshVW {
239		arg := a
240		testFunVW(t, "shlVU_g", shlVW_g, arg)
241		testFunVW(t, "shlVU", shlVW, arg)
242	}
243
244	shrVW_g := makeFunVW(shrVU_g)
245	shrVW := makeFunVW(shrVU)
246	for _, a := range rshVW {
247		arg := a
248		testFunVW(t, "shrVU_g", shrVW_g, arg)
249		testFunVW(t, "shrVU", shrVW, arg)
250	}
251}
252
253func benchmarkFunVW(b *testing.B, f funVW, n int) {
254	x := rndV(n)
255	y := rndW()
256	z := make([]Word, n)
257	b.SetBytes(int64(n * _W))
258	b.ResetTimer()
259	for i := 0; i < b.N; i++ {
260		f(z, x, y)
261	}
262}
263
264func BenchmarkAddVW_1(b *testing.B)   { benchmarkFunVW(b, addVW, 1) }
265func BenchmarkAddVW_2(b *testing.B)   { benchmarkFunVW(b, addVW, 2) }
266func BenchmarkAddVW_3(b *testing.B)   { benchmarkFunVW(b, addVW, 3) }
267func BenchmarkAddVW_4(b *testing.B)   { benchmarkFunVW(b, addVW, 4) }
268func BenchmarkAddVW_5(b *testing.B)   { benchmarkFunVW(b, addVW, 5) }
269func BenchmarkAddVW_1e1(b *testing.B) { benchmarkFunVW(b, addVW, 1e1) }
270func BenchmarkAddVW_1e2(b *testing.B) { benchmarkFunVW(b, addVW, 1e2) }
271func BenchmarkAddVW_1e3(b *testing.B) { benchmarkFunVW(b, addVW, 1e3) }
272func BenchmarkAddVW_1e4(b *testing.B) { benchmarkFunVW(b, addVW, 1e4) }
273func BenchmarkAddVW_1e5(b *testing.B) { benchmarkFunVW(b, addVW, 1e5) }
274
275type funVWW func(z, x []Word, y, r Word) (c Word)
276type argVWW struct {
277	z, x nat
278	y, r Word
279	c    Word
280}
281
282var prodVWW = []argVWW{
283	{},
284	{nat{0}, nat{0}, 0, 0, 0},
285	{nat{991}, nat{0}, 0, 991, 0},
286	{nat{0}, nat{_M}, 0, 0, 0},
287	{nat{991}, nat{_M}, 0, 991, 0},
288	{nat{0}, nat{0}, _M, 0, 0},
289	{nat{991}, nat{0}, _M, 991, 0},
290	{nat{1}, nat{1}, 1, 0, 0},
291	{nat{992}, nat{1}, 1, 991, 0},
292	{nat{22793}, nat{991}, 23, 0, 0},
293	{nat{22800}, nat{991}, 23, 7, 0},
294	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
295	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
296	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
297	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
298	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
299	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
300	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
301	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
302	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
303	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
304	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
305	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
306}
307
308func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
309	z := make(nat, len(a.z))
310	c := f(z, a.x, a.y, a.r)
311	for i, zi := range z {
312		if zi != a.z[i] {
313			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
314			break
315		}
316	}
317	if c != a.c {
318		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
319	}
320}
321
322// TODO(gri) mulAddVWW and divWVW are symmetric operations but
323//           their signature is not symmetric. Try to unify.
324
325type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
326type argWVW struct {
327	z  nat
328	xn Word
329	x  nat
330	y  Word
331	r  Word
332}
333
334func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
335	z := make(nat, len(a.z))
336	r := f(z, a.xn, a.x, a.y)
337	for i, zi := range z {
338		if zi != a.z[i] {
339			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
340			break
341		}
342	}
343	if r != a.r {
344		t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
345	}
346}
347
348func TestFunVWW(t *testing.T) {
349	for _, a := range prodVWW {
350		arg := a
351		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
352		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
353
354		if a.y != 0 && a.r < a.y {
355			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
356			testFunWVW(t, "divWVW_g", divWVW_g, arg)
357			testFunWVW(t, "divWVW", divWVW, arg)
358		}
359	}
360}
361
362var mulWWTests = []struct {
363	x, y Word
364	q, r Word
365}{
366	{_M, _M, _M - 1, 1},
367	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
368}
369
370func TestMulWW(t *testing.T) {
371	for i, test := range mulWWTests {
372		q, r := mulWW_g(test.x, test.y)
373		if q != test.q || r != test.r {
374			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
375		}
376	}
377}
378
379var mulAddWWWTests = []struct {
380	x, y, c Word
381	q, r    Word
382}{
383	// TODO(agl): These will only work on 64-bit platforms.
384	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
385	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
386	{_M, _M, 0, _M - 1, 1},
387	{_M, _M, _M, _M, 0},
388}
389
390func TestMulAddWWW(t *testing.T) {
391	for i, test := range mulAddWWWTests {
392		q, r := mulAddWWW_g(test.x, test.y, test.c)
393		if q != test.q || r != test.r {
394			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
395		}
396	}
397}
398
399func benchmarkAddMulVVW(b *testing.B, n int) {
400	x := rndV(n)
401	y := rndW()
402	z := make([]Word, n)
403	b.SetBytes(int64(n * _W))
404	b.ResetTimer()
405	for i := 0; i < b.N; i++ {
406		addMulVVW(z, x, y)
407	}
408}
409
410func BenchmarkAddMulVVW_1(b *testing.B)   { benchmarkAddMulVVW(b, 1) }
411func BenchmarkAddMulVVW_2(b *testing.B)   { benchmarkAddMulVVW(b, 2) }
412func BenchmarkAddMulVVW_3(b *testing.B)   { benchmarkAddMulVVW(b, 3) }
413func BenchmarkAddMulVVW_4(b *testing.B)   { benchmarkAddMulVVW(b, 4) }
414func BenchmarkAddMulVVW_5(b *testing.B)   { benchmarkAddMulVVW(b, 5) }
415func BenchmarkAddMulVVW_1e1(b *testing.B) { benchmarkAddMulVVW(b, 1e1) }
416func BenchmarkAddMulVVW_1e2(b *testing.B) { benchmarkAddMulVVW(b, 1e2) }
417func BenchmarkAddMulVVW_1e3(b *testing.B) { benchmarkAddMulVVW(b, 1e3) }
418func BenchmarkAddMulVVW_1e4(b *testing.B) { benchmarkAddMulVVW(b, 1e4) }
419func BenchmarkAddMulVVW_1e5(b *testing.B) { benchmarkAddMulVVW(b, 1e5) }
420
421func testWordBitLen(t *testing.T, fname string, f func(Word) int) {
422	for i := 0; i <= _W; i++ {
423		x := Word(1) << uint(i-1) // i == 0 => x == 0
424		n := f(x)
425		if n != i {
426			t.Errorf("got %d; want %d for %s(%#x)", n, i, fname, x)
427		}
428	}
429}
430
431func TestWordBitLen(t *testing.T) {
432	testWordBitLen(t, "bitLen", bitLen)
433	testWordBitLen(t, "bitLen_g", bitLen_g)
434}
435
436// runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1.
437func benchmarkBitLenN(b *testing.B, nbits uint) {
438	testword := Word((uint64(1) << nbits) - 1)
439	for i := 0; i < b.N; i++ {
440		bitLen(testword)
441	}
442}
443
444// Individual bitLen tests.  Numbers chosen to examine both sides
445// of powers-of-two boundaries.
446func BenchmarkBitLen0(b *testing.B)  { benchmarkBitLenN(b, 0) }
447func BenchmarkBitLen1(b *testing.B)  { benchmarkBitLenN(b, 1) }
448func BenchmarkBitLen2(b *testing.B)  { benchmarkBitLenN(b, 2) }
449func BenchmarkBitLen3(b *testing.B)  { benchmarkBitLenN(b, 3) }
450func BenchmarkBitLen4(b *testing.B)  { benchmarkBitLenN(b, 4) }
451func BenchmarkBitLen5(b *testing.B)  { benchmarkBitLenN(b, 5) }
452func BenchmarkBitLen8(b *testing.B)  { benchmarkBitLenN(b, 8) }
453func BenchmarkBitLen9(b *testing.B)  { benchmarkBitLenN(b, 9) }
454func BenchmarkBitLen16(b *testing.B) { benchmarkBitLenN(b, 16) }
455func BenchmarkBitLen17(b *testing.B) { benchmarkBitLenN(b, 17) }
456func BenchmarkBitLen31(b *testing.B) { benchmarkBitLenN(b, 31) }
457