To: Atle Smelvær
From: Duncan Parsons
Newsgroup: embarcadero.public.delphi.language.basm
 
29-Feb-2012

Re: MurmurHash3 32bit BASM implementation [Edit]

> {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
 
Originally created by
Tamarack Associates
Thu, 28 Mar 2024 19:35:58 UTC
Copyright © 2009-2024
HREF Tools Corp.