...

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