A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
int64x64-128.cc
Go to the documentation of this file.
1 #include "int64x64-128.h"
2 #include "abort.h"
3 #include "assert.h"
4 #include "log.h"
5 
6 // Note: Logging in this file is largely avoided due to the
7 // number of calls that are made to these functions and the possibility
8 // of causing recursions leading to stack overflow
9 
10 NS_LOG_COMPONENT_DEFINE ("int64x64-128");
11 
12 namespace ns3 {
13 
14 #define OUTPUT_SIGN(sa,sb,ua,ub) \
15  ({ bool negA, negB; \
16  negA = sa < 0; \
17  negB = sb < 0; \
18  ua = negA ? -sa : sa; \
19  ub = negB ? -sb : sb; \
20  (negA && !negB) || (!negA && negB); })
21 
22 
23 #define MASK_LO ((((int128_t)1)<<64)-1)
24 #define MASK_HI (~MASK_LO)
25 
26 void
27 int64x64_t::Mul (int64x64_t const &o)
28 {
29  bool negResult;
30  uint128_t a, b;
31  negResult = OUTPUT_SIGN (_v, o._v, a, b);
32  int128_t result = Umul (a, b);
33  // add the sign to the result
34  result = negResult ? -result : result;
35  _v = result;
36 }
37 
38 uint128_t
39 int64x64_t::Umul (uint128_t a, uint128_t b)
40 {
41  uint128_t aL = a & MASK_LO;
42  uint128_t bL = b & MASK_LO;
43  uint128_t aH = (a >> 64) & MASK_LO;
44  uint128_t bH = (b >> 64) & MASK_LO;
45 
46  uint128_t result;
47  uint128_t hiPart,loPart,midPart;
48 
49  // Multiplying (a.h 2^64 + a.l) x (b.h 2^64 + b.l) =
50  // 2^128 a.h b.h + 2^64*(a.h b.l+b.h a.l) + a.l b.l
51  // get the low part a.l b.l
52  // multiply the fractional part
53  loPart = aL * bL;
54  // compute the middle part 2^64*(a.h b.l+b.h a.l)
55  midPart = aL * bH + aH * bL;
56  // truncate the low part
57  result = (loPart >> 64) + (midPart & MASK_LO);
58  // compute the high part 2^128 a.h b.h
59  hiPart = aH * bH;
60  // truncate the high part and only use the low part
61  result |= ((hiPart & MASK_LO) << 64) + (midPart & MASK_HI);
62  // if the high part is not zero, put a warning
63  NS_ABORT_MSG_IF ((hiPart & MASK_HI) != 0,
64  "High precision 128 bits multiplication error: multiplication overflow.");
65  return result;
66 }
67 void
68 int64x64_t::Div (int64x64_t const &o)
69 {
70  bool negResult;
71  uint128_t a, b;
72  negResult = OUTPUT_SIGN (_v, o._v, a, b);
73  int128_t result = Divu (a, b);
74  result = negResult ? -result : result;
75  _v = result;
76 }
77 
78 uint128_t
79 int64x64_t::Divu (uint128_t a, uint128_t b)
80 {
81  uint128_t quo = a / b;
82  uint128_t rem = (a % b);
83  uint128_t result = quo << 64;
84  // Now, manage the remainder
85  uint128_t tmp = rem >> 64;
86  uint128_t div;
87  if (tmp == 0)
88  {
89  rem = rem << 64;
90  div = b;
91  }
92  else
93  {
94  div = b >> 64;
95  }
96  quo = rem / div;
97  result = result + quo;
98  return result;
99 }
100 
101 void
102 int64x64_t::MulByInvert (const int64x64_t &o)
103 {
104  bool negResult = _v < 0;
105  uint128_t a = negResult ? -_v : _v;
106  uint128_t result = UmulByInvert (a, o._v);
107 
108  _v = negResult ? -result : result;
109 }
110 uint128_t
111 int64x64_t::UmulByInvert (uint128_t a, uint128_t b)
112 {
113  uint128_t result, ah, bh, al, bl;
114  uint128_t hi, mid;
115  ah = a >> 64;
116  bh = b >> 64;
117  al = a & MASK_LO;
118  bl = b & MASK_LO;
119  hi = ah * bh;
120  mid = ah * bl + al * bh;
121  mid >>= 64;
122  result = hi + mid;
123  return result;
124 }
125 int64x64_t
126 int64x64_t::Invert (uint64_t v)
127 {
128  NS_ASSERT (v > 1);
129  uint128_t a;
130  a = 1;
131  a <<= 64;
132  int64x64_t result;
133  result._v = Divu (a, v);
134  int64x64_t tmp = int64x64_t (v, false);
135  tmp.MulByInvert (result);
136  if (tmp.GetHigh () != 1)
137  {
138  result._v += 1;
139  }
140  return result;
141 }
142 
143 } // namespace ns3
144 
#define OUTPUT_SIGN(sa, sb, ua, ub)
Definition: int64x64-128.cc:14
#define MASK_LO
Definition: int64x64-128.cc:23
#define NS_ASSERT(condition)
Definition: assert.h:64
NS_LOG_COMPONENT_DEFINE("int64x64-128")
#define MASK_HI
Definition: int64x64-128.cc:24
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if cond is true.
Definition: abort.h:98