Skip to content

Instantly share code, notes, and snippets.

@funny-falcon funny-falcon/hasher.cr
Last active Jun 17, 2017

Embed
What would you like to do?
Hasher Crystal draft
require "secure_random"
require "static_array"
module Hashing
alias Type = UInt32
@@seed = uninitialized StaticArray(UInt32, 6)
struct StdHasher
# lucky777 hash https://github.com/funny-falcon/fanom_hash/blob/master/lucky777.h
struct Impl
def initialize(@a : UInt32, @b : UInt32)
end
def permute(v : UInt32)
permute(v.to_u32, pointerof(@a), pointerof(@b))
end
def permute_nil
# xor-shift generator
# hope state is not all-zero :-)
t = @a ^ (@a << 10)
@a = @b
@b ^= (@b >> 10) ^ t ^ (t >> 13)
end
def finish(seed)
a, b = @a, @b + seed
a ^= b; a += rotl(b, 3);
b ^= a; b -= rotr(a, 5);
a ^= b; a += rotl(b, 8);
b ^= a; b += rotr(a, 16);
b
end
def hash_bytes(buf : Bytes)
bsz = buf.size
v = bsz.to_u32 << 24
u = buf.to_unsafe
a, b = @a, @b
i = bsz.unsafe_div 4
while i > 0
permute(u.as(Pointer(UInt32)).value, pointerof(a), pointerof(b))
u += 4
i -= 1
end
r = (bsz&3).to_u32
if r != 0
v |= u[0].to_u32|(u[r/2].to_u32<<8)|(u[r-1].to_u32<<16)
end
permute(v, pointerof(a), pointerof(b))
@a, @b = a, b
self
end
private def permute(v : UInt32, a : Pointer(UInt32), b : Pointer(UInt32))
a.value += v
b.value ^= a.value
a.value = rotl(a.value, 7) - b.value
b.value = rotr(b.value, 7) ^ a.value
a.value = rotl(a.value, 7)
end
private def rotl(v : UInt32, sh)
(v << sh) | (v >> (sizeof(UInt32) * 8 - sh))
end
private def rotr(v : UInt32, sh)
(v << (sizeof(UInt32) * 8 - sh)) | (v >> sh)
end
end
@@seed = uninitialized StaticArray(UInt32, 6)
def self.init
buf = uninitialized StaticArray(UInt8, sizeof(UInt32[6]))
SecureRandom.random_bytes(buf.to_slice)
@@seed = pointerof(buf).as(Pointer(UInt32[6])).value
end
init
private def initialize(@h : Pointer(Impl))
end
def initialize
@h = Pointer(Impl).malloc(1,
Impl.new(@@seed[0], @@seed[1])
)
end
def self.build
h = Impl.new(@@seed[0], @@seed[1])
s = new(pointerof(h))
yield s
s.finish
end
def <<(v : Nil)
@h.value.permute_nil
self
end
def <<(v : Int8|Int16|Int32|UInt8|UInt16|UInt32)
@h.value.permute(v.to_u32)
self
end
def <<(v : UInt64)
@h.value.permute(v.to_u32)
@h.value.permute((v>>32).to_u32)
self
end
def <<(v : Int64)
self << v.to_u64
end
def <<(v)
v.hash(self)
self
end
def hash_bytes(b : Bytes)
@h.value.hash_bytes(b)
self
end
def finish
@h.value.finish(@@seed[2])
end
def self.fasthash_u32(v : UInt32)
h = @@seed[3] + v
h ^= h >> 16
h *= 0x52c6a2d9_u32
h += @@seed[4]
h ^ (h >> 16)
end
def self.fasthash_u16(v : Int8|UInt8|UInt16|UInt8)
h = @@seed[5] + v.to_u32
h *= 0x52c6a2d9_u32
h ^ (h >> 16)
end
end
end
class String
def hash(hasher)
hasher.hash_bytes(to_slice)
end
end
struct Float64
def hash
Hashing::StdHasher.build do |h|
h << self
end
end
def hash(hasher)
hasher << unsafe_as(UInt64)
end
end
struct Int
def hash(hasher)
hasher << self
end
end
class Object
def hash
Hashing::StdHasher.build do |h|
h << self
end
end
def hash(hasher)
hasher << object_id
end
end
struct Nil
def hash(hasher)
hasher << nil
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.