| 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 |