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