> {quote:title=Atle Smelvær wrote:}{quote}
> Hi there
>
> Have anyone tried to convert the MurmurHash3 to a optimized BASM version?
> This could really be a nice BASM challenge.
>
> Code snippet from MurmurHash3.cpp by Austin Appleby:
>
> void MurmurHash3_x86_32 ( const void * key, int len,
> uint32_t seed, void * out )
> {...}
>
> -Atle
Hi
I needed an Object Pascal port of MurmurHash3 (I had been using MurmurHash2, but see it's been superseded), so I'll offer that up here. Alas, it's not BASM, but a pure Pascal implementation is still pretty good.
function rotl32 (x: Cardinal; r: byte): Cardinal;
begin
Result := (x shl r) or (x shr (32 -r));
end;
// 32bit version
// TODO: -o Anyone -c write a 64bit version for wider pointers
function getblock (p: Pointer; i: Integer): Cardinal;
var lp: Pointer;
begin
lp := Pointer(Integer(p) + (i * SizeOf(Integer)));
result := Integer(lp^);
end;
function fmix(h: Cardinal): Cardinal;
begin
h := h xor (h shr 16);
h := h * $85EBCA6B;
h := h xor (h shr 13);
h := h * $C2B2AE35;
h := h xor (h shr 16);
Result := h;
end;
procedure MurmurHash3 (key: Pointer; len: Cardinal; seed: Cardinal; out: Pointer);
const c1: Cardinal = $CC9E2D51;
c2: Cardinal = $1B873593;
var data: PByte;
nblocks: Integer;
h1: Cardinal;
blocks: PCardinal;
i: Integer;
k1: Cardinal;
tail: PByte;
begin
data := PByte(key);
nblocks := len div 4; //number of 4byte chunks
h1 := seed;
//Body
// NB not 64bit safe
blocks := PCardinal( Integer(data) + (nblocks * 4) ); //Pointer to the end of the buffer (rounded to nearest 4)
//Read forward
for i := -nblocks to 0 do
begin
k1 := getblock(blocks, i); //read out the integer representation of the current block
k1 := k1 * c1;
k1 := rotl32(k1, 15);
k1 := k1 * c2;
h1 := h1 xor k1;
h1 := rotl32(h1, 13);
h1 := h1 * 5 + $E6546B64;
end;
//Tail
// NB not 64bit safe
tail := PByte( Integer(data) + (nblocks * 4) ); //Pointer to the last few bytes
k1 := 0;
i := len and 3; //how many bytes to clean up?
// NB not 64bit safe
if (i = 3) then k1 := k1 xor (PByte(Integer(tail) + 2)^ shl 16);
if (i >= 2) then k1 := k1 xor (PByte(Integer(tail) + 1)^ shl 8);
if (i >= 1) then k1 := k1 xor (tail^);
k1 := k1 * c1;
k1 := rotl32(k1,15);
k1 := k1 * c2;
h1 := h1 xor k1;
//Finalisation
h1 := h1 xor len;
h1 := fmix(h1);
PCardinal(out)^ := h1;
end;
As noted in comments, this isn't 64bit safe, so those with XE2 or using FPC, do beware :-)
Hope it's of some benefit to someone other than me!
DSP
Edited by: Duncan Parsons on Feb 29, 2012 7:39 AM