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
34namespace 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.
52template <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>
59class Integer {
60public:
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
72private:
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
88public:
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
1014private:
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
1054extern template class Integer<8>;
1055extern template class Integer<16>;
1056extern template class Integer<32>;
1057extern template class Integer<64>;
1058using X87IntegerContainer =
1059 Integer<80, true, 16, std::uint16_t, std::uint32_t, 128>;
1060extern template class Integer<80, true, 16, std::uint16_t, std::uint32_t, 128>;
1061extern 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.

source code of flang/include/flang/Evaluate/integer.h