Caffe2 - C++ API
A deep learning, cross platform ML framework
fixed_divisor.h
1 #ifndef CAFFE2_UTILS_FIXED_DIVISOR_H_
2 #define CAFFE2_UTILS_FIXED_DIVISOR_H_
3 
4 #include <cstdlib>
5 #include <stdint.h>
6 
7 namespace caffe2 {
8 
9 // Utility class for quickly calculating quotients and remainders for
10 // a known integer divisor
11 template <typename T>
12 class FixedDivisor {
13 };
14 
15 // Works for any positive divisor, 1 to INT_MAX. One 64-bit
16 // multiplication and one 64-bit shift is used to calculate the
17 // result.
18 template <>
19 class FixedDivisor<int32_t> {
20  public:
21  FixedDivisor(int32_t d) : d_(d) {
22  calcSignedMagic();
23  }
24 
25  uint64_t getMagic() const {
26  return magic_;
27  }
28 
29  int getShift() const {
30  return shift_;
31  }
32 
34  inline int32_t div(int32_t n) const {
35  // In lieu of a mulhi instruction being available, perform the
36  // work in uint64
37  uint64_t mul64 = magic_ * (uint64_t) n;
38  return (int32_t) (mul64 >> shift_);
39  }
40 
42  inline int32_t mod(int32_t n) const {
43  return n - d_ * div(n);
44  }
45 
47  inline void divMod(int32_t n, int32_t& q, int32_t& r) const {
48  const int32_t quotient = div(n);
49  q = quotient;
50  r = n - d_ * quotient;
51  }
52 
53  private:
59  void calcSignedMagic() {
60  if (d_ == 1) {
61  magic_ = UINT64_C(0x1) << 32;
62  shift_ = 32;
63  return;
64  }
65 
66  const uint32_t two31 = UINT32_C(0x80000000);
67  uint32_t ad = std::abs(d_);
68  uint32_t t = two31 + ((uint32_t) d_ >> 31);
69  uint32_t anc = t - 1 - t % ad; // Absolute value of nc.
70  uint32_t p = 31; // Init. p.
71  uint32_t q1 = two31 / anc; // Init. q1 = 2**p/|nc|.
72  uint32_t r1 = two31 - q1 * anc; // Init. r1 = rem(2**p, |nc|).
73  uint32_t q2 = two31 / ad; // Init. q2 = 2**p/|d|.
74  uint32_t r2 = two31 - q2 * ad; // Init. r2 = rem(2**p, |d|).
75  uint32_t delta = 0;
76 
77  do {
78  p = p + 1;
79  q1 = 2 * q1; // Update q1 = 2**p/|nc|.
80  r1 = 2 * r1; // Update r1 = rem(2**p, |nc|).
81 
82  if (r1 >= anc) { // (Must be an unsigned
83  q1 = q1 + 1; // comparison here).
84  r1 = r1 - anc;
85  }
86 
87  q2 = 2 * q2; // Update q2 = 2**p/|d|.
88  r2 = 2 * r2; // Update r2 = rem(2**p, |d|).
89 
90  if (r2 >= ad) { // (Must be an unsigned
91  q2 = q2 + 1; // comparison here).
92  r2 = r2 - ad;
93  }
94 
95  delta = ad - r2;
96  } while (q1 < delta || (q1 == delta && r1 == 0));
97 
98  int32_t magic = q2 + 1;
99  if (d_ < 0) {
100  magic = -magic;
101  }
102  shift_ = p;
103  magic_ = (uint64_t) (uint32_t) magic;
104  }
105 
106  int32_t d_;
107  uint64_t magic_;
108  int shift_;
109 };
110 
111 } // namespace caffe2
112 
113 #endif // CAFFE2_UTILS_FIXED_DIVISOR_H_
int32_t div(int32_t n) const
Calculates q = n / d.
Definition: fixed_divisor.h:34
int32_t mod(int32_t n) const
Calculates r = n % d.
Definition: fixed_divisor.h:42
Simple registry implementation in Caffe2 that uses static variables to register object creators durin...
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:47