Caffe2 - C++ API
A deep learning, cross platform ML framework
fixed_divisor.h
1 
17 #ifndef CAFFE2_UTILS_FIXED_DIVISOR_H_
18 #define CAFFE2_UTILS_FIXED_DIVISOR_H_
19 
20 #include <cstdlib>
21 #include <stdint.h>
22 
23 namespace caffe2 {
24 
25 // Utility class for quickly calculating quotients and remainders for
26 // a known integer divisor
27 template <typename T>
28 class FixedDivisor {
29 };
30 
31 // Works for any positive divisor, 1 to INT_MAX. One 64-bit
32 // multiplication and one 64-bit shift is used to calculate the
33 // result.
34 template <>
35 class FixedDivisor<int32_t> {
36  public:
37  FixedDivisor(int32_t d) : d_(d) {
38  calcSignedMagic();
39  }
40 
41  uint64_t getMagic() const {
42  return magic_;
43  }
44 
45  int getShift() const {
46  return shift_;
47  }
48 
50  inline int32_t div(int32_t n) const {
51  // In lieu of a mulhi instruction being available, perform the
52  // work in uint64
53  uint64_t mul64 = magic_ * (uint64_t) n;
54  return (int32_t) (mul64 >> shift_);
55  }
56 
58  inline int32_t mod(int32_t n) const {
59  return n - d_ * div(n);
60  }
61 
63  inline void divMod(int32_t n, int32_t& q, int32_t& r) const {
64  const int32_t quotient = div(n);
65  q = quotient;
66  r = n - d_ * quotient;
67  }
68 
69  private:
75  void calcSignedMagic() {
76  if (d_ == 1) {
77  magic_ = UINT64_C(0x1) << 32;
78  shift_ = 32;
79  return;
80  }
81 
82  const uint32_t two31 = UINT32_C(0x80000000);
83  uint32_t ad = std::abs(d_);
84  uint32_t t = two31 + ((uint32_t) d_ >> 31);
85  uint32_t anc = t - 1 - t % ad; // Absolute value of nc.
86  uint32_t p = 31; // Init. p.
87  uint32_t q1 = two31 / anc; // Init. q1 = 2**p/|nc|.
88  uint32_t r1 = two31 - q1 * anc; // Init. r1 = rem(2**p, |nc|).
89  uint32_t q2 = two31 / ad; // Init. q2 = 2**p/|d|.
90  uint32_t r2 = two31 - q2 * ad; // Init. r2 = rem(2**p, |d|).
91  uint32_t delta = 0;
92 
93  do {
94  p = p + 1;
95  q1 = 2 * q1; // Update q1 = 2**p/|nc|.
96  r1 = 2 * r1; // Update r1 = rem(2**p, |nc|).
97 
98  if (r1 >= anc) { // (Must be an unsigned
99  q1 = q1 + 1; // comparison here).
100  r1 = r1 - anc;
101  }
102 
103  q2 = 2 * q2; // Update q2 = 2**p/|d|.
104  r2 = 2 * r2; // Update r2 = rem(2**p, |d|).
105 
106  if (r2 >= ad) { // (Must be an unsigned
107  q2 = q2 + 1; // comparison here).
108  r2 = r2 - ad;
109  }
110 
111  delta = ad - r2;
112  } while (q1 < delta || (q1 == delta && r1 == 0));
113 
114  int32_t magic = q2 + 1;
115  if (d_ < 0) {
116  magic = -magic;
117  }
118  shift_ = p;
119  magic_ = (uint64_t) (uint32_t) magic;
120  }
121 
122  int32_t d_;
123  uint64_t magic_;
124  int shift_;
125 };
126 
127 } // namespace caffe2
128 
129 #endif // CAFFE2_UTILS_FIXED_DIVISOR_H_
Copyright (c) 2016-present, Facebook, Inc.
int32_t div(int32_t n) const
Calculates q = n / d.
Definition: fixed_divisor.h:50
void divMod(int32_t n, int32_t &q, int32_t &r) const
Calculates q = n / d and r = n % d together.
Definition: fixed_divisor.h:63
int32_t mod(int32_t n) const
Calculates r = n % d.
Definition: fixed_divisor.h:58