...

Source file src/math/bits/bits_test.go

Documentation: math/bits

     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 TestAdd64OverflowPanic(t *testing.T) {
   810  	// Test that 64-bit overflow panics fire correctly.
   811  	// These are designed to improve coverage of compiler intrinsics.
   812  	tests := []func(uint64, uint64) uint64{
   813  		func(a, b uint64) uint64 {
   814  			x, c := Add64(a, b, 0)
   815  			if c > 0 {
   816  				panic("overflow")
   817  			}
   818  			return x
   819  		},
   820  		func(a, b uint64) uint64 {
   821  			x, c := Add64(a, b, 0)
   822  			if c != 0 {
   823  				panic("overflow")
   824  			}
   825  			return x
   826  		},
   827  		func(a, b uint64) uint64 {
   828  			x, c := Add64(a, b, 0)
   829  			if c == 1 {
   830  				panic("overflow")
   831  			}
   832  			return x
   833  		},
   834  		func(a, b uint64) uint64 {
   835  			x, c := Add64(a, b, 0)
   836  			if c != 1 {
   837  				return x
   838  			}
   839  			panic("overflow")
   840  		},
   841  		func(a, b uint64) uint64 {
   842  			x, c := Add64(a, b, 0)
   843  			if c == 0 {
   844  				return x
   845  			}
   846  			panic("overflow")
   847  		},
   848  	}
   849  	for _, test := range tests {
   850  		shouldPanic := func(f func()) {
   851  			defer func() {
   852  				if err := recover(); err == nil {
   853  					t.Fatalf("expected panic")
   854  				}
   855  			}()
   856  			f()
   857  		}
   858  
   859  		// overflow
   860  		shouldPanic(func() { test(_M64, 1) })
   861  		shouldPanic(func() { test(1, _M64) })
   862  		shouldPanic(func() { test(_M64, _M64) })
   863  
   864  		// no overflow
   865  		test(_M64, 0)
   866  		test(0, 0)
   867  		test(1, 1)
   868  	}
   869  }
   870  
   871  func TestSub64OverflowPanic(t *testing.T) {
   872  	// Test that 64-bit overflow panics fire correctly.
   873  	// These are designed to improve coverage of compiler intrinsics.
   874  	tests := []func(uint64, uint64) uint64{
   875  		func(a, b uint64) uint64 {
   876  			x, c := Sub64(a, b, 0)
   877  			if c > 0 {
   878  				panic("overflow")
   879  			}
   880  			return x
   881  		},
   882  		func(a, b uint64) uint64 {
   883  			x, c := Sub64(a, b, 0)
   884  			if c != 0 {
   885  				panic("overflow")
   886  			}
   887  			return x
   888  		},
   889  		func(a, b uint64) uint64 {
   890  			x, c := Sub64(a, b, 0)
   891  			if c == 1 {
   892  				panic("overflow")
   893  			}
   894  			return x
   895  		},
   896  		func(a, b uint64) uint64 {
   897  			x, c := Sub64(a, b, 0)
   898  			if c != 1 {
   899  				return x
   900  			}
   901  			panic("overflow")
   902  		},
   903  		func(a, b uint64) uint64 {
   904  			x, c := Sub64(a, b, 0)
   905  			if c == 0 {
   906  				return x
   907  			}
   908  			panic("overflow")
   909  		},
   910  	}
   911  	for _, test := range tests {
   912  		shouldPanic := func(f func()) {
   913  			defer func() {
   914  				if err := recover(); err == nil {
   915  					t.Fatalf("expected panic")
   916  				}
   917  			}()
   918  			f()
   919  		}
   920  
   921  		// overflow
   922  		shouldPanic(func() { test(0, 1) })
   923  		shouldPanic(func() { test(1, _M64) })
   924  		shouldPanic(func() { test(_M64-1, _M64) })
   925  
   926  		// no overflow
   927  		test(_M64, 0)
   928  		test(0, 0)
   929  		test(1, 1)
   930  	}
   931  }
   932  
   933  func TestMulDiv(t *testing.T) {
   934  	testMul := func(msg string, f func(x, y uint) (hi, lo uint), x, y, hi, lo uint) {
   935  		hi1, lo1 := f(x, y)
   936  		if hi1 != hi || lo1 != lo {
   937  			t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
   938  		}
   939  	}
   940  	testDiv := func(msg string, f func(hi, lo, y uint) (q, r uint), hi, lo, y, q, r uint) {
   941  		q1, r1 := f(hi, lo, y)
   942  		if q1 != q || r1 != r {
   943  			t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
   944  		}
   945  	}
   946  	for _, a := range []struct {
   947  		x, y      uint
   948  		hi, lo, r uint
   949  	}{
   950  		{1 << (UintSize - 1), 2, 1, 0, 1},
   951  		{_M, _M, _M - 1, 1, 42},
   952  	} {
   953  		testMul("Mul", Mul, a.x, a.y, a.hi, a.lo)
   954  		testMul("Mul symmetric", Mul, a.y, a.x, a.hi, a.lo)
   955  		testDiv("Div", Div, a.hi, a.lo+a.r, a.y, a.x, a.r)
   956  		testDiv("Div symmetric", Div, a.hi, a.lo+a.r, a.x, a.y, a.r)
   957  		// The above code can't test intrinsic implementation, because the passed function is not called directly.
   958  		// The following code uses a closure to test the intrinsic version in case the function is intrinsified.
   959  		testMul("Mul intrinsic", func(x, y uint) (uint, uint) { return Mul(x, y) }, a.x, a.y, a.hi, a.lo)
   960  		testMul("Mul intrinsic symmetric", func(x, y uint) (uint, uint) { return Mul(x, y) }, a.y, a.x, a.hi, a.lo)
   961  		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)
   962  		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)
   963  	}
   964  }
   965  
   966  func TestMulDiv32(t *testing.T) {
   967  	testMul := func(msg string, f func(x, y uint32) (hi, lo uint32), x, y, hi, lo uint32) {
   968  		hi1, lo1 := f(x, y)
   969  		if hi1 != hi || lo1 != lo {
   970  			t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
   971  		}
   972  	}
   973  	testDiv := func(msg string, f func(hi, lo, y uint32) (q, r uint32), hi, lo, y, q, r uint32) {
   974  		q1, r1 := f(hi, lo, y)
   975  		if q1 != q || r1 != r {
   976  			t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
   977  		}
   978  	}
   979  	for _, a := range []struct {
   980  		x, y      uint32
   981  		hi, lo, r uint32
   982  	}{
   983  		{1 << 31, 2, 1, 0, 1},
   984  		{0xc47dfa8c, 50911, 0x98a4, 0x998587f4, 13},
   985  		{_M32, _M32, _M32 - 1, 1, 42},
   986  	} {
   987  		testMul("Mul32", Mul32, a.x, a.y, a.hi, a.lo)
   988  		testMul("Mul32 symmetric", Mul32, a.y, a.x, a.hi, a.lo)
   989  		testDiv("Div32", Div32, a.hi, a.lo+a.r, a.y, a.x, a.r)
   990  		testDiv("Div32 symmetric", Div32, a.hi, a.lo+a.r, a.x, a.y, a.r)
   991  	}
   992  }
   993  
   994  func TestMulDiv64(t *testing.T) {
   995  	testMul := func(msg string, f func(x, y uint64) (hi, lo uint64), x, y, hi, lo uint64) {
   996  		hi1, lo1 := f(x, y)
   997  		if hi1 != hi || lo1 != lo {
   998  			t.Errorf("%s: got hi:lo = %#x:%#x; want %#x:%#x", msg, hi1, lo1, hi, lo)
   999  		}
  1000  	}
  1001  	testDiv := func(msg string, f func(hi, lo, y uint64) (q, r uint64), hi, lo, y, q, r uint64) {
  1002  		q1, r1 := f(hi, lo, y)
  1003  		if q1 != q || r1 != r {
  1004  			t.Errorf("%s: got q:r = %#x:%#x; want %#x:%#x", msg, q1, r1, q, r)
  1005  		}
  1006  	}
  1007  	for _, a := range []struct {
  1008  		x, y      uint64
  1009  		hi, lo, r uint64
  1010  	}{
  1011  		{1 << 63, 2, 1, 0, 1},
  1012  		{0x3626229738a3b9, 0xd8988a9f1cc4a61, 0x2dd0712657fe8, 0x9dd6a3364c358319, 13},
  1013  		{_M64, _M64, _M64 - 1, 1, 42},
  1014  	} {
  1015  		testMul("Mul64", Mul64, a.x, a.y, a.hi, a.lo)
  1016  		testMul("Mul64 symmetric", Mul64, a.y, a.x, a.hi, a.lo)
  1017  		testDiv("Div64", Div64, a.hi, a.lo+a.r, a.y, a.x, a.r)
  1018  		testDiv("Div64 symmetric", Div64, a.hi, a.lo+a.r, a.x, a.y, a.r)
  1019  		// The above code can't test intrinsic implementation, because the passed function is not called directly.
  1020  		// The following code uses a closure to test the intrinsic version in case the function is intrinsified.
  1021  		testMul("Mul64 intrinsic", func(x, y uint64) (uint64, uint64) { return Mul64(x, y) }, a.x, a.y, a.hi, a.lo)
  1022  		testMul("Mul64 intrinsic symmetric", func(x, y uint64) (uint64, uint64) { return Mul64(x, y) }, a.y, a.x, a.hi, a.lo)
  1023  		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)
  1024  		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)
  1025  	}
  1026  }
  1027  
  1028  const (
  1029  	divZeroError  = "runtime error: integer divide by zero"
  1030  	overflowError = "runtime error: integer overflow"
  1031  )
  1032  
  1033  func TestDivPanicOverflow(t *testing.T) {
  1034  	// Expect a panic
  1035  	defer func() {
  1036  		if err := recover(); err == nil {
  1037  			t.Error("Div should have panicked when y<=hi")
  1038  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
  1039  			t.Errorf("Div expected panic: %q, got: %q ", overflowError, e.Error())
  1040  		}
  1041  	}()
  1042  	q, r := Div(1, 0, 1)
  1043  	t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r)
  1044  }
  1045  
  1046  func TestDiv32PanicOverflow(t *testing.T) {
  1047  	// Expect a panic
  1048  	defer func() {
  1049  		if err := recover(); err == nil {
  1050  			t.Error("Div32 should have panicked when y<=hi")
  1051  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
  1052  			t.Errorf("Div32 expected panic: %q, got: %q ", overflowError, e.Error())
  1053  		}
  1054  	}()
  1055  	q, r := Div32(1, 0, 1)
  1056  	t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r)
  1057  }
  1058  
  1059  func TestDiv64PanicOverflow(t *testing.T) {
  1060  	// Expect a panic
  1061  	defer func() {
  1062  		if err := recover(); err == nil {
  1063  			t.Error("Div64 should have panicked when y<=hi")
  1064  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != overflowError {
  1065  			t.Errorf("Div64 expected panic: %q, got: %q ", overflowError, e.Error())
  1066  		}
  1067  	}()
  1068  	q, r := Div64(1, 0, 1)
  1069  	t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r)
  1070  }
  1071  
  1072  func TestDivPanicZero(t *testing.T) {
  1073  	// Expect a panic
  1074  	defer func() {
  1075  		if err := recover(); err == nil {
  1076  			t.Error("Div should have panicked when y==0")
  1077  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
  1078  			t.Errorf("Div expected panic: %q, got: %q ", divZeroError, e.Error())
  1079  		}
  1080  	}()
  1081  	q, r := Div(1, 1, 0)
  1082  	t.Errorf("undefined q, r = %v, %v calculated when Div should have panicked", q, r)
  1083  }
  1084  
  1085  func TestDiv32PanicZero(t *testing.T) {
  1086  	// Expect a panic
  1087  	defer func() {
  1088  		if err := recover(); err == nil {
  1089  			t.Error("Div32 should have panicked when y==0")
  1090  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
  1091  			t.Errorf("Div32 expected panic: %q, got: %q ", divZeroError, e.Error())
  1092  		}
  1093  	}()
  1094  	q, r := Div32(1, 1, 0)
  1095  	t.Errorf("undefined q, r = %v, %v calculated when Div32 should have panicked", q, r)
  1096  }
  1097  
  1098  func TestDiv64PanicZero(t *testing.T) {
  1099  	// Expect a panic
  1100  	defer func() {
  1101  		if err := recover(); err == nil {
  1102  			t.Error("Div64 should have panicked when y==0")
  1103  		} else if e, ok := err.(runtime.Error); !ok || e.Error() != divZeroError {
  1104  			t.Errorf("Div64 expected panic: %q, got: %q ", divZeroError, e.Error())
  1105  		}
  1106  	}()
  1107  	q, r := Div64(1, 1, 0)
  1108  	t.Errorf("undefined q, r = %v, %v calculated when Div64 should have panicked", q, r)
  1109  }
  1110  
  1111  func TestRem32(t *testing.T) {
  1112  	// Sanity check: for non-oveflowing dividends, the result is the
  1113  	// same as the rem returned by Div32
  1114  	hi, lo, y := uint32(510510), uint32(9699690), uint32(510510+1) // ensure hi < y
  1115  	for i := 0; i < 1000; i++ {
  1116  		r := Rem32(hi, lo, y)
  1117  		_, r2 := Div32(hi, lo, y)
  1118  		if r != r2 {
  1119  			t.Errorf("Rem32(%v, %v, %v) returned %v, but Div32 returned rem %v", hi, lo, y, r, r2)
  1120  		}
  1121  		y += 13
  1122  	}
  1123  }
  1124  
  1125  func TestRem32Overflow(t *testing.T) {
  1126  	// To trigger a quotient overflow, we need y <= hi
  1127  	hi, lo, y := uint32(510510), uint32(9699690), uint32(7)
  1128  	for i := 0; i < 1000; i++ {
  1129  		r := Rem32(hi, lo, y)
  1130  		_, r2 := Div64(0, uint64(hi)<<32|uint64(lo), uint64(y))
  1131  		if r != uint32(r2) {
  1132  			t.Errorf("Rem32(%v, %v, %v) returned %v, but Div64 returned rem %v", hi, lo, y, r, r2)
  1133  		}
  1134  		y += 13
  1135  	}
  1136  }
  1137  
  1138  func TestRem64(t *testing.T) {
  1139  	// Sanity check: for non-oveflowing dividends, the result is the
  1140  	// same as the rem returned by Div64
  1141  	hi, lo, y := uint64(510510), uint64(9699690), uint64(510510+1) // ensure hi < y
  1142  	for i := 0; i < 1000; i++ {
  1143  		r := Rem64(hi, lo, y)
  1144  		_, r2 := Div64(hi, lo, y)
  1145  		if r != r2 {
  1146  			t.Errorf("Rem64(%v, %v, %v) returned %v, but Div64 returned rem %v", hi, lo, y, r, r2)
  1147  		}
  1148  		y += 13
  1149  	}
  1150  }
  1151  
  1152  func TestRem64Overflow(t *testing.T) {
  1153  	Rem64Tests := []struct {
  1154  		hi, lo, y uint64
  1155  		rem       uint64
  1156  	}{
  1157  		// Testcases computed using Python 3, as:
  1158  		//   >>> hi = 42; lo = 1119; y = 42
  1159  		//   >>> ((hi<<64)+lo) % y
  1160  		{42, 1119, 42, 27},
  1161  		{42, 1119, 38, 9},
  1162  		{42, 1119, 26, 23},
  1163  		{469, 0, 467, 271},
  1164  		{469, 0, 113, 58},
  1165  		{111111, 111111, 1171, 803},
  1166  		{3968194946088682615, 3192705705065114702, 1000037, 56067},
  1167  	}
  1168  
  1169  	for _, rt := range Rem64Tests {
  1170  		if rt.hi < rt.y {
  1171  			t.Fatalf("Rem64(%v, %v, %v) is not a test with quo overflow", rt.hi, rt.lo, rt.y)
  1172  		}
  1173  		rem := Rem64(rt.hi, rt.lo, rt.y)
  1174  		if rem != rt.rem {
  1175  			t.Errorf("Rem64(%v, %v, %v) returned %v, wanted %v",
  1176  				rt.hi, rt.lo, rt.y, rem, rt.rem)
  1177  		}
  1178  	}
  1179  }
  1180  
  1181  func BenchmarkAdd(b *testing.B) {
  1182  	var z, c uint
  1183  	for i := 0; i < b.N; i++ {
  1184  		z, c = Add(uint(Input), uint(i), c)
  1185  	}
  1186  	Output = int(z + c)
  1187  }
  1188  
  1189  func BenchmarkAdd32(b *testing.B) {
  1190  	var z, c uint32
  1191  	for i := 0; i < b.N; i++ {
  1192  		z, c = Add32(uint32(Input), uint32(i), c)
  1193  	}
  1194  	Output = int(z + c)
  1195  }
  1196  
  1197  func BenchmarkAdd64(b *testing.B) {
  1198  	var z, c uint64
  1199  	for i := 0; i < b.N; i++ {
  1200  		z, c = Add64(uint64(Input), uint64(i), c)
  1201  	}
  1202  	Output = int(z + c)
  1203  }
  1204  
  1205  func BenchmarkAdd64multiple(b *testing.B) {
  1206  	var z0 = uint64(Input)
  1207  	var z1 = uint64(Input)
  1208  	var z2 = uint64(Input)
  1209  	var z3 = uint64(Input)
  1210  	for i := 0; i < b.N; i++ {
  1211  		var c uint64
  1212  		z0, c = Add64(z0, uint64(i), c)
  1213  		z1, c = Add64(z1, uint64(i), c)
  1214  		z2, c = Add64(z2, uint64(i), c)
  1215  		z3, _ = Add64(z3, uint64(i), c)
  1216  	}
  1217  	Output = int(z0 + z1 + z2 + z3)
  1218  }
  1219  
  1220  func BenchmarkSub(b *testing.B) {
  1221  	var z, c uint
  1222  	for i := 0; i < b.N; i++ {
  1223  		z, c = Sub(uint(Input), uint(i), c)
  1224  	}
  1225  	Output = int(z + c)
  1226  }
  1227  
  1228  func BenchmarkSub32(b *testing.B) {
  1229  	var z, c uint32
  1230  	for i := 0; i < b.N; i++ {
  1231  		z, c = Sub32(uint32(Input), uint32(i), c)
  1232  	}
  1233  	Output = int(z + c)
  1234  }
  1235  
  1236  func BenchmarkSub64(b *testing.B) {
  1237  	var z, c uint64
  1238  	for i := 0; i < b.N; i++ {
  1239  		z, c = Sub64(uint64(Input), uint64(i), c)
  1240  	}
  1241  	Output = int(z + c)
  1242  }
  1243  
  1244  func BenchmarkSub64multiple(b *testing.B) {
  1245  	var z0 = uint64(Input)
  1246  	var z1 = uint64(Input)
  1247  	var z2 = uint64(Input)
  1248  	var z3 = uint64(Input)
  1249  	for i := 0; i < b.N; i++ {
  1250  		var c uint64
  1251  		z0, c = Sub64(z0, uint64(i), c)
  1252  		z1, c = Sub64(z1, uint64(i), c)
  1253  		z2, c = Sub64(z2, uint64(i), c)
  1254  		z3, _ = Sub64(z3, uint64(i), c)
  1255  	}
  1256  	Output = int(z0 + z1 + z2 + z3)
  1257  }
  1258  
  1259  func BenchmarkMul(b *testing.B) {
  1260  	var hi, lo uint
  1261  	for i := 0; i < b.N; i++ {
  1262  		hi, lo = Mul(uint(Input), uint(i))
  1263  	}
  1264  	Output = int(hi + lo)
  1265  }
  1266  
  1267  func BenchmarkMul32(b *testing.B) {
  1268  	var hi, lo uint32
  1269  	for i := 0; i < b.N; i++ {
  1270  		hi, lo = Mul32(uint32(Input), uint32(i))
  1271  	}
  1272  	Output = int(hi + lo)
  1273  }
  1274  
  1275  func BenchmarkMul64(b *testing.B) {
  1276  	var hi, lo uint64
  1277  	for i := 0; i < b.N; i++ {
  1278  		hi, lo = Mul64(uint64(Input), uint64(i))
  1279  	}
  1280  	Output = int(hi + lo)
  1281  }
  1282  
  1283  func BenchmarkDiv(b *testing.B) {
  1284  	var q, r uint
  1285  	for i := 0; i < b.N; i++ {
  1286  		q, r = Div(1, uint(i), uint(Input))
  1287  	}
  1288  	Output = int(q + r)
  1289  }
  1290  
  1291  func BenchmarkDiv32(b *testing.B) {
  1292  	var q, r uint32
  1293  	for i := 0; i < b.N; i++ {
  1294  		q, r = Div32(1, uint32(i), uint32(Input))
  1295  	}
  1296  	Output = int(q + r)
  1297  }
  1298  
  1299  func BenchmarkDiv64(b *testing.B) {
  1300  	var q, r uint64
  1301  	for i := 0; i < b.N; i++ {
  1302  		q, r = Div64(1, uint64(i), uint64(Input))
  1303  	}
  1304  	Output = int(q + r)
  1305  }
  1306  
  1307  // ----------------------------------------------------------------------------
  1308  // Testing support
  1309  
  1310  type entry = struct {
  1311  	nlz, ntz, pop int
  1312  }
  1313  
  1314  // tab contains results for all uint8 values
  1315  var tab [256]entry
  1316  
  1317  func init() {
  1318  	tab[0] = entry{8, 8, 0}
  1319  	for i := 1; i < len(tab); i++ {
  1320  		// nlz
  1321  		x := i // x != 0
  1322  		n := 0
  1323  		for x&0x80 == 0 {
  1324  			n++
  1325  			x <<= 1
  1326  		}
  1327  		tab[i].nlz = n
  1328  
  1329  		// ntz
  1330  		x = i // x != 0
  1331  		n = 0
  1332  		for x&1 == 0 {
  1333  			n++
  1334  			x >>= 1
  1335  		}
  1336  		tab[i].ntz = n
  1337  
  1338  		// pop
  1339  		x = i // x != 0
  1340  		n = 0
  1341  		for x != 0 {
  1342  			n += int(x & 1)
  1343  			x >>= 1
  1344  		}
  1345  		tab[i].pop = n
  1346  	}
  1347  }
  1348  

View as plain text