Warning: This file is not a C or C++ file. It does not have highlighting.
1 | //===-- include/flang/Evaluate/integer.h ------------------------*- 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 FORTRAN_EVALUATE_INTEGER_H_ |
10 | #define FORTRAN_EVALUATE_INTEGER_H_ |
11 | |
12 | // Emulates binary integers of an arbitrary (but fixed) bit size for use |
13 | // when the host C++ environment does not support that size or when the |
14 | // full suite of Fortran's integer intrinsic scalar functions are needed. |
15 | // The data model is typeless, so signed* and unsigned operations |
16 | // are distinguished from each other with distinct member function interfaces. |
17 | // (*"Signed" here means two's-complement, just to be clear. Ones'-complement |
18 | // and signed-magnitude encodings appear to be extinct in 2018.) |
19 | |
20 | #include "flang/Common/bit-population-count.h" |
21 | #include "flang/Common/leading-zero-bit-count.h" |
22 | #include "flang/Evaluate/common.h" |
23 | #include <cinttypes> |
24 | #include <climits> |
25 | #include <cstddef> |
26 | #include <cstdint> |
27 | #include <string> |
28 | #include <type_traits> |
29 | |
30 | // Some environments, viz. glibc 2.17 and *BSD, allow the macro HUGE |
31 | // to leak out of <math.h>. |
32 | #undef HUGE |
33 | |
34 | namespace Fortran::evaluate::value { |
35 | |
36 | // Implements an integer as an assembly of smaller host integer parts |
37 | // that constitute the digits of a large-radix fixed-point number. |
38 | // For best performance, the type of these parts should be half of the |
39 | // size of the largest efficient integer supported by the host processor. |
40 | // These parts are stored in either little- or big-endian order, which can |
41 | // match that of the host's endianness or not; but if the ordering matches |
42 | // that of the host, raw host data can be overlaid with a properly configured |
43 | // instance of this class and used in situ. |
44 | // To facilitate exhaustive testing of what would otherwise be more rare |
45 | // edge cases, this class template may be configured to use other part |
46 | // types &/or partial fields in the parts. The radix (i.e., the number |
47 | // of possible values in a part), however, must be a power of two; this |
48 | // template class is not generalized to enable, say, decimal arithmetic. |
49 | // Member functions that correspond to Fortran intrinsic functions are |
50 | // named accordingly in ALL CAPS so that they can be referenced easily in |
51 | // the language standard. |
52 | template <int BITS, bool IS_LITTLE_ENDIAN = isHostLittleEndian, |
53 | int PARTBITS = BITS <= 32 ? BITS |
54 | : BITS % 32 == 0 ? 32 |
55 | : BITS % 16 == 0 ? 16 |
56 | : 8, |
57 | typename PART = HostUnsignedInt<PARTBITS>, |
58 | typename BIGPART = HostUnsignedInt<PARTBITS * 2>, int ALIGNMENT = BITS> |
59 | class Integer { |
60 | public: |
61 | static constexpr int bits{BITS}; |
62 | static constexpr int partBits{PARTBITS}; |
63 | using Part = PART; |
64 | using BigPart = BIGPART; |
65 | static_assert(std::is_integral_v<Part>); |
66 | static_assert(std::is_unsigned_v<Part>); |
67 | static_assert(std::is_integral_v<BigPart>); |
68 | static_assert(std::is_unsigned_v<BigPart>); |
69 | static_assert(CHAR_BIT * sizeof(BigPart) >= 2 * partBits); |
70 | static constexpr bool littleEndian{IS_LITTLE_ENDIAN}; |
71 | |
72 | private: |
73 | static constexpr int maxPartBits{CHAR_BIT * sizeof(Part)}; |
74 | static_assert(partBits > 0 && partBits <= maxPartBits); |
75 | static constexpr int extraPartBits{maxPartBits - partBits}; |
76 | static constexpr int parts{(bits + partBits - 1) / partBits}; |
77 | static_assert(parts >= 1); |
78 | static constexpr int extraTopPartBits{ |
79 | extraPartBits + (parts * partBits) - bits}; |
80 | static constexpr int topPartBits{maxPartBits - extraTopPartBits}; |
81 | static_assert(topPartBits > 0 && topPartBits <= partBits); |
82 | static_assert((parts - 1) * partBits + topPartBits == bits); |
83 | static constexpr Part partMask{static_cast<Part>(~0) >> extraPartBits}; |
84 | static constexpr Part topPartMask{static_cast<Part>(~0) >> extraTopPartBits}; |
85 | static constexpr int partsWithAlignment{ |
86 | (ALIGNMENT + partBits - 1) / partBits}; |
87 | |
88 | public: |
89 | // Some types used for member function results |
90 | struct ValueWithOverflow { |
91 | Integer value; |
92 | bool overflow; |
93 | }; |
94 | |
95 | struct ValueWithCarry { |
96 | Integer value; |
97 | bool carry; |
98 | }; |
99 | |
100 | struct Product { |
101 | bool SignedMultiplicationOverflowed() const { |
102 | return lower.IsNegative() ? (upper.POPCNT() != bits) : !upper.IsZero(); |
103 | } |
104 | Integer upper, lower; |
105 | }; |
106 | |
107 | struct QuotientWithRemainder { |
108 | Integer quotient, remainder; |
109 | bool divisionByZero, overflow; |
110 | }; |
111 | |
112 | struct PowerWithErrors { |
113 | Integer power; |
114 | bool divisionByZero{false}, overflow{false}, zeroToZero{false}; |
115 | }; |
116 | |
117 | // Constructors and value-generating static functions |
118 | constexpr Integer() { Clear(); } // default constructor: zero |
119 | constexpr Integer(const Integer &) = default; |
120 | constexpr Integer(Integer &&) = default; |
121 | |
122 | // C++'s integral types can all be converted to Integer |
123 | // with silent truncation. |
124 | template <typename INT, typename = std::enable_if_t<std::is_integral_v<INT>>> |
125 | constexpr Integer(INT n) { |
126 | constexpr int nBits = CHAR_BIT * sizeof n; |
127 | if constexpr (nBits < partBits) { |
128 | if constexpr (std::is_unsigned_v<INT>) { |
129 | // Zero-extend an unsigned smaller value. |
130 | SetLEPart(0, n); |
131 | for (int j{1}; j < parts; ++j) { |
132 | SetLEPart(j, 0); |
133 | } |
134 | } else { |
135 | // n has a signed type smaller than the usable |
136 | // bits in a Part. |
137 | // Avoid conversions that change both size and sign. |
138 | using SignedPart = std::make_signed_t<Part>; |
139 | Part p = static_cast<SignedPart>(n); |
140 | SetLEPart(0, p); |
141 | if constexpr (parts > 1) { |
142 | Part signExtension = static_cast<SignedPart>(-(n < 0)); |
143 | for (int j{1}; j < parts; ++j) { |
144 | SetLEPart(j, signExtension); |
145 | } |
146 | } |
147 | } |
148 | } else { |
149 | // n has some integral type no smaller than the usable |
150 | // bits in a Part. |
151 | // Ensure that all shifts are smaller than a whole word. |
152 | if constexpr (std::is_unsigned_v<INT>) { |
153 | for (int j{0}; j < parts; ++j) { |
154 | SetLEPart(j, static_cast<Part>(n)); |
155 | if constexpr (nBits > partBits) { |
156 | n >>= partBits; |
157 | } else { |
158 | n = 0; |
159 | } |
160 | } |
161 | } else { |
162 | // Avoid left shifts of negative signed values (that's an undefined |
163 | // behavior in C++). |
164 | auto signExtension{std::make_unsigned_t<INT>(n < 0)}; |
165 | signExtension = ~signExtension + 1; |
166 | static_assert(nBits >= partBits); |
167 | if constexpr (nBits > partBits) { |
168 | signExtension <<= nBits - partBits; |
169 | for (int j{0}; j < parts; ++j) { |
170 | SetLEPart(j, static_cast<Part>(n)); |
171 | n >>= partBits; |
172 | n |= signExtension; |
173 | } |
174 | } else { |
175 | SetLEPart(0, static_cast<Part>(n)); |
176 | for (int j{1}; j < parts; ++j) { |
177 | SetLEPart(j, static_cast<Part>(signExtension)); |
178 | } |
179 | } |
180 | } |
181 | } |
182 | } |
183 | |
184 | constexpr Integer &operator=(const Integer &) = default; |
185 | |
186 | constexpr bool operator<(const Integer &that) const { |
187 | return CompareSigned(that) == Ordering::Less; |
188 | } |
189 | constexpr bool operator<=(const Integer &that) const { |
190 | return CompareSigned(that) != Ordering::Greater; |
191 | } |
192 | constexpr bool operator==(const Integer &that) const { |
193 | return CompareSigned(that) == Ordering::Equal; |
194 | } |
195 | constexpr bool operator!=(const Integer &that) const { |
196 | return !(*this == that); |
197 | } |
198 | constexpr bool operator>=(const Integer &that) const { |
199 | return CompareSigned(that) != Ordering::Less; |
200 | } |
201 | constexpr bool operator>(const Integer &that) const { |
202 | return CompareSigned(that) == Ordering::Greater; |
203 | } |
204 | |
205 | // Left-justified mask (e.g., MASKL(1) has only its sign bit set) |
206 | static constexpr Integer MASKL(int places) { |
207 | if (places <= 0) { |
208 | return {}; |
209 | } else if (places >= bits) { |
210 | return MASKR(bits); |
211 | } else { |
212 | return MASKR(bits - places).NOT(); |
213 | } |
214 | } |
215 | |
216 | // Right-justified mask (e.g., MASKR(1) == 1, MASKR(2) == 3, &c.) |
217 | static constexpr Integer MASKR(int places) { |
218 | Integer result{nullptr}; |
219 | int j{0}; |
220 | for (; j + 1 < parts && places >= partBits; ++j, places -= partBits) { |
221 | result.LEPart(j) = partMask; |
222 | } |
223 | if (places > 0) { |
224 | if (j + 1 < parts) { |
225 | result.LEPart(j++) = partMask >> (partBits - places); |
226 | } else if (j + 1 == parts) { |
227 | if (places >= topPartBits) { |
228 | result.LEPart(j++) = topPartMask; |
229 | } else { |
230 | result.LEPart(j++) = topPartMask >> (topPartBits - places); |
231 | } |
232 | } |
233 | } |
234 | for (; j < parts; ++j) { |
235 | result.LEPart(j) = 0; |
236 | } |
237 | return result; |
238 | } |
239 | |
240 | static constexpr ValueWithOverflow Read( |
241 | const char *&pp, std::uint64_t base = 10, bool isSigned = false) { |
242 | Integer result; |
243 | bool overflow{false}; |
244 | const char *p{pp}; |
245 | while (*p == ' ' || *p == '\t') { |
246 | ++p; |
247 | } |
248 | bool negate{*p == '-'}; |
249 | if (negate || *p == '+') { |
250 | while (*++p == ' ' || *p == '\t') { |
251 | } |
252 | } |
253 | Integer radix{base}; |
254 | // This code makes assumptions about local contiguity in regions of the |
255 | // character set and only works up to base 36. These assumptions hold |
256 | // for all current combinations of surviving character sets (ASCII, UTF-8, |
257 | // EBCDIC) and the bases used in Fortran source and formatted I/O |
258 | // (viz., 2, 8, 10, & 16). But: management thought that a disclaimer |
259 | // might be needed here to warn future users of this code about these |
260 | // assumptions, so here you go, future programmer in some postapocalyptic |
261 | // hellscape, and best of luck with the inexorable killer robots. |
262 | for (; std::uint64_t digit = *p; ++p) { |
263 | if (digit >= '0' && digit <= '9' && digit < '0' + base) { |
264 | digit -= '0'; |
265 | } else if (base > 10 && digit >= 'A' && digit < 'A' + base - 10) { |
266 | digit -= 'A' - 10; |
267 | } else if (base > 10 && digit >= 'a' && digit < 'a' + base - 10) { |
268 | digit -= 'a' - 10; |
269 | } else { |
270 | break; |
271 | } |
272 | Product shifted{result.MultiplyUnsigned(radix)}; |
273 | overflow |= !shifted.upper.IsZero(); |
274 | ValueWithCarry next{shifted.lower.AddUnsigned(Integer{digit})}; |
275 | overflow |= next.carry; |
276 | result = next.value; |
277 | } |
278 | pp = p; |
279 | if (negate) { |
280 | result = result.Negate().value; |
281 | overflow |= isSigned && !result.IsNegative() && !result.IsZero(); |
282 | } else { |
283 | overflow |= isSigned && result.IsNegative(); |
284 | } |
285 | return {result, overflow}; |
286 | } |
287 | |
288 | template <typename FROM> |
289 | static constexpr ValueWithOverflow ConvertUnsigned(const FROM &that) { |
290 | std::uint64_t field{that.ToUInt64()}; |
291 | ValueWithOverflow result{field, false}; |
292 | if constexpr (bits < 64) { |
293 | result.overflow = (field >> bits) != 0; |
294 | } |
295 | for (int j{64}; j < that.bits && !result.overflow; j += 64) { |
296 | field = that.SHIFTR(j).ToUInt64(); |
297 | if (bits <= j) { |
298 | result.overflow = field != 0; |
299 | } else { |
300 | result.value = result.value.IOR(Integer{field}.SHIFTL(j)); |
301 | if (bits < j + 64) { |
302 | result.overflow = (field >> (bits - j)) != 0; |
303 | } |
304 | } |
305 | } |
306 | return result; |
307 | } |
308 | |
309 | template <typename FROM> |
310 | static constexpr ValueWithOverflow ConvertSigned(const FROM &that) { |
311 | ValueWithOverflow result{ConvertUnsigned(that)}; |
312 | if constexpr (bits > FROM::bits) { |
313 | if (that.IsNegative()) { |
314 | result.value = result.value.IOR(MASKL(bits - FROM::bits)); |
315 | } |
316 | result.overflow = false; |
317 | } else if constexpr (bits < FROM::bits) { |
318 | auto back{FROM::template ConvertSigned(result.value)}; |
319 | result.overflow = back.value.CompareUnsigned(that) != Ordering::Equal; |
320 | } |
321 | return result; |
322 | } |
323 | |
324 | std::string UnsignedDecimal() const { |
325 | if constexpr (bits < 4) { |
326 | char digit = '0' + ToUInt64(); |
327 | return {digit}; |
328 | } else if (IsZero()) { |
329 | return {'0'}; |
330 | } else { |
331 | QuotientWithRemainder qr{DivideUnsigned(10)}; |
332 | char digit = '0' + qr.remainder.ToUInt64(); |
333 | if (qr.quotient.IsZero()) { |
334 | return {digit}; |
335 | } else { |
336 | return qr.quotient.UnsignedDecimal() + digit; |
337 | } |
338 | } |
339 | } |
340 | |
341 | std::string SignedDecimal() const { |
342 | if (IsNegative()) { |
343 | return std::string{'-'} + Negate().value.UnsignedDecimal(); |
344 | } else { |
345 | return UnsignedDecimal(); |
346 | } |
347 | } |
348 | |
349 | // Omits a leading "0x". |
350 | std::string Hexadecimal() const { |
351 | std::string result; |
352 | int digits{(bits + 3) >> 2}; |
353 | for (int j{0}; j < digits; ++j) { |
354 | int pos{(digits - 1 - j) * 4}; |
355 | char nybble = IBITS(pos, 4).ToUInt64(); |
356 | if (nybble != 0 || !result.empty() || j + 1 == digits) { |
357 | char digit = '0' + nybble; |
358 | if (digit > '9') { |
359 | digit += 'a' - ('9' + 1); |
360 | } |
361 | result += digit; |
362 | } |
363 | } |
364 | return result; |
365 | } |
366 | |
367 | static constexpr int DIGITS{bits - 1}; // don't count the sign bit |
368 | static constexpr Integer HUGE() { return MASKR(bits - 1); } |
369 | static constexpr Integer Least() { return MASKL(1); } |
370 | static constexpr int RANGE{// in the sense of SELECTED_INT_KIND |
371 | // This magic value is LOG10(2.)*1E12. |
372 | static_cast<int>(((bits - 1) * 301029995664) / 1000000000000)}; |
373 | |
374 | constexpr bool IsZero() const { |
375 | for (int j{0}; j < parts; ++j) { |
376 | if (part_[j] != 0) { |
377 | return false; |
378 | } |
379 | } |
380 | return true; |
381 | } |
382 | |
383 | constexpr bool IsNegative() const { |
384 | return (LEPart(parts - 1) >> (topPartBits - 1)) & 1; |
385 | } |
386 | |
387 | constexpr Ordering CompareToZeroSigned() const { |
388 | if (IsNegative()) { |
389 | return Ordering::Less; |
390 | } else if (IsZero()) { |
391 | return Ordering::Equal; |
392 | } else { |
393 | return Ordering::Greater; |
394 | } |
395 | } |
396 | |
397 | // Count the number of contiguous most-significant bit positions |
398 | // that are clear. |
399 | constexpr int LEADZ() const { |
400 | if (LEPart(parts - 1) != 0) { |
401 | int lzbc{common::LeadingZeroBitCount(LEPart(parts - 1))}; |
402 | return lzbc - extraTopPartBits; |
403 | } |
404 | int upperZeroes{topPartBits}; |
405 | for (int j{1}; j < parts; ++j) { |
406 | if (Part p{LEPart(parts - 1 - j)}) { |
407 | int lzbc{common::LeadingZeroBitCount(p)}; |
408 | return upperZeroes + lzbc - extraPartBits; |
409 | } |
410 | upperZeroes += partBits; |
411 | } |
412 | return bits; |
413 | } |
414 | |
415 | // Count the number of bit positions that are set. |
416 | constexpr int POPCNT() const { |
417 | int count{0}; |
418 | for (int j{0}; j < parts; ++j) { |
419 | count += common::BitPopulationCount(part_[j]); |
420 | } |
421 | return count; |
422 | } |
423 | |
424 | // True when POPCNT is odd. |
425 | constexpr bool POPPAR() const { return POPCNT() & 1; } |
426 | |
427 | constexpr int TRAILZ() const { |
428 | auto minus1{AddUnsigned(MASKR(bits))}; // { x-1, carry = x > 0 } |
429 | if (!minus1.carry) { |
430 | return bits; // was zero |
431 | } else { |
432 | // x ^ (x-1) has all bits set at and below original least-order set bit. |
433 | return IEOR(minus1.value).POPCNT() - 1; |
434 | } |
435 | } |
436 | |
437 | constexpr bool BTEST(int pos) const { |
438 | if (pos < 0 || pos >= bits) { |
439 | return false; |
440 | } else { |
441 | return (LEPart(pos / partBits) >> (pos % partBits)) & 1; |
442 | } |
443 | } |
444 | |
445 | constexpr Ordering CompareUnsigned(const Integer &y) const { |
446 | for (int j{parts}; j-- > 0;) { |
447 | if (LEPart(j) > y.LEPart(j)) { |
448 | return Ordering::Greater; |
449 | } |
450 | if (LEPart(j) < y.LEPart(j)) { |
451 | return Ordering::Less; |
452 | } |
453 | } |
454 | return Ordering::Equal; |
455 | } |
456 | |
457 | constexpr bool BGE(const Integer &y) const { |
458 | return CompareUnsigned(y) != Ordering::Less; |
459 | } |
460 | constexpr bool BGT(const Integer &y) const { |
461 | return CompareUnsigned(y) == Ordering::Greater; |
462 | } |
463 | constexpr bool BLE(const Integer &y) const { return !BGT(y); } |
464 | constexpr bool BLT(const Integer &y) const { return !BGE(y); } |
465 | |
466 | constexpr Ordering CompareSigned(const Integer &y) const { |
467 | bool isNegative{IsNegative()}; |
468 | if (isNegative != y.IsNegative()) { |
469 | return isNegative ? Ordering::Less : Ordering::Greater; |
470 | } |
471 | return CompareUnsigned(y); |
472 | } |
473 | |
474 | template <typename UINT = std::uint64_t> constexpr UINT ToUInt() const { |
475 | UINT n{LEPart(0)}; |
476 | std::size_t filled{partBits}; |
477 | constexpr std::size_t maxBits{CHAR_BIT * sizeof n}; |
478 | for (int j{1}; filled < maxBits && j < parts; ++j, filled += partBits) { |
479 | n |= UINT{LEPart(j)} << filled; |
480 | } |
481 | return n; |
482 | } |
483 | |
484 | template <typename SINT = std::int64_t, typename UINT = std::uint64_t> |
485 | constexpr SINT ToSInt() const { |
486 | SINT n = ToUInt<UINT>(); |
487 | constexpr std::size_t maxBits{CHAR_BIT * sizeof n}; |
488 | if constexpr (bits < maxBits) { |
489 | // Avoid left shifts of negative signed values (that's an undefined |
490 | // behavior in C++). |
491 | auto u{std::make_unsigned_t<SINT>(ToUInt())}; |
492 | u = (u >> (bits - 1)) << (bits - 1); // Get the sign bit only. |
493 | u = ~u + 1; // Negate top bits if not 0. |
494 | n |= static_cast<SINT>(u); |
495 | } |
496 | return n; |
497 | } |
498 | |
499 | constexpr std::uint64_t ToUInt64() const { return ToUInt<std::uint64_t>(); } |
500 | |
501 | constexpr std::int64_t ToInt64() const { |
502 | return ToSInt<std::int64_t, std::uint64_t>(); |
503 | } |
504 | |
505 | // Ones'-complement (i.e., C's ~) |
506 | constexpr Integer NOT() const { |
507 | Integer result{nullptr}; |
508 | for (int j{0}; j < parts; ++j) { |
509 | result.SetLEPart(j, ~LEPart(j)); |
510 | } |
511 | return result; |
512 | } |
513 | |
514 | // Two's-complement negation (-x = ~x + 1). |
515 | // An overflow flag accompanies the result, and will be true when the |
516 | // operand is the most negative signed number (MASKL(1)). |
517 | constexpr ValueWithOverflow Negate() const { |
518 | Integer result{nullptr}; |
519 | Part carry{1}; |
520 | for (int j{0}; j + 1 < parts; ++j) { |
521 | Part newCarry{LEPart(j) == 0 && carry}; |
522 | result.SetLEPart(j, ~LEPart(j) + carry); |
523 | carry = newCarry; |
524 | } |
525 | Part top{LEPart(parts - 1)}; |
526 | result.SetLEPart(parts - 1, ~top + carry); |
527 | bool overflow{top != 0 && result.LEPart(parts - 1) == top}; |
528 | return {result, overflow}; |
529 | } |
530 | |
531 | constexpr ValueWithOverflow ABS() const { |
532 | if (IsNegative()) { |
533 | return Negate(); |
534 | } else { |
535 | return {*this, false}; |
536 | } |
537 | } |
538 | |
539 | // Shifts the operand left when the count is positive, right when negative. |
540 | // Vacated bit positions are filled with zeroes. |
541 | constexpr Integer ISHFT(int count) const { |
542 | if (count < 0) { |
543 | return SHIFTR(-count); |
544 | } else { |
545 | return SHIFTL(count); |
546 | } |
547 | } |
548 | |
549 | // Left shift with zero fill. |
550 | constexpr Integer SHIFTL(int count) const { |
551 | if (count <= 0) { |
552 | return *this; |
553 | } else { |
554 | Integer result{nullptr}; |
555 | int shiftParts{count / partBits}; |
556 | int bitShift{count - partBits * shiftParts}; |
557 | int j{parts - 1}; |
558 | if (bitShift == 0) { |
559 | for (; j >= shiftParts; --j) { |
560 | result.SetLEPart(j, LEPart(j - shiftParts)); |
561 | } |
562 | for (; j >= 0; --j) { |
563 | result.LEPart(j) = 0; |
564 | } |
565 | } else { |
566 | for (; j > shiftParts; --j) { |
567 | result.SetLEPart(j, |
568 | ((LEPart(j - shiftParts) << bitShift) | |
569 | (LEPart(j - shiftParts - 1) >> (partBits - bitShift)))); |
570 | } |
571 | if (j == shiftParts) { |
572 | result.SetLEPart(j, LEPart(0) << bitShift); |
573 | --j; |
574 | } |
575 | for (; j >= 0; --j) { |
576 | result.LEPart(j) = 0; |
577 | } |
578 | } |
579 | return result; |
580 | } |
581 | } |
582 | |
583 | // Circular shift of a field of least-significant bits. The least-order |
584 | // "size" bits are shifted circularly in place by "count" positions; |
585 | // the shift is leftward if count is nonnegative, rightward otherwise. |
586 | // Higher-order bits are unchanged. |
587 | constexpr Integer ISHFTC(int count, int size = bits) const { |
588 | if (count == 0 || size <= 0) { |
589 | return *this; |
590 | } |
591 | if (size > bits) { |
592 | size = bits; |
593 | } |
594 | count %= size; |
595 | if (count == 0) { |
596 | return *this; |
597 | } |
598 | int middleBits{size - count}, leastBits{count}; |
599 | if (count < 0) { |
600 | middleBits = -count; |
601 | leastBits = size + count; |
602 | } |
603 | if (size == bits) { |
604 | return SHIFTL(leastBits).IOR(SHIFTR(middleBits)); |
605 | } |
606 | Integer unchanged{IAND(MASKL(bits - size))}; |
607 | Integer middle{IAND(MASKR(middleBits)).SHIFTL(leastBits)}; |
608 | Integer least{SHIFTR(middleBits).IAND(MASKR(leastBits))}; |
609 | return unchanged.IOR(middle).IOR(least); |
610 | } |
611 | |
612 | // Double shifts, aka shifts with specific fill. |
613 | constexpr Integer SHIFTLWithFill(const Integer &fill, int count) const { |
614 | if (count <= 0) { |
615 | return *this; |
616 | } else if (count >= 2 * bits) { |
617 | return {}; |
618 | } else if (count > bits) { |
619 | return fill.SHIFTL(count - bits); |
620 | } else if (count == bits) { |
621 | return fill; |
622 | } else { |
623 | return SHIFTL(count).IOR(fill.SHIFTR(bits - count)); |
624 | } |
625 | } |
626 | |
627 | constexpr Integer SHIFTRWithFill(const Integer &fill, int count) const { |
628 | if (count <= 0) { |
629 | return *this; |
630 | } else if (count >= 2 * bits) { |
631 | return {}; |
632 | } else if (count > bits) { |
633 | return fill.SHIFTR(count - bits); |
634 | } else if (count == bits) { |
635 | return fill; |
636 | } else { |
637 | return SHIFTR(count).IOR(fill.SHIFTL(bits - count)); |
638 | } |
639 | } |
640 | |
641 | constexpr Integer DSHIFTL(const Integer &fill, int count) const { |
642 | // DSHIFTL(I,J) shifts I:J left; the second argument is the right fill. |
643 | return SHIFTLWithFill(fill, count); |
644 | } |
645 | |
646 | constexpr Integer DSHIFTR(const Integer &value, int count) const { |
647 | // DSHIFTR(I,J) shifts I:J right; the *first* argument is the left fill. |
648 | return value.SHIFTRWithFill(*this, count); |
649 | } |
650 | |
651 | // Vacated upper bits are filled with zeroes. |
652 | constexpr Integer SHIFTR(int count) const { |
653 | if (count <= 0) { |
654 | return *this; |
655 | } else { |
656 | Integer result{nullptr}; |
657 | int shiftParts{count / partBits}; |
658 | int bitShift{count - partBits * shiftParts}; |
659 | int j{0}; |
660 | if (bitShift == 0) { |
661 | for (; j + shiftParts < parts; ++j) { |
662 | result.LEPart(j) = LEPart(j + shiftParts); |
663 | } |
664 | for (; j < parts; ++j) { |
665 | result.LEPart(j) = 0; |
666 | } |
667 | } else { |
668 | for (; j + shiftParts + 1 < parts; ++j) { |
669 | result.SetLEPart(j, |
670 | (LEPart(j + shiftParts) >> bitShift) | |
671 | (LEPart(j + shiftParts + 1) << (partBits - bitShift))); |
672 | } |
673 | if (j + shiftParts + 1 == parts) { |
674 | result.LEPart(j++) = LEPart(parts - 1) >> bitShift; |
675 | } |
676 | for (; j < parts; ++j) { |
677 | result.LEPart(j) = 0; |
678 | } |
679 | } |
680 | return result; |
681 | } |
682 | } |
683 | |
684 | // Be advised, an arithmetic (sign-filling) right shift is not |
685 | // the same as a division by a power of two in all cases. |
686 | constexpr Integer SHIFTA(int count) const { |
687 | if (count <= 0) { |
688 | return *this; |
689 | } else if (IsNegative()) { |
690 | return SHIFTR(count).IOR(MASKL(count)); |
691 | } else { |
692 | return SHIFTR(count); |
693 | } |
694 | } |
695 | |
696 | // Clears a single bit. |
697 | constexpr Integer IBCLR(int pos) const { |
698 | if (pos < 0 || pos >= bits) { |
699 | return *this; |
700 | } else { |
701 | Integer result{*this}; |
702 | result.LEPart(pos / partBits) &= ~(Part{1} << (pos % partBits)); |
703 | return result; |
704 | } |
705 | } |
706 | |
707 | // Sets a single bit. |
708 | constexpr Integer IBSET(int pos) const { |
709 | if (pos < 0 || pos >= bits) { |
710 | return *this; |
711 | } else { |
712 | Integer result{*this}; |
713 | result.LEPart(pos / partBits) |= Part{1} << (pos % partBits); |
714 | return result; |
715 | } |
716 | } |
717 | |
718 | // Extracts a field. |
719 | constexpr Integer IBITS(int pos, int size) const { |
720 | return SHIFTR(pos).IAND(MASKR(size)); |
721 | } |
722 | |
723 | constexpr Integer IAND(const Integer &y) const { |
724 | Integer result{nullptr}; |
725 | for (int j{0}; j < parts; ++j) { |
726 | result.LEPart(j) = LEPart(j) & y.LEPart(j); |
727 | } |
728 | return result; |
729 | } |
730 | |
731 | constexpr Integer IOR(const Integer &y) const { |
732 | Integer result{nullptr}; |
733 | for (int j{0}; j < parts; ++j) { |
734 | result.LEPart(j) = LEPart(j) | y.LEPart(j); |
735 | } |
736 | return result; |
737 | } |
738 | |
739 | constexpr Integer IEOR(const Integer &y) const { |
740 | Integer result{nullptr}; |
741 | for (int j{0}; j < parts; ++j) { |
742 | result.LEPart(j) = LEPart(j) ^ y.LEPart(j); |
743 | } |
744 | return result; |
745 | } |
746 | |
747 | constexpr Integer MERGE_BITS(const Integer &y, const Integer &mask) const { |
748 | return IAND(mask).IOR(y.IAND(mask.NOT())); |
749 | } |
750 | |
751 | constexpr Integer MAX(const Integer &y) const { |
752 | if (CompareSigned(y) == Ordering::Less) { |
753 | return y; |
754 | } else { |
755 | return *this; |
756 | } |
757 | } |
758 | |
759 | constexpr Integer MIN(const Integer &y) const { |
760 | if (CompareSigned(y) == Ordering::Less) { |
761 | return *this; |
762 | } else { |
763 | return y; |
764 | } |
765 | } |
766 | |
767 | // Unsigned addition with carry. |
768 | constexpr ValueWithCarry AddUnsigned( |
769 | const Integer &y, bool carryIn = false) const { |
770 | Integer sum{nullptr}; |
771 | BigPart carry{carryIn}; |
772 | for (int j{0}; j + 1 < parts; ++j) { |
773 | carry += LEPart(j); |
774 | carry += y.LEPart(j); |
775 | sum.SetLEPart(j, carry); |
776 | carry >>= partBits; |
777 | } |
778 | carry += LEPart(parts - 1); |
779 | carry += y.LEPart(parts - 1); |
780 | sum.SetLEPart(parts - 1, carry); |
781 | return {sum, carry > topPartMask}; |
782 | } |
783 | |
784 | constexpr ValueWithOverflow AddSigned(const Integer &y) const { |
785 | bool isNegative{IsNegative()}; |
786 | bool sameSign{isNegative == y.IsNegative()}; |
787 | ValueWithCarry sum{AddUnsigned(y)}; |
788 | bool overflow{sameSign && sum.value.IsNegative() != isNegative}; |
789 | return {sum.value, overflow}; |
790 | } |
791 | |
792 | constexpr ValueWithOverflow SubtractSigned(const Integer &y) const { |
793 | bool isNegative{IsNegative()}; |
794 | bool sameSign{isNegative == y.IsNegative()}; |
795 | ValueWithCarry diff{AddUnsigned(y.Negate().value)}; |
796 | bool overflow{!sameSign && diff.value.IsNegative() != isNegative}; |
797 | return {diff.value, overflow}; |
798 | } |
799 | |
800 | // DIM(X,Y)=MAX(X-Y, 0) |
801 | constexpr ValueWithOverflow DIM(const Integer &y) const { |
802 | if (CompareSigned(y) != Ordering::Greater) { |
803 | return {}; |
804 | } else { |
805 | return SubtractSigned(y); |
806 | } |
807 | } |
808 | |
809 | constexpr ValueWithOverflow SIGN(bool toNegative) const { |
810 | if (toNegative == IsNegative()) { |
811 | return {*this, false}; |
812 | } else if (toNegative) { |
813 | return Negate(); |
814 | } else { |
815 | return ABS(); |
816 | } |
817 | } |
818 | |
819 | constexpr ValueWithOverflow SIGN(const Integer &sign) const { |
820 | return SIGN(sign.IsNegative()); |
821 | } |
822 | |
823 | constexpr Product MultiplyUnsigned(const Integer &y) const { |
824 | Part product[2 * parts]{}; // little-endian full product |
825 | for (int j{0}; j < parts; ++j) { |
826 | if (Part xpart{LEPart(j)}) { |
827 | for (int k{0}; k < parts; ++k) { |
828 | if (Part ypart{y.LEPart(k)}) { |
829 | BigPart xy{xpart}; |
830 | xy *= ypart; |
831 | #if defined __GNUC__ && __GNUC__ < 8 |
832 | // && to < (2 * parts) was added to avoid GCC < 8 build failure on |
833 | // -Werror=array-bounds. This can be removed if -Werror is disable. |
834 | for (int to{j + k}; xy != 0 && to < (2 * parts); ++to) { |
835 | #else |
836 | for (int to{j + k}; xy != 0; ++to) { |
837 | #endif |
838 | xy += product[to]; |
839 | product[to] = xy & partMask; |
840 | xy >>= partBits; |
841 | } |
842 | } |
843 | } |
844 | } |
845 | } |
846 | Integer upper{nullptr}, lower{nullptr}; |
847 | for (int j{0}; j < parts; ++j) { |
848 | lower.LEPart(j) = product[j]; |
849 | upper.LEPart(j) = product[j + parts]; |
850 | } |
851 | if constexpr (topPartBits < partBits) { |
852 | upper = upper.SHIFTL(partBits - topPartBits); |
853 | upper.LEPart(0) |= lower.LEPart(parts - 1) >> topPartBits; |
854 | lower.LEPart(parts - 1) &= topPartMask; |
855 | } |
856 | return {upper, lower}; |
857 | } |
858 | |
859 | constexpr Product MultiplySigned(const Integer &y) const { |
860 | bool yIsNegative{y.IsNegative()}; |
861 | Integer absy{y}; |
862 | if (yIsNegative) { |
863 | absy = y.Negate().value; |
864 | } |
865 | bool isNegative{IsNegative()}; |
866 | Integer absx{*this}; |
867 | if (isNegative) { |
868 | absx = Negate().value; |
869 | } |
870 | Product product{absx.MultiplyUnsigned(absy)}; |
871 | if (isNegative != yIsNegative) { |
872 | product.lower = product.lower.NOT(); |
873 | product.upper = product.upper.NOT(); |
874 | Integer one{1}; |
875 | auto incremented{product.lower.AddUnsigned(one)}; |
876 | product.lower = incremented.value; |
877 | if (incremented.carry) { |
878 | product.upper = product.upper.AddUnsigned(one).value; |
879 | } |
880 | } |
881 | return product; |
882 | } |
883 | |
884 | constexpr QuotientWithRemainder DivideUnsigned(const Integer &divisor) const { |
885 | if (divisor.IsZero()) { |
886 | return {MASKR(bits), Integer{}, true, false}; // overflow to max value |
887 | } |
888 | int bitsDone{LEADZ()}; |
889 | Integer top{SHIFTL(bitsDone)}; |
890 | Integer quotient, remainder; |
891 | for (; bitsDone < bits; ++bitsDone) { |
892 | auto doubledTop{top.AddUnsigned(top)}; |
893 | top = doubledTop.value; |
894 | remainder = remainder.AddUnsigned(remainder, doubledTop.carry).value; |
895 | bool nextBit{remainder.CompareUnsigned(divisor) != Ordering::Less}; |
896 | quotient = quotient.AddUnsigned(quotient, nextBit).value; |
897 | if (nextBit) { |
898 | remainder = remainder.SubtractSigned(divisor).value; |
899 | } |
900 | } |
901 | return {quotient, remainder, false, false}; |
902 | } |
903 | |
904 | // A nonzero remainder has the sign of the dividend, i.e., it computes |
905 | // the MOD intrinsic (X-INT(X/Y)*Y), not MODULO (which is below). |
906 | // 8/5 = 1r3; -8/5 = -1r-3; 8/-5 = -1r3; -8/-5 = 1r-3 |
907 | constexpr QuotientWithRemainder DivideSigned(Integer divisor) const { |
908 | bool dividendIsNegative{IsNegative()}; |
909 | bool negateQuotient{dividendIsNegative}; |
910 | Ordering divisorOrdering{divisor.CompareToZeroSigned()}; |
911 | if (divisorOrdering == Ordering::Less) { |
912 | negateQuotient = !negateQuotient; |
913 | auto negated{divisor.Negate()}; |
914 | if (negated.overflow) { |
915 | // divisor was (and is) the most negative number |
916 | if (CompareUnsigned(divisor) == Ordering::Equal) { |
917 | return {MASKR(1), Integer{}, false, bits <= 1}; |
918 | } else { |
919 | return {Integer{}, *this, false, false}; |
920 | } |
921 | } |
922 | divisor = negated.value; |
923 | } else if (divisorOrdering == Ordering::Equal) { |
924 | // division by zero |
925 | if (dividendIsNegative) { |
926 | return {MASKL(1), Integer{}, true, false}; |
927 | } else { |
928 | return {MASKR(bits - 1), Integer{}, true, false}; |
929 | } |
930 | } |
931 | Integer dividend{*this}; |
932 | if (dividendIsNegative) { |
933 | auto negated{Negate()}; |
934 | if (negated.overflow) { |
935 | // Dividend was (and remains) the most negative number. |
936 | // See whether the original divisor was -1 (if so, it's 1 now). |
937 | if (divisorOrdering == Ordering::Less && |
938 | divisor.CompareUnsigned(Integer{1}) == Ordering::Equal) { |
939 | // most negative number / -1 is the sole overflow case |
940 | return {*this, Integer{}, false, true}; |
941 | } |
942 | } else { |
943 | dividend = negated.value; |
944 | } |
945 | } |
946 | // Overflow is not possible, and both the dividend and divisor |
947 | // are now positive. |
948 | QuotientWithRemainder result{dividend.DivideUnsigned(divisor)}; |
949 | if (negateQuotient) { |
950 | result.quotient = result.quotient.Negate().value; |
951 | } |
952 | if (dividendIsNegative) { |
953 | result.remainder = result.remainder.Negate().value; |
954 | } |
955 | return result; |
956 | } |
957 | |
958 | // Result has the sign of the divisor argument. |
959 | // 8 mod 5 = 3; -8 mod 5 = 2; 8 mod -5 = -2; -8 mod -5 = -3 |
960 | constexpr ValueWithOverflow MODULO(const Integer &divisor) const { |
961 | bool negativeDivisor{divisor.IsNegative()}; |
962 | bool distinctSigns{IsNegative() != negativeDivisor}; |
963 | QuotientWithRemainder divided{DivideSigned(divisor)}; |
964 | if (distinctSigns && !divided.remainder.IsZero()) { |
965 | return {divided.remainder.AddUnsigned(divisor).value, divided.overflow}; |
966 | } else { |
967 | return {divided.remainder, divided.overflow}; |
968 | } |
969 | } |
970 | |
971 | constexpr PowerWithErrors Power(const Integer &exponent) const { |
972 | PowerWithErrors result{1, false, false, false}; |
973 | if (exponent.IsZero()) { |
974 | // x**0 -> 1, including the case 0**0, which is not defined specifically |
975 | // in F'18 afaict; however, other Fortrans tested all produce 1, not 0, |
976 | // apart from nagfor, which stops with an error at runtime. |
977 | // Ada, APL, C's pow(), Haskell, Julia, MATLAB, and R all produce 1 too. |
978 | // F'77 explicitly states that 0**0 is mathematically undefined and |
979 | // therefore prohibited. |
980 | result.zeroToZero = IsZero(); |
981 | } else if (exponent.IsNegative()) { |
982 | if (IsZero()) { |
983 | result.divisionByZero = true; |
984 | result.power = MASKR(bits - 1); |
985 | } else if (CompareSigned(Integer{1}) == Ordering::Equal) { |
986 | result.power = *this; // 1**x -> 1 |
987 | } else if (CompareSigned(Integer{-1}) == Ordering::Equal) { |
988 | if (exponent.BTEST(0)) { |
989 | result.power = *this; // (-1)**x -> -1 if x is odd |
990 | } |
991 | } else { |
992 | result.power.Clear(); // j**k -> 0 if |j| > 1 and k < 0 |
993 | } |
994 | } else { |
995 | Integer shifted{*this}; |
996 | Integer pow{exponent}; |
997 | int nbits{bits - pow.LEADZ()}; |
998 | for (int j{0}; j < nbits; ++j) { |
999 | if (pow.BTEST(j)) { |
1000 | Product product{result.power.MultiplySigned(shifted)}; |
1001 | result.power = product.lower; |
1002 | result.overflow |= product.SignedMultiplicationOverflowed(); |
1003 | } |
1004 | if (j + 1 < nbits) { |
1005 | Product squared{shifted.MultiplySigned(shifted)}; |
1006 | result.overflow |= squared.SignedMultiplicationOverflowed(); |
1007 | shifted = squared.lower; |
1008 | } |
1009 | } |
1010 | } |
1011 | return result; |
1012 | } |
1013 | |
1014 | private: |
1015 | // A private constructor, selected by the use of nullptr, |
1016 | // that is used by member functions when it would be a waste |
1017 | // of time to initialize parts_[]. |
1018 | constexpr Integer(std::nullptr_t) {} |
1019 | |
1020 | // Accesses parts in little-endian order. |
1021 | constexpr const Part &LEPart(int part) const { |
1022 | if constexpr (littleEndian) { |
1023 | return part_[part]; |
1024 | } else { |
1025 | return part_[parts - 1 - part]; |
1026 | } |
1027 | } |
1028 | |
1029 | constexpr Part &LEPart(int part) { |
1030 | if constexpr (littleEndian) { |
1031 | return part_[part]; |
1032 | } else { |
1033 | return part_[parts - 1 - part]; |
1034 | } |
1035 | } |
1036 | |
1037 | constexpr void SetLEPart(int part, Part x) { |
1038 | LEPart(part) = x & PartMask(part); |
1039 | } |
1040 | |
1041 | static constexpr Part PartMask(int part) { |
1042 | return part == parts - 1 ? topPartMask : partMask; |
1043 | } |
1044 | |
1045 | constexpr void Clear() { |
1046 | for (int j{0}; j < parts; ++j) { |
1047 | part_[j] = 0; |
1048 | } |
1049 | } |
1050 | |
1051 | Part part_[partsWithAlignment]{}; |
1052 | }; |
1053 | |
1054 | extern template class Integer<8>; |
1055 | extern template class Integer<16>; |
1056 | extern template class Integer<32>; |
1057 | extern template class Integer<64>; |
1058 | using X87IntegerContainer = |
1059 | Integer<80, true, 16, std::uint16_t, std::uint32_t, 128>; |
1060 | extern template class Integer<80, true, 16, std::uint16_t, std::uint32_t, 128>; |
1061 | extern template class Integer<128>; |
1062 | } // namespace Fortran::evaluate::value |
1063 | #endif // FORTRAN_EVALUATE_INTEGER_H_ |
1064 |
Warning: This file is not a C or C++ file. It does not have highlighting.