MurMurHash3 有 Delphi 实现吗？
Is there any Delphi implementation of MurMurHash3?
是否有任何 Delphi MurMurHash 3 的实现？我尝试自己实现它，但我的实现实际上比 MurMurHash2 慢。正常吗？
还有其他实现吗？
这是我的：
function MurMur3_32(const S: AnsiString; const Seed: LongWord=47b28c): LongWord;
const
c1 = $cc9e2d51;
c2 = b873593;
r1 = 15;
r2 = 13;
m = 5;
n = $e6546b64;
var
hash: LongWord;
len: LongWord;
k, k2: LongWord;
data: Integer;
begin
Hash := Seed;
len := Length(S);
//The default seed, 47b28c, is from the original C library
// Initialize the hash to a 'random' value
hash := seed xor len;
// Mix 4 bytes at a time into the hash
data := 1;
while(len >= 4) do
begin
k := PLongWord(@S[data])^;
k := k*c1;
k := (k shl r1) or (k shr (32 - r1));
k := k*c2;
hash := hash xor k;
hash := ((hash shl r2) or (hash shr (32 - r2))) * m + n;
Inc(Data, 4);
Dec(len, 4);
end;
k2 := 0;
{ Handle the last few bytes of the input array
S: ... f
}
Assert(len <= 3);
if len = 3 then
k2 := k2 xor (LongWord(s[data+2]) shl 16);
if len >= 2 then
k2 := k2 xor (LongWord(s[data+1]) shl 8);
if len >= 1 then
begin
k2 := k2 xor (LongWord(s[data]));
k2 := k2 * c1;
k2 := (k2 shl r1) or (k2 shr (32 - r1));
k2 := k2 * c2;
hash := hash xor k2;
end;
// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.
len := Length(S);
hash := hash xor len;
hash := hash xor (hash shr 16);
hash := hash * ebca6b;
hash := hash xor (hash shr 13);
hash := hash * $c2b2ae35;
hash := hash xor (hash shr 16);
Result := hash;
end;
免责声明：我不知道 Seed 值是否正确。
我在 https://github.com/JBontes/FastCode
的 FastDefaults 单元中有一个 murmurhash3 实现
这是 Murmurhash3 的源代码：
{$pointermath on}
function MurmurHash3(const [ref] HashData; Len: integer; Seed: integer = 0): integer;
const
c1 = $CC9E2D51;
c2 = B873593;
r1 = 15;
r2 = 13;
m = 5;
n = $E6546B64;
f1 = EBCA6B;
f2 = $C2B2AE35;
{$IFDEF purepascal}
var
i, Len2: integer;
k: cardinal;
remaining: cardinal;
Data: PCardinal;
label
case1, case2, case3, final;
begin
Result:= Seed;
Data:= @HashData;
for i:= 0 to (Len shr 2) - 1 do begin
k:= Data[i];
k:= k * c1;
k:= (k shl r1) or (k shr (32 - r1));
k:= k * c2;
Result:= Result xor k;
Result:= (Result shl r2) or (Result shr (32 - r2));
Result:= Result * m + n;
end; {for i}
Len2:= Len;
remaining:= 0;
case Len and of
1: goto case1;
2: goto case2;
3: goto case3;
else goto final;
end;
case3:
dec(Len2);
inc(remaining, PByte(Data)[Len2] shl 16);
case2:
dec(Len2);
inc(remaining, PByte(Data)[Len2] shl 8);
case1:
dec(Len2);
inc(remaining, PByte(Data)[Len2]);
remaining:= remaining * c1;
remaining:= (remaining shl r1) or (remaining shr (32 - r1));
remaining:= remaining * c2;
Result:= Result xor remaining;
final:
Result:= Result xor Len;
Result:= Result xor (Result shr 16);
Result:= Result * f1;
Result:= Result xor (Result shr 13);
Result:= Result * f2;
Result:= Result xor (Result shr 16);
end;
{$ELSE}
{$REGION 'asm'}
{$IFDEF CPUx86}
asm
push EBX
push EDI
push ESI
xchg ECX,EDX
//EAX = data
//ECX = count in bytes
//EDX = seed
mov ESI,ECX
shr ECX,2
jz @remaining_bytes
@loop:
mov EDI,[EAX]
imul EDI,EDI,c1
rol EDI,r1
imul EDI,EDI,c2
xor EDX,EDI
rol EDX,r2
lea EDX,[EDX*4+EDX+n]
lea EAX,[EAX+4]
dec ECX
jnz @loop
@remaining_bytes:
mov ECX,ESI
and ECX,
jz @finalization
xor EBX,EBX
dec ECX
mov BL,byte ptr [EAX+ECX]
jz @process_remaining
shl EBX,8
dec ECX
mov BL,byte ptr [EAX+ECX]
jz @process_remaining
shl EBX,8
mov BL,byte ptr [EAX]
@process_remaining:
imul EBX,EBX,c1
rol EBX,r1
imul EBX,EBX,c2
xor EDX,EBX
@finalization:
xor EDX,ESI
mov EAX,EDX
shr EDX,16
xor EDX,EAX
imul EDX,EDX,f1
mov EAX,EDX
shr EDX,13
xor EDX,EAX
imul EDX,EDX,f2
mov EAX,EDX
shr EDX,16
xor EAX,EDX
pop ESI
pop EDI
pop EBX
end;
{$ENDIF}
{$IFDEF CPUx64}
asm
push RBX
push RDI
push RSI
mov RAX,RCX
mov RCX,RDX
mov RDX,R8
//RAX = data
//RCX = count in bytes
//RDX = seed
mov ESI,ECX
shr ECX,2
jz @remaining_bytes
@loop:
mov EDI, dword ptr [RAX]
imul EDI,EDI,c1
rol EDI,r1
imul EDI,EDI,c2
xor EDX,EDI
rol EDX,r2
lea EDX,dword ptr [EDX*4+EDX+n] // *5 + n
lea RAX,qword ptr [RAX+4]
dec ECX
jnz @loop
@remaining_bytes:
mov ECX,ESI
and ECX,
jz @finalization
xor RBX,RBX
dec ECX
mov BL,byte ptr [RAX+RCX]
jz @process_remaining
shl EBX,8
dec ECX
mov BL,byte ptr [RAX+RCX]
jz @process_remaining
shl EBX,8
mov BL,byte ptr [RAX]
@process_remaining:
imul EBX,EBX,c1
rol EBX,r1
imul EBX,EBX,c2
xor EDX,EBX
@finalization:
xor EDX,ESI
mov EAX,EDX
shr EDX,16
xor EDX,EAX
imul EDX,EDX,f1
mov EAX,EDX
shr EDX,13
xor EDX,EAX
imul EDX,EDX,f2
mov EAX,EDX
shr EDX,16
xor EAX,EDX
pop RSI
pop RDI
pop RBX
end;
{$ENDIF}
{$ENDREGION}
{$ENDIF}
goto 用于模拟 C 的 fallthough switch/case 语句。
这种代码在 asm 中更容易编写，它比 asm Delphi 生成的寄存器使用更好。
为什么你的代码很慢
我唯一能看到问题的地方是：
Project42.dpr.54: while(len >= 4) do //a for loop is faster.
00420E17 83FE04 cmp esi,
00420E1A 7242 jb [=11=]420e5e
//This translates into inefficient code
Project42.dpr.56: k := PLongWord(@S[data])^;
00420E1C 8B0424 mov eax,[esp]
00420E1F 8D4438FF lea eax,[eax+edi-]
00420E23 8B00 mov eax,[eax]
三个间接内存引用和 read is misaligned!!
有关更多信息，请参见此处：Purpose of memory alignment 不要介意已接受的答案，请参见第二个答案。
双字的读取应该始终发生在双字边界上。
@pointer^ 技巧使编译器添加额外的间接级别（以及额外的内存往返（糟糕））。
使用{$pointermath on}并将指针作为数组寻址。
整数 != 指针
此外，使用 integer 存储指针也是错误的。
它会在 X64 中中断。 改用 NativeUInt。
我的版本中的等效代码转换为：
Project42.dpr.128: Data:= @HashData;
00420FCD 89442404 mov [esp+],eax
Project42.dpr.129: for i:= 0 to (Len shr 2) - 1 do begin
00420FD1 8B1C24 mov ebx,[esp]
00420FD4 C1EB02 shr ebx,
00420FD7 4B dec ebx
00420FD8 85DB test ebx,ebx
00420FDA 7C3E jl [=12=]42101a
00420FDC 43 inc ebx
00420FDD 33D2 xor edx,edx
////------------------------------------------///
Project42.dpr.130: k:= Data[i];
00420FDF 8B442404 mov eax,[esp+]
00420FE3 8B0490 mov eax,[eax+edx*4]
请注意，没有 更少不需要的间接内存引用并且读取已正确对齐。
当然asm版本稍微好一些，但是asm和pascal版本之间的差异应该小于两个Pascal版本之间的差异。
这就是我认为你的表现被浪费的地方。
未对齐的读取在 X86 上占用了大量（浪费的）周期。
在其他处理器上，减速甚至更糟。
代码的其他问题
将您的实现限制为字符串是一件坏事。
如果我想散列记录怎么办？
不要将二进制数据强制转换为字符串。
字符串不适合二进制数据。
只需使用无类型参数和指针。
种子值
我认为没有 正确的 种子值。按照我的理解，种子就在那里，所以你可以链式调用 Murmurhash。
您使用第一个散列的输出作为第二个 运行.
的种子
这样你就可以输入 2 个变量并获得与一次处理这两个变量相同的输出。
让我知道它们如何针对您的代码执行。
是否有任何 Delphi MurMurHash 3 的实现？我尝试自己实现它，但我的实现实际上比 MurMurHash2 慢。正常吗？ 还有其他实现吗？
这是我的：
function MurMur3_32(const S: AnsiString; const Seed: LongWord=47b28c): LongWord;
const
c1 = $cc9e2d51;
c2 = b873593;
r1 = 15;
r2 = 13;
m = 5;
n = $e6546b64;
var
hash: LongWord;
len: LongWord;
k, k2: LongWord;
data: Integer;
begin
Hash := Seed;
len := Length(S);
//The default seed, 47b28c, is from the original C library
// Initialize the hash to a 'random' value
hash := seed xor len;
// Mix 4 bytes at a time into the hash
data := 1;
while(len >= 4) do
begin
k := PLongWord(@S[data])^;
k := k*c1;
k := (k shl r1) or (k shr (32 - r1));
k := k*c2;
hash := hash xor k;
hash := ((hash shl r2) or (hash shr (32 - r2))) * m + n;
Inc(Data, 4);
Dec(len, 4);
end;
k2 := 0;
{ Handle the last few bytes of the input array
S: ... f
}
Assert(len <= 3);
if len = 3 then
k2 := k2 xor (LongWord(s[data+2]) shl 16);
if len >= 2 then
k2 := k2 xor (LongWord(s[data+1]) shl 8);
if len >= 1 then
begin
k2 := k2 xor (LongWord(s[data]));
k2 := k2 * c1;
k2 := (k2 shl r1) or (k2 shr (32 - r1));
k2 := k2 * c2;
hash := hash xor k2;
end;
// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.
len := Length(S);
hash := hash xor len;
hash := hash xor (hash shr 16);
hash := hash * ebca6b;
hash := hash xor (hash shr 13);
hash := hash * $c2b2ae35;
hash := hash xor (hash shr 16);
Result := hash;
end;
免责声明：我不知道 Seed 值是否正确。
我在 https://github.com/JBontes/FastCode
的 FastDefaults 单元中有一个 murmurhash3 实现这是 Murmurhash3 的源代码：
{$pointermath on}
function MurmurHash3(const [ref] HashData; Len: integer; Seed: integer = 0): integer;
const
c1 = $CC9E2D51;
c2 = B873593;
r1 = 15;
r2 = 13;
m = 5;
n = $E6546B64;
f1 = EBCA6B;
f2 = $C2B2AE35;
{$IFDEF purepascal}
var
i, Len2: integer;
k: cardinal;
remaining: cardinal;
Data: PCardinal;
label
case1, case2, case3, final;
begin
Result:= Seed;
Data:= @HashData;
for i:= 0 to (Len shr 2) - 1 do begin
k:= Data[i];
k:= k * c1;
k:= (k shl r1) or (k shr (32 - r1));
k:= k * c2;
Result:= Result xor k;
Result:= (Result shl r2) or (Result shr (32 - r2));
Result:= Result * m + n;
end; {for i}
Len2:= Len;
remaining:= 0;
case Len and of
1: goto case1;
2: goto case2;
3: goto case3;
else goto final;
end;
case3:
dec(Len2);
inc(remaining, PByte(Data)[Len2] shl 16);
case2:
dec(Len2);
inc(remaining, PByte(Data)[Len2] shl 8);
case1:
dec(Len2);
inc(remaining, PByte(Data)[Len2]);
remaining:= remaining * c1;
remaining:= (remaining shl r1) or (remaining shr (32 - r1));
remaining:= remaining * c2;
Result:= Result xor remaining;
final:
Result:= Result xor Len;
Result:= Result xor (Result shr 16);
Result:= Result * f1;
Result:= Result xor (Result shr 13);
Result:= Result * f2;
Result:= Result xor (Result shr 16);
end;
{$ELSE}
{$REGION 'asm'}
{$IFDEF CPUx86}
asm
push EBX
push EDI
push ESI
xchg ECX,EDX
//EAX = data
//ECX = count in bytes
//EDX = seed
mov ESI,ECX
shr ECX,2
jz @remaining_bytes
@loop:
mov EDI,[EAX]
imul EDI,EDI,c1
rol EDI,r1
imul EDI,EDI,c2
xor EDX,EDI
rol EDX,r2
lea EDX,[EDX*4+EDX+n]
lea EAX,[EAX+4]
dec ECX
jnz @loop
@remaining_bytes:
mov ECX,ESI
and ECX,
jz @finalization
xor EBX,EBX
dec ECX
mov BL,byte ptr [EAX+ECX]
jz @process_remaining
shl EBX,8
dec ECX
mov BL,byte ptr [EAX+ECX]
jz @process_remaining
shl EBX,8
mov BL,byte ptr [EAX]
@process_remaining:
imul EBX,EBX,c1
rol EBX,r1
imul EBX,EBX,c2
xor EDX,EBX
@finalization:
xor EDX,ESI
mov EAX,EDX
shr EDX,16
xor EDX,EAX
imul EDX,EDX,f1
mov EAX,EDX
shr EDX,13
xor EDX,EAX
imul EDX,EDX,f2
mov EAX,EDX
shr EDX,16
xor EAX,EDX
pop ESI
pop EDI
pop EBX
end;
{$ENDIF}
{$IFDEF CPUx64}
asm
push RBX
push RDI
push RSI
mov RAX,RCX
mov RCX,RDX
mov RDX,R8
//RAX = data
//RCX = count in bytes
//RDX = seed
mov ESI,ECX
shr ECX,2
jz @remaining_bytes
@loop:
mov EDI, dword ptr [RAX]
imul EDI,EDI,c1
rol EDI,r1
imul EDI,EDI,c2
xor EDX,EDI
rol EDX,r2
lea EDX,dword ptr [EDX*4+EDX+n] // *5 + n
lea RAX,qword ptr [RAX+4]
dec ECX
jnz @loop
@remaining_bytes:
mov ECX,ESI
and ECX,
jz @finalization
xor RBX,RBX
dec ECX
mov BL,byte ptr [RAX+RCX]
jz @process_remaining
shl EBX,8
dec ECX
mov BL,byte ptr [RAX+RCX]
jz @process_remaining
shl EBX,8
mov BL,byte ptr [RAX]
@process_remaining:
imul EBX,EBX,c1
rol EBX,r1
imul EBX,EBX,c2
xor EDX,EBX
@finalization:
xor EDX,ESI
mov EAX,EDX
shr EDX,16
xor EDX,EAX
imul EDX,EDX,f1
mov EAX,EDX
shr EDX,13
xor EDX,EAX
imul EDX,EDX,f2
mov EAX,EDX
shr EDX,16
xor EAX,EDX
pop RSI
pop RDI
pop RBX
end;
{$ENDIF}
{$ENDREGION}
{$ENDIF}
goto 用于模拟 C 的 fallthough switch/case 语句。
这种代码在 asm 中更容易编写，它比 asm Delphi 生成的寄存器使用更好。
为什么你的代码很慢
我唯一能看到问题的地方是：
Project42.dpr.54: while(len >= 4) do //a for loop is faster.
00420E17 83FE04 cmp esi,
00420E1A 7242 jb [=11=]420e5e
//This translates into inefficient code
Project42.dpr.56: k := PLongWord(@S[data])^;
00420E1C 8B0424 mov eax,[esp]
00420E1F 8D4438FF lea eax,[eax+edi-]
00420E23 8B00 mov eax,[eax]
三个间接内存引用和 read is misaligned!!
有关更多信息，请参见此处：Purpose of memory alignment 不要介意已接受的答案，请参见第二个答案。
双字的读取应该始终发生在双字边界上。
@pointer^ 技巧使编译器添加额外的间接级别（以及额外的内存往返（糟糕））。
使用{$pointermath on}并将指针作为数组寻址。
整数 != 指针
此外，使用 integer 存储指针也是错误的。
它会在 X64 中中断。 改用 NativeUInt。
我的版本中的等效代码转换为：
Project42.dpr.128: Data:= @HashData;
00420FCD 89442404 mov [esp+],eax
Project42.dpr.129: for i:= 0 to (Len shr 2) - 1 do begin
00420FD1 8B1C24 mov ebx,[esp]
00420FD4 C1EB02 shr ebx,
00420FD7 4B dec ebx
00420FD8 85DB test ebx,ebx
00420FDA 7C3E jl [=12=]42101a
00420FDC 43 inc ebx
00420FDD 33D2 xor edx,edx
////------------------------------------------///
Project42.dpr.130: k:= Data[i];
00420FDF 8B442404 mov eax,[esp+]
00420FE3 8B0490 mov eax,[eax+edx*4]
请注意，没有 更少不需要的间接内存引用并且读取已正确对齐。
当然asm版本稍微好一些，但是asm和pascal版本之间的差异应该小于两个Pascal版本之间的差异。
这就是我认为你的表现被浪费的地方。
未对齐的读取在 X86 上占用了大量（浪费的）周期。
在其他处理器上，减速甚至更糟。
代码的其他问题
将您的实现限制为字符串是一件坏事。
如果我想散列记录怎么办？
不要将二进制数据强制转换为字符串。
字符串不适合二进制数据。
只需使用无类型参数和指针。
种子值
我认为没有 正确的 种子值。按照我的理解，种子就在那里，所以你可以链式调用 Murmurhash。
您使用第一个散列的输出作为第二个 运行.
的种子
这样你就可以输入 2 个变量并获得与一次处理这两个变量相同的输出。
让我知道它们如何针对您的代码执行。