1// Copyright 2017 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 bits_test 6 7import ( 8 . "math/bits" 9 "runtime" 10 "testing" 11 "unsafe" 12) 13 14func TestUintSize(t *testing.T) { 15 var x uint 16 if want := unsafe.Sizeof(x) * 8; UintSize != want { 17 t.Fatalf("UintSize = %d; want %d", UintSize, want) 18 } 19} 20 21func TestLeadingZeros(t *testing.T) { 22 for i := 0; i < 256; i++ { 23 nlz := tab[i].nlz 24 for k := 0; k < 64-8; k++ { 25 x := uint64(i) << uint(k) 26 if x <= 1<<8-1 { 27 got := LeadingZeros8(uint8(x)) 28 want := nlz - k + (8 - 8) 29 if x == 0 { 30 want = 8 31 } 32 if got != want { 33 t.Fatalf("LeadingZeros8(%#02x) == %d; want %d", x, got, want) 34 } 35 } 36 37 if x <= 1<<16-1 { 38 got := LeadingZeros16(uint16(x)) 39 want := nlz - k + (16 - 8) 40 if x == 0 { 41 want = 16 42 } 43 if got != want { 44 t.Fatalf("LeadingZeros16(%#04x) == %d; want %d", x, got, want) 45 } 46 } 47 48 if x <= 1<<32-1 { 49 got := LeadingZeros32(uint32(x)) 50 want := nlz - k + (32 - 8) 51 if x == 0 { 52 want = 32 53 } 54 if got != want { 55 t.Fatalf("LeadingZeros32(%#08x) == %d; want %d", x, got, want) 56 } 57 if UintSize == 32 { 58 got = LeadingZeros(uint(x)) 59 if got != want { 60 t.Fatalf("LeadingZeros(%#08x) == %d; want %d", x, got, want) 61 } 62 } 63 } 64 65 if x <= 1<<64-1 { 66 got := LeadingZeros64(uint64(x)) 67 want := nlz - k + (64 - 8) 68 if x == 0 { 69 want = 64 70 } 71 if got != want { 72 t.Fatalf("LeadingZeros64(%#016x) == %d; want %d", x, got, want) 73 } 74 if UintSize == 64 { 75 got = LeadingZeros(uint(x)) 76 if got != want { 77 t.Fatalf("LeadingZeros(%#016x) == %d; want %d", x, got, want) 78 } 79 } 80 } 81 } 82 } 83} 84 85// Exported (global) variable serving as input for some 86// of the benchmarks to ensure side-effect free calls 87// are not optimized away. 88var Input uint64 = DeBruijn64 89 90// Exported (global) variable to store function results 91// during benchmarking to ensure side-effect free calls 92// are not optimized away. 93var Output int 94 95func BenchmarkLeadingZeros(b *testing.B) { 96 var s int 97 for i := 0; i < b.N; i++ { 98 s += LeadingZeros(uint(Input) >> (uint(i) % UintSize)) 99 } 100 Output = s 101} 102 103func BenchmarkLeadingZeros8(b *testing.B) { 104 var s int 105 for i := 0; i < b.N; i++ { 106 s += LeadingZeros8(uint8(Input) >> (uint(i) % 8)) 107 } 108 Output = s 109} 110 111func BenchmarkLeadingZeros16(b *testing.B) { 112 var s int 113 for i := 0; i < b.N; i++ { 114 s += LeadingZeros16(uint16(Input) >> (uint(i) % 16)) 115 } 116 Output = s 117} 118 119func BenchmarkLeadingZeros32(b *testing.B) { 120 var s int 121 for i := 0; i < b.N; i++ { 122 s += LeadingZeros32(uint32(Input) >> (uint(i) % 32)) 123 } 124 Output = s 125} 126 127func BenchmarkLeadingZeros64(b *testing.B) { 128 var s int 129 for i := 0; i < b.N; i++ { 130 s += LeadingZeros64(uint64(Input) >> (uint(i) % 64)) 131 } 132 Output = s 133} 134 135func TestTrailingZeros(t *testing.T) { 136 for i := 0; i < 256; i++ { 137 ntz := tab[i].ntz 138 for k := 0; k < 64-8; k++ { 139 x := uint64(i) << uint(k) 140 want := ntz + k 141 if x <= 1<<8-1 { 142 got := TrailingZeros8(uint8(x)) 143 if x == 0 { 144 want = 8 145 } 146 if got != want { 147 t.Fatalf("TrailingZeros8(%#02x) == %d; want %d", x, got, want) 148 } 149 } 150 151 if x <= 1<<16-1 { 152 got := TrailingZeros16(uint16(x)) 153 if x == 0 { 154 want = 16 155 } 156 if got != want { 157 t.Fatalf("TrailingZeros16(%#04x) == %d; want %d", x, got, want) 158 } 159 } 160 161 if x <= 1<<32-1 { 162 got := TrailingZeros32(uint32(x)) 163 if x == 0 { 164 want = 32 165 } 166 if got != want { 167 t.Fatalf("TrailingZeros32(%#08x) == %d; want %d", x, got, want) 168 } 169 if UintSize == 32 { 170 got = TrailingZeros(uint(x)) 171 if got != want { 172 t.Fatalf("TrailingZeros(%#08x) == %d; want %d", x, got, want) 173 } 174 } 175 } 176 177 if x <= 1<<64-1 { 178 got := TrailingZeros64(uint64(x)) 179 if x == 0 { 180 want = 64 181 } 182 if got != want { 183 t.Fatalf("TrailingZeros64(%#016x) == %d; want %d", x, got, want) 184 } 185 if UintSize == 64 { 186 got = TrailingZeros(uint(x)) 187 if got != want { 188 t.Fatalf("TrailingZeros(%#016x) == %d; want %d", x, got, want) 189 } 190 } 191 } 192 } 193 } 194} 195 196func BenchmarkTrailingZeros(b *testing.B) { 197 var s int 198 for i := 0; i < b.N; i++ { 199 s += TrailingZeros(uint(Input) << (uint(i) % UintSize)) 200 } 201 Output = s 202} 203 204func BenchmarkTrailingZeros8(b *testing.B) { 205 var s int 206 for i := 0; i < b.N; i++ { 207 s += TrailingZeros8(uint8(Input) << (uint(i) % 8)) 208 } 209 Output = s 210} 211 212func BenchmarkTrailingZeros16(b *testing.B) { 213 var s int 214 for i := 0; i < b.N; i++ { 215 s += TrailingZeros16(uint16(Input) << (uint(i) % 16)) 216 } 217 Output = s 218} 219 220func BenchmarkTrailingZeros32(b *testing.B) { 221 var s int 222 for i := 0; i < b.N; i++ { 223 s += TrailingZeros32(uint32(Input) << (uint(i) % 32)) 224 } 225 Output = s 226} 227 228func BenchmarkTrailingZeros64(b *testing.B) { 229 var s int 230 for i := 0; i < b.N; i++ { 231 s += TrailingZeros64(uint64(Input) << (uint(i) % 64)) 232 } 233 Output = s 234} 235 236func TestOnesCount(t *testing.T) { 237 var x uint64 238 for i := 0; i <= 64; i++ { 239 testOnesCount(t, x, i) 240 x = x<<1 | 1 241 } 242 243 for i := 64; i >= 0; i-- { 244 testOnesCount(t, x, i) 245 x = x << 1 246 } 247 248 for i := 0; i < 256; i++ { 249 for k := 0; k < 64-8; k++ { 250 testOnesCount(t, uint64(i)<<uint(k), tab[i].pop) 251 } 252 } 253} 254 255func testOnesCount(t *testing.T, x uint64, want int) { 256 if x <= 1<<8-1 { 257 got := OnesCount8(uint8(x)) 258 if got != want { 259 t.Fatalf("OnesCount8(%#02x) == %d; want %d", uint8(x), got, want) 260 } 261 } 262 263 if x <= 1<<16-1 { 264 got := OnesCount16(uint16(x)) 265 if got != want { 266 t.Fatalf("OnesCount16(%#04x) == %d; want %d", uint16(x), got, want) 267 } 268 } 269 270 if x <= 1<<32-1 { 271 got := OnesCount32(uint32(x)) 272 if got != want { 273 t.Fatalf("OnesCount32(%#08x) == %d; want %d", uint32(x), got, want) 274 } 275 if UintSize == 32 { 276 got = OnesCount(uint(x)) 277 if got != want { 278 t.Fatalf("OnesCount(%#08x) == %d; want %d", uint32(x), got, want) 279 } 280 } 281 } 282 283 if x <= 1<<64-1 { 284 got := OnesCount64(uint64(x)) 285 if got != want { 286 t.Fatalf("OnesCount64(%#016x) == %d; want %d", x, got, want) 287 } 288 if UintSize == 64 { 289 got = OnesCount(uint(x)) 290 if got != want { 291 t.Fatalf("OnesCount(%#016x) == %d; want %d", x, got, want) 292 } 293 } 294 } 295} 296 297func BenchmarkOnesCount(b *testing.B) { 298 var s int 299 for i := 0; i < b.N; i++ { 300 s += OnesCount(uint(Input)) 301 } 302 Output = s 303} 304 305func BenchmarkOnesCount8(b *testing.B) { 306 var s int 307 for i := 0; i < b.N; i++ { 308 s += OnesCount8(uint8(Input)) 309 } 310 Output = s 311} 312 313func BenchmarkOnesCount16(b *testing.B) { 314 var s int 315 for i := 0; i < b.N; i++ { 316 s += OnesCount16(uint16(Input)) 317 } 318 Output = s 319} 320 321func BenchmarkOnesCount32(b *testing.B) { 322 var s int 323 for i := 0; i < b.N; i++ { 324 s += OnesCount32(uint32(Input)) 325 } 326 Output = s 327} 328 329func BenchmarkOnesCount64(b *testing.B) { 330 var s int 331 for i := 0; i < b.N; i++ { 332 s += OnesCount64(uint64(Input)) 333 } 334 Output = s 335} 336 337func TestRotateLeft(t *testing.T) { 338 var m uint64 = DeBruijn64 339 340 for k := uint(0); k < 128; k++ { 341 x8 := uint8(m) 342 got8 := RotateLeft8(x8, int(k)) 343 want8 := x8<<(k&0x7) | x8>>(8-k&0x7) 344 if got8 != want8 { 345 t.Fatalf("RotateLeft8(%#02x, %d) == %#02x; want %#02x", x8, k, got8, want8) 346 } 347 got8 = RotateLeft8(want8, -int(k)) 348 if got8 != x8 { 349 t.Fatalf("RotateLeft8(%#02x, -%d) == %#02x; want %#02x", want8, k, got8, x8) 350 } 351 352 x16 := uint16(m) 353 got16 := RotateLeft16(x16, int(k)) 354 want16 := x16<<(k&0xf) | x16>>(16-k&0xf) 355 if got16 != want16 { 356 t.Fatalf("RotateLeft16(%#04x, %d) == %#04x; want %#04x", x16, k, got16, want16) 357 } 358 got16 = RotateLeft16(want16, -int(k)) 359 if got16 != x16 { 360 t.Fatalf("RotateLeft16(%#04x, -%d) == %#04x; want %#04x", want16, k, got16, x16) 361 } 362 363 x32 := uint32(m) 364 got32 := RotateLeft32(x32, int(k)) 365 want32 := x32<<(k&0x1f) | x32>>(32-k&0x1f) 366 if got32 != want32 { 367 t.Fatalf("RotateLeft32(%#08x, %d) == %#08x; want %#08x", x32, k, got32, want32) 368 } 369 got32 = RotateLeft32(want32, -int(k)) 370 if got32 != x32 { 371 t.Fatalf("RotateLeft32(%#08x, -%d) == %#08x; want %#08x", want32, k, got32, x32) 372 } 373 if UintSize == 32 { 374 x := uint(m) 375 got := RotateLeft(x, int(k)) 376 want := x<<(k&0x1f) | x>>(32-k&0x1f) 377 if got != want { 378 t.Fatalf("RotateLeft(%#08x, %d) == %#08x; want %#08x", x, k, got, want) 379 } 380 got = RotateLeft(want, -int(k)) 381 if got != x { 382 t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x) 383 } 384 } 385 386 x64 := uint64(m) 387 got64 := RotateLeft64(x64, int(k)) 388 want64 := x64<<(k&0x3f) | x64>>(64-k&0x3f) 389 if got64 != want64 { 390 t.Fatalf("RotateLeft64(%#016x, %d) == %#016x; want %#016x", x64, k, got64, want64) 391 } 392 got64 = RotateLeft64(want64, -int(k)) 393 if got64 != x64 { 394 t.Fatalf("RotateLeft64(%#016x, -%d) == %#016x; want %#016x", want64, k, got64, x64) 395 } 396 if UintSize == 64 { 397 x := uint(m) 398 got := RotateLeft(x, int(k)) 399 want := x<<(k&0x3f) | x>>(64-k&0x3f) 400 if got != want { 401 t.Fatalf("RotateLeft(%#016x, %d) == %#016x; want %#016x", x, k, got, want) 402 } 403 got = RotateLeft(want, -int(k)) 404 if got != x { 405 t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x) 406 } 407 } 408 } 409} 410 411func BenchmarkRotateLeft(b *testing.B) { 412 var s uint 413 for i := 0; i < b.N; i++ { 414 s += RotateLeft(uint(Input), i) 415 } 416 Output = int(s) 417} 418 419func BenchmarkRotateLeft8(b *testing.B) { 420 var s uint8 421 for i := 0; i < b.N; i++ { 422 s += RotateLeft8(uint8(Input), i) 423 } 424 Output = int(s) 425} 426 427func BenchmarkRotateLeft16(b *testing.B) { 428 var s uint16 429 for i := 0; i < b.N; i++ { 430 s += RotateLeft16(uint16(Input), i) 431 } 432 Output = int(s) 433} 434 435func BenchmarkRotateLeft32(b *testing.B) { 436 var s uint32 437 for i := 0; i < b.N; i++ { 438 s += RotateLeft32(uint32(Input), i) 439 } 440 Output = int(s) 441} 442 443func BenchmarkRotateLeft64(b *testing.B) { 444 var s uint64 445 for i := 0; i < b.N; i++ { 446 s += RotateLeft64(uint64(Input), i) 447 } 448 Output = int(s) 449} 450 451func TestReverse(t *testing.T) { 452 // test each bit 453 for i := uint(0); i < 64; i++ { 454 testReverse(t, uint64(1)<<i, uint64(1)<<(63-i)) 455 } 456 457 // test a few patterns 458 for _, test := range []struct { 459 x, r uint64 460 }{ 461 {0, 0}, 462 {0x1, 0x8 << 60}, 463 {0x2, 0x4 << 60}, 464 {0x3, 0xc << 60}, 465 {0x4, 0x2 << 60}, 466 {0x5, 0xa << 60}, 467 {0x6, 0x6 << 60}, 468 {0x7, 0xe << 60}, 469 {0x8, 0x1 << 60}, 470 {0x9, 0x9 << 60}, 471 {0xa, 0x5 << 60}, 472 {0xb, 0xd << 60}, 473 {0xc, 0x3 << 60}, 474 {0xd, 0xb << 60}, 475 {0xe, 0x7 << 60}, 476 {0xf, 0xf << 60}, 477 {0x5686487, 0xe12616a000000000}, 478 {0x0123456789abcdef, 0xf7b3d591e6a2c480}, 479 } { 480 testReverse(t, test.x, test.r) 481 testReverse(t, test.r, test.x) 482 } 483} 484 485func testReverse(t *testing.T, x64, want64 uint64) { 486 x8 := uint8(x64) 487 got8 := Reverse8(x8) 488 want8 := uint8(want64 >> (64 - 8)) 489 if got8 != want8 { 490 t.Fatalf("Reverse8(%#02x) == %#02x; want %#02x", x8, got8, want8) 491 } 492 493 x16 := uint16(x64) 494 got16 := Reverse16(x16) 495 want16 := uint16(want64 >> (64 - 16)) 496 if got16 != want16 { 497 t.Fatalf("Reverse16(%#04x) == %#04x; want %#04x", x16, got16, want16) 498 } 499 500 x32 := uint32(x64) 501 got32 := Reverse32(x32) 502 want32 := uint32(want64 >> (64 - 32)) 503 if got32 != want32 { 504 t.Fatalf("Reverse32(%#08x) == %#08x; want %#08x", x32, got32, want32) 505 } 506 if UintSize == 32 { 507 x := uint(x32) 508 got := Reverse(x) 509 want := uint(want32) 510 if got != want { 511 t.Fatalf("Reverse(%#08x) == %#08x; want %#08x", x, got, want) 512 } 513 } 514 515 got64 := Reverse64(x64) 516 if got64 != want64 { 517 t.Fatalf("Reverse64(%#016x) == %#016x; want %#016x", x64, got64, want64) 518 } 519 if UintSize == 64 { 520 x := uint(x64) 521 got := Reverse(x) 522 want := uint(want64) 523 if got != want { 524 t.Fatalf("Reverse(%#08x) == %#016x; want %#016x", x, got, want) 525 } 526 } 527} 528 529func BenchmarkReverse(b *testing.B) { 530 var s uint 531 for i := 0; i < b.N; i++ { 532 s += Reverse(uint(i)) 533 } 534 Output = int(s) 535} 536 537func BenchmarkReverse8(b *testing.B) { 538 var s uint8 539 for i := 0; i < b.N; i++ { 540 s += Reverse8(uint8(i)) 541 } 542 Output = int(s) 543} 544 545func BenchmarkReverse16(b *testing.B) { 546 var s uint16 547 for i := 0; i < b.N; i++ { 548 s += Reverse16(uint16(i)) 549 } 550 Output = int(s) 551} 552 553func BenchmarkReverse32(b *testing.B) { 554 var s uint32 555 for i := 0; i < b.N; i++ { 556 s += Reverse32(uint32(i)) 557 } 558 Output = int(s) 559} 560 561func BenchmarkReverse64(b *testing.B) { 562 var s uint64 563 for i := 0; i < b.N; i++ { 564 s += Reverse64(uint64(i)) 565 } 566 Output = int(s) 567} 568 569func TestReverseBytes(t *testing.T) { 570 for _, test := range []struct { 571 x, r uint64 572 }{ 573 {0, 0}, 574 {0x01, 0x01 << 56}, 575 {0x0123, 0x2301 << 48}, 576 {0x012345, 0x452301 << 40}, 577 {0x01234567, 0x67452301 << 32}, 578 {0x0123456789, 0x8967452301 << 24}, 579 {0x0123456789ab, 0xab8967452301 << 16}, 580 {0x0123456789abcd, 0xcdab8967452301 << 8}, 581 {0x0123456789abcdef, 0xefcdab8967452301 << 0}, 582 } { 583 testReverseBytes(t, test.x, test.r) 584 testReverseBytes(t, test.r, test.x) 585 } 586} 587 588func testReverseBytes(t *testing.T, x64, want64 uint64) { 589 x16 := uint16(x64) 590 got16 := ReverseBytes16(x16) 591 want16 := uint16(want64 >> (64 - 16)) 592 if got16 != want16 { 593 t.Fatalf("ReverseBytes16(%#04x) == %#04x; want %#04x", x16, got16, want16) 594 } 595 596 x32 := uint32(x64) 597 got32 := ReverseBytes32(x32) 598 want32 := uint32(want64 >> (64 - 32)) 599 if got32 != want32 { 600 t.Fatalf("ReverseBytes32(%#08x) == %#08x; want %#08x", x32, got32, want32) 601 } 602 if UintSize == 32 { 603 x := uint(x32) 604 got := ReverseBytes(x) 605 want := uint(want32) 606 if got != want { 607 t.Fatalf("ReverseBytes(%#08x) == %#08x; want %#08x", x, got, want) 608 } 609 } 610 611 got64 := ReverseBytes64(x64) 612 if got64 != want64 { 613 t.Fatalf("ReverseBytes64(%#016x) == %#016x; want %#016x", x64, got64, want64) 614 } 615 if UintSize == 64 { 616 x := uint(x64) 617 got := ReverseBytes(x) 618 want := uint(want64) 619 if got != want { 620 t.Fatalf("ReverseBytes(%#016x) == %#016x; want %#016x", x, got, want) 621 } 622 } 623} 624 625func BenchmarkReverseBytes(b *testing.B) { 626 var s uint 627 for i := 0; i < b.N; i++ { 628 s += ReverseBytes(uint(i)) 629 } 630 Output = int(s) 631} 632 633func BenchmarkReverseBytes16(b *testing.B) { 634 var s uint16 635 for i := 0; i < b.N; i++ { 636 s += ReverseBytes16(uint16(i)) 637 } 638 Output = int(s) 639} 640 641func BenchmarkReverseBytes32(b *testing.B) { 642 var s uint32 643 for i := 0; i < b.N; i++ { 644 s += ReverseBytes32(uint32(i)) 645 } 646 Output = int(s) 647} 648 649func BenchmarkReverseBytes64(b *testing.B) { 650 var s uint64 651 for i := 0; i < b.N; i++ { 652 s += ReverseBytes64(uint64(i)) 653 } 654 Output = int(s) 655} 656 657func TestLen(t *testing.T) { 658 for i := 0; i < 256; i++ { 659 len := 8 - tab[i].nlz 660 for k := 0; k < 64-8; k++ { 661 x := uint64(i) << uint(k) 662 want := 0 663 if x != 0 { 664 want = len + k 665 } 666 if x <= 1<<8-1 { 667 got := Len8(uint8(x)) 668 if got != want { 669 t.Fatalf("Len8(%#02x) == %d; want %d", x, got, want) 670 } 671 } 672 673 if x <= 1<<16-1 { 674 got := Len16(uint16(x)) 675 if got != want { 676 t.Fatalf("Len16(%#04x) == %d; want %d", x, got, want) 677 } 678 } 679 680 if x <= 1<<32-1 { 681 got := Len32(uint32(x)) 682 if got != want { 683 t.Fatalf("Len32(%#08x) == %d; want %d", x, got, want) 684 } 685 if UintSize == 32 { 686 got := Len(uint(x)) 687 if got != want { 688 t.Fatalf("Len(%#08x) == %d; want %d", x, got, want) 689 } 690 } 691 } 692 693 if x <= 1<<64-1 { 694 got := Len64(uint64(x)) 695 if got != want { 696 t.Fatalf("Len64(%#016x) == %d; want %d", x, got, want) 697 } 698 if UintSize == 64 { 699 got := Len(uint(x)) 700 if got != want { 701 t.Fatalf("Len(%#016x) == %d; want %d", x, got, want) 702 } 703 } 704 } 705 } 706 } 707} 708 709const ( 710 _M = 1<<UintSize - 1 711 _M32 = 1<<32 - 1 712 _M64 = 1<<64 - 1 713) 714 715func TestAddSubUint(t *testing.T) { 716 test := func(msg string, f func(x, y, c uint) (z, cout uint), x, y, c, z, cout uint) { 717 z1, cout1 := f(x, y, c) 718 if z1 != z || cout1 != cout { 719 t.Errorf("%s: got z:cout = %#x:%#x; want %#x:%#x", msg, z1, cout1, z, cout) 720 } 721 } 722 for _, a := range []struct{ x, y, c, z, cout uint }{ 723 {0, 0, 0, 0, 0}, 724 {0, 1, 0, 1, 0}, 725 {0, 0, 1, 1, 0}, 726 {0, 1, 1, 2, 0}, 727 {12345, 67890, 0, 80235, 0}, 728 {12345, 67890, 1, 80236, 0}, 729 {_M, 1, 0, 0, 1}, 730 {_M, 0, 1, 0, 1}, 731 {_M, 1, 1, 1, 1}, 732 {_M, _M, 0, _M - 1, 1}, 733 {_M, _M, 1, _M, 1}, 734 } { 735 test("Add", Add, a.x, a.y, a.c, a.z, a.cout) 736 test("Add symmetric", Add, a.y, a.x, a.c, a.z, a.cout) 737 test("Sub", Sub, a.z, a.x, a.c, a.y, a.cout) 738 test("Sub symmetric", Sub, a.z, a.y, a.c, a.x, a.cout) 739 } 740} 741 742func TestAddSubUint32(t *testing.T) { 743 test := func(msg string, f func(x, y, c uint32) (z, cout uint32), x, y, c, z, cout uint32) { 744 z1, cout1 := f(x, y, c) 745 if z1 != z || cout1 != cout { 746 t.Errorf("%s: got z:cout = %#x:%#x; want %#x:%#x", msg, z1, cout1, z, cout) 747 } 748 } 749 for _, a := range []struct{ x, y, c, z, cout uint32 }{ 750 {0, 0, 0, 0, 0}, 751 {0, 1, 0, 1, 0}, 752 {0, 0, 1, 1, 0}, 753 {0, 1, 1, 2, 0}, 754 {12345, 67890, 0, 80235, 0}, 755 {12345, 67890, 1, 80236, 0}, 756 {_M32, 1, 0, 0, 1}, 757 {_M32, 0, 1, 0, 1}, 758 {_M32, 1, 1, 1, 1}, 759 {_M32, _M32, 0, _M32 - 1, 1}, 760 {_M32, _M32, 1, _M32, 1}, 761 } { 762 test("Add32", Add32, a.x, a.y, a.c, a.z, a.cout) 763 test("Add32 symmetric", Add32, a.y, a.x, a.c, a.z, a.cout) 764 test("Sub32", Sub32, a.z, a.x, a.c, a.y, a.cout) 765 test("Sub32 symmetric", Sub32, a.z, a.y, a.c, a.x, a.cout) 766 } 767} 768 769func TestAddSubUint64(t *testing.T) { 770 test := func(msg string, f func(x, y, c uint64) (z, cout uint64), x, y, c, z, cout uint64) { 771 z1, cout1 := f(x, y, c) 772 if z1 != z || cout1 != cout { 773 t.Errorf("%s: got z:cout = %#x:%#x; want %#x:%#x", msg, z1, cout1, z, cout) 774 } 775 } 776 for _, a := range []struct{ x, y, c, z, cout uint64 }{ 777 {0, 0, 0, 0, 0}, 778 {0, 1, 0, 1, 0}, 779 {0, 0, 1, 1, 0}, 780 {0, 1, 1, 2, 0}, 781 {12345, 67890, 0, 80235, 0}, 782 {12345, 67890, 1, 80236, 0}, 783 {_M64, 1, 0, 0, 1}, 784 {_M64, 0, 1, 0, 1}, 785 {_M64, 1, 1, 1, 1}, 786 {_M64, _M64, 0, _M64 - 1, 1}, 787 {_M64, _M64, 1, _M64, 1}, 788 } { 789 test("Add64", Add64, a.x, a.y, a.c, a.z, a.cout) 790 test("Add64 symmetric", Add64, a.y, a.x, a.c, a.z, a.cout) 791 test("Sub64", Sub64, a.z, a.x, a.c, a.y, a.cout) 792 test("Sub64 symmetric", Sub64, a.z, a.y, a.c, a.x, a.cout) 793 } 794} 795 796func TestMulDiv(t *testing.T) { 797 testMul := func(msg string, f func(x, y uint) (hi, lo uint), x, y, hi, lo uint) { 798 hi1, lo1 := f(x, y) 799 if hi1 != hi || lo1 != lo { 800 t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo) 801 } 802 } 803 testDiv := func(msg string, f func(hi, lo, y uint) (q, r uint), hi, lo, y, q, r uint) { 804 q1, r1 := f(hi, lo, y) 805 if q1 != q || r1 != r { 806 t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r) 807 } 808 } 809 for _, a := range []struct { 810 x, y uint 811 hi, lo, r uint 812 }{ 813 {1 << (UintSize - 1), 2, 1, 0, 1}, 814 {_M, _M, _M - 1, 1, 42}, 815 } { 816 testMul("Mul", Mul, a.x, a.y, a.hi, a.lo) 817 testMul("Mul symmetric", Mul, a.y, a.x, a.hi, a.lo) 818 testDiv("Div", Div, a.hi, a.lo+a.r, a.y, a.x, a.r) 819 testDiv("Div symmetric", Div, a.hi, a.lo+a.r, a.x, a.y, a.r) 820 } 821} 822 823func TestMulDiv32(t *testing.T) { 824 testMul := func(msg string, f func(x, y uint32) (hi, lo uint32), x, y, hi, lo uint32) { 825 hi1, lo1 := f(x, y) 826 if hi1 != hi || lo1 != lo { 827 t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo) 828 } 829 } 830 testDiv := func(msg string, f func(hi, lo, y uint32) (q, r uint32), hi, lo, y, q, r uint32) { 831 q1, r1 := f(hi, lo, y) 832 if q1 != q || r1 != r { 833 t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r) 834 } 835 } 836 for _, a := range []struct { 837 x, y uint32 838 hi, lo, r uint32 839 }{ 840 {1 << 31, 2, 1, 0, 1}, 841 {0xc47dfa8c, 50911, 0x98a4, 0x998587f4, 13}, 842 {_M32, _M32, _M32 - 1, 1, 42}, 843 } { 844 testMul("Mul32", Mul32, a.x, a.y, a.hi, a.lo) 845 testMul("Mul32 symmetric", Mul32, a.y, a.x, a.hi, a.lo) 846 testDiv("Div32", Div32, a.hi, a.lo+a.r, a.y, a.x, a.r) 847 testDiv("Div32 symmetric", Div32, a.hi, a.lo+a.r, a.x, a.y, a.r) 848 } 849} 850 851func TestMulDiv64(t *testing.T) { 852 testMul := func(msg string, f func(x, y uint64) (hi, lo uint64), x, y, hi, lo uint64) { 853 hi1, lo1 := f(x, y) 854 if hi1 != hi || lo1 != lo { 855 t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo) 856 } 857 } 858 testDiv := func(msg string, f func(hi, lo, y uint64) (q, r uint64), hi, lo, y, q, r uint64) { 859 q1, r1 := f(hi, lo, y) 860 if q1 != q || r1 != r { 861 t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r) 862 } 863 } 864 for _, a := range []struct { 865 x, y uint64 866 hi, lo, r uint64 867 }{ 868 {1 << 63, 2, 1, 0, 1}, 869 {0x3626229738a3b9, 0xd8988a9f1cc4a61, 0x2dd0712657fe8, 0x9dd6a3364c358319, 13}, 870 {_M64, _M64, _M64 - 1, 1, 42}, 871 } { 872 testMul("Mul64", Mul64, a.x, a.y, a.hi, a.lo) 873 testMul("Mul64 symmetric", Mul64, a.y, a.x, a.hi, a.lo) 874 testDiv("Div64", Div64, a.hi, a.lo+a.r, a.y, a.x, a.r) 875 testDiv("Div64 symmetric", Div64, a.hi, a.lo+a.r, a.x, a.y, a.r) 876 } 877} 878 879const ( 880 divZeroError = "runtime error: integer divide by zero" 881 overflowError = "runtime error: integer overflow" 882) 883 884func TestDivPanicOverflow(t *testing.T) { 885 // Expect a panic 886 defer func() { 887 if err := recover(); err == nil { 888 t.Error("Div should have panicked when y<=hi") 889 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError { 890 t.Errorf("Div expected panic: %q, got: %q ", overflowError, e.Error()) 891 } 892 }() 893 q, r := Div(1, 0, 1) 894 t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r) 895} 896 897func TestDiv32PanicOverflow(t *testing.T) { 898 // Expect a panic 899 defer func() { 900 if err := recover(); err == nil { 901 t.Error("Div32 should have panicked when y<=hi") 902 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError { 903 t.Errorf("Div32 expected panic: %q, got: %q ", overflowError, e.Error()) 904 } 905 }() 906 q, r := Div32(1, 0, 1) 907 t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r) 908} 909 910func TestDiv64PanicOverflow(t *testing.T) { 911 // Expect a panic 912 defer func() { 913 if err := recover(); err == nil { 914 t.Error("Div64 should have panicked when y<=hi") 915 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError { 916 t.Errorf("Div64 expected panic: %q, got: %q ", overflowError, e.Error()) 917 } 918 }() 919 q, r := Div64(1, 0, 1) 920 t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r) 921} 922 923func TestDivPanicZero(t *testing.T) { 924 // Expect a panic 925 defer func() { 926 if err := recover(); err == nil { 927 t.Error("Div should have panicked when y==0") 928 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError { 929 t.Errorf("Div expected panic: %q, got: %q ", divZeroError, e.Error()) 930 } 931 }() 932 q, r := Div(1, 1, 0) 933 t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r) 934} 935 936func TestDiv32PanicZero(t *testing.T) { 937 // Expect a panic 938 defer func() { 939 if err := recover(); err == nil { 940 t.Error("Div32 should have panicked when y==0") 941 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError { 942 t.Errorf("Div32 expected panic: %q, got: %q ", divZeroError, e.Error()) 943 } 944 }() 945 q, r := Div32(1, 1, 0) 946 t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r) 947} 948 949func TestDiv64PanicZero(t *testing.T) { 950 // Expect a panic 951 defer func() { 952 if err := recover(); err == nil { 953 t.Error("Div64 should have panicked when y==0") 954 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError { 955 t.Errorf("Div64 expected panic: %q, got: %q ", divZeroError, e.Error()) 956 } 957 }() 958 q, r := Div64(1, 1, 0) 959 t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r) 960} 961 962func BenchmarkAdd(b *testing.B) { 963 var z, c uint 964 for i := 0; i < b.N; i++ { 965 z, c = Add(uint(Input), uint(i), c) 966 } 967 Output = int(z + c) 968} 969 970func BenchmarkAdd32(b *testing.B) { 971 var z, c uint32 972 for i := 0; i < b.N; i++ { 973 z, c = Add32(uint32(Input), uint32(i), c) 974 } 975 Output = int(z + c) 976} 977 978func BenchmarkAdd64(b *testing.B) { 979 var z, c uint64 980 for i := 0; i < b.N; i++ { 981 z, c = Add64(uint64(Input), uint64(i), c) 982 } 983 Output = int(z + c) 984} 985 986func BenchmarkAdd64multiple(b *testing.B) { 987 var z0 = uint64(Input) 988 var z1 = uint64(Input) 989 var z2 = uint64(Input) 990 var z3 = uint64(Input) 991 for i := 0; i < b.N; i++ { 992 var c uint64 993 z0, c = Add64(z0, uint64(i), c) 994 z1, c = Add64(z1, uint64(i), c) 995 z2, c = Add64(z2, uint64(i), c) 996 z3, _ = Add64(z3, uint64(i), c) 997 } 998 Output = int(z0 + z1 + z2 + z3) 999} 1000 1001func BenchmarkSub(b *testing.B) { 1002 var z, c uint 1003 for i := 0; i < b.N; i++ { 1004 z, c = Sub(uint(Input), uint(i), c) 1005 } 1006 Output = int(z + c) 1007} 1008 1009func BenchmarkSub32(b *testing.B) { 1010 var z, c uint32 1011 for i := 0; i < b.N; i++ { 1012 z, c = Sub32(uint32(Input), uint32(i), c) 1013 } 1014 Output = int(z + c) 1015} 1016 1017func BenchmarkSub64(b *testing.B) { 1018 var z, c uint64 1019 for i := 0; i < b.N; i++ { 1020 z, c = Sub64(uint64(Input), uint64(i), c) 1021 } 1022 Output = int(z + c) 1023} 1024 1025func BenchmarkSub64multiple(b *testing.B) { 1026 var z0 = uint64(Input) 1027 var z1 = uint64(Input) 1028 var z2 = uint64(Input) 1029 var z3 = uint64(Input) 1030 for i := 0; i < b.N; i++ { 1031 var c uint64 1032 z0, c = Sub64(z0, uint64(i), c) 1033 z1, c = Sub64(z1, uint64(i), c) 1034 z2, c = Sub64(z2, uint64(i), c) 1035 z3, _ = Sub64(z3, uint64(i), c) 1036 } 1037 Output = int(z0 + z1 + z2 + z3) 1038} 1039 1040func BenchmarkMul(b *testing.B) { 1041 var hi, lo uint 1042 for i := 0; i < b.N; i++ { 1043 hi, lo = Mul(uint(Input), uint(i)) 1044 } 1045 Output = int(hi + lo) 1046} 1047 1048func BenchmarkMul32(b *testing.B) { 1049 var hi, lo uint32 1050 for i := 0; i < b.N; i++ { 1051 hi, lo = Mul32(uint32(Input), uint32(i)) 1052 } 1053 Output = int(hi + lo) 1054} 1055 1056func BenchmarkMul64(b *testing.B) { 1057 var hi, lo uint64 1058 for i := 0; i < b.N; i++ { 1059 hi, lo = Mul64(uint64(Input), uint64(i)) 1060 } 1061 Output = int(hi + lo) 1062} 1063 1064func BenchmarkDiv(b *testing.B) { 1065 var q, r uint 1066 for i := 0; i < b.N; i++ { 1067 q, r = Div(1, uint(i), uint(Input)) 1068 } 1069 Output = int(q + r) 1070} 1071 1072func BenchmarkDiv32(b *testing.B) { 1073 var q, r uint32 1074 for i := 0; i < b.N; i++ { 1075 q, r = Div32(1, uint32(i), uint32(Input)) 1076 } 1077 Output = int(q + r) 1078} 1079 1080func BenchmarkDiv64(b *testing.B) { 1081 var q, r uint64 1082 for i := 0; i < b.N; i++ { 1083 q, r = Div64(1, uint64(i), uint64(Input)) 1084 } 1085 Output = int(q + r) 1086} 1087 1088// ---------------------------------------------------------------------------- 1089// Testing support 1090 1091type entry = struct { 1092 nlz, ntz, pop int 1093} 1094 1095// tab contains results for all uint8 values 1096var tab [256]entry 1097 1098func init() { 1099 tab[0] = entry{8, 8, 0} 1100 for i := 1; i < len(tab); i++ { 1101 // nlz 1102 x := i // x != 0 1103 n := 0 1104 for x&0x80 == 0 { 1105 n++ 1106 x <<= 1 1107 } 1108 tab[i].nlz = n 1109 1110 // ntz 1111 x = i // x != 0 1112 n = 0 1113 for x&1 == 0 { 1114 n++ 1115 x >>= 1 1116 } 1117 tab[i].ntz = n 1118 1119 // pop 1120 x = i // x != 0 1121 n = 0 1122 for x != 0 { 1123 n += int(x & 1) 1124 x >>= 1 1125 } 1126 tab[i].pop = n 1127 } 1128} 1129