INCOMPATIBILITY: changed encoding of bignums

uwiger · uwiger · commit ff10beb7a791 · 2013-03-05T17:54:27.000+01:00
Bignums were encoded in a way that didn't preserve the sorting property.

To fix this, I have prepended a length indicator. In order to be
able to read legacy-encoded bignums, I made use of the fact that
the first byte returned in the return value from encode_big1/1
was never &gt; 254. Thus, 255 is used to indicate the new format. I.e.
&lt;&lt;11, 255, ...length indicator..., ...encoded bignum...&gt;&gt;

The length indicator gives the number of bytes, and will usually
be one byte long. If the number of bytes is &gt; 127, the length
indicator will be encoded as a sequence of 7-bit "septets", where
each except the last is tagged with 1 in the MSB.

The decode function removes the size indicator, and also recognizes
that if the first byte is =&lt; 254, there is no size indicator,
and decodes a legacy bignum.

This means that a data set can be converted by simply decoding and
encoding each value.

For further backwards compatibility, the function
sext:legacy_encode_bignum/1 encodes a bignum in the old format.
diff --git a/src/sext.erl b/src/sext.erl
@@ -28,6 +28,8 @@
 -export([to_sb32/1, from_sb32/1]).
 -export([to_hex/1, from_hex/1]).
 
+-export([legacy_encode_bignum/1]).
+
 -define(negbig   , 8).
 -define(neg4     , 9).
 -define(pos4     , 10).
@@ -422,15 +424,83 @@ encode_neg_int(I,R) when I < -16#7fFFffFF ->
 %%      RAdj = MaxR - Ri,
 %%     ?dbg("RAdj = ~p~n", [<<RAdj:Sz>>]),
 %%     encode_bits_elems(<<RAdj:Sz>>).
+legacy_encode_bignum(I) when is_integer(I), I > 16#7fffffff ->
+    Bl = encode_big1(I),
+    ?dbg("Bl = ~p~n", [Bl]),
+    Bb = list_to_binary(Bl),
+    ?dbg("Bb = ~p~n", [Bb]),
+    <<?posbig, (encode_bin_elems(Bb))/binary, 0:8>>.
 
 
 encode_big(I) ->
     Bl = encode_big1(I),
     ?dbg("Bl = ~p~n", [Bl]),
-    Bb = list_to_binary(Bl),
+    Bb = prepend_size(list_to_binary(Bl)),
     ?dbg("Bb = ~p~n", [Bb]),
     encode_bin_elems(Bb).
 
+prepend_size(B) ->
+    Sz = byte_size(B),
+    <<255, (encode_size(Sz))/binary, B/binary>>.
+
+remove_size_bits(<<255, T/binary>>) ->
+    {_, Rest} = untag_7bits(T, <<>>),
+    Rest;
+remove_size_bits(B) ->
+    %% legacy bignum
+    B.
+
+
+encode_size(I) when I > 127 ->
+    B = int_to_binary(I),
+    tag_7bits(B);
+    %% %% <<1:1, (I band 127):7, (encode_size(I bsr 7))/binary>>;
+    %% <<1:1, (H - 127):7, (encode_size(I bsr 8))/binary>>;
+encode_size(I) ->
+    <<I>>.
+
+tag_7bits(B) when bit_size(B) > 7 ->
+    <<H:7, T/bitstring>> = B,
+    <<1:1, H:7, (tag_7bits(T))/binary>>;
+tag_7bits(B) ->
+    Sz = bit_size(B),
+    <<I:Sz>> = B,
+    <<0:1, I:7>>.
+
+untag_7bits(<<1:1, H:7, T/binary>>, Acc) ->
+    untag_7bits(T, <<Acc/bitstring, H:7>>);
+untag_7bits(<<0:1, H:7, T/binary>>, Acc) ->
+    AccBits = bit_size(Acc),
+    HBits = 8 - (AccBits rem 8),
+    {<<Acc/bitstring, H:HBits>>, T}.
+
+
+int_to_binary(I) when I =< 16#ff -> <<I:8>>;
+int_to_binary(I) when I =< 16#ffff -> <<I:16>>;
+int_to_binary(I) when I =< 16#ffffff -> <<I:24>>;
+int_to_binary(I) when I =< 16#ffffffff -> <<I:32>>;
+int_to_binary(I) when I =< 16#ffffffffff -> <<I:40>>;
+int_to_binary(I) when I =< 16#ffffffffffff -> <<I:48>>;
+int_to_binary(I) when I =< 16#ffffffffffffff -> <<I:56>>;
+int_to_binary(I) when I =< 16#ffffffffffffffff -> <<I:64>>;
+int_to_binary(I) ->
+    %% Realm of the ridiculous
+    list_to_binary(
+      lists:dropwhile(fun(X) -> X==0 end, binary_to_list(<<I:256>>))).
+
+
+%% This function exists for documentation, but not used right now.
+%% It's the reverse of encode_size/1, used for encoding bignums.
+%%
+%% decode_size(<<1:1, _/bitstring>> = T) ->
+%%     {SzBin, Rest} = untag_7bits(T, <<>>),
+%%     Bits = bit_size(SzBin),
+%%     <<Sz:Bits>> = SzBin,
+%%     {Sz, Rest};
+%% decode_size(<<0:1, H:7, T/binary>>) ->
+%%     {H, T}.
+
+
 encode_big_neg(I) ->
     {Words, Max} = get_max(-I),
     ?dbg("Words = ~p | Max = ~p~n", [Words,Max]),
@@ -735,7 +805,8 @@ decode_pos(I, 1, Bin) ->	% float > 1
 
 decode_pos_big(Bin) ->
     ?dbg("decode_pos_big(~p)~n", [Bin]),
-    {Ib, Rest} = decode_binary(Bin),
+    {Ib0, Rest} = decode_binary(Bin),
+    Ib = remove_size_bits(Ib0),
     ?dbg("Ib = ~p~n", [Ib]),
     ISz = size(Ib) * 8,
     ?dbg("ISz = ~p~n", [ISz]),
diff --git a/test/sext_eqc.erl b/test/sext_eqc.erl
@@ -27,6 +27,7 @@ sext_test_() ->
     {timeout, 60,
      [
       fun() -> t(run(N, prop_encode, fun prop_encode/0)) end
+      , fun() -> t(run(N, prop_decode_legacy_big, fun prop_decode_legacy_big/0)) end
       , fun() -> t(run(N, prop_prefix_equiv,fun prop_prefix_equiv/0))end
       , fun() -> t(run(N, prop_sort, fun prop_sort/0)) end
       , fun() -> t(run(N, prop_encode_sb32, fun prop_encode_sb32/0)) end
@@ -51,9 +52,12 @@ good_number_of_tests() ->
 
 run(Num) ->
     [
-     run (Num, prop_encode , fun prop_encode/0)
+     run  (Num, prop_encode , fun prop_encode/0)
+     , run(Num, prop_decode_legacy_big, fun prop_decode_legacy_big/0)
      , run(Num, prop_prefix_equiv,fun prop_prefix_equiv/0)
-     , run(Num, prop_sort , fun prop_encode/0)
+     %% , run(Num, prop_prefix_equiv,fun prop_prefix_equiv/0)
+     , run(Num, prop_sort , fun prop_sort/0)
+     , run(Num, prop_sort_big, fun prop_sort_big/0)
      , run(Num, prop_encode_sb32, fun prop_encode_sb32/0)
      , run(Num, prop_sort_sb32 , fun prop_sort_sb32/0)
      , run(Num, prop_is_prefix1, fun prop_is_prefix1/0)
@@ -82,6 +86,14 @@ prop_sort() ->
                         comp(X1,X2) == comp_i(T1,T2))
             end).
 
+prop_sort_big() ->
+    ?FORALL({T1,T2}, {big(), big()},
+            begin
+                {X1,X2} = {sext:encode(T1), sext:encode(T2)},
+                collect(size(term_to_binary({T1,T2})),
+                        comp(X1,X2) == comp_i(T1,T2))
+            end).
+
 prop_sort_sb32() ->
     ?FORALL({T1,T2}, {term(), term()},
             begin
@@ -117,6 +129,10 @@ prop_encode() ->
     ?FORALL(T, term(),
             sext:decode(sext:encode(T)) == T).
 
+prop_decode_legacy_big() ->
+    ?FORALL(T, big(),
+	    sext:decode(sext:legacy_encode_bignum(T)) == T).
+
 prop_encode_sb32() ->
     ?FORALL(T, term(),
             sext:decode_sb32(sext:encode_sb32(T)) == T).
