A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
int64x64-128.cc
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#include "int64x64-128.h"
8
9#include "abort.h"
10#include "assert.h"
11#include "log.h"
12
13#if defined(INT64X64_USE_128) && !defined(PYTHON_SCAN)
14
15/**
16 * @file
17 * @ingroup highprec
18 * Implementation of the ns3::int64x64_t type using a native int128_t type.
19 */
20
21namespace ns3
22{
23
24// Note: Logging in this file is largely avoided due to the
25// number of calls that are made to these functions and the possibility
26// of causing recursions leading to stack overflow
27NS_LOG_COMPONENT_DEFINE("int64x64-128");
28
29/**
30 * @ingroup highprec
31 * Compute the sign of the result of multiplying or dividing
32 * Q64.64 fixed precision operands.
33 *
34 * @param [in] sa The signed value of the first operand.
35 * @param [in] sb The signed value of the second operand.
36 * @param [out] ua The unsigned magnitude of the first operand.
37 * @param [out] ub The unsigned magnitude of the second operand.
38 * @returns \c true if the result will be negative.
39 */
40static inline bool
41output_sign(const int128_t sa, const int128_t sb, uint128_t& ua, uint128_t& ub)
42{
43 bool negA = sa < 0;
44 bool negB = sb < 0;
45 ua = negA ? -static_cast<uint128_t>(sa) : sa;
46 ub = negB ? -static_cast<uint128_t>(sb) : sb;
47 return negA != negB;
48}
49
50void
52{
53 uint128_t a;
54 uint128_t b;
55 bool negative = output_sign(_v, o._v, a, b);
56 uint128_t result = Umul(a, b);
57 if (negative)
58 {
59 NS_ASSERT_MSG(result <= HP128_MASK_HI_BIT, "overflow detected");
60 _v = -result;
61 }
62 else
63 {
64 NS_ASSERT_MSG(result < HP128_MASK_HI_BIT, "overflow detected");
65 _v = result;
66 }
67}
68
71{
72 uint128_t al = a & HP_MASK_LO;
73 uint128_t bl = b & HP_MASK_LO;
74 uint128_t ah = a >> 64;
75 uint128_t bh = b >> 64;
76
77 // Let Q(x) be the unsigned Q64.64 fixed point value represented by the uint128_t x:
78 // Q(x) * 2^64 = x = xh * 2^64 + xl.
79 // (Defining x this way avoids ambiguity about the meaning of the division operators in
80 // Q(x) = x / 2^64 = xh + xl / 2^64.)
81 // Then
82 // Q(a) = ah + al / 2^64
83 // and
84 // Q(b) = bh + bl / 2^64.
85 // We need to find uint128_t c such that
86 // Q(c) = Q(a) * Q(b).
87 // Then
88 // c = Q(c) * 2^64
89 // = (ah + al / 2^64) * (bh + bl / 2^64) * 2^64
90 // = (ah * 2^64 + al) * (bh * 2^64 + bl) / 2^64
91 // = ah * bh * 2^64 + (ah * bl + al * bh) + al * bl / 2^64.
92 // We compute the last part of c by (al * bl) >> 64 which truncates (instead of rounds)
93 // the LSB. If c exceeds 2^127, we might assert. This is because our caller
94 // (Mul function) will not be able to represent the result.
95
96 uint128_t res = (al * bl) >> 64;
97 {
98 // ah, bh <= 2^63 and al, bl <= 2^64 - 1, so mid < 2^128 - 2^64 and there is no
99 // integer overflow.
100 uint128_t mid = ah * bl + al * bh;
101 // res < 2^64, so there is no integer overflow.
102 res += mid;
103 }
104 {
105 uint128_t high = ah * bh;
106 // If high > 2^63, then the result will overflow.
107 NS_ASSERT_MSG(high <= (static_cast<uint128_t>(1) << 63), "overflow detected");
108 high <<= 64;
109 NS_ASSERT_MSG(res + high >= res, "overflow detected");
110 // No overflow since res, high <= 2^127 and one of res, high is < 2^127.
111 res += high;
112 }
113
114 return res;
115}
116
117void
119{
120 uint128_t a;
121 uint128_t b;
122 bool negative = output_sign(_v, o._v, a, b);
123 int128_t result = Udiv(a, b);
124 _v = negative ? -result : result;
125}
126
129{
130 uint128_t rem = a;
131 uint128_t den = b;
132 uint128_t quo = rem / den;
133 rem = rem % den;
134 uint128_t result = quo;
135
136 // Now, manage the remainder
137 const uint64_t DIGITS = 64; // Number of fraction digits (bits) we need
138 const uint128_t ZERO = 0;
139
140 NS_ASSERT_MSG(rem < den, "Remainder not less than divisor");
141
142 uint64_t digis = 0; // Number of digits we have already
143 uint64_t shift = 0; // Number we are going to get this round
144
145 // Skip trailing zeros in divisor
146 while ((shift < DIGITS) && !(den & 0x1))
147 {
148 ++shift;
149 den >>= 1;
150 }
151
152 while ((digis < DIGITS) && (rem != ZERO))
153 {
154 // Skip leading zeros in remainder
155 while ((digis + shift < DIGITS) && !(rem & HP128_MASK_HI_BIT))
156 {
157 ++shift;
158 rem <<= 1;
159 }
160
161 // Cast off denominator bits if:
162 // Need more digits and
163 // LSB is zero or
164 // rem < den
165 while ((digis + shift < DIGITS) && (!(den & 0x1) || (rem < den)))
166 {
167 ++shift;
168 den >>= 1;
169 }
170
171 // Do the division
172 quo = rem / den;
173 rem = rem % den;
174
175 // Add in the quotient as shift bits of the fraction
176 result <<= shift;
177 result += quo;
178
179 digis += shift;
180 shift = 0;
181 }
182 // Did we run out of remainder?
183 if (digis < DIGITS)
184 {
185 shift = DIGITS - digis;
186 result <<= shift;
187 }
188
189 return result;
190}
191
192void
194{
195 bool negResult = _v < 0;
196 uint128_t a = negResult ? -static_cast<uint128_t>(_v) : _v;
197 uint128_t result = UmulByInvert(a, o._v);
198
199 _v = negResult ? -result : result;
200}
201
204{
205 // Since b is assumed to be the output of Invert(), b <= 2^127.
207
208 uint128_t al = a & HP_MASK_LO;
209 uint128_t bl = b & HP_MASK_LO;
210 uint128_t ah = a >> 64;
211 uint128_t bh = b >> 64;
212
213 // Since ah, bh <= 2^63, high <= 2^126 and there is no overflow.
214 uint128_t high = ah * bh;
215
216 // Since ah, bh <= 2^63 and al, bl < 2^64, mid < 2^128 and there is
217 // no overflow.
218 uint128_t mid = ah * bl + al * bh;
219 mid >>= 64;
220
221 // Since high <= 2^126 and mid < 2^64, result < 2^127 and there is no overflow.
222 uint128_t result = high + mid;
223
224 return result;
225}
226
228int64x64_t::Invert(const uint64_t v)
229{
230 NS_ASSERT(v > 1);
231 uint128_t a;
232 a = 1;
233 a <<= 64;
234 int64x64_t result;
235 result._v = Udiv(a, v);
236 int64x64_t tmp(v, 0);
237 tmp.MulByInvert(result);
238 if (tmp.GetHigh() != 1)
239 {
240 result._v += 1;
241 }
242 return result;
243}
244
245} // namespace ns3
246
247#endif /* INT64X64_128_H */
NS_ABORT_x macro definitions.
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
High precision numerical type, implementing Q64.64 fixed precision.
int64_t GetHigh() const
Get the integer portion.
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).
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...
static uint128_t UmulByInvert(const uint128_t a, const uint128_t b)
Unsigned multiplication of Q64.64 and Q0.128 values.
int128_t _v
The Q64.64 value.
void Div(const int64x64_t &o)
Implement /=.
static int64x64_t Invert(const uint64_t v)
Compute the inverse of an integer value.
static uint128_t Umul(const uint128_t a, const uint128_t b)
Unsigned multiplication of Q64.64 values.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition assert.h:55
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition assert.h:75
__uint128_t uint128_t
Use uint128_t for int64x64_t implementation.
__int128_t int128_t
Use uint128_t for int64x64_t implementation.
static bool output_sign(const int128_t sa, const int128_t sb, uint128_t &ua, uint128_t &ub)
Compute the sign of the result of multiplying or dividing Q64.64 fixed precision operands.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
Declaration of the ns3::int64x64_t type using a native int128_t type.
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.