Line data    Source code

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