libc/src/__support/FPUtil/UInt.h

//===-- A class to manipulate wide integers. --------------------*- 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 LLVM_LIBC_UTILS_FPUTIL_UINT_H
#define LLVM_LIBC_UTILS_FPUTIL_UINT_H

#include <stddef.h> // For size_t
#include <stdint.h>

namespace __llvm_libc {
namespace fputil {

template <size_t Bits> class UInt {

  // This is mainly used for debugging.
  enum Kind {
    NotANumber,
    Valid,
  };

  static_assert(Bits > 0 && Bits % 64 == 0,
                "Number of bits in UInt should be a multiple of 64.");
  static constexpr uint64_t Mask32 = 0xFFFFFFFF;
  static constexpr size_t WordCount = Bits / 64;
  static constexpr uint64_t InvalidHexDigit = 20;
  uint64_t val[WordCount];
  Kind kind;

  uint64_t low(uint64_t v) { return v & Mask32; }

  uint64_t high(uint64_t v) { return (v >> 32) & Mask32; }

  uint64_t hexval(char c) {
    uint64_t diff;
    if ((diff = uint64_t(c) - 'A') < 6)
      return diff + 10;
    else if ((diff = uint64_t(c) - 'a') < 6)
      return diff + 10;
    else if ((diff = uint64_t(c) - '0') < 10)
      return diff;
    else
      return InvalidHexDigit;
  }

  size_t strlen(const char *s) {
    size_t len;
    for (len = 0; *s != '\0'; ++s, ++len)
      ;
    return len;
  }

public:
  UInt() { kind = Valid; }

  UInt(const UInt<Bits> &other) : kind(other.kind) {
    if (kind == Valid) {
      for (size_t i = 0; i < WordCount; ++i)
        val[i] = other.val[i];
    }
  }

  // This constructor is used for debugging.
  explicit UInt(const char *s) {
    size_t len = strlen(s);
    if (len > Bits / 4 + 2 || len < 3) {
      kind = NotANumber;
      return;
    }

    if (!(s[0] == '0' && s[1] == 'x')) {
      kind = NotANumber;
      return;
    }

    for (size_t i = 0; i < WordCount; ++i)
      val[i] = 0;

    for (size_t i = len - 1, w = 0; i >= 2; --i, w += 4) {
      uint64_t hex = hexval(s[i]);
      if (hex == InvalidHexDigit) {
        kind = NotANumber;
        return;
      }
      val[w / 64] |= (hex << (w % 64));
    }

    kind = Valid;
  }

  explicit UInt(uint64_t v) {
    val[0] = v;
    for (size_t i = 1; i < WordCount; ++i)
      val[i] = 0;
    kind = Valid;
  }

  explicit UInt(uint64_t data[WordCount]) {
    for (size_t i = 0; i < WordCount; ++i)
      val[i] = data[i];
    kind = Valid;
  }

  bool is_valid() const { return kind == Valid; }

  // Add x to this number and store the result in this number.
  // Returns the carry value produced by the addition operation.
  uint64_t add(const UInt<Bits> &x) {
    uint64_t carry = 0;
    for (size_t i = 0; i < WordCount; ++i) {
      uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry;
      carry = high(res_lo);
      res_lo = low(res_lo);

      uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry;
      carry = high(res_hi);
      res_hi = low(res_hi);

      val[i] = res_lo + (res_hi << 32);
    }
    return carry;
  }

  // Multiply this number with x and store the result in this number. It is
  // implemented using the long multiplication algorithm by splitting the
  // 64-bit words of this number and |x| in to 32-bit halves but peforming
  // the operations using 64-bit numbers. This ensures that we don't lose the
  // carry bits.
  // Returns the carry value produced by the multiplication operation.
  uint64_t mul(uint64_t x) {
    uint64_t x_lo = low(x);
    uint64_t x_hi = high(x);

    uint64_t row1[WordCount + 1];
    uint64_t carry = 0;
    for (size_t i = 0; i < WordCount; ++i) {
      uint64_t l = low(val[i]);
      uint64_t h = high(val[i]);
      uint64_t p1 = x_lo * l;
      uint64_t p2 = x_lo * h;

      uint64_t res_lo = low(p1) + carry;
      carry = high(res_lo);
      uint64_t res_hi = high(p1) + low(p2) + carry;
      carry = high(res_hi) + high(p2);

      res_lo = low(res_lo);
      res_hi = low(res_hi);
      row1[i] = res_lo + (res_hi << 32);
    }
    row1[WordCount] = carry;

    uint64_t row2[WordCount + 1];
    row2[0] = 0;
    carry = 0;
    for (size_t i = 0; i < WordCount; ++i) {
      uint64_t l = low(val[i]);
      uint64_t h = high(val[i]);
      uint64_t p1 = x_hi * l;
      uint64_t p2 = x_hi * h;

      uint64_t res_lo = low(p1) + carry;
      carry = high(res_lo);
      uint64_t res_hi = high(p1) + low(p2) + carry;
      carry = high(res_hi) + high(p2);

      res_lo = low(res_lo);
      res_hi = low(res_hi);
      row2[i] = res_lo + (res_hi << 32);
    }
    row2[WordCount] = carry;

    UInt<(WordCount + 1) * 64> r1(row1), r2(row2);
    r2.shift_left(32);
    r1.add(r2);
    for (size_t i = 0; i < WordCount; ++i) {
      val[i] = r1[i];
    }
    return r1[WordCount];
  }

  void shift_left(size_t s) {
    const size_t drop = s / 64;  // Number of words to drop
    const size_t shift = s % 64; // Bits to shift in the remaining words.
    const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift);

    for (size_t i = WordCount; drop > 0 && i > 0; --i) {
      if (i - drop > 0)
        val[i - 1] = val[i - drop - 1];
      else
        val[i - 1] = 0;
    }
    for (size_t i = WordCount; shift > 0 && i > drop; --i) {
      uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift);
      val[i - 1] <<= shift;
      if (i < WordCount)
        val[i] |= drop_val;
    }
  }

  void shift_right(size_t s) {
    const size_t drop = s / 64;  // Number of words to drop
    const size_t shift = s % 64; // Bit shift in the remaining words.
    const uint64_t mask = (uint64_t(1) << shift) - 1;

    for (size_t i = 0; drop > 0 && i < WordCount; ++i) {
      if (i + drop < WordCount)
        val[i] = val[i + drop];
      else
        val[i] = 0;
    }
    for (size_t i = 0; shift > 0 && i < WordCount; ++i) {
      uint64_t drop_val = ((val[i] & mask) << (64 - shift));
      val[i] >>= shift;
      if (i > 0)
        val[i - 1] |= drop_val;
    }
  }

  const uint64_t &operator[](size_t i) const { return val[i]; }

  uint64_t &operator[](size_t i) { return val[i]; }

  uint64_t *data() { return val; }

  const uint64_t *data() const { return val; }
};

} // namespace fputil
} // namespace __llvm_libc

#endif // LLVM_LIBC_UTILS_FPUTIL_UINT_H