# Build:
#  crystal build --release checksum.cr
# Run:
#  ./checksum current | tee checksum_current.out
#  ./checksum correct | tee checksum_correct.out

struct BA
  def initialize
    @bytes = Pointer(UInt8).malloc(1u32<<31)
    @extra = Hash(UInt32,UInt32).new(0)
  end

  def [](index : UInt32) : UInt32
    ix, off = index.divmod(2)
    off *= 4
    v = @bytes[ix]
    v = (v>>off) & 0xf
    v < 0xf ? v.to_u32 : @extra[index]
  end

  def []=(index : UInt32, value : UInt32)
    ix, off = index.divmod(2)
    off *= 4
    b = @bytes[ix]
    if value < 0xf
      b &= ~(0xfu8 << off)
      b |= value.to_u8 << off
    else
      b |= 0xfu8 << off
      @extra[index] = value
    end
    @bytes[ix] = b
    value
  end
end

ba = BA.new

FNV = 16777619u32
case (ARGV[0]||"current")
when "current"
  0u32.upto(~0u32) do |i|
    c : UInt32 = i &* (FNV ^ (i >> 17))
    ba[c] += 1
  end
when "correct"
  0u32.upto(~0u32) do |i|
    c : UInt32 = (i &* FNV) ^ (i >> 17)
    ba[c] += 1
  end
when "murmur"
  0u32.upto(~0u32) do |i|
    c : UInt32 = i ^ (i >> 16)
    c = c &* 0x85ebca6bu32
    c ^= c >> 13
    c = c &* 0xc2b2ae35u32
    c ^= c >> 16
    ba[c] += 1
  end
else
  raise "Unrecognized algo"
end

collisions = Hash(UInt32, UInt64).new(0)
0u32.upto(~0u32) do |i|
  v = ba[i]
  collisions[v] += 1
  if v >= 255
    printf "Pathologic %d collisions at slot %08x\n", v, i
  end
end

collisions.to_a.
    sort_by{|k,v| k}.
    reverse.
    each do |k,v|
  printf "- %d items at %d slots\n", k, v
end