Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

Jesper Louis Andersen-2
Hi,

While working on transit-erlang, Isaiah Peng and I found what we believe to be a bug in the Erlang compiler:

9> A = -576460752303423488.
-576460752303423488
10> B = binary_to_integer(integer_to_binary(A)).
-576460752303423488
11> A == B.
false
12> A.
-576460752303423488
13> B.
-576460752303423488
14>

I expected command 11 (A == B) to return true, as the numbers are the same. But it looks like constants are not treated the same way as converted vaues for some reason and the equality test fails.

This fails in the interpreter and in compiled code. It *also* fails with list_to_integer/1 and integer_to_list/1.  The number is not chosen arbitrarily. It is -1 * 2^59 which is a borderline number on a 64bit machine. (OTP release 17.1). Isaiah notes that these borderline numbers are not caught by the OTP test cases. They probably should be.

In the interest of full exploration, I've written a QuickCheck test case to catch the remaining trouble. It explicitly tests the borderline numbers and only finds this error.



-module(integer_coding).

-compile(export_all).

-include_lib("eqc/include/eqc.hrl").

power(_N, 0) -> 1;
power(N, P) -> N * power(N, P-1).

perturb() ->
    elements([0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]).

sign() ->
    elements([1, -1]).

nat_power() ->
    frequency([{1, elements([27, 28, 29, 31, 32, 33, 59, 60, 61, 63, 64, 65])},
               {1, nat()}]).

interesting_int() ->
    ?LET({K, Sign, Perturb}, {nat_power(), sign(), perturb()},
      power(2, K)*Sign + Perturb).

prop_binary_iso() ->
    ?FORALL(K, interesting_int(),
            begin
                I = binary_to_integer(integer_to_binary(K)),
                I == K
            end).

prop_list_iso() ->
    ?FORALL(K, interesting_int(),
            begin
                I = list_to_integer(integer_to_list(K)),
                I == K
            end).

all() ->
    eqc:module({numtests, 3000}, ?MODULE).

t() ->
    eqc:quickcheck(eqc:testing_time(300, prop_binary_iso())).


[...]

Produces:

8> integer_coding:all().
prop_list_iso: .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 1498 tests.
-576460752303423488
prop_binary_iso: ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 588 tests.
-576460752303423488
[prop_list_iso,prop_binary_iso]
9>


--
J.

_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs
Reply | Threaded
Open this post in threaded view
|

Re: Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

Lukas Larsson-8
Hello Jesper,

There seems to be a bug in the generic c-code for binary/list_to_integer for that specific value where a bignum is returned when a small should have been returned. If no-one feels like submitting a patch to fix it, I'll take a look later this week.

Thanks for the bug report!

Lukas
On 18/08/14 14:36, Jesper Louis Andersen wrote:
Hi,

While working on transit-erlang, Isaiah Peng and I found what we believe to be a bug in the Erlang compiler:

9> A = -576460752303423488.
-576460752303423488
10> B = binary_to_integer(integer_to_binary(A)).
-576460752303423488
11> A == B.
false
12> A.
-576460752303423488
13> B.
-576460752303423488
14>

I expected command 11 (A == B) to return true, as the numbers are the same. But it looks like constants are not treated the same way as converted vaues for some reason and the equality test fails.

This fails in the interpreter and in compiled code. It *also* fails with list_to_integer/1 and integer_to_list/1.  The number is not chosen arbitrarily. It is -1 * 2^59 which is a borderline number on a 64bit machine. (OTP release 17.1). Isaiah notes that these borderline numbers are not caught by the OTP test cases. They probably should be.

In the interest of full exploration, I've written a QuickCheck test case to catch the remaining trouble. It explicitly tests the borderline numbers and only finds this error.


-module(integer_coding).

-compile(export_all).

-include_lib("eqc/include/eqc.hrl").

power(_N, 0) -> 1;
power(N, P) -> N * power(N, P-1).

perturb() ->
    elements([0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]).

sign() ->
    elements([1, -1]).

nat_power() ->
    frequency([{1, elements([27, 28, 29, 31, 32, 33, 59, 60, 61, 63, 64, 65])},
               {1, nat()}]).

interesting_int() ->
    ?LET({K, Sign, Perturb}, {nat_power(), sign(), perturb()},
      power(2, K)*Sign + Perturb).

prop_binary_iso() ->
    ?FORALL(K, interesting_int(),
            begin
                I = binary_to_integer(integer_to_binary(K)),
                I == K
            end).

prop_list_iso() ->
    ?FORALL(K, interesting_int(),
            begin
                I = list_to_integer(integer_to_list(K)),
                I == K
            end).

all() ->
    eqc:module({numtests, 3000}, ?MODULE).

t() ->
    eqc:quickcheck(eqc:testing_time(300, prop_binary_iso())).


[...]

Produces:

8> integer_coding:all().
prop_list_iso: ..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................!
 ..........
.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 1498 tests.
-576460752303423488
prop_binary_iso: ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 588 tests.
-576460752303423488
[prop_list_iso,prop_binary_iso]
9>

--
J.


_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs


_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs
Reply | Threaded
Open this post in threaded view
|

Re: Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

Mikael Pettersson-5
Lukas Larsson writes:
 > Hello Jesper,
 >
 > There seems to be a bug in the generic c-code for binary/list_to_integer
 > for that specific value where a bignum is returned when a small should
 > have been returned. If no-one feels like submitting a patch to fix it,
 > I'll take a look later this week.
 >
 > Thanks for the bug report!

Using hipe_bifs:show_term/1 it's easy to determine why ==/2 fails:

1> A = -576460752303423488.
-576460752303423488
2> B = binary_to_integer(integer_to_binary(A)).
-576460752303423488
3> A == B.
false
4> hipe_bifs:show_term(A).
0x800000000000000f
-576460752303423488
true
5> hipe_bifs:show_term(B).
0x00007f4f8d4ae5fa
0x00007f4f8d4ae5f8: 0x000000000000004c
0x00007f4f8d4ae600: 0x0800000000000000
-576460752303423488
true

That is, A is a fixnum but B became a bignum.  That's not allowed
in the VM: every integer that fits in a fixnum MUST be a fixnum.

The bug also exists in R16B03-1.  R15 doesn't seem to have
integer_to_binary/1.


 >
 > Lukas
 > On 18/08/14 14:36, Jesper Louis Andersen wrote:
 > > Hi,
 > >
 > > While working on transit-erlang, Isaiah Peng and I found what we
 > > believe to be a bug in the Erlang compiler:
 > >
 > > 9> A = -576460752303423488.
 > > -576460752303423488
 > > 10> B = binary_to_integer(integer_to_binary(A)).
 > > -576460752303423488
 > > 11> A == B.
 > > false
 > > 12> A.
 > > -576460752303423488
 > > 13> B.
 > > -576460752303423488
 > > 14>
 > >
 > > I expected command 11 (A == B) to return true, as the numbers are the
 > > same. But it looks like constants are not treated the same way as
 > > converted vaues for some reason and the equality test fails.
 > >
 > > This fails in the interpreter and in compiled code. It *also* fails
 > > with list_to_integer/1 and integer_to_list/1.  The number is not
 > > chosen arbitrarily. It is -1 * 2^59 which is a borderline number on a
 > > 64bit machine. (OTP release 17.1). Isaiah notes that these borderline
 > > numbers are not caught by the OTP test cases. They probably should be.
 > >
 > > In the interest of full exploration, I've written a QuickCheck test
 > > case to catch the remaining trouble. It explicitly tests the
 > > borderline numbers and only finds this error.
 > >
 > > https://gist.github.com/jlouis/52b68d9d4150af3bd00c
 > >
 > > -module(integer_coding).
 > >
 > > -compile(export_all).
 > >
 > > -include_lib("eqc/include/eqc.hrl").
 > >
 > > power(_N, 0) -> 1;
 > > power(N, P) -> N * power(N, P-1).
 > >
 > > perturb() ->
 > >      elements([0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]).
 > >
 > > sign() ->
 > >      elements([1, -1]).
 > >
 > > nat_power() ->
 > >      frequency([{1, elements([27, 28, 29, 31, 32, 33, 59, 60, 61, 63, 64, 65])},
 > >                 {1, nat()}]).
 > >
 > > interesting_int() ->
 > >      ?LET({K, Sign, Perturb}, {nat_power(), sign(), perturb()},
 > >        power(2, K)*Sign + Perturb).
 > >
 > > prop_binary_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = binary_to_integer(integer_to_binary(K)),
 > >                  I == K
 > >              end).
 > >
 > > prop_list_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = list_to_integer(integer_to_list(K)),
 > >                  I == K
 > >              end).
 > >
 > > all() ->
 > >      eqc:module({numtests, 3000}, ?MODULE).
 > >
 > > t() ->
 > >      eqc:quickcheck(eqc:testing_time(300, prop_binary_iso())).
 > >
 > >
 > > [...]
 > >
 > > Produces:
 > >
 > > 8> integer_coding:all().
 > > prop_list_iso: ..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
 ...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 1498 tests.
 > > -576460752303423488
 > > prop_binary_iso: ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 588 tests.
 > > -576460752303423488
 > > [prop_list_iso,prop_binary_iso]
 > > 9>
 > >
 > > --
 > > J.
 > >
 > >
 > > _______________________________________________
 > > erlang-bugs mailing list
 > > [hidden email]
 > > http://erlang.org/mailman/listinfo/erlang-bugs
 >
 >
 > ----------------------------------------------------------------------
 > _______________________________________________
 > erlang-bugs mailing list
 > [hidden email]
 > http://erlang.org/mailman/listinfo/erlang-bugs

--
_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs
Reply | Threaded
Open this post in threaded view
|

Re: Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

Mikael Pettersson-5
In reply to this post by Lukas Larsson-8
Lukas Larsson writes:
 > Hello Jesper,
 >
 > There seems to be a bug in the generic c-code for binary/list_to_integer
 > for that specific value where a bignum is returned when a small should
 > have been returned. If no-one feels like submitting a patch to fix it,
 > I'll take a look later this week.

The bug in binary_to_integer is because of a (classic) algorithm
mistake in big.c:erts_chars_to_integer.  That code converts in
unsigned, keeping the representation as fixnum as long as possible,
and only at the very last step negates if the chars started with '-'.
However, for the largest permitted negative fixnum you'll have,
in the last step, a positive number that's just beyond the range
for fixnums, so it is represented as a bignum.  The negation step
just flips the sign bit, without checking if the negated value now
should be a fixnum.

I haven't looked at the list_to_integer case yet, but suspect it's
similar.

/Mikael

 >
 > Thanks for the bug report!
 >
 > Lukas
 > On 18/08/14 14:36, Jesper Louis Andersen wrote:
 > > Hi,
 > >
 > > While working on transit-erlang, Isaiah Peng and I found what we
 > > believe to be a bug in the Erlang compiler:
 > >
 > > 9> A = -576460752303423488.
 > > -576460752303423488
 > > 10> B = binary_to_integer(integer_to_binary(A)).
 > > -576460752303423488
 > > 11> A == B.
 > > false
 > > 12> A.
 > > -576460752303423488
 > > 13> B.
 > > -576460752303423488
 > > 14>
 > >
 > > I expected command 11 (A == B) to return true, as the numbers are the
 > > same. But it looks like constants are not treated the same way as
 > > converted vaues for some reason and the equality test fails.
 > >
 > > This fails in the interpreter and in compiled code. It *also* fails
 > > with list_to_integer/1 and integer_to_list/1.  The number is not
 > > chosen arbitrarily. It is -1 * 2^59 which is a borderline number on a
 > > 64bit machine. (OTP release 17.1). Isaiah notes that these borderline
 > > numbers are not caught by the OTP test cases. They probably should be.
 > >
 > > In the interest of full exploration, I've written a QuickCheck test
 > > case to catch the remaining trouble. It explicitly tests the
 > > borderline numbers and only finds this error.
 > >
 > > https://gist.github.com/jlouis/52b68d9d4150af3bd00c
 > >
 > > -module(integer_coding).
 > >
 > > -compile(export_all).
 > >
 > > -include_lib("eqc/include/eqc.hrl").
 > >
 > > power(_N, 0) -> 1;
 > > power(N, P) -> N * power(N, P-1).
 > >
 > > perturb() ->
 > >      elements([0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]).
 > >
 > > sign() ->
 > >      elements([1, -1]).
 > >
 > > nat_power() ->
 > >      frequency([{1, elements([27, 28, 29, 31, 32, 33, 59, 60, 61, 63, 64, 65])},
 > >                 {1, nat()}]).
 > >
 > > interesting_int() ->
 > >      ?LET({K, Sign, Perturb}, {nat_power(), sign(), perturb()},
 > >        power(2, K)*Sign + Perturb).
 > >
 > > prop_binary_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = binary_to_integer(integer_to_binary(K)),
 > >                  I == K
 > >              end).
 > >
 > > prop_list_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = list_to_integer(integer_to_list(K)),
 > >                  I == K
 > >              end).
 > >
 > > all() ->
 > >      eqc:module({numtests, 3000}, ?MODULE).
 > >
 > > t() ->
 > >      eqc:quickcheck(eqc:testing_time(300, prop_binary_iso())).
 > >
 > >
 > > [...]
 > >
 > > Produces:
 > >
 > > 8> integer_coding:all().
 > > prop_list_iso: ..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
 ...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 1498 tests.
 > > -576460752303423488
 > > prop_binary_iso: ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 588 tests.
 > > -576460752303423488
 > > [prop_list_iso,prop_binary_iso]
 > > 9>
 > >
 > > --
 > > J.
 > >
 > >
 > > _______________________________________________
 > > erlang-bugs mailing list
 > > [hidden email]
 > > http://erlang.org/mailman/listinfo/erlang-bugs
 >
 >
 > ----------------------------------------------------------------------
 > _______________________________________________
 > erlang-bugs mailing list
 > [hidden email]
 > http://erlang.org/mailman/listinfo/erlang-bugs

--
_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs
Reply | Threaded
Open this post in threaded view
|

Re: Problem with binary_to_integer/1 and list_to_integer/1 (QuickCheck test case)

Mikael Pettersson-5
In reply to this post by Lukas Larsson-8
Lukas Larsson writes:
 > Hello Jesper,
 >
 > There seems to be a bug in the generic c-code for binary/list_to_integer
 > for that specific value where a bignum is returned when a small should
 > have been returned. If no-one feels like submitting a patch to fix it,
 > I'll take a look later this week.

I have a patch for 17.1 which I intend to submit later today or tomorrow.
It fixes both binary_to_integer and list_to_integer.

/Mikael

 >
 > Thanks for the bug report!
 >
 > Lukas
 > On 18/08/14 14:36, Jesper Louis Andersen wrote:
 > > Hi,
 > >
 > > While working on transit-erlang, Isaiah Peng and I found what we
 > > believe to be a bug in the Erlang compiler:
 > >
 > > 9> A = -576460752303423488.
 > > -576460752303423488
 > > 10> B = binary_to_integer(integer_to_binary(A)).
 > > -576460752303423488
 > > 11> A == B.
 > > false
 > > 12> A.
 > > -576460752303423488
 > > 13> B.
 > > -576460752303423488
 > > 14>
 > >
 > > I expected command 11 (A == B) to return true, as the numbers are the
 > > same. But it looks like constants are not treated the same way as
 > > converted vaues for some reason and the equality test fails.
 > >
 > > This fails in the interpreter and in compiled code. It *also* fails
 > > with list_to_integer/1 and integer_to_list/1.  The number is not
 > > chosen arbitrarily. It is -1 * 2^59 which is a borderline number on a
 > > 64bit machine. (OTP release 17.1). Isaiah notes that these borderline
 > > numbers are not caught by the OTP test cases. They probably should be.
 > >
 > > In the interest of full exploration, I've written a QuickCheck test
 > > case to catch the remaining trouble. It explicitly tests the
 > > borderline numbers and only finds this error.
 > >
 > > https://gist.github.com/jlouis/52b68d9d4150af3bd00c
 > >
 > > -module(integer_coding).
 > >
 > > -compile(export_all).
 > >
 > > -include_lib("eqc/include/eqc.hrl").
 > >
 > > power(_N, 0) -> 1;
 > > power(N, P) -> N * power(N, P-1).
 > >
 > > perturb() ->
 > >      elements([0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5]).
 > >
 > > sign() ->
 > >      elements([1, -1]).
 > >
 > > nat_power() ->
 > >      frequency([{1, elements([27, 28, 29, 31, 32, 33, 59, 60, 61, 63, 64, 65])},
 > >                 {1, nat()}]).
 > >
 > > interesting_int() ->
 > >      ?LET({K, Sign, Perturb}, {nat_power(), sign(), perturb()},
 > >        power(2, K)*Sign + Perturb).
 > >
 > > prop_binary_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = binary_to_integer(integer_to_binary(K)),
 > >                  I == K
 > >              end).
 > >
 > > prop_list_iso() ->
 > >      ?FORALL(K, interesting_int(),
 > >              begin
 > >                  I = list_to_integer(integer_to_list(K)),
 > >                  I == K
 > >              end).
 > >
 > > all() ->
 > >      eqc:module({numtests, 3000}, ?MODULE).
 > >
 > > t() ->
 > >      eqc:quickcheck(eqc:testing_time(300, prop_binary_iso())).
 > >
 > >
 > > [...]
 > >
 > > Produces:
 > >
 > > 8> integer_coding:all().
 > > prop_list_iso: ..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
 ...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 1498 tests.
 > > -576460752303423488
 > > prop_binary_iso: ...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Failed! After 588 tests.
 > > -576460752303423488
 > > [prop_list_iso,prop_binary_iso]
 > > 9>
 > >
 > > --
 > > J.
 > >
 > >
 > > _______________________________________________
 > > erlang-bugs mailing list
 > > [hidden email]
 > > http://erlang.org/mailman/listinfo/erlang-bugs
 >
 >
 > ----------------------------------------------------------------------
 > _______________________________________________
 > erlang-bugs mailing list
 > [hidden email]
 > http://erlang.org/mailman/listinfo/erlang-bugs

--
_______________________________________________
erlang-bugs mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-bugs