Fix comparison of Float64 and Int64 In Num_Compare_To methods, account for integers that can't be represented exactly as double.
In Num_Equals methods, don't blindly cast floats to integers as overflow is undefined behavior. Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/b1b44e0c Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/b1b44e0c Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/b1b44e0c Branch: refs/heads/master Commit: b1b44e0c78d7a635c528ac934d0363e1ad9df066 Parents: 28fbdde Author: Nick Wellnhofer <[email protected]> Authored: Sun May 24 14:49:08 2015 +0200 Committer: Nick Wellnhofer <[email protected]> Committed: Thu Jul 9 16:34:00 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Num.c | 184 ++++++++++++++++++++++------- runtime/core/Clownfish/Num.cfh | 18 +-- runtime/core/Clownfish/Test/TestNum.c | 54 ++++++++- 3 files changed, 202 insertions(+), 54 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/b1b44e0c/runtime/core/Clownfish/Num.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Num.c b/runtime/core/Clownfish/Num.c index c3f4777..3575fea 100644 --- a/runtime/core/Clownfish/Num.c +++ b/runtime/core/Clownfish/Num.c @@ -21,6 +21,8 @@ #define C_CFISH_FLOAT64 #define CFISH_USE_SHORT_NAMES +#include <float.h> + #include "charmony.h" #include "Clownfish/Num.h" @@ -28,6 +30,34 @@ #include "Clownfish/Err.h" #include "Clownfish/Class.h" +#if FLT_RADIX != 2 + #error Unsupported FLT_RADIX +#endif + +#if DBL_MANT_DIG != 53 + #error Unsupported DBL_MANT_DIG +#endif + +#define MAX_PRECISE_I64 (INT64_C(1) << DBL_MANT_DIG) +#define MIN_PRECISE_I64 -MAX_PRECISE_I64 + +// For floating point range checks, it's important to use constants that +// can be exactly represented as doubles. `f64 > INT64_MAX` can produce +// wrong results. +#define POW_2_63 9223372036854775808.0 + +static int32_t +S_compare_f64(double a, double b); + +static int32_t +S_compare_i64(int64_t a, int64_t b); + +static int32_t +S_compare_i64_f64(int64_t i64, double f64); + +static bool +S_equals_i64_f64(int64_t i64, double f64); + Num* Num_init(Num *self) { ABSTRACT_CLASS_CHECK(self, NUM); @@ -35,16 +65,6 @@ Num_init(Num *self) { } bool -Num_Equals_IMP(Num *self, Obj *other) { - Num *twin = (Num*)other; - if (twin == self) { return true; } - if (!Obj_is_a(other, NUM)) { return false; } - if (Num_To_F64(self) != Num_To_F64(twin)) { return false; } - if (Num_To_I64(self) != Num_To_I64(twin)) { return false; } - return true; -} - -bool Num_To_Bool_IMP(Num *self) { return !!Num_To_I64(self); } @@ -57,15 +77,6 @@ FloatNum_init(FloatNum *self) { return (FloatNum*)Num_init((Num*)self); } -int32_t -FloatNum_Compare_To_IMP(FloatNum *self, Obj *other) { - Num *twin = (Num*)CERTIFY(other, NUM); - double f64_diff = FloatNum_To_F64(self) - Num_To_F64(twin); - if (f64_diff < 0) { return -1; } - else if (f64_diff > 0) { return 1; } - return 0; -} - String* FloatNum_To_String_IMP(FloatNum *self) { return Str_newf("%f64", FloatNum_To_F64(self)); @@ -79,18 +90,6 @@ IntNum_init(IntNum *self) { return (IntNum*)Num_init((Num*)self); } -int32_t -IntNum_Compare_To_IMP(IntNum *self, Obj *other) { - if (!Obj_is_a(other, INTNUM)) { - return -Obj_Compare_To(other, (Obj*)self); - } - int64_t self_value = IntNum_To_I64(self); - int64_t other_value = IntNum_To_I64((IntNum*)other); - if (self_value < other_value) { return -1; } - else if (self_value > other_value) { return 1; } - return 0; -} - String* IntNum_To_String_IMP(IntNum *self) { return Str_newf("%i64", IntNum_To_I64(self)); @@ -110,6 +109,37 @@ Float64_init(Float64 *self, double value) { return (Float64*)FloatNum_init((FloatNum*)self); } +bool +Float64_Equals_IMP(Float64 *self, Obj *other) { + if (Obj_is_a(other, FLOAT64)) { + Float64 *twin = (Float64*)other; + return self->value == twin->value; + } + else if (Obj_is_a(other, INTEGER64)) { + Integer64 *twin = (Integer64*)other; + return S_equals_i64_f64(twin->value, self->value); + } + else { + return false; + } +} + +int32_t +Float64_Compare_To_IMP(Float64 *self, Obj *other) { + if (Obj_is_a(other, FLOAT64)) { + Float64 *twin = (Float64*)other; + return S_compare_f64(self->value, twin->value); + } + else if (Obj_is_a(other, INTEGER64)) { + Integer64 *twin = (Integer64*)other; + return -S_compare_i64_f64(twin->value, self->value); + } + else { + THROW(ERR, "Can't compare Float64 to %o", Obj_get_class_name(other)); + UNREACHABLE_RETURN(int32_t); + } +} + double Float64_Get_Value_IMP(Float64 *self) { return self->value; @@ -155,6 +185,37 @@ Int64_init(Integer64 *self, int64_t value) { return (Integer64*)IntNum_init((IntNum*)self); } +bool +Int64_Equals_IMP(Integer64 *self, Obj *other) { + if (Obj_is_a(other, INTEGER64)) { + Integer64 *twin = (Integer64*)other; + return self->value == twin->value; + } + else if (Obj_is_a(other, FLOAT64)) { + Float64 *twin = (Float64*)other; + return S_equals_i64_f64(self->value, twin->value); + } + else { + return false; + } +} + +int32_t +Int64_Compare_To_IMP(Integer64 *self, Obj *other) { + if (Obj_is_a(other, INTEGER64)) { + Integer64 *twin = (Integer64*)other; + return S_compare_i64(self->value, twin->value); + } + else if (Obj_is_a(other, FLOAT64)) { + Float64 *twin = (Float64*)other; + return S_compare_i64_f64(self->value, twin->value); + } + else { + THROW(ERR, "Can't compare Int64 to %o", Obj_get_class_name(other)); + UNREACHABLE_RETURN(int32_t); + } +} + int64_t Int64_Get_Value_IMP(Integer64 *self) { return self->value; @@ -186,20 +247,55 @@ Int64_Mimic_IMP(Integer64 *self, Obj *other) { self->value = twin->value; } -bool -Int64_Equals_IMP(Integer64 *self, Obj *other) { - Num *twin = (Num*)other; - if (twin == (Num*)self) { return true; } - if (!Obj_is_a(other, NUM)) { return false; } - if (Obj_is_a(other, FLOATNUM)) { - double floating_val = Num_To_F64(twin); - int64_t int_val = (int64_t)floating_val; - if ((double)int_val != floating_val) { return false; } - if (int_val != self->value) { return false; } +static int32_t +S_compare_f64(double a, double b) { + return a == b ? 0 : a < b ? -1 : 1; +} + +static int32_t +S_compare_i64(int64_t a, int64_t b) { + return a == b ? 0 : a < b ? -1 : 1; +} + +static int32_t +S_compare_i64_f64(int64_t i64, double f64) { + int f64_comparison = S_compare_f64((double)i64, f64); + + // If the integer can be represented precisely as a double or the numbers + // compare as unequal when converted to double, the result is correct. + if ((i64 >= MIN_PRECISE_I64 && i64 <= MAX_PRECISE_I64) + || f64_comparison != 0 + ) { + return f64_comparison; } - else { - if (self->value != Num_To_I64(twin)) { return false; } + + // Otherwise, the double is an integer. + + // Corner case. 2^63 can compare equal to an int64_t although it is + // out of range. + if (f64 == POW_2_63) { return -1; } + + return S_compare_i64(i64, (int64_t)f64); +} + +static bool +S_equals_i64_f64(int64_t i64, double f64) { + bool equal = ((double)i64 == f64); + + // If the integer can be represented precisely as a double or the numbers + // compare as unequal when converted to double, the result is correct. + if ((i64 >= MIN_PRECISE_I64 && i64 <= MAX_PRECISE_I64) + || !equal + ) { + return equal; } - return true; + + // Otherwise, the double is an integer. + + // Corner case. 2^63 can compare equal to an int64_t although it is + // out of range. + if (f64 == POW_2_63) { return false; } + + return i64 == (int64_t)f64; } http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/b1b44e0c/runtime/core/Clownfish/Num.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Num.cfh b/runtime/core/Clownfish/Num.cfh index 61b4f7b..053c94d 100644 --- a/runtime/core/Clownfish/Num.cfh +++ b/runtime/core/Clownfish/Num.cfh @@ -23,9 +23,6 @@ abstract class Clownfish::Num inherits Clownfish::Obj { inert Num* init(Num *self); - public bool - Equals(Num *self, Obj *other); - /** Convert the number to a 64-bit integer. */ public abstract int64_t @@ -50,9 +47,6 @@ abstract class Clownfish::FloatNum inherits Clownfish::Num { inert FloatNum* init(FloatNum *self); - public int32_t - Compare_To(FloatNum *self, Obj *other); - public incremented String* To_String(FloatNum *self); } @@ -65,9 +59,6 @@ abstract class Clownfish::IntNum inherits Clownfish::Num { inert IntNum* init(IntNum *self); - public int32_t - Compare_To(IntNum *self, Obj *other); - public incremented String* To_String(IntNum *self); } @@ -102,6 +93,12 @@ final class Clownfish::Float64 inherits Clownfish::FloatNum { public double To_F64(Float64 *self); + public bool + Equals(Float64 *self, Obj *other); + + public int32_t + Compare_To(Float64 *self, Obj *other); + public incremented Float64* Clone(Float64 *self); @@ -144,6 +141,9 @@ final class Clownfish::Integer64 nickname Int64 public bool Equals(Integer64 *self, Obj *other); + public int32_t + Compare_To(Integer64 *self, Obj *other); + public incremented Integer64* Clone(Integer64 *self); http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/b1b44e0c/runtime/core/Clownfish/Test/TestNum.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestNum.c b/runtime/core/Clownfish/Test/TestNum.c index 9da7bb5..8947d2e 100644 --- a/runtime/core/Clownfish/Test/TestNum.c +++ b/runtime/core/Clownfish/Test/TestNum.c @@ -17,6 +17,10 @@ #define CFISH_USE_SHORT_NAMES #define TESTCFISH_USE_SHORT_NAMES +#include <math.h> + +#include "charmony.h" + #include "Clownfish/Test/TestNum.h" #include "Clownfish/String.h" @@ -79,6 +83,41 @@ test_accessors(TestBatchRunner *runner) { } static void +S_test_compare_float_int(TestBatchRunner *runner, double f64_val, + int64_t i64_val, int32_t result) { + Float64 *f64; + Integer64 *i64; + + f64 = Float64_new(f64_val); + i64 = Int64_new(i64_val); + TEST_INT_EQ(runner, Float64_Compare_To(f64, (Obj*)i64), result, + "Float64_Compare_To %f %" PRId64, f64_val, i64_val); + TEST_INT_EQ(runner, Int64_Compare_To(i64, (Obj*)f64), -result, + "Int64_Compare_To %" PRId64" %f", i64_val, f64_val); + TEST_INT_EQ(runner, Float64_Equals(f64, (Obj*)i64), result == 0, + "Float64_Equals %f %" PRId64, f64_val, i64_val); + TEST_INT_EQ(runner, Int64_Equals(i64, (Obj*)f64), result == 0, + "Int64_Equals %" PRId64 " %f", i64_val, f64_val); + DECREF(f64); + DECREF(i64); + + if (i64_val == INT64_MIN) { return; } + + f64 = Float64_new(-f64_val); + i64 = Int64_new(-i64_val); + TEST_INT_EQ(runner, Float64_Compare_To(f64, (Obj*)i64), -result, + "Float64_Compare_To %f %" PRId64, -f64_val, -i64_val); + TEST_INT_EQ(runner, Int64_Compare_To(i64, (Obj*)f64), result, + "Int64_Compare_To %" PRId64" %f", -i64_val, -f64_val); + TEST_INT_EQ(runner, Float64_Equals(f64, (Obj*)i64), result == 0, + "Float64_Equals %f %" PRId64, -f64_val, -i64_val); + TEST_INT_EQ(runner, Int64_Equals(i64, (Obj*)f64), result == 0, + "Int64_Equals %" PRId64 " %f", -i64_val, -f64_val); + DECREF(f64); + DECREF(i64); +} + +static void test_Equals_and_Compare_To(TestBatchRunner *runner) { Float64 *f1 = Float64_new(1.0); Float64 *f2 = Float64_new(1.0); @@ -116,6 +155,19 @@ test_Equals_and_Compare_To(TestBatchRunner *runner) { DECREF(i64); DECREF(f1); DECREF(f2); + + // NOTICE: When running these tests on x86/x64, it's best to compile + // with -ffloat-store to avoid excess FPU precision which can hide + // implementation bugs. + S_test_compare_float_int(runner, pow(2.0, 60.0), INT64_C(1) << 60, 0); + S_test_compare_float_int(runner, pow(2.0, 60.0), (INT64_C(1) << 60) - 1, + 1); + S_test_compare_float_int(runner, pow(2.0, 60.0), (INT64_C(1) << 60) + 1, + -1); + S_test_compare_float_int(runner, pow(2.0, 63.0), INT64_MAX, 1); + S_test_compare_float_int(runner, -pow(2.0, 63.0), INT64_MIN, 0); + // -9223372036854777856.0 == nextafter(-pow(2, 63), -INFINITY) + S_test_compare_float_int(runner, -9223372036854777856.0, INT64_MIN, -1); } static void @@ -154,7 +206,7 @@ test_Mimic(TestBatchRunner *runner) { void TestNum_Run_IMP(TestNum *self, TestBatchRunner *runner) { - TestBatchRunner_Plan(runner, (TestBatch*)self, 20); + TestBatchRunner_Plan(runner, (TestBatch*)self, 60); test_To_String(runner); test_accessors(runner); test_Equals_and_Compare_To(runner);
