Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : // Check all examples from table 10-1 of "Hacker's Delight".
6 :
7 : #include "src/base/division-by-constant.h"
8 :
9 : #include <stdint.h>
10 :
11 : #include <ostream> // NOLINT
12 :
13 : #include "testing/gtest-support.h"
14 :
15 : namespace v8 {
16 : namespace base {
17 :
18 : template <class T>
19 0 : std::ostream& operator<<(std::ostream& os,
20 : const MagicNumbersForDivision<T>& mag) {
21 0 : return os << "{ multiplier: " << mag.multiplier << ", shift: " << mag.shift
22 0 : << ", add: " << mag.add << " }";
23 : }
24 :
25 :
26 : // Some abbreviations...
27 :
28 : typedef MagicNumbersForDivision<uint32_t> M32;
29 : typedef MagicNumbersForDivision<uint64_t> M64;
30 :
31 :
32 : static M32 s32(int32_t d) {
33 74 : return SignedDivisionByConstant<uint32_t>(static_cast<uint32_t>(d));
34 : }
35 :
36 :
37 : static M64 s64(int64_t d) {
38 138 : return SignedDivisionByConstant<uint64_t>(static_cast<uint64_t>(d));
39 : }
40 :
41 :
42 42 : static M32 u32(uint32_t d) { return UnsignedDivisionByConstant<uint32_t>(d); }
43 74 : static M64 u64(uint64_t d) { return UnsignedDivisionByConstant<uint64_t>(d); }
44 :
45 :
46 15188 : TEST(DivisionByConstant, Signed32) {
47 2 : EXPECT_EQ(M32(0x99999999U, 1, false), s32(-5));
48 2 : EXPECT_EQ(M32(0x55555555U, 1, false), s32(-3));
49 : int32_t d = -1;
50 32 : for (unsigned k = 1; k <= 32 - 1; ++k) {
51 31 : d *= 2;
52 62 : EXPECT_EQ(M32(0x7FFFFFFFU, k - 1, false), s32(d));
53 : }
54 30 : for (unsigned k = 1; k <= 32 - 2; ++k) {
55 90 : EXPECT_EQ(M32(0x80000001U, k - 1, false), s32(1 << k));
56 : }
57 2 : EXPECT_EQ(M32(0x55555556U, 0, false), s32(3));
58 2 : EXPECT_EQ(M32(0x66666667U, 1, false), s32(5));
59 2 : EXPECT_EQ(M32(0x2AAAAAABU, 0, false), s32(6));
60 2 : EXPECT_EQ(M32(0x92492493U, 2, false), s32(7));
61 2 : EXPECT_EQ(M32(0x38E38E39U, 1, false), s32(9));
62 2 : EXPECT_EQ(M32(0x66666667U, 2, false), s32(10));
63 2 : EXPECT_EQ(M32(0x2E8BA2E9U, 1, false), s32(11));
64 2 : EXPECT_EQ(M32(0x2AAAAAABU, 1, false), s32(12));
65 2 : EXPECT_EQ(M32(0x51EB851FU, 3, false), s32(25));
66 2 : EXPECT_EQ(M32(0x10624DD3U, 3, false), s32(125));
67 2 : EXPECT_EQ(M32(0x68DB8BADU, 8, false), s32(625));
68 1 : }
69 :
70 :
71 15188 : TEST(DivisionByConstant, Unsigned32) {
72 2 : EXPECT_EQ(M32(0x00000000U, 0, true), u32(1));
73 31 : for (unsigned k = 1; k <= 30; ++k) {
74 90 : EXPECT_EQ(M32(1U << (32 - k), 0, false), u32(1U << k));
75 : }
76 2 : EXPECT_EQ(M32(0xAAAAAAABU, 1, false), u32(3));
77 2 : EXPECT_EQ(M32(0xCCCCCCCDU, 2, false), u32(5));
78 2 : EXPECT_EQ(M32(0xAAAAAAABU, 2, false), u32(6));
79 2 : EXPECT_EQ(M32(0x24924925U, 3, true), u32(7));
80 2 : EXPECT_EQ(M32(0x38E38E39U, 1, false), u32(9));
81 2 : EXPECT_EQ(M32(0xCCCCCCCDU, 3, false), u32(10));
82 2 : EXPECT_EQ(M32(0xBA2E8BA3U, 3, false), u32(11));
83 2 : EXPECT_EQ(M32(0xAAAAAAABU, 3, false), u32(12));
84 2 : EXPECT_EQ(M32(0x51EB851FU, 3, false), u32(25));
85 2 : EXPECT_EQ(M32(0x10624DD3U, 3, false), u32(125));
86 2 : EXPECT_EQ(M32(0xD1B71759U, 9, false), u32(625));
87 1 : }
88 :
89 :
90 15188 : TEST(DivisionByConstant, Signed64) {
91 2 : EXPECT_EQ(M64(0x9999999999999999ULL, 1, false), s64(-5));
92 2 : EXPECT_EQ(M64(0x5555555555555555ULL, 1, false), s64(-3));
93 : int64_t d = -1;
94 64 : for (unsigned k = 1; k <= 64 - 1; ++k) {
95 63 : d *= 2;
96 126 : EXPECT_EQ(M64(0x7FFFFFFFFFFFFFFFULL, k - 1, false), s64(d));
97 : }
98 62 : for (unsigned k = 1; k <= 64 - 2; ++k) {
99 186 : EXPECT_EQ(M64(0x8000000000000001ULL, k - 1, false), s64(1LL << k));
100 : }
101 2 : EXPECT_EQ(M64(0x5555555555555556ULL, 0, false), s64(3));
102 2 : EXPECT_EQ(M64(0x6666666666666667ULL, 1, false), s64(5));
103 2 : EXPECT_EQ(M64(0x2AAAAAAAAAAAAAABULL, 0, false), s64(6));
104 2 : EXPECT_EQ(M64(0x4924924924924925ULL, 1, false), s64(7));
105 2 : EXPECT_EQ(M64(0x1C71C71C71C71C72ULL, 0, false), s64(9));
106 2 : EXPECT_EQ(M64(0x6666666666666667ULL, 2, false), s64(10));
107 2 : EXPECT_EQ(M64(0x2E8BA2E8BA2E8BA3ULL, 1, false), s64(11));
108 2 : EXPECT_EQ(M64(0x2AAAAAAAAAAAAAABULL, 1, false), s64(12));
109 2 : EXPECT_EQ(M64(0xA3D70A3D70A3D70BULL, 4, false), s64(25));
110 2 : EXPECT_EQ(M64(0x20C49BA5E353F7CFULL, 4, false), s64(125));
111 2 : EXPECT_EQ(M64(0x346DC5D63886594BULL, 7, false), s64(625));
112 1 : }
113 :
114 :
115 15188 : TEST(DivisionByConstant, Unsigned64) {
116 2 : EXPECT_EQ(M64(0x0000000000000000ULL, 0, true), u64(1));
117 63 : for (unsigned k = 1; k <= 64 - 2; ++k) {
118 186 : EXPECT_EQ(M64(1ULL << (64 - k), 0, false), u64(1ULL << k));
119 : }
120 2 : EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 1, false), u64(3));
121 2 : EXPECT_EQ(M64(0xCCCCCCCCCCCCCCCDULL, 2, false), u64(5));
122 2 : EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 2, false), u64(6));
123 2 : EXPECT_EQ(M64(0x2492492492492493ULL, 3, true), u64(7));
124 2 : EXPECT_EQ(M64(0xE38E38E38E38E38FULL, 3, false), u64(9));
125 2 : EXPECT_EQ(M64(0xCCCCCCCCCCCCCCCDULL, 3, false), u64(10));
126 2 : EXPECT_EQ(M64(0x2E8BA2E8BA2E8BA3ULL, 1, false), u64(11));
127 2 : EXPECT_EQ(M64(0xAAAAAAAAAAAAAAABULL, 3, false), u64(12));
128 2 : EXPECT_EQ(M64(0x47AE147AE147AE15ULL, 5, true), u64(25));
129 2 : EXPECT_EQ(M64(0x0624DD2F1A9FBE77ULL, 7, true), u64(125));
130 2 : EXPECT_EQ(M64(0x346DC5D63886594BULL, 7, false), u64(625));
131 1 : }
132 :
133 : } // namespace base
134 9111 : } // namespace v8
|
