Source file
src/math/bits/bits_test.go
1
2
3
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
86
87
88 var Input uint64 = DeBruijn64
89
90
91
92
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
453 for i := uint(0); i < 64; i++ {
454 testReverse(t, uint64(1)<<i, uint64(1)<<(63-i))
455 }
456
457
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
740
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
801
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
811
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
860 shouldPanic(func() { test(_M64, 1) })
861 shouldPanic(func() { test(1, _M64) })
862 shouldPanic(func() { test(_M64, _M64) })
863
864
865 test(_M64, 0)
866 test(0, 0)
867 test(1, 1)
868 }
869 }
870
871 func TestSub64OverflowPanic(t *testing.T) {
872
873
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
922 shouldPanic(func() { test(0, 1) })
923 shouldPanic(func() { test(1, _M64) })
924 shouldPanic(func() { test(_M64-1, _M64) })
925
926
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
958
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
1020
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
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
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
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
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
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
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
1113
1114 hi, lo, y := uint32(510510), uint32(9699690), uint32(510510+1)
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
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
1140
1141 hi, lo, y := uint64(510510), uint64(9699690), uint64(510510+1)
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
1158
1159
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
1309
1310 type entry = struct {
1311 nlz, ntz, pop int
1312 }
1313
1314
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
1321 x := i
1322 n := 0
1323 for x&0x80 == 0 {
1324 n++
1325 x <<= 1
1326 }
1327 tab[i].nlz = n
1328
1329
1330 x = i
1331 n = 0
1332 for x&1 == 0 {
1333 n++
1334 x >>= 1
1335 }
1336 tab[i].ntz = n
1337
1338
1339 x = i
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