Source file src/pkg/big/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 "testing"
     8	
     9	type funWW func(x, y, c Word) (z1, z0 Word)
    10	type argWW struct {
    11		x, y, c, z1, z0 Word
    12	}
    13	
    14	var sumWW = []argWW{
    15		{0, 0, 0, 0, 0},
    16		{0, 1, 0, 0, 1},
    17		{0, 0, 1, 0, 1},
    18		{0, 1, 1, 0, 2},
    19		{12345, 67890, 0, 0, 80235},
    20		{12345, 67890, 1, 0, 80236},
    21		{_M, 1, 0, 1, 0},
    22		{_M, 0, 1, 1, 0},
    23		{_M, 1, 1, 1, 1},
    24		{_M, _M, 0, 1, _M - 1},
    25		{_M, _M, 1, 1, _M},
    26	}
    27	
    28	func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
    29		z1, z0 := f(a.x, a.y, a.c)
    30		if z1 != a.z1 || z0 != a.z0 {
    31			t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0)
    32		}
    33	}
    34	
    35	func TestFunWW(t *testing.T) {
    36		for _, a := range sumWW {
    37			arg := a
    38			testFunWW(t, "addWW_g", addWW_g, arg)
    39	
    40			arg = argWW{a.y, a.x, a.c, a.z1, a.z0}
    41			testFunWW(t, "addWW_g symmetric", addWW_g, arg)
    42	
    43			arg = argWW{a.z0, a.x, a.c, a.z1, a.y}
    44			testFunWW(t, "subWW_g", subWW_g, arg)
    45	
    46			arg = argWW{a.z0, a.y, a.c, a.z1, a.x}
    47			testFunWW(t, "subWW_g symmetric", subWW_g, arg)
    48		}
    49	}
    50	
    51	type funVV func(z, x, y []Word) (c Word)
    52	type argVV struct {
    53		z, x, y nat
    54		c       Word
    55	}
    56	
    57	var sumVV = []argVV{
    58		{},
    59		{nat{0}, nat{0}, nat{0}, 0},
    60		{nat{1}, nat{1}, nat{0}, 0},
    61		{nat{0}, nat{_M}, nat{1}, 1},
    62		{nat{80235}, nat{12345}, nat{67890}, 0},
    63		{nat{_M - 1}, nat{_M}, nat{_M}, 1},
    64		{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
    65		{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
    66		{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
    67	}
    68	
    69	func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
    70		z := make(nat, len(a.z))
    71		c := f(z, a.x, a.y)
    72		for i, zi := range z {
    73			if zi != a.z[i] {
    74				t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
    75				break
    76			}
    77		}
    78		if c != a.c {
    79			t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
    80		}
    81	}
    82	
    83	func TestFunVV(t *testing.T) {
    84		for _, a := range sumVV {
    85			arg := a
    86			testFunVV(t, "addVV_g", addVV_g, arg)
    87			testFunVV(t, "addVV", addVV, arg)
    88	
    89			arg = argVV{a.z, a.y, a.x, a.c}
    90			testFunVV(t, "addVV_g symmetric", addVV_g, arg)
    91			testFunVV(t, "addVV symmetric", addVV, arg)
    92	
    93			arg = argVV{a.x, a.z, a.y, a.c}
    94			testFunVV(t, "subVV_g", subVV_g, arg)
    95			testFunVV(t, "subVV", subVV, arg)
    96	
    97			arg = argVV{a.y, a.z, a.x, a.c}
    98			testFunVV(t, "subVV_g symmetric", subVV_g, arg)
    99			testFunVV(t, "subVV symmetric", subVV, arg)
   100		}
   101	}
   102	
   103	type funVW func(z, x []Word, y Word) (c Word)
   104	type argVW struct {
   105		z, x nat
   106		y    Word
   107		c    Word
   108	}
   109	
   110	var sumVW = []argVW{
   111		{},
   112		{nil, nil, 2, 2},
   113		{nat{0}, nat{0}, 0, 0},
   114		{nat{1}, nat{0}, 1, 0},
   115		{nat{1}, nat{1}, 0, 0},
   116		{nat{0}, nat{_M}, 1, 1},
   117		{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
   118	}
   119	
   120	var prodVW = []argVW{
   121		{},
   122		{nat{0}, nat{0}, 0, 0},
   123		{nat{0}, nat{_M}, 0, 0},
   124		{nat{0}, nat{0}, _M, 0},
   125		{nat{1}, nat{1}, 1, 0},
   126		{nat{22793}, nat{991}, 23, 0},
   127		{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0},
   128		{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0},
   129		{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0},
   130		{nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)},
   131		{nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)},
   132		{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)},
   133	}
   134	
   135	var lshVW = []argVW{
   136		{},
   137		{nat{0}, nat{0}, 0, 0},
   138		{nat{0}, nat{0}, 1, 0},
   139		{nat{0}, nat{0}, 20, 0},
   140	
   141		{nat{_M}, nat{_M}, 0, 0},
   142		{nat{_M << 1 & _M}, nat{_M}, 1, 1},
   143		{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
   144	
   145		{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   146		{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
   147		{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
   148	}
   149	
   150	var rshVW = []argVW{
   151		{},
   152		{nat{0}, nat{0}, 0, 0},
   153		{nat{0}, nat{0}, 1, 0},
   154		{nat{0}, nat{0}, 20, 0},
   155	
   156		{nat{_M}, nat{_M}, 0, 0},
   157		{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
   158		{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
   159	
   160		{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
   161		{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
   162		{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
   163	}
   164	
   165	func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
   166		z := make(nat, len(a.z))
   167		c := f(z, a.x, a.y)
   168		for i, zi := range z {
   169			if zi != a.z[i] {
   170				t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   171				break
   172			}
   173		}
   174		if c != a.c {
   175			t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   176		}
   177	}
   178	
   179	func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
   180		return func(z, x []Word, s Word) (c Word) {
   181			return f(z, x, uint(s))
   182		}
   183	}
   184	
   185	func TestFunVW(t *testing.T) {
   186		for _, a := range sumVW {
   187			arg := a
   188			testFunVW(t, "addVW_g", addVW_g, arg)
   189			testFunVW(t, "addVW", addVW, arg)
   190	
   191			arg = argVW{a.x, a.z, a.y, a.c}
   192			testFunVW(t, "subVW_g", subVW_g, arg)
   193			testFunVW(t, "subVW", subVW, arg)
   194		}
   195	
   196		shlVW_g := makeFunVW(shlVU_g)
   197		shlVW := makeFunVW(shlVU)
   198		for _, a := range lshVW {
   199			arg := a
   200			testFunVW(t, "shlVU_g", shlVW_g, arg)
   201			testFunVW(t, "shlVU", shlVW, arg)
   202		}
   203	
   204		shrVW_g := makeFunVW(shrVU_g)
   205		shrVW := makeFunVW(shrVU)
   206		for _, a := range rshVW {
   207			arg := a
   208			testFunVW(t, "shrVU_g", shrVW_g, arg)
   209			testFunVW(t, "shrVU", shrVW, arg)
   210		}
   211	}
   212	
   213	type funVWW func(z, x []Word, y, r Word) (c Word)
   214	type argVWW struct {
   215		z, x nat
   216		y, r Word
   217		c    Word
   218	}
   219	
   220	var prodVWW = []argVWW{
   221		{},
   222		{nat{0}, nat{0}, 0, 0, 0},
   223		{nat{991}, nat{0}, 0, 991, 0},
   224		{nat{0}, nat{_M}, 0, 0, 0},
   225		{nat{991}, nat{_M}, 0, 991, 0},
   226		{nat{0}, nat{0}, _M, 0, 0},
   227		{nat{991}, nat{0}, _M, 991, 0},
   228		{nat{1}, nat{1}, 1, 0, 0},
   229		{nat{992}, nat{1}, 1, 991, 0},
   230		{nat{22793}, nat{991}, 23, 0, 0},
   231		{nat{22800}, nat{991}, 23, 7, 0},
   232		{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
   233		{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
   234		{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
   235		{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
   236		{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
   237		{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
   238		{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
   239		{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
   240		{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
   241		{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   242		{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
   243		{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
   244	}
   245	
   246	func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
   247		z := make(nat, len(a.z))
   248		c := f(z, a.x, a.y, a.r)
   249		for i, zi := range z {
   250			if zi != a.z[i] {
   251				t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   252				break
   253			}
   254		}
   255		if c != a.c {
   256			t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
   257		}
   258	}
   259	
   260	// TODO(gri) mulAddVWW and divWVW are symmetric operations but
   261	//           their signature is not symmetric. Try to unify.
   262	
   263	type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
   264	type argWVW struct {
   265		z  nat
   266		xn Word
   267		x  nat
   268		y  Word
   269		r  Word
   270	}
   271	
   272	func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
   273		z := make(nat, len(a.z))
   274		r := f(z, a.xn, a.x, a.y)
   275		for i, zi := range z {
   276			if zi != a.z[i] {
   277				t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
   278				break
   279			}
   280		}
   281		if r != a.r {
   282			t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
   283		}
   284	}
   285	
   286	func TestFunVWW(t *testing.T) {
   287		for _, a := range prodVWW {
   288			arg := a
   289			testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
   290			testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
   291	
   292			if a.y != 0 && a.r < a.y {
   293				arg := argWVW{a.x, a.c, a.z, a.y, a.r}
   294				testFunWVW(t, "divWVW_g", divWVW_g, arg)
   295				testFunWVW(t, "divWVW", divWVW, arg)
   296			}
   297		}
   298	}
   299	
   300	var mulWWTests = []struct {
   301		x, y Word
   302		q, r Word
   303	}{
   304		{_M, _M, _M - 1, 1},
   305		// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
   306	}
   307	
   308	func TestMulWW(t *testing.T) {
   309		for i, test := range mulWWTests {
   310			q, r := mulWW_g(test.x, test.y)
   311			if q != test.q || r != test.r {
   312				t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   313			}
   314		}
   315	}
   316	
   317	var mulAddWWWTests = []struct {
   318		x, y, c Word
   319		q, r    Word
   320	}{
   321		// TODO(agl): These will only work on 64-bit platforms.
   322		// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
   323		// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
   324		{_M, _M, 0, _M - 1, 1},
   325		{_M, _M, _M, _M, 0},
   326	}
   327	
   328	func TestMulAddWWW(t *testing.T) {
   329		for i, test := range mulAddWWWTests {
   330			q, r := mulAddWWW_g(test.x, test.y, test.c)
   331			if q != test.q || r != test.r {
   332				t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
   333			}
   334		}
   335	}
The Go Programming Language

Source file src/pkg/big/arith_test.go
