Hasher Crystal draft

hasher.cr

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