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