A Discrete-Event Network Simulator
API
int64x64-128.cc
Go to the documentation of this file.
1/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2010 INRIA
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 */
19
20#include "int64x64-128.h"
21#include "abort.h"
22#include "assert.h"
23#include "log.h"
24
31namespace ns3 {
32
33// Note: Logging in this file is largely avoided due to the
34// number of calls that are made to these functions and the possibility
35// of causing recursions leading to stack overflow
36NS_LOG_COMPONENT_DEFINE ("int64x64-128");
37
49static inline
50bool
51output_sign (const int128_t sa,
52 const int128_t sb,
53 uint128_t & ua,
54 uint128_t & ub)
55{
56 bool negA = sa < 0;
57 bool negB = sb < 0;
58 ua = negA ? -sa : sa;
59 ub = negB ? -sb : sb;
60 return (negA && !negB) || (!negA && negB);
61}
62
63void
65{
66 uint128_t a, b;
67 bool negative = output_sign (_v, o._v, a, b);
68 uint128_t result = Umul (a, b);
69 _v = negative ? -result : result;
70}
71
72uint128_t
73int64x64_t::Umul (const uint128_t a, const uint128_t b)
74{
75 uint128_t aL = a & HP_MASK_LO;
76 uint128_t bL = b & HP_MASK_LO;
77 uint128_t aH = (a >> 64) & HP_MASK_LO;
78 uint128_t bH = (b >> 64) & HP_MASK_LO;
79
80 uint128_t result;
81 uint128_t hiPart, loPart, midPart;
82 uint128_t res1, res2;
83
84 // Multiplying (a.h 2^64 + a.l) x (b.h 2^64 + b.l) =
85 // 2^128 a.h b.h + 2^64*(a.h b.l+b.h a.l) + a.l b.l
86 // get the low part a.l b.l
87 // multiply the fractional part
88 loPart = aL * bL;
89 // compute the middle part 2^64*(a.h b.l+b.h a.l)
90 midPart = aL * bH + aH * bL;
91 // compute the high part 2^128 a.h b.h
92 hiPart = aH * bH;
93 // if the high part is not zero, put a warning
94 NS_ABORT_MSG_IF ((hiPart & HP_MASK_HI) != 0,
95 "High precision 128 bits multiplication error: multiplication overflow.");
96
97 // Adding 64-bit terms to get 128-bit results, with carries
98 res1 = loPart >> 64;
99 res2 = midPart & HP_MASK_LO;
100 result = res1 + res2;
101
102 res1 = midPart >> 64;
103 res2 = hiPart & HP_MASK_LO;
104 res1 += res2;
105 res1 <<= 64;
106
107 result += res1;
108
109 return result;
110}
111
112void
114{
115 uint128_t a, b;
116 bool negative = output_sign (_v, o._v, a, b);
117 int128_t result = Udiv (a, b);
118 _v = negative ? -result : result;
119}
120
121uint128_t
122int64x64_t::Udiv (const uint128_t a, const uint128_t b)
123{
124
125 uint128_t rem = a;
126 uint128_t den = b;
127 uint128_t quo = rem / den;
128 rem = rem % den;
129 uint128_t result = quo;
130
131 // Now, manage the remainder
132 const uint64_t DIGITS = 64; // Number of fraction digits (bits) we need
133 const uint128_t ZERO = 0;
134
135 NS_ASSERT_MSG (rem < den,
136 "Remainder not less than divisor");
137
138 uint64_t digis = 0; // Number of digits we have already
139 uint64_t shift = 0; // Number we are going to get this round
140
141 // Skip trailing zeros in divisor
142 while ( (shift < DIGITS) && !(den & 0x1))
143 {
144 ++shift;
145 den >>= 1;
146 }
147
148 while ( (digis < DIGITS) && (rem != ZERO) )
149 {
150 // Skip leading zeros in remainder
151 while ( (digis + shift < DIGITS)
152 && !(rem & HP128_MASK_HI_BIT))
153 {
154 ++shift;
155 rem <<= 1;
156 }
157
158 // Cast off denominator bits if:
159 // Need more digits and
160 // LSB is zero or
161 // rem < den
162 while ( (digis + shift < DIGITS)
163 && ( !(den & 0x1) || (rem < den) ) )
164 {
165 ++shift;
166 den >>= 1;
167 }
168
169 // Do the division
170 quo = rem / den;
171 rem = rem % den;
172
173 // Add in the quotient as shift bits of the fraction
174 result <<= shift;
175 result += quo;
176
177 digis += shift;
178 shift = 0;
179 }
180 // Did we run out of remainder?
181 if (digis < DIGITS)
182 {
183 shift = DIGITS - digis;
184 result <<= shift;
185 }
186
187 return result;
188}
189
190void
192{
193 bool negResult = _v < 0;
194 uint128_t a = negResult ? -_v : _v;
195 uint128_t result = UmulByInvert (a, o._v);
196
197 _v = negResult ? -result : result;
198}
199
200uint128_t
201int64x64_t::UmulByInvert (const uint128_t a, const uint128_t b)
202{
203 uint128_t result, ah, bh, al, bl;
204 uint128_t hi, mid;
205 ah = a >> 64;
206 bh = b >> 64;
207 al = a & HP_MASK_LO;
208 bl = b & HP_MASK_LO;
209 hi = ah * bh;
210 mid = ah * bl + al * bh;
211 mid >>= 64;
212 result = hi + mid;
213 return result;
214}
215
217int64x64_t::Invert (const uint64_t v)
218{
219 NS_ASSERT (v > 1);
220 uint128_t a;
221 a = 1;
222 a <<= 64;
224 result._v = Udiv (a, v);
225 int64x64_t tmp = int64x64_t (v, false);
226 tmp.MulByInvert (result);
227 if (tmp.GetHigh () != 1)
228 {
229 result._v += 1;
230 }
231 return result;
232}
233
234} // namespace ns3
235
NS_ABORT_x macro definitions.
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
High precision numerical type, implementing Q64.64 fixed precision.
static const uint64_t HP_MASK_LO
Mask for fraction part.
static cairo_uint128_t Umul(const cairo_uint128_t a, const cairo_uint128_t b)
Unsigned multiplication of Q64.64 values.
Definition: int64x64-128.cc:73
static cairo_uint128_t UmulByInvert(const cairo_uint128_t a, const cairo_uint128_t b)
Unsigned multiplication of Q64.64 and Q0.128 values.
void Mul(const int64x64_t &o)
Implement *=.
Definition: int64x64-128.cc:64
void MulByInvert(const int64x64_t &o)
Multiply this value by a Q0.128 value, presumably representing an inverse, completing a division oper...
static cairo_uint128_t Udiv(const cairo_uint128_t a, const cairo_uint128_t b)
Unsigned division of Q64.64 values.
cairo_int128_t _v
The Q64.64 value.
int64_t GetHigh(void) const
Get the integer portion.
void Div(const int64x64_t &o)
Implement /=.
static int64x64_t Invert(const uint64_t v)
Compute the inverse of an integer value.
int64x64_t()
Default constructor.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:67
#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:88
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition: abort.h:108
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.
Definition: int64x64-128.cc:51
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.