/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * Copyright (c) 2010 INRIA

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License version 2 as

 * published by the Free Software Foundation;

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 */

#include "ns3/core-config.h"

#if !defined(INT64X64_128_H) && defined (INT64X64_USE_128) && !defined(PYTHON_SCAN)

#define INT64X64_128_H

#include <stdint.h>

#include <cmath>  // pow

#if defined(HAVE___UINT128_T) && !defined(HAVE_UINT128_T)

typedef __uint128_t uint128_t;

typedef __int128_t int128_t;

#endif

namespace ns3 {

/**

 * \internal

 * The implementation documented here is based on native 128-bit integers.

 */

class int64x64_t

{

  /// uint128_t high bit (sign bit).

  static const uint128_t   HP128_MASK_HI_BIT = (((int128_t)1)<<127);

  /// Mask for fraction part.

  static const uint64_t    HP_MASK_LO = 0xffffffffffffffffULL;

  /// Mask for sign + integer part.

  static const uint64_t    HP_MASK_HI = ~HP_MASK_LO;

  /**

   * Floating point value of HP_MASK_LO + 1.

   * We really want:

   * \code

   *   static const long double HP_MAX_64 = std:pow (2.0L, 64);

   * \endcode

   * but we can't call functions in const definitions.

   *

   * We could make this a static and initialize in int64x64-128.cc or

   * int64x64.cc, but this requires handling static initialization order

   * when most of the implementation is inline.  Instead, we resort to

   * this define.

   */

#define HP_MAX_64    (std::pow (2.0L, 64))

public:

  /**

   * Type tag for the underlying implementation.

   *

   * A few testcases are are sensitive to implementation,

   * specifically the double implementation.  To handle this,

   * we expose the underlying implementation type here.

   */

  enum impl_type {

    int128_impl,  //!< Native \c int128_t implementation.

    cairo_impl,   //!< Cairo wideint implementation.

    ld_impl,      //!< `long double` implementation.

  };

  /// Type tag for this implementation.

  static const enum impl_type implementation = int128_impl;

  /// Default constructor.

  inline int64x64_t ()

    : _v (0)  {}

  /**

   *

   * \param [in] value Floating value to represent.

   */

  inline int64x64_t (const double value)

  {

    const int64x64_t tmp ((long double)value);

    _v = tmp._v;

  }

  inline int64x64_t (const long double value)

  {

    const bool negative = value < 0;

    const long double v = negative ? -value : value;

    long double fhi;

    long double flo = std::modf (v, &fhi);

    // Add 0.5 to round, which improves the last count

    // This breaks these tests:

    //   TestSuite devices-mesh-dot11s-regression

    //   TestSuite devices-mesh-flame-regression

    //   TestSuite routing-aodv-regression

    //   TestSuite routing-olsr-regression

    // Setting round = 0; breaks:

    //   TestSuite int64x64

    const long double round = 0.5;

    flo = flo * HP_MAX_64 + round;

    int128_t hi = fhi;

    const uint64_t lo = flo;

    if (flo >= HP_MAX_64)

      {

	// conversion to uint64 rolled over

	++hi;

      }

    _v = hi << 64;

    _v |= lo;

    _v = negative ? -_v : _v;

  }

  /**@}*/

  /**

   *

   * \param [in] v Integer value to represent.

   */

  inline int64x64_t (const int v)

    : _v (v)

  {

    _v <<= 64;

  }

  inline int64x64_t (const long int v)

    : _v (v) 

  {

    _v <<= 64;

  }

  inline int64x64_t (const long long int v)

    : _v (v) 

  {

    _v <<= 64;

  }

  inline int64x64_t (const unsigned int v)

    : _v (v)

  {

    _v <<= 64;

  }

  inline int64x64_t (const unsigned long int v)

    : _v (v) 

  {

    _v <<= 64;

  }

  inline int64x64_t (const unsigned long long int v)

    : _v (v) 

  {

    _v <<= 64;

  }

  /**@}*/

  /**

   * Construct from explicit high and low values.

   *

   * \param [in] hi Integer portion.

   * \param [in] lo Fractional portion, already scaled to HP_MAX_64.

   */

  explicit inline int64x64_t (const int64_t hi, const uint64_t lo)

  {

    _v = (int128_t)hi << 64;

    _v |= lo;

  }

  /**

   * Copy constructor.

   *

   * \param [in] o Value to copy.

   */

  inline int64x64_t (const int64x64_t & o)

    : _v (o._v) {}

  /**

   * Assignment.

   *

   * \param [in] o Value to assign to this int64x64_t.

   * \returns This int64x64_t.

   */

  inline int64x64_t & operator = (const int64x64_t & o)

  {

    _v = o._v;

    return *this;

  }

  /**

   * Get this value as a double.

   *

   * \return This value in floating form.

   */

  inline double GetDouble (void) const

  {

    const bool negative = _v < 0;

    const uint128_t value = negative ? -_v : _v;

    const long double fhi = value >> 64;

    const long double flo = (value & HP_MASK_LO) / HP_MAX_64;

    long double retval = fhi;

    retval += flo;

    retval = negative ? -retval : retval;

    return retval;

  }

  /**

   * Get the integer portion.

   *

   * \return The integer portion of this value.

   */

  inline int64_t GetHigh (void) const

  {

    const int128_t retval = _v >> 64;

    return retval;

  }

  /**

   * Get the fractional portion of this value, unscaled.

   *

   * \return The fractional portion, unscaled, as an integer.

   */

  inline uint64_t GetLow (void) const

  {

    const uint128_t retval = _v & HP_MASK_LO;

    return retval;

  }

  /**

   * Multiply this value by a Q0.128 value, presumably representing an inverse,

   * completing a division operation.

   *

   * \param [in] o The inverse operand.

   *

   * \see Invert()

   */

  void MulByInvert (const int64x64_t & o);

  /**

   * Compute the inverse of an integer value.

   *

   * Ordinary division by an integer would be limited to 64 bits of precsion.

   * Instead, we multiply by the 128-bit inverse of the divisor.

   * This function computes the inverse to 128-bit precision.

   * MulByInvert() then completes the division.

   *

   * (Really this should be a separate type representing Q0.128.)

   *

   * \param [in] v The value to compute the inverse of.

   * \return A Q0.128 representation of the inverse.

   */

  static int64x64_t Invert (const uint64_t v);

private:

  friend bool         operator == (const int64x64_t & lhs, const int64x64_t & rhs);

  friend bool         operator <  (const int64x64_t & lhs, const int64x64_t & rhs);

  friend bool         operator >  (const int64x64_t & lhs, const int64x64_t & rhs);

  friend int64x64_t & operator += (      int64x64_t & lhs, const int64x64_t & rhs);

  friend int64x64_t & operator -= (      int64x64_t & lhs, const int64x64_t & rhs);

  friend int64x64_t & operator *= (      int64x64_t & lhs, const int64x64_t & rhs);

  friend int64x64_t & operator /= (      int64x64_t & lhs, const int64x64_t & rhs);

  friend int64x64_t   operator -  (const int64x64_t & lhs);

  friend int64x64_t   operator !  (const int64x64_t & lhs);

  /**

   * Implement `*=`.

   *

   * \param [in] o The other factor.

   */   

  void Mul (const int64x64_t & o);

  /**

   * Implement `/=`.

   *

   * \param [in] o The divisor.

   */

  void Div (const int64x64_t & o);

  /**

   * Unsigned multiplication of Q64.64 values.

   *

   * Mathematically this should produce a Q128.128 value;

   * we keep the central 128 bits, representing the Q64.64 result.

   * We assert on integer overflow beyond the 64-bit integer portion.

   *

   * \param [in] a First factor.

   * \param [in] b Second factor.

   * \return The Q64.64 product.

   *

   * \internal

   *

   * It might be tempting to just use \pname{a} `*` \pname{b}

   * and be done with it, but it's not that simple.  With \pname{a}

   * and \pname{b} as 128-bit integers, \pname{a} `*` \pname{b}

   * mathematically produces a 256-bit result, which the computer

   * truncates to the lowest 128 bits.  In our case, where \pname{a}

   * and \pname{b} are interpreted as Q64.64 fixed point numbers,

   * the multiplication mathematically produces a Q128.128 fixed point number.

   * We want the middle 128 bits from the result, truncating both the

   * high and low 64 bits.  To achieve this, we carry out the multiplication

   * explicitly with 64-bit operands and 128-bit intermediate results.

   */

  static uint128_t Umul         (const uint128_t a, const uint128_t b);

  /**

   * Unsigned division of Q64.64 values.

   *

   * \param [in] a Numerator.

   * \param [in] b Denominator.

   * \return The Q64.64 representation of `a / b`.

   */

  static uint128_t Udiv         (const uint128_t a, const uint128_t b);

  /**

   * Unsigned multiplication of Q64.64 and Q0.128 values.

   *

   * \param [in] a The numerator, a Q64.64 value.

   * \param [in] b The inverse of the denominator, a Q0.128 value

   * \return The product `a * b`, representing the ration `a / b^-1`.

   *

   * \see Invert()

   */

  static uint128_t UmulByInvert (const uint128_t a, const uint128_t b);

  /**

   * Construct from an integral type.

   *

   * \param [in] v Integer value to represent.

   */

  inline int64x64_t (const int128_t v)

    : _v (v) {}

  int128_t _v;  //!< The Q64.64 value.

};  // class int64x64_t

/**

 * \ingroup highprec

 * Equality operator.

 */

inline bool operator == (const int64x64_t & lhs, const int64x64_t & rhs)

{

  return lhs._v == rhs._v;

}

/**

 * \ingroup highprec

 * Less than operator.

 */

inline bool operator < (const int64x64_t & lhs, const int64x64_t & rhs)

{

  return lhs._v < rhs._v;

}

/**

 * \ingroup highprec

 * Greater operator.

 */

inline bool operator > (const int64x64_t & lhs, const int64x64_t & rhs)

{

  return lhs._v > rhs._v;

}

/**

 * \ingroup highprec

 * Compound addition operator.

 */

inline int64x64_t & operator += (int64x64_t & lhs, const int64x64_t & rhs)

{

  lhs._v += rhs._v;

  return lhs;

}

/**

 * \ingroup highprec

 * Compound subtraction operator.

 */

inline int64x64_t & operator -= (int64x64_t & lhs, const int64x64_t & rhs)

{

  lhs._v -= rhs._v;

  return lhs;

}

/**

 * \ingroup highprec

 * Compound multiplication operator.

 */

inline int64x64_t & operator *= (int64x64_t & lhs, const int64x64_t & rhs)

{

  lhs.Mul (rhs);

  return lhs;

}

/**

 * \ingroup highprec

 * Compound division operator.

 */

inline int64x64_t & operator /= (int64x64_t & lhs, const int64x64_t & rhs)

{

  lhs.Div (rhs);

  return lhs;

}

/**

 * \ingroup highprec

 * Unary plus operator.

 */

inline int64x64_t operator + (const int64x64_t & lhs)

{

  return lhs;

}

/**

 * \ingroup highprec

 * Unary negation operator (change sign operator).

 */

inline int64x64_t operator - (const int64x64_t & lhs)

{

  return int64x64_t (-lhs._v);

}

/**

 * \ingroup highprec

 * Logical not operator.

 */

inline int64x64_t operator ! (const int64x64_t & lhs)

{

  return int64x64_t (!lhs._v);

}

} // namespace ns3

#endif /* INT64X64_128_H */