Merge branch 'lukas/erts/large_float_cmp/OTP-9497'

* lukas/erts/large_float_cmp/OTP-9497:
  Update documentation after changes in integer and float comparison
  Do small optimisation on platforms with 32 bit Eterm
  Add tests for equality checking
  Optimize comparison of huge floats and smaller bignums
  Add tests for comparing large floats and small bignums
  Cleanup double_to_bignum conversion code
  Update size of tmp cmp bignum buffer
  Expand tests for float and number comparison
  Update heauristic to work on halfword
  Add heauristics bignum vs float checks
  Optimise bugnum and small comparison
  Add float vs integer comparison tests
  Update integer and floating point number comparisons

5 files changed, 242 insertions, 23 deletions

diff --git a/erts/emulator/beam/big.c b/erts/emulator/beam/big.c
index d18de9ae5d..b90ea6b478 100644
--- a/erts/emulator/beam/big.c
+++ b/erts/emulator/beam/big.c
@@ -1584,6 +1584,62 @@ big_to_double(Wterm x, double* resp)
     return 0;
 }
 
+/*
+ * Logic has been copied from erl_bif_guard.c and slightly
+ * modified to use a static instead of dynamic heap
+ */
+Eterm
+double_to_big(double x, Eterm *heap)
+{
+    int is_negative;
+    int ds;
+    ErtsDigit* xp;
+    Eterm res;
+    int i;
+    size_t sz;
+    Eterm* hp;
+    double dbase;
+
+    if (x >= 0) {
+	is_negative = 0;
+    } else {
+	is_negative = 1;
+	x = -x;
+    }
+
+    /* Unscale & (calculate exponent) */
+    ds = 0;
+    dbase = ((double) (D_MASK) + 1);
+    while (x >= 1.0) {
+	x /= dbase; /* "shift" right */
+	ds++;
+    }
+    sz = BIG_NEED_SIZE(ds); /* number of words including arity */
+
+    hp = heap;
+    res = make_big(hp);
+    xp = (ErtsDigit*) (hp + 1);
+
+    for (i = ds - 1; i >= 0; i--) {
+	ErtsDigit d;
+
+	x *= dbase; /* "shift" left */
+	d = x; /* trunc */
+	xp[i] = d; /* store digit */
+	x -= d; /* remove integer part */
+    }
+    while ((ds & (BIG_DIGITS_PER_WORD - 1)) != 0) {
+	xp[ds++] = 0;
+    }
+
+    if (is_negative) {
+	*hp = make_neg_bignum_header(sz-1);
+    } else {
+	*hp = make_pos_bignum_header(sz-1);
+    }
+    return res;
+}
+
 
 /*
  ** Estimate the number of decimal digits (include sign)
diff --git a/erts/emulator/beam/big.h b/erts/emulator/beam/big.h
index 2afc37004f..256f1c2b45 100644
--- a/erts/emulator/beam/big.h
+++ b/erts/emulator/beam/big.h
@@ -140,6 +140,7 @@ Eterm big_lshift(Eterm, Sint, Eterm*);
 int big_comp (Wterm, Wterm);
 int big_ucomp (Eterm, Eterm);
 int big_to_double(Wterm x, double* resp);
+Eterm double_to_big(double, Eterm*);
 Eterm small_to_big(Sint, Eterm*);
 Eterm uint_to_big(Uint, Eterm*);
 Eterm uword_to_big(UWord, Eterm*);
diff --git a/erts/emulator/beam/erl_vm.h b/erts/emulator/beam/erl_vm.h
index e7fd144ec3..f810392e60 100644
--- a/erts/emulator/beam/erl_vm.h
+++ b/erts/emulator/beam/erl_vm.h
@@ -55,7 +55,7 @@
    heap data on the C stack or if we use the buffers in the scheduler data. */
 #define TMP_HEAP_SIZE 128            /* Number of Eterm in the schedulers
 				        small heap for transient heap data */
-#define CMP_TMP_HEAP_SIZE       2    /* cmp wants its own tmp-heap... */
+#define CMP_TMP_HEAP_SIZE       32   /* cmp wants its own tmp-heap... */
 #define ERL_ARITH_TMP_HEAP_SIZE 4    /* as does erl_arith... */
 #define BEAM_EMU_TMP_HEAP_SIZE  2    /* and beam_emu... */
 
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 3f6accba2d..825cb140b2 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -2642,7 +2642,7 @@ tailrecur_ne:
 	FloatDef f1, f2;
 	Eterm big;
 #if HEAP_ON_C_STACK
-	Eterm big_buf[2]; /* If HEAP_ON_C_STACK */
+	Eterm big_buf[32]; /* If HEAP_ON_C_STACK */
 #else
 	Eterm *big_buf = erts_get_scheduler_data()->cmp_tmp_heap;
 #endif
@@ -2653,41 +2653,108 @@ tailrecur_ne:
 	Eterm aw = a;
 	Eterm bw = b;
 #endif
+#define MAX_LOSSLESS_FLOAT ((double)((1LL << 53) - 2))
+#define MIN_LOSSLESS_FLOAT ((double)(((1LL << 53) - 2)*-1))
 	b_tag = tag_val_def(bw);
 
 	switch(_NUMBER_CODE(a_tag, b_tag)) {
 	case SMALL_BIG:
-	    big = small_to_big(signed_val(a), big_buf);
-	    j = big_comp(big, bw);
+	    j = big_sign(bw) ? 1 : -1;
+	    break;
+	case BIG_SMALL:
+	    j = big_sign(aw) ? -1 : 1;
 	    break;
 	case SMALL_FLOAT:
-	    f1.fd = signed_val(a);
 	    GET_DOUBLE(bw, f2);
-	    j = float_comp(f1.fd, f2.fd);
-	    break;
-	case BIG_SMALL:
-	    big = small_to_big(signed_val(b), big_buf);
-	    j = big_comp(aw, big);
+	    if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) {
+		// Float is within the no loss limit
+		f1.fd = signed_val(aw);
+		j = float_comp(f1.fd, f2.fd);
+#if ERTS_SIZEOF_ETERM == 8
+	    } else if (f2.fd > (double) (MAX_SMALL + 1)) {
+		// Float is a positive bignum, i.e. bigger
+		j = -1;
+	    } else if (f2.fd < (double) (MIN_SMALL - 1)) {
+		// Float is a negative bignum, i.e. smaller
+		j = 1;
+	    } else { // Float is a Sint but less precise
+		j = signed_val(aw) - (Sint) f2.fd;
+	    }
+#else
+	    } else {
+		// If float is positive it is bigger than small
+		j = (f2.fd > 0.0) ? -1 : 1;
+	    }
+#endif // ERTS_SIZEOF_ETERM == 8
 	    break;
 	case BIG_FLOAT:
-	    if (big_to_double(aw, &f1.fd) < 0) {
-		j = big_sign(a) ? -1 : 1;
+	    GET_DOUBLE(bw, f2);
+	    if ((f2.fd < (double) (MAX_SMALL + 1))
+		    && (f2.fd > (double) (MIN_SMALL - 1))) {
+		// Float is a Sint
+		j = big_sign(aw) ? -1 : 1;
+	    } else if ((pow(2.0,(big_arity(aw)-1.0)*D_EXP)-1.0) > fabs(f2.fd)) {
+		// If bignum size shows that it is bigger than the abs float
+		j = big_sign(aw) ? -1 : 1;
+	    } else if ((pow(2.0,(big_arity(aw))*D_EXP)-1.0) < fabs(f2.fd)) {
+		// If bignum size shows that it is smaller than the abs float
+		j = f2.fd < 0 ? 1 : -1;
+	    } else if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) {
+		// Float is within the no loss limit
+		if (big_to_double(aw, &f1.fd) < 0) {
+		    j = big_sign(aw) ? -1 : 1;
+		} else {
+		    j = float_comp(f1.fd, f2.fd);
+		}
 	    } else {
-		GET_DOUBLE(bw, f2);
-		j = float_comp(f1.fd, f2.fd);
+		big = double_to_big(f2.fd, big_buf);
+		j = big_comp(aw, big);
 	    }
 	    break;
 	case FLOAT_SMALL:
 	    GET_DOUBLE(aw, f1);
-	    f2.fd = signed_val(b);
-	    j = float_comp(f1.fd, f2.fd);
+	    if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) {
+		// Float is within the no loss limit
+		f2.fd = signed_val(bw);
+		j = float_comp(f1.fd, f2.fd);
+#if ERTS_SIZEOF_ETERM == 8
+	    } else if (f1.fd > (double) (MAX_SMALL + 1)) {
+		// Float is a positive bignum, i.e. bigger
+		j = 1;
+	    } else if (f1.fd < (double) (MIN_SMALL - 1)) {
+		// Float is a negative bignum, i.e. smaller
+		j = -1;
+	    } else { // Float is a Sint but less precise it
+		j = (Sint) f1.fd - signed_val(bw);
+	    }
+#else
+	    } else {
+		// If float is positive it is bigger than small
+		j = (f1.fd > 0.0) ? 1 : -1;
+	    }
+#endif // ERTS_SIZEOF_ETERM == 8
 	    break;
 	case FLOAT_BIG:
-	    if (big_to_double(bw, &f2.fd) < 0) {
-		j = big_sign(b) ? 1 : -1;
+	    GET_DOUBLE(aw, f1);
+	    if ((f1.fd < (double) (MAX_SMALL + 1))
+		    && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint
+		j = big_sign(bw) ? 1 : -1;
+	    } else if ((pow(2.0, (big_arity(bw) - 1.0) * D_EXP) - 1.0) > fabs(f1.fd)) {
+		// If bignum size shows that it is bigger than the abs float
+		j = big_sign(bw) ? 1 : -1;
+	    } else if ((pow(2.0,(big_arity(bw))*D_EXP)-1.0) < fabs(f1.fd)) {
+		// If bignum size shows that it is smaller than the abs float
+		j = f1.fd < 0 ? -1 : 1;
+	    } else if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) {
+		// Float is within the no loss limit
+		if (big_to_double(bw, &f2.fd) < 0) {
+		    j = big_sign(bw) ? 1 : -1;
+		} else {
+		    j = float_comp(f1.fd, f2.fd);
+		}
 	    } else {
-		GET_DOUBLE(aw, f1);
-		j = float_comp(f1.fd, f2.fd);
+		big = double_to_big(f1.fd, big_buf);
+		j = big_comp(big, bw);
 	    }
 	    break;
 	default:
diff --git a/erts/emulator/test/float_SUITE.erl b/erts/emulator/test/float_SUITE.erl
index 736510339f..46466427c5 100644
--- a/erts/emulator/test/float_SUITE.erl
+++ b/erts/emulator/test/float_SUITE.erl
@@ -25,7 +25,7 @@
 	 init_per_group/2,end_per_group/2,
 	 init_per_testcase/2,end_per_testcase/2,
 	 fpe/1,fp_drv/1,fp_drv_thread/1,denormalized/1,match/1,
-	 bad_float_unpack/1]).
+	 bad_float_unpack/1,cmp_zero/1, cmp_integer/1, cmp_bignum/1]).
 -export([otp_7178/1]).
 
 
@@ -41,10 +41,10 @@ suite() -> [{ct_hooks,[ts_install_cth]}].
 
 all() -> 
     [fpe, fp_drv, fp_drv_thread, otp_7178, denormalized,
-     match, bad_float_unpack].
+     match, bad_float_unpack, {group, comparison}].
 
 groups() -> 
-    [].
+    [{comparison, [parallel], [cmp_zero, cmp_integer, cmp_bignum]}].
 
 init_per_suite(Config) ->
     Config.
@@ -187,6 +187,101 @@ bad_float_unpack(Config) when is_list(Config) ->
 bad_float_unpack_match(<<F:64/float>>) -> F;
 bad_float_unpack_match(<<I:64/integer-signed>>) -> I.
 
+cmp_zero(_Config) ->
+    cmp(0.5e-323,0).
+
+cmp_integer(_Config) ->
+    Axis = (1 bsl 53)-2.0, %% The point where floating points become unprecise
+    span_cmp(Axis,2,200),
+    cmp(Axis*Axis,round(Axis)).
+
+cmp_bignum(_Config) ->
+    span_cmp((1 bsl 58) - 1.0),%% Smallest bignum float
+
+    %% Test when the big num goes from I to I+1 in size
+    [span_cmp((1 bsl (32*I)) - 1.0) || I <- lists:seq(2,30)],
+
+    %% Test bignum greater then largest float
+    cmp((1 bsl (64*16)) - 1, (1 bsl (64*15)) * 1.0),
+    %% Test when num is much larger then float
+    [cmp((1 bsl (32*I)) - 1, (1 bsl (32*(I-2))) * 1.0) || I <- lists:seq(3,30)],
+    %% Test when float is much larger than num
+    [cmp((1 bsl (64*15)) * 1.0, (1 bsl (32*(I)))) || I <- lists:seq(1,29)],
+
+    %% Test that all int == float works as they should
+    [true = 1 bsl N == (1 bsl N)*1.0 || N <- lists:seq(0, 1023)],
+    [true = (1 bsl N)*-1 == (1 bsl N)*-1.0 || N <- lists:seq(0, 1023)].
+
+span_cmp(Axis) ->
+    span_cmp(Axis, 25).
+span_cmp(Axis, Length) ->
+    span_cmp(Axis, round(Axis) bsr 52, Length).
+span_cmp(Axis, Incr, Length) ->
+    [span_cmp(Axis, Incr, Length, 1 bsl (1 bsl I)) || I <- lists:seq(0,6)].
+%% This function creates tests around number axis. Both <, > and == is tested
+%% for both negative and positive numbers.
+%%
+%% Axis: The number around which to do the tests eg. (1 bsl 58) - 1.0
+%% Incr: How much to increment the test numbers inbetween each test.
+%% Length: Length/2 is the number of Incr away from Axis to test on the
+%%         negative and positive plane.
+%% Diff: How much the float and int should differ when comparing
+span_cmp(Axis, Incr, Length, Diff) ->
+    [begin
+	 cmp(round(Axis*-1.0)+Diff+I*Incr,Axis*-1.0+I*Incr),
+	 cmp(Axis*-1.0+I*Incr,round(Axis*-1.0)-Diff+I*Incr)
+     end || I <- lists:seq((Length div 2)*-1,(Length div 2))],
+    [begin
+	 cmp(round(Axis)+Diff+I*Incr,Axis+I*Incr),
+	 cmp(Axis+I*Incr,round(Axis)-Diff+I*Incr)
+     end || I <- lists:seq((Length div 2)*-1,(Length div 2))].
+
+cmp(Big,Small) when is_float(Big) ->
+    BigGtSmall = lists:flatten(
+		 io_lib:format("~f > ~p",[Big,Small])),
+    BigLtSmall = lists:flatten(
+		 io_lib:format("~f < ~p",[Big,Small])),
+    BigEqSmall = lists:flatten(
+		 io_lib:format("~f == ~p",[Big,Small])),
+    SmallGtBig = lists:flatten(
+		   io_lib:format("~p > ~f",[Small,Big])),
+    SmallLtBig = lists:flatten(
+		   io_lib:format("~p < ~f",[Small,Big])),
+    SmallEqBig = lists:flatten(
+		   io_lib:format("~p == ~f",[Small,Big])),
+    cmp(Big,Small,BigGtSmall,BigLtSmall,SmallGtBig,SmallLtBig,
+	SmallEqBig,BigEqSmall);
+cmp(Big,Small) when is_float(Small) ->
+    BigGtSmall = lists:flatten(
+		   io_lib:format("~p > ~f",[Big,Small])),
+    BigLtSmall = lists:flatten(
+		   io_lib:format("~p < ~f",[Big,Small])),
+    BigEqSmall = lists:flatten(
+		   io_lib:format("~p == ~f",[Big,Small])),
+    SmallGtBig = lists:flatten(
+		   io_lib:format("~f > ~p",[Small,Big])),
+    SmallLtBig = lists:flatten(
+		   io_lib:format("~f < ~p",[Small,Big])),
+    SmallEqBig = lists:flatten(
+		   io_lib:format("~f == ~p",[Small,Big])),
+    cmp(Big,Small,BigGtSmall,BigLtSmall,SmallGtBig,SmallLtBig,
+	SmallEqBig,BigEqSmall).
+
+cmp(Big,Small,BigGtSmall,BigLtSmall,SmallGtBig,SmallLtBig,
+    SmallEqBig,BigEqSmall) ->
+    {_,_,_,true} = {Big,Small,BigGtSmall,
+		    Big > Small},
+    {_,_,_,false} = {Big,Small,BigLtSmall,
+		     Big < Small},
+    {_,_,_,false} = {Big,Small,SmallGtBig,
+		     Small > Big},
+    {_,_,_,true} = {Big,Small,SmallLtBig,
+		    Small < Big},
+    {_,_,_,false} = {Big,Small,SmallEqBig,
+		     Small == Big},
+    {_,_,_,false} = {Big,Small,BigEqSmall,
+		     Big == Small}.
+
 id(I) -> I.
     
 start_node(Config) when is_list(Config) ->