• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
SignedDivisionByConstant(T d)16 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   const bool neg = (min & d) != 0;
22   const T ad = neg ? (0 - d) : d;
23   const T t = min + (d >> (bits - 1));
24   const T anc = t - 1 - t % ad;  // Absolute value of nc
25   unsigned p = bits - 1;         // Init. p.
26   T q1 = min / anc;              // Init. q1 = 2**p/|nc|.
27   T r1 = min - q1 * anc;         // Init. r1 = rem(2**p, |nc|).
28   T q2 = min / ad;               // Init. q2 = 2**p/|d|.
29   T r2 = min - q2 * ad;          // Init. r2 = rem(2**p, |d|).
30   T delta;
31   do {
32     p = p + 1;
33     q1 = 2 * q1;      // Update q1 = 2**p/|nc|.
34     r1 = 2 * r1;      // Update r1 = rem(2**p, |nc|).
35     if (r1 >= anc) {  // Must be an unsigned comparison here.
36       q1 = q1 + 1;
37       r1 = r1 - anc;
38     }
39     q2 = 2 * q2;     // Update q2 = 2**p/|d|.
40     r2 = 2 * r2;     // Update r2 = rem(2**p, |d|).
41     if (r2 >= ad) {  // Must be an unsigned comparison here.
42       q2 = q2 + 1;
43       r2 = r2 - ad;
44     }
45     delta = ad - r2;
46   } while (q1 < delta || (q1 == delta && r1 == 0));
47   T mul = q2 + 1;
48   return MagicNumbersForDivision<T>(neg ? (0 - mul) : mul, p - bits, false);
49 }
50 
51 
52 template <class T>
UnsignedDivisionByConstant(T d,unsigned leading_zeros)53 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   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   const T nc = ones - (ones - d) % d;
62   bool a = false;         // Init. "add" indicator.
63   unsigned p = bits - 1;  // Init. p.
64   T q1 = min / nc;        // Init. q1 = 2**p/nc
65   T r1 = min - q1 * nc;   // Init. r1 = rem(2**p,nc)
66   T q2 = max / d;         // Init. q2 = (2**p - 1)/d.
67   T r2 = max - q2 * d;    // Init. r2 = rem(2**p - 1, d).
68   T delta;
69   do {
70     p = p + 1;
71     if (r1 >= nc - r1) {
72       q1 = 2 * q1 + 1;
73       r1 = 2 * r1 - nc;
74     } else {
75       q1 = 2 * q1;
76       r1 = 2 * r1;
77     }
78     if (r2 + 1 >= d - r2) {
79       if (q2 >= max) a = true;
80       q2 = 2 * q2 + 1;
81       r2 = 2 * r2 + 1 - d;
82     } else {
83       if (q2 >= min) a = true;
84       q2 = 2 * q2;
85       r2 = 2 * r2 + 1;
86     }
87     delta = d - 1 - r2;
88   } while (p < bits * 2 && (q1 < delta || (q1 == delta && r1 == 0)));
89   return MagicNumbersForDivision<T>(q2 + 1, p - bits, a);
90 }
91 
92 
93 // -----------------------------------------------------------------------------
94 // Instantiations.
95 
96 template struct V8_BASE_EXPORT MagicNumbersForDivision<uint32_t>;
97 template struct V8_BASE_EXPORT MagicNumbersForDivision<uint64_t>;
98 
99 template MagicNumbersForDivision<uint32_t> SignedDivisionByConstant(uint32_t d);
100 template MagicNumbersForDivision<uint64_t> SignedDivisionByConstant(uint64_t d);
101 
102 template MagicNumbersForDivision<uint32_t> UnsignedDivisionByConstant(
103     uint32_t d, unsigned leading_zeros);
104 template MagicNumbersForDivision<uint64_t> UnsignedDivisionByConstant(
105     uint64_t d, unsigned leading_zeros);
106 
107 }  // namespace base
108 }  // namespace v8
109