TensorUInt128.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2015 Benoit Steiner <benoit.steiner.goog@gmail.com>
5 //
6 // This Source Code Form is subject to the terms of the Mozilla
7 // Public License v. 2.0. If a copy of the MPL was not distributed
8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 
10 #ifndef EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
11 #define EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
12 
13 namespace Eigen {
14 namespace internal {
15 
16 
17 template <uint64_t n>
18 struct static_val {
19  static const uint64_t value = n;
20  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator uint64_t() const { return n; }
21 
22  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val() { }
23  template <typename T>
24  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE static_val(const T& v) {
25  eigen_assert(v == n);
26  }
27 };
28 
29 
30 template <typename HIGH = uint64_t, typename LOW = uint64_t>
31 struct TensorUInt128
32 {
33  HIGH high;
34  LOW low;
35 
36  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
37  TensorUInt128(int x) : high(0), low(x) {
38  eigen_assert(x >= 0);
39  }
40  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
41  TensorUInt128(int64_t x) : high(0), low(x) {
42  eigen_assert(x >= 0);
43  }
44  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
45  TensorUInt128(uint64_t x) : high(0), low(x) { }
46  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
47  TensorUInt128(uint64_t y, uint64_t x) : high(y), low(x) { }
48 
49  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE operator LOW() const {
50  return low;
51  }
52  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE LOW lower() const {
53  return low;
54  }
55  EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE HIGH upper() const {
56  return high;
57  }
58 };
59 
60 
61 template <typename HL, typename LL, typename HR, typename LR>
62 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
63 static bool operator == (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
64 {
65  return (lhs.high == rhs.high) & (lhs.low == rhs.low);
66 }
67 
68 template <typename HL, typename LL, typename HR, typename LR>
69 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
70 static bool operator != (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
71 {
72  return (lhs.high != rhs.high) | (lhs.low != rhs.low);
73 }
74 
75 template <typename HL, typename LL, typename HR, typename LR>
76 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
77 static bool operator >= (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
78 {
79  if (lhs.high != rhs.high) {
80  return lhs.high > rhs.high;
81  }
82  return lhs.low >= rhs.low;
83 }
84 
85 template <typename HL, typename LL, typename HR, typename LR>
86 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
87 static bool operator < (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
88 {
89  if (lhs.high != rhs.high) {
90  return lhs.high < rhs.high;
91  }
92  return lhs.low < rhs.low;
93 }
94 
95 template <typename HL, typename LL, typename HR, typename LR>
96 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
97 static TensorUInt128<uint64_t, uint64_t> operator + (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
98 {
99  TensorUInt128<uint64_t, uint64_t> result(lhs.high + rhs.high, lhs.low + rhs.low);
100  if (result.low < rhs.low) {
101  result.high += 1;
102  }
103  return result;
104 }
105 
106 template <typename HL, typename LL, typename HR, typename LR>
107 EIGEN_DEVICE_FUNC EIGEN_ALWAYS_INLINE
108 static TensorUInt128<uint64_t, uint64_t> operator - (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
109 {
110  TensorUInt128<uint64_t, uint64_t> result(lhs.high - rhs.high, lhs.low - rhs.low);
111  if (result.low > lhs.low) {
112  result.high -= 1;
113  }
114  return result;
115 }
116 
117 
118 template <typename HL, typename LL, typename HR, typename LR>
119 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE
120 static TensorUInt128<uint64_t, uint64_t> operator * (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
121 {
122  // Split each 128-bit integer into 4 32-bit integers, and then do the
123  // multiplications by hand as follow:
124  // lhs a b c d
125  // rhs e f g h
126  // -----------
127  // ah bh ch dh
128  // bg cg dg
129  // cf df
130  // de
131  // The result is stored in 2 64bit integers, high and low.
132 
133  const uint64_t LOW = 0x00000000FFFFFFFFLL;
134  const uint64_t HIGH = 0xFFFFFFFF00000000LL;
135 
136  uint64_t d = lhs.low & LOW;
137  uint64_t c = (lhs.low & HIGH) >> 32LL;
138  uint64_t b = lhs.high & LOW;
139  uint64_t a = (lhs.high & HIGH) >> 32LL;
140 
141  uint64_t h = rhs.low & LOW;
142  uint64_t g = (rhs.low & HIGH) >> 32LL;
143  uint64_t f = rhs.high & LOW;
144  uint64_t e = (rhs.high & HIGH) >> 32LL;
145 
146  // Compute the low 32 bits of low
147  uint64_t acc = d * h;
148  uint64_t low = acc & LOW;
149  // Compute the high 32 bits of low. Add a carry every time we wrap around
150  acc >>= 32LL;
151  uint64_t carry = 0;
152  uint64_t acc2 = acc + c * h;
153  if (acc2 < acc) {
154  carry++;
155  }
156  acc = acc2 + d * g;
157  if (acc < acc2) {
158  carry++;
159  }
160  low |= (acc << 32LL);
161 
162  // Carry forward the high bits of acc to initiate the computation of the
163  // low 32 bits of high
164  acc2 = (acc >> 32LL) | (carry << 32LL);
165  carry = 0;
166 
167  acc = acc2 + b * h;
168  if (acc < acc2) {
169  carry++;
170  }
171  acc2 = acc + c * g;
172  if (acc2 < acc) {
173  carry++;
174  }
175  acc = acc2 + d * f;
176  if (acc < acc2) {
177  carry++;
178  }
179  uint64_t high = acc & LOW;
180 
181  // Start to compute the high 32 bits of high.
182  acc2 = (acc >> 32LL) | (carry << 32LL);
183 
184  acc = acc2 + a * h;
185  acc2 = acc + b * g;
186  acc = acc2 + c * f;
187  acc2 = acc + d * e;
188  high |= (acc2 << 32LL);
189 
190  return TensorUInt128<uint64_t, uint64_t>(high, low);
191 }
192 
193 template <typename HL, typename LL, typename HR, typename LR>
194 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE
195 static TensorUInt128<uint64_t, uint64_t> operator / (const TensorUInt128<HL, LL>& lhs, const TensorUInt128<HR, LR>& rhs)
196 {
197  if (rhs == TensorUInt128<static_val<0>, static_val<1> >(1)) {
198  return TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
199  } else if (lhs < rhs) {
200  return TensorUInt128<uint64_t, uint64_t>(0);
201  } else {
202  // calculate the biggest power of 2 times rhs that's less than or equal to lhs
203  TensorUInt128<uint64_t, uint64_t> power2(1);
204  TensorUInt128<uint64_t, uint64_t> d(rhs);
205  TensorUInt128<uint64_t, uint64_t> tmp(lhs - d);
206  while (lhs >= d) {
207  tmp = tmp - d;
208  d = d + d;
209  power2 = power2 + power2;
210  }
211 
212  tmp = TensorUInt128<uint64_t, uint64_t>(lhs.high, lhs.low);
213  TensorUInt128<uint64_t, uint64_t> result(0);
214  while (power2 != TensorUInt128<static_val<0>, static_val<0> >(0)) {
215  if (tmp >= d) {
216  tmp = tmp - d;
217  result = result + power2;
218  }
219  // Shift right
220  power2 = TensorUInt128<uint64_t, uint64_t>(power2.high >> 1, (power2.low >> 1) | (power2.high << 63));
221  d = TensorUInt128<uint64_t, uint64_t>(d.high >> 1, (d.low >> 1) | (d.high << 63));
222  }
223 
224  return result;
225  }
226 }
227 
228 
229 } // namespace internal
230 } // namespace Eigen
231 
232 
233 #endif // EIGEN_CXX11_TENSOR_TENSOR_UINT128_H
Namespace containing all symbols from the Eigen library.
Definition: CXX11Meta.h:13