checksums.murmur: implementation of MurmurHash.

diff --git a/basis/checksums/murmur/authors.txt b/basis/checksums/murmur/authors.txt
new file mode 100644 (file)
index 0000000..e091bb8
--- /dev/null
+++ b/basis/checksums/murmur/authors.txt
@@ -0,0 +1 @@
+John Benediktsson

diff --git a/basis/checksums/murmur/murmur-docs.factor b/basis/checksums/murmur/murmur-docs.factor
new file mode 100644 (file)
index 0000000..da9f612
--- /dev/null
+++ b/basis/checksums/murmur/murmur-docs.factor
@@ -0,0 +1,11 @@
+USING: help.markup help.syntax ;
+IN: checksums.murmur
+
+HELP: murmur3-32
+{ $class-description "MurmurHash3 32-bit checksum algorithm." } ;
+
+ARTICLE: "checksums.murmur" "MurmurHash checksum"
+"MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup, created by Austin Appleby in 2008."
+{ $subsections murmur3-32 } ;
+
+ABOUT: "checksums.murmur"

diff --git a/basis/checksums/murmur/murmur-tests.factor b/basis/checksums/murmur/murmur-tests.factor
new file mode 100644 (file)
index 0000000..f07e215
--- /dev/null
+++ b/basis/checksums/murmur/murmur-tests.factor
@@ -0,0 +1,9 @@
+USING: checksums tools.test ;
+IN: checksums.murmur
+
+{ 455139366 } [ "asdf" 0 <murmur3-32> checksum-bytes ] unit-test
+{ 417250299 } [ "asdf" 156 <murmur3-32> checksum-bytes ] unit-test
+{ -392455434 } [ "abcde" 0 <murmur3-32> checksum-bytes ] unit-test
+{ -1850534962 } [ "12345678" 0 <murmur3-32> checksum-bytes ] unit-test
+{ -1710454456 } [ "12345678" 156 <murmur3-32> checksum-bytes ] unit-test
+{ -734568571 } [ "hello, world!!!" 156 <murmur3-32> checksum-bytes ] unit-test

diff --git a/basis/checksums/murmur/murmur.factor b/basis/checksums/murmur/murmur.factor
new file mode 100644 (file)
index 0000000..13e645f
--- /dev/null
+++ b/basis/checksums/murmur/murmur.factor
@@ -0,0 +1,41 @@
+! Copyright (C) 2013 John Benediktsson.
+! See http://factorcode.org/license.txt for BSD license.
+USING: accessors checksums fry grouping io.binary kernel math
+math.bitwise sequences ;
+IN: checksums.murmur
+
+TUPLE: murmur3-32 seed ;
+
+C: <murmur3-32> murmur3-32
+
+CONSTANT: c1 0xcc9e2d51
+CONSTANT: c2 0x1b873593
+CONSTANT: r1 15
+CONSTANT: r2 13
+CONSTANT: m 5
+CONSTANT: n 0xe6546b64
+
+<PRIVATE
+
+: 32-bit ( n -- n' ) 32 on-bits mask ; inline
+
+: rotl ( k r -- k' )
+    [ shift ] [ 32 - shift ] 2bi bitor ; inline
+
+: (hash-chunk) ( k -- k' )
+    c1 * 32-bit r1 rotl c2 * 32-bit ; inline
+
+: hash-chunk ( hash k -- hash' )
+    (hash-chunk) bitxor r2 rotl m * n + 32-bit ; inline
+
+PRIVATE>
+
+M: murmur3-32 checksum-bytes ( bytes checksum -- value )
+    [ [ length ] keep over 4 mod cut* ] [ seed>> 32-bit ] bi*
+    '[ 4 <groups> _ [ le> hash-chunk ] reduce ]
+    [ be> (hash-chunk) bitxor bitxor 32-bit ] bi*
+    [ -16 shift ] [ bitxor 0x85ebca6b * 32-bit ] bi
+    [ -13 shift ] [ bitxor 0xc2b2ae35 * 32-bit ] bi
+    [ -16 shift ] [ bitxor 32 >signed ] bi ;
+
+INSTANCE: murmur3-32 checksum

diff --git a/basis/checksums/murmur/summary.txt b/basis/checksums/murmur/summary.txt
new file mode 100644 (file)
index 0000000..4ac7b4a
--- /dev/null
+++ b/basis/checksums/murmur/summary.txt
@@ -0,0 +1 @@
+MurmurHash checksum algorithm