A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
int64x64-128.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 */
6
7#ifndef INT64X64_128_H
8#define INT64X64_128_H
9
10#include "ns3/core-config.h"
11
12/**
13 * @ingroup highprec
14 * Use uint128_t for int64x64_t implementation
15 */
16#if defined(INT64X64_USE_128) && !defined(PYTHON_SCAN)
17
18#include <cmath> // pow
19#include <stdint.h>
20
21#if defined(HAVE___UINT128_T) && !defined(HAVE_UINT128_T)
22/**
23 * @ingroup highprec
24 * Some compilers do not have this defined, so we define it.
25 * @{
26 */
27typedef __uint128_t uint128_t;
28typedef __int128_t int128_t;
29/** @} */
30#endif
31
32/**
33 * @file
34 * @ingroup highprec
35 * Declaration of the ns3::int64x64_t type using a native int128_t type.
36 */
37
38namespace ns3
39{
40
41/**
42 * @internal
43 * The implementation documented here is based on native 128-bit integers.
44 */
45class int64x64_t
46{
47 /// uint128_t high bit (sign bit).
48 static const uint128_t HP128_MASK_HI_BIT = (((int128_t)1) << 127);
49 /// Mask for fraction part.
50 static const uint64_t HP_MASK_LO = 0xffffffffffffffffULL;
51
52 public:
53 /// Floating point value of HP_MASK_LO + 1.
54 static constexpr long double HP_MAX_64 = (static_cast<uint64_t>(1) << 63) * 2.0L;
55
56 /**
57 * Type tag for the underlying implementation.
58 *
59 * A few testcases are are sensitive to implementation,
60 * specifically the double implementation. To handle this,
61 * we expose the underlying implementation type here.
62 */
64 {
65 int128_impl, //!< Native \c int128_t implementation.
66 cairo_impl, //!< Cairo wideint implementation.
67 ld_impl, //!< `long double` implementation.
68 };
69
70 /// Type tag for this implementation.
72
73 /// Default constructor.
74 inline int64x64_t()
75 : _v(0)
76 {
77 }
78
79 /**
80 * @name Construct from a floating point value.
81 */
82 /**
83 * @{
84 * Constructor from a floating point.
85 *
86 * @param [in] value Floating value to represent.
87 */
88 inline int64x64_t(const double value)
89 {
90 const int64x64_t tmp((long double)value);
91 _v = tmp._v;
92 }
93
94 inline int64x64_t(const long double value)
95 {
96 const bool negative = value < 0;
97 const long double v = negative ? -value : value;
98
99 long double fhi;
100 long double flo = std::modf(v, &fhi);
101 // Add 0.5 to round, which improves the last count
102 // This breaks these tests:
103 // TestSuite devices-mesh-dot11s-regression
104 // TestSuite devices-mesh-flame-regression
105 // TestSuite routing-aodv-regression
106 // TestSuite routing-olsr-regression
107 // Setting round = 0; breaks:
108 // TestSuite int64x64
109 const long double round = 0.5;
110 flo = flo * HP_MAX_64 + round;
111 int128_t hi = fhi;
112 const uint64_t lo = flo;
113 if (flo >= HP_MAX_64)
114 {
115 // conversion to uint64 rolled over
116 ++hi;
117 }
118 _v = hi << 64;
119 _v |= lo;
120 _v = negative ? -_v : _v;
121 }
122
123 /**@}*/
124
125 /**
126 * @name Construct from an integral type.
127 */
128 /**@{*/
129 /**
130 * Construct from an integral type.
131 *
132 * @param [in] v Integer value to represent.
133 */
134 inline int64x64_t(const int v)
135 : _v(v)
136 {
137 _v <<= 64;
138 }
139
140 inline int64x64_t(const long int v)
141 : _v(v)
142 {
143 _v <<= 64;
144 }
145
146 inline int64x64_t(const long long int v)
147 : _v(v)
148 {
149 _v <<= 64;
150 }
151
152 inline int64x64_t(const unsigned int v)
153 : _v(v)
154 {
155 _v <<= 64;
156 }
157
158 inline int64x64_t(const unsigned long int v)
159 : _v(v)
160 {
161 _v <<= 64;
162 }
163
164 inline int64x64_t(const unsigned long long int v)
165 : _v(v)
166 {
167 _v <<= 64;
168 }
169
170 /**@}*/
171
172 /**
173 * Construct from explicit high and low values.
174 *
175 * @param [in] hi Integer portion.
176 * @param [in] lo Fractional portion, already scaled to HP_MAX_64.
177 */
178 explicit inline int64x64_t(const int64_t hi, const uint64_t lo)
179 {
180 _v = (int128_t)hi << 64;
181 _v |= lo;
182 }
183
184 /**
185 * Copy constructor.
186 *
187 * @param [in] o Value to copy.
188 */
189 inline int64x64_t(const int64x64_t& o)
190 : _v(o._v)
191 {
192 }
193
194 /**
195 * Assignment.
196 *
197 * @param [in] o Value to assign to this int64x64_t.
198 * @returns This int64x64_t.
199 */
201 {
202 _v = o._v;
203 return *this;
204 }
205
206 /** Explicit bool conversion. */
207 inline explicit operator bool() const
208 {
209 return (_v != 0);
210 }
211
212 /**
213 * Get this value as a double.
214 *
215 * @return This value in floating form.
216 */
217 inline double GetDouble() const
218 {
219 const bool negative = _v < 0;
220 const int128_t vTemp = _v + (_v == std::numeric_limits<int128_t>::min());
221 const uint128_t value = negative ? -vTemp : vTemp;
222 const long double fhi = value >> 64;
223 const long double flo = (value & HP_MASK_LO) / HP_MAX_64;
224 long double retval = fhi;
225 retval += flo;
226 retval = negative ? -retval : retval;
227 return retval;
228 }
229
230 /**
231 * Get the integer portion.
232 *
233 * @return The integer portion of this value.
234 */
235 inline int64_t GetHigh() const
236 {
237 const int128_t retval = _v >> 64;
238 return retval;
239 }
240
241 /**
242 * Get the fractional portion of this value, unscaled.
243 *
244 * @return The fractional portion, unscaled, as an integer.
245 */
246 inline uint64_t GetLow() const
247 {
248 const uint128_t retval = _v & HP_MASK_LO;
249 return retval;
250 }
251
252 /**
253 * Truncate to an integer.
254 * Truncation is always toward zero,
255 * @return The value truncated toward zero.
256 */
257 int64_t GetInt() const
258 {
259 const bool negative = _v < 0;
260 const uint128_t value = negative ? -_v : _v;
261 int64_t retval = value >> 64;
262 retval = negative ? -retval : retval;
263 return retval;
264 }
265
266 /**
267 * Round to the nearest int.
268 * Similar to std::round this rounds halfway cases away from zero,
269 * regardless of the current (floating) rounding mode.
270 * @return The value rounded to the nearest int.
271 */
272 int64_t Round() const
273 {
274 const bool negative = _v < 0;
275 int64x64_t value = (negative ? -(*this) : *this);
276 const int64x64_t half(0, 1LL << 63);
277 value += half;
278 int64_t retval = value.GetHigh();
279 retval = negative ? -retval : retval;
280 return retval;
281 }
282
283 /**
284 * Multiply this value by a Q0.128 value, presumably representing an inverse,
285 * completing a division operation.
286 *
287 * @param [in] o The inverse operand.
288 *
289 * @see Invert()
290 */
291 void MulByInvert(const int64x64_t& o);
292
293 /**
294 * Compute the inverse of an integer value.
295 *
296 * Ordinary division by an integer would be limited to 64 bits of precision.
297 * Instead, we multiply by the 128-bit inverse of the divisor.
298 * This function computes the inverse to 128-bit precision.
299 * MulByInvert() then completes the division.
300 *
301 * (Really this should be a separate type representing Q0.128.)
302 *
303 * @param [in] v The value to compute the inverse of.
304 * @return A Q0.128 representation of the inverse.
305 */
306 static int64x64_t Invert(const uint64_t v);
307
308 private:
309 /**
310 * @name Arithmetic Operators
311 * Arithmetic operators for int64x64_t.
312 */
313 /**
314 * @{
315 * Arithmetic operator.
316 * @param [in] lhs Left hand argument
317 * @param [in] rhs Right hand argument
318 * @return The result of the operator.
319 */
320
321 friend inline bool operator==(const int64x64_t& lhs, const int64x64_t& rhs)
322 {
323 return lhs._v == rhs._v;
324 }
325
326 friend inline bool operator<(const int64x64_t& lhs, const int64x64_t& rhs)
327 {
328 return lhs._v < rhs._v;
329 }
330
331 friend inline bool operator>(const int64x64_t& lhs, const int64x64_t& rhs)
332 {
333 return lhs._v > rhs._v;
334 }
335
336 friend inline int64x64_t& operator+=(int64x64_t& lhs, const int64x64_t& rhs)
337 {
338 lhs._v += rhs._v;
339 return lhs;
340 }
341
342 friend inline int64x64_t& operator-=(int64x64_t& lhs, const int64x64_t& rhs)
343 {
344 lhs._v -= rhs._v;
345 return lhs;
346 }
347
348 friend inline int64x64_t& operator*=(int64x64_t& lhs, const int64x64_t& rhs)
349 {
350 lhs.Mul(rhs);
351 return lhs;
352 }
353
354 friend inline int64x64_t& operator/=(int64x64_t& lhs, const int64x64_t& rhs)
355 {
356 lhs.Div(rhs);
357 return lhs;
358 }
359
360 /**@}*/
361
362 /**
363 * @name Unary Operators
364 * Unary operators for int64x64_t.
365 */
366 /**
367 * @{
368 * Unary operator.
369 * @param [in] lhs Left hand argument
370 * @return The result of the operator.
371 */
372 friend inline int64x64_t operator+(const int64x64_t& lhs)
373 {
374 return lhs;
375 }
376
377 friend inline int64x64_t operator-(const int64x64_t& lhs)
378 {
379 int64x64_t res;
380 res._v = -lhs._v;
381 return res;
382 }
383
384 friend inline int64x64_t operator!(const int64x64_t& lhs)
385 {
386 return int64x64_t(!lhs._v);
387 }
388
389 /**@}*/
390
391 /**
392 * Implement `*=`.
393 * We assert if the product cannot be encoded in int64x64_t.
394 *
395 * @param [in] o The other factor.
396 */
397 void Mul(const int64x64_t& o);
398 /**
399 * Implement `/=`.
400 *
401 * @param [in] o The divisor.
402 */
403 void Div(const int64x64_t& o);
404 /**
405 * Unsigned multiplication of Q64.64 values.
406 *
407 * Mathematically this should produce a Q128.128 value;
408 * we keep the central 128 bits, representing the Q64.64 result.
409 * We might assert if the result, in uint128_t format, exceeds 2^127.
410 *
411 * @param [in] a First factor.
412 * @param [in] b Second factor.
413 * @return The Q64.64 product.
414 *
415 * @internal
416 *
417 * It might be tempting to just use \pname{a} `*` \pname{b}
418 * and be done with it, but it's not that simple. With \pname{a}
419 * and \pname{b} as 128-bit integers, \pname{a} `*` \pname{b}
420 * mathematically produces a 256-bit result, which the computer
421 * truncates to the lowest 128 bits. In our case, where \pname{a}
422 * and \pname{b} are interpreted as Q64.64 fixed point numbers,
423 * the multiplication mathematically produces a Q128.128 fixed point number.
424 * We want the middle 128 bits from the result, truncating both the
425 * high and low 64 bits. To achieve this, we carry out the multiplication
426 * explicitly with 64-bit operands and 128-bit intermediate results.
427 */
428 static uint128_t Umul(const uint128_t a, const uint128_t b);
429 /**
430 * Unsigned division of Q64.64 values.
431 *
432 * @param [in] a Numerator.
433 * @param [in] b Denominator.
434 * @return The Q64.64 representation of `a / b`.
435 */
436 static uint128_t Udiv(const uint128_t a, const uint128_t b);
437 /**
438 * Unsigned multiplication of Q64.64 and Q0.128 values.
439 *
440 * @param [in] a The numerator, a Q64.64 value.
441 * @param [in] b The inverse of the denominator, a Q0.128 value
442 * @return The product `a * b`, representing the ration `a / b^-1`.
443 *
444 * @see Invert()
445 */
446 static uint128_t UmulByInvert(const uint128_t a, const uint128_t b);
447
448 int128_t _v; //!< The Q64.64 value.
449
450}; // class int64x64_t
451
452} // namespace ns3
453
454#endif /* defined(INT64X64_USE_128) && !defined(PYTHON_SCAN) */
455#endif /* INT64X64_128_H */
High precision numerical type, implementing Q64.64 fixed precision.
int64_t GetHigh() const
Get the integer portion.
friend bool operator==(const int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
static const uint64_t HP_MASK_LO
Mask for fraction part.
static const uint128_t HP128_MASK_HI_BIT
uint128_t high bit (sign bit).
impl_type
Type tag for the underlying implementation.
@ int128_impl
Native int128_t implementation.
@ ld_impl
long double implementation.
@ cairo_impl
Cairo wideint implementation.
friend int64x64_t & operator-=(int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
friend int64x64_t operator+(const int64x64_t &lhs)
Unary operator.
static constexpr long double HP_MAX_64
Floating point value of HP_MASK_LO + 1.
int64_t Round() const
Round to the nearest int.
void Mul(const int64x64_t &o)
Implement *=.
static uint128_t Udiv(const uint128_t a, const uint128_t b)
Unsigned division of Q64.64 values.
void MulByInvert(const int64x64_t &o)
Multiply this value by a Q0.128 value, presumably representing an inverse, completing a division oper...
friend bool operator<(const int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
int64x64_t(const long double value)
Constructor from a floating point.
static uint128_t UmulByInvert(const uint128_t a, const uint128_t b)
Unsigned multiplication of Q64.64 and Q0.128 values.
static enum impl_type implementation
Type tag for this implementation.
friend int64x64_t operator!(const int64x64_t &lhs)
Unary operator.
int128_t _v
The Q64.64 value.
friend int64x64_t & operator*=(int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
int64x64_t(const int64_t hi, const uint64_t lo)
Construct from explicit high and low values.
void Div(const int64x64_t &o)
Implement /=.
int64x64_t(const unsigned long long int v)
Construct from an integral type.
int64x64_t(const unsigned int v)
Construct from an integral type.
int64x64_t(const long int v)
Construct from an integral type.
int64x64_t(const long long int v)
Construct from an integral type.
double GetDouble() const
Get this value as a double.
friend int64x64_t & operator+=(int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
int64x64_t(const unsigned long int v)
Construct from an integral type.
int64_t GetInt() const
Truncate to an integer.
int64x64_t & operator=(const int64x64_t &o)
Assignment.
friend bool operator>(const int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
int64x64_t(const int v)
Construct from an integral type.
uint64_t GetLow() const
Get the fractional portion of this value, unscaled.
friend int64x64_t operator-(const int64x64_t &lhs)
Unary operator.
static int64x64_t Invert(const uint64_t v)
Compute the inverse of an integer value.
int64x64_t(const double value)
Constructor from a floating point.
int64x64_t(const int64x64_t &o)
Copy constructor.
friend int64x64_t & operator/=(int64x64_t &lhs, const int64x64_t &rhs)
Arithmetic operator.
int64x64_t()
Default constructor.
static uint128_t Umul(const uint128_t a, const uint128_t b)
Unsigned multiplication of Q64.64 values.
__uint128_t uint128_t
Use uint128_t for int64x64_t implementation.
__int128_t int128_t
Use uint128_t for int64x64_t implementation.
Every class exported by the ns3 library is enclosed in the ns3 namespace.