* [tarantool-patches] [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h
2019-08-06 22:02 [tarantool-patches] [PATCH 0/2] Fix border case in float-int comparison in SQL Nikita Pettik
@ 2019-08-06 22:02 ` Nikita Pettik
2019-08-08 21:37 ` [tarantool-patches] ***UNCHECKED*** " Vladislav Shpilevoy
2019-08-08 21:37 ` [tarantool-patches] ***UNCHECKED*** " Vladislav Shpilevoy
2019-08-06 22:02 ` [tarantool-patches] [PATCH 2/2] sql: use double_compare_uint64() for int<->float cmp Nikita Pettik
2019-08-22 12:31 ` [tarantool-patches] Re: [PATCH 0/2] Fix border case in float-int comparison in SQL Kirill Yukhin
2 siblings, 2 replies; 8+ messages in thread
From: Nikita Pettik @ 2019-08-06 22:02 UTC (permalink / raw)
To: tarantool-patches; +Cc: v.shpilevoy, Nikita Pettik
This function implements common way of precise comparison between
unsigned integer and floating point values (doubles). Currently, it is
used in tuple comparators, but we need the same thing in SQL. Hence,
let's move it to header containing set of utilities.
---
src/box/tuple_compare.cc | 80 ++----------------------------------------------
src/lib/core/util.c | 63 ++++++++++++++++++++++++++++++++++++++
src/trivia/util.h | 14 +++++++++
3 files changed, 80 insertions(+), 77 deletions(-)
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index b7b54e21a..e9951eaa0 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -90,8 +90,6 @@ static enum mp_class mp_classes[] = {
/* .MP_BIN = */ MP_CLASS_BIN
};
-#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
-
static enum mp_class
mp_classof(enum mp_type type)
{
@@ -137,77 +135,6 @@ mp_compare_integer_with_type(const char *field_a, enum mp_type a_type,
}
}
-#define EXP2_53 9007199254740992.0 /* 2.0 ^ 53 */
-#define EXP2_64 1.8446744073709552e+19 /* 2.0 ^ 64 */
-
-/*
- * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
- * comparison result (strcmp-style).
- * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
- * were swapped).
- * K is needed to enable tail call optimization in Release build.
- * NOINLINE attribute was added to avoid aggressive inlining which
- * resulted in over 2Kb code size for mp_compare_number.
- */
-NOINLINE static int
-mp_compare_double_uint64(double lhs, uint64_t rhs, int k)
-{
- assert(k==1 || k==-1);
- /*
- * IEEE double represents 2^N precisely.
- * The value below is 2^53. If a double exceeds this threshold,
- * there's no fractional part. Moreover, the "next" float is
- * 2^53+2, i.e. there's not enough precision to encode even some
- * "odd" integers.
- * Note: ">=" is important, see next block.
- */
- if (lhs >= EXP2_53) {
- /*
- * The value below is 2^64.
- * Note: UINT64_MAX is 2^64-1, hence ">="
- */
- if (lhs >= EXP2_64)
- return k;
- /* Within [2^53, 2^64) double->uint64_t is lossless. */
- assert((double)(uint64_t)lhs == lhs);
- return k*COMPARE_RESULT((uint64_t)lhs, rhs);
- }
- /*
- * According to the IEEE 754 the double format is the
- * following:
- * +------+----------+----------+
- * | sign | exponent | fraction |
- * +------+----------+----------+
- * 1 bit 11 bits 52 bits
- * If the exponent is 0x7FF, the value is a special one.
- * Special value can be NaN, +inf and -inf.
- * If the fraction == 0, the value is inf. Sign depends on
- * the sign bit.
- * If the first bit of the fraction is 1, the value is the
- * quiet NaN, else the signaling NaN.
- */
- if (!isnan(lhs)) {
- /*
- * lhs is a number or inf.
- * If RHS < 2^53, uint64_t->double is lossless.
- * Otherwize the value may get rounded. It's
- * unspecified whether it gets rounded up or down,
- * i.e. the conversion may yield 2^53 for a
- * RHS > 2^53. Since we've aready ensured that
- * LHS < 2^53, the result is still correct even if
- * rounding happens.
- */
- assert(lhs < EXP2_53);
- assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53);
- return k*COMPARE_RESULT(lhs, (double)rhs);
- }
- /*
- * Lhs is NaN. We assume all NaNs to be less than any
- * number.
- */
- return -k;
-}
-
static int
mp_compare_double_any_int(double lhs, const char *rhs, enum mp_type rhs_type,
int k)
@@ -215,13 +142,12 @@ mp_compare_double_any_int(double lhs, const char *rhs, enum mp_type rhs_type,
if (rhs_type == MP_INT) {
int64_t v = mp_decode_int(&rhs);
if (v < 0) {
- return mp_compare_double_uint64(-lhs, (uint64_t)-v,
- -k);
+ return double_compare_uint64(-lhs, (uint64_t)-v, -k);
}
- return mp_compare_double_uint64(lhs, (uint64_t)v, k);
+ return double_compare_uint64(lhs, (uint64_t)v, k);
}
assert(rhs_type == MP_UINT);
- return mp_compare_double_uint64(lhs, mp_decode_uint(&rhs), k);
+ return double_compare_uint64(lhs, mp_decode_uint(&rhs), k);
}
static int
diff --git a/src/lib/core/util.c b/src/lib/core/util.c
index 4ca99e177..ffa1d2b51 100644
--- a/src/lib/core/util.c
+++ b/src/lib/core/util.c
@@ -30,6 +30,7 @@
*/
#include "trivia/util.h"
+#include <math.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
@@ -324,3 +325,65 @@ fpconv_check()
*/
assert(buf[1] == '.');
}
+
+#define EXP2_53 9007199254740992.0 /* 2.0 ^ 53 */
+#define EXP2_64 1.8446744073709552e+19 /* 2.0 ^ 64 */
+
+int
+double_compare_uint64(double lhs, uint64_t rhs, int k)
+{
+ assert(k==1 || k==-1);
+ /*
+ * IEEE double represents 2^N precisely.
+ * The value below is 2^53. If a double exceeds this threshold,
+ * there's no fractional part. Moreover, the "next" float is
+ * 2^53+2, i.e. there's not enough precision to encode even some
+ * "odd" integers.
+ * Note: ">=" is important, see next block.
+ */
+ if (lhs >= EXP2_53) {
+ /*
+ * The value below is 2^64.
+ * Note: UINT64_MAX is 2^64-1, hence ">="
+ */
+ if (lhs >= EXP2_64)
+ return k;
+ /* Within [2^53, 2^64) double->uint64_t is lossless. */
+ assert((double)(uint64_t)lhs == lhs);
+ return k*COMPARE_RESULT((uint64_t)lhs, rhs);
+ }
+ /*
+ * According to the IEEE 754 the double format is the
+ * following:
+ * +------+----------+----------+
+ * | sign | exponent | fraction |
+ * +------+----------+----------+
+ * 1 bit 11 bits 52 bits
+ * If the exponent is 0x7FF, the value is a special one.
+ * Special value can be NaN, +inf and -inf.
+ * If the fraction == 0, the value is inf. Sign depends on
+ * the sign bit.
+ * If the first bit of the fraction is 1, the value is the
+ * quiet NaN, else the signaling NaN.
+ */
+ if (!isnan(lhs)) {
+ /*
+ * lhs is a number or inf.
+ * If RHS < 2^53, uint64_t->double is lossless.
+ * Otherwize the value may get rounded. It's
+ * unspecified whether it gets rounded up or down,
+ * i.e. the conversion may yield 2^53 for a
+ * RHS > 2^53. Since we've aready ensured that
+ * LHS < 2^53, the result is still correct even if
+ * rounding happens.
+ */
+ assert(lhs < EXP2_53);
+ assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53);
+ return k*COMPARE_RESULT(lhs, (double)rhs);
+ }
+ /*
+ * Lhs is NaN. We assume all NaNs to be less than any
+ * number.
+ */
+ return -k;
+}
diff --git a/src/trivia/util.h b/src/trivia/util.h
index 1e01013db..ebfe0c392 100644
--- a/src/trivia/util.h
+++ b/src/trivia/util.h
@@ -500,6 +500,20 @@ json_escape(char *buf, int size, const char *data);
} \
} while(0)
+#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
+
+/**
+ * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
+ * comparison result (strcmp-style).
+ * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
+ * were swapped).
+ * K is needed to enable tail call optimization in Release build.
+ * NOINLINE attribute was added to avoid aggressive inlining which
+ * resulted in over 2Kb code size for mp_compare_number.
+ */
+int
+double_compare_uint64(double lhs, uint64_t rhs, int k);
+
#if !defined(__cplusplus) && !defined(static_assert)
# define static_assert _Static_assert
#endif
--
2.15.1
^ permalink raw reply [flat|nested] 8+ messages in thread* [tarantool-patches] [PATCH 2/2] sql: use double_compare_uint64() for int<->float cmp
2019-08-06 22:02 [tarantool-patches] [PATCH 0/2] Fix border case in float-int comparison in SQL Nikita Pettik
2019-08-06 22:02 ` [tarantool-patches] [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h Nikita Pettik
@ 2019-08-06 22:02 ` Nikita Pettik
2019-08-22 12:31 ` [tarantool-patches] Re: [PATCH 0/2] Fix border case in float-int comparison in SQL Kirill Yukhin
2 siblings, 0 replies; 8+ messages in thread
From: Nikita Pettik @ 2019-08-06 22:02 UTC (permalink / raw)
To: tarantool-patches; +Cc: v.shpilevoy, Nikita Pettik
To compare floating point values and integers in SQL functions
compare_uint_float() and compare_int_float() are used. Unfortunately,
they contain bug connected with checking border case: that's not correct
to cast UINT64_MAX (2^64 - 1) to double. Proper way is to use exp2(2^64)
or predefined floating point constant. To not bother fixing function
which in turn may contain other tricky places, let's use instead already
verified double_compare_uint64(). So that we have unified way of
integer<->float comparison.
---
src/box/sql/vdbeaux.c | 74 +++++++++++----------------------------------------
test/sql/types.result | 2 +-
2 files changed, 17 insertions(+), 59 deletions(-)
diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c
index e7accc745..2654f5c7a 100644
--- a/src/box/sql/vdbeaux.c
+++ b/src/box/sql/vdbeaux.c
@@ -2886,52 +2886,6 @@ sqlBlobCompare(const Mem * pB1, const Mem * pB2)
return n1 - n2;
}
-/**
- * Do a comparison between a 64-bit unsigned/signed integer and a
- * 64-bit floating-point number. Return negative, zero, or
- * positive if the first (integer) is less than, equal to, or
- * greater than the second (double).
- */
-static int
-compare_uint_float(uint64_t u, double r)
-{
- if (r > (double) UINT64_MAX)
- return -1;
- if (r < 0.0)
- return +1;
- uint64_t y = (uint64_t) r;
- if (u < y)
- return -1;
- if (u > y)
- return +1;
- double s = (double) u;
- if (s < r)
- return -1;
- if (s > r)
- return +1;
- return 0;
-}
-
-static int
-compare_int_float(int64_t i, double r)
-{
- if (r < (double) INT64_MIN)
- return +1;
- if (r >= 0.0)
- return -1;
- int64_t y = (int64_t) r;
- if (i < y)
- return -1;
- if (i > y)
- return +1;
- double s = (double) i;
- if (s < r)
- return -1;
- if (s > r)
- return +1;
- return 0;
-}
-
/*
* Compare the values contained by the two memory cells, returning
* negative, zero or positive if pMem1 is less than, equal to, or greater
@@ -2997,16 +2951,16 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl)
}
if ((f1 & MEM_Int) != 0) {
if ((f2 & MEM_Real) != 0) {
- return compare_int_float(pMem1->u.i,
- pMem2->u.r);
+ return double_compare_uint64(-pMem2->u.r,
+ -pMem1->u.i, 1);
} else {
return -1;
}
}
if ((f1 & MEM_UInt) != 0) {
if ((f2 & MEM_Real) != 0) {
- return compare_uint_float(pMem1->u.u,
- pMem2->u.r);
+ return double_compare_uint64(pMem2->u.r,
+ pMem1->u.u, -1);
} else if ((f2 & MEM_Int) != 0) {
return +1;
} else {
@@ -3015,11 +2969,11 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl)
}
if ((f1 & MEM_Real) != 0) {
if ((f2 & MEM_Int) != 0) {
- return -compare_int_float(pMem2->u.i,
- pMem1->u.r);
+ return double_compare_uint64(-pMem1->u.r,
+ -pMem2->u.i, -1);
} else if ((f2 & MEM_UInt) != 0) {
- return -compare_uint_float(pMem2->u.u,
- pMem1->u.r);
+ return double_compare_uint64(pMem1->u.r,
+ pMem2->u.u, 1);
} else {
return -1;
}
@@ -3188,7 +3142,8 @@ sqlVdbeCompareMsgpack(const char **key1,
else if (mem1.u.u > pKey2->u.u)
rc = +1;
} else if ((pKey2->flags & MEM_Real) != 0) {
- rc = compare_uint_float(mem1.u.u, pKey2->u.r);
+ rc = double_compare_uint64(pKey2->u.r,
+ mem1.u.u, -1);
} else {
rc = (pKey2->flags & MEM_Null) ? +1 : -1;
}
@@ -3205,7 +3160,8 @@ sqlVdbeCompareMsgpack(const char **key1,
rc = +1;
}
} else if (pKey2->flags & MEM_Real) {
- rc = compare_int_float(mem1.u.i, pKey2->u.r);
+ rc = double_compare_uint64(-pKey2->u.r,
+ -mem1.u.i, 1);
} else {
rc = (pKey2->flags & MEM_Null) ? +1 : -1;
}
@@ -3219,9 +3175,11 @@ sqlVdbeCompareMsgpack(const char **key1,
mem1.u.r = mp_decode_double(&aKey1);
do_float:
if ((pKey2->flags & MEM_Int) != 0) {
- rc = -compare_int_float(pKey2->u.i, mem1.u.r);
+ rc = double_compare_uint64(-mem1.u.r,
+ -pKey2->u.i, -1);
} else if (pKey2->flags & MEM_UInt) {
- rc = -compare_uint_float(pKey2->u.u, mem1.u.r);
+ rc = double_compare_uint64(mem1.u.r,
+ pKey2->u.u, 1);
} else if (pKey2->flags & MEM_Real) {
if (mem1.u.r < pKey2->u.r) {
rc = -1;
diff --git a/test/sql/types.result b/test/sql/types.result
index 83820af53..c95d21e0f 100644
--- a/test/sql/types.result
+++ b/test/sql/types.result
@@ -1286,7 +1286,7 @@ box.execute("SELECT 18446744073709551615.0 > 18446744073709551615")
- name: 18446744073709551615.0 > 18446744073709551615
type: boolean
rows:
- - [false]
+ - [true]
...
box.execute("SELECT 18446744073709551615 IN ('18446744073709551615', 18446744073709551615.0)")
---
--
2.15.1
^ permalink raw reply [flat|nested] 8+ messages in thread