ehash

%% Copyright 2017 (c) Benoit Chesneau.
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%%     http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
%% implied. See the License for the specific language governing
%% permissions and limitations under the License.

-module(ehash).

%% API exports
-export([hash/2, to_hex/1, uuid5/1, term_to_binary/1]).

%%====================================================================
%% API functions
%%====================================================================

%% @doc return a reproducible hash of an Erlang term
-spec hash(Type :: crypto:hash_algorithms(), Term :: any()) -> Hash :: binary().
hash(Type, Term) ->
  Ctx = crypto:hash_init(Type),
  crypto:hash_final(hash_1(Term, crypto:hash_update(Ctx, <<131>>))).

hash_1(Map, Ctx) when is_map(Map) ->
  lists:foldl(fun({K, V}, Ctx1) ->
                hash_1(V, hash_1(K, Ctx1))
            end,
            crypto:hash_update(Ctx, << 116, (maps:size(Map)):32 >>),
            lists:sort(maps:to_list(Map)));
hash_1(List, Ctx) when is_list(List) ->
  lists:foldl(fun(E, Ctx1) ->
                  hash_1(E, Ctx1)
              end,
              crypto:hash_update(Ctx, << 108, (length(List)):32 >>),
              List);
hash_1(Tuple, Ctx) when is_tuple(Tuple) ->
  L = tuple_to_list(Tuple),
  lists:foldl(fun(E, Ctx1) ->
                  hash_1(E, Ctx1)
              end,
              crypto:hash_update(Ctx, << 105, (length(L)):32 >>),
              L);
hash_1(Term, Ctx) ->
  << 131, Bin1/binary >> = erlang:term_to_binary(Term),
  crypto:hash_update(Ctx, Bin1).


%% @doc Returns a reproducible binary data object that is the result of
%% encoding Term according to the Erlang Term Format
-spec term_to_binary(Term :: any()) -> erlang:ext_binary().
term_to_binary(Term) ->
  term_to_binary_1(Term, << 131 >>).

term_to_binary_1(Map, Bin) when is_map(Map) ->
  lists:foldl(fun({K, V}, Bin1) ->
                  term_to_binary_1(V, term_to_binary_1(K, Bin1))
              end,
              << Bin/binary, 116, (maps:size(Map)):32 >>,
              lists:sort(maps:to_list(Map)));
term_to_binary_1(List, Bin) when is_list(List) ->
  Bin2 = lists:foldl(
           fun(E, Bin1) -> term_to_binary_1(E, Bin1) end,
           << Bin/binary, 108, (length(List)):32 >>, List),
  << Bin2/binary, 106 >>;
term_to_binary_1(Tuple, Bin) when is_tuple(Tuple)->
  L = tuple_to_list(Tuple),
  lists:foldl(
    fun(E, Bin1) -> term_to_binary_1(E, Bin1) end,
    << Bin/binary, 105, (length(L)):32 >>, L);
term_to_binary_1(Term, Bin) ->
  << 131, Bin1/binary >> = erlang:term_to_binary(Term),
  << Bin/binary, Bin1/binary >>.

%% @doc return the hash encoded with the hash function as an hexadecimal.
-spec to_hex(Hash :: binary()) -> Hex :: binary().
to_hex(Hash) ->
  << <<(to_digit(H)),(to_digit(L))>> || <<H:4,L:4>> <= Hash >>.

to_digit(N) when N < 10 -> $0 + N;
to_digit(N)             -> $a + N-10.

%% @doc hash an erlang term and return the result as an UUID5 following the rfc 4122
-spec uuid5(Term :: any()) -> UUID5 :: binary().
uuid5(Term) ->
  <<B1:48, _:4, B2:12, _:2, B3:14, B4:48, _:32>> = hash(sha, Term),
  << V:128/unsigned-integer>> = <<B1:48,
                                  0:1, 1:1, 0:1, 1:1,  % version 5 bits
                                  B2:12,
                                  1:1, 0:1,            % RFC 4122 variant bits
                                  B3:14,
                                  B4:48>>,
  [N01, N02, N03, N04, N05, N06, N07, N08,
   N09, N10, N11, N12,
   N13, N14, N15, N16,
   N17, N18, N19, N20,
   N21, N22, N23, N24, N25, N26, N27, N28, N29, N30, N31, N32]
    = int_to_hex_list(V, 32),
  <<N01, N02, N03, N04, N05, N06, N07, N08, $-,
    N09, N10, N11, N12, $-,
    N13, N14, N15, N16, $-,
    N17, N18, N19, N20, $-,
    N21, N22, N23, N24, N25, N26, N27, N28, N29, N30, N31, N32>>.


int_to_hex_list(I, N) when is_integer(I), I >= 0 ->
  int_to_hex_list([], I, 1, N).

int_to_list_pad(L, 0) ->
  L;
int_to_list_pad(L, Count) ->
  int_to_list_pad([$0 | L], Count - 1).

int_to_hex_list(L, I, Count, N)
  when I < 16 ->
  int_to_list_pad([int_to_hex(I) | L], N - Count);
int_to_hex_list(L, I, Count, N) ->
  int_to_hex_list([int_to_hex(I rem 16) | L], I div 16, Count + 1, N).

int_to_hex(I) when 0 =< I, I =< 9 ->
  I + $0;
int_to_hex(I) when 10 =< I, I =< 15 ->
  (I - 10) + $a.