flang/Evaluate/integer.h

//===-- include/flang/Evaluate/integer.h ------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef FORTRAN_EVALUATE_INTEGER_H_
#define FORTRAN_EVALUATE_INTEGER_H_

// Emulates binary integers of an arbitrary (but fixed) bit size for use
// when the host C++ environment does not support that size or when the
// full suite of Fortran's integer intrinsic scalar functions are needed.
// The data model is typeless, so signed* and unsigned operations
// are distinguished from each other with distinct member function interfaces.
// (*"Signed" here means two's-complement, just to be clear.  Ones'-complement
// and signed-magnitude encodings appear to be extinct in 2018.)

#include "flang/Common/bit-population-count.h"
#include "flang/Common/leading-zero-bit-count.h"
#include "flang/Evaluate/common.h"
#include <cinttypes>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <string>
#include <type_traits>

// Some environments, viz. clang on Darwin, allow the macro HUGE
// to leak out of <math.h> even when it is never directly included.
#undef HUGE

namespace Fortran::evaluate::value {

// Implements an integer as an assembly of smaller host integer parts
// that constitute the digits of a large-radix fixed-point number.
// For best performance, the type of these parts should be half of the
// size of the largest efficient integer supported by the host processor.
// These parts are stored in either little- or big-endian order, which can
// match that of the host's endianness or not; but if the ordering matches
// that of the host, raw host data can be overlaid with a properly configured
// instance of this class and used in situ.
// To facilitate exhaustive testing of what would otherwise be more rare
// edge cases, this class template may be configured to use other part
// types &/or partial fields in the parts.  The radix (i.e., the number
// of possible values in a part), however, must be a power of two; this
// template class is not generalized to enable, say, decimal arithmetic.
// Member functions that correspond to Fortran intrinsic functions are
// named accordingly in ALL CAPS so that they can be referenced easily in
// the language standard.
template <int BITS, bool IS_LITTLE_ENDIAN = isHostLittleEndian,
    int PARTBITS = BITS <= 32 ? BITS : 32,
    typename PART = HostUnsignedInt<PARTBITS>,
    typename BIGPART = HostUnsignedInt<PARTBITS * 2>>
class Integer {
public:
  static constexpr int bits{BITS};
  static constexpr int partBits{PARTBITS};
  using Part = PART;
  using BigPart = BIGPART;
  static_assert(std::is_integral_v<Part>);
  static_assert(std::is_unsigned_v<Part>);
  static_assert(std::is_integral_v<BigPart>);
  static_assert(std::is_unsigned_v<BigPart>);
  static_assert(CHAR_BIT * sizeof(BigPart) >= 2 * partBits);
  static constexpr bool littleEndian{IS_LITTLE_ENDIAN};

private:
  static constexpr int maxPartBits{CHAR_BIT * sizeof(Part)};
  static_assert(partBits > 0 && partBits <= maxPartBits);
  static constexpr int extraPartBits{maxPartBits - partBits};
  static constexpr int parts{(bits + partBits - 1) / partBits};
  static_assert(parts >= 1);
  static constexpr int extraTopPartBits{
      extraPartBits + (parts * partBits) - bits};
  static constexpr int topPartBits{maxPartBits - extraTopPartBits};
  static_assert(topPartBits > 0 && topPartBits <= partBits);
  static_assert((parts - 1) * partBits + topPartBits == bits);
  static constexpr Part partMask{static_cast<Part>(~0) >> extraPartBits};
  static constexpr Part topPartMask{static_cast<Part>(~0) >> extraTopPartBits};

public:
  // Some types used for member function results
  struct ValueWithOverflow {
    Integer value;
    bool overflow;
  };

  struct ValueWithCarry {
    Integer value;
    bool carry;
  };

  struct Product {
    bool SignedMultiplicationOverflowed() const {
      return lower.IsNegative() ? (upper.POPCNT() != bits) : !upper.IsZero();
    }
    Integer upper, lower;
  };

  struct QuotientWithRemainder {
    Integer quotient, remainder;
    bool divisionByZero, overflow;
  };

  struct PowerWithErrors {
    Integer power;
    bool divisionByZero{false}, overflow{false}, zeroToZero{false};
  };

  // Constructors and value-generating static functions
  constexpr Integer() { Clear(); } // default constructor: zero
  constexpr Integer(const Integer &) = default;
  constexpr Integer(Integer &&) = default;

  // C++'s integral types can all be converted to Integer
  // with silent truncation.
  template <typename INT, typename = std::enable_if_t<std::is_integral_v<INT>>>
  constexpr Integer(INT n) {
    constexpr int nBits = CHAR_BIT * sizeof n;
    if constexpr (nBits < partBits) {
      if constexpr (std::is_unsigned_v<INT>) {
        // Zero-extend an unsigned smaller value.
        SetLEPart(0, n);
        for (int j{1}; j < parts; ++j) {
          SetLEPart(j, 0);
        }
      } else {
        // n has a signed type smaller than the usable
        // bits in a Part.
        // Avoid conversions that change both size and sign.
        using SignedPart = std::make_signed_t<Part>;
        Part p = static_cast<SignedPart>(n);
        SetLEPart(0, p);
        if constexpr (parts > 1) {
          Part signExtension = static_cast<SignedPart>(-(n < 0));
          for (int j{1}; j < parts; ++j) {
            SetLEPart(j, signExtension);
          }
        }
      }
    } else {
      // n has some integral type no smaller than the usable
      // bits in a Part.
      // Ensure that all shifts are smaller than a whole word.
      if constexpr (std::is_unsigned_v<INT>) {
        for (int j{0}; j < parts; ++j) {
          SetLEPart(j, static_cast<Part>(n));
          if constexpr (nBits > partBits) {
            n >>= partBits;
          } else {
            n = 0;
          }
        }
      } else {
        INT signExtension{-(n < 0)};
        static_assert(nBits >= partBits);
        if constexpr (nBits > partBits) {
          signExtension <<= nBits - partBits;
          for (int j{0}; j < parts; ++j) {
            SetLEPart(j, static_cast<Part>(n));
            n >>= partBits;
            n |= signExtension;
          }
        } else {
          SetLEPart(0, static_cast<Part>(n));
          for (int j{1}; j < parts; ++j) {
            SetLEPart(j, static_cast<Part>(signExtension));
          }
        }
      }
    }
  }

  constexpr Integer &operator=(const Integer &) = default;

  constexpr bool operator<(const Integer &that) const {
    return CompareSigned(that) == Ordering::Less;
  }
  constexpr bool operator<=(const Integer &that) const {
    return CompareSigned(that) != Ordering::Greater;
  }
  constexpr bool operator==(const Integer &that) const {
    return CompareSigned(that) == Ordering::Equal;
  }
  constexpr bool operator!=(const Integer &that) const {
    return !(*this == that);
  }
  constexpr bool operator>=(const Integer &that) const {
    return CompareSigned(that) != Ordering::Less;
  }
  constexpr bool operator>(const Integer &that) const {
    return CompareSigned(that) == Ordering::Greater;
  }

  // Left-justified mask (e.g., MASKL(1) has only its sign bit set)
  static constexpr Integer MASKL(int places) {
    if (places <= 0) {
      return {};
    } else if (places >= bits) {
      return MASKR(bits);
    } else {
      return MASKR(bits - places).NOT();
    }
  }

  // Right-justified mask (e.g., MASKR(1) == 1, MASKR(2) == 3, &c.)
  static constexpr Integer MASKR(int places) {
    Integer result{nullptr};
    int j{0};
    for (; j + 1 < parts && places >= partBits; ++j, places -= partBits) {
      result.LEPart(j) = partMask;
    }
    if (places > 0) {
      if (j + 1 < parts) {
        result.LEPart(j++) = partMask >> (partBits - places);
      } else if (j + 1 == parts) {
        if (places >= topPartBits) {
          result.LEPart(j++) = topPartMask;
        } else {
          result.LEPart(j++) = topPartMask >> (topPartBits - places);
        }
      }
    }
    for (; j < parts; ++j) {
      result.LEPart(j) = 0;
    }
    return result;
  }

  static constexpr ValueWithOverflow Read(
      const char *&pp, std::uint64_t base = 10, bool isSigned = false) {
    Integer result;
    bool overflow{false};
    const char *p{pp};
    while (*p == ' ' || *p == '\t') {
      ++p;
    }
    bool negate{*p == '-'};
    if (negate || *p == '+') {
      while (*++p == ' ' || *p == '\t') {
      }
    }
    Integer radix{base};
    // This code makes assumptions about local contiguity in regions of the
    // character set and only works up to base 36.  These assumptions hold
    // for all current combinations of surviving character sets (ASCII, UTF-8,
    // EBCDIC) and the bases used in Fortran source and formatted I/O
    // (viz., 2, 8, 10, & 16).  But: management thought that a disclaimer
    // might be needed here to warn future users of this code about these
    // assumptions, so here you go, future programmer in some postapocalyptic
    // hellscape, and best of luck with the inexorable killer robots.
    for (; std::uint64_t digit = *p; ++p) {
      if (digit >= '0' && digit <= '9' && digit < '0' + base) {
        digit -= '0';
      } else if (base > 10 && digit >= 'A' && digit < 'A' + base - 10) {
        digit -= 'A' - 10;
      } else if (base > 10 && digit >= 'a' && digit < 'a' + base - 10) {
        digit -= 'a' - 10;
      } else {
        break;
      }
      Product shifted{result.MultiplyUnsigned(radix)};
      overflow |= !shifted.upper.IsZero();
      ValueWithCarry next{shifted.lower.AddUnsigned(Integer{digit})};
      overflow |= next.carry;
      result = next.value;
    }
    pp = p;
    if (negate) {
      result = result.Negate().value;
      overflow |= isSigned && !result.IsNegative() && !result.IsZero();
    } else {
      overflow |= isSigned && result.IsNegative();
    }
    return {result, overflow};
  }

  template <typename FROM>
  static constexpr ValueWithOverflow ConvertUnsigned(const FROM &that) {
    std::uint64_t field{that.ToUInt64()};
    ValueWithOverflow result{field, false};
    if constexpr (bits < 64) {
      result.overflow = (field >> bits) != 0;
    }
    for (int j{64}; j < that.bits && !result.overflow; j += 64) {
      field = that.SHIFTR(j).ToUInt64();
      if (bits <= j) {
        result.overflow = field != 0;
      } else {
        result.value = result.value.IOR(Integer{field}.SHIFTL(j));
        if (bits < j + 64) {
          result.overflow = (field >> (bits - j)) != 0;
        }
      }
    }
    return result;
  }

  template <typename FROM>
  static constexpr ValueWithOverflow ConvertSigned(const FROM &that) {
    ValueWithOverflow result{ConvertUnsigned(that)};
    if constexpr (bits > FROM::bits) {
      if (that.IsNegative()) {
        result.value = result.value.IOR(MASKL(bits - FROM::bits));
      }
      result.overflow = false;
    } else if constexpr (bits < FROM::bits) {
      auto back{FROM::template ConvertSigned(result.value)};
      result.overflow = back.value.CompareUnsigned(that) != Ordering::Equal;
    }
    return result;
  }

  std::string UnsignedDecimal() const {
    if constexpr (bits < 4) {
      char digit = '0' + ToUInt64();
      return {digit};
    } else if (IsZero()) {
      return {'0'};
    } else {
      QuotientWithRemainder qr{DivideUnsigned(10)};
      char digit = '0' + qr.remainder.ToUInt64();
      if (qr.quotient.IsZero()) {
        return {digit};
      } else {
        return qr.quotient.UnsignedDecimal() + digit;
      }
    }
  }

  std::string SignedDecimal() const {
    if (IsNegative()) {
      return std::string{'-'} + Negate().value.UnsignedDecimal();
    } else {
      return UnsignedDecimal();
    }
  }

  // Omits a leading "0x".
  std::string Hexadecimal() const {
    std::string result;
    int digits{(bits + 3) >> 2};
    for (int j{0}; j < digits; ++j) {
      int pos{(digits - 1 - j) * 4};
      char nybble = IBITS(pos, 4).ToUInt64();
      if (nybble != 0 || !result.empty() || j + 1 == digits) {
        char digit = '0' + nybble;
        if (digit > '9') {
          digit += 'a' - ('9' + 1);
        }
        result += digit;
      }
    }
    return result;
  }

  static constexpr int DIGITS{bits - 1}; // don't count the sign bit
  static constexpr Integer HUGE() { return MASKR(bits - 1); }
  static constexpr int RANGE{// in the sense of SELECTED_INT_KIND
      // This magic value is LOG10(2.)*1E12.
      static_cast<int>(((bits - 1) * 301029995664) / 1000000000000)};

  constexpr bool IsZero() const {
    for (int j{0}; j < parts; ++j) {
      if (part_[j] != 0) {
        return false;
      }
    }
    return true;
  }

  constexpr bool IsNegative() const {
    return (LEPart(parts - 1) >> (topPartBits - 1)) & 1;
  }

  constexpr Ordering CompareToZeroSigned() const {
    if (IsNegative()) {
      return Ordering::Less;
    } else if (IsZero()) {
      return Ordering::Equal;
    } else {
      return Ordering::Greater;
    }
  }

  // Count the number of contiguous most-significant bit positions
  // that are clear.
  constexpr int LEADZ() const {
    if (LEPart(parts - 1) != 0) {
      int lzbc{common::LeadingZeroBitCount(LEPart(parts - 1))};
      return lzbc - extraTopPartBits;
    }
    int upperZeroes{topPartBits};
    for (int j{1}; j < parts; ++j) {
      if (Part p{LEPart(parts - 1 - j)}) {
        int lzbc{common::LeadingZeroBitCount(p)};
        return upperZeroes + lzbc - extraPartBits;
      }
      upperZeroes += partBits;
    }
    return bits;
  }

  // Count the number of bit positions that are set.
  constexpr int POPCNT() const {
    int count{0};
    for (int j{0}; j < parts; ++j) {
      count += common::BitPopulationCount(part_[j]);
    }
    return count;
  }

  // True when POPCNT is odd.
  constexpr bool POPPAR() const { return POPCNT() & 1; }

  constexpr int TRAILZ() const {
    auto minus1{AddUnsigned(MASKR(bits))}; // { x-1, carry = x > 0 }
    if (!minus1.carry) {
      return bits; // was zero
    } else {
      // x ^ (x-1) has all bits set at and below original least-order set bit.
      return IEOR(minus1.value).POPCNT() - 1;
    }
  }

  constexpr bool BTEST(int pos) const {
    if (pos < 0 || pos >= bits) {
      return false;
    } else {
      return (LEPart(pos / partBits) >> (pos % partBits)) & 1;
    }
  }

  constexpr Ordering CompareUnsigned(const Integer &y) const {
    for (int j{parts}; j-- > 0;) {
      if (LEPart(j) > y.LEPart(j)) {
        return Ordering::Greater;
      }
      if (LEPart(j) < y.LEPart(j)) {
        return Ordering::Less;
      }
    }
    return Ordering::Equal;
  }

  constexpr bool BGE(const Integer &y) const {
    return CompareUnsigned(y) != Ordering::Less;
  }
  constexpr bool BGT(const Integer &y) const {
    return CompareUnsigned(y) == Ordering::Greater;
  }
  constexpr bool BLE(const Integer &y) const { return !BGT(y); }
  constexpr bool BLT(const Integer &y) const { return !BGE(y); }

  constexpr Ordering CompareSigned(const Integer &y) const {
    bool isNegative{IsNegative()};
    if (isNegative != y.IsNegative()) {
      return isNegative ? Ordering::Less : Ordering::Greater;
    }
    return CompareUnsigned(y);
  }

  template <typename UINT = std::uint64_t> constexpr UINT ToUInt() const {
    UINT n{LEPart(0)};
    std::size_t filled{partBits};
    constexpr std::size_t maxBits{CHAR_BIT * sizeof n};
    for (int j{1}; filled < maxBits && j < parts; ++j, filled += partBits) {
      n |= UINT{LEPart(j)} << filled;
    }
    return n;
  }

  template <typename SINT = std::int64_t, typename UINT = std::uint64_t>
  constexpr SINT ToSInt() const {
    SINT n = ToUInt<UINT>();
    constexpr std::size_t maxBits{CHAR_BIT * sizeof n};
    if constexpr (bits < maxBits) {
      n |= -(n >> (bits - 1)) << bits;
    }
    return n;
  }

  constexpr std::uint64_t ToUInt64() const { return ToUInt<std::uint64_t>(); }

  constexpr std::int64_t ToInt64() const {
    return ToSInt<std::int64_t, std::uint64_t>();
  }

  // Ones'-complement (i.e., C's ~)
  constexpr Integer NOT() const {
    Integer result{nullptr};
    for (int j{0}; j < parts; ++j) {
      result.SetLEPart(j, ~LEPart(j));
    }
    return result;
  }

  // Two's-complement negation (-x = ~x + 1).
  // An overflow flag accompanies the result, and will be true when the
  // operand is the most negative signed number (MASKL(1)).
  constexpr ValueWithOverflow Negate() const {
    Integer result{nullptr};
    Part carry{1};
    for (int j{0}; j + 1 < parts; ++j) {
      Part newCarry{LEPart(j) == 0 && carry};
      result.SetLEPart(j, ~LEPart(j) + carry);
      carry = newCarry;
    }
    Part top{LEPart(parts - 1)};
    result.SetLEPart(parts - 1, ~top + carry);
    bool overflow{top != 0 && result.LEPart(parts - 1) == top};
    return {result, overflow};
  }

  constexpr ValueWithOverflow ABS() const {
    if (IsNegative()) {
      return Negate();
    } else {
      return {*this, false};
    }
  }

  // Shifts the operand left when the count is positive, right when negative.
  // Vacated bit positions are filled with zeroes.
  constexpr Integer ISHFT(int count) const {
    if (count < 0) {
      return SHIFTR(-count);
    } else {
      return SHIFTL(count);
    }
  }

  // Left shift with zero fill.
  constexpr Integer SHIFTL(int count) const {
    if (count <= 0) {
      return *this;
    } else {
      Integer result{nullptr};
      int shiftParts{count / partBits};
      int bitShift{count - partBits * shiftParts};
      int j{parts - 1};
      if (bitShift == 0) {
        for (; j >= shiftParts; --j) {
          result.SetLEPart(j, LEPart(j - shiftParts));
        }
        for (; j >= 0; --j) {
          result.LEPart(j) = 0;
        }
      } else {
        for (; j > shiftParts; --j) {
          result.SetLEPart(j,
              ((LEPart(j - shiftParts) << bitShift) |
                  (LEPart(j - shiftParts - 1) >> (partBits - bitShift))));
        }
        if (j == shiftParts) {
          result.SetLEPart(j, LEPart(0) << bitShift);
          --j;
        }
        for (; j >= 0; --j) {
          result.LEPart(j) = 0;
        }
      }
      return result;
    }
  }

  // Circular shift of a field of least-significant bits.  The least-order
  // "size" bits are shifted circularly in place by "count" positions;
  // the shift is leftward if count is nonnegative, rightward otherwise.
  // Higher-order bits are unchanged.
  constexpr Integer ISHFTC(int count, int size = bits) const {
    if (count == 0 || size <= 0) {
      return *this;
    }
    if (size > bits) {
      size = bits;
    }
    count %= size;
    if (count == 0) {
      return *this;
    }
    int middleBits{size - count}, leastBits{count};
    if (count < 0) {
      middleBits = -count;
      leastBits = size + count;
    }
    if (size == bits) {
      return SHIFTL(leastBits).IOR(SHIFTR(middleBits));
    }
    Integer unchanged{IAND(MASKL(bits - size))};
    Integer middle{IAND(MASKR(middleBits)).SHIFTL(leastBits)};
    Integer least{SHIFTR(middleBits).IAND(MASKR(leastBits))};
    return unchanged.IOR(middle).IOR(least);
  }

  // Double shifts, aka shifts with specific fill.
  constexpr Integer SHIFTLWithFill(const Integer &fill, int count) const {
    if (count <= 0) {
      return *this;
    } else if (count >= 2 * bits) {
      return {};
    } else if (count > bits) {
      return fill.SHIFTL(count - bits);
    } else if (count == bits) {
      return fill;
    } else {
      return SHIFTL(count).IOR(fill.SHIFTR(bits - count));
    }
  }

  constexpr Integer SHIFTRWithFill(const Integer &fill, int count) const {
    if (count <= 0) {
      return *this;
    } else if (count >= 2 * bits) {
      return {};
    } else if (count > bits) {
      return fill.SHIFTR(count - bits);
    } else if (count == bits) {
      return fill;
    } else {
      return SHIFTR(count).IOR(fill.SHIFTL(bits - count));
    }
  }

  constexpr Integer DSHIFTL(const Integer &fill, int count) const {
    // DSHIFTL(I,J) shifts I:J left; the second argument is the right fill.
    return SHIFTLWithFill(fill, count);
  }

  constexpr Integer DSHIFTR(const Integer &value, int count) const {
    // DSHIFTR(I,J) shifts I:J right; the *first* argument is the left fill.
    return value.SHIFTRWithFill(*this, count);
  }

  // Vacated upper bits are filled with zeroes.
  constexpr Integer SHIFTR(int count) const {
    if (count <= 0) {
      return *this;
    } else {
      Integer result{nullptr};
      int shiftParts{count / partBits};
      int bitShift{count - partBits * shiftParts};
      int j{0};
      if (bitShift == 0) {
        for (; j + shiftParts < parts; ++j) {
          result.LEPart(j) = LEPart(j + shiftParts);
        }
        for (; j < parts; ++j) {
          result.LEPart(j) = 0;
        }
      } else {
        for (; j + shiftParts + 1 < parts; ++j) {
          result.SetLEPart(j,
              (LEPart(j + shiftParts) >> bitShift) |
                  (LEPart(j + shiftParts + 1) << (partBits - bitShift)));
        }
        if (j + shiftParts + 1 == parts) {
          result.LEPart(j++) = LEPart(parts - 1) >> bitShift;
        }
        for (; j < parts; ++j) {
          result.LEPart(j) = 0;
        }
      }
      return result;
    }
  }

  // Be advised, an arithmetic (sign-filling) right shift is not
  // the same as a division by a power of two in all cases.
  constexpr Integer SHIFTA(int count) const {
    if (count <= 0) {
      return *this;
    } else if (IsNegative()) {
      return SHIFTR(count).IOR(MASKL(count));
    } else {
      return SHIFTR(count);
    }
  }

  // Clears a single bit.
  constexpr Integer IBCLR(int pos) const {
    if (pos < 0 || pos >= bits) {
      return *this;
    } else {
      Integer result{*this};
      result.LEPart(pos / partBits) &= ~(Part{1} << (pos % partBits));
      return result;
    }
  }

  // Sets a single bit.
  constexpr Integer IBSET(int pos) const {
    if (pos < 0 || pos >= bits) {
      return *this;
    } else {
      Integer result{*this};
      result.LEPart(pos / partBits) |= Part{1} << (pos % partBits);
      return result;
    }
  }

  // Extracts a field.
  constexpr Integer IBITS(int pos, int size) const {
    return SHIFTR(pos).IAND(MASKR(size));
  }

  constexpr Integer IAND(const Integer &y) const {
    Integer result{nullptr};
    for (int j{0}; j < parts; ++j) {
      result.LEPart(j) = LEPart(j) & y.LEPart(j);
    }
    return result;
  }

  constexpr Integer IOR(const Integer &y) const {
    Integer result{nullptr};
    for (int j{0}; j < parts; ++j) {
      result.LEPart(j) = LEPart(j) | y.LEPart(j);
    }
    return result;
  }

  constexpr Integer IEOR(const Integer &y) const {
    Integer result{nullptr};
    for (int j{0}; j < parts; ++j) {
      result.LEPart(j) = LEPart(j) ^ y.LEPart(j);
    }
    return result;
  }

  constexpr Integer MERGE_BITS(const Integer &y, const Integer &mask) const {
    return IAND(mask).IOR(y.IAND(mask.NOT()));
  }

  constexpr Integer MAX(const Integer &y) const {
    if (CompareSigned(y) == Ordering::Less) {
      return y;
    } else {
      return *this;
    }
  }

  constexpr Integer MIN(const Integer &y) const {
    if (CompareSigned(y) == Ordering::Less) {
      return *this;
    } else {
      return y;
    }
  }

  // Unsigned addition with carry.
  constexpr ValueWithCarry AddUnsigned(
      const Integer &y, bool carryIn = false) const {
    Integer sum{nullptr};
    BigPart carry{carryIn};
    for (int j{0}; j + 1 < parts; ++j) {
      carry += LEPart(j);
      carry += y.LEPart(j);
      sum.SetLEPart(j, carry);
      carry >>= partBits;
    }
    carry += LEPart(parts - 1);
    carry += y.LEPart(parts - 1);
    sum.SetLEPart(parts - 1, carry);
    return {sum, carry > topPartMask};
  }

  constexpr ValueWithOverflow AddSigned(const Integer &y) const {
    bool isNegative{IsNegative()};
    bool sameSign{isNegative == y.IsNegative()};
    ValueWithCarry sum{AddUnsigned(y)};
    bool overflow{sameSign && sum.value.IsNegative() != isNegative};
    return {sum.value, overflow};
  }

  constexpr ValueWithOverflow SubtractSigned(const Integer &y) const {
    bool isNegative{IsNegative()};
    bool sameSign{isNegative == y.IsNegative()};
    ValueWithCarry diff{AddUnsigned(y.Negate().value)};
    bool overflow{!sameSign && diff.value.IsNegative() != isNegative};
    return {diff.value, overflow};
  }

  // MAX(X-Y, 0)
  constexpr Integer DIM(const Integer &y) const {
    if (CompareSigned(y) != Ordering::Greater) {
      return {};
    } else {
      return SubtractSigned(y).value;
    }
  }

  constexpr ValueWithOverflow SIGN(bool toNegative) const {
    if (toNegative == IsNegative()) {
      return {*this, false};
    } else if (toNegative) {
      return Negate();
    } else {
      return ABS();
    }
  }

  constexpr ValueWithOverflow SIGN(const Integer &sign) const {
    return SIGN(sign.IsNegative());
  }

  constexpr Product MultiplyUnsigned(const Integer &y) const {
    Part product[2 * parts]{}; // little-endian full product
    for (int j{0}; j < parts; ++j) {
      if (Part xpart{LEPart(j)}) {
        for (int k{0}; k < parts; ++k) {
          if (Part ypart{y.LEPart(k)}) {
            BigPart xy{xpart};
            xy *= ypart;
#if defined __GNUC__ && __GNUC__ < 8
            // && to < (2 * parts) was added to avoid GCC < 8 build failure on
            // -Werror=array-bounds. This can be removed if -Werror is disable.
            for (int to{j + k}; xy != 0 && to < (2 * parts); ++to) {
#else
            for (int to{j + k}; xy != 0; ++to) {
#endif
              xy += product[to];
              product[to] = xy & partMask;
              xy >>= partBits;
            }
          }
        }
      }
    }
    Integer upper{nullptr}, lower{nullptr};
    for (int j{0}; j < parts; ++j) {
      lower.LEPart(j) = product[j];
      upper.LEPart(j) = product[j + parts];
    }
    if constexpr (topPartBits < partBits) {
      upper = upper.SHIFTL(partBits - topPartBits);
      upper.LEPart(0) |= lower.LEPart(parts - 1) >> topPartBits;
      lower.LEPart(parts - 1) &= topPartMask;
    }
    return {upper, lower};
  }

  constexpr Product MultiplySigned(const Integer &y) const {
    bool yIsNegative{y.IsNegative()};
    Integer absy{y};
    if (yIsNegative) {
      absy = y.Negate().value;
    }
    bool isNegative{IsNegative()};
    Integer absx{*this};
    if (isNegative) {
      absx = Negate().value;
    }
    Product product{absx.MultiplyUnsigned(absy)};
    if (isNegative != yIsNegative) {
      product.lower = product.lower.NOT();
      product.upper = product.upper.NOT();
      Integer one{1};
      auto incremented{product.lower.AddUnsigned(one)};
      product.lower = incremented.value;
      if (incremented.carry) {
        product.upper = product.upper.AddUnsigned(one).value;
      }
    }
    return product;
  }

  constexpr QuotientWithRemainder DivideUnsigned(const Integer &divisor) const {
    if (divisor.IsZero()) {
      return {MASKR(bits), Integer{}, true, false}; // overflow to max value
    }
    int bitsDone{LEADZ()};
    Integer top{SHIFTL(bitsDone)};
    Integer quotient, remainder;
    for (; bitsDone < bits; ++bitsDone) {
      auto doubledTop{top.AddUnsigned(top)};
      top = doubledTop.value;
      remainder = remainder.AddUnsigned(remainder, doubledTop.carry).value;
      bool nextBit{remainder.CompareUnsigned(divisor) != Ordering::Less};
      quotient = quotient.AddUnsigned(quotient, nextBit).value;
      if (nextBit) {
        remainder = remainder.SubtractSigned(divisor).value;
      }
    }
    return {quotient, remainder, false, false};
  }

  // A nonzero remainder has the sign of the dividend, i.e., it computes
  // the MOD intrinsic (X-INT(X/Y)*Y), not MODULO (which is below).
  // 8/5 = 1r3;  -8/5 = -1r-3;  8/-5 = -1r3;  -8/-5 = 1r-3
  constexpr QuotientWithRemainder DivideSigned(Integer divisor) const {
    bool dividendIsNegative{IsNegative()};
    bool negateQuotient{dividendIsNegative};
    Ordering divisorOrdering{divisor.CompareToZeroSigned()};
    if (divisorOrdering == Ordering::Less) {
      negateQuotient = !negateQuotient;
      auto negated{divisor.Negate()};
      if (negated.overflow) {
        // divisor was (and is) the most negative number
        if (CompareUnsigned(divisor) == Ordering::Equal) {
          return {MASKR(1), Integer{}, false, bits <= 1};
        } else {
          return {Integer{}, *this, false, false};
        }
      }
      divisor = negated.value;
    } else if (divisorOrdering == Ordering::Equal) {
      // division by zero
      if (dividendIsNegative) {
        return {MASKL(1), Integer{}, true, false};
      } else {
        return {MASKR(bits - 1), Integer{}, true, false};
      }
    }
    Integer dividend{*this};
    if (dividendIsNegative) {
      auto negated{Negate()};
      if (negated.overflow) {
        // Dividend was (and remains) the most negative number.
        // See whether the original divisor was -1 (if so, it's 1 now).
        if (divisorOrdering == Ordering::Less &&
            divisor.CompareUnsigned(Integer{1}) == Ordering::Equal) {
          // most negative number / -1 is the sole overflow case
          return {*this, Integer{}, false, true};
        }
      } else {
        dividend = negated.value;
      }
    }
    // Overflow is not possible, and both the dividend and divisor
    // are now positive.
    QuotientWithRemainder result{dividend.DivideUnsigned(divisor)};
    if (negateQuotient) {
      result.quotient = result.quotient.Negate().value;
    }
    if (dividendIsNegative) {
      result.remainder = result.remainder.Negate().value;
    }
    return result;
  }

  // Result has the sign of the divisor argument.
  // 8 mod 5 = 3;  -8 mod 5 = 2;  8 mod -5 = -2;  -8 mod -5 = -3
  constexpr ValueWithOverflow MODULO(const Integer &divisor) const {
    bool negativeDivisor{divisor.IsNegative()};
    bool distinctSigns{IsNegative() != negativeDivisor};
    QuotientWithRemainder divided{DivideSigned(divisor)};
    if (distinctSigns && !divided.remainder.IsZero()) {
      return {divided.remainder.AddUnsigned(divisor).value, divided.overflow};
    } else {
      return {divided.remainder, divided.overflow};
    }
  }

  constexpr PowerWithErrors Power(const Integer &exponent) const {
    PowerWithErrors result{1, false, false, false};
    if (exponent.IsZero()) {
      // x**0 -> 1, including the case 0**0, which is not defined specifically
      // in F'18 afaict; however, other Fortrans tested all produce 1, not 0,
      // apart from nagfor, which stops with an error at runtime.
      // Ada, APL, C's pow(), Haskell, Julia, MATLAB, and R all produce 1 too.
      // F'77 explicitly states that 0**0 is mathematically undefined and
      // therefore prohibited.
      result.zeroToZero = IsZero();
    } else if (exponent.IsNegative()) {
      if (IsZero()) {
        result.divisionByZero = true;
        result.power = MASKR(bits - 1);
      } else if (CompareSigned(Integer{1}) == Ordering::Equal) {
        result.power = *this; // 1**x -> 1
      } else if (CompareSigned(Integer{-1}) == Ordering::Equal) {
        if (exponent.BTEST(0)) {
          result.power = *this; // (-1)**x -> -1 if x is odd
        }
      } else {
        result.power.Clear(); // j**k -> 0 if |j| > 1 and k < 0
      }
    } else {
      Integer shifted{*this};
      Integer pow{exponent};
      int nbits{bits - pow.LEADZ()};
      for (int j{0}; j < nbits; ++j) {
        if (pow.BTEST(j)) {
          Product product{result.power.MultiplySigned(shifted)};
          result.power = product.lower;
          result.overflow |= product.SignedMultiplicationOverflowed();
        }
        if (j + 1 < nbits) {
          Product squared{shifted.MultiplySigned(shifted)};
          result.overflow |= squared.SignedMultiplicationOverflowed();
          shifted = squared.lower;
        }
      }
    }
    return result;
  }

private:
  // A private constructor, selected by the use of nullptr,
  // that is used by member functions when it would be a waste
  // of time to initialize parts_[].
  constexpr Integer(std::nullptr_t) {}

  // Accesses parts in little-endian order.
  constexpr const Part &LEPart(int part) const {
    if constexpr (littleEndian) {
      return part_[part];
    } else {
      return part_[parts - 1 - part];
    }
  }

  constexpr Part &LEPart(int part) {
    if constexpr (littleEndian) {
      return part_[part];
    } else {
      return part_[parts - 1 - part];
    }
  }

  constexpr void SetLEPart(int part, Part x) {
    LEPart(part) = x & PartMask(part);
  }

  static constexpr Part PartMask(int part) {
    return part == parts - 1 ? topPartMask : partMask;
  }

  constexpr void Clear() {
    for (int j{0}; j < parts; ++j) {
      part_[j] = 0;
    }
  }

  Part part_[parts]{};
};

extern template class Integer<8>;
extern template class Integer<16>;
extern template class Integer<32>;
extern template class Integer<64>;
extern template class Integer<80>;
extern template class Integer<128>;
} // namespace Fortran::evaluate::value
#endif // FORTRAN_EVALUATE_INTEGER_H_