src/v8/src/base/division-by-constant.cc

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