Int128 Class Reference

#include <src/libslic3r/Int128.hpp>

Static Public Member Functions
static int	sign_determinant_2x2_filtered (int64_t a11, int64_t a12, int64_t a21, int64_t a22)
static int	compare_rationals_filtered (int64_t p1, int64_t q1, int64_t p2, int64_t q2)

Private Member Functions
	Int128 (int64_t lo=0)
	Int128 (const Int128 &val)
	Int128 (const int64_t &hi, const uint64_t &lo)
Int128 &	operator= (const int64_t &val)
uint64_t	lo () const
int64_t	hi () const
int	sign () const
bool	operator== (const Int128 &val) const
bool	operator!= (const Int128 &val) const
bool	operator> (const Int128 &val) const
bool	operator< (const Int128 &val) const
bool	operator>= (const Int128 &val) const
bool	operator<= (const Int128 &val) const
Int128 &	operator+= (const Int128 &rhs)
Int128	operator+ (const Int128 &rhs) const
Int128 &	operator-= (const Int128 &rhs)
Int128	operator- (const Int128 &rhs) const
Int128	operator- () const
	operator double () const

Static Private Member Functions
static Int128	multiply (int64_t lhs, int64_t rhs)
static int	sign_determinant_2x2 (int64_t a11, int64_t a12, int64_t a21, int64_t a22)
static int	compare_rationals (int64_t p1, int64_t q1, int64_t p2, int64_t q2)

Private Attributes
uint64_t	m_lo
int64_t	m_hi

Detailed Description

Constructor & Destructor Documentation

Int128() [1/3]

Int128::Int128 ( int64_t  lo = 0 )

inlineprivate

: m_lo((uint64_t)lo), m_hi((lo < 0) ? -1 : 0) {}

Int128() [2/3]

Int128::Int128 ( const Int128 &  val )

inlineprivate

: m_lo(val.m_lo), m_hi(val.m_hi) {}

Int128() [3/3]

Int128::Int128 ( const int64_t &  hi, const uint64_t &  lo  )

inlineprivate

: m_lo(lo), m_hi(hi) {}

Member Function Documentation

compare_rationals()

static int Int128::compare_rationals ( int64_t  p1, int64_t  q1, int64_t  p2, int64_t  q2  )

inlinestaticprivate

  {
    int invert = ((q1 < 0) == (q2 < 0)) ? 1 : -1;
    Int128 det = Int128::multiply(p1, q2) - Int128::multiply(p2, q1);
    return det.sign() * invert;
  }

References multiply(), and sign().

Referenced by compare_rationals_filtered().

Here is the call graph for this function:

Here is the caller graph for this function:

compare_rationals_filtered()

static int Int128::compare_rationals_filtered ( int64_t  p1, int64_t  q1, int64_t  p2, int64_t  q2  )

inlinestatic

  {
    // First try to calculate the determinant over the upper 31 bits.
    // Round p1, p2, q1, q2 to 31 bits.
    int     invert = ((q1 < 0) == (q2 < 0)) ? 1 : -1;
    int64_t q1s = (q1 + (1 << 31)) >> 32;
    int64_t q2s = (q2 + (1 << 31)) >> 32;
    if (q1s != 0 && q2s != 0) {
      int64_t p1s = (p1 + (1 << 31)) >> 32;
      int64_t p2s = (p2 + (1 << 31)) >> 32;
      // Result fits 63 bits, it is an approximate of the determinant divided by 2^64.
      int64_t det = p1s * q2s - p2s * q1s;
      // Maximum absolute of the remainder of the exact determinant, divided by 2^64.
      int64_t err = ((std::abs(p1s) + std::abs(q1s) + std::abs(p2s) + std::abs(q2s)) << 1) + 1;
      assert(std::abs(det) <= err || ((det > 0) ? 1 : -1) * invert == compare_rationals(p1, q1, p2, q2));
      if (std::abs(det) > err)
        return ((det > 0) ? 1 : -1) * invert;
    }
    return sign_determinant_2x2(p1, q1, p2, q2) * invert;
  }

References compare_rationals(), and sign_determinant_2x2().

Here is the call graph for this function:

hi()

int64_t Int128::hi ( ) const

inlineprivate

{ return m_hi; }

References m_hi.

lo()

uint64_t Int128::lo ( ) const

inlineprivate

{ return m_lo; }

References m_lo.

multiply()

static Int128 Int128::multiply ( int64_t  lhs, int64_t  rhs  )

inlinestaticprivate

  {
#if defined(_MSC_VER) && defined(_WIN64)
    // On Visual Studio 64bit, use the _mul128() intrinsic function.
    Int128 result;
      result.m_lo = (uint64_t)_mul128(lhs, rhs, &result.m_hi);
      return result;
#else
      // This branch should only be executed in case there is neither __int16 type nor _mul128 intrinsic
      // function available. This is mostly on 32bit operating systems.
      // Use a pure C implementation of _mul128().
 
    int negate = (lhs < 0) != (rhs < 0);
 
    if (lhs < 0)
      lhs = -lhs;
    uint64_t int1Hi = uint64_t(lhs) >> 32;
    uint64_t int1Lo = uint64_t(lhs & 0xFFFFFFFF);
 
    if (rhs < 0)
      rhs = -rhs;
    uint64_t int2Hi = uint64_t(rhs) >> 32;
    uint64_t int2Lo = uint64_t(rhs & 0xFFFFFFFF);
 
    //because the high (sign) bits in both int1Hi & int2Hi have been zeroed,
    //there's no risk of 64 bit overflow in the following assignment
    //(ie: $7FFFFFFF*$FFFFFFFF + $7FFFFFFF*$FFFFFFFF < 64bits)
    uint64_t a = int1Hi * int2Hi;
    uint64_t b = int1Lo * int2Lo;
    //Result = A shl 64 + C shl 32 + B ...
    uint64_t c = int1Hi * int2Lo + int1Lo * int2Hi;
 
    Int128 tmp;
    tmp.m_hi = int64_t(a + (c >> 32));
    tmp.m_lo = int64_t(c << 32);
    tmp.m_lo += int64_t(b);
    if (tmp.m_lo < b) 
      ++ tmp.m_hi;
    if (negate) 
      tmp = - tmp;
    return tmp;
#endif
  }

References m_hi, and m_lo.

Referenced by compare_rationals(), and sign_determinant_2x2().

Here is the caller graph for this function:

operator double()

Int128::operator double ( ) const

inlineprivate

  {
    const double shift64 = 18446744073709551616.0; //2^64
    return (m_hi < 0) ?
    ((m_lo == 0) ? 
    (double)m_hi * shift64 :
    -(double)(~m_lo + ~m_hi * shift64)) :
    (double)(m_lo + m_hi * shift64);
  }

References m_hi, and m_lo.

operator!=()

bool Int128::operator!= ( const Int128 &  val ) const

inlineprivate

{ return ! (*this == val); }

operator+()

Int128 Int128::operator+ ( const Int128 &  rhs ) const

inlineprivate

  {
    Int128 result(*this);
    result+= rhs;
    return result;
  }

operator+=()

Int128 & Int128::operator+= ( const Int128 &  rhs )

inlineprivate

  {
    m_hi += rhs.m_hi;
    m_lo += rhs.m_lo;
    if (m_lo < rhs.m_lo) m_hi++;
    return *this;
  }

References m_hi, and m_lo.

operator-() [1/2]

Int128 Int128::operator- ( ) const

inlineprivate

{ return (m_lo == 0) ? Int128(-m_hi, 0) : Int128(~m_hi, ~m_lo + 1); }

References m_hi, and m_lo.

operator-() [2/2]

Int128 Int128::operator- ( const Int128 &  rhs ) const

inlineprivate

  {
    Int128 result(*this);
    result -= rhs;
    return result;
  }

operator-=()

Int128 & Int128::operator-= ( const Int128 &  rhs )

inlineprivate

  {
    *this += -rhs;
    return *this;
  }

operator<()

bool Int128::operator< ( const Int128 &  val ) const

inlineprivate

{ return (m_hi == val.m_hi) ? m_lo < val.m_lo : m_hi < val.m_hi; }

References m_hi, and m_lo.

operator<=()

bool Int128::operator<= ( const Int128 &  val ) const

inlineprivate

{ return ! (*this > val); }

operator=()

Int128 & Int128::operator= ( const int64_t &  val )

inlineprivate

  {
    m_lo = (uint64_t)val;
    m_hi = (val < 0) ? -1 : 0;
    return *this;
  }

References m_hi, and m_lo.

operator==()

bool Int128::operator== ( const Int128 &  val ) const

inlineprivate

{ return m_hi == val.m_hi && m_lo == val.m_lo; }

References m_hi, and m_lo.

operator>()

bool Int128::operator> ( const Int128 &  val ) const

inlineprivate

{ return (m_hi == val.m_hi) ? m_lo > val.m_lo : m_hi > val.m_hi; }

References m_hi, and m_lo.

operator>=()

bool Int128::operator>= ( const Int128 &  val ) const

inlineprivate

{ return ! (*this < val); }

sign()

int Int128::sign ( ) const

inlineprivate

{ return (m_hi == 0) ? (m_lo > 0) : (m_hi > 0) - (m_hi < 0); }

References m_hi, and m_lo.

Referenced by compare_rationals().

Here is the caller graph for this function:

sign_determinant_2x2()

static int Int128::sign_determinant_2x2 ( int64_t  a11, int64_t  a12, int64_t  a21, int64_t  a22  )

inlinestaticprivate

  {
    return (Int128::multiply(a11, a22) - Int128::multiply(a12, a21)).sign();
  }

References multiply().

Referenced by compare_rationals_filtered(), and sign_determinant_2x2_filtered().

Here is the call graph for this function:

Here is the caller graph for this function:

sign_determinant_2x2_filtered()

static int Int128::sign_determinant_2x2_filtered ( int64_t  a11, int64_t  a12, int64_t  a21, int64_t  a22  )

inlinestatic

  {
    // First try to calculate the determinant over the upper 31 bits.
    // Round p1, p2, q1, q2 to 31 bits.
    int64_t a11s = (a11 + (1 << 31)) >> 32;
    int64_t a12s = (a12 + (1 << 31)) >> 32;
    int64_t a21s = (a21 + (1 << 31)) >> 32;
    int64_t a22s = (a22 + (1 << 31)) >> 32;
    // Result fits 63 bits, it is an approximate of the determinant divided by 2^64.
    int64_t det  = a11s * a22s - a12s * a21s;
    // Maximum absolute of the remainder of the exact determinant, divided by 2^64.
    int64_t err  = ((std::abs(a11s) + std::abs(a12s) + std::abs(a21s) + std::abs(a22s)) << 1) + 1;
    assert(std::abs(det) <= err || ((det > 0) ? 1 : -1) == sign_determinant_2x2(a11, a12, a21, a22));
    return (std::abs(det) > err) ?
      ((det > 0) ? 1 : -1) :
      sign_determinant_2x2(a11, a12, a21, a22);
  }

References sign_determinant_2x2().

Referenced by Slic3r::int128::cross(), and Slic3r::int128::orient().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_hi

int64_t Int128::m_hi

private

Referenced by hi(), multiply(), operator double(), operator+=(), operator-(), operator<(), operator=(), operator==(), operator>(), and sign().

m_lo

uint64_t Int128::m_lo

private

Referenced by lo(), multiply(), operator double(), operator+=(), operator-(), operator<(), operator=(), operator==(), operator>(), and sign().

---

The documentation for this class was generated from the following file:

• src/libslic3r/Int128.hpp