12 |
12 |
13 |
13 |
14 namespace ns3 { |
14 namespace ns3 { |
15 |
15 |
16 /** |
16 /** |
17 * \ingroup core |
17 * \internal |
18 * \defgroup highprec High Precision Q64.64 |
18 * The implementation documented here is based on native 128-bit integers. |
19 * |
|
20 * Functions and class for high precision Q64.64 fixed point arithmetic. |
|
21 */ |
|
22 |
|
23 /** |
|
24 * \ingroup highprec |
|
25 * High precision numerical type, implementing Q64.64 fixed precision. |
|
26 * |
|
27 * A Q64.64 fixed precision number consists of: |
|
28 * |
|
29 * Bits | Function |
|
30 * ---- | -------- |
|
31 * 1 | Sign bit |
|
32 * 63 | Integer portion |
|
33 * 64 | Fractional portion |
|
34 * |
|
35 * All standard arithemetic operations are supported: |
|
36 * |
|
37 * Category | Operators |
|
38 * ----------- | --------- |
|
39 * Computation | `+`, `+=`, `-`, `-=`, `*`, `*=`, `/`, `/=` |
|
40 * Comparison | `==`, `!=`, `<`, `<=`, `>`, `>=` |
|
41 * Unary | `+`, `-`, `!` |
|
42 * |
|
43 */ |
19 */ |
44 class int64x64_t |
20 class int64x64_t |
45 { |
21 { |
46 /// uint128_t high bit (sign bit) |
22 /// uint128_t high bit (sign bit) |
47 static const uint128_t HP128_MASK_HI_BIT = (((int128_t)1)<<127); |
23 static const uint128_t HP128_MASK_HI_BIT = (((int128_t)1)<<127); |
70 * A few testcases are are sensitive to implementation, |
46 * A few testcases are are sensitive to implementation, |
71 * specifically the double implementation. To handle this, |
47 * specifically the double implementation. To handle this, |
72 * we expose the underlying implementation type here. |
48 * we expose the underlying implementation type here. |
73 */ |
49 */ |
74 enum impl_type { |
50 enum impl_type { |
75 int128_impl = 0, //!< Native int128_t implementation. |
51 int128_impl, //!< Native int128_t implementation. |
76 cairo_impl = 1, //!< cairo wideint implementation |
52 cairo_impl, //!< cairo wideint implementation |
77 ld_impl = 2 //!< long double implementation |
53 ld_impl, //!< long double implementation |
78 }; |
54 }; |
79 |
55 |
80 /// Type tag for this implementation. |
56 /// Type tag for this implementation. |
81 static const enum impl_type implementation = int128_impl; |
57 static const enum impl_type implementation = int128_impl; |
82 |
58 |
87 /** |
63 /** |
88 * Construct from a floating point value. |
64 * Construct from a floating point value. |
89 * |
65 * |
90 * \param [in] value floating value to represent |
66 * \param [in] value floating value to represent |
91 */ |
67 */ |
92 inline int64x64_t (double value) |
68 inline int64x64_t (const double value) |
93 { |
69 { |
94 bool sign = value < 0; |
70 const int64x64_t tmp ((long double)value); |
95 value = sign ? -value : value; |
71 _v = tmp._v; |
96 long double hi = std::floor ((long double)value); |
72 } |
97 long double fr = value - hi; |
73 inline int64x64_t (const long double value) |
98 long double lo = fr * HP_MAX_64; |
74 { |
99 _v = (uint128_t)hi << 64; |
75 const bool negative = value < 0; |
100 _v += (uint128_t)lo; |
76 const long double v = negative ? -value : value; |
101 _v = sign ? -_v : _v; |
77 |
102 } |
78 long double fhi; |
103 inline int64x64_t (long double value) |
79 long double flo = std::modf (v, &fhi); |
104 { |
80 // Add 0.5 to round, which improves the last count |
105 bool sign = value < 0; |
81 // This breaks these tests: |
106 value = sign ? -value : value; |
82 // TestSuite devices-mesh-dot11s-regression |
107 long double hi = std::floor (value); |
83 // TestSuite devices-mesh-flame-regression |
108 long double fr = value - hi; |
84 // TestSuite routing-aodv-regression |
109 long double lo = fr * HP_MAX_64; |
85 // TestSuite routing-olsr-regression |
110 _v = (uint128_t)hi << 64; |
86 // Setting round = 0; breaks: |
111 _v += (uint128_t)lo; |
87 // TestSuite int64x64 |
112 _v = sign ? -_v : _v; |
88 const long double round = 0.5; |
|
89 flo = flo * HP_MAX_64 + round; |
|
90 int128_t hi = fhi; |
|
91 const uint64_t lo = flo; |
|
92 if (flo >= HP_MAX_64) |
|
93 { |
|
94 // conversion to uint64 rolled over |
|
95 ++hi; |
|
96 } |
|
97 _v = hi << 64; |
|
98 _v |= lo; |
|
99 _v = negative ? -_v : _v; |
113 } |
100 } |
114 /**@}*/ |
101 /**@}*/ |
115 |
102 |
116 /**@{*/ |
103 /**@{*/ |
117 /** |
104 /** |
118 * Construct from an integral type. |
105 * Construct from an integral type. |
119 * |
106 * |
120 * \param [in] v integer value to represent |
107 * \param [in] v integer value to represent |
121 */ |
108 */ |
122 inline int64x64_t (int v) |
109 inline int64x64_t (const int v) |
123 : _v (v) |
110 : _v (v) |
124 { |
111 { |
125 _v <<= 64; |
112 _v <<= 64; |
126 } |
113 } |
127 inline int64x64_t (long int v) |
114 inline int64x64_t (const long int v) |
128 : _v (v) |
115 : _v (v) |
129 { |
116 { |
130 _v <<= 64; |
117 _v <<= 64; |
131 } |
118 } |
132 inline int64x64_t (long long int v) |
119 inline int64x64_t (const long long int v) |
133 : _v (v) |
120 : _v (v) |
134 { |
121 { |
135 _v <<= 64; |
122 _v <<= 64; |
136 } |
123 } |
137 inline int64x64_t (unsigned int v) |
124 inline int64x64_t (const unsigned int v) |
138 : _v (v) |
125 : _v (v) |
139 { |
126 { |
140 _v <<= 64; |
127 _v <<= 64; |
141 } |
128 } |
142 inline int64x64_t (unsigned long int v) |
129 inline int64x64_t (const unsigned long int v) |
143 : _v (v) |
130 : _v (v) |
144 { |
131 { |
145 _v <<= 64; |
132 _v <<= 64; |
146 } |
133 } |
147 inline int64x64_t (unsigned long long int v) |
134 inline int64x64_t (const unsigned long long int v) |
148 : _v (v) |
135 : _v (v) |
149 { |
136 { |
150 _v <<= 64; |
137 _v <<= 64; |
151 } |
138 } |
152 /**@}*/ |
139 /**@}*/ |
154 * Construct from explicit high and low values. |
141 * Construct from explicit high and low values. |
155 * |
142 * |
156 * \param [in] hi Integer portion. |
143 * \param [in] hi Integer portion. |
157 * \param [in] lo Fractional portion, already scaled to HP_MAX_64. |
144 * \param [in] lo Fractional portion, already scaled to HP_MAX_64. |
158 */ |
145 */ |
159 explicit inline int64x64_t (int64_t hi, uint64_t lo) |
146 explicit inline int64x64_t (const int64_t hi, const uint64_t lo) |
160 { |
147 { |
161 bool sign = hi<0; |
148 _v = (int128_t)hi << 64; |
162 _v = sign ? -hi : hi; |
149 _v |= lo; |
163 _v <<= 64; |
|
164 _v += lo; |
|
165 _v = sign ? -_v : _v; |
|
166 } |
150 } |
167 |
151 |
168 /** |
152 /** |
169 * Copy constructor. |
153 * Copy constructor. |
170 * |
154 * |
188 * |
172 * |
189 * \return This value in floating form. |
173 * \return This value in floating form. |
190 */ |
174 */ |
191 inline double GetDouble (void) const |
175 inline double GetDouble (void) const |
192 { |
176 { |
193 bool sign = _v < 0; |
177 const bool negative = _v < 0; |
194 uint128_t value = sign ? -_v : _v; |
178 const uint128_t value = negative ? -_v : _v; |
195 long double flo = (value & HP_MASK_LO) / HP_MAX_64; |
179 const long double fhi = value >> 64; |
196 long double retval = value >> 64; |
180 const long double flo = (value & HP_MASK_LO) / HP_MAX_64; |
|
181 long double retval = fhi; |
197 retval += flo; |
182 retval += flo; |
198 retval = sign ? -retval : retval; |
183 retval = negative ? -retval : retval; |
199 return retval; |
184 return retval; |
200 } |
185 } |
201 /** |
186 /** |
202 * Get the integer portion. |
187 * Get the integer portion. |
203 * |
188 * |
204 * \return The integer portion of this value. |
189 * \return The integer portion of this value. |
205 */ |
190 */ |
206 inline int64_t GetHigh (void) const |
191 inline int64_t GetHigh (void) const |
207 { |
192 { |
208 bool sign = _v < 0; |
193 const int128_t retval = _v >> 64; |
209 int128_t value = sign ? -_v : _v; |
194 return retval; |
210 value >>= 64; |
|
211 int64_t retval = value; |
|
212 return sign ? -retval : retval; |
|
213 } |
195 } |
214 /** |
196 /** |
215 * Get the fractional portion of this value, unscaled. |
197 * Get the fractional portion of this value, unscaled. |
216 * |
198 * |
217 * \return The fractional portion, unscaled, as an integer. |
199 * \return The fractional portion, unscaled, as an integer. |
218 */ |
200 */ |
219 inline uint64_t GetLow (void) const |
201 inline uint64_t GetLow (void) const |
220 { |
202 { |
221 bool sign = _v < 0; |
203 const uint128_t retval = _v & HP_MASK_LO; |
222 int128_t value = sign ? -_v : _v; |
|
223 uint128_t retval = value & HP_MASK_LO; |
|
224 return retval; |
204 return retval; |
225 } |
205 } |
226 |
206 |
227 /** |
207 /** |
228 * Multiply this value by a Q0.128 value, presumably representing an inverse, |
208 * Multiply this value by a Q0.128 value, presumably representing an inverse, |
245 * (Really this should be a separate type representing Q0.128.) |
225 * (Really this should be a separate type representing Q0.128.) |
246 * |
226 * |
247 * \param [in] v The value to compute the inverse of. |
227 * \param [in] v The value to compute the inverse of. |
248 * \return A Q0.128 representation of the inverse. |
228 * \return A Q0.128 representation of the inverse. |
249 */ |
229 */ |
250 static int64x64_t Invert (uint64_t v); |
230 static int64x64_t Invert (const uint64_t v); |
251 |
231 |
252 private: |
232 private: |
253 friend bool operator == (const int64x64_t & lhs, const int64x64_t & rhs); |
233 friend bool operator == (const int64x64_t & lhs, const int64x64_t & rhs); |
254 |
234 |
255 friend bool operator < (const int64x64_t & lhs, const int64x64_t & rhs); |
235 friend bool operator < (const int64x64_t & lhs, const int64x64_t & rhs); |
256 friend bool operator <= (const int64x64_t & lhs, const int64x64_t & rhs); |
|
257 friend bool operator > (const int64x64_t & lhs, const int64x64_t & rhs); |
236 friend bool operator > (const int64x64_t & lhs, const int64x64_t & rhs); |
258 friend bool operator >= (const int64x64_t & lhs, const int64x64_t & rhs); |
|
259 |
237 |
260 friend int64x64_t & operator += ( int64x64_t & lhs, const int64x64_t & rhs); |
238 friend int64x64_t & operator += ( int64x64_t & lhs, const int64x64_t & rhs); |
261 friend int64x64_t & operator -= ( int64x64_t & lhs, const int64x64_t & rhs); |
239 friend int64x64_t & operator -= ( int64x64_t & lhs, const int64x64_t & rhs); |
262 friend int64x64_t & operator *= ( int64x64_t & lhs, const int64x64_t & rhs); |
240 friend int64x64_t & operator *= ( int64x64_t & lhs, const int64x64_t & rhs); |
263 friend int64x64_t & operator /= ( int64x64_t & lhs, const int64x64_t & rhs); |
241 friend int64x64_t & operator /= ( int64x64_t & lhs, const int64x64_t & rhs); |
299 * the multiplication mathematically produces a Q128.128 fixed point number. |
277 * the multiplication mathematically produces a Q128.128 fixed point number. |
300 * We want the middle 128 bits from the result, truncating both the |
278 * We want the middle 128 bits from the result, truncating both the |
301 * high and low 64 bits. To achieve this, we carry out the multiplication |
279 * high and low 64 bits. To achieve this, we carry out the multiplication |
302 * explicitly with 64-bit operands and 128-bit intermediate results. |
280 * explicitly with 64-bit operands and 128-bit intermediate results. |
303 */ |
281 */ |
304 static uint128_t Umul (uint128_t a, uint128_t b); |
282 static uint128_t Umul (const uint128_t a, const uint128_t b); |
305 /** |
283 /** |
306 * Unsigned division of Q64.64 values. |
284 * Unsigned division of Q64.64 values. |
307 * |
285 * |
308 * \param [in] a Numerator. |
286 * \param [in] a Numerator. |
309 * \param [in] b Denominator. |
287 * \param [in] b Denominator. |
310 * \return The Q64.64 representation of `a / b` |
288 * \return The Q64.64 representation of `a / b` |
311 */ |
289 */ |
312 static uint128_t Udiv (uint128_t a, uint128_t b); |
290 static uint128_t Udiv (const uint128_t a, const uint128_t b); |
313 /** |
291 /** |
314 * Unsigned multiplication of Q64.64 and Q0.128 values. |
292 * Unsigned multiplication of Q64.64 and Q0.128 values. |
315 * |
293 * |
316 * \param [in] a The numerator, a Q64.64 value. |
294 * \param [in] a The numerator, a Q64.64 value. |
317 * \param [in] b The inverse of the denominator, a Q0.128 value |
295 * \param [in] b The inverse of the denominator, a Q0.128 value |
318 * \return The product `a * b`, representing the ration `a / b^-1` |
296 * \return The product `a * b`, representing the ration `a / b^-1` |
319 * |
297 * |
320 * \see Invert |
298 * \see Invert |
321 */ |
299 */ |
322 static uint128_t UmulByInvert (uint128_t a, uint128_t b); |
300 static uint128_t UmulByInvert (const uint128_t a, const uint128_t b); |
323 |
301 |
324 /** |
302 /** |
325 * Construct from an integral type. |
303 * Construct from an integral type. |
326 * |
304 * |
327 * \param [in] v integer value to represent |
305 * \param [in] v integer value to represent |
328 */ |
306 */ |
329 inline int64x64_t (int128_t v) |
307 inline int64x64_t (const int128_t v) |
330 : _v (v) {} |
308 : _v (v) {} |
331 |
309 |
332 int128_t _v; //!< The Q64.64 value. |
310 int128_t _v; //!< The Q64.64 value. |
333 |
311 |
334 }; // class int64x64_t |
312 }; // class int64x64_t |
342 { |
320 { |
343 return lhs._v == rhs._v; |
321 return lhs._v == rhs._v; |
344 } |
322 } |
345 /** |
323 /** |
346 * \ingroup highprec |
324 * \ingroup highprec |
347 * Inequality operator |
|
348 */ |
|
349 inline bool operator != (const int64x64_t & lhs, const int64x64_t & rhs) |
|
350 { |
|
351 return !(lhs == rhs); |
|
352 } |
|
353 /** |
|
354 * \ingroup highprec |
|
355 * Less than operator |
325 * Less than operator |
356 */ |
326 */ |
357 inline bool operator < (const int64x64_t & lhs, const int64x64_t & rhs) |
327 inline bool operator < (const int64x64_t & lhs, const int64x64_t & rhs) |
358 { |
328 { |
359 return lhs._v < rhs._v; |
329 return lhs._v < rhs._v; |
360 } |
330 } |
361 /** |
331 /** |
362 * \ingroup highprec |
332 * \ingroup highprec |
363 * Less or equal operator |
|
364 */ |
|
365 inline bool operator <= (const int64x64_t & lhs, const int64x64_t & rhs) |
|
366 { |
|
367 return lhs._v <= rhs._v; |
|
368 } |
|
369 /** |
|
370 * \ingroup highprec |
|
371 * Greater operator |
333 * Greater operator |
372 */ |
334 */ |
373 inline bool operator > (const int64x64_t & lhs, const int64x64_t & rhs) |
335 inline bool operator > (const int64x64_t & lhs, const int64x64_t & rhs) |
374 { |
336 { |
375 return lhs._v > rhs._v; |
337 return lhs._v > rhs._v; |
376 } |
|
377 /** |
|
378 * \ingroup highprec |
|
379 * Greater or equal operator |
|
380 */ |
|
381 inline bool operator >= (const int64x64_t & lhs, const int64x64_t & rhs) |
|
382 { |
|
383 return lhs._v >= rhs._v; |
|
384 } |
338 } |
385 |
339 |
386 /** |
340 /** |
387 * \ingroup highprec |
341 * \ingroup highprec |
388 * Compound addition operator |
342 * Compound addition operator |