Add binary:longest_common_prefix/longest_common_suffix

Add allcoator parameter to erts_get_aligned_binary_bytes_extra.
Add testcases for the functions above.
Add reference implementation for the functions above.

2 files changed, 155 insertions, 1 deletions

diff --git a/lib/stdlib/test/binary_module_SUITE.erl b/lib/stdlib/test/binary_module_SUITE.erl
index 24545f296a..5ab9bb7b25 100644
--- a/lib/stdlib/test/binary_module_SUITE.erl
+++ b/lib/stdlib/test/binary_module_SUITE.erl
@@ -179,6 +179,88 @@ do_interesting(Module) ->
 					      [<<4,5>>,<<7>>,<<8>>],<<>>,
 					      [global,{scope,{0,5}},
 					       {insert_replaced,1}])),
+    ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>]),
+    ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2>>]),
+    ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1>>]),
+    ?line 0 = Module:longest_common_prefix([<<1,2,4>>,<<>>]),
+    ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>]),
+    ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>,<<1,2,4>>]),
+    ?line 1251 = Module:longest_common_prefix([<<0:10000,1,2,4>>,
+					       <<0:10000,1,2,3>>,
+					       <<0:10000,1,3,3>>,
+					       <<0:10000,1,2,4>>]),
+    ?line 12501 = Module:longest_common_prefix([<<0:100000,1,2,4>>,
+						<<0:100000,1,2,3>>,
+						<<0:100000,1,3,3>>,
+						<<0:100000,1,2,4>>]),
+    ?line 1251 = Module:longest_common_prefix(
+		   [make_unaligned(<<0:10000,1,2,4>>),
+		    <<0:10000,1,2,3>>,
+		    make_unaligned(<<0:10000,1,3,3>>),
+		    <<0:10000,1,2,4>>]),
+    ?line 12501 = Module:longest_common_prefix(
+		    [<<0:100000,1,2,4>>,
+		     make_unaligned(<<0:100000,1,2,3>>),
+		     <<0:100000,1,3,3>>,
+		     make_unaligned(<<0:100000,1,2,4>>)]),
+    ?line 1250001 = Module:longest_common_prefix([<<0:10000000,1,2,4>>,
+						  <<0:10000000,1,2,3>>,
+						  <<0:10000000,1,3,3>>,
+						  <<0:10000000,1,2,4>>]),
+    if % Too cruel for the reference implementation
+	Module =:= binary ->
+	    ?line 125000001 = Module:longest_common_prefix(
+				[<<0:1000000000,1,2,4>>,
+				 <<0:1000000000,1,2,3>>,
+				 <<0:1000000000,1,3,3>>,
+				 <<0:1000000000,1,2,4>>]);
+	true ->
+	    ok
+    end,
+    ?line 1 = Module:longest_common_suffix([<<0:1000000000,1,2,4,5>>,
+					    <<0:1000000000,1,2,3,5>>,
+					    <<0:1000000000,1,3,3,5>>,
+					    <<0:1000000000,1,2,4,5>>]),
+    ?line 1 = Module:longest_common_suffix([<<1,2,4,5>>,
+					    <<0:1000000000,1,2,3,5>>,
+					    <<0:1000000000,1,3,3,5>>,
+					    <<0:1000000000,1,2,4,5>>]),
+    ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+					    <<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5>>]),
+    ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+					    <<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4>>]),
+    ?line 2 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+					    <<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5>>,
+					    <<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<>>,
+					    <<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 2 = Module:longest_common_suffix([<<5,5>>,<<0:1000000000,1,3,3,5,5>>,
+					    <<0:1000000000,1,2,4,5,5>>]),
+    ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<4,5,5>>]),
+    ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<5,5>>]),
+    ?line 3 = Module:longest_common_suffix([<<4,5,5>>,<<4,5,5>>,<<4,5,5>>]),
+    ?line 0 = Module:longest_common_suffix([<<>>]),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([apa])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<>>]])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<0>>,
+							      <<1:9>>]])),
+    ?line 0 = Module:longest_common_prefix([<<>>]),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([apa])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<>>]])),
+    ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<0>>,
+							      <<1:9>>]])),
     ok.
 
 parts(doc) ->
diff --git a/lib/stdlib/test/binref.erl b/lib/stdlib/test/binref.erl
index 484112428c..e98b1b2bc8 100644
--- a/lib/stdlib/test/binref.erl
+++ b/lib/stdlib/test/binref.erl
@@ -3,7 +3,8 @@
 -export([compile_pattern/1,match/2,match/3,matches/2,matches/3,
 	 split/2,split/3,replace/3,replace/4,first/1,last/1,at/2,
 	 part/2,part/3,copy/1,copy/2,encode_unsigned/1,encode_unsigned/2,
-	 decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1]).
+	 decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1,
+	 longest_common_prefix/1,longest_common_suffix/1 ]).
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -319,6 +320,77 @@ at(Subject,X) ->
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% longest_common_prefix
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+longest_common_prefix(LB) ->
+    try
+	true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause
+	do_longest_common_prefix(LB,0)
+    catch
+	_:_ ->
+	    erlang:error(badarg)
+    end.
+
+do_longest_common_prefix(LB,X) ->
+    case do_lcp(LB,X,no) of
+	true ->
+	    do_longest_common_prefix(LB,X+1);
+	false ->
+	    X
+    end.
+do_lcp([],_,_) ->
+    true;
+do_lcp([Bin|_],X,_) when byte_size(Bin) =< X ->
+    false;
+do_lcp([Bin|T],X,no) ->
+    Ch = at(Bin,X),
+    do_lcp(T,X,Ch);
+do_lcp([Bin|T],X,Ch) ->
+    Ch2 = at(Bin,X),
+    if
+	Ch =:= Ch2 ->
+	    do_lcp(T,X,Ch);
+	true ->
+	    false
+    end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% longest_common_suffix
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+longest_common_suffix(LB) ->
+    try
+	true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause
+	do_longest_common_suffix(LB,0)
+    catch
+	_:_ ->
+	    erlang:error(badarg)
+    end.
+
+do_longest_common_suffix(LB,X) ->
+    case do_lcs(LB,X,no) of
+	true ->
+	    do_longest_common_suffix(LB,X+1);
+	false ->
+	    X
+    end.
+do_lcs([],_,_) ->
+    true;
+do_lcs([Bin|_],X,_) when byte_size(Bin) =< X ->
+    false;
+do_lcs([Bin|T],X,no) ->
+    Ch = at(Bin,byte_size(Bin) - 1 - X),
+    do_lcs(T,X,Ch);
+do_lcs([Bin|T],X,Ch) ->
+    Ch2 = at(Bin,byte_size(Bin) - 1 - X),
+    if
+	Ch =:= Ch2 ->
+	    do_lcs(T,X,Ch);
+	true ->
+	    false
+    end.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% part
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 part(Subject,Part) ->