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
13namespace v8 {
14namespace base {
15
16template <class T>
17std::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
26typedef MagicNumbersForDivision<uint32_t> M32;
27typedef MagicNumbersForDivision<uint64_t> M64;
28
29
30static M32 s32(int32_t d) {
31  return SignedDivisionByConstant<uint32_t>(static_cast<uint32_t>(d));
32}
33
34
35static M64 s64(int64_t d) {
36  return SignedDivisionByConstant<uint64_t>(static_cast<uint64_t>(d));
37}
38
39
40static M32 u32(uint32_t d) { return UnsignedDivisionByConstant<uint32_t>(d); }
41static M64 u64(uint64_t d) { return UnsignedDivisionByConstant<uint64_t>(d); }
42
43
44TEST(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
69TEST(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
88TEST(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
113TEST(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
133