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 #include "src/base/division-by-constant.h" 6 7 #include <stdint.h> 8 9 #include "src/base/logging.h" 10 #include "src/base/macros.h" 11 12 namespace v8 { 13 namespace base { 14 15 template <class T> 16 bool MagicNumbersForDivision<T>::operator==( 17 const MagicNumbersForDivision& rhs) const { 18 return multiplier == rhs.multiplier && shift == rhs.shift && add == rhs.add; 19 } 20 21 22 template <class T> 23 MagicNumbersForDivision<T> SignedDivisionByConstant(T d) { 24 STATIC_ASSERT(static_cast<T>(0) < static_cast<T>(-1)); 25 DCHECK(d != static_cast<T>(-1) && d != 0 && d != 1); 26 const unsigned bits = static_cast<unsigned>(sizeof(T)) * 8; 27 const T min = (static_cast<T>(1) << (bits - 1)); 28 const bool neg = (min & d) != 0; 29 const T ad = neg ? (0 - d) : d; 30 const T t = min + (d >> (bits - 1)); 31 const T anc = t - 1 - t % ad; // Absolute value of nc 32 unsigned p = bits - 1; // Init. p. 33 T q1 = min / anc; // Init. q1 = 2**p/|nc|. 34 T r1 = min - q1 * anc; // Init. r1 = rem(2**p, |nc|). 35 T q2 = min / ad; // Init. q2 = 2**p/|d|. 36 T r2 = min - q2 * ad; // Init. r2 = rem(2**p, |d|). 37 T delta; 38 do { 39 p = p + 1; 40 q1 = 2 * q1; // Update q1 = 2**p/|nc|. 41 r1 = 2 * r1; // Update r1 = rem(2**p, |nc|). 42 if (r1 >= anc) { // Must be an unsigned comparison here. 43 q1 = q1 + 1; 44 r1 = r1 - anc; 45 } 46 q2 = 2 * q2; // Update q2 = 2**p/|d|. 47 r2 = 2 * r2; // Update r2 = rem(2**p, |d|). 48 if (r2 >= ad) { // Must be an unsigned comparison here. 49 q2 = q2 + 1; 50 r2 = r2 - ad; 51 } 52 delta = ad - r2; 53 } while (q1 < delta || (q1 == delta && r1 == 0)); 54 T mul = q2 + 1; 55 return MagicNumbersForDivision<T>(neg ? (0 - mul) : mul, p - bits, false); 56 } 57 58 59 template <class T> 60 MagicNumbersForDivision<T> UnsignedDivisionByConstant(T d, 61 unsigned leading_zeros) { 62 STATIC_ASSERT(static_cast<T>(0) < static_cast<T>(-1)); 63 DCHECK(d != 0); 64 const unsigned bits = static_cast<unsigned>(sizeof(T)) * 8; 65 const T ones = ~static_cast<T>(0) >> leading_zeros; 66 const T min = static_cast<T>(1) << (bits - 1); 67 const T max = ~static_cast<T>(0) >> 1; 68 const T nc = ones - (ones - d) % d; 69 bool a = false; // Init. "add" indicator. 70 unsigned p = bits - 1; // Init. p. 71 T q1 = min / nc; // Init. q1 = 2**p/nc 72 T r1 = min - q1 * nc; // Init. r1 = rem(2**p,nc) 73 T q2 = max / d; // Init. q2 = (2**p - 1)/d. 74 T r2 = max - q2 * d; // Init. r2 = rem(2**p - 1, d). 75 T delta; 76 do { 77 p = p + 1; 78 if (r1 >= nc - r1) { 79 q1 = 2 * q1 + 1; 80 r1 = 2 * r1 - nc; 81 } else { 82 q1 = 2 * q1; 83 r1 = 2 * r1; 84 } 85 if (r2 + 1 >= d - r2) { 86 if (q2 >= max) a = true; 87 q2 = 2 * q2 + 1; 88 r2 = 2 * r2 + 1 - d; 89 } else { 90 if (q2 >= min) a = true; 91 q2 = 2 * q2; 92 r2 = 2 * r2 + 1; 93 } 94 delta = d - 1 - r2; 95 } while (p < bits * 2 && (q1 < delta || (q1 == delta && r1 == 0))); 96 return MagicNumbersForDivision<T>(q2 + 1, p - bits, a); 97 } 98 99 100 // ----------------------------------------------------------------------------- 101 // Instantiations. 102 103 template struct MagicNumbersForDivision<uint32_t>; 104 template struct MagicNumbersForDivision<uint64_t>; 105 106 template MagicNumbersForDivision<uint32_t> SignedDivisionByConstant(uint32_t d); 107 template MagicNumbersForDivision<uint64_t> SignedDivisionByConstant(uint64_t d); 108 109 template MagicNumbersForDivision<uint32_t> UnsignedDivisionByConstant( 110 uint32_t d, unsigned leading_zeros); 111 template MagicNumbersForDivision<uint64_t> UnsignedDivisionByConstant( 112 uint64_t d, unsigned leading_zeros); 113 114 } // namespace base 115 } // namespace v8 116
