hashes: implement murmur3 (#12022)

* hashes: implement murmur3
* refactoring; there is only one murmurHash and it works at compile-time via VM hooks
* fixes JS tests
* makes toOpenArrayByte work with C++
* make it bootstrap in C++ mode for 0.20

3 files changed, 38 insertions, 6 deletions

diff --git a/compiler/ccgcalls.nim b/compiler/ccgcalls.nim
index 4efd33d1e..53ebc2806 100644
--- a/compiler/ccgcalls.nim
+++ b/compiler/ccgcalls.nim
@@ -100,21 +100,23 @@ proc openArrayLoc(p: BProc, n: PNode): Rope =
     if optBoundsCheck in p.options:
       genBoundsCheck(p, a, b, c)
     let ty = skipTypes(a.t, abstractVar+{tyPtr})
+    let dest = getTypeDesc(p.module, n.typ.sons[0])
     case ty.kind
     of tyArray:
       let first = toInt64(firstOrd(p.config, ty))
       if first == 0:
-        result = "($1)+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c)]
+        result = "($4*)(($1)+($2)), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dest]
       else:
-        result = "($1)+(($2)-($4)), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), intLiteral(first)]
-    of tyOpenArray, tyVarargs, tyUncheckedArray:
-      result = "($1)+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c)]
+        result = "($5*)($1)+(($2)-($4)), ($3)-($2)+1" %
+          [rdLoc(a), rdLoc(b), rdLoc(c), intLiteral(first), dest]
+    of tyOpenArray, tyVarargs, tyUncheckedArray, tyCString:
+      result = "($4*)($1)+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dest]
     of tyString, tySequence:
       if skipTypes(n.typ, abstractInst).kind == tyVar and
           not compileToCpp(p.module):
-        result = "(*$1)$4+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dataField(p)]
+        result = "($5*)(*$1)$4+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dataField(p), dest]
       else:
-        result = "$1$4+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dataField(p)]
+        result = "($5*)$1$4+($2), ($3)-($2)+1" % [rdLoc(a), rdLoc(b), rdLoc(c), dataField(p), dest]
     else:
       internalError(p.config, "openArrayLoc: " & typeToString(a.t))
   else:
diff --git a/compiler/condsyms.nim b/compiler/condsyms.nim
index 15a625472..00ce352f2 100644
--- a/compiler/condsyms.nim
+++ b/compiler/condsyms.nim
@@ -97,4 +97,5 @@ proc initDefines*(symbols: StringTableRef) =
 
   defineSymbol("nimFixedOwned")
   defineSymbol("nimHasStyleChecks")
+  defineSymbol("nimToOpenArrayCString")
   defineSymbol("nimHasUsed")
diff --git a/compiler/vmops.nim b/compiler/vmops.nim
index 792feb0be..b0325b5b0 100644
--- a/compiler/vmops.nim
+++ b/compiler/vmops.nim
@@ -17,6 +17,8 @@ from os import getEnv, existsEnv, dirExists, fileExists, putEnv, walkDir, getApp
 from md5 import getMD5
 from sighashes import symBodyDigest
 
+from hashes import hash
+
 template mathop(op) {.dirty.} =
   registerCallback(c, "stdlib.math." & astToStr(op), `op Wrapper`)
 
@@ -157,3 +159,30 @@ proc registerAdditionalOps*(c: PCtx) =
       stackTrace(c, PStackFrame(prc: c.prc.sym, comesFrom: 0, next: nil), c.exceptionInstr,
                   "isExported() requires a symbol. '" & $n & "' is of kind '" & $n.kind & "'", n.info)
     setResult(a, sfExported in n.sym.flags)
+
+  proc hashVmImpl(a: VmArgs) =
+    var res = hashes.hash(a.getString(0), a.getInt(1).int, a.getInt(2).int)
+    if c.config.cmd == cmdCompileToJS:
+      # emulate JS's terrible integers:
+      res = cast[int32](res)
+    setResult(a, res)
+
+  registerCallback c, "stdlib.hashes.hashVmImpl", hashVmImpl
+
+  proc hashVmImplByte(a: VmArgs) =
+    # nkBracket[...]
+    let sPos = a.getInt(1).int
+    let ePos = a.getInt(2).int
+    let arr = a.getNode(0)
+    var bytes = newSeq[byte](arr.len)
+    for i in 0 ..< arr.len:
+      bytes[i] = byte(arr[i].intVal and 0xff)
+
+    var res = hashes.hash(bytes, sPos, ePos)
+    if c.config.cmd == cmdCompileToJS:
+      # emulate JS's terrible integers:
+      res = cast[int32](res)
+    setResult(a, res)
+
+  registerCallback c, "stdlib.hashes.hashVmImplByte", hashVmImplByte
+  registerCallback c, "stdlib.hashes.hashVmImplChar", hashVmImplByte