1 | #pragma once |
2 | |
3 | #include <cmath> |
4 | #include <limits> |
5 | #include "Defines.h" |
6 | #include "Types.h" |
7 | #include <Common/NaNUtils.h> |
8 | #include <Common/UInt128.h> |
9 | |
10 | /** Preceptually-correct number comparisons. |
11 | * Example: Int8(-1) != UInt8(255) |
12 | */ |
13 | |
14 | namespace accurate |
15 | { |
16 | |
17 | using DB::UInt64; |
18 | |
19 | /** Cases: |
20 | 1) Safe conversion (in case of default C++ operators) |
21 | a) int vs any int |
22 | b) uint vs any uint |
23 | c) float vs any float |
24 | 2) int vs uint |
25 | a) sizeof(int) <= sizeof(uint). Accurate comparison with MAX_INT tresholds |
26 | b) sizeof(int) > sizeof(uint). Casting to int |
27 | 3) integral_type vs floating_type |
28 | a) sizeof(integral_type) <= 4. Comparison via casting arguments to Float64 |
29 | b) sizeof(integral_type) == 8. Accurate comparison. Consider 3 sets of intervals: |
30 | 1) interval between adjacent floats less or equal 1 |
31 | 2) interval between adjacent floats greater then 2 |
32 | 3) float is outside [MIN_INT64; MAX_INT64] |
33 | */ |
34 | |
35 | // Case 1. Is pair of floats or pair of ints or pair of uints |
36 | template <typename A, typename B> |
37 | constexpr bool is_safe_conversion = (std::is_floating_point_v<A> && std::is_floating_point_v<B>) |
38 | || (is_integral_v<A> && is_integral_v<B> && !(is_signed_v<A> ^ is_signed_v<B>)) |
39 | || (std::is_same_v<A, DB::Int128> && std::is_same_v<B, DB::Int128>) |
40 | || (is_integral_v<A> && std::is_same_v<B, DB::Int128>) |
41 | || (std::is_same_v<A, DB::Int128> && is_integral_v<B>); |
42 | template <typename A, typename B> |
43 | using bool_if_safe_conversion = std::enable_if_t<is_safe_conversion<A, B>, bool>; |
44 | template <typename A, typename B> |
45 | using bool_if_not_safe_conversion = std::enable_if_t<!is_safe_conversion<A, B>, bool>; |
46 | |
47 | |
48 | /// Case 2. Are params IntXX and UIntYY ? |
49 | template <typename TInt, typename TUInt> |
50 | constexpr bool is_any_int_vs_uint |
51 | = is_integral_v<TInt> && is_integral_v<TUInt> && is_signed_v<TInt> && is_unsigned_v<TUInt>; |
52 | |
53 | |
54 | // Case 2a. Are params IntXX and UIntYY and sizeof(IntXX) >= sizeof(UIntYY) (in such case will use accurate compare) |
55 | template <typename TInt, typename TUInt> |
56 | constexpr bool is_le_int_vs_uint = is_any_int_vs_uint<TInt, TUInt> && (sizeof(TInt) <= sizeof(TUInt)); |
57 | |
58 | template <typename TInt, typename TUInt> |
59 | using bool_if_le_int_vs_uint_t = std::enable_if_t<is_le_int_vs_uint<TInt, TUInt>, bool>; |
60 | |
61 | template <typename TInt, typename TUInt> |
62 | inline bool_if_le_int_vs_uint_t<TInt, TUInt> greaterOpTmpl(TInt a, TUInt b) |
63 | { |
64 | return static_cast<TUInt>(a) > b && a >= 0 && b <= static_cast<TUInt>(std::numeric_limits<TInt>::max()); |
65 | } |
66 | |
67 | template <typename TUInt, typename TInt> |
68 | inline bool_if_le_int_vs_uint_t<TInt, TUInt> greaterOpTmpl(TUInt a, TInt b) |
69 | { |
70 | return a > static_cast<TUInt>(b) || b < 0 || a > static_cast<TUInt>(std::numeric_limits<TInt>::max()); |
71 | } |
72 | |
73 | template <typename TInt, typename TUInt> |
74 | inline bool_if_le_int_vs_uint_t<TInt, TUInt> equalsOpTmpl(TInt a, TUInt b) |
75 | { |
76 | return static_cast<TUInt>(a) == b && a >= 0 && b <= static_cast<TUInt>(std::numeric_limits<TInt>::max()); |
77 | } |
78 | |
79 | template <typename TUInt, typename TInt> |
80 | inline bool_if_le_int_vs_uint_t<TInt, TUInt> equalsOpTmpl(TUInt a, TInt b) |
81 | { |
82 | return a == static_cast<TUInt>(b) && b >= 0 && a <= static_cast<TUInt>(std::numeric_limits<TInt>::max()); |
83 | } |
84 | |
85 | |
86 | // Case 2b. Are params IntXX and UIntYY and sizeof(IntXX) > sizeof(UIntYY) (in such case will cast UIntYY to IntXX and compare) |
87 | template <typename TInt, typename TUInt> |
88 | constexpr bool is_gt_int_vs_uint = is_any_int_vs_uint<TInt, TUInt> && (sizeof(TInt) > sizeof(TUInt)); |
89 | |
90 | template <typename TInt, typename TUInt> |
91 | using bool_if_gt_int_vs_uint = std::enable_if_t<is_gt_int_vs_uint<TInt, TUInt>, bool>; |
92 | |
93 | template <typename TInt, typename TUInt> |
94 | inline bool_if_gt_int_vs_uint<TInt, TUInt> greaterOpTmpl(TInt a, TUInt b) |
95 | { |
96 | return static_cast<TInt>(a) > static_cast<TInt>(b); |
97 | } |
98 | |
99 | template <typename TInt, typename TUInt> |
100 | inline bool_if_gt_int_vs_uint<TInt, TUInt> greaterOpTmpl(TUInt a, TInt b) |
101 | { |
102 | return static_cast<TInt>(a) > static_cast<TInt>(b); |
103 | } |
104 | |
105 | template <typename TInt, typename TUInt> |
106 | inline bool_if_gt_int_vs_uint<TInt, TUInt> equalsOpTmpl(TInt a, TUInt b) |
107 | { |
108 | return static_cast<TInt>(a) == static_cast<TInt>(b); |
109 | } |
110 | |
111 | template <typename TInt, typename TUInt> |
112 | inline bool_if_gt_int_vs_uint<TInt, TUInt> equalsOpTmpl(TUInt a, TInt b) |
113 | { |
114 | return static_cast<TInt>(a) == static_cast<TInt>(b); |
115 | } |
116 | |
117 | |
118 | // Case 3a. Comparison via conversion to double. |
119 | template <typename TAInt, typename TAFloat> |
120 | using bool_if_double_can_be_used |
121 | = std::enable_if_t<is_integral_v<TAInt> && (sizeof(TAInt) <= 4) && std::is_floating_point_v<TAFloat>, bool>; |
122 | |
123 | template <typename TAInt, typename TAFloat> |
124 | inline bool_if_double_can_be_used<TAInt, TAFloat> greaterOpTmpl(TAInt a, TAFloat b) |
125 | { |
126 | return static_cast<double>(a) > static_cast<double>(b); |
127 | } |
128 | |
129 | template <typename TAInt, typename TAFloat> |
130 | inline bool_if_double_can_be_used<TAInt, TAFloat> greaterOpTmpl(TAFloat a, TAInt b) |
131 | { |
132 | return static_cast<double>(a) > static_cast<double>(b); |
133 | } |
134 | |
135 | template <typename TAInt, typename TAFloat> |
136 | inline bool_if_double_can_be_used<TAInt, TAFloat> equalsOpTmpl(TAInt a, TAFloat b) |
137 | { |
138 | return static_cast<double>(a) == static_cast<double>(b); |
139 | } |
140 | |
141 | template <typename TAInt, typename TAFloat> |
142 | inline bool_if_double_can_be_used<TAInt, TAFloat> equalsOpTmpl(TAFloat a, TAInt b) |
143 | { |
144 | return static_cast<double>(a) == static_cast<double>(b); |
145 | } |
146 | |
147 | /* Final realiztions */ |
148 | |
149 | |
150 | template <typename A, typename B> |
151 | inline bool_if_not_safe_conversion<A, B> greaterOp(A a, B b) |
152 | { |
153 | return greaterOpTmpl(a, b); |
154 | } |
155 | |
156 | template <typename A, typename B> |
157 | inline bool_if_safe_conversion<A, B> greaterOp(A a, B b) |
158 | { |
159 | return a > b; |
160 | } |
161 | |
162 | // Case 3b. 64-bit integers vs floats comparison. |
163 | // See hint at https://github.com/JuliaLang/julia/issues/257 (but it doesn't work properly for -2**63) |
164 | |
165 | constexpr DB::Int64 MAX_INT64_WITH_EXACT_FLOAT64_REPR = 9007199254740992LL; // 2^53 |
166 | |
167 | template <> |
168 | inline bool greaterOp<DB::Float64, DB::Int64>(DB::Float64 f, DB::Int64 i) |
169 | { |
170 | if (-MAX_INT64_WITH_EXACT_FLOAT64_REPR <= i && i <= MAX_INT64_WITH_EXACT_FLOAT64_REPR) |
171 | return f > static_cast<DB::Float64>(i); |
172 | |
173 | return (f >= static_cast<DB::Float64>(std::numeric_limits<DB::Int64>::max())) // rhs is 2**63 (not 2^63 - 1) |
174 | || (f > static_cast<DB::Float64>(std::numeric_limits<DB::Int64>::min()) && static_cast<DB::Int64>(f) > i); |
175 | } |
176 | |
177 | template <> |
178 | inline bool greaterOp<DB::Int64, DB::Float64>(DB::Int64 i, DB::Float64 f) |
179 | { |
180 | if (-MAX_INT64_WITH_EXACT_FLOAT64_REPR <= i && i <= MAX_INT64_WITH_EXACT_FLOAT64_REPR) |
181 | return f < static_cast<DB::Float64>(i); |
182 | |
183 | return (f < static_cast<DB::Float64>(std::numeric_limits<DB::Int64>::min())) |
184 | || (f < static_cast<DB::Float64>(std::numeric_limits<DB::Int64>::max()) && i > static_cast<DB::Int64>(f)); |
185 | } |
186 | |
187 | template <> |
188 | inline bool greaterOp<DB::Float64, DB::UInt64>(DB::Float64 f, DB::UInt64 u) |
189 | { |
190 | if (u <= static_cast<DB::UInt64>(MAX_INT64_WITH_EXACT_FLOAT64_REPR)) |
191 | return f > static_cast<DB::Float64>(u); |
192 | |
193 | return (f >= static_cast<DB::Float64>(std::numeric_limits<DB::UInt64>::max())) |
194 | || (f >= 0 && static_cast<DB::UInt64>(f) > u); |
195 | } |
196 | |
197 | template <> |
198 | inline bool greaterOp<DB::UInt64, DB::Float64>(DB::UInt64 u, DB::Float64 f) |
199 | { |
200 | if (u <= static_cast<DB::UInt64>(MAX_INT64_WITH_EXACT_FLOAT64_REPR)) |
201 | return static_cast<DB::Float64>(u) > f; |
202 | |
203 | return (f < 0) |
204 | || (f < static_cast<DB::Float64>(std::numeric_limits<DB::UInt64>::max()) && u > static_cast<UInt64>(f)); |
205 | } |
206 | |
207 | // Case 3b for float32 |
208 | template <> |
209 | inline bool greaterOp<DB::Float32, DB::Int64>(DB::Float32 f, DB::Int64 i) |
210 | { |
211 | return greaterOp(static_cast<DB::Float64>(f), i); |
212 | } |
213 | |
214 | template <> |
215 | inline bool greaterOp<DB::Int64, DB::Float32>(DB::Int64 i, DB::Float32 f) |
216 | { |
217 | return greaterOp(i, static_cast<DB::Float64>(f)); |
218 | } |
219 | |
220 | template <> |
221 | inline bool greaterOp<DB::Float32, DB::UInt64>(DB::Float32 f, DB::UInt64 u) |
222 | { |
223 | return greaterOp(static_cast<DB::Float64>(f), u); |
224 | } |
225 | |
226 | template <> |
227 | inline bool greaterOp<DB::UInt64, DB::Float32>(DB::UInt64 u, DB::Float32 f) |
228 | { |
229 | return greaterOp(u, static_cast<DB::Float64>(f)); |
230 | } |
231 | |
232 | template <> |
233 | inline bool greaterOp<DB::Float64, DB::UInt128>(DB::Float64 f, DB::UInt128 u) |
234 | { |
235 | return u.low == 0 && greaterOp(f, u.high); |
236 | } |
237 | |
238 | template <> |
239 | inline bool greaterOp<DB::UInt128, DB::Float64>(DB::UInt128 u, DB::Float64 f) |
240 | { |
241 | return u.low != 0 || greaterOp(u.high, f); |
242 | } |
243 | |
244 | template <> |
245 | inline bool greaterOp<DB::Float32, DB::UInt128>(DB::Float32 f, DB::UInt128 u) |
246 | { |
247 | return greaterOp(static_cast<DB::Float64>(f), u); |
248 | } |
249 | |
250 | template <> |
251 | inline bool greaterOp<DB::UInt128, DB::Float32>(DB::UInt128 u, DB::Float32 f) |
252 | { |
253 | return greaterOp(u, static_cast<DB::Float64>(f)); |
254 | } |
255 | |
256 | template <typename A, typename B> |
257 | inline bool_if_not_safe_conversion<A, B> equalsOp(A a, B b) |
258 | { |
259 | return equalsOpTmpl(a, b); |
260 | } |
261 | |
262 | template <typename A, typename B> |
263 | inline bool_if_safe_conversion<A, B> equalsOp(A a, B b) |
264 | { |
265 | using LargestType = std::conditional_t<sizeof(A) >= sizeof(B), A, B>; |
266 | return static_cast<LargestType>(a) == static_cast<LargestType>(b); |
267 | } |
268 | |
269 | template <> |
270 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Float64, DB::UInt64>(DB::Float64 f, DB::UInt64 u) |
271 | { |
272 | return static_cast<DB::UInt64>(f) == u && f == static_cast<DB::Float64>(u); |
273 | } |
274 | |
275 | template <> |
276 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::UInt64, DB::Float64>(DB::UInt64 u, DB::Float64 f) |
277 | { |
278 | return u == static_cast<DB::UInt64>(f) && static_cast<DB::Float64>(u) == f; |
279 | } |
280 | |
281 | template <> |
282 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Float64, DB::Int64>(DB::Float64 f, DB::Int64 u) |
283 | { |
284 | return static_cast<DB::Int64>(f) == u && f == static_cast<DB::Float64>(u); |
285 | } |
286 | |
287 | template <> |
288 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Int64, DB::Float64>(DB::Int64 u, DB::Float64 f) |
289 | { |
290 | return u == static_cast<DB::Int64>(f) && static_cast<DB::Float64>(u) == f; |
291 | } |
292 | |
293 | template <> |
294 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Float32, DB::UInt64>(DB::Float32 f, DB::UInt64 u) |
295 | { |
296 | return static_cast<DB::UInt64>(f) == u && f == static_cast<DB::Float32>(u); |
297 | } |
298 | |
299 | template <> |
300 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::UInt64, DB::Float32>(DB::UInt64 u, DB::Float32 f) |
301 | { |
302 | return u == static_cast<DB::UInt64>(f) && static_cast<DB::Float32>(u) == f; |
303 | } |
304 | |
305 | template <> |
306 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Float32, DB::Int64>(DB::Float32 f, DB::Int64 u) |
307 | { |
308 | return static_cast<DB::Int64>(f) == u && f == static_cast<DB::Float32>(u); |
309 | } |
310 | |
311 | template <> |
312 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::Int64, DB::Float32>(DB::Int64 u, DB::Float32 f) |
313 | { |
314 | return u == static_cast<DB::Int64>(f) && static_cast<DB::Float32>(u) == f; |
315 | } |
316 | |
317 | template <> |
318 | inline bool NO_SANITIZE_UNDEFINED equalsOp<DB::UInt128, DB::Float64>(DB::UInt128 u, DB::Float64 f) |
319 | { |
320 | return u.low == 0 && equalsOp(static_cast<UInt64>(u.high), f); |
321 | } |
322 | |
323 | template <> |
324 | inline bool equalsOp<DB::UInt128, DB::Float32>(DB::UInt128 u, DB::Float32 f) |
325 | { |
326 | return equalsOp(u, static_cast<DB::Float64>(f)); |
327 | } |
328 | |
329 | template <> |
330 | inline bool equalsOp<DB::Float64, DB::UInt128>(DB::Float64 f, DB::UInt128 u) |
331 | { |
332 | return equalsOp(u, f); |
333 | } |
334 | |
335 | template <> |
336 | inline bool equalsOp<DB::Float32, DB::UInt128>(DB::Float32 f, DB::UInt128 u) |
337 | { |
338 | return equalsOp(static_cast<DB::Float64>(f), u); |
339 | } |
340 | |
341 | inline bool NO_SANITIZE_UNDEFINED greaterOp(DB::Int128 i, DB::Float64 f) |
342 | { |
343 | static constexpr __int128 min_int128 = __int128(0x8000000000000000ll) << 64; |
344 | static constexpr __int128 max_int128 = (__int128(0x7fffffffffffffffll) << 64) + 0xffffffffffffffffll; |
345 | |
346 | if (-MAX_INT64_WITH_EXACT_FLOAT64_REPR <= i && i <= MAX_INT64_WITH_EXACT_FLOAT64_REPR) |
347 | return static_cast<DB::Float64>(i) > f; |
348 | |
349 | return (f < static_cast<DB::Float64>(min_int128)) |
350 | || (f < static_cast<DB::Float64>(max_int128) && i > static_cast<DB::Int128>(f)); |
351 | } |
352 | |
353 | inline bool NO_SANITIZE_UNDEFINED greaterOp(DB::Float64 f, DB::Int128 i) |
354 | { |
355 | static constexpr __int128 min_int128 = __int128(0x8000000000000000ll) << 64; |
356 | static constexpr __int128 max_int128 = (__int128(0x7fffffffffffffffll) << 64) + 0xffffffffffffffffll; |
357 | |
358 | if (-MAX_INT64_WITH_EXACT_FLOAT64_REPR <= i && i <= MAX_INT64_WITH_EXACT_FLOAT64_REPR) |
359 | return f > static_cast<DB::Float64>(i); |
360 | |
361 | return (f >= static_cast<DB::Float64>(max_int128)) |
362 | || (f > static_cast<DB::Float64>(min_int128) && static_cast<DB::Int128>(f) > i); |
363 | } |
364 | |
365 | inline bool greaterOp(DB::Int128 i, DB::Float32 f) { return greaterOp(i, static_cast<DB::Float64>(f)); } |
366 | inline bool greaterOp(DB::Float32 f, DB::Int128 i) { return greaterOp(static_cast<DB::Float64>(f), i); } |
367 | |
368 | inline bool NO_SANITIZE_UNDEFINED equalsOp(DB::Int128 i, DB::Float64 f) { return i == static_cast<DB::Int128>(f) && static_cast<DB::Float64>(i) == f; } |
369 | inline bool NO_SANITIZE_UNDEFINED equalsOp(DB::Int128 i, DB::Float32 f) { return i == static_cast<DB::Int128>(f) && static_cast<DB::Float32>(i) == f; } |
370 | inline bool equalsOp(DB::Float64 f, DB::Int128 i) { return equalsOp(i, f); } |
371 | inline bool equalsOp(DB::Float32 f, DB::Int128 i) { return equalsOp(i, f); } |
372 | |
373 | template <typename A, typename B> |
374 | inline bool_if_not_safe_conversion<A, B> notEqualsOp(A a, B b) |
375 | { |
376 | return !equalsOp(a, b); |
377 | } |
378 | |
379 | template <typename A, typename B> |
380 | inline bool_if_safe_conversion<A, B> notEqualsOp(A a, B b) |
381 | { |
382 | return a != b; |
383 | } |
384 | |
385 | |
386 | template <typename A, typename B> |
387 | inline bool_if_not_safe_conversion<A, B> lessOp(A a, B b) |
388 | { |
389 | return greaterOp(b, a); |
390 | } |
391 | |
392 | template <typename A, typename B> |
393 | inline bool_if_safe_conversion<A, B> lessOp(A a, B b) |
394 | { |
395 | return a < b; |
396 | } |
397 | |
398 | |
399 | template <typename A, typename B> |
400 | inline bool_if_not_safe_conversion<A, B> lessOrEqualsOp(A a, B b) |
401 | { |
402 | if (isNaN(a) || isNaN(b)) |
403 | return false; |
404 | return !greaterOp(a, b); |
405 | } |
406 | |
407 | template <typename A, typename B> |
408 | inline bool_if_safe_conversion<A, B> lessOrEqualsOp(A a, B b) |
409 | { |
410 | return a <= b; |
411 | } |
412 | |
413 | |
414 | template <typename A, typename B> |
415 | inline bool_if_not_safe_conversion<A, B> greaterOrEqualsOp(A a, B b) |
416 | { |
417 | if (isNaN(a) || isNaN(b)) |
418 | return false; |
419 | return !greaterOp(b, a); |
420 | } |
421 | |
422 | template <typename A, typename B> |
423 | inline bool_if_safe_conversion<A, B> greaterOrEqualsOp(A a, B b) |
424 | { |
425 | return a >= b; |
426 | } |
427 | |
428 | /// Converts numeric to an equal numeric of other type. |
429 | template <typename From, typename To> |
430 | inline bool NO_SANITIZE_UNDEFINED convertNumeric(From value, To & result) |
431 | { |
432 | /// If the type is actually the same it's not necessary to do any checks. |
433 | if constexpr (std::is_same_v<From, To>) |
434 | { |
435 | result = value; |
436 | return true; |
437 | } |
438 | |
439 | /// Note that NaNs doesn't compare equal to anything, but they are still in range of any Float type. |
440 | if (isNaN(value) && std::is_floating_point_v<To>) |
441 | { |
442 | result = value; |
443 | return true; |
444 | } |
445 | |
446 | result = static_cast<To>(value); |
447 | return equalsOp(value, result); |
448 | } |
449 | |
450 | } |
451 | |
452 | |
453 | namespace DB |
454 | { |
455 | |
456 | template <typename A, typename B> struct EqualsOp |
457 | { |
458 | /// An operation that gives the same result, if arguments are passed in reverse order. |
459 | using SymmetricOp = EqualsOp<B, A>; |
460 | |
461 | static UInt8 apply(A a, B b) { return accurate::equalsOp(a, b); } |
462 | }; |
463 | |
464 | template <typename A, typename B> struct NotEqualsOp |
465 | { |
466 | using SymmetricOp = NotEqualsOp<B, A>; |
467 | static UInt8 apply(A a, B b) { return accurate::notEqualsOp(a, b); } |
468 | }; |
469 | |
470 | template <typename A, typename B> struct GreaterOp; |
471 | |
472 | template <typename A, typename B> struct LessOp |
473 | { |
474 | using SymmetricOp = GreaterOp<B, A>; |
475 | static UInt8 apply(A a, B b) { return accurate::lessOp(a, b); } |
476 | }; |
477 | |
478 | template <typename A, typename B> struct GreaterOp |
479 | { |
480 | using SymmetricOp = LessOp<B, A>; |
481 | static UInt8 apply(A a, B b) { return accurate::greaterOp(a, b); } |
482 | }; |
483 | |
484 | template <typename A, typename B> struct GreaterOrEqualsOp; |
485 | |
486 | template <typename A, typename B> struct LessOrEqualsOp |
487 | { |
488 | using SymmetricOp = GreaterOrEqualsOp<B, A>; |
489 | static UInt8 apply(A a, B b) { return accurate::lessOrEqualsOp(a, b); } |
490 | }; |
491 | |
492 | template <typename A, typename B> struct GreaterOrEqualsOp |
493 | { |
494 | using SymmetricOp = LessOrEqualsOp<B, A>; |
495 | static UInt8 apply(A a, B b) { return accurate::greaterOrEqualsOp(a, b); } |
496 | }; |
497 | |
498 | } |
499 | |