basis/checksums/murmur/murmur.factor

   1 ! Copyright (C) 2013 John Benediktsson.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3
   4 USING: accessors alien alien.c-types alien.data byte-arrays
   5 checksums endian grouping kernel math math.bitwise
   6 ranges sequences ;
   7
   8 IN: checksums.murmur
   9
  10 TUPLE: murmur3-32 seed ;
  11
  12 C: <murmur3-32> murmur3-32
  13
  14 CONSTANT: c1 0xcc9e2d51
  15 CONSTANT: c2 0x1b873593
  16 CONSTANT: r1 15
  17 CONSTANT: r2 13
  18 CONSTANT: m 5
  19 CONSTANT: n 0xe6546b64
  20
  21 <PRIVATE
  22
  23 : (hash-chunk) ( k -- k' )
  24     c1 w* r1 bitroll-32 c2 w* ; inline
  25
  26 : hash-chunk ( hash k -- hash' )
  27     (hash-chunk) bitxor r2 bitroll-32 m w* n w+ ; inline
  28
  29 : main-loop ( seq hash -- seq hash' )
  30     over byte-array? alien.data:little-endian? and [
  31         [ 0 over length 4 - 4 <range> ] dip
  32         [ pick <displaced-alien> int deref hash-chunk ] reduce
  33     ] [
  34         [ dup length 4 mod dupd head-slice* 4 <groups> ] dip
  35         [ le> hash-chunk ] reduce
  36     ] if ; inline
  37
  38 : end-case ( seq hash -- hash' )
  39     swap dup length
  40     [ 4 mod tail-slice* be> (hash-chunk) bitxor ]
  41     [ bitxor ] bi 32 bits ; inline
  42
  43 : avalanche ( hash -- hash' )
  44     [ -16 shift ] [ bitxor 0x85ebca6b w* ] bi
  45     [ -13 shift ] [ bitxor 0xc2b2ae35 w* ] bi
  46     [ -16 shift ] [ bitxor ] bi ; inline
  47
  48 PRIVATE>
  49
  50 M: murmur3-32 checksum-bytes
  51     seed>> 32 bits main-loop end-case avalanche ;
  52
  53 INSTANCE: murmur3-32 checksum