murmur2_erl / murmur2.erl

%% @author Jay Baird <jay@mochimedia.com>
%% @copyright 2009 Mochi Media, Inc.

%% Permission is hereby granted, free of charge, to any person obtaining a copy
%% of this software and associated documentation files (the "Software"), to deal
%% in the Software without restriction, including without limitation the rights
%% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
%% copies of the Software, and to permit persons to whom the Software is
%% furnished to do so, subject to the following conditions:
%%
%% The above copyright notice and this permission notice shall be included in
%% all copies or substantial portions of the Software.
%%
%% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
%% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
%% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
%% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
%% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
%% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
%% THE SOFTWARE.

%% @doc Port of http://bitbucket.org/etrepum/hashfunctions/src/tip/hashfunctions/hash_murmur2.py

-module(murmur2).
-author('Jay Baird <jay@mochimedia.com>').
-export([hash/1, hash/2]).
-include_lib("eunit/include/eunit.hrl").

hash(Key) ->
    hash(Key, 0).

hash(Key, Seed) ->
    M = 16#5bd1e995,
    Mask = 16#ffffffff,
    R = 24,
    KeyLen = size(Key),
    H = (Seed bxor KeyLen) band Mask,
    H2 = murmur2_hash(Key, M, Mask, R, H),
    H3 = (H2 bxor (H2 bsr 13)),
    H4 = (H3 * M) band Mask,
    H5 = (H4 bxor (H4 bsr 15)),
    H5 band Mask.

murmur2_hash(<<K:32/little, T/binary>>, M, Mask, R, H) ->
    K1 = (K * M) band Mask,
    K2 = (K1 bxor (K1 bsr R)),
    K3 = (K2 * M),
    H1 = (H * M),
    H2 = (H1 bxor K3) band Mask,
    murmur2_hash(T, M, Mask, R, H2);
murmur2_hash(<<>>, _M, _Mask, _R, H) ->
    H;
murmur2_hash(Remainder, M, Mask, _R, H) ->
    N = size(Remainder) * 8,
    <<K:N/little>> = Remainder,
    ((H bxor K) * M) band Mask.

hash_test() ->
    ?assertEqual(3680343784, hash(<<"lkasjdfklajslku2i1op3u49puid">>, 89012738)),
    F1 = fun (N, Seed) ->
                hash(list_to_binary(integer_to_list(N)), Seed)
        end,
    ?assertEqual(2187758613, lists:foldl(F1, 0, lists:seq(0, 99))),
    F2 = fun (N, Seed) ->
                hash(list_to_binary(integer_to_list(N * N)), Seed)
        end,
    ?assertEqual(384923386, lists:foldl(F2, 0, lists:seq(0, 99))).
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.