basis/checksums/xxhash/xxhash.factor

   1 ! Copyright (C) 2014 John Benediktsson.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3
   4 USING: accessors alien.c-types alien.data byte-arrays
   5 checksums combinators endian generalizations grouping kernel
   6 math math.bitwise sequences specialized-arrays ;
   7 SPECIALIZED-ARRAY: uint64_t
   8
   9 IN: checksums.xxhash
  10
  11 CONSTANT: prime1 2654435761
  12 CONSTANT: prime2 2246822519
  13 CONSTANT: prime3 3266489917
  14 CONSTANT: prime4 668265263
  15 CONSTANT: prime5 374761393
  16
  17 TUPLE: xxhash seed ;
  18
  19 C: <xxhash> xxhash
  20
  21 <PRIVATE
  22
  23 :: native-mapper ( from to bytes c-type -- seq )
  24     from to bytes <slice>
  25     bytes byte-array? alien.data:little-endian? and
  26     [ c-type cast-array ]
  27     [ c-type heap-size <groups> [ le> ] map ] if ; inline
  28
  29 PRIVATE>
  30
  31 M:: xxhash checksum-bytes ( bytes checksum -- value )
  32     checksum seed>> :> seed
  33     bytes length :> len
  34
  35     len dup 16 mod - :> len/16
  36     len dup 4 mod - :> len/4
  37
  38     len 16 >= [
  39
  40         seed prime1 w+ prime2 w+
  41         seed prime2 w+
  42         seed
  43         seed prime1 w-
  44
  45         0 len/16 bytes uint native-mapper
  46
  47         4 <groups> [
  48             first4
  49             [ prime2 w* w+ 13 bitroll-32 prime1 w* ]
  50             4 napply
  51         ] each
  52
  53         {
  54             [ 1 bitroll-32 ]
  55             [ 7 bitroll-32 ]
  56             [ 12 bitroll-32 ]
  57             [ 18 bitroll-32 ]
  58         } spread w+ w+ w+
  59     ] [
  60         seed prime5 w+
  61     ] if
  62
  63     len w+
  64
  65     len/16 len/4 bytes uint native-mapper
  66     [ prime3 w* w+ 17 bitroll-32 prime4 w* ] each
  67
  68     bytes len/4 tail-slice
  69     [ prime5 w* w+ 11 bitroll-32 prime1 w* ] each
  70
  71     [ -15 shift ] [ bitxor ] bi prime2 w*
  72     [ -13 shift ] [ bitxor ] bi prime3 w*
  73     [ -16 shift ] [ bitxor ] bi ;
  74
  75 INSTANCE: xxhash checksum