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