From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id ADFB122DFB for ; Tue, 6 Aug 2019 18:02:20 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id l1_kI-RBUkWB for ; Tue, 6 Aug 2019 18:02:20 -0400 (EDT) Received: from smtp32.i.mail.ru (smtp32.i.mail.ru [94.100.177.92]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id EFCB422DBA for ; Tue, 6 Aug 2019 18:02:19 -0400 (EDT) From: Nikita Pettik Subject: [tarantool-patches] [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h Date: Wed, 7 Aug 2019 01:02:14 +0300 Message-Id: <2ff7204c9f8b908b028bec926635118ce1982674.1565120194.git.korablev@tarantool.org> In-Reply-To: References: In-Reply-To: References: Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: tarantool-patches@freelists.org Cc: v.shpilevoy@tarantool.org, 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 #include #include #include @@ -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