32-bit xxhash

[IcedQuinn]

I ported this over from my Nim port out of curiosity. Not sure yet if I will bring over 64-bit and XX3 and a test rig.

I use xxhash to run my hopscotch tables since its supposed to be resistant to shenanigans.

global xxhash = @record {}

global xxhash.version_major   <const, comptime> = 0
global xxhash.version_minor   <const, comptime> = 7
global xxhash.version_release <const, comptime> = 4
-- TODO get preprocessor to compute this
global xxhash.version_number  <const, comptime> = (xxhash.version_major * 100 * 100 + xxhash.version_minor * 100 + xxhash.version_release)

local secret_size_min      <const> = 136
local secret_default_size  <const> = 192 -- minimum XXH3_SECRET_SIZE_MIN
local internal_buffer_size <const> = 256

local alignment = @enum{
  unaligned = 0,
  aligned
}

local prime32: []uint32 <const> = {
  0x9E3779B1, -- 0b10011110001101110111100110110001
  0x85EBCA77, -- 0b10000101111010111100101001110111
  0xC2B2AE3D, -- 0b11000010101100101010111000111101
  0x27D4EB2F, -- 0b00100111110101001110101100101111
  0x165667B1, -- 0b00010110010101100110011110110001
}

local prime64: []uint64 <const> = {
  0x9E3779B185EBCA87, -- 0b1001111000110111011110011011000110000101111010111100101010000111
  0xC2B2AE3D27D4EB4F, -- 0b1100001010110010101011100011110100100111110101001110101101001111
  0x165667B19E3779F9, -- 0b0001011001010110011001111011000110011110001101110111100111111001
  0x85EBCA77C2B2AE63, -- 0b1000010111101011110010100111011111000010101100101010111001100011
  0x27D4EB2F165667C5, -- 0b0010011111010100111010110010111100010110010101100110011111000101
}

global xxhash.state32 = @record {
  total_len_32: uint32,
  large_len: uint32,
  v: [4]uint32,
  mem32: [4]uint32,
  memsize: uint32,
}

global xxhash.state64 = @record {
  total_len: uint64,
  large_len: uint64,
  v: [4]uint64,
  mem: [4]uint64,
  memsize: uint64,
}

-- TODO compiler-specific primitives
-- clang/gcc
--  define XXH_rotl32 __builtin_rotateleft32
--  define XXH_rotl64 __builtin_rotateleft64
-- msvc
--  define XXH_rotl32(x,r) _rotl(x,r)
--  define XXH_rotl64(x,r) _rotl64(x,r)

local function rotl32(x: uint32, r: uint32): uint32 <inline>
  return ((x << r) | (x >> (32 - r)))
end

local function rotl64(x: uint64, r: uint64): uint64 <inline>
  return ((x << r) | (x >> (64 - r)))
end

-- TODO compiler-specific primitives
-- clang/gcc
--  define XXH_swap32 __builtin_bswap32
-- msvc
--  define XXH_swap32 _byteswap_ulong
local function swap32(x: uint32): uint32 <inline>
    return ((x << 24) & 0xff000000 ) |
           ((x <<  8) & 0x00ff0000 ) |
           ((x >>  8) & 0x0000ff00 ) |
           ((x >> 24) & 0x000000ff )
end

local function round32(acc: uint32, input: uint32): uint32 <inline>
  local result = acc
  result = result + (input * prime32[1])
  result = rotl32(result, 13)
  result = result * (prime32[0])
  return result
end

local function avalanche32(h32: uint32): uint32 <inline>
  local result = h32
  result = result ~ (result >> 15)
  result = result * prime32[1]
  result = result ~ (result >> 13)
  result = result * prime32[2]
  result = result ~ (result >> 16)
  return result
end

local function read32(p: pointer): uint32 <inline>
  return $(@*uint32)(p)
end

local function read_le32(p: pointer): uint32 <inline>
  if #[is_little_endian]# then
    return read32(p)
  else
    return swap32(read32(p))
  end
end

local function read_be32(p: pointer): uint32 <inline>
  if #[is_little_endian]# then
    return swap32(read32(p))
  else
    return read32(p)
  end
end

local function read_le32_align(p: pointer, align: alignment): uint32 <inline>
  -- XXX i think the alignment hint here is for SIMD optimized versions
  return read_le32(p)
end

local function finalize32(ch32: uint32, cp: pointer, clen: integer, align: alignment): uint32
  local h32 = ch32
  local p   = (@isize)(cp)
  local len = clen & 15

  while len >= 4 do
    h32 = h32 + (read_le32_align((@pointer)(p), align) * prime32[2])
    p = p + 4
    h32  = rotl32(h32, 17) * prime32[3]
    len = len - 4
  end

  while len > 0 do
    h32 = h32 + ($(@*uint8)(p) * prime32[4])
    p = p + 1
    h32 = rotl32(h32, 11) * prime32[0]
    len = len - 1
  end

  return avalanche32(h32)
end

local function endian_align32(cinput: pointer, clen: integer, seed: uint32, align: alignment): uint32
  local input: auto = (@isize)(cinput)
  local bEnd: auto = input + clen;
  local h32: uint32
  local len = clen

  if cinput == nil then
    len   = 0
    bEnd  = 16
    input = bEnd
  end

  if len >= 16 then
    local limit <const> = bEnd - 15

    local v1: uint32 = seed + prime32[0] + prime32[1]
    local v2: uint32 = seed + prime32[1]
    local v3: uint32 = seed + 0
    local v4: uint32 = seed - prime32[0]

    while input < limit do
      ## for i=1,4 do
      #|'v'..i|# = round32(#|'v'..i|#, read_le32_align((@pointer)(input), align))
      input = input + 4
      ## end
    end

    h32 = rotl32(v1, 1) + rotl32(v2, 7) + rotl32(v3, 12) + rotl32(v4, 18)
  else
    h32 = seed + prime32[4]
  end

  h32 = h32 + (@uint32)(len)

  return finalize32(h32, (@pointer)(input), len & 15, align)
end

function xxhash.xx32(input: pointer, len: integer, seed: uint32): uint32
  if (@isize)(input) & 3 == 0 then
    -- Input is 4-bytes aligned, leverage the speed benefit
    return endian_align32(input, len, seed, alignment.aligned)
  else
    return endian_align32(input, len, seed, alignment.unaligned)
  end
end

local slug = "#test-string-one"
local slug2 = "#test-string-two"
-- XXX deep hack; nelua string is a struct of {int_8*, size_t}
print(xxhash.xx32($(@*pointer)(&slug), #slug, 0))
print(xxhash.xx32($(@*pointer)(&slug2), #slug2, 0))