1 //===-- A class to manipulate wide integers. --------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_LIBC_UTILS_CPP_UINT_H
10 #define LLVM_LIBC_UTILS_CPP_UINT_H
11 
12 #include "Array.h"
13 
14 #include <stddef.h> // For size_t
15 #include <stdint.h>
16 
17 namespace __llvm_libc {
18 namespace cpp {
19 
20 template <size_t Bits> class UInt {
21 
22   static_assert(Bits > 0 && Bits % 64 == 0,
23                 "Number of bits in UInt should be a multiple of 64.");
24   static constexpr size_t WordCount = Bits / 64;
25   uint64_t val[WordCount];
26 
27   static constexpr uint64_t MASK32 = 0xFFFFFFFFu;
28 
29   static constexpr uint64_t low(uint64_t v) { return v & MASK32; }
30   static constexpr uint64_t high(uint64_t v) { return (v >> 32) & MASK32; }
31 
32 public:
33   constexpr UInt() {}
34 
35   constexpr UInt(const UInt<Bits> &other) {
36     for (size_t i = 0; i < WordCount; ++i)
37       val[i] = other.val[i];
38   }
39 
40   // Initialize the first word to |v| and the rest to 0.
41   constexpr UInt(uint64_t v) {
42     val[0] = v;
43     for (size_t i = 1; i < WordCount; ++i) {
44       val[i] = 0;
45     }
46   }
47   constexpr explicit UInt(const cpp::Array<uint64_t, WordCount> &words) {
48     for (size_t i = 0; i < WordCount; ++i)
49       val[i] = words[i];
50   }
51 
52   constexpr explicit operator uint64_t() const { return val[0]; }
53 
54   constexpr explicit operator uint32_t() const {
55     return uint32_t(uint64_t(*this));
56   }
57 
58   constexpr explicit operator uint8_t() const {
59     return uint8_t(uint64_t(*this));
60   }
61 
62   UInt<Bits> &operator=(const UInt<Bits> &other) {
63     for (size_t i = 0; i < WordCount; ++i)
64       val[i] = other.val[i];
65     return *this;
66   }
67 
68   // Add x to this number and store the result in this number.
69   // Returns the carry value produced by the addition operation.
70   constexpr uint64_t add(const UInt<Bits> &x) {
71     uint64_t carry = 0;
72     for (size_t i = 0; i < WordCount; ++i) {
73       uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry;
74       carry = high(res_lo);
75       res_lo = low(res_lo);
76 
77       uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry;
78       carry = high(res_hi);
79       res_hi = low(res_hi);
80 
81       val[i] = res_lo + (res_hi << 32);
82     }
83     return carry;
84   }
85 
86   constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
87     UInt<Bits> result(*this);
88     result.add(other);
89     return result;
90   }
91 
92   // Multiply this number with x and store the result in this number. It is
93   // implemented using the long multiplication algorithm by splitting the
94   // 64-bit words of this number and |x| in to 32-bit halves but peforming
95   // the operations using 64-bit numbers. This ensures that we don't lose the
96   // carry bits.
97   // Returns the carry value produced by the multiplication operation.
98   constexpr uint64_t mul(uint64_t x) {
99     uint64_t x_lo = low(x);
100     uint64_t x_hi = high(x);
101 
102     cpp::Array<uint64_t, WordCount + 1> row1;
103     uint64_t carry = 0;
104     for (size_t i = 0; i < WordCount; ++i) {
105       uint64_t l = low(val[i]);
106       uint64_t h = high(val[i]);
107       uint64_t p1 = x_lo * l;
108       uint64_t p2 = x_lo * h;
109 
110       uint64_t res_lo = low(p1) + carry;
111       carry = high(res_lo);
112       uint64_t res_hi = high(p1) + low(p2) + carry;
113       carry = high(res_hi) + high(p2);
114 
115       res_lo = low(res_lo);
116       res_hi = low(res_hi);
117       row1[i] = res_lo + (res_hi << 32);
118     }
119     row1[WordCount] = carry;
120 
121     cpp::Array<uint64_t, WordCount + 1> row2;
122     row2[0] = 0;
123     carry = 0;
124     for (size_t i = 0; i < WordCount; ++i) {
125       uint64_t l = low(val[i]);
126       uint64_t h = high(val[i]);
127       uint64_t p1 = x_hi * l;
128       uint64_t p2 = x_hi * h;
129 
130       uint64_t res_lo = low(p1) + carry;
131       carry = high(res_lo);
132       uint64_t res_hi = high(p1) + low(p2) + carry;
133       carry = high(res_hi) + high(p2);
134 
135       res_lo = low(res_lo);
136       res_hi = low(res_hi);
137       row2[i] = res_lo + (res_hi << 32);
138     }
139     row2[WordCount] = carry;
140 
141     UInt<(WordCount + 1) * 64> r1(row1), r2(row2);
142     r2.shift_left(32);
143     r1.add(r2);
144     for (size_t i = 0; i < WordCount; ++i) {
145       val[i] = r1[i];
146     }
147     return r1[WordCount];
148   }
149 
150   constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
151     UInt<Bits> result(0);
152     for (size_t i = 0; i < WordCount; ++i) {
153       UInt<Bits> row_result(*this);
154       row_result.mul(other[i]);
155       row_result.shift_left(64 * i);
156       result = result + row_result;
157     }
158     return result;
159   }
160 
161   constexpr void shift_left(size_t s) {
162     const size_t drop = s / 64;  // Number of words to drop
163     const size_t shift = s % 64; // Bits to shift in the remaining words.
164     const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift);
165 
166     for (size_t i = WordCount; drop > 0 && i > 0; --i) {
167       if (i > drop)
168         val[i - 1] = val[i - drop - 1];
169       else
170         val[i - 1] = 0;
171     }
172     for (size_t i = WordCount; shift > 0 && i > drop; --i) {
173       uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift);
174       val[i - 1] <<= shift;
175       if (i < WordCount)
176         val[i] |= drop_val;
177     }
178   }
179 
180   constexpr UInt<Bits> operator<<(size_t s) const {
181     UInt<Bits> result(*this);
182     result.shift_left(s);
183     return result;
184   }
185 
186   constexpr void shift_right(size_t s) {
187     const size_t drop = s / 64;  // Number of words to drop
188     const size_t shift = s % 64; // Bit shift in the remaining words.
189     const uint64_t mask = (uint64_t(1) << shift) - 1;
190 
191     for (size_t i = 0; drop > 0 && i < WordCount; ++i) {
192       if (i + drop < WordCount)
193         val[i] = val[i + drop];
194       else
195         val[i] = 0;
196     }
197     for (size_t i = 0; shift > 0 && i < WordCount; ++i) {
198       uint64_t drop_val = ((val[i] & mask) << (64 - shift));
199       val[i] >>= shift;
200       if (i > 0)
201         val[i - 1] |= drop_val;
202     }
203   }
204 
205   constexpr UInt<Bits> operator>>(size_t s) const {
206     UInt<Bits> result(*this);
207     result.shift_right(s);
208     return result;
209   }
210 
211   constexpr UInt<Bits> operator&(const UInt<Bits> &other) const {
212     UInt<Bits> result;
213     for (size_t i = 0; i < WordCount; ++i)
214       result.val[i] = val[i] & other.val[i];
215     return result;
216   }
217 
218   constexpr UInt<Bits> operator|(const UInt<Bits> &other) const {
219     UInt<Bits> result;
220     for (size_t i = 0; i < WordCount; ++i)
221       result.val[i] = val[i] | other.val[i];
222     return result;
223   }
224 
225   constexpr UInt<Bits> operator^(const UInt<Bits> &other) const {
226     UInt<Bits> result;
227     for (size_t i = 0; i < WordCount; ++i)
228       result.val[i] = val[i] ^ other.val[i];
229     return result;
230   }
231 
232   constexpr bool operator==(const UInt<Bits> &other) const {
233     for (size_t i = 0; i < WordCount; ++i) {
234       if (val[i] != other.val[i])
235         return false;
236     }
237     return true;
238   }
239 
240   constexpr bool operator!=(const UInt<Bits> &other) const {
241     for (size_t i = 0; i < WordCount; ++i) {
242       if (val[i] != other.val[i])
243         return true;
244     }
245     return false;
246   }
247 
248   constexpr bool operator>(const UInt<Bits> &other) const {
249     for (size_t i = WordCount; i > 0; --i) {
250       uint64_t word = val[i - 1];
251       uint64_t other_word = other.val[i - 1];
252       if (word > other_word)
253         return true;
254       else if (word < other_word)
255         return false;
256     }
257     // Equal
258     return false;
259   }
260 
261   constexpr bool operator>=(const UInt<Bits> &other) const {
262     for (size_t i = WordCount; i > 0; --i) {
263       uint64_t word = val[i - 1];
264       uint64_t other_word = other.val[i - 1];
265       if (word > other_word)
266         return true;
267       else if (word < other_word)
268         return false;
269     }
270     // Equal
271     return true;
272   }
273 
274   constexpr bool operator<(const UInt<Bits> &other) const {
275     for (size_t i = WordCount; i > 0; --i) {
276       uint64_t word = val[i - 1];
277       uint64_t other_word = other.val[i - 1];
278       if (word > other_word)
279         return false;
280       else if (word < other_word)
281         return true;
282     }
283     // Equal
284     return false;
285   }
286 
287   constexpr bool operator<=(const UInt<Bits> &other) const {
288     for (size_t i = WordCount; i > 0; --i) {
289       uint64_t word = val[i - 1];
290       uint64_t other_word = other.val[i - 1];
291       if (word > other_word)
292         return false;
293       else if (word < other_word)
294         return true;
295     }
296     // Equal
297     return true;
298   }
299 
300   // Return the i-th 64-bit word of the number.
301   constexpr const uint64_t &operator[](size_t i) const { return val[i]; }
302 
303   // Return the i-th 64-bit word of the number.
304   constexpr uint64_t &operator[](size_t i) { return val[i]; }
305 
306   uint64_t *data() { return val; }
307 
308   const uint64_t *data() const { return val; }
309 };
310 
311 template <>
312 constexpr UInt<128> UInt<128>::operator*(const UInt<128> &other) const {
313   // temp low covers bits 0-63, middle covers 32-95, high covers 64-127, and
314   // high overflow covers 96-159.
315   uint64_t temp_low = low(val[0]) * low(other[0]);
316   uint64_t temp_middle_1 = low(val[0]) * high(other[0]);
317   uint64_t temp_middle_2 = high(val[0]) * low(other[0]);
318 
319   // temp_middle is split out so that overflows can be handled, but since
320   // but since the result will be truncated to 128 bits any overflow from here
321   // on doesn't matter.
322   uint64_t temp_high = low(val[0]) * low(other[1]) +
323                        high(val[0]) * high(other[0]) +
324                        low(val[1]) * low(other[0]);
325 
326   uint64_t temp_high_overflow =
327       low(val[0]) * high(other[1]) + high(val[0]) * low(other[1]) +
328       low(val[1]) * high(other[0]) + high(val[1]) * low(other[0]);
329 
330   // temp_low_middle has just the high 32 bits of low, as well as any
331   // overflow.
332   uint64_t temp_low_middle =
333       high(temp_low) + low(temp_middle_1) + low(temp_middle_2);
334 
335   uint64_t new_low = low(temp_low) + (low(temp_low_middle) << 32);
336   uint64_t new_high = high(temp_low_middle) + high(temp_middle_1) +
337                       high(temp_middle_2) + temp_high +
338                       (low(temp_high_overflow) << 32);
339   UInt<128> result(0);
340   result[0] = new_low;
341   result[1] = new_high;
342   return result;
343 }
344 
345 } // namespace cpp
346 } // namespace __llvm_libc
347 
348 /* TODO: determine the best way to support uint128 using this class.
349 #if !defined(__SIZEOF_INT128__)
350 using __uint128_t = __llvm_libc::internal::UInt<128>;
351 #endif // uint128 is not defined, define it with this class.
352 */
353 
354 #endif // LLVM_LIBC_UTILS_CPP_UINT_H
355