wide_uint.hpp

Go to the documentation of this file.

 
 
#ifndef MORTON_WIDE_UINT_HPP
#define MORTON_WIDE_UINT_HPP
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <type_traits>
 
#include "morton/hd.hpp"
 
// MORTON_HAS_INT128: set when the compiler provides the `__int128` built-ins (GCC/Clang/nvcc).
// Defined here rather than in morton.hpp because wide_uint.hpp is the lowest header that needs it.
#if defined(__SIZEOF_INT128__)
#define MORTON_HAS_INT128 1
#endif
 
namespace morton {
namespace detail {
 
#if defined(MORTON_HAS_INT128)
__extension__ using uint128_t = unsigned __int128;
#endif
 
template <std::size_t W>
struct wide_uint {
  static_assert(W >= 2, "use a built-in integer for <= 64 bits");
  std::array<std::uint64_t, W> w{};  
 
  MORTON_HD constexpr wide_uint() = default;
 
  // From any built-in integral value up to 64 bits (low word).
  template <typename T, typename = std::enable_if_t<std::is_integral_v<T> && (sizeof(T) <= 8)>>
  MORTON_HD constexpr wide_uint(T v) : w{} {
    w[0] = std::uint64_t(static_cast<std::make_unsigned_t<T>>(v));
  }
 
#if defined(MORTON_HAS_INT128)
  // From a 128-bit built-in (fills the low two words).
  MORTON_HD constexpr wide_uint(uint128_t v) : w{} {
    w[0] = std::uint64_t(v);
    if constexpr (W >= 2)
      w[1] = std::uint64_t(v >> 64);
  }
#endif
 
  // From a wide_uint of a different width (truncate or zero-extend).
  template <std::size_t W2, typename = std::enable_if_t<W2 != W>>
  MORTON_HD constexpr explicit wide_uint(const wide_uint<W2>& o) : w{} {
    for (std::size_t i = 0; i < W && i < W2; ++i)
      w[i] = o.w[i];
  }
 
  MORTON_HD explicit constexpr operator std::uint64_t() const { return w[0]; }
#if defined(MORTON_HAS_INT128)
  MORTON_HD explicit constexpr operator uint128_t() const {
    uint128_t r = w[0];
    if constexpr (W >= 2)
      r |= uint128_t(w[1]) << 64;
    return r;
  }
#endif
  MORTON_HD explicit constexpr operator bool() const {
    for (std::size_t i = 0; i < W; ++i)
      if (w[i])
        return true;
    return false;
  }
 
  // ---- bitwise ----------------------------------------------------------
  MORTON_HD constexpr wide_uint operator~() const {
    wide_uint r;
    for (std::size_t i = 0; i < W; ++i)
      r.w[i] = ~w[i];
    return r;
  }
  MORTON_HD constexpr wide_uint& operator&=(const wide_uint& o) {
    for (std::size_t i = 0; i < W; ++i)
      w[i] &= o.w[i];
    return *this;
  }
  MORTON_HD constexpr wide_uint& operator|=(const wide_uint& o) {
    for (std::size_t i = 0; i < W; ++i)
      w[i] |= o.w[i];
    return *this;
  }
  MORTON_HD constexpr wide_uint& operator^=(const wide_uint& o) {
    for (std::size_t i = 0; i < W; ++i)
      w[i] ^= o.w[i];
    return *this;
  }
  friend MORTON_HD constexpr wide_uint operator&(wide_uint a, const wide_uint& b) { return a &= b; }
  friend MORTON_HD constexpr wide_uint operator|(wide_uint a, const wide_uint& b) { return a |= b; }
  friend MORTON_HD constexpr wide_uint operator^(wide_uint a, const wide_uint& b) { return a ^= b; }
 
  // ---- shifts -----------------------------------------------------------
  MORTON_HD constexpr wide_uint operator<<(unsigned s) const {
    wide_uint r;
    const unsigned ws = s / 64, bs = s % 64;
    for (int i = int(W) - 1; i >= 0; --i) {
      const int src = i - int(ws);
      std::uint64_t v = 0;
      if (src >= 0) {
        v = w[std::size_t(src)] << bs;
        if (bs && src - 1 >= 0)
          v |= w[std::size_t(src - 1)] >> (64 - bs);
      }
      r.w[std::size_t(i)] = v;
    }
    return r;
  }
  MORTON_HD constexpr wide_uint operator>>(unsigned s) const {
    wide_uint r;
    const unsigned ws = s / 64, bs = s % 64;
    for (std::size_t i = 0; i < W; ++i) {
      const std::size_t src = i + ws;
      std::uint64_t v = 0;
      if (src < W) {
        v = w[src] >> bs;
        if (bs && src + 1 < W)
          v |= w[src + 1] << (64 - bs);
      }
      r.w[i] = v;
    }
    return r;
  }
  MORTON_HD constexpr wide_uint& operator<<=(unsigned s) { return *this = (*this << s); }
  MORTON_HD constexpr wide_uint& operator>>=(unsigned s) { return *this = (*this >> s); }
 
  // ---- add / sub (ripple) -----------------------------------------------
  friend MORTON_HD constexpr wide_uint operator+(const wide_uint& a, const wide_uint& b) {
    wide_uint r;
    std::uint64_t carry = 0;
    for (std::size_t i = 0; i < W; ++i) {
      std::uint64_t s1 = a.w[i] + b.w[i];
      std::uint64_t c1 = (s1 < a.w[i]) ? 1u : 0u;
      std::uint64_t s2 = s1 + carry;
      std::uint64_t c2 = (s2 < s1) ? 1u : 0u;
      r.w[i] = s2;
      carry = c1 | c2;
    }
    return r;
  }
  friend MORTON_HD constexpr wide_uint operator-(const wide_uint& a, const wide_uint& b) {
    wide_uint r;
    std::uint64_t borrow = 0;
    for (std::size_t i = 0; i < W; ++i) {
      std::uint64_t d1 = a.w[i] - b.w[i];
      std::uint64_t b1 = (a.w[i] < b.w[i]) ? 1u : 0u;
      std::uint64_t d2 = d1 - borrow;
      std::uint64_t b2 = (d1 < borrow) ? 1u : 0u;
      r.w[i] = d2;
      borrow = b1 | b2;
    }
    return r;
  }
  MORTON_HD constexpr wide_uint& operator++() { return *this = (*this + wide_uint(1)); }
  MORTON_HD constexpr wide_uint& operator--() { return *this = (*this - wide_uint(1)); }
 
  // ---- comparison -------------------------------------------------------
  friend MORTON_HD constexpr bool operator==(const wide_uint& a, const wide_uint& b) {
    for (std::size_t i = 0; i < W; ++i)
      if (a.w[i] != b.w[i])
        return false;
    return true;
  }
  friend MORTON_HD constexpr bool operator!=(const wide_uint& a, const wide_uint& b) {
    return !(a == b);
  }
  friend MORTON_HD constexpr bool operator<(const wide_uint& a, const wide_uint& b) {
    for (std::size_t i = W; i-- > 0;) {
      if (a.w[i] != b.w[i])
        return a.w[i] < b.w[i];
    }
    return false;
  }
  friend MORTON_HD constexpr bool operator>(const wide_uint& a, const wide_uint& b) {
    return b < a;
  }
  friend MORTON_HD constexpr bool operator<=(const wide_uint& a, const wide_uint& b) {
    return !(b < a);
  }
  friend MORTON_HD constexpr bool operator>=(const wide_uint& a, const wide_uint& b) {
    return !(a < b);
  }
};
 
}  // namespace detail
}  // namespace morton
 
#endif  // MORTON_WIDE_UINT_HPP