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