1// Copyright 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bits
6
7import (
8	"testing"
9	"unsafe"
10)
11
12func 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
19func 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.
86var 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.
91var Output int
92
93func 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
101func 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
109func 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
117func 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
125func 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
133func 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
194func 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
202func 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
210func 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
218func 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
226func 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
234func 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
253func 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
295func 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
303func 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
311func 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
319func 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
327func 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
335func 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
409func 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
417func 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
425func 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
433func 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
441func 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
449func 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
483func 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
527func 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
535func 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
543func 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
551func 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
559func 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
567func 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
586func 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
623func 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
631func 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
639func 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
647func 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
655func 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
710type entry = struct {
711	nlz, ntz, pop int
712}
713
714// tab contains results for all uint8 values
715var tab [256]entry
716
717func 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