Home | History | Annotate | Download | only in 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
      6 
      7 import (
      8 	"testing"
      9 	"unsafe"
     10 )
     11 
     12 func TestUintSize(t *testing.T) {
     13 	var x uint
     14 	if want := unsafe.Sizeof(x) * 8; UintSize != want {
     15 		t.Fatalf("UintSize = %d; want %d", UintSize, want)
     16 	}
     17 }
     18 
     19 func TestLeadingZeros(t *testing.T) {
     20 	for i := 0; i < 256; i++ {
     21 		nlz := tab[i].nlz
     22 		for k := 0; k < 64-8; k++ {
     23 			x := uint64(i) << uint(k)
     24 			if x <= 1<<8-1 {
     25 				got := LeadingZeros8(uint8(x))
     26 				want := nlz - k + (8 - 8)
     27 				if x == 0 {
     28 					want = 8
     29 				}
     30 				if got != want {
     31 					t.Fatalf("LeadingZeros8(%#02x) == %d; want %d", x, got, want)
     32 				}
     33 			}
     34 
     35 			if x <= 1<<16-1 {
     36 				got := LeadingZeros16(uint16(x))
     37 				want := nlz - k + (16 - 8)
     38 				if x == 0 {
     39 					want = 16
     40 				}
     41 				if got != want {
     42 					t.Fatalf("LeadingZeros16(%#04x) == %d; want %d", x, got, want)
     43 				}
     44 			}
     45 
     46 			if x <= 1<<32-1 {
     47 				got := LeadingZeros32(uint32(x))
     48 				want := nlz - k + (32 - 8)
     49 				if x == 0 {
     50 					want = 32
     51 				}
     52 				if got != want {
     53 					t.Fatalf("LeadingZeros32(%#08x) == %d; want %d", x, got, want)
     54 				}
     55 				if UintSize == 32 {
     56 					got = LeadingZeros(uint(x))
     57 					if got != want {
     58 						t.Fatalf("LeadingZeros(%#08x) == %d; want %d", x, got, want)
     59 					}
     60 				}
     61 			}
     62 
     63 			if x <= 1<<64-1 {
     64 				got := LeadingZeros64(uint64(x))
     65 				want := nlz - k + (64 - 8)
     66 				if x == 0 {
     67 					want = 64
     68 				}
     69 				if got != want {
     70 					t.Fatalf("LeadingZeros64(%#016x) == %d; want %d", x, got, want)
     71 				}
     72 				if UintSize == 64 {
     73 					got = LeadingZeros(uint(x))
     74 					if got != want {
     75 						t.Fatalf("LeadingZeros(%#016x) == %d; want %d", x, got, want)
     76 					}
     77 				}
     78 			}
     79 		}
     80 	}
     81 }
     82 
     83 // Exported (global) variable serving as input for some
     84 // of the benchmarks to ensure side-effect free calls
     85 // are not optimized away.
     86 var Input uint64 = deBruijn64
     87 
     88 // Exported (global) variable to store function results
     89 // during benchmarking to ensure side-effect free calls
     90 // are not optimized away.
     91 var Output int
     92 
     93 func BenchmarkLeadingZeros(b *testing.B) {
     94 	var s int
     95 	for i := 0; i < b.N; i++ {
     96 		s += LeadingZeros(uint(Input) >> (uint(i) % UintSize))
     97 	}
     98 	Output = s
     99 }
    100 
    101 func BenchmarkLeadingZeros8(b *testing.B) {
    102 	var s int
    103 	for i := 0; i < b.N; i++ {
    104 		s += LeadingZeros8(uint8(Input) >> (uint(i) % 8))
    105 	}
    106 	Output = s
    107 }
    108 
    109 func BenchmarkLeadingZeros16(b *testing.B) {
    110 	var s int
    111 	for i := 0; i < b.N; i++ {
    112 		s += LeadingZeros16(uint16(Input) >> (uint(i) % 16))
    113 	}
    114 	Output = s
    115 }
    116 
    117 func BenchmarkLeadingZeros32(b *testing.B) {
    118 	var s int
    119 	for i := 0; i < b.N; i++ {
    120 		s += LeadingZeros32(uint32(Input) >> (uint(i) % 32))
    121 	}
    122 	Output = s
    123 }
    124 
    125 func BenchmarkLeadingZeros64(b *testing.B) {
    126 	var s int
    127 	for i := 0; i < b.N; i++ {
    128 		s += LeadingZeros64(uint64(Input) >> (uint(i) % 64))
    129 	}
    130 	Output = s
    131 }
    132 
    133 func TestTrailingZeros(t *testing.T) {
    134 	for i := 0; i < 256; i++ {
    135 		ntz := tab[i].ntz
    136 		for k := 0; k < 64-8; k++ {
    137 			x := uint64(i) << uint(k)
    138 			want := ntz + k
    139 			if x <= 1<<8-1 {
    140 				got := TrailingZeros8(uint8(x))
    141 				if x == 0 {
    142 					want = 8
    143 				}
    144 				if got != want {
    145 					t.Fatalf("TrailingZeros8(%#02x) == %d; want %d", x, got, want)
    146 				}
    147 			}
    148 
    149 			if x <= 1<<16-1 {
    150 				got := TrailingZeros16(uint16(x))
    151 				if x == 0 {
    152 					want = 16
    153 				}
    154 				if got != want {
    155 					t.Fatalf("TrailingZeros16(%#04x) == %d; want %d", x, got, want)
    156 				}
    157 			}
    158 
    159 			if x <= 1<<32-1 {
    160 				got := TrailingZeros32(uint32(x))
    161 				if x == 0 {
    162 					want = 32
    163 				}
    164 				if got != want {
    165 					t.Fatalf("TrailingZeros32(%#08x) == %d; want %d", x, got, want)
    166 				}
    167 				if UintSize == 32 {
    168 					got = TrailingZeros(uint(x))
    169 					if got != want {
    170 						t.Fatalf("TrailingZeros(%#08x) == %d; want %d", x, got, want)
    171 					}
    172 				}
    173 			}
    174 
    175 			if x <= 1<<64-1 {
    176 				got := TrailingZeros64(uint64(x))
    177 				if x == 0 {
    178 					want = 64
    179 				}
    180 				if got != want {
    181 					t.Fatalf("TrailingZeros64(%#016x) == %d; want %d", x, got, want)
    182 				}
    183 				if UintSize == 64 {
    184 					got = TrailingZeros(uint(x))
    185 					if got != want {
    186 						t.Fatalf("TrailingZeros(%#016x) == %d; want %d", x, got, want)
    187 					}
    188 				}
    189 			}
    190 		}
    191 	}
    192 }
    193 
    194 func BenchmarkTrailingZeros(b *testing.B) {
    195 	var s int
    196 	for i := 0; i < b.N; i++ {
    197 		s += TrailingZeros(uint(Input) << (uint(i) % UintSize))
    198 	}
    199 	Output = s
    200 }
    201 
    202 func BenchmarkTrailingZeros8(b *testing.B) {
    203 	var s int
    204 	for i := 0; i < b.N; i++ {
    205 		s += TrailingZeros8(uint8(Input) << (uint(i) % 8))
    206 	}
    207 	Output = s
    208 }
    209 
    210 func BenchmarkTrailingZeros16(b *testing.B) {
    211 	var s int
    212 	for i := 0; i < b.N; i++ {
    213 		s += TrailingZeros16(uint16(Input) << (uint(i) % 16))
    214 	}
    215 	Output = s
    216 }
    217 
    218 func BenchmarkTrailingZeros32(b *testing.B) {
    219 	var s int
    220 	for i := 0; i < b.N; i++ {
    221 		s += TrailingZeros32(uint32(Input) << (uint(i) % 32))
    222 	}
    223 	Output = s
    224 }
    225 
    226 func BenchmarkTrailingZeros64(b *testing.B) {
    227 	var s int
    228 	for i := 0; i < b.N; i++ {
    229 		s += TrailingZeros64(uint64(Input) << (uint(i) % 64))
    230 	}
    231 	Output = s
    232 }
    233 
    234 func TestOnesCount(t *testing.T) {
    235 	var x uint64
    236 	for i := 0; i <= 64; i++ {
    237 		testOnesCount(t, x, i)
    238 		x = x<<1 | 1
    239 	}
    240 
    241 	for i := 64; i >= 0; i-- {
    242 		testOnesCount(t, x, i)
    243 		x = x << 1
    244 	}
    245 
    246 	for i := 0; i < 256; i++ {
    247 		for k := 0; k < 64-8; k++ {
    248 			testOnesCount(t, uint64(i)<<uint(k), tab[i].pop)
    249 		}
    250 	}
    251 }
    252 
    253 func testOnesCount(t *testing.T, x uint64, want int) {
    254 	if x <= 1<<8-1 {
    255 		got := OnesCount8(uint8(x))
    256 		if got != want {
    257 			t.Fatalf("OnesCount8(%#02x) == %d; want %d", uint8(x), got, want)
    258 		}
    259 	}
    260 
    261 	if x <= 1<<16-1 {
    262 		got := OnesCount16(uint16(x))
    263 		if got != want {
    264 			t.Fatalf("OnesCount16(%#04x) == %d; want %d", uint16(x), got, want)
    265 		}
    266 	}
    267 
    268 	if x <= 1<<32-1 {
    269 		got := OnesCount32(uint32(x))
    270 		if got != want {
    271 			t.Fatalf("OnesCount32(%#08x) == %d; want %d", uint32(x), got, want)
    272 		}
    273 		if UintSize == 32 {
    274 			got = OnesCount(uint(x))
    275 			if got != want {
    276 				t.Fatalf("OnesCount(%#08x) == %d; want %d", uint32(x), got, want)
    277 			}
    278 		}
    279 	}
    280 
    281 	if x <= 1<<64-1 {
    282 		got := OnesCount64(uint64(x))
    283 		if got != want {
    284 			t.Fatalf("OnesCount64(%#016x) == %d; want %d", x, got, want)
    285 		}
    286 		if UintSize == 64 {
    287 			got = OnesCount(uint(x))
    288 			if got != want {
    289 				t.Fatalf("OnesCount(%#016x) == %d; want %d", x, got, want)
    290 			}
    291 		}
    292 	}
    293 }
    294 
    295 func BenchmarkOnesCount(b *testing.B) {
    296 	var s int
    297 	for i := 0; i < b.N; i++ {
    298 		s += OnesCount(uint(Input))
    299 	}
    300 	Output = s
    301 }
    302 
    303 func BenchmarkOnesCount8(b *testing.B) {
    304 	var s int
    305 	for i := 0; i < b.N; i++ {
    306 		s += OnesCount8(uint8(Input))
    307 	}
    308 	Output = s
    309 }
    310 
    311 func BenchmarkOnesCount16(b *testing.B) {
    312 	var s int
    313 	for i := 0; i < b.N; i++ {
    314 		s += OnesCount16(uint16(Input))
    315 	}
    316 	Output = s
    317 }
    318 
    319 func BenchmarkOnesCount32(b *testing.B) {
    320 	var s int
    321 	for i := 0; i < b.N; i++ {
    322 		s += OnesCount32(uint32(Input))
    323 	}
    324 	Output = s
    325 }
    326 
    327 func BenchmarkOnesCount64(b *testing.B) {
    328 	var s int
    329 	for i := 0; i < b.N; i++ {
    330 		s += OnesCount64(uint64(Input))
    331 	}
    332 	Output = s
    333 }
    334 
    335 func TestRotateLeft(t *testing.T) {
    336 	var m uint64 = deBruijn64
    337 
    338 	for k := uint(0); k < 128; k++ {
    339 		x8 := uint8(m)
    340 		got8 := RotateLeft8(x8, int(k))
    341 		want8 := x8<<(k&0x7) | x8>>(8-k&0x7)
    342 		if got8 != want8 {
    343 			t.Fatalf("RotateLeft8(%#02x, %d) == %#02x; want %#02x", x8, k, got8, want8)
    344 		}
    345 		got8 = RotateLeft8(want8, -int(k))
    346 		if got8 != x8 {
    347 			t.Fatalf("RotateLeft8(%#02x, -%d) == %#02x; want %#02x", want8, k, got8, x8)
    348 		}
    349 
    350 		x16 := uint16(m)
    351 		got16 := RotateLeft16(x16, int(k))
    352 		want16 := x16<<(k&0xf) | x16>>(16-k&0xf)
    353 		if got16 != want16 {
    354 			t.Fatalf("RotateLeft16(%#04x, %d) == %#04x; want %#04x", x16, k, got16, want16)
    355 		}
    356 		got16 = RotateLeft16(want16, -int(k))
    357 		if got16 != x16 {
    358 			t.Fatalf("RotateLeft16(%#04x, -%d) == %#04x; want %#04x", want16, k, got16, x16)
    359 		}
    360 
    361 		x32 := uint32(m)
    362 		got32 := RotateLeft32(x32, int(k))
    363 		want32 := x32<<(k&0x1f) | x32>>(32-k&0x1f)
    364 		if got32 != want32 {
    365 			t.Fatalf("RotateLeft32(%#08x, %d) == %#08x; want %#08x", x32, k, got32, want32)
    366 		}
    367 		got32 = RotateLeft32(want32, -int(k))
    368 		if got32 != x32 {
    369 			t.Fatalf("RotateLeft32(%#08x, -%d) == %#08x; want %#08x", want32, k, got32, x32)
    370 		}
    371 		if UintSize == 32 {
    372 			x := uint(m)
    373 			got := RotateLeft(x, int(k))
    374 			want := x<<(k&0x1f) | x>>(32-k&0x1f)
    375 			if got != want {
    376 				t.Fatalf("RotateLeft(%#08x, %d) == %#08x; want %#08x", x, k, got, want)
    377 			}
    378 			got = RotateLeft(want, -int(k))
    379 			if got != x {
    380 				t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x)
    381 			}
    382 		}
    383 
    384 		x64 := uint64(m)
    385 		got64 := RotateLeft64(x64, int(k))
    386 		want64 := x64<<(k&0x3f) | x64>>(64-k&0x3f)
    387 		if got64 != want64 {
    388 			t.Fatalf("RotateLeft64(%#016x, %d) == %#016x; want %#016x", x64, k, got64, want64)
    389 		}
    390 		got64 = RotateLeft64(want64, -int(k))
    391 		if got64 != x64 {
    392 			t.Fatalf("RotateLeft64(%#016x, -%d) == %#016x; want %#016x", want64, k, got64, x64)
    393 		}
    394 		if UintSize == 64 {
    395 			x := uint(m)
    396 			got := RotateLeft(x, int(k))
    397 			want := x<<(k&0x3f) | x>>(64-k&0x3f)
    398 			if got != want {
    399 				t.Fatalf("RotateLeft(%#016x, %d) == %#016x; want %#016x", x, k, got, want)
    400 			}
    401 			got = RotateLeft(want, -int(k))
    402 			if got != x {
    403 				t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x)
    404 			}
    405 		}
    406 	}
    407 }
    408 
    409 func BenchmarkRotateLeft(b *testing.B) {
    410 	var s uint
    411 	for i := 0; i < b.N; i++ {
    412 		s += RotateLeft(uint(Input), i)
    413 	}
    414 	Output = int(s)
    415 }
    416 
    417 func BenchmarkRotateLeft8(b *testing.B) {
    418 	var s uint8
    419 	for i := 0; i < b.N; i++ {
    420 		s += RotateLeft8(uint8(Input), i)
    421 	}
    422 	Output = int(s)
    423 }
    424 
    425 func BenchmarkRotateLeft16(b *testing.B) {
    426 	var s uint16
    427 	for i := 0; i < b.N; i++ {
    428 		s += RotateLeft16(uint16(Input), i)
    429 	}
    430 	Output = int(s)
    431 }
    432 
    433 func BenchmarkRotateLeft32(b *testing.B) {
    434 	var s uint32
    435 	for i := 0; i < b.N; i++ {
    436 		s += RotateLeft32(uint32(Input), i)
    437 	}
    438 	Output = int(s)
    439 }
    440 
    441 func BenchmarkRotateLeft64(b *testing.B) {
    442 	var s uint64
    443 	for i := 0; i < b.N; i++ {
    444 		s += RotateLeft64(uint64(Input), i)
    445 	}
    446 	Output = int(s)
    447 }
    448 
    449 func TestReverse(t *testing.T) {
    450 	// test each bit
    451 	for i := uint(0); i < 64; i++ {
    452 		testReverse(t, uint64(1)<<i, uint64(1)<<(63-i))
    453 	}
    454 
    455 	// test a few patterns
    456 	for _, test := range []struct {
    457 		x, r uint64
    458 	}{
    459 		{0, 0},
    460 		{0x1, 0x8 << 60},
    461 		{0x2, 0x4 << 60},
    462 		{0x3, 0xc << 60},
    463 		{0x4, 0x2 << 60},
    464 		{0x5, 0xa << 60},
    465 		{0x6, 0x6 << 60},
    466 		{0x7, 0xe << 60},
    467 		{0x8, 0x1 << 60},
    468 		{0x9, 0x9 << 60},
    469 		{0xa, 0x5 << 60},
    470 		{0xb, 0xd << 60},
    471 		{0xc, 0x3 << 60},
    472 		{0xd, 0xb << 60},
    473 		{0xe, 0x7 << 60},
    474 		{0xf, 0xf << 60},
    475 		{0x5686487, 0xe12616a000000000},
    476 		{0x0123456789abcdef, 0xf7b3d591e6a2c480},
    477 	} {
    478 		testReverse(t, test.x, test.r)
    479 		testReverse(t, test.r, test.x)
    480 	}
    481 }
    482 
    483 func testReverse(t *testing.T, x64, want64 uint64) {
    484 	x8 := uint8(x64)
    485 	got8 := Reverse8(x8)
    486 	want8 := uint8(want64 >> (64 - 8))
    487 	if got8 != want8 {
    488 		t.Fatalf("Reverse8(%#02x) == %#02x; want %#02x", x8, got8, want8)
    489 	}
    490 
    491 	x16 := uint16(x64)
    492 	got16 := Reverse16(x16)
    493 	want16 := uint16(want64 >> (64 - 16))
    494 	if got16 != want16 {
    495 		t.Fatalf("Reverse16(%#04x) == %#04x; want %#04x", x16, got16, want16)
    496 	}
    497 
    498 	x32 := uint32(x64)
    499 	got32 := Reverse32(x32)
    500 	want32 := uint32(want64 >> (64 - 32))
    501 	if got32 != want32 {
    502 		t.Fatalf("Reverse32(%#08x) == %#08x; want %#08x", x32, got32, want32)
    503 	}
    504 	if UintSize == 32 {
    505 		x := uint(x32)
    506 		got := Reverse(x)
    507 		want := uint(want32)
    508 		if got != want {
    509 			t.Fatalf("Reverse(%#08x) == %#08x; want %#08x", x, got, want)
    510 		}
    511 	}
    512 
    513 	got64 := Reverse64(x64)
    514 	if got64 != want64 {
    515 		t.Fatalf("Reverse64(%#016x) == %#016x; want %#016x", x64, got64, want64)
    516 	}
    517 	if UintSize == 64 {
    518 		x := uint(x64)
    519 		got := Reverse(x)
    520 		want := uint(want64)
    521 		if got != want {
    522 			t.Fatalf("Reverse(%#08x) == %#016x; want %#016x", x, got, want)
    523 		}
    524 	}
    525 }
    526 
    527 func BenchmarkReverse(b *testing.B) {
    528 	var s uint
    529 	for i := 0; i < b.N; i++ {
    530 		s += Reverse(uint(i))
    531 	}
    532 	Output = int(s)
    533 }
    534 
    535 func BenchmarkReverse8(b *testing.B) {
    536 	var s uint8
    537 	for i := 0; i < b.N; i++ {
    538 		s += Reverse8(uint8(i))
    539 	}
    540 	Output = int(s)
    541 }
    542 
    543 func BenchmarkReverse16(b *testing.B) {
    544 	var s uint16
    545 	for i := 0; i < b.N; i++ {
    546 		s += Reverse16(uint16(i))
    547 	}
    548 	Output = int(s)
    549 }
    550 
    551 func BenchmarkReverse32(b *testing.B) {
    552 	var s uint32
    553 	for i := 0; i < b.N; i++ {
    554 		s += Reverse32(uint32(i))
    555 	}
    556 	Output = int(s)
    557 }
    558 
    559 func BenchmarkReverse64(b *testing.B) {
    560 	var s uint64
    561 	for i := 0; i < b.N; i++ {
    562 		s += Reverse64(uint64(i))
    563 	}
    564 	Output = int(s)
    565 }
    566 
    567 func TestReverseBytes(t *testing.T) {
    568 	for _, test := range []struct {
    569 		x, r uint64
    570 	}{
    571 		{0, 0},
    572 		{0x01, 0x01 << 56},
    573 		{0x0123, 0x2301 << 48},
    574 		{0x012345, 0x452301 << 40},
    575 		{0x01234567, 0x67452301 << 32},
    576 		{0x0123456789, 0x8967452301 << 24},
    577 		{0x0123456789ab, 0xab8967452301 << 16},
    578 		{0x0123456789abcd, 0xcdab8967452301 << 8},
    579 		{0x0123456789abcdef, 0xefcdab8967452301 << 0},
    580 	} {
    581 		testReverseBytes(t, test.x, test.r)
    582 		testReverseBytes(t, test.r, test.x)
    583 	}
    584 }
    585 
    586 func testReverseBytes(t *testing.T, x64, want64 uint64) {
    587 	x16 := uint16(x64)
    588 	got16 := ReverseBytes16(x16)
    589 	want16 := uint16(want64 >> (64 - 16))
    590 	if got16 != want16 {
    591 		t.Fatalf("ReverseBytes16(%#04x) == %#04x; want %#04x", x16, got16, want16)
    592 	}
    593 
    594 	x32 := uint32(x64)
    595 	got32 := ReverseBytes32(x32)
    596 	want32 := uint32(want64 >> (64 - 32))
    597 	if got32 != want32 {
    598 		t.Fatalf("ReverseBytes32(%#08x) == %#08x; want %#08x", x32, got32, want32)
    599 	}
    600 	if UintSize == 32 {
    601 		x := uint(x32)
    602 		got := ReverseBytes(x)
    603 		want := uint(want32)
    604 		if got != want {
    605 			t.Fatalf("ReverseBytes(%#08x) == %#08x; want %#08x", x, got, want)
    606 		}
    607 	}
    608 
    609 	got64 := ReverseBytes64(x64)
    610 	if got64 != want64 {
    611 		t.Fatalf("ReverseBytes64(%#016x) == %#016x; want %#016x", x64, got64, want64)
    612 	}
    613 	if UintSize == 64 {
    614 		x := uint(x64)
    615 		got := ReverseBytes(x)
    616 		want := uint(want64)
    617 		if got != want {
    618 			t.Fatalf("ReverseBytes(%#016x) == %#016x; want %#016x", x, got, want)
    619 		}
    620 	}
    621 }
    622 
    623 func BenchmarkReverseBytes(b *testing.B) {
    624 	var s uint
    625 	for i := 0; i < b.N; i++ {
    626 		s += ReverseBytes(uint(i))
    627 	}
    628 	Output = int(s)
    629 }
    630 
    631 func BenchmarkReverseBytes16(b *testing.B) {
    632 	var s uint16
    633 	for i := 0; i < b.N; i++ {
    634 		s += ReverseBytes16(uint16(i))
    635 	}
    636 	Output = int(s)
    637 }
    638 
    639 func BenchmarkReverseBytes32(b *testing.B) {
    640 	var s uint32
    641 	for i := 0; i < b.N; i++ {
    642 		s += ReverseBytes32(uint32(i))
    643 	}
    644 	Output = int(s)
    645 }
    646 
    647 func BenchmarkReverseBytes64(b *testing.B) {
    648 	var s uint64
    649 	for i := 0; i < b.N; i++ {
    650 		s += ReverseBytes64(uint64(i))
    651 	}
    652 	Output = int(s)
    653 }
    654 
    655 func TestLen(t *testing.T) {
    656 	for i := 0; i < 256; i++ {
    657 		len := 8 - tab[i].nlz
    658 		for k := 0; k < 64-8; k++ {
    659 			x := uint64(i) << uint(k)
    660 			want := 0
    661 			if x != 0 {
    662 				want = len + k
    663 			}
    664 			if x <= 1<<8-1 {
    665 				got := Len8(uint8(x))
    666 				if got != want {
    667 					t.Fatalf("Len8(%#02x) == %d; want %d", x, got, want)
    668 				}
    669 			}
    670 
    671 			if x <= 1<<16-1 {
    672 				got := Len16(uint16(x))
    673 				if got != want {
    674 					t.Fatalf("Len16(%#04x) == %d; want %d", x, got, want)
    675 				}
    676 			}
    677 
    678 			if x <= 1<<32-1 {
    679 				got := Len32(uint32(x))
    680 				if got != want {
    681 					t.Fatalf("Len32(%#08x) == %d; want %d", x, got, want)
    682 				}
    683 				if UintSize == 32 {
    684 					got := Len(uint(x))
    685 					if got != want {
    686 						t.Fatalf("Len(%#08x) == %d; want %d", x, got, want)
    687 					}
    688 				}
    689 			}
    690 
    691 			if x <= 1<<64-1 {
    692 				got := Len64(uint64(x))
    693 				if got != want {
    694 					t.Fatalf("Len64(%#016x) == %d; want %d", x, got, want)
    695 				}
    696 				if UintSize == 64 {
    697 					got := Len(uint(x))
    698 					if got != want {
    699 						t.Fatalf("Len(%#016x) == %d; want %d", x, got, want)
    700 					}
    701 				}
    702 			}
    703 		}
    704 	}
    705 }
    706 
    707 // ----------------------------------------------------------------------------
    708 // Testing support
    709 
    710 type entry = struct {
    711 	nlz, ntz, pop int
    712 }
    713 
    714 // tab contains results for all uint8 values
    715 var tab [256]entry
    716 
    717 func init() {
    718 	tab[0] = entry{8, 8, 0}
    719 	for i := 1; i < len(tab); i++ {
    720 		// nlz
    721 		x := i // x != 0
    722 		n := 0
    723 		for x&0x80 == 0 {
    724 			n++
    725 			x <<= 1
    726 		}
    727 		tab[i].nlz = n
    728 
    729 		// ntz
    730 		x = i // x != 0
    731 		n = 0
    732 		for x&1 == 0 {
    733 			n++
    734 			x >>= 1
    735 		}
    736 		tab[i].ntz = n
    737 
    738 		// pop
    739 		x = i // x != 0
    740 		n = 0
    741 		for x != 0 {
    742 			n += int(x & 1)
    743 			x >>= 1
    744 		}
    745 		tab[i].pop = n
    746 	}
    747 }
    748