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