OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/base/division-by-constant.h" | 5 #include "src/base/division-by-constant.h" |
6 | 6 |
7 #include <stdint.h> | 7 #include <stdint.h> |
8 | 8 |
9 #include "src/base/logging.h" | 9 #include "src/base/logging.h" |
10 #include "src/base/macros.h" | 10 #include "src/base/macros.h" |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
45 } | 45 } |
46 q2 = 2 * q2; // Update q2 = 2**p/|d|. | 46 q2 = 2 * q2; // Update q2 = 2**p/|d|. |
47 r2 = 2 * r2; // Update r2 = rem(2**p, |d|). | 47 r2 = 2 * r2; // Update r2 = rem(2**p, |d|). |
48 if (r2 >= ad) { // Must be an unsigned comparison here. | 48 if (r2 >= ad) { // Must be an unsigned comparison here. |
49 q2 = q2 + 1; | 49 q2 = q2 + 1; |
50 r2 = r2 - ad; | 50 r2 = r2 - ad; |
51 } | 51 } |
52 delta = ad - r2; | 52 delta = ad - r2; |
53 } while (q1 < delta || (q1 == delta && r1 == 0)); | 53 } while (q1 < delta || (q1 == delta && r1 == 0)); |
54 T mul = q2 + 1; | 54 T mul = q2 + 1; |
55 return {neg ? (0 - mul) : mul, p - bits, false}; | 55 return MagicNumbersForDivision<T>(neg ? (0 - mul) : mul, p - bits, false); |
56 } | 56 } |
57 | 57 |
58 | 58 |
59 template <class T> | 59 template <class T> |
60 MagicNumbersForDivision<T> UnsignedDivisionByConstant(T d, | 60 MagicNumbersForDivision<T> UnsignedDivisionByConstant(T d, |
61 unsigned leading_zeros) { | 61 unsigned leading_zeros) { |
62 STATIC_ASSERT(static_cast<T>(0) < static_cast<T>(-1)); | 62 STATIC_ASSERT(static_cast<T>(0) < static_cast<T>(-1)); |
63 DCHECK(d != 0); | 63 DCHECK(d != 0); |
64 const unsigned bits = static_cast<unsigned>(sizeof(T)) * 8; | 64 const unsigned bits = static_cast<unsigned>(sizeof(T)) * 8; |
65 const T ones = ~static_cast<T>(0) >> leading_zeros; | 65 const T ones = ~static_cast<T>(0) >> leading_zeros; |
(...skipping 20 matching lines...) Expand all Loading... |
86 if (q2 >= max) a = true; | 86 if (q2 >= max) a = true; |
87 q2 = 2 * q2 + 1; | 87 q2 = 2 * q2 + 1; |
88 r2 = 2 * r2 + 1 - d; | 88 r2 = 2 * r2 + 1 - d; |
89 } else { | 89 } else { |
90 if (q2 >= min) a = true; | 90 if (q2 >= min) a = true; |
91 q2 = 2 * q2; | 91 q2 = 2 * q2; |
92 r2 = 2 * r2 + 1; | 92 r2 = 2 * r2 + 1; |
93 } | 93 } |
94 delta = d - 1 - r2; | 94 delta = d - 1 - r2; |
95 } while (p < bits * 2 && (q1 < delta || (q1 == delta && r1 == 0))); | 95 } while (p < bits * 2 && (q1 < delta || (q1 == delta && r1 == 0))); |
96 return {q2 + 1, p - bits, a}; | 96 return MagicNumbersForDivision<T>(q2 + 1, p - bits, a); |
97 } | 97 } |
98 | 98 |
99 | 99 |
100 // ----------------------------------------------------------------------------- | 100 // ----------------------------------------------------------------------------- |
101 // Instantiations. | 101 // Instantiations. |
102 | 102 |
103 template struct MagicNumbersForDivision<uint32_t>; | 103 template struct MagicNumbersForDivision<uint32_t>; |
104 template struct MagicNumbersForDivision<uint64_t>; | 104 template struct MagicNumbersForDivision<uint64_t>; |
105 | 105 |
106 template MagicNumbersForDivision<uint32_t> SignedDivisionByConstant(uint32_t d); | 106 template MagicNumbersForDivision<uint32_t> SignedDivisionByConstant(uint32_t d); |
107 template MagicNumbersForDivision<uint64_t> SignedDivisionByConstant(uint64_t d); | 107 template MagicNumbersForDivision<uint64_t> SignedDivisionByConstant(uint64_t d); |
108 | 108 |
109 template MagicNumbersForDivision<uint32_t> UnsignedDivisionByConstant( | 109 template MagicNumbersForDivision<uint32_t> UnsignedDivisionByConstant( |
110 uint32_t d, unsigned leading_zeros); | 110 uint32_t d, unsigned leading_zeros); |
111 template MagicNumbersForDivision<uint64_t> UnsignedDivisionByConstant( | 111 template MagicNumbersForDivision<uint64_t> UnsignedDivisionByConstant( |
112 uint64_t d, unsigned leading_zeros); | 112 uint64_t d, unsigned leading_zeros); |
113 | 113 |
114 } // namespace base | 114 } // namespace base |
115 } // namespace v8 | 115 } // namespace v8 |
OLD | NEW |