#### SpookyHash
#### Copyright (c) 2023-2024, Remilia Scarlet
#### Copyright (c) 2015, Guillaume Voirin
#### BSD 3-Clause License
####
#### All rights reserved.
####
#### Redistribution and use in source and binary forms, with or without
#### modification, are permitted provided that the following conditions are met:
####
#### Redistributions of source code must retain the above copyright notice,
#### this list of conditions and the following disclaimer.
####
#### Redistributions in binary form must reproduce the above copyright
#### notice, this list of conditions and the following disclaimer in the
#### documentation and/or other materials provided with the distribution.
####
#### Neither the name of the copyright holder nor the names of its
#### contributors may be used to endorse or promote products derived from
#### this software without specific prior written permission.
####
#### THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
#### AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
#### IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
#### ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
#### LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
#### CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
#### SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
#### INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
#### CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
#### ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
#### POSSIBILITY OF SUCH DAMAGE.
require "./globals"
####
#### Core internal functionality.
####
# :nodoc:
# Hacky stuff.
lib SpookyHashLib
union DataUnion
p8 : Pointer(UInt8)
p32 : Pointer(UInt32)
p64 : Pointer(UInt64)
i : LibC::SizeT
end
union DataUnion128
p8 : Pointer(UInt8)
p64 : Pointer(UInt64)
i : LibC::SizeT
end
end
class RemiLib::Digest::SpookyHash
@data : Slice(UInt64) = Slice(UInt64).new(2 * SPOOKYHASH_VARIABLES, 0u64)
@state : Slice(UInt64) = Slice(UInt64).new(SPOOKYHASH_VARIABLES, 0u64)
@length : Int64 = 0
@remainder : UInt8 = 0
@[AlwaysInline]
protected def self.shortEnd(h0 : PUInt64, h1 : PUInt64, h2 : PUInt64, h3 : PUInt64) : Nil
h3.value ^= h2.value
h2.value = rotate(h2.value, 15)
h3.value = h3.value &+ h2.value
h0.value ^= h3.value
h3.value = rotate(h3.value, 52)
h0.value = h0.value &+ h3.value
h1.value ^= h0.value
h0.value = rotate(h0.value, 26)
h1.value = h1.value &+ h0.value
h2.value ^= h1.value
h1.value = rotate(h1.value, 51)
h2.value = h2.value &+ h1.value
h3.value ^= h2.value
h2.value = rotate(h2.value, 28)
h3.value = h3.value &+ h2.value
h0.value ^= h3.value
h3.value = rotate(h3.value, 9)
h0.value = h0.value &+ h3.value
h1.value ^= h0.value
h0.value = rotate(h0.value, 47)
h1.value = h1.value &+ h0.value
h2.value ^= h1.value
h1.value = rotate(h1.value, 54)
h2.value = h2.value &+ h1.value
h3.value ^= h2.value
h2.value = rotate(h2.value, 32)
h3.value = h3.value &+ h2.value
h0.value ^= h3.value
h3.value = rotate(h3.value, 25)
h0.value = h0.value &+ h3.value
h1.value ^= h0.value
h0.value = rotate(h0.value, 63)
h1.value = h1.value &+ h0.value
end
@[AlwaysInline]
protected def self.shortMix(h0 : PUInt64, h1 : PUInt64, h2 : PUInt64, h3 : PUInt64) : Nil
h2.value = rotate(h2.value, 50)
h2.value = h2.value &+ h3.value
h0.value ^= h2.value
h3.value = rotate(h3.value, 52)
h3.value = h3.value &+ h0.value
h1.value ^= h3.value
h0.value = rotate(h0.value, 30)
h0.value = h0.value &+ h1.value
h2.value ^= h0.value
h1.value = rotate(h1.value, 41)
h1.value = h1.value &+ h2.value
h3.value ^= h1.value
h2.value = rotate(h2.value, 54)
h2.value = h2.value &+ h3.value
h0.value ^= h2.value
h3.value = rotate(h3.value, 48)
h3.value = h3.value &+ h0.value
h1.value ^= h3.value
h0.value = rotate(h0.value, 38)
h0.value = h0.value &+ h1.value
h2.value ^= h0.value
h1.value = rotate(h1.value, 37)
h1.value = h1.value &+ h2.value
h3.value ^= h1.value
h2.value = rotate(h2.value, 62)
h2.value = h2.value &+ h3.value
h0.value ^= h2.value
h3.value = rotate(h3.value, 34)
h3.value = h3.value &+ h0.value
h1.value ^= h3.value
h0.value = rotate(h0.value, 5)
h0.value = h0.value &+ h1.value
h2.value ^= h0.value
h1.value = rotate(h1.value, 36)
h1.value = h1.value &+ h2.value
h3.value ^= h1.value
end
@[AlwaysInline]
protected def self.finishPartial(h0 : PUInt64, h1 : PUInt64, h2 : PUInt64, h3 : PUInt64, h4 : PUInt64,
h5 : PUInt64, h6 : PUInt64, h7 : PUInt64, h8 : PUInt64, h9 : PUInt64,
h10 : PUInt64, h11 : PUInt64) : Nil
h11.value = h11.value &+ h1.value
h2.value ^= h11.value
h1.value = rotate(h1.value, 44)
h0.value = h0.value &+ h2.value
h3.value ^= h0.value
h2.value = rotate(h2.value, 15)
h1.value = h1.value &+ h3.value
h4.value ^= h1.value
h3.value = rotate(h3.value, 34)
h2.value = h2.value &+ h4.value
h5.value ^= h2.value
h4.value = rotate(h4.value, 21)
h3.value = h3.value &+ h5.value
h6.value ^= h3.value
h5.value = rotate(h5.value, 38)
h4.value = h4.value &+ h6.value
h7.value ^= h4.value
h6.value = rotate(h6.value, 33)
h5.value = h5.value &+ h7.value
h8.value ^= h5.value
h7.value = rotate(h7.value, 10)
h6.value = h6.value &+ h8.value
h9.value ^= h6.value
h8.value = rotate(h8.value, 13)
h7.value = h7.value &+ h9.value
h10.value ^= h7.value
h9.value = rotate(h9.value, 38)
h8.value = h8.value &+ h10.value
h11.value ^= h8.value
h10.value = rotate(h10.value, 53)
h9.value = h9.value &+ h11.value
h0.value ^= h9.value
h11.value = rotate(h11.value, 42)
h10.value = h10.value &+ h0.value
h1.value ^= h10.value
h0.value = rotate(h0.value, 54)
end
@[AlwaysInline]
protected def self.finish(data : PUInt64, h0 : PUInt64, h1 : PUInt64, h2 : PUInt64, h3 : PUInt64, h4 : PUInt64,
h5 : PUInt64, h6 : PUInt64, h7 : PUInt64, h8 : PUInt64, h9 : PUInt64,
h10 : PUInt64, h11 : PUInt64) : Nil
h0.value = h0.value &+ little(data.[0])
h1.value = h1.value &+ little(data.[1])
h2.value = h2.value &+ little(data.[2])
h3.value = h3.value &+ little(data.[3])
h4.value = h4.value &+ little(data.[4])
h5.value = h5.value &+ little(data.[5])
h6.value = h6.value &+ little(data.[6])
h7.value = h7.value &+ little(data.[7])
h8.value = h8.value &+ little(data.[8])
h9.value = h9.value &+ little(data.[9])
h10.value = h10.value &+ little(data.[10])
h11.value = h11.value &+ little(data.[11])
finishPartial(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11)
finishPartial(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11)
finishPartial(h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11)
end
@[AlwaysInline]
protected def self.mix(data : PUInt64, s0 : PUInt64, s1 : PUInt64, s2 : PUInt64, s3 : PUInt64, s4 : PUInt64,
s5 : PUInt64, s6 : PUInt64, s7 : PUInt64, s8 : PUInt64, s9 : PUInt64,
s10 : PUInt64, s11 : PUInt64) : Nil
s0.value = s0.value &+ little(data[0])
s2.value ^= s10.value
s11.value ^= s0.value
s0.value = rotate(s0.value, 11)
s11.value = s11.value &+ s1.value
s1.value = s1.value &+ little(data[1])
s3.value ^= s11.value
s0.value ^= s1.value
s1.value = rotate(s1.value, 32)
s0.value = s0.value &+ s2.value
s2.value = s2.value &+ little(data[2])
s4.value ^= s0.value
s1.value ^= s2.value
s2.value = rotate(s2.value, 43)
s1.value = s1.value &+ s3.value
s3.value = s3.value &+ little(data[3])
s5.value ^= s1.value
s2.value ^= s3.value
s3.value = rotate(s3.value, 31)
s2.value = s2.value &+ s4.value
s4.value = s4.value &+ little(data[4])
s6.value ^= s2.value
s3.value ^= s4.value
s4.value = rotate(s4.value, 17)
s3.value = s3.value &+ s5.value
s5.value = s5.value &+ little(data[5])
s7.value ^= s3.value
s4.value ^= s5.value
s5.value = rotate(s5.value, 28)
s4.value = s4.value &+ s6.value
s6.value = s6.value &+ little(data[6])
s8.value ^= s4.value
s5.value ^= s6.value
s6.value = rotate(s6.value, 39)
s5.value = s5.value &+ s7.value
s7.value = s7.value &+ little(data[7])
s9.value ^= s5.value
s6.value ^= s7.value
s7.value = rotate(s7.value, 57)
s6.value = s6.value &+ s8.value
s8.value = s8.value &+ little(data[8])
s10.value ^= s6.value
s7.value ^= s8.value
s8.value = rotate(s8.value, 55)
s7.value = s7.value &+ s9.value
s9.value = s9.value &+ little(data[9])
s11.value ^= s7.value
s8.value ^= s9.value
s9.value = rotate(s9.value, 54)
s8.value = s8.value &+ s10.value
s10.value = s10.value &+ little(data[10])
s0.value ^= s8.value
s9.value ^= s10.value
s10.value = rotate(s10.value, 22)
s9.value = s9.value &+ s11.value
s11.value = s11.value &+ little(data[11])
s1.value ^= s9.value
s10.value ^= s11.value
s11.value = rotate(s11.value, 46)
s10.value = s10.value &+ s0.value
end
@[AlwaysInline]
protected def self.short(message : PUInt8, len : Int, hash1 : PUInt64, hash2 : PUInt64) : Nil
buffer : Slice(UInt64) = Slice(UInt64).new(2 * SPOOKYHASH_VARIABLES, 0u64)
bufferPtr : PUInt64 = buffer.to_unsafe
u : SpookyHashLib::DataUnion = SpookyHashLib::DataUnion.new
u.p8 = message
if bitflag?(u.i, 0x07)
(bufferPtr.unsafe_as(PUInt8)).copy_from(message, len)
u.p64 = bufferPtr
end
remainder : Int32 = (len % 32).to_i32!
a : UInt64 = hash1.value
b : UInt64 = hash2.value
c : UInt64 = SPOOKYHASH_CONSTANT
d : UInt64 = SPOOKYHASH_CONSTANT
aPtr : PUInt64 = pointerof(a)
bPtr : PUInt64 = pointerof(b)
cPtr : PUInt64 = pointerof(c)
dPtr : PUInt64 = pointerof(d)
if len > 15
finish = u.p64 + (len.tdiv(32) &* 4)
while u.p64 < finish
c = c &+ little(u.p64[0])
d = d &+ little(u.p64[1])
shortMix(aPtr, bPtr, cPtr, dPtr)
a = a &+ little(u.p64[2])
b = b &+ little(u.p64[3])
u.p64 += 4
end
if remainder >= 16
c = c &+ little(u.p64[0])
d = d &+ little(u.p64[1])
shortMix(aPtr, bPtr, cPtr, dPtr)
u.p64 += 2
remainder = remainder &- 16
end
end
d = d &+ len.to_u64!.unsafe_shl(56)
# Crystal needs a fallthrough statement ^_^;
case remainder
when 15
d = d &+ u.p8[14].to_u64!.unsafe_shl(48)
d = d &+ u.p8[13].to_u64!.unsafe_shl(40)
d = d &+ u.p8[12].to_u64!.unsafe_shl(32)
d = d &+ u.p32[2]
c = c &+ u.p64[0]
when 14
d = d &+ u.p8[13].to_u64!.unsafe_shl(40)
d = d &+ u.p8[12].to_u64!.unsafe_shl(32)
d = d &+ u.p32[2]
c = c &+ u.p64[0]
when 13
d = d &+ u.p8[12].to_u64!.unsafe_shl(32)
d = d &+ u.p32[2]
c = c &+ u.p64[0]
when 12
d = d &+ u.p32[2]
c = c &+ u.p64[0]
when 11
d = d &+ u.p8[10].to_u64!.unsafe_shl(16)
d = d &+ u.p8[9].to_u64!.unsafe_shl(8)
d = d &+ u.p8[8].to_u64!
c = c &+ u.p64[0]
when 10
d = d &+ u.p8[9].to_u64!.unsafe_shl(8)
d = d &+ u.p8[8].to_u64!
c = c &+ u.p64[0]
when 9
d = d &+ u.p8[8].to_u64!
c = c &+ u.p64[0]
when 8
c = c &+ u.p64[0]
when 7
c = c &+ u.p8[6].to_u64!.unsafe_shl(48)
c = c &+ u.p8[5].to_u64!.unsafe_shl(40)
c = c &+ u.p8[4].to_u64!.unsafe_shl(32)
c = c &+ u.p32[0]
when 6
c = c &+ u.p8[5].to_u64!.unsafe_shl(40)
c = c &+ u.p8[4].to_u64!.unsafe_shl(32)
c = c &+ u.p32[0]
when 5
c = c &+ u.p8[4].to_u64!.unsafe_shl(32)
c = c &+ u.p32[0]
when 4
c = c &+ u.p32[0]
when 3
c = c &+ u.p8[2].to_u64!.unsafe_shl(16)
c = c &+ u.p8[1].to_u64!.unsafe_shl(8)
c = c &+ u.p8[0].to_u64!
when 2
c = c &+ u.p8[1].to_u64!.unsafe_shl(8)
c = c &+ u.p8[0].to_u64!
when 1
c = c &+ u.p8[0].to_u64!
when 0
c = c &+ SPOOKYHASH_CONSTANT
d = d &+ SPOOKYHASH_CONSTANT
end
shortEnd(aPtr, bPtr, cPtr, dPtr)
hash1.value = a
hash2.value = b
end
end