I'm implementing a variation of the SuperFastHash in VBA for use in Excel (32-bit version, so no LongLong available) to hash strings.
To get around the limitations of signed 32-bit Long values, I'm doing the addition and bit-shifting using Double types, and then converting from Double to Long in a way that truncates it at 31 bits (the maximum positive value -- don't want to deal with two's complement and signs).
I'm getting answers and avoiding overflows so far, but I have a suspicion I'm making some mistakes in translation, since most implementations use all 32 bits of a uint and also deal with individual bytes from an array rather than 16-bit values coming from AscW().
Any suggestions of improvement, especially of the string-handling, bit-shifting, or the final avalanche?
Public Function shr(ByVal Value As Long, ByVal Shift As Byte) As Long
shr = Value
If Shift > 0 Then shr = shr \ (2 ^ Shift)
End Function
Public Function shl(ByVal Value As Long, ByVal Shift As Byte) As Long
If Shift > 0 Then
shl = LimitDouble(CDbl(Value) * (2& ^ Shift))
Else
shl = Value
End If
End Function
Public Function LimitDouble(ByVal d As Double) As Long
'' Prevent overflow by lopping off anything beyond 31 bits
Const MaxNumber As Double = 2 ^ 31
LimitDouble = CLng(d - (Fix(d / MaxNumber) * MaxNumber))
End Function
Public Function SuperFastHash(ByVal dataToHash As String) As Long
Dim dataLength As Long
dataLength = Len(dataToHash)
If (dataLength = 0) Then
SuperFastHash = 0
Exit Function
End If
Dim hash As Long
hash = dataLength
Dim remainingBytes As Integer
remainingBytes = dataLength Mod 2
Dim numberOfLoops As Integer
numberOfLoops = dataLength \ 2
Dim currentIndex As Integer
currentIndex = 0
Dim tmp As Double
Do While (numberOfLoops > 0)
hash = LimitDouble(CDbl(hash) + AscW(Mid$(dataToHash, currentIndex + 1, 1)))
tmp = shl(AscW(Mid$(dataToHash, currentIndex + 2, 1)), 11) Xor hash
hash = shl(hash, 16) Xor tmp
hash = LimitDouble(CDbl(hash) + shr(hash, 11))
currentIndex = currentIndex + 2
numberOfLoops = numberOfLoops - 1
Loop
If remainingBytes = 1 Then
hash = LimitDouble(CDbl(hash) + AscW(Mid$(dataToHash, currentIndex + 1, 1)))
hash = hash Xor shl(hash, 10)
hash = LimitDouble(CDbl(hash) + shr(hash, 1))
End If
'' Final avalanche
hash = hash Xor shl(hash, 3)
hash = LimitDouble(CDbl(hash) + shr(hash, 5))
hash = hash Xor shl(hash, 4)
hash = LimitDouble(CDbl(hash) + shr(hash, 17))
hash = hash Xor shl(hash, 25)
hash = LimitDouble(CDbl(hash) + shr(hash, 6))
SuperFastHash = hash
End Function
Decimal
data type? From excel helpDecimal variables are stored as 96-bit (12-byte) signed integers scaled by a variable power of 10
.Decimal
can store 32bit or 64 bit unsigned integers \$\endgroup\$ – chris neilsen Oct 10 '12 at 9:44