title: Most Efficient Unicode Hash Function for Delphi 2009
body: <p>I am in need of the fastest hash function possible in Delphi 2009 that will create hashed values from a Unicode string that will distribute fairly randomly into buckets.</p>
  
  <p>I originally started with <a href="https://stackoverflow.com/users/4997/gabr">Gabr</a>'s HashOf function from GpStringHash:</p>
  
  <pre><code>function HashOf(const key: string): cardinal;
  asm
    xor edx,edx     { result := 0 }
    and eax,eax     { test if 0 }
    jz @End         { skip if nil }
    mov ecx,[eax-4] { ecx := string length }
    jecxz @End      { skip if length = 0 }
  @loop:            { repeat }
    rol edx,2       { edx := (edx shl 2) or (edx shr 30)... }
    xor dl,[eax]    { ... xor Ord(key[eax]) }
    inc eax         { inc(eax) }
    loop @loop      { until ecx = 0 }
  @End:
    mov eax,edx     { result := eax }
  end; { HashOf }
  </code></pre>
  
  <p>But I found that this did not produce good numbers from Unicode strings. I noted that Gabr's routines have not been updated to Delphi 2009.</p>
  
  <p>Then I discovered HashNameMBCS in SysUtils of Delphi 2009 and translated it to this simple function (where "string" is a Delphi 2009 Unicode string):</p>
  
  <pre><code>function HashOf(const key: string): cardinal;
  var
    I: integer;
  begin
    Result := 0;
    for I := 1 to length(key) do
    begin
      Result := (Result shl 5) or (Result shr 27);
      Result := Result xor Cardinal(key[I]);
    end;
  end; { HashOf }
  </code></pre>
  
  <p>I thought this was pretty good until I looked at the CPU window and saw the assembler code it generated:</p>
  
  <pre><code>Process.pas.1649: Result := 0;
  0048DEA8 33DB             xor ebx,ebx
  Process.pas.1650: for I := 1 to length(key) do begin
  0048DEAA 8BC6             mov eax,esi
  0048DEAC E89734F7FF       call $00401348
  0048DEB1 85C0             test eax,eax
  0048DEB3 7E1C             jle $0048ded1
  0048DEB5 BA01000000       mov edx,$00000001
  Process.pas.1651: Result := (Result shl 5) or (Result shr 27);
  0048DEBA 8BCB             mov ecx,ebx
  0048DEBC C1E105           shl ecx,$05
  0048DEBF C1EB1B           shr ebx,$1b
  0048DEC2 0BCB             or ecx,ebx
  0048DEC4 8BD9             mov ebx,ecx
  Process.pas.1652: Result := Result xor Cardinal(key[I]);
  0048DEC6 0FB74C56FE       movzx ecx,[esi+edx*2-$02]
  0048DECB 33D9             xor ebx,ecx
  Process.pas.1653: end;
  0048DECD 42               inc edx
  Process.pas.1650: for I := 1 to length(key) do begin
  0048DECE 48               dec eax
  0048DECF 75E9             jnz $0048deba
  Process.pas.1654: end; { HashOf }
  0048DED1 8BC3             mov eax,ebx
  </code></pre>
  
  <p>This seems to contain quite a bit more assembler code than Gabr's code. </p>
  
  <p>Speed is of the essence. Is there anything I can do to improve either the pascal code I wrote or the assembler that my code generated?</p>
  
  <hr>
  
  <p>Followup.</p>
  
  <p>I finally went with the HashOf function based on SysUtils.HashNameMBCS. It seems to give a good hash distribution for Unicode strings, and appears to be quite fast. </p>
  
  <p>Yes, there is a lot of assembler code generated, but the Delphi code that generates it is so simple and uses only bit-shift operations, so it's hard to believe it wouldn't be fast.</p>