murmur.nim

#[
D20190624T151119
ADAPTED from https://github.com/PeterScott/murmur3/blob/master/murmur3.c which said:
MurmurHash3 was written by Austin Appleby, and is placed in the public domain
and ported to nim
]#

template `[]`*[T](p: ptr T, off: int): T =
  (p + off)[]
template `+`*[T](p: ptr T, off: int): ptr T =
  cast[ptr T](cast[ByteAddress](p) +% off * sizeof(T))

template `^=`(a, b) = a = a xor b

template rotl32(x: uint32, r: int8): uint32 =
  (x shl r) | (x shr (32 - r))

template ROTL64(x: uint64, r: int8): uint64 =
  (x shl r) or (x shr (64 - r))

#[
Block read - if your platform needs to do endian-swapping or can only handle aligned reads, do the conversion here
]#
template getblock(p, i): untyped = p[i]

proc fmix32(h: uint32): uint32 =
  # Finalization mix - force all bits of a hash block to avalanche
  var h = h
  h ^= h shr 16
  h *= 0x85ebca6b'u32
  h ^= h shr 13
  h *= 0xc2b2ae35'u32
  h ^= h shr 16
  return h

proc fmix64(k: uint64): uint64 {.inline.} =
  var k = k
  k ^= k shr 33
  k *= 0xff51afd7ed558ccd'u64
  k ^= k shr 33
  k *= 0xc4ceb9fe1a85ec53'u64
  k ^= k shr 33
  k

proc MurmurHash3_x64_128*(key: ptr uint8, len: int, seed: uint32 = 0, nBits: static int): auto =
  # let data: ptr uint8 = key[0].unsafeAddr
  # let data: ptr uint8 = cast[ptr uint8](key[0].unsafeAddr)
  let data: ptr uint8 = key
  let nblocks = len div 16
  var i=0
  var h1: uint64 = seed
  var h2: uint64 = seed
  const c1 = 0x87c37b91114253d5'u64
  const c2 = 0x4cf5ad432745937f'u64
  # body
  let blocks = cast[ptr uint64](data)
  for i in 0 ..< nblocks:
    var k1: uint64 = getblock(blocks, i*2+0)
    var k2: uint64 = getblock(blocks, i*2+1)
    k1 *= c1
    k1 = ROTL64(k1,31)
    k1 *= c2
    h1 ^= k1
    h1 = ROTL64(h1,27)
    h1 += h2
    h1 = h1*5+0x52dce729
    k2 *= c2
    k2  = ROTL64(k2,33)
    k2 *= c1
    h2 ^= k2
    h2 = ROTL64(h2,31)
    h2 += h1
    h2 = h2*5+0x38495ab5

  # tail
  let tail: ptr uint8 = (data + nblocks*16)
  var k1 = 0'u64
  var k2 = 0'u64
  var state = len and 15
  while state > 0:
    case state
    of 15: k2 ^= tail[14].uint shl 48
    of 14: k2 ^= tail[13].uint shl 40
    of 13: k2 ^= tail[12].uint shl 32
    of 12: k2 ^= tail[11].uint shl 24
    of 11: k2 ^= tail[10].uint shl 16
    of 10: k2 ^= tail[ 9].uint shl 8
    of 9:
      k2 ^= tail[ 8].uint shl 0
      k2 *= c2
      k2  = ROTL64(k2,33)
      k2 *= c1
      h2 ^= k2

    of 8: k1 ^= tail[ 7].uint shl 56
    of 7: k1 ^= tail[ 6].uint shl 48
    of 6: k1 ^= tail[ 5].uint shl 40
    of 5: k1 ^= tail[ 4].uint shl 32
    of 4: k1 ^= tail[ 3].uint shl 24
    of 3: k1 ^= tail[ 2].uint shl 16
    of 2: k1 ^= tail[ 1].uint shl 8
    of 1:
      k1 ^= tail[ 0].uint shl 0
      k1 *= c1
      k1  = ROTL64(k1,31)
      k1 *= c2
      h1 ^= k1
      break
    of 0: break
    else: assert false
    state.dec

  # finalization
  h1 ^= len.uint64
  h2 ^= len.uint64

  h1 += h2
  h2 += h1

  h1 = fmix64(h1)
  h2 = fmix64(h2)

  h1 += h2
  when nBits == 128:
    result = [h1, h1 + h2]
  elif nBits == 64:
    result = h1
  else:
    static: doAssert false, $nBits

const nBitsDefault = 64

proc toHashMurmur3*(x: pointer, len: int, seed = 0'u32, nBits: static int = nBitsDefault): auto =
  MurmurHash3_x64_128(cast[ptr uint8](x), len, seed, nBits=nBits)

proc toHashMurmur3*(x: string, seed = 0'u32, nBits: static int = nBitsDefault): auto =
  MurmurHash3_x64_128(cast[ptr uint8](x[0].unsafeAddr), x.len, seed, nBits=nBits)
  # MurmurHash3_x64_128(x.toOpenArray(0, high(x)), seed)
  # MurmurHash3_x64_128(x[0].unsafeAddr, x.len, seed)

when isMainModule:
  import std/strutils

  {.compile: "/Users/timothee/git_clone/murmur3/murmur3.c" .} # PATH
  # {.compile: "/Users/timothee/git_clone/nim/timn/src/timn/murmur3.c" .}
  proc c_MurmurHash3_x64_128(key: pointer, len: cint, seed: uint32, pout: ptr array[2, uint64]) {.importc: "MurmurHash3_x64_128".}

  proc fun() =
    let seed = 0'u32
    let prefix = "hellow ljasdf lksajdfpiwjepijfaspdf 1"
    var x = prefix & "a"
    let h1 = toHashMurmur3(x)
    echo h1

    when nimvm: discard
    else:
      var pout: array[2, uint64]
      echo "c version:"
      c_MurmurHash3_x64_128(x[0].addr, x.len.cint, seed, pout.addr)
      doAssert pout == h1
      echo pout

    block:
      var x2 = prefix & "b"
      var x3 = prefix & "c"
      let h2 = toHashMurmur3(x2)
      let h3 = toHashMurmur3(x3)
      echo toBin(cast[BiggestInt](h1[1]), 64)
      echo toBin(cast[BiggestInt](h2[1]), 64)
      echo toBin(cast[BiggestInt](h3[1]), 64)

  proc main() =
    # static: fun() # TODO: use VM callback to allow its use in VM?
    fun()

  main()