1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2000-2016. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21%%
22%% Verifying erlang:phash/2. And now also phash2/2, to some extent.
23%% Test the hashing algorithm for integer numbers in 2 ways:
24%% 1 Test that numbers in diferent sequences get sufficiently spread
25%%   in a "bit pattern" way (modulo 256 etc).
26%% 2 Test that numbers are correctly hashed compared to a reference implementation,
27%%   regardless of their internal representation. The hashing algorithm should never
28%%   change.
29%% The hashing of other datatypes is tested with a few samples, so that we are sure
30%% it does not change across versions.
31%% Also tests that the limit can be between 0 and 16#FFFFFFFF.
32%%
33-module(hash_SUITE).
34-export([basic_test/0,cmp_test/1,range_test/0,spread_test/1,
35	 phash2_test/0, otp_5292_test/0,
36         otp_7127_test/0,
37         run_phash2_benchmarks/0,
38         test_phash2_binary_aligned_and_unaligned_equal/1,
39         test_phash2_4GB_plus_bin/1,
40         test_phash2_10MB_plus_bin/1,
41         test_phash2_large_map/1,
42         test_phash2_shallow_long_list/1,
43         test_phash2_deep_list/1,
44         test_phash2_deep_tuple/1,
45         test_phash2_deep_tiny/1,
46         test_phash2_with_42/1,
47         test_phash2_with_short_tuple/1,
48         test_phash2_with_short_list/1,
49         test_phash2_with_tiny_bin/1,
50         test_phash2_with_tiny_unaligned_sub_binary/1,
51         test_phash2_with_small_unaligned_sub_binary/1,
52         test_phash2_with_large_bin/1,
53         test_phash2_with_large_unaligned_sub_binary/1,
54         test_phash2_with_super_large_unaligned_sub_binary/1]).
55
56%%
57%% Define to run outside of test server
58%%
59%-define(STANDALONE,1).
60
61%%
62%% Define for debug output
63%%
64-define(debug,1).
65
66-ifdef(STANDALONE).
67-define(config(A,B),config(A,B)).
68-record(event, {name, data}).
69-export([config/2]).
70-else.
71-include_lib("common_test/include/ct.hrl").
72-include_lib("common_test/include/ct_event.hrl").
73-endif.
74
75-ifdef(debug).
76-ifdef(STANDALONE).
77-define(line, erlang:display({?MODULE,?LINE}), ).
78-endif.
79-define(dbgformat(A,B),io:format(A,B)).
80-else.
81-ifdef(STANDALONE).
82-define(line, noop, ).
83-endif.
84-define(dbgformat(A,B),noop).
85-endif.
86
87-ifdef(STANDALONE).
88config(priv_dir,_) ->
89    ".".
90notify(X) ->
91    erlang:display(X).
92-else.
93%% When run in test server.
94-export([groups/0, all/0, suite/0,
95	 test_basic/1,test_cmp/1,test_range/1,test_spread/1,
96	 test_phash2/1,otp_5292/1,bit_level_binaries/1,otp_7127/1,
97         test_hash_zero/1, init_per_suite/1, end_per_suite/1,
98         init_per_group/2, end_per_group/2]).
99
100suite() ->
101    [{ct_hooks,[ts_install_cth]},
102     {timetrap, {minutes, 10}}].
103
104all() ->
105    [test_basic, test_cmp, test_range, test_spread,
106     test_phash2, otp_5292, bit_level_binaries, otp_7127,
107     test_hash_zero, test_phash2_binary_aligned_and_unaligned_equal,
108     test_phash2_4GB_plus_bin,
109     test_phash2_10MB_plus_bin,
110     {group, phash2_benchmark_tests},
111     {group, phash2_benchmark}].
112
113get_phash2_benchmarks() ->
114    [
115     test_phash2_large_map,
116     test_phash2_shallow_long_list,
117     test_phash2_deep_list,
118     test_phash2_deep_tuple,
119     test_phash2_deep_tiny,
120     test_phash2_with_42,
121     test_phash2_with_short_tuple,
122     test_phash2_with_short_list,
123     test_phash2_with_tiny_bin,
124     test_phash2_with_tiny_unaligned_sub_binary,
125     test_phash2_with_small_unaligned_sub_binary,
126     test_phash2_with_large_bin,
127     test_phash2_with_large_unaligned_sub_binary,
128     test_phash2_with_super_large_unaligned_sub_binary
129    ].
130
131groups() ->
132    [
133     {
134      phash2_benchmark_tests,
135      [],
136      get_phash2_benchmarks()
137     },
138     {
139      phash2_benchmark,
140      [],
141      get_phash2_benchmarks()
142     }
143    ].
144
145
146init_per_suite(Config) ->
147    io:format("START APPS~n"),
148    A0 = case application:start(sasl) of
149	     ok -> [sasl];
150	     _ -> []
151	 end,
152    A = case application:start(os_mon) of
153	     ok -> [os_mon|A0];
154	     _ -> A0
155	 end,
156    io:format("APPS STARTED~n"),
157    [{started_apps, A}|Config].
158
159end_per_suite(Config) ->
160    As = proplists:get_value(started_apps, Config),
161    lists:foreach(fun (A) -> application:stop(A) end, As),
162    Config.
163
164init_per_group(phash2_benchmark_tests, Config) ->
165    [phash2_benchmark_tests |Config];
166init_per_group(_, Config) ->
167    Config.
168
169end_per_group(_, Config) ->
170    Config.
171
172
173%% Tests basic functionality of erlang:phash and that the
174%% hashes has not changed (neither hash nor phash)
175test_basic(Config) when is_list(Config) ->
176    basic_test().
177
178
179%% Compares integer hashes made by erlang:phash with those of a reference implementation
180test_cmp(Config) when is_list(Config) ->
181    cmp_test(10000).
182
183%% Tests ranges on erlang:phash from 1 to 2^32
184test_range(Config) when is_list(Config) ->
185    range_test().
186
187%% Tests that the hashes are spread ok
188test_spread(Config) when is_list(Config) ->
189    spread_test(10).
190
191%% Tests phash2
192test_phash2(Config) when is_list(Config) ->
193    phash2_test().
194
195%% Tests hash, phash and phash2 regarding integers.
196otp_5292(Config) when is_list(Config) ->
197    otp_5292_test().
198
199%% Test hashing bit-level binaries.
200bit_level_binaries(Config) when is_list(Config) ->
201    bit_level_binaries_do().
202
203%% Tests phash2/1.
204otp_7127(Config) when is_list(Config) ->
205    otp_7127_test().
206
207test_hash_zero(Config) when is_list(Config) ->
208    hash_zero_test().
209
210notify(X) ->
211    ct_event:notify(X).
212-endif.
213
214
215
216%%
217%% Here are the real tests, they can be run without test_server,
218%% define -DSTANDALONE when compiling.
219%%
220basic_test() ->
221    685556714 = erlang:phash({a,b,c},16#FFFFFFFF),
222    37442646 =  erlang:phash([a,b,c,{1,2,3},c:pid(0,2,3),
223				    16#77777777777777],16#FFFFFFFF),
224    ExternalReference = <<131,114,0,3,100,0,13,110,111,110,111,100,101,64,
225			 110,111,104,111,115,116,0,0,0,0,122,0,0,0,0,0,0,0,0>>,
226    ExternalReference = <<131,114,0,3,100,0,13,110,111,110,111,100,101,64,
227			 110,111,104,111,115,116,0,0,0,0,122,0,0,0,0,0,0,0,0>>,
228    1113403635 = phash_from_external(ExternalReference),
229
230    ExternalFun = <<131,112,0,0,0,70,1,212,190,220,28,179,144,194,131,
231                    19,215,105,97,77,251,125,93,0,0,0,0,0,0,0,2,100,0,1,
232                    116,97,0,98,6,165,246,224,103,100,0,13,110,111,
233                    110,111,100,101,64,110,111,104,111,115,116,0,0,0,91,
234                    0,0,0,0,0,97,2,97,1>>,
235    25769064 = phash_from_external(ExternalFun),
236
237    case (catch erlang:phash(1,0)) of
238	{'EXIT',{badarg, _}} ->
239	    ok;
240	_ ->
241	    exit(phash_accepted_zero_as_range)
242    end.
243
244phash_from_external(Ext) ->
245    erlang:phash(binary_to_term(Ext), 16#FFFFFFFF).
246
247range_test() ->
248    F = fun(From,From,_FF) ->
249		ok;
250	   (From,To,FF) ->
251		R = rand:uniform(16#FFFFFFFFFFFFFFFF),
252		X = erlang:phash(R, From),
253		Y = erlang:phash(R, 16#100000000) - 1,
254		Z = (Y rem From) + 1,
255		case X =:= Z of
256		    true ->
257			FF(From*2,To,FF);
258		    _ ->
259			exit({range_test_failed, hash_on, R, range, From})
260		end
261	end,
262    F(1,16#100000000,F).
263
264
265spread_test(N) ->
266    test_fun(N,{erlang,phash},16#50000000000,fun(X) ->
267						     X
268					     end),
269    test_fun(N,{erlang,phash},0,fun(X) ->
270					X
271				end),
272    test_fun(N,{erlang,phash},16#123456789ABCDEF123456789ABCDEF,fun(X) ->
273									X
274								end),
275    test_fun(N,{erlang,phash},16#50000000000,fun(X) ->
276						     integer_to_list(X)
277					     end),
278    test_fun(N,{erlang,phash},16#50000000000,fun(X) ->
279						     integer_to_bytelist(X,[])
280					     end),
281    test_fun(N,{erlang,phash},16#50000000000,fun(X) ->
282						     integer_to_binary_value(X)
283					     end).
284
285
286
287cmp_test(N) ->
288    do_cmp_hashes(N,8).
289
290do_cmp_hashes(0,_) ->
291    ok;
292do_cmp_hashes(N,Steps) ->
293    R0 = rand:uniform(1 bsl Steps - 1) + rand:uniform(16#FFFFFFFF),
294    R = case rand:uniform(2) of
295	    1 ->
296		R0;
297	    _ ->
298		-R0
299	end,
300    NSteps = case N rem 10 of
301		 0 ->
302		     case (Steps + 8) rem 1024 of
303			 0 ->
304			     8;
305			 OK ->
306			     OK
307		     end;
308		 _ ->
309		     Steps
310	     end,
311    X = erlang:phash(R,16#FFFFFFFF),
312    Y = make_hash(R,16#FFFFFFFF),
313    case X =:= Y of
314	true ->
315	    do_cmp_hashes(N - 1, NSteps);
316	_ ->
317	    exit({missmatch_on_input, R, phash, X, make_hash, Y})
318    end.
319
320phash2_test() ->
321    Max = 1 bsl 32,
322    BPort = <<131,102,100,0,13,110,111,110,111,100,101,64,110,111,104,
323              111,115,116,0,0,0,1,0>>,
324    Port = binary_to_term(BPort),
325
326    BXPort = <<131,102,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
327               0,0,0,24,3>>,
328    XPort = binary_to_term(BXPort),
329
330    BRef = <<131,114,0,3,100,0,13,110,111,110,111,100,101,64,110,111,104,
331             111,115,116,0,0,0,1,255,0,0,0,0,0,0,0,0>>,
332    Ref = binary_to_term(BRef),
333
334    BXRef = <<131,114,0,3,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
335              2,0,0,0,155,0,0,0,0,0,0,0,0>>,
336    XRef = binary_to_term(BXRef),
337
338    BXPid = <<131,103,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
339              0,0,0,36,0,0,0,0,1>>,
340    XPid = binary_to_term(BXPid),
341
342
343    %% X = f1(), Y = f2(), Z = f3(X, Y),
344
345    %% F1 = fun f1/0, % -> abc
346    B1 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
347           13,196,76,242,0,0,0,1,0,0,0,0,100,0,1,116,97,1,98,2,195,126,
348           58,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
349           115,116,0,0,0,112,0,0,0,0,0>>,
350    F1 = binary_to_term(B1),
351
352    %% F2 = fun f2/0, % -> abd
353    B2 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
354           13,196,76,242,0,0,0,2,0,0,0,0,100,0,1,116,97,2,98,3,130,152,
355           185,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
356           115,116,0,0,0,112,0,0,0,0,0>>,
357    F2 = binary_to_term(B2),
358
359    %% F3 = fun f3/2, % -> {abc, abd}
360    B3 = <<131,112,0,0,0,66,2,215,206,77,69,249,50,170,17,129,47,21,98,
361           13,196,76,242,0,0,0,3,0,0,0,0,100,0,1,116,97,3,98,7,168,160,
362           93,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
363           115,116,0,0,0,112,0,0,0,0,0>>,
364    F3 = binary_to_term(B3),
365
366    %% F4 = fun () -> 123456789012345678901234567 end,
367    B4 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
368           13,196,76,242,0,0,0,4,0,0,0,0,100,0,1,116,97,4,98,2,230,21,
369           171,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
370           115,116,0,0,0,112,0,0,0,0,0>>,
371    F4 = binary_to_term(B4),
372
373    %% F5 = fun() -> {X,Y,Z} end,
374    B5 = <<131,112,0,0,0,92,0,215,206,77,69,249,50,170,17,129,47,21,98,
375           13,196,76,242,0,0,0,5,0,0,0,3,100,0,1,116,97,5,98,0,99,101,
376           130,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
377           115,116,0,0,0,112,0,0,0,0,0,100,0,3,97,98,99,100,0,3,97,98,
378           100,104,2,100,0,3,97,98,99,100,0,3,97,98,100>>,
379    F5 = binary_to_term(B5),
380
381    Chars = lists:seq(32,127),
382    NotAHeapBin = list_to_binary(lists:flatten(lists:duplicate(500,Chars))),
383    <<_:128,SubBin/binary>> = NotAHeapBin,
384    L = [%% nil
385	 {[], 3468870702},
386
387	 %% atom :( not very good ):
388         %% (cannot use block_hash due to compatibility issues...)
389	 {abc,26499},
390	 {abd,26500},
391	 {'åäö', 62518},
392	 %% 81 runes as an atom, 'ᚠᚡᚢᚣᚤᚥᚦᚧᚨᚩᚪᚫᚬᚭᚮᚯᚰᚱᚲᚳᚴᚵᚶᚷᚸᚹᚺᚻᚼᚽᚾᚿᛀᛁᛂᛃᛄᛅᛆᛇᛈᛉᛊᛋᛌᛍᛎᛏᛐᛑᛒᛓᛔᛕᛖᛗᛘᛙᛚᛛᛜᛝᛞᛟᛠᛡᛢᛣᛤᛥᛦᛧᛨᛩᛪ᛫᛬᛭ᛮᛯᛰ'
393	 {erlang:binary_to_term(<<131, 118, 0, 243, (unicode:characters_to_binary(lists:seq(5792, 5872)))/binary >>), 241561024},
394	 %% åäö dynamic
395	 {erlang:binary_to_term(<<131, 118, 0, 6, 195, 165, 195, 164, 195, 182>>),62518},
396	 %% the atom '゙゚゛゜ゝゞゟ゠ァアィイゥウェエォオカガキギクグケゲコゴサザシジスズ'
397	 {erlang:binary_to_term(<<131, 118, 0, 102, (unicode:characters_to_binary(lists:seq(12441, 12542)))/binary>>), 246053818},
398	 %% the atom, '��'
399	 {erlang:binary_to_term(<<131, 118, 0, 4, 240, 159, 152, 131>>), 1026307},
400
401	 %% small
402	 {0,3175731469},
403	 {1, 539485162},
404	 {-1, 1117813597},
405	 {1 bsl 20, 1477815345},
406	 {-(1 bsl 20), 3076904293},
407
408	 %% bignum
409	 {4294967296, 2108323275},
410	 {-4294967296, 2586067094},
411	 {981494972710656, 1622082818},
412	 {-981494972710656, 3367191372},
413	 {36893488147419103232, 2545846594},
414	 {-36893488147419103232, 1649047068},
415	 {1606938044258990275541962092341162602522202993782792835301376,
416	  2573322433},
417	 {-1606938044258990275541962092341162602522202993782792835301376,
418	  2288753377},
419
420	 %% binary
421	 {<<>>, 147926629},
422	 {<<0:8>>, 2914887855},
423	 {<<0:32>>, 2014511533},
424	 {<<"abc">>, 1306188027},
425	 {<<"12345678901234567890">>, 3021061640},
426	 {NotAHeapBin,2644086993},
427	 {SubBin,3575839236},
428
429	 %% unaligned sub binaries
430	 {unaligned_sub_bin(<<>>), 147926629},
431	 {unaligned_sub_bin(<<0:8>>), 2914887855},
432	 {unaligned_sub_bin(<<0:32>>), 2014511533},
433	 {unaligned_sub_bin(<<"abc">>), 1306188027},
434	 {unaligned_sub_bin(<<"12345678901234567890">>), 3021061640},
435	 {unaligned_sub_bin(NotAHeapBin),2644086993},
436	 {unaligned_sub_bin(SubBin),3575839236},
437
438	 %% bit-level binaries
439	 {<<0:7>>, 1055790816},
440	 {(fun()-> B = <<255,7:3>>, <<_:4,D/bitstring>> = B, D end)(), 911751529},
441	 {<<"abc",13:4>>, 670412287},
442	 {<<5:3,"12345678901234567890">>, 289973273},
443
444	 %% fun
445	 {F1, 3826013332},
446	 {F2, 126009152},
447	 {F3, 3482452479},
448	 {F4, 633704783},
449	 {F5, 1241537408},
450
451	 %% module fun
452	 {fun lists:map/2, 840287883},
453 	 {fun lists:map/3, 2318478565},
454 	 {fun lists:filter/2, 635165125},
455 	 {fun lists:filter/3, 3824649396},
456 	 {fun xxx:map/2, 2630071865},
457 	 {fun xxx:map/3, 4237970519},
458
459	 %% pid
460	 {c:pid(0,0,0), 2858162279},
461	 {c:pid(0,1,0), 2870503209},
462	 {c:pid(0,2,0), 1707788908},
463	 {XPid, 1290188489},
464
465	 %% port
466	 {Port,1954394636},
467	 {XPort,274735},
468
469	 %% ref
470	 {Ref, 1675501484},
471	 {XRef, 3845846926},
472
473	 %% float
474	 {0.0, 423528920},
475	 {3.14, 3731709215},
476	 {-3.14, 1827518724},
477
478	 %% list
479	 {[0.0], 167906877},
480	 {[{}], 4050867804},
481	 {[<<>>], 440873397},
482	 {[[]], 499070068},
483	 {[abc], 3112446404},
484         {[a,b,c], 1505666924},
485	 {[a,b|c], 433753489},
486	 {"abc", 519996486},
487	 {"abc"++[1009], 290369864},
488	 {"abc"++[1009]++"de", 4134369195},
489	 {"1234567890123456", 963649519},
490
491	 %% tuple
492	 {{}, 221703996},
493	 {{{}}, 2165044361},
494	 {{<<>>}, 682464809},
495	 {{0.0}, 688441152},
496	 {{[]}, 1775079505},
497	 {{abc}, 2032039329},
498	 {{a,1,{},-3.14}, 1364396939},
499	 {{c:pid(0,2,0)}, 686997880},
500	 {{F4}, 2279632930},
501	 {{a,<<>>}, 2724468891},
502	 {{b,<<>>}, 2702508511}
503	],
504    SpecFun = fun(S) -> sofs:no_elements(S) > 1 end,
505    F = sofs:relation_to_family(sofs:converse(sofs:relation(L))),
506    D = sofs:to_external(sofs:family_specification(SpecFun, F)),
507    [] = D,
508    [] = [{E,H,H2} || {E,H} <- L, (H2 = erlang:phash2(E, Max)) =/= H],
509    ok.
510
511test_phash2_binary_aligned_and_unaligned_equal(Config) when is_list(Config) ->
512    erts_debug:set_internal_state(available_internal_state, true),
513    test_aligned_and_unaligned_equal_up_to(256*12+255),
514    erts_debug:set_internal_state(available_internal_state, false).
515
516test_aligned_and_unaligned_equal_up_to(BinSize) ->
517    Results =
518        lists:map(fun(Size) ->
519                          test_aligned_and_unaligned_equal(Size)
520                  end, lists:seq(1, BinSize)),
521    %% DataDir = filename:join(filename:dirname(code:which(?MODULE)), "hash_SUITE_data"),
522    %% ExpResFile = filename:join(DataDir, "phash2_bin_expected_results.txt"),
523    %% {ok, [ExpRes]} = file:consult(ExpResFile),
524    %% %% ok = file:write_file(ExpResFile, io_lib:format("~w.~n", [Results])),
525    %% Results = ExpRes,
526    110469206 = erlang:phash2(Results).
527
528test_aligned_and_unaligned_equal(BinSize) ->
529    Bin = make_random_bin(BinSize),
530    LastByte = last_byte(Bin),
531    LastInBitstring = LastByte rem 11,
532    Bitstring = << Bin/binary, <<LastInBitstring:5>>/bitstring >>,
533    UnalignedBin = make_unaligned_sub_bitstring(Bin),
534    UnalignedBitstring = make_unaligned_sub_bitstring(Bitstring),
535    case erts_debug:get_internal_state(available_internal_state) of
536        false -> erts_debug:set_internal_state(available_internal_state, true);
537        _ -> ok
538    end,
539    erts_debug:set_internal_state(reds_left, 3),
540    BinHash = erlang:phash2(Bin),
541    BinHash = erlang:phash2(Bin),
542    erts_debug:set_internal_state(reds_left, 3),
543    UnalignedBinHash = erlang:phash2(UnalignedBin),
544    UnalignedBinHash = erlang:phash2(UnalignedBin),
545    BinHash = UnalignedBinHash,
546    erts_debug:set_internal_state(reds_left, 3),
547    BitstringHash = erlang:phash2(Bitstring),
548    BitstringHash = erlang:phash2(Bitstring),
549    erts_debug:set_internal_state(reds_left, 3),
550    UnalignedBitstringHash = erlang:phash2(UnalignedBitstring),
551    UnalignedBitstringHash = erlang:phash2(UnalignedBitstring),
552    BitstringHash = UnalignedBitstringHash,
553    {BinHash, BitstringHash}.
554
555last_byte(Bin) ->
556    NotLastByteSize = (erlang:bit_size(Bin)) - 8,
557    <<_:NotLastByteSize/bitstring, LastByte:8>> = Bin,
558    LastByte.
559
560test_phash2_4GB_plus_bin(Config) when is_list(Config) ->
561    run_when_enough_resources(
562      fun() ->
563              {ok, N} = start_node(?FUNCTION_NAME),
564              erpc:call(N,
565                        fun() ->
566                                erts_debug:set_internal_state(available_internal_state, true),
567                                %% Created Bin4GB here so it only needs to be created once
568                                erts_debug:set_internal_state(force_gc, self()),
569                                Bin4GB = get_4GB_bin(),
570                                test_phash2_plus_bin_helper1(Bin4GB, <<>>, <<>>, 13708901),
571                                erts_debug:set_internal_state(force_gc, self()),
572                                test_phash2_plus_bin_helper1(Bin4GB, <<>>, <<3:5>>, 66617678),
573                                erts_debug:set_internal_state(force_gc, self()),
574                                test_phash2_plus_bin_helper1(Bin4GB, <<13>>, <<>>, 31308392),
575                                erts_debug:set_internal_state(force_gc, self()),
576                                erts_debug:set_internal_state(available_internal_state, false)
577                        end),
578              stop_node(N)
579      end).
580
581
582test_phash2_10MB_plus_bin(Config) when is_list(Config) ->
583    erts_debug:set_internal_state(available_internal_state, true),
584    erts_debug:set_internal_state(force_gc, self()),
585    Bin10MB = get_10MB_bin(),
586    test_phash2_plus_bin_helper1(Bin10MB, <<>>, <<>>, 22776267),
587    erts_debug:set_internal_state(force_gc, self()),
588    test_phash2_plus_bin_helper1(Bin10MB, <<>>, <<3:5>>, 124488972),
589    erts_debug:set_internal_state(force_gc, self()),
590    test_phash2_plus_bin_helper1(Bin10MB, <<13>>, <<>>, 72958346),
591    erts_debug:set_internal_state(force_gc, self()),
592    erts_debug:set_internal_state(available_internal_state, false).
593
594get_10MB_bin() ->
595    TmpBin = make_random_bin(10239),
596    Bin = erlang:iolist_to_binary([0, TmpBin]),
597    IOList10MB = duplicate_iolist(Bin, 10),
598    Bin10MB = erlang:iolist_to_binary(IOList10MB),
599    10485760 = size(Bin10MB),
600    Bin10MB.
601
602get_4GB_bin() ->
603    TmpBin = make_random_bin(65535),
604    Bin = erlang:iolist_to_binary([0, TmpBin]),
605    IOList4GB = duplicate_iolist(Bin, 16),
606    Bin4GB = erlang:iolist_to_binary(IOList4GB),
607    4294967296 = size(Bin4GB),
608    Bin4GB.
609
610duplicate_iolist(IOList, 0) ->
611    IOList;
612duplicate_iolist(IOList, NrOfTimes) ->
613    duplicate_iolist([IOList, IOList], NrOfTimes - 1).
614
615test_phash2_plus_bin_helper1(Bin4GB, ExtraBytes, ExtraBits, ExpectedHash) ->
616    test_phash2_plus_bin_helper2(Bin4GB, fun id/1, ExtraBytes, ExtraBits, ExpectedHash),
617    test_phash2_plus_bin_helper2(Bin4GB, fun make_unaligned_sub_bitstring/1, ExtraBytes, ExtraBits, ExpectedHash).
618
619test_phash2_plus_bin_helper2(Bin, TransformerFun, ExtraBytes, ExtraBits, ExpectedHash) ->
620    ExtraBitstring = << ExtraBytes/binary, ExtraBits/bitstring >>,
621    LargerBitstring = << ExtraBytes/binary,
622                         ExtraBits/bitstring,
623                         Bin/bitstring >>,
624    LargerTransformedBitstring = TransformerFun(LargerBitstring),
625    ExtraBitstringHash = erlang:phash2(ExtraBitstring),
626    ExpectedHash =
627        case size(LargerTransformedBitstring) < 4294967296 of
628            true ->
629                erts_debug:set_internal_state(force_gc, self()),
630                erts_debug:set_internal_state(reds_left, 1),
631                Hash = erlang:phash2(LargerTransformedBitstring),
632                Hash = erlang:phash2(LargerTransformedBitstring),
633                Hash;
634            false ->
635                erts_debug:set_internal_state(force_gc, self()),
636                erts_debug:set_internal_state(reds_left, 1),
637                ExtraBitstringHash = erlang:phash2(LargerTransformedBitstring),
638                ExtraBitstringHash = erlang:phash2(LargerTransformedBitstring),
639                ExtraBitstringHash
640        end.
641
642run_when_enough_resources(Fun) ->
643    Bits = 8 * erlang:system_info({wordsize,external}),
644    Mem = total_memory(),
645    Build = erlang:system_info(build_type),
646
647    if Bits =:= 64, is_integer(Mem), Mem >= 31,
648       Build =/= valgrind, Build =/= asan ->
649            Fun();
650
651       true ->
652            {skipped,
653             io_lib:format("Not enough resources (System Memory = ~p, Bits = ~p, Build = ~p)",
654                           [Mem, Bits, Build])}
655    end.
656
657%% Total memory in GB
658total_memory() ->
659    try
660        MemoryData = memsup:get_system_memory_data(),
661        case lists:keysearch(total_memory, 1, MemoryData) of
662            {value, {total_memory, TM}} ->
663        	TM div (1024*1024*1024);
664            false ->
665        	{value, {system_total_memory, STM}} =
666        	    lists:keysearch(system_total_memory, 1, MemoryData),
667        	STM div (1024*1024*1024)
668        end
669    catch
670        _ : _ ->
671            undefined
672    end.
673
674start_node(X) ->
675    start_node(X, [], []).
676
677start_node(X, Y) ->
678    start_node(X, Y, []).
679
680start_node(Name, Args, Rel) when is_atom(Name), is_list(Rel) ->
681    Pa = filename:dirname(code:which(?MODULE)),
682    Cookie = atom_to_list(erlang:get_cookie()),
683    RelArg = case Rel of
684                 [] -> [];
685                 _ -> [{erl,[{release,Rel}]}]
686             end,
687    test_server:start_node(Name, slave,
688                           [{args,
689                             Args++" -setcookie "++Cookie++" -pa \""++Pa++"\""}
690                            | RelArg]);
691start_node(Config, Args, Rel) when is_list(Config), is_list(Rel) ->
692    Name = list_to_atom((atom_to_list(?MODULE)
693                         ++ "-"
694                         ++ atom_to_list(proplists:get_value(testcase, Config))
695                         ++ "-"
696                         ++ integer_to_list(erlang:system_time(second))
697                         ++ "-"
698                         ++ integer_to_list(erlang:unique_integer([positive])))),
699    start_node(Name, Args, Rel).
700
701stop_node(Node) ->
702    test_server:stop_node(Node).
703
704-ifdef(FALSE).
705f1() ->
706    abc.
707
708f2() ->
709    abd.
710
711f3(X, Y) ->
712    {X, Y}.
713-endif.
714
715otp_5292_test() ->
716    PH = fun(E) ->
717                 EInList = [1, 2, 3, E],
718                 EInList2 = [E, 1, 2, 3],
719                 NegEInList = [1, 2, 3, -E],
720                 NegEInList2 = [-E, 1, 2, 3],
721                 [erlang:phash(E, 1 bsl 32),
722                  erlang:phash(-E, 1 bsl 32),
723                  erlang:phash2(E, 1 bsl 32),
724                  erlang:phash2(-E, 1 bsl 32),
725                  erlang:phash2(EInList, 1 bsl 32),
726                  erlang:phash2(EInList2, 1 bsl 32),
727                  erlang:phash2(NegEInList, 1 bsl 32),
728                  erlang:phash2(NegEInList2, 1 bsl 32)]
729         end,
730    S2 = md5([md5(hash_int(S, E, PH)) || {Start, N, Sz} <- d(),
731                                         {S, E} <- int(Start, N, Sz)]),
732    <<234,63,192,76,253,57,250,32,44,11,73,1,161,102,14,238>> = S2,
733    ok.
734
735d() ->
736    [%% Start,          NumOfIntervals, SizeOfInterval
737        {(1 bsl I)-100, 2,              100} || I <- lists:seq(1, 1000)].
738
739int(Start, N, Sz) ->
740    {_, R} = lists:mapfoldl(fun(S, Acc) ->
741                                    {S + Sz, [{S,S+Sz-1} | Acc]}
742                            end, [], lists:seq(Start, Start+(N-1)*Sz, Sz)),
743    lists:reverse(R).
744
745hash_int(Start, End, F) ->
746    HL = lists:flatmap(fun(E) -> F(E) end, lists:seq(Start, End)),
747    {Start, End, md5(HL)}.
748
749md5(T) ->
750    erlang:md5(term_to_binary(T)).
751
752bit_level_binaries_do() ->
753    [3511317,7022633,14044578,28087749,56173436,112344123,90467083|_] =
754	bit_level_all_different(fun erlang:phash/2),
755    [102233154,19716,102133857,4532024,123369135,24565730,109558721|_] =
756	bit_level_all_different(fun erlang:phash2/2),
757
758    13233341 = test_hash_phash(<<42:7>>, 16#7FFFFFF),
759    79121243 = test_hash_phash(<<99:7>>, 16#7FFFFFF),
760    95517726 = test_hash_phash(<<16#378ABF73:31>>, 16#7FFFFFF),
761
762    64409098 = test_phash2(<<99:7>>, 16#7FFFFFF),
763    55555814 = test_phash2(<<123,19:2>>, 16#7FFFFFF),
764    83868582 = test_phash2(<<123,45,6:3>>, 16#7FFFFFF),
765    2123204 = test_phash2(<<123,45,7:3>>, 16#7FFFFFF),
766
767    ok.
768
769bit_level_all_different(Hash) ->
770    {name,Name} = erlang:fun_info(Hash, name),
771    Seq = lists:seq(1, 32),
772    Hashes0 = [Hash(<<1:Sz>>, 16#7FFFFFF) || Sz <- Seq],
773    io:format("~p/2 ~p", [Name,Hashes0]),
774    Hashes0 = [Hash(unaligned_sub_bitstr(<<1:Sz>>), 16#7FFFFFF) || Sz <- Seq],
775    32 = length(lists:usort(Hashes0)),
776
777    Hashes1 = [Hash(<<(1 bsl (Sz-1)):Sz>>, 16#7FFFFFF) || Sz <- Seq],
778    io:format("~p/2 ~p", [Name,Hashes1]),
779    Hashes1 = [Hash(unaligned_sub_bitstr(<<(1 bsl (Sz-1)):Sz>>), 16#7FFFFFF) ||
780		  Sz <- Seq],
781    32 = length(lists:usort(Hashes1)),
782
783    Hashes2 = [Hash(<<0:Sz>>, 16#7FFFFFF) || Sz <- Seq],
784    io:format("~p/2 ~p", [Name,Hashes2]),
785    Hashes2 = [Hash(unaligned_sub_bitstr(<<0:Sz>>), 16#7FFFFFF) || Sz <- Seq],
786    32 = length(lists:usort(Hashes2)),
787
788    Hashes1.
789
790test_hash_phash(Bitstr, Rem) ->
791    Hash = erlang:phash(Bitstr, Rem),
792    Hash = erlang:phash(unaligned_sub_bitstr(Bitstr), Rem).
793
794test_phash2(Bitstr, Rem) ->
795    Hash = erlang:phash2(Bitstr, Rem),
796    Hash = erlang:phash2(unaligned_sub_bitstr(Bitstr), Rem).
797
798otp_7127_test() ->
799    %% Used to return 2589127136.
800    38990304 = erlang:phash2(<<"Scott9">>),
801    ok.
802
803hash_zero_test() ->
804    Zs = [0.0, -0.0, 0/-1, 0.0/-1, 0/-(1 bsl 65),
805          binary_to_term(<<131,70,0,0,0,0,0,0,0,0>>),    %% +0.0
806          binary_to_term(<<131,70,128,0,0,0,0,0,0,0>>)], %% -0.0
807    ok = hash_zero_test(Zs,fun(T) -> erlang:phash2(T, 1 bsl 32) end),
808    ok = hash_zero_test(Zs,fun(T) -> erlang:phash(T, 1 bsl 32) end),
809    ok.
810
811hash_zero_test([Z|Zs],F) ->
812    hash_zero_test(Zs,Z,F(Z),F).
813hash_zero_test([Z|Zs],Z0,V,F) ->
814    true = Z0 =:= Z, %% assert exact equal
815    Z0   = Z,        %% assert matching
816    V    = F(Z),     %% assert hash
817    hash_zero_test(Zs,Z0,V,F);
818hash_zero_test([],_,_,_) ->
819    ok.
820
821
822%%
823%% Reference implementation of integer hashing
824%%
825
826%%
827%% These are primes just above 2^28 that will never be changed, they are also in
828%% utils.c.
829%%
830-define(FN2,268439161).
831-define(FN3,268435459).
832-define(FN4,268436141).
833
834make_hash(N,M) ->
835    Prime1 = ?FN2,
836    {Prime2, BL0} = to_bytes(N),
837    BL = pad(BL0),
838    (integer_hash(BL, Prime1, Prime2) rem M) + 1.
839
840to_bytes(N) when N < 0 ->
841    {?FN4,to_bytes(-N,[])};
842to_bytes(N) ->
843    {?FN3,to_bytes(N,[])}.
844to_bytes(0,Acc) ->
845    Acc;
846to_bytes(N,Acc) ->
847    to_bytes(N bsr 8, [N band 16#FF | Acc]).
848
849pad([]) ->
850    [0,0,0,0];
851pad(L) ->
852    case 4 - (length(L) rem 4) of
853	4 ->
854	    L;
855	N ->
856	    lists:duplicate(N,0) ++ L
857    end.
858
859integer_hash(BL,P1,P2) ->
860    (do_ihash(0,lists:reverse(BL),P1) * P2) band 16#FFFFFFFF.
861
862do_ihash(Hash,[],_) ->
863    Hash;
864do_ihash(Hash, [H|T], P) ->
865    do_ihash((((Hash * P) band 16#FFFFFFFF) + H) band 16#FFFFFFFF, T, P).
866
867
868
869
870%%
871%% Utilities for the test of "spreading"
872%%
873-ifdef(debug).
874hex(N) ->
875    hex(0,N,[]).
876hex(X,0,Acc) when X >= 8 ->
877    [$0, $x | Acc];
878hex(X,N,Acc) ->
879    hex(X+1,N bsr 4, [trans(N band 16#F) | Acc]).
880
881trans(N) when N < 10 ->
882    N + $0;
883trans(10) ->
884    $A;
885trans(11) ->
886    $B;
887trans(12) ->
888    $C;
889trans(13) ->
890    $D;
891trans(14) ->
892    $E;
893trans(15) ->
894    $F.
895-endif.
896
897gen_keys(N, Template, BP,Fun) ->
898    Ratio = (1 bsl (BP * 8)),
899    Low = Template + Ratio,
900    High = Template + (N*Ratio),
901    ?dbgformat("N = ~p, BP = ~p, Template = ~p, Low = ~s, High = ~s~n",
902	      [hex(N),hex(BP),hex(Template),hex(Low),hex(High-1)]),
903    Fun(Template),
904    gen_keys2(Low, High,Ratio,Fun).
905
906gen_keys2(High,High2,_,_) when High >= High2 ->
907    [];
908gen_keys2(Low,High,R,Fun) ->
909    Fun(Low),
910    gen_keys2(Low + R,High,R,Fun).
911
912test_fun(N,{HM,HF}, Template, Fun) ->
913    init_table(),
914    test_fun_1(0,1,N+1,{HM,HF},Template,Fun).
915
916test_fun_1(_,To,To,_,_,_) ->
917    ok;
918test_fun_1(A,X,To,Y,Z,W) when A > To ->
919    ?dbgformat("~p:~p(~p,~p,~p,~p,~p,~p)~n",[?MODULE,test_fun_1,To,X,To,Y,Z,W]),
920    test_fun_1(0,X+1,To,Y,Z,W);
921test_fun_1(Pos,Siz,To,{HM,HF},Template,Fun) when 1 bsl (Siz*8) =< 65536 ->
922    io:format("Byte: ~p, Size: ~p~n",[Pos,Siz]),
923    N = 1 bsl (Siz*8),
924    gen_keys(N,Template,Pos,fun (X) ->
925				    P = HM:HF(Fun(X),N),
926				    ets:insert(?MODULE,{P})
927			    end
928	    ),
929    Hits = collect_hits(),
930    io:format(
931      "Hashing of ~p values spread over ~p buckets~n",
932      [N,Hits]),
933    case (N div Hits) > 2 of
934	true ->
935	    exit({not_spread_enough, Hits, on, N});
936	_ ->
937	    test_fun_1(Pos + Siz, Siz, To,{HM,HF},Template,Fun)
938    end;
939test_fun_1(_,_,_,_,_,_) ->
940    ok.
941
942init_table() ->
943    (catch ets:delete(?MODULE)),
944    ets:new(?MODULE,[ordered_set,named_table]).
945
946collect_hits() ->
947    N = ets:info(?MODULE,size),
948    init_table(),
949    N.
950
951integer_to_binary_value(N) ->
952    list_to_binary(lists:reverse(integer_to_bytelist(N,[]))).
953
954integer_to_bytelist(0,Acc) ->
955    Acc;
956integer_to_bytelist(N,Acc) ->
957    integer_to_bytelist(N bsr 8, [N band 16#FF | Acc]).
958
959unaligned_sub_bin(Bin0) when is_binary(Bin0) ->
960    Bin1 = <<42:6,Bin0/binary,3:2>>,
961    Sz = size(Bin0),
962    <<42:6,Bin:Sz/binary,3:2>> = id(Bin1),
963    Bin.
964
965unaligned_sub_bitstr(Bin0) when is_bitstring(Bin0) ->
966    Bin1 = <<(-1):4,Bin0/bits,(-1):64>>,
967    Bits = bit_size(Bin0),
968    <<_:4,Bin:Bits/bits,_:64>> = id(Bin1),
969    Bin.
970
971id(I) -> I.
972
973
974%% Benchmarks for phash2
975
976run_phash2_benchmarks() ->
977    Benchmarks = [
978                  test_phash2_large_map,
979                  test_phash2_shallow_long_list,
980                  test_phash2_deep_list,
981                  test_phash2_deep_tuple,
982                  test_phash2_deep_tiny,
983                  test_phash2_with_42,
984                  test_phash2_with_short_tuple,
985                  test_phash2_with_short_list,
986                  test_phash2_with_tiny_bin,
987                  test_phash2_with_tiny_unaligned_sub_binary,
988                  test_phash2_with_small_unaligned_sub_binary,
989                  test_phash2_with_large_bin,
990                  test_phash2_with_large_unaligned_sub_binary,
991                  test_phash2_with_super_large_unaligned_sub_binary
992                 ],
993    [print_comment(B) || B <- Benchmarks].
994
995
996print_comment(FunctionName) ->
997    io:format("~p~n", [FunctionName]),
998    io:format("~s~n", [element(2, erlang:apply(?MODULE, FunctionName, [[]]))]).
999
1000nr_of_iters(BenchmarkNumberOfIterations, Config) ->
1001    case lists:member(phash2_benchmark_tests, Config) of
1002        true -> 1;
1003        false -> BenchmarkNumberOfIterations
1004    end.
1005
1006
1007test_phash2_large_map(Config) when is_list(Config) ->
1008    {Size, ExpectedHash} =
1009        case {total_memory(), erlang:system_info(wordsize)} of
1010            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1011                {1000000, 121857429};
1012            _ ->
1013                {1000, 66609305}
1014        end,
1015    run_phash2_test_and_benchmark(nr_of_iters(45, Config),
1016                                  get_map(Size),
1017                                  ExpectedHash).
1018
1019test_phash2_shallow_long_list(Config) when is_list(Config) ->
1020    {Size, ExpectedHash} =
1021        case {total_memory(), erlang:system_info(wordsize)} of
1022            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1023                {1000000, 78700388};
1024            _ ->
1025                {1000, 54749638}
1026        end,
1027    run_phash2_test_and_benchmark(nr_of_iters(1, Config),
1028                                  lists:duplicate(Size, get_complex_tuple()),
1029                                  ExpectedHash).
1030
1031test_phash2_deep_list(Config) when is_list(Config) ->
1032    {Size, ExpectedHash} =
1033        case {total_memory(), erlang:system_info(wordsize)} of
1034            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1035                {500000, 17986444};
1036            _ ->
1037                {1000, 81794308}
1038        end,
1039    run_phash2_test_and_benchmark(nr_of_iters(1, Config),
1040                                  make_deep_list(Size, get_complex_tuple()),
1041                                  ExpectedHash).
1042
1043test_phash2_deep_tuple(Config) when is_list(Config) ->
1044    {Size, ExpectedHash} =
1045        case {total_memory(), erlang:system_info(wordsize)} of
1046            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1047                {500000, 116594715};
1048            _ ->
1049                {500, 109057352}
1050        end,
1051    run_phash2_test_and_benchmark(nr_of_iters(1, Config),
1052                                  make_deep_tuple(Size, get_complex_tuple()),
1053                                  ExpectedHash).
1054
1055test_phash2_deep_tiny(Config) when is_list(Config) ->
1056    run_phash2_test_and_benchmark(nr_of_iters(1000000, Config),
1057                                  make_deep_list(19, 42),
1058                                  111589624).
1059
1060test_phash2_with_42(Config) when is_list(Config) ->
1061    run_phash2_test_and_benchmark(nr_of_iters(20000000, Config),
1062                                  42,
1063                                  30328728).
1064
1065test_phash2_with_short_tuple(Config) when is_list(Config) ->
1066    run_phash2_test_and_benchmark(nr_of_iters(10000000, Config),
1067                                  {a,b,<<"hej">>, "hej"},
1068                                  50727199).
1069
1070test_phash2_with_short_list(Config) when is_list(Config) ->
1071    run_phash2_test_and_benchmark(nr_of_iters(10000000, Config),
1072                                  [a,b,"hej", "hello"],
1073                                  117108642).
1074
1075test_phash2_with_tiny_bin(Config) when is_list(Config) ->
1076    run_phash2_test_and_benchmark(nr_of_iters(20000000, Config),
1077                                  make_random_bin(10),
1078                                  129616602).
1079
1080test_phash2_with_tiny_unaligned_sub_binary(Config) when is_list(Config) ->
1081    run_phash2_test_and_benchmark(nr_of_iters(10000000, Config),
1082                                  make_unaligned_sub_binary(make_random_bin(11)),
1083                                  59364725).
1084
1085test_phash2_with_small_unaligned_sub_binary(Config) when is_list(Config) ->
1086    run_phash2_test_and_benchmark(nr_of_iters(400000, Config),
1087                                  make_unaligned_sub_binary(make_random_bin(1001)),
1088                                  130388119).
1089
1090test_phash2_with_large_bin(Config) when is_list(Config) ->
1091    {Size, ExpectedHash} =
1092        case {total_memory(), erlang:system_info(wordsize)} of
1093            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1094                {10000000, 48249379};
1095            _ ->
1096                {1042, 14679520}
1097        end,
1098    run_phash2_test_and_benchmark(nr_of_iters(150, Config),
1099                                  make_random_bin(Size),
1100                                  ExpectedHash).
1101
1102test_phash2_with_large_unaligned_sub_binary(Config) when is_list(Config) ->
1103    {Size, ExpectedHash} =
1104        case {total_memory(), erlang:system_info(wordsize)} of
1105            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1106                {10000001, 122836437};
1107            _ ->
1108                {10042, 127144287}
1109        end,
1110    run_phash2_test_and_benchmark(nr_of_iters(50, Config),
1111                                  make_unaligned_sub_binary(make_random_bin(Size)),
1112                                  ExpectedHash).
1113
1114test_phash2_with_super_large_unaligned_sub_binary(Config) when is_list(Config) ->
1115    {Size, ExpectedHash} =
1116        case {total_memory(), erlang:system_info(wordsize)} of
1117            {Mem, 8} when is_integer(Mem) andalso Mem > 2 ->
1118                {20000001, 112086727};
1119            _ ->
1120                {20042, 91996619}
1121        end,
1122    run_phash2_test_and_benchmark(nr_of_iters(20, Config),
1123                                  make_unaligned_sub_binary(make_random_bin(Size)),
1124                                  ExpectedHash).
1125
1126make_deep_list(1, Item) ->
1127    {Item, Item};
1128make_deep_list(Depth, Item) ->
1129    [{Item, Item}, make_deep_list(Depth - 1, Item)].
1130
1131make_deep_tuple(1, Item) ->
1132    [Item, Item];
1133make_deep_tuple(Depth, Item) ->
1134    {[Item, Item], make_deep_tuple(Depth - 1, Item)}.
1135
1136% Helper functions for benchmarking
1137
1138loop(0, _) -> ok;
1139loop(Iterations, Fun) ->
1140    Fun(),
1141    loop(Iterations - 1, Fun).
1142
1143run_phash2_test_and_benchmark(Iterations, Term, ExpectedHash) ->
1144    Parent = self(),
1145    Test =
1146        fun() ->
1147                Hash = erlang:phash2(Term),
1148                case ExpectedHash =:= Hash of
1149                    false ->
1150                        Parent ! {got_bad_hash, Hash},
1151                        ExpectedHash = Hash;
1152                    _ -> ok
1153                end
1154        end,
1155    Benchmark =
1156        fun() ->
1157                garbage_collect(),
1158                {Time, _} =timer:tc(fun() -> loop(Iterations, Test) end),
1159                Parent ! Time
1160        end,
1161    spawn(Benchmark),
1162    receive
1163        {got_bad_hash, Hash} ->
1164            ExpectedHash = Hash;
1165        Time ->
1166            TimeInS = case (Time/1000000) of
1167                          0.0 -> 0.0000000001;
1168                          T -> T
1169                      end,
1170            IterationsPerSecond = Iterations / TimeInS,
1171            notify(#event{ name = benchmark_data, data = [{value, IterationsPerSecond}]}),
1172            {comment, io_lib:format("Iterations per second: ~p, Iterations ~p, Benchmark time: ~p seconds)",
1173                                    [IterationsPerSecond, Iterations, Time/1000000])}
1174    end.
1175
1176get_complex_tuple() ->
1177    BPort = <<131,102,100,0,13,110,111,110,111,100,101,64,110,111,104,
1178              111,115,116,0,0,0,1,0>>,
1179    Port = binary_to_term(BPort),
1180
1181    BXPort = <<131,102,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
1182               0,0,0,24,3>>,
1183    XPort = binary_to_term(BXPort),
1184
1185    BRef = <<131,114,0,3,100,0,13,110,111,110,111,100,101,64,110,111,104,
1186             111,115,116,0,0,0,1,255,0,0,0,0,0,0,0,0>>,
1187    Ref = binary_to_term(BRef),
1188
1189    BXRef = <<131,114,0,3,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
1190              2,0,0,0,155,0,0,0,0,0,0,0,0>>,
1191    XRef = binary_to_term(BXRef),
1192
1193    BXPid = <<131,103,100,0,11,97,112,97,64,108,101,103,111,108,97,115,
1194              0,0,0,36,0,0,0,0,1>>,
1195    XPid = binary_to_term(BXPid),
1196
1197
1198    %% X = f1(), Y = f2(), Z = f3(X, Y),
1199
1200    %% F1 = fun f1/0, % -> abc
1201    B1 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
1202           13,196,76,242,0,0,0,1,0,0,0,0,100,0,1,116,97,1,98,2,195,126,
1203           58,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
1204           115,116,0,0,0,112,0,0,0,0,0>>,
1205    F1 = binary_to_term(B1),
1206
1207    %% F2 = fun f2/0, % -> abd
1208    B2 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
1209           13,196,76,242,0,0,0,2,0,0,0,0,100,0,1,116,97,2,98,3,130,152,
1210           185,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
1211           115,116,0,0,0,112,0,0,0,0,0>>,
1212    F2 = binary_to_term(B2),
1213
1214    %% F3 = fun f3/2, % -> {abc, abd}
1215    B3 = <<131,112,0,0,0,66,2,215,206,77,69,249,50,170,17,129,47,21,98,
1216           13,196,76,242,0,0,0,3,0,0,0,0,100,0,1,116,97,3,98,7,168,160,
1217           93,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
1218           115,116,0,0,0,112,0,0,0,0,0>>,
1219    F3 = binary_to_term(B3),
1220
1221    %% F4 = fun () -> 123456789012345678901234567 end,
1222    B4 = <<131,112,0,0,0,66,0,215,206,77,69,249,50,170,17,129,47,21,98,
1223           13,196,76,242,0,0,0,4,0,0,0,0,100,0,1,116,97,4,98,2,230,21,
1224           171,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
1225           115,116,0,0,0,112,0,0,0,0,0>>,
1226    F4 = binary_to_term(B4),
1227
1228    %% F5 = fun() -> {X,Y,Z} end,
1229    B5 = <<131,112,0,0,0,92,0,215,206,77,69,249,50,170,17,129,47,21,98,
1230           13,196,76,242,0,0,0,5,0,0,0,3,100,0,1,116,97,5,98,0,99,101,
1231           130,103,100,0,13,110,111,110,111,100,101,64,110,111,104,111,
1232           115,116,0,0,0,112,0,0,0,0,0,100,0,3,97,98,99,100,0,3,97,98,
1233           100,104,2,100,0,3,97,98,99,100,0,3,97,98,100>>,
1234    F5 = binary_to_term(B5),
1235    {{1,{2}},an_atom, 1, 3434.923942394,<<"this is a binary">>,
1236     make_unaligned_sub_binary(<<"this is also a binary">>),c,d,e,f,g,h,i,j,k,l,[f],
1237     999999999999999999666666662123123123123324234999999999999999, 234234234,
1238     BPort, Port, BXPort, XPort, BRef, Ref, BXRef, XRef, BXPid, XPid, F1, F2, F3, F4, F5,
1239     #{a => 1, b => 2, c => 3, d => 4, e => 5, f => 6, g => 7, h => 8, i => 9,
1240       j => 1, k => 1, l => 123123123123213, m => [1,2,3,4,5,6,7,8], o => 5, p => 6,
1241       q => 7, r => 8, s => 9}}.
1242
1243get_map_helper(MapSoFar, 0) ->
1244    MapSoFar;
1245get_map_helper(MapSoFar, NumOfItemsToAdd) ->
1246    NewMapSoFar = maps:put(NumOfItemsToAdd, NumOfItemsToAdd, MapSoFar),
1247    get_map_helper(NewMapSoFar, NumOfItemsToAdd -1).
1248
1249get_map(Size) ->
1250    get_map_helper(#{}, Size).
1251
1252
1253%% Copied from binary_SUITE
1254make_unaligned_sub_binary(Bin0) when is_binary(Bin0) ->
1255    Bin1 = <<0:3,Bin0/binary,31:5>>,
1256    Sz = size(Bin0),
1257    <<0:3,Bin:Sz/binary,31:5>> = id(Bin1),
1258    Bin.
1259
1260make_unaligned_sub_bitstring(Bin0) ->
1261    Bin1 = <<0:3,Bin0/bitstring,31:5>>,
1262    Sz = erlang:bit_size(Bin0),
1263    <<0:3,Bin:Sz/bitstring,31:5>> = id(Bin1),
1264    Bin.
1265
1266make_random_bin(Size) ->
1267    make_random_bin(Size, []).
1268
1269make_random_bin(0, Acc) ->
1270    iolist_to_binary(Acc);
1271make_random_bin(Size, []) ->
1272    make_random_bin(Size - 1, [simple_rand() rem 256]);
1273make_random_bin(Size, [N | Tail]) ->
1274    make_random_bin(Size - 1, [simple_rand(N) rem 256, N |Tail]).
1275
1276simple_rand() ->
1277    123456789.
1278simple_rand(Seed) ->
1279    A = 1103515245,
1280    C = 12345,
1281    M = (1 bsl 31),
1282    (A * Seed + C) rem M.
1283