checksums.murmur: make checksum on byte-arrays much faster.

diff --git a/basis/checksums/murmur/murmur-tests.factor b/basis/checksums/murmur/murmur-tests.factor
index 79769a8f24a9101779740cd4f2bd39da3657862e..8a16c5a90552e07181a30eb3cfb29f69c8973891 100644 (file)
--- a/basis/checksums/murmur/murmur-tests.factor
+++ b/basis/checksums/murmur/murmur-tests.factor
@@ -1,10 +1,38 @@
-USING: checksums tools.test ;
+USING: byte-arrays checksums fry kernel math sequences
+tools.test ;
 IN: checksums.murmur
 
-{ 455139366 } [ "asdf" 0 <murmur3-32> checksum-bytes ] unit-test
-{ 417250299 } [ "asdf" 156 <murmur3-32> checksum-bytes ] unit-test
-{ 3902511862 } [ "abcde" 0 <murmur3-32> checksum-bytes ] unit-test
-{ 2517562459 } [ "abcde" 156 <murmur3-32> checksum-bytes ] unit-test
-{ 2444432334 } [ "12345678" 0 <murmur3-32> checksum-bytes ] unit-test
-{ 2584512840 } [ "12345678" 156 <murmur3-32> checksum-bytes ] unit-test
-{ 3560398725 } [ "hello, world!!!" 156 <murmur3-32> checksum-bytes ] unit-test
+{ 455139366 } [ "asdf" >byte-array 0 <murmur3-32> checksum-bytes ] unit-test
+{ 417250299 } [ "asdf" >byte-array 156 <murmur3-32> checksum-bytes ] unit-test
+{ 3902511862 } [ "abcde" >byte-array 0 <murmur3-32> checksum-bytes ] unit-test
+{ 2517562459 } [ "abcde" >byte-array 156 <murmur3-32> checksum-bytes ] unit-test
+{ 2444432334 } [ "12345678" >byte-array 0 <murmur3-32> checksum-bytes ] unit-test
+{ 2584512840 } [ "12345678" >byte-array 156 <murmur3-32> checksum-bytes ] unit-test
+{ 3560398725 } [ "hello, world!!!" >byte-array 156 <murmur3-32> checksum-bytes ] unit-test
+
+{
+    {
+        3903553677
+        3120384252
+        3928660296
+        2995164002
+        500661690
+        2764333444
+        1941147762
+        161439790
+        2584512840
+        3803370487
+        626154228
+    }
+} [
+    "1234567890" [ length 1 + ] keep 156 <murmur3-32>
+    '[ _ swap head _ checksum-bytes ] { } map-integers
+] unit-test
+
+
+{ t } [
+    "1234567890" dup >byte-array [
+        [ length 1 + ] keep 156 <murmur3-32>
+        '[ _ swap head _ checksum-bytes ] { } map-integers
+    ] bi@ =
+] unit-test

diff --git a/basis/checksums/murmur/murmur.factor b/basis/checksums/murmur/murmur.factor
index d0f7dc9e90ec8b53882666f57d4b7fb822703d51..b06820d820b7a9d071399e4abadc9ff5d8aca979 100644 (file)
--- a/basis/checksums/murmur/murmur.factor
+++ b/basis/checksums/murmur/murmur.factor
@@ -1,8 +1,9 @@
 ! 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 ;
+USING: accessors alien alien.c-types alien.data byte-arrays
+checksums fry grouping io.binary kernel math math.bitwise
+math.ranges sequences ;
 
 IN: checksums.murmur
 
@@ -30,14 +31,28 @@ CONSTANT: n 0xe6546b64
 : hash-chunk ( hash k -- hash' )
     (hash-chunk) bitxor r2 rotl m * n + 32-bit ; inline
 
+: main-loop ( seq hash -- seq hash' )
+    over byte-array? little-endian? and [
+        [ 0 over length 4 - 4 <range> ] dip
+        [ pick <displaced-alien> int deref hash-chunk ] reduce
+    ] [
+        [ dup length 4 mod dupd head-slice* 4 <groups> ] dip
+        [ le> hash-chunk ] reduce
+    ] if ; inline
+
+: end-case ( seq hash -- hash' )
+    swap dup length
+    [ 4 mod tail-slice* be> (hash-chunk) bitxor ]
+    [ bitxor ] bi 32-bit ; inline
+
+: avalanche ( hash -- hash' )
+    [ -16 shift ] [ bitxor 0x85ebca6b * 32-bit ] bi
+    [ -13 shift ] [ bitxor 0xc2b2ae35 * 32-bit ] bi
+    [ -16 shift ] [ bitxor ] bi ; 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 ] bi ;
+    seed>> 32-bit main-loop end-case avalanche ;
 
 INSTANCE: murmur3-32 checksum