BLI_fixed_width_int.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2024 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */

 
#pragma once
 
#include <cmath>
 
#include "BLI_string_ref.hh"
#include "BLI_unroll.hh"
 
namespace blender::fixed_width_int {

template<typename T, int S> struct UIntF {
  static_assert(std::is_unsigned_v<T>);
  static_assert(S >= 1);

  std::array<T, S> v;

  UIntF() = default;

  explicit UIntF(uint64_t value);

  explicit UIntF(StringRefNull str, int base = 10);

  explicit operator uint64_t() const;

  explicit operator double() const;
  explicit operator float() const;
 
/* See `BLI_fixed_width_int_str.hh`. */
#ifdef WITH_GMP
  void set_from_str(StringRefNull str, int base = 10);

  std::string to_string(int base = 10) const;
#endif
};

template<typename T, int S> struct IntF {
  static_assert(std::is_unsigned_v<T>);
  static_assert(S >= 1);

  std::array<T, S> v;

  IntF() = default;

  explicit IntF(int64_t value);

  explicit IntF(const UIntF<T, S> &value);

  explicit IntF(StringRefNull str, int base = 10);

  explicit operator int64_t() const;

  explicit operator double() const;
  explicit operator float() const;

  explicit operator UIntF<T, S>() const;
 
/* See `BLI_fixed_width_int_str.hh`. */
#ifdef WITH_GMP
  void set_from_str(const StringRefNull str, const int base = 10);

  std::string to_string(int base = 10) const;
#endif
};
 
template<typename T> struct DoubleUIntType {
  using type = void;
};
template<> struct DoubleUIntType<uint8_t> {
  using type = uint16_t;
};
template<> struct DoubleUIntType<uint16_t> {
  using type = uint32_t;
};
template<> struct DoubleUIntType<uint32_t> {
  using type = uint64_t;
};
#ifndef _MSC_VER
template<> struct DoubleUIntType<uint64_t> {
  using type = __uint128_t;
};
#endif

template<typename T> using double_uint_type = typename DoubleUIntType<T>::type;
 
using UInt64_8 = UIntF<uint8_t, 8>;
using UInt64_16 = UIntF<uint16_t, 4>;
using UInt64_32 = UIntF<uint32_t, 2>;
 
using Int64_8 = IntF<uint8_t, 8>;
using Int64_16 = IntF<uint16_t, 4>;
using Int64_32 = IntF<uint32_t, 2>;
 
using UInt128_8 = UIntF<uint8_t, 16>;
using UInt128_16 = UIntF<uint16_t, 8>;
using UInt128_32 = UIntF<uint32_t, 4>;
using UInt128_64 = UIntF<uint64_t, 2>;
 
using UInt256_8 = UIntF<uint8_t, 32>;
using UInt256_16 = UIntF<uint16_t, 16>;
using UInt256_32 = UIntF<uint32_t, 8>;
using UInt256_64 = UIntF<uint64_t, 4>;
 
using Int128_8 = IntF<uint8_t, 16>;
using Int128_16 = IntF<uint16_t, 8>;
using Int128_32 = IntF<uint32_t, 4>;
using Int128_64 = IntF<uint64_t, 2>;
 
using Int256_8 = IntF<uint8_t, 32>;
using Int256_16 = IntF<uint16_t, 16>;
using Int256_32 = IntF<uint32_t, 8>;
using Int256_64 = IntF<uint64_t, 4>;
 
#ifdef _MSC_VER
using UInt128 = UInt128_32;
using UInt256 = UInt256_32;
using Int128 = Int128_32;
using Int256 = Int256_32;
#else
using UInt128 = UInt128_64;
using UInt256 = UInt256_64;
using Int128 = Int128_64;
using Int256 = Int256_64;
#endif
 
template<typename T, int S> inline UIntF<T, S>::UIntF(const uint64_t value)
{
  constexpr int Count = std::min(S, int(sizeof(decltype(value)) / sizeof(T)));
  constexpr int BitsPerT = 8 * sizeof(T);
 
  for (int i = 0; i < Count; i++) {
    this->v[i] = T(value >> (BitsPerT * i));
  }
  for (int i = Count; i < S; i++) {
    this->v[i] = 0;
  }
}
 
template<typename T, int S> inline IntF<T, S>::IntF(const int64_t value)
{
  constexpr int Count = std::min(S, int(sizeof(decltype(value)) / sizeof(T)));
  constexpr int BitsPerT = 8 * sizeof(T);
 
  for (int i = 0; i < Count; i++) {
    this->v[i] = T(value >> (BitsPerT * i));
  }
  const T sign_extend_fill = value < 0 ? T(-1) : T(0);
  for (int i = Count; i < S; i++) {
    this->v[i] = sign_extend_fill;
  }
}
 
template<typename T, int S> inline IntF<T, S>::IntF(const UIntF<T, S> &value) : v(value.v) {}
 
#ifdef WITH_GMP
template<typename T, int S> UIntF<T, S>::UIntF(const StringRefNull str, const int base)
{
  this->set_from_str(str, base);
}
 
template<typename T, int S> IntF<T, S>::IntF(const StringRefNull str, const int base)
{
  this->set_from_str(str, base);
}
#endif /* WITH_GMP */
 
template<typename T, int S> inline UIntF<T, S>::operator uint64_t() const
{
  constexpr int Count = std::min(S, int(sizeof(uint64_t) / sizeof(T)));
  constexpr int BitsPerT = 8 * sizeof(T);
 
  uint64_t result = 0;
  for (int i = 0; i < Count; i++) {
    result |= uint64_t(this->v[i]) << (BitsPerT * i);
  }
  return result;
}
 
template<typename T, int S> inline UIntF<T, S>::operator double() const
{
  double result = double(this->v[0]);
  for (int i = 1; i < S; i++) {
    const T a = this->v[i];
    if (a == 0) {
      continue;
    }
    result += ldexp(a, 8 * sizeof(T) * i);
  }
  return result;
}
 
template<typename T, int S> inline UIntF<T, S>::operator float() const
{
  return float(double(*this));
}
 
template<typename T, int S> inline IntF<T, S>::operator int64_t() const
{
  return int64_t(uint64_t(UIntF<T, S>(*this)));
}
 
template<typename T, int S> inline IntF<T, S>::operator double() const
{
  if (is_negative(*this)) {
    return -double(-*this);
  }
  double result = double(this->v[0]);
  for (int i = 1; i < S; i++) {
    const T a = this->v[i];
    if (a == 0) {
      continue;
    }
    result += ldexp(a, 8 * sizeof(T) * i);
  }
  return result;
}
 
template<typename T, int S> inline IntF<T, S>::operator float() const
{
  return float(double(*this));
}
 
template<typename T, int S> inline IntF<T, S>::operator UIntF<T, S>() const
{
  UIntF<T, S> result;
  result.v = this->v;
  return result;
}

template<typename T, typename T2, int S>
inline void generic_add(T *__restrict dst, const T *a, const T *b)
{
  constexpr int shift = 8 * sizeof(T);
  T2 carry = 0;
  unroll<S>([&](auto i) {
    const T2 ai = T2(a[i]);
    const T2 bi = T2(b[i]);
    const T2 ri = ai + bi + carry;
    dst[i] = T(ri);
    carry = ri >> shift;
  });
}

template<typename T, typename T2, int S>
inline void generic_sub(T *__restrict dst, const T *a, const T *b)
{
  T2 carry = 0;
  unroll<S>([&](auto i) {
    const T2 ai = T2(a[i]);
    const T2 bi = T2(b[i]);
    const T2 ri = ai - bi - carry;
    dst[i] = T(ri);
    carry = ri > ai;
  });
}

template<typename T, typename T2, int S>
inline void generic_unsigned_mul(T *__restrict dst, const T *a, const T *b)
{
  constexpr int shift = 8 * sizeof(T);
 
  T2 r[S] = {};
 
  for (int i = 0; i < S; i++) {
    const T2 bi = T2(b[i]);
    T2 carry = 0;
    for (int j = 0; j < S - i; j++) {
      const T2 rji = T2(a[j]) * bi + carry;
      carry = rji >> shift;
      r[i + j] += T2(T(rji));
    }
  }
 
  T2 carry = 0;
  for (int i = 0; i < S; i++) {
    const T2 ri = r[i] + carry;
    carry = ri >> shift;
    dst[i] = T(ri);
  }
}
 
template<typename T, int Size, BLI_ENABLE_IF((!std::is_void_v<double_uint_type<T>>))>
inline UIntF<T, Size> operator+(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  UIntF<T, Size> result;
  generic_add<T, double_uint_type<T>, Size>(result.v.data(), a.v.data(), b.v.data());
  return result;
}
 
template<typename T, int Size, BLI_ENABLE_IF((!std::is_void_v<double_uint_type<T>>))>
inline IntF<T, Size> operator+(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  IntF<T, Size> result;
  generic_add<T, double_uint_type<T>, Size>(result.v.data(), a.v.data(), b.v.data());
  return result;
}
 
template<typename T, int Size>
inline UIntF<T, Size> operator-(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  UIntF<T, Size> result;
  generic_sub<T, double_uint_type<T>, Size>(result.v.data(), a.v.data(), b.v.data());
  return result;
}
 
template<typename T, int Size>
inline IntF<T, Size> operator-(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  IntF<T, Size> result;
  generic_sub<T, double_uint_type<T>, Size>(result.v.data(), a.v.data(), b.v.data());
  return result;
}
 
template<typename T, int Size, BLI_ENABLE_IF((!std::is_void_v<double_uint_type<T>>))>
inline UIntF<T, Size> operator*(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  UIntF<T, Size> result;
  generic_unsigned_mul<T, double_uint_type<T>, Size>(result.v.data(), a.v.data(), b.v.data());
  return result;
}

template<typename T, int Size> bool is_negative(const IntF<T, Size> &a)
{
  return (a.v[Size - 1] & (T(1) << (sizeof(T) * 8 - 1))) != 0;
}
 
template<typename T, int Size> inline bool is_zero(const UIntF<T, Size> &a)
{
  bool result = true;
  unroll<Size>([&](auto i) { result &= (a.v[i] == 0); });
  return result;
}
 
template<typename T, int Size> inline bool is_zero(const IntF<T, Size> &a)
{
  bool result = true;
  unroll<Size>([&](auto i) { result &= (a.v[i] == 0); });
  return result;
}
 
template<typename T, int Size, BLI_ENABLE_IF((!std::is_void_v<double_uint_type<T>>))>
inline IntF<T, Size> operator*(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  using UIntF = UIntF<T, Size>;
  using IntF = IntF<T, Size>;
 
  /* Signed multiplication is implemented in terms of unsigned multiplication. */
  const bool is_negative_a = is_negative(a);
  const bool is_negative_b = is_negative(b);
  if (is_negative_a && is_negative_b) {
    return IntF(UIntF(-a) * UIntF(-b));
  }
  if (is_negative_a) {
    return -IntF(UIntF(-a) * UIntF(b));
  }
  if (is_negative_b) {
    return -IntF(UIntF(a) * UIntF(-b));
  }
  return IntF(UIntF(a) * UIntF(b));
}
 
template<typename T, int Size> inline IntF<T, Size> operator-(const IntF<T, Size> &a)
{
  IntF<T, Size> result;
  for (int i = 0; i < Size; i++) {
    result.v[i] = ~a.v[i];
  }
  return result + IntF<T, Size>(1);
}
 
template<typename T, int Size> inline void operator+=(UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  a = a + b;
}
 
template<typename T, int Size> inline void operator+=(IntF<T, Size> &a, const IntF<T, Size> &b)
{
  a = a + b;
}
 
template<typename T, int Size> inline void operator-=(UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  a = a - b;
}
 
template<typename T, int Size> inline void operator-=(IntF<T, Size> &a, const IntF<T, Size> &b)
{
  a = a - b;
}
 
template<typename T, int Size> inline void operator*=(UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  a = a * b;
}
 
template<typename T, int Size> inline void operator*=(IntF<T, Size> &a, const IntF<T, Size> &b)
{
  a = a * b;
}
 
template<typename T, int Size>
inline bool operator==(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  return a.v == b.v;
}
 
template<typename T, int Size>
inline bool operator==(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return a.v == b.v;
}
 
template<typename T, int Size>
inline bool operator!=(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  return a.v != b.v;
}
 
template<typename T, int Size>
inline bool operator!=(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return a.v != b.v;
}
 
template<typename T, size_t Size>
inline int compare_reversed_order(const std::array<T, Size> &a, const std::array<T, Size> &b)
{
  for (int i = Size - 1; i >= 0; i--) {
    if (a[i] < b[i]) {
      return -1;
    }
    if (a[i] > b[i]) {
      return 1;
    }
  }
  return 0;
}
 
template<typename T, int Size>
inline bool operator<(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  const bool is_negative_a = is_negative(a);
  const bool is_negative_b = is_negative(b);
  if (is_negative_a == is_negative_b) {
    return compare_reversed_order(a.v, b.v) < 0;
  }
  return is_negative_a;
}
 
template<typename T, int Size>
inline bool operator<=(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  const bool is_negative_a = is_negative(a);
  const bool is_negative_b = is_negative(b);
  if (is_negative_a == is_negative_b) {
    return compare_reversed_order(a.v, b.v) <= 0;
  }
  return is_negative_a;
}
 
template<typename T, int Size>
inline bool operator>(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  const bool is_negative_a = is_negative(a);
  const bool is_negative_b = is_negative(b);
  if (is_negative_a == is_negative_b) {
    return compare_reversed_order(a.v, b.v) > 0;
  }
  return is_negative_b;
}
 
template<typename T, int Size>
inline bool operator>=(const IntF<T, Size> &a, const IntF<T, Size> &b)
{
  const bool is_negative_a = is_negative(a);
  const bool is_negative_b = is_negative(b);
  if (is_negative_a == is_negative_b) {
    return compare_reversed_order(a.v, b.v) >= 0;
  }
  return is_negative_b;
}
 
template<typename T, int Size>
inline bool operator<(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return compare_reversed_order(a.v, b.v) < 0;
}
 
template<typename T, int Size>
inline bool operator<=(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return compare_reversed_order(a.v, b.v) <= 0;
}
 
template<typename T, int Size>
inline bool operator>(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return compare_reversed_order(a.v, b.v) > 0;
}
 
template<typename T, int Size>
inline bool operator>=(const UIntF<T, Size> &a, const UIntF<T, Size> &b)
{
  return compare_reversed_order(a.v, b.v) >= 0;
}
 
}  // namespace blender::fixed_width_int