MRFastInt.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRFastInt128.h"
#include <MRPch/MRBindingMacros.h>
#include <array>
#include <cassert>
#include <compare>
#include <cstdint>
#include <type_traits>
 
namespace MR
{

 
namespace detail
{

template <typename T>
constexpr bool cFitsFastInt128 = std::is_integral_v<T> || std::is_same_v<T, FastInt128>;


[[nodiscard]] inline constexpr std::uint64_t addCarry64( std::uint64_t a, std::uint64_t b, std::uint64_t & carry ) noexcept
{
    const FastUInt128 t = FastUInt128( a ) + FastUInt128( b ) + FastUInt128( carry );
    carry = std::uint64_t( t >> 64 );
    return std::uint64_t( t );
}

[[nodiscard]] inline constexpr std::uint64_t subBorrow64( std::uint64_t a, std::uint64_t b, std::uint64_t & borrow ) noexcept
{
    const FastUInt128 t = FastUInt128( a ) - FastUInt128( b ) - FastUInt128( borrow );
    borrow = std::uint64_t( t >> 64 ) & 1;
    return std::uint64_t( t );
}

[[nodiscard]] inline constexpr std::uint64_t signWord( std::uint64_t hi ) noexcept
{
    return std::int64_t( hi ) < 0 ? ~std::uint64_t( 0 ) : 0;
}

template <std::size_t n, std::size_t m> 
[[nodiscard]] constexpr std::array<std::uint64_t, n + m> mulWords(
    const std::array<std::uint64_t, n> & a, const std::array<std::uint64_t, m> & b ) noexcept
{
    std::array<std::uint64_t, n + m> res = {};
    for ( std::size_t i = 0; i < n; ++i ) 
    {
        if ( a[i] == 0 )
            continue; 
        std::uint64_t carry = 0;
        for ( std::size_t j = 0; j < m; ++j )
        {
            const FastUInt128 t = FastUInt128( a[i] ) * FastUInt128( b[j] ) + FastUInt128( res[i + j] ) + FastUInt128( carry );
            res[i + j] = std::uint64_t( t );
            carry = std::uint64_t( t >> 64 );
        }
        res[i + m] = carry; 
    }

    if ( std::int64_t( a[n - 1] ) < 0 )
    {
        std::uint64_t borrow = 0;
        for ( std::size_t i = 0; i < m; ++i )
            res[n + i] = subBorrow64( res[n + i], b[i], borrow );
    }
    if ( std::int64_t( b[m - 1] ) < 0 )
    {
        std::uint64_t borrow = 0;
        for ( std::size_t i = 0; i < n; ++i )
            res[m + i] = subBorrow64( res[m + i], a[i], borrow );
    }
    return res;
}

template <typename T>
constexpr int cMulBits = std::is_same_v<T, FastInt128> || ( std::is_unsigned_v<T> && sizeof( T ) >= 8 ) ? 128 : 64;

template <typename T>
[[nodiscard]] constexpr auto mulWordsOf( T v ) noexcept
{
    if constexpr ( cMulBits<T> == 128 )
    {
        const FastInt128 x = FastInt128( v );
        return std::array{ std::uint64_t( x ), std::uint64_t( x >> 64 ) };
    }
    else
        return std::array{ std::uint64_t( std::int64_t( v ) ) };
}

[[nodiscard]] MRMESH_API double doubleFromWords( const std::uint64_t * w, int n ) noexcept;
 
}

[[nodiscard]] MR_BIND_IGNORE inline double toDouble( FastInt128 v ) noexcept
{
#ifdef MR_HAS_BUILTIN_INT128
    return double( v ); 
#else
    const FastUInt128 u( v );
    const std::uint64_t w[2] = { std::uint64_t( u ), std::uint64_t( u >> 64 ) };
    return detail::doubleFromWords( w, 2 );
#endif
}

template <int nBits>
class MR_BIND_IGNORE FastInt
{
public:
    static_assert( nBits >= 192 && nBits % 64 == 0 );

    static constexpr int numWords = nBits / 64;

    std::array<std::uint64_t, numWords> w = {};
 
    FastInt() noexcept = default;

    template <typename T>
    requires detail::cFitsFastInt128<T>
    constexpr FastInt( T v ) noexcept
    {
        const FastInt128 x = FastInt128( v );
        w[0] = std::uint64_t( x );
        w[1] = std::uint64_t( x >> 64 );
        const auto s = detail::signWord( w[1] );
        for ( int i = 2; i < numWords; ++i )
            w[i] = s;
    }

    template <int mBits>
    requires ( mBits < nBits )
    constexpr FastInt( const FastInt<mBits> & v ) noexcept
    {
        constexpr int m = FastInt<mBits>::numWords;
        for ( int i = 0; i < m; ++i )
            w[i] = v.w[i];
        const auto s = detail::signWord( v.w[m - 1] );
        for ( int i = m; i < numWords; ++i )
            w[i] = s;
    }

    template <int mBits>
    requires ( mBits > nBits )
    constexpr explicit FastInt( const FastInt<mBits> & v ) noexcept
    {
        for ( int i = 0; i < numWords; ++i )
            w[i] = v.w[i];
        [[maybe_unused]] const auto s = detail::signWord( w[numWords - 1] );
        for ( int i = numWords; i < FastInt<mBits>::numWords; ++i )
            assert( v.w[i] == s ); 
    }

    [[nodiscard]] constexpr int sign() const noexcept
    {
        if ( std::int64_t( w[numWords - 1] ) < 0 )
            return -1;
        std::uint64_t any = 0;
        for ( int i = 0; i < numWords; ++i )
            any |= w[i];
        return any != 0 ? 1 : 0;
    }
 
    constexpr FastInt & operator +=( const FastInt & b ) noexcept
    {
        std::uint64_t carry = 0;
        for ( int i = 0; i < numWords; ++i )
            w[i] = detail::addCarry64( w[i], b.w[i], carry );
        return *this;
    }
 
    constexpr FastInt & operator -=( const FastInt & b ) noexcept
    {
        std::uint64_t borrow = 0;
        for ( int i = 0; i < numWords; ++i )
            w[i] = detail::subBorrow64( w[i], b.w[i], borrow );
        return *this;
    }
 
    [[nodiscard]] constexpr FastInt operator -() const noexcept
    {
        FastInt res;
        res -= *this;
        return res;
    }
 
    [[nodiscard]] friend constexpr FastInt operator +( FastInt a, const FastInt & b ) noexcept { a += b; return a; }
    [[nodiscard]] friend constexpr FastInt operator -( FastInt a, const FastInt & b ) noexcept { a -= b; return a; }
 
    [[nodiscard]] friend constexpr bool operator ==( const FastInt & a, const FastInt & b ) noexcept { return a.w == b.w; }
 
    [[nodiscard]] friend constexpr std::strong_ordering operator <=>( const FastInt & a, const FastInt & b ) noexcept
    {
        if ( const auto c = std::int64_t( a.w[numWords - 1] ) <=> std::int64_t( b.w[numWords - 1] ); c != std::strong_ordering::equal )
            return c;
        for ( int i = numWords - 2; i >= 0; --i )
            if ( const auto c = a.w[i] <=> b.w[i]; c != std::strong_ordering::equal )
                return c;
        return std::strong_ordering::equal;
    }
};

template <int nBits>
[[nodiscard]] MR_BIND_IGNORE inline double toDouble( const FastInt<nBits> & v ) noexcept
{
    return detail::doubleFromWords( v.w.data(), FastInt<nBits>::numWords );
}
 
using FastInt256 = FastInt<256>;
using FastInt512 = FastInt<512>;
using FastInt1024 = FastInt<1024>;

 
template <int nBits, int mBits>
[[nodiscard]] MR_BIND_IGNORE constexpr FastInt<nBits + mBits> operator *( const FastInt<nBits> & a, const FastInt<mBits> & b ) noexcept
{
    FastInt<nBits + mBits> res;
    res.w = detail::mulWords( a.w, b.w );
    return res;
}
 
template <int nBits, typename T>
requires detail::cFitsFastInt128<T>
[[nodiscard]] MR_BIND_IGNORE constexpr FastInt<nBits + detail::cMulBits<T>> operator *( const FastInt<nBits> & a, T b ) noexcept
{
    FastInt<nBits + detail::cMulBits<T>> res;
    res.w = detail::mulWords( a.w, detail::mulWordsOf( b ) );
    return res;
}
 
template <int nBits, typename T>
requires detail::cFitsFastInt128<T>
[[nodiscard]] MR_BIND_IGNORE constexpr FastInt<nBits + detail::cMulBits<T>> operator *( T a, const FastInt<nBits> & b ) noexcept
{
    return b * a;
}

class MR_BIND_IGNORE Int128Mul256
{
public:
    Int128Mul256() noexcept = default;
 
    template <typename T>
    requires detail::cFitsFastInt128<T>
    constexpr Int128Mul256( T v ) noexcept : v_( v ) { }
 
    [[nodiscard]] constexpr explicit operator FastInt128() const noexcept { return v_; }
 
    [[nodiscard]] friend constexpr FastInt128 operator +( Int128Mul256 a ) noexcept { return a.v_; }
    [[nodiscard]] friend constexpr FastInt128 operator -( Int128Mul256 a ) noexcept { return -a.v_; }
 
    [[nodiscard]] friend constexpr FastInt128 operator +( Int128Mul256 a, Int128Mul256 b ) noexcept { return a.v_ + b.v_; }
    [[nodiscard]] friend constexpr FastInt128 operator -( Int128Mul256 a, Int128Mul256 b ) noexcept { return a.v_ - b.v_; }
    [[nodiscard]] friend constexpr FastInt128 operator /( Int128Mul256 a, Int128Mul256 b ) noexcept { return a.v_ / b.v_; }
 
    [[nodiscard]] friend constexpr FastInt256 operator *( Int128Mul256 a, Int128Mul256 b ) noexcept
    {
        const FastUInt128 ua( a.v_ ), ub( b.v_ );
        FastInt256 res;
        res.w = detail::mulWords( std::array{ std::uint64_t( ua ), std::uint64_t( ua >> 64 ) },
                                  std::array{ std::uint64_t( ub ), std::uint64_t( ub >> 64 ) } );
        return res;
    }
 
    [[nodiscard]] friend constexpr bool operator ==( Int128Mul256 a, Int128Mul256 b ) noexcept { return a.v_ == b.v_; }
    [[nodiscard]] friend constexpr auto operator <=>( Int128Mul256 a, Int128Mul256 b ) noexcept { return a.v_ <=> b.v_; }
 
private:
    FastInt128 v_;
};

#if !defined MR_PARSING_FOR_ANY_BINDINGS && !defined MR_COMPILING_ANY_BINDINGS
using Vector2i128mul = Vector2<Int128Mul256>;
using Vector3i128mul = Vector3<Int128Mul256>;
#endif

 
}