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 
5 namespace ns3 {
6 
7 #define OUTPUT_SIGN(sa,sb,ua,ub) \
8  ({ bool negA, negB; \
9  negA = sa < 0; \
10  negB = sb < 0; \
11  ua = negA ? -sa : sa; \
12  ub = negB ? -sb : sb; \
13  (negA && !negB) || (!negA && negB); })
14 
15 
16 #define MASK_LO ((((int128_t)1)<<64)-1)
17 #define MASK_HI (~MASK_LO)
18 
19 void
20 int64x64_t::Mul (int64x64_t const &o)
21 {
22  bool negResult;
23  uint128_t a, b;
24  negResult = OUTPUT_SIGN (_v, o._v, a, b);
25  int128_t result = Umul (a, b);
26  // add the sign to the result
27  result = negResult ? -result : result;
28  _v = result;
29 }
30 
31 uint128_t
32 int64x64_t::Umul (uint128_t a, uint128_t b)
33 {
34  uint128_t aL = a & MASK_LO;
35  uint128_t bL = b & MASK_LO;
36  uint128_t aH = (a >> 64) & MASK_LO;
37  uint128_t bH = (b >> 64) & MASK_LO;
38 
39  uint128_t result;
40  uint128_t hiPart,loPart,midPart;
41 
42  // Multiplying (a.h 2^64 + a.l) x (b.h 2^64 + b.l) =
43  // 2^128 a.h b.h + 2^64*(a.h b.l+b.h a.l) + a.l b.l
44  // get the low part a.l b.l
45  // multiply the fractional part
46  loPart = aL * bL;
47  // compute the middle part 2^64*(a.h b.l+b.h a.l)
48  midPart = aL * bH + aH * bL;
49  // truncate the low part
50  result = (loPart >> 64) + (midPart & MASK_LO);
51  // compute the high part 2^128 a.h b.h
52  hiPart = aH * bH;
53  // truncate the high part and only use the low part
54  result |= ((hiPart & MASK_LO) << 64) + (midPart & MASK_HI);
55  // if the high part is not zero, put a warning
56  NS_ABORT_MSG_IF ((hiPart & MASK_HI) != 0,
57  "High precision 128 bits multiplication error: multiplication overflow.");
58  return result;
59 }
60 void
61 int64x64_t::Div (int64x64_t const &o)
62 {
63  bool negResult;
64  uint128_t a, b;
65  negResult = OUTPUT_SIGN (_v, o._v, a, b);
66  int128_t result = Divu (a, b);
67  result = negResult ? -result : result;
68  _v = result;
69 }
70 
71 uint128_t
72 int64x64_t::Divu (uint128_t a, uint128_t b)
73 {
74  uint128_t quo = a / b;
75  uint128_t rem = (a % b);
76  uint128_t result = quo << 64;
77  // Now, manage the remainder
78  uint128_t tmp = rem >> 64;
79  uint128_t div;
80  if (tmp == 0)
81  {
82  rem = rem << 64;
83  div = b;
84  }
85  else
86  {
87  div = b >> 64;
88  }
89  quo = rem / div;
90  result = result + quo;
91  return result;
92 }
93 
94 void
95 int64x64_t::MulByInvert (const int64x64_t &o)
96 {
97  bool negResult = _v < 0;
98  uint128_t a = negResult ? -_v : _v;
99  uint128_t result = UmulByInvert (a, o._v);
100 
101  _v = negResult ? -result : result;
102 }
103 uint128_t
104 int64x64_t::UmulByInvert (uint128_t a, uint128_t b)
105 {
106  uint128_t result, ah, bh, al, bl;
107  uint128_t hi, mid;
108  ah = a >> 64;
109  bh = b >> 64;
110  al = a & MASK_LO;
111  bl = b & MASK_LO;
112  hi = ah * bh;
113  mid = ah * bl + al * bh;
114  mid >>= 64;
115  result = hi + mid;
116  return result;
117 }
118 int64x64_t
119 int64x64_t::Invert (uint64_t v)
120 {
121  NS_ASSERT (v > 1);
122  uint128_t a;
123  a = 1;
124  a <<= 64;
125  int64x64_t result;
126  result._v = Divu (a, v);
127  int64x64_t tmp = int64x64_t (v, false);
128  tmp.MulByInvert (result);
129  if (tmp.GetHigh () != 1)
130  {
131  result._v += 1;
132  }
133  return result;
134 }
135 
136 } // namespace ns3
137