libgo/go/math/bits/bits_test.go

   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
   5 package bits_test
   6
   7 import (
   8         . "math/bits"
   9         "runtime"
  10         "testing"
  11         "unsafe"
  12 )
  13
  14 func 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
  21 func 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.
  88 var 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.
  93 var Output int
  94
  95 func 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
 103 func 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
 111 func 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
 119 func 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
 127 func 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
 135 func 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
 196 func 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
 204 func 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
 212 func 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
 220 func 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
 228 func 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
 236 func 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
 255 func 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
 297 func 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
 305 func 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
 313 func 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
 321 func 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
 329 func 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
 337 func 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
 411 func 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
 419 func 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
 427 func 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
 435 func 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
 443 func 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
 451 func 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
 485 func 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
 529 func 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
 537 func 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
 545 func 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
 553 func 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
 561 func 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
 569 func 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
 588 func 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
 625 func 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
 633 func 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
 641 func 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
 649 func 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
 657 func 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
 709 const (
 710         _M   = 1<<UintSize - 1
 711         _M32 = 1<<32 - 1
 712         _M64 = 1<<64 - 1
 713 )
 714
 715 func 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                 // The above code can't test intrinsic implementation, because the passed function is not called directly.
 740                 // The following code uses a closure to test the intrinsic version in case the function is intrinsified.
 741                 test("Add intrinsic", func(x, y, c uint) (uint, uint) { return Add(x, y, c) }, a.x, a.y, a.c, a.z, a.cout)
 742                 test("Add intrinsic symmetric", func(x, y, c uint) (uint, uint) { return Add(x, y, c) }, a.y, a.x, a.c, a.z, a.cout)
 743                 test("Sub intrinsic", func(x, y, c uint) (uint, uint) { return Sub(x, y, c) }, a.z, a.x, a.c, a.y, a.cout)
 744                 test("Sub intrinsic symmetric", func(x, y, c uint) (uint, uint) { return Sub(x, y, c) }, a.z, a.y, a.c, a.x, a.cout)
 745
 746         }
 747 }
 748
 749 func TestAddSubUint32(t *testing.T) {
 750         test := func(msg string, f func(x, y, c uint32) (z, cout uint32), x, y, c, z, cout uint32) {
 751                 z1, cout1 := f(x, y, c)
 752                 if z1 != z || cout1 != cout {
 753                         t.Errorf("%s: got z:cout = %#x:%#x; want %#x:%#x", msg, z1, cout1, z, cout)
 754                 }
 755         }
 756         for _, a := range []struct{ x, y, c, z, cout uint32 }{
 757                 {0, 0, 0, 0, 0},
 758                 {0, 1, 0, 1, 0},
 759                 {0, 0, 1, 1, 0},
 760                 {0, 1, 1, 2, 0},
 761                 {12345, 67890, 0, 80235, 0},
 762                 {12345, 67890, 1, 80236, 0},
 763                 {_M32, 1, 0, 0, 1},
 764                 {_M32, 0, 1, 0, 1},
 765                 {_M32, 1, 1, 1, 1},
 766                 {_M32, _M32, 0, _M32 - 1, 1},
 767                 {_M32, _M32, 1, _M32, 1},
 768         } {
 769                 test("Add32", Add32, a.x, a.y, a.c, a.z, a.cout)
 770                 test("Add32 symmetric", Add32, a.y, a.x, a.c, a.z, a.cout)
 771                 test("Sub32", Sub32, a.z, a.x, a.c, a.y, a.cout)
 772                 test("Sub32 symmetric", Sub32, a.z, a.y, a.c, a.x, a.cout)
 773         }
 774 }
 775
 776 func TestAddSubUint64(t *testing.T) {
 777         test := func(msg string, f func(x, y, c uint64) (z, cout uint64), x, y, c, z, cout uint64) {
 778                 z1, cout1 := f(x, y, c)
 779                 if z1 != z || cout1 != cout {
 780                         t.Errorf("%s: got z:cout = %#x:%#x; want %#x:%#x", msg, z1, cout1, z, cout)
 781                 }
 782         }
 783         for _, a := range []struct{ x, y, c, z, cout uint64 }{
 784                 {0, 0, 0, 0, 0},
 785                 {0, 1, 0, 1, 0},
 786                 {0, 0, 1, 1, 0},
 787                 {0, 1, 1, 2, 0},
 788                 {12345, 67890, 0, 80235, 0},
 789                 {12345, 67890, 1, 80236, 0},
 790                 {_M64, 1, 0, 0, 1},
 791                 {_M64, 0, 1, 0, 1},
 792                 {_M64, 1, 1, 1, 1},
 793                 {_M64, _M64, 0, _M64 - 1, 1},
 794                 {_M64, _M64, 1, _M64, 1},
 795         } {
 796                 test("Add64", Add64, a.x, a.y, a.c, a.z, a.cout)
 797                 test("Add64 symmetric", Add64, a.y, a.x, a.c, a.z, a.cout)
 798                 test("Sub64", Sub64, a.z, a.x, a.c, a.y, a.cout)
 799                 test("Sub64 symmetric", Sub64, a.z, a.y, a.c, a.x, a.cout)
 800                 // The above code can't test intrinsic implementation, because the passed function is not called directly.
 801                 // The following code uses a closure to test the intrinsic version in case the function is intrinsified.
 802                 test("Add64 intrinsic", func(x, y, c uint64) (uint64, uint64) { return Add64(x, y, c) }, a.x, a.y, a.c, a.z, a.cout)
 803                 test("Add64 intrinsic symmetric", func(x, y, c uint64) (uint64, uint64) { return Add64(x, y, c) }, a.y, a.x, a.c, a.z, a.cout)
 804                 test("Sub64 intrinsic", func(x, y, c uint64) (uint64, uint64) { return Sub64(x, y, c) }, a.z, a.x, a.c, a.y, a.cout)
 805                 test("Sub64 intrinsic symmetric", func(x, y, c uint64) (uint64, uint64) { return Sub64(x, y, c) }, a.z, a.y, a.c, a.x, a.cout)
 806         }
 807 }
 808
 809 func TestMulDiv(t *testing.T) {
 810         testMul := func(msg string, f func(x, y uint) (hi, lo uint), x, y, hi, lo uint) {
 811                 hi1, lo1 := f(x, y)
 812                 if hi1 != hi || lo1 != lo {
 813                         t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
 814                 }
 815         }
 816         testDiv := func(msg string, f func(hi, lo, y uint) (q, r uint), hi, lo, y, q, r uint) {
 817                 q1, r1 := f(hi, lo, y)
 818                 if q1 != q || r1 != r {
 819                         t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
 820                 }
 821         }
 822         for _, a := range []struct {
 823                 x, y      uint
 824                 hi, lo, r uint
 825         }{
 826                 {1 << (UintSize - 1), 2, 1, 0, 1},
 827                 {_M, _M, _M - 1, 1, 42},
 828         } {
 829                 testMul("Mul", Mul, a.x, a.y, a.hi, a.lo)
 830                 testMul("Mul symmetric", Mul, a.y, a.x, a.hi, a.lo)
 831                 testDiv("Div", Div, a.hi, a.lo+a.r, a.y, a.x, a.r)
 832                 testDiv("Div symmetric", Div, a.hi, a.lo+a.r, a.x, a.y, a.r)
 833                 // The above code can't test intrinsic implementation, because the passed function is not called directly.
 834                 // The following code uses a closure to test the intrinsic version in case the function is intrinsified.
 835                 testMul("Mul intrinsic", func(x, y uint) (uint, uint) { return Mul(x, y) }, a.x, a.y, a.hi, a.lo)
 836                 testMul("Mul intrinsic symmetric", func(x, y uint) (uint, uint) { return Mul(x, y) }, a.y, a.x, a.hi, a.lo)
 837                 testDiv("Div intrinsic", func(hi, lo, y uint) (uint, uint) { return Div(hi, lo, y) }, a.hi, a.lo+a.r, a.y, a.x, a.r)
 838                 testDiv("Div intrinsic symmetric", func(hi, lo, y uint) (uint, uint) { return Div(hi, lo, y) }, a.hi, a.lo+a.r, a.x, a.y, a.r)
 839         }
 840 }
 841
 842 func TestMulDiv32(t *testing.T) {
 843         testMul := func(msg string, f func(x, y uint32) (hi, lo uint32), x, y, hi, lo uint32) {
 844                 hi1, lo1 := f(x, y)
 845                 if hi1 != hi || lo1 != lo {
 846                         t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
 847                 }
 848         }
 849         testDiv := func(msg string, f func(hi, lo, y uint32) (q, r uint32), hi, lo, y, q, r uint32) {
 850                 q1, r1 := f(hi, lo, y)
 851                 if q1 != q || r1 != r {
 852                         t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
 853                 }
 854         }
 855         for _, a := range []struct {
 856                 x, y      uint32
 857                 hi, lo, r uint32
 858         }{
 859                 {1 << 31, 2, 1, 0, 1},
 860                 {0xc47dfa8c, 50911, 0x98a4, 0x998587f4, 13},
 861                 {_M32, _M32, _M32 - 1, 1, 42},
 862         } {
 863                 testMul("Mul32", Mul32, a.x, a.y, a.hi, a.lo)
 864                 testMul("Mul32 symmetric", Mul32, a.y, a.x, a.hi, a.lo)
 865                 testDiv("Div32", Div32, a.hi, a.lo+a.r, a.y, a.x, a.r)
 866                 testDiv("Div32 symmetric", Div32, a.hi, a.lo+a.r, a.x, a.y, a.r)
 867         }
 868 }
 869
 870 func TestMulDiv64(t *testing.T) {
 871         testMul := func(msg string, f func(x, y uint64) (hi, lo uint64), x, y, hi, lo uint64) {
 872                 hi1, lo1 := f(x, y)
 873                 if hi1 != hi || lo1 != lo {
 874                         t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
 875                 }
 876         }
 877         testDiv := func(msg string, f func(hi, lo, y uint64) (q, r uint64), hi, lo, y, q, r uint64) {
 878                 q1, r1 := f(hi, lo, y)
 879                 if q1 != q || r1 != r {
 880                         t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
 881                 }
 882         }
 883         for _, a := range []struct {
 884                 x, y      uint64
 885                 hi, lo, r uint64
 886         }{
 887                 {1 << 63, 2, 1, 0, 1},
 888                 {0x3626229738a3b9, 0xd8988a9f1cc4a61, 0x2dd0712657fe8, 0x9dd6a3364c358319, 13},
 889                 {_M64, _M64, _M64 - 1, 1, 42},
 890         } {
 891                 testMul("Mul64", Mul64, a.x, a.y, a.hi, a.lo)
 892                 testMul("Mul64 symmetric", Mul64, a.y, a.x, a.hi, a.lo)
 893                 testDiv("Div64", Div64, a.hi, a.lo+a.r, a.y, a.x, a.r)
 894                 testDiv("Div64 symmetric", Div64, a.hi, a.lo+a.r, a.x, a.y, a.r)
 895                 // The above code can't test intrinsic implementation, because the passed function is not called directly.
 896                 // The following code uses a closure to test the intrinsic version in case the function is intrinsified.
 897                 testMul("Mul64 intrinsic", func(x, y uint64) (uint64, uint64) { return Mul64(x, y) }, a.x, a.y, a.hi, a.lo)
 898                 testMul("Mul64 intrinsic symmetric", func(x, y uint64) (uint64, uint64) { return Mul64(x, y) }, a.y, a.x, a.hi, a.lo)
 899                 testDiv("Div64 intrinsic", func(hi, lo, y uint64) (uint64, uint64) { return Div64(hi, lo, y) }, a.hi, a.lo+a.r, a.y, a.x, a.r)
 900                 testDiv("Div64 intrinsic symmetric", func(hi, lo, y uint64) (uint64, uint64) { return Div64(hi, lo, y) }, a.hi, a.lo+a.r, a.x, a.y, a.r)
 901         }
 902 }
 903
 904 const (
 905         divZeroError  = "runtime error: integer divide by zero"
 906         overflowError = "runtime error: integer overflow"
 907 )
 908
 909 func TestDivPanicOverflow(t *testing.T) {
 910         // Expect a panic
 911         defer func() {
 912                 if err := recover(); err == nil {
 913                         t.Error("Div should have panicked when y<=hi")
 914                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
 915                         t.Errorf("Div expected panic: %q, got: %q ", overflowError, e.Error())
 916                 }
 917         }()
 918         q, r := Div(1, 0, 1)
 919         t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r)
 920 }
 921
 922 func TestDiv32PanicOverflow(t *testing.T) {
 923         // Expect a panic
 924         defer func() {
 925                 if err := recover(); err == nil {
 926                         t.Error("Div32 should have panicked when y<=hi")
 927                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
 928                         t.Errorf("Div32 expected panic: %q, got: %q ", overflowError, e.Error())
 929                 }
 930         }()
 931         q, r := Div32(1, 0, 1)
 932         t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r)
 933 }
 934
 935 func TestDiv64PanicOverflow(t *testing.T) {
 936         // Expect a panic
 937         defer func() {
 938                 if err := recover(); err == nil {
 939                         t.Error("Div64 should have panicked when y<=hi")
 940                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
 941                         t.Errorf("Div64 expected panic: %q, got: %q ", overflowError, e.Error())
 942                 }
 943         }()
 944         q, r := Div64(1, 0, 1)
 945         t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r)
 946 }
 947
 948 func TestDivPanicZero(t *testing.T) {
 949         // Expect a panic
 950         defer func() {
 951                 if err := recover(); err == nil {
 952                         t.Error("Div should have panicked when y==0")
 953                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
 954                         t.Errorf("Div expected panic: %q, got: %q ", divZeroError, e.Error())
 955                 }
 956         }()
 957         q, r := Div(1, 1, 0)
 958         t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r)
 959 }
 960
 961 func TestDiv32PanicZero(t *testing.T) {
 962         // Expect a panic
 963         defer func() {
 964                 if err := recover(); err == nil {
 965                         t.Error("Div32 should have panicked when y==0")
 966                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
 967                         t.Errorf("Div32 expected panic: %q, got: %q ", divZeroError, e.Error())
 968                 }
 969         }()
 970         q, r := Div32(1, 1, 0)
 971         t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r)
 972 }
 973
 974 func TestDiv64PanicZero(t *testing.T) {
 975         // Expect a panic
 976         defer func() {
 977                 if err := recover(); err == nil {
 978                         t.Error("Div64 should have panicked when y==0")
 979                 } else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
 980                         t.Errorf("Div64 expected panic: %q, got: %q ", divZeroError, e.Error())
 981                 }
 982         }()
 983         q, r := Div64(1, 1, 0)
 984         t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r)
 985 }
 986
 987 func BenchmarkAdd(b *testing.B) {
 988         var z, c uint
 989         for i := 0; i < b.N; i++ {
 990                 z, c = Add(uint(Input), uint(i), c)
 991         }
 992         Output = int(z + c)
 993 }
 994
 995 func BenchmarkAdd32(b *testing.B) {
 996         var z, c uint32
 997         for i := 0; i < b.N; i++ {
 998                 z, c = Add32(uint32(Input), uint32(i), c)
 999         }
1000         Output = int(z + c)
1001 }
1002
1003 func BenchmarkAdd64(b *testing.B) {
1004         var z, c uint64
1005         for i := 0; i < b.N; i++ {
1006                 z, c = Add64(uint64(Input), uint64(i), c)
1007         }
1008         Output = int(z + c)
1009 }
1010
1011 func BenchmarkAdd64multiple(b *testing.B) {
1012         var z0 = uint64(Input)
1013         var z1 = uint64(Input)
1014         var z2 = uint64(Input)
1015         var z3 = uint64(Input)
1016         for i := 0; i < b.N; i++ {
1017                 var c uint64
1018                 z0, c = Add64(z0, uint64(i), c)
1019                 z1, c = Add64(z1, uint64(i), c)
1020                 z2, c = Add64(z2, uint64(i), c)
1021                 z3, _ = Add64(z3, uint64(i), c)
1022         }
1023         Output = int(z0 + z1 + z2 + z3)
1024 }
1025
1026 func BenchmarkSub(b *testing.B) {
1027         var z, c uint
1028         for i := 0; i < b.N; i++ {
1029                 z, c = Sub(uint(Input), uint(i), c)
1030         }
1031         Output = int(z + c)
1032 }
1033
1034 func BenchmarkSub32(b *testing.B) {
1035         var z, c uint32
1036         for i := 0; i < b.N; i++ {
1037                 z, c = Sub32(uint32(Input), uint32(i), c)
1038         }
1039         Output = int(z + c)
1040 }
1041
1042 func BenchmarkSub64(b *testing.B) {
1043         var z, c uint64
1044         for i := 0; i < b.N; i++ {
1045                 z, c = Sub64(uint64(Input), uint64(i), c)
1046         }
1047         Output = int(z + c)
1048 }
1049
1050 func BenchmarkSub64multiple(b *testing.B) {
1051         var z0 = uint64(Input)
1052         var z1 = uint64(Input)
1053         var z2 = uint64(Input)
1054         var z3 = uint64(Input)
1055         for i := 0; i < b.N; i++ {
1056                 var c uint64
1057                 z0, c = Sub64(z0, uint64(i), c)
1058                 z1, c = Sub64(z1, uint64(i), c)
1059                 z2, c = Sub64(z2, uint64(i), c)
1060                 z3, _ = Sub64(z3, uint64(i), c)
1061         }
1062         Output = int(z0 + z1 + z2 + z3)
1063 }
1064
1065 func BenchmarkMul(b *testing.B) {
1066         var hi, lo uint
1067         for i := 0; i < b.N; i++ {
1068                 hi, lo = Mul(uint(Input), uint(i))
1069         }
1070         Output = int(hi + lo)
1071 }
1072
1073 func BenchmarkMul32(b *testing.B) {
1074         var hi, lo uint32
1075         for i := 0; i < b.N; i++ {
1076                 hi, lo = Mul32(uint32(Input), uint32(i))
1077         }
1078         Output = int(hi + lo)
1079 }
1080
1081 func BenchmarkMul64(b *testing.B) {
1082         var hi, lo uint64
1083         for i := 0; i < b.N; i++ {
1084                 hi, lo = Mul64(uint64(Input), uint64(i))
1085         }
1086         Output = int(hi + lo)
1087 }
1088
1089 func BenchmarkDiv(b *testing.B) {
1090         var q, r uint
1091         for i := 0; i < b.N; i++ {
1092                 q, r = Div(1, uint(i), uint(Input))
1093         }
1094         Output = int(q + r)
1095 }
1096
1097 func BenchmarkDiv32(b *testing.B) {
1098         var q, r uint32
1099         for i := 0; i < b.N; i++ {
1100                 q, r = Div32(1, uint32(i), uint32(Input))
1101         }
1102         Output = int(q + r)
1103 }
1104
1105 func BenchmarkDiv64(b *testing.B) {
1106         var q, r uint64
1107         for i := 0; i < b.N; i++ {
1108                 q, r = Div64(1, uint64(i), uint64(Input))
1109         }
1110         Output = int(q + r)
1111 }
1112
1113 // ----------------------------------------------------------------------------
1114 // Testing support
1115
1116 type entry = struct {
1117         nlz, ntz, pop int
1118 }
1119
1120 // tab contains results for all uint8 values
1121 var tab [256]entry
1122
1123 func init() {
1124         tab[0] = entry{8, 8, 0}
1125         for i := 1; i < len(tab); i++ {
1126                 // nlz
1127                 x := i // x != 0
1128                 n := 0
1129                 for x&0x80 == 0 {
1130                         n++
1131                         x <<= 1
1132                 }
1133                 tab[i].nlz = n
1134
1135                 // ntz
1136                 x = i // x != 0
1137                 n = 0
1138                 for x&1 == 0 {
1139                         n++
1140                         x >>= 1
1141                 }
1142                 tab[i].ntz = n
1143
1144                 // pop
1145                 x = i // x != 0
1146                 n = 0
1147                 for x != 0 {
1148                         n += int(x & 1)
1149                         x >>= 1
1150                 }
1151                 tab[i].pop = n
1152         }
1153 }