Recent

« previous next »
Pages: [1]

Author Topic: Fast hash functions  (Read 1818 times)

julkas

  • Guest
Fast hash functions
« on: June 13, 2020, 08:57:22 am »
Code: Pascal  [Select][+][-]
  1. unit hash;
  2. {
  3.   Fast hash functions
  4.   http://www.sanmayce.com/Fastest_Hash/
  5. }
  6.  
  7. {$ifdef FPC}
  8. {$mode delphi}
  9. {$endif}
  10.  
  11. {$inline on}
  12. {$pointermath on}
  13.  
  14. interface
  15.  
  16. uses
  17.   Classes, SysUtils;
  18.  
  19. function FNV1A_Hash_Jesteress(key: PChar; keyLen: integer): DWord; inline;
  20. function FNV1A_Hash_Meiyan(key: PChar; keyLen: integer): DWord; inline;
  21. function FNV1A_Hash_Mantis(key: PChar; keyLen: integer): DWord; inline;
  22.  
  23. implementation
  24.  
  25. {$Q-}{$R-}
  26.  
  27. function FNV1A_Hash_Jesteress(key: PChar; keyLen: integer): DWord;
  28. var
  29.   hash32: DWord;
  30. begin
  31.   hash32 := 2166136261;
  32.  
  33.   while keyLen >= SizeOf(QWord) do
  34.   begin
  35.     hash32 := (hash32 xor (
  36.       (((PDWord(key))^ shl 5) or ((PDWord(key))^ shr 27)) xor
  37.       (PDWord(key + SizeOf(DWord)))^
  38.       )) * 709607;
  39.     Dec(keyLen, SizeOf(QWord));
  40.     Inc(key, SizeOf(QWord));
  41.   end;
  42.  
  43.   if (keyLen and SizeOf(DWord)) <> 0 then
  44.   begin
  45.     hash32 := (hash32 xor (PDWord(key))^) * 709607;
  46.     Inc(key, SizeOf(DWord));
  47.   end;
  48.  
  49.   if (keyLen and SizeOf(Word)) <> 0 then
  50.   begin
  51.     hash32 := (hash32 xor (PWord(key))^) * 709607;
  52.     Inc(key, SizeOf(Word));
  53.   end;
  54.  
  55.   if (keyLen and SizeOf(Byte)) <> 0 then
  56.     hash32 := (hash32 xor (PByte(key))^) * 709607;
  57.  
  58.   Result := hash32 xor (hash32 shr 16);
  59.  
  60. end;
  61.  
  62. function FNV1A_Hash_Meiyan(key: PChar; keyLen: integer): DWord;
  63. var
  64.   hash32: DWord;
  65. begin
  66.   hash32 := 2166136261;
  67.  
  68.   while keyLen >= SizeOf(QWord) do
  69.   begin
  70.     hash32 := (hash32 xor (
  71.       (((PDWord(key))^ shl 5) or ((PDWord(key))^ shr 27)) xor
  72.       (PDWord(key + SizeOf(DWord)))^
  73.       )) * 709607;
  74.     Dec(keyLen, SizeOf(QWord));
  75.     Inc(key, SizeOf(QWord));
  76.   end;
  77.  
  78.   if (keyLen and SizeOf(DWord)) <> 0 then
  79.   begin
  80.     hash32 := (hash32 xor (PWord(key))^) * 709607;
  81.     Inc(key, SizeOf(Word));
  82.     hash32 := (hash32 xor (PWord(key))^) * 709607;
  83.     Inc(key, SizeOf(Word));
  84.   end;
  85.  
  86.   if (keyLen and SizeOf(Word)) <> 0 then
  87.   begin
  88.     hash32 := (hash32 xor (PWord(key))^) * 709607;
  89.     Inc(key, SizeOf(Word));
  90.   end;
  91.  
  92.   if (keyLen and SizeOf(Byte)) <> 0 then
  93.     hash32 := (hash32 xor (PByte(key))^) * 709607;
  94.  
  95.   Result := hash32 xor (hash32 shr 16);
  96.  
  97. end;
  98.  
  99. function FNV1A_Hash_Mantis(key: PChar; keyLen: integer): DWord;
  100. var
  101.   hash32: DWord;
  102.   p: PChar;
  103. begin
  104.   hash32 := 2166136261;
  105.   p := key;
  106.  
  107.   if (keyLen and SizeOf(DWord)) <> 0 then
  108.   begin
  109.     hash32 := (hash32 xor (PWord(p))^) * 709607;
  110.     Inc(p, SizeOf(Word));
  111.     hash32 := (hash32 xor (PWord(p))^) * 709607;
  112.     Inc(p, SizeOf(Word));
  113.   end;
  114.  
  115.   if (keyLen and SizeOf(Word)) <> 0 then
  116.   begin
  117.     hash32 := (hash32 xor (PWord(p))^) * 709607;
  118.     Inc(p, SizeOf(Word));
  119.   end;
  120.  
  121.   if (keyLen and SizeOf(Byte)) <> 0 then
  122.   begin
  123.     hash32 := (hash32 xor (PByte(p))^) * 709607;
  124.     Inc(p, SizeOf(Byte));
  125.   end;
  126.  
  127.   Dec(keyLen, p - key);
  128.  
  129.   while keyLen > SizeOf(QWord) do
  130.   begin
  131.     hash32 := (hash32 xor (
  132.       (((PDWord(p))^ shl 5) or ((PDWord(p))^ shr 27)) xor
  133.       (PDWord(p + SizeOf(DWord)))^
  134.       )) * 709607;
  135.     Dec(keyLen, SizeOf(QWord));
  136.     Inc(p, SizeOf(QWord));
  137.   end;
  138.  
  139.   if keyLen <> 0 then
  140.   begin
  141.     hash32 := (hash32 xor (PWord(p + 0 * SizeOf(Word)))^) * 709607;
  142.     hash32 := (hash32 xor (PWord(p + 1 * SizeOf(Word)))^) * 709607;
  143.     hash32 := (hash32 xor (PWord(p + 2 * SizeOf(Word)))^) * 709607;
  144.     hash32 := (hash32 xor (PWord(p + 3 * SizeOf(Word)))^) * 709607;
  145.   end;
  146.  
  147.   Result := hash32 xor (hash32 shr 16);
  148.  
  149. end;
  150.  
  151. {$Q+}{$R+}
  152.  
  153. initialization
  154.  
  155. finalization
  156.  
  157. end.
  158.  
Logged

Thaddy

  • Hero Member
  • *****
  • Posts: 18684
  • Jungle wars. And failing health it seems.
Re: Fast hash functions
« Reply #1 on: June 13, 2020, 09:04:36 am »
Code: Pascal  [Select][+][-]
  1. function ElfHash(const Value: string): Integer;
  2. var
  3.   i, x: Integer;
  4. begin
  5.   Result := 0;
  6.   for i := 1 to Length(Value) do
  7.   begin
  8.     Result := (Result shl 4) + Ord(Value[i]);
  9.     x := Result and $F0000000;
  10.     if (x <> 0) then
  11.       Result := Result xor (x shr 24);
  12.     Result := Result and (not x);
  13.   end;
  14. end;
Is really fast.
I also have a 32 bit intel version that takes only 7 cycles.
Code: Pascal  [Select][+][-]
  1. //Function listed below is a little faster on my P4
  2. //(it takes 7 tick/char against 7.5 tick/char).
  3. function ElfHash_Sha(const s: string): integer;
  4. asm
  5. mov edx, eax
  6. xor eax, eax
  7. test edx, edx
  8. jz @Ret
  9. sub eax, [edx-4]
  10. jz @Ret
  11. mov ecx, eax
  12. sub edx, eax
  13. xor eax, eax
  14. push ebx
  15. @Loop:
  16. movzx ebx, [edx+ecx]
  17. add ebx, eax
  18. lea eax, [ebx+ebx]
  19. shr ebx, 20
  20. lea eax, [8*eax]
  21. and ebx, $0F00
  22. xor eax, ebx
  23. add ecx, 1
  24. jnz @Loop
  25. shr eax, 4
  26. pop ebx
  27. @Ret:
  28. end;
Written on my request by Aleksandr Sharahov. (Again many thanks!)
See here: http://www.delphigroups.info/2/9/1024232.html

Theory is here: https://en.wikipedia.org/wiki/PJW_hash_function

I guess these are faster, but I do not have the time to measure it..
« Last Edit: June 13, 2020, 09:24:39 am by Thaddy »
Logged
Due to censorship, I changed this to "Nelly the Elephant". Keeps the message clear.

Tz

  • Jr. Member
  • **
  • Posts: 54
  • Tz with FPC Pen Cil
Re: Fast hash functions
« Reply #2 on: June 15, 2020, 12:42:32 pm »
according to Reini Urban
https://github.com/rurban/smhasher

by Wang Yi
https://github.com/wangyi-fudan/wyhash

I tried version 2, not tested yet.


Code: Pascal  [Select][+][-]
  1. {
  2. Author: Wang Yi <godspeed_china@yeah.net>
  3. https://github.com/wangyi-fudan/wyhash
  4.  
  5. ref
  6. https://github.com/rurban/smhasher
  7. https://docs.rs/wyhash/0.3.0/wyhash/
  8. https://www.partow.net/programming/hashfunctions/
  9.  
  10. }
  11. { version 2 64 bit only }
  12. {$mode delphi}
  13. unit wyhash_v2;
  14.  
  15. interface
  16.  
  17. function wyhash64(AString :String) :UInt64; inline;
  18.  
  19. implementation
  20.  
  21. const
  22.   _wyp0 = UInt64($a0761d6478bd642f);
  23.   _wyp1 = UInt64($e7037ed1a0b428db);
  24.   _wyp2 = UInt64($8ebc6af09c88c6e3);
  25.   _wyp3 = UInt64($589965cc75374cc3);
  26.   _wyp4 = UInt64($1d8e4e27c47d124f);
  27.  
  28. var
  29.   wyseed :UInt64;
  30.  
  31. (*
  32.   // dangling c boolean true = 1 or not zero
  33.   #include <stdint.h>
  34.   #include <stdio.h>
  35.   int main()
  36.   {
  37.      uint64_t rl = 10, t = 0, c = t < rl;
  38.      printf("%lu", c); // result 1 using gcc
  39.      return 0;
  40.   }
  41. *)
  42.  
  43.  
  44. function _wymum(A, B :UInt64) :UInt64; inline;
  45.   var ha, hb, la, lb, hi, lo  :UInt64;
  46.       rh, rm0, rm1, rl, t, c  :UInt64;
  47.   begin
  48.     ha  := A shr 32;
  49.     hb  := B shr 32;
  50.     la  := UInt32(A); // A and $FFFFFFFF;
  51.     lb  := UInt32(B); // B and $FFFFFFFF;
  52.  
  53.     rh  := ha * hb;
  54.     rm0 := ha * lb;
  55.     rm1 := hb * la;
  56.     rl  := la * lb;
  57.     t   := rl + (rm0 shl 32);
  58.     c   := UInt64(t < rl);      // c ? true = 1
  59.     lo  := t  + (rm1 shl 32);
  60.     c   := c  + UInt64(lo < t); // c ? true = 1
  61.     hi  := rh + (rm0 shr 32) + (rm1 shr 32) + c;
  62.     result := hi xor lo;
  63.   end;
  64.  
  65. function _wymix0(A, B, seed :UInt64) :UInt64; inline;
  66.   begin
  67.     result := _wymum(A xor seed xor _wyp0, B xor seed xor _wyp1);
  68.   end;
  69.  
  70. function _wymix1(A, B, seed :UInt64) :UInt64; inline;
  71.   begin
  72.     result := _wymum(A xor seed xor _wyp2, B xor seed xor _wyp3);
  73.   end;
  74.  
  75. // macro ?? or better endian
  76. function _wyr08(const p :PUInt8) :UInt64; inline;
  77.   begin
  78.     Move(p, result, 1);
  79.   end;
  80.  
  81. function _wyr16(const p :PUInt8) :UInt64; inline;
  82.   begin
  83.     Move(p, result, 2);
  84.   end;
  85.  
  86. function _wyr32(const p :PUInt8) :UInt64; inline;
  87.   begin
  88.     Move(p, result, 4);
  89.   end;
  90.  
  91. function _wyr64(const p :PUInt8) :UInt64; inline;
  92.   begin
  93.     Move(p, result, 8);
  94.   end;
  95.  
  96. function __wyr64(const p :PUInt8) :UInt64; inline;
  97.   begin
  98.     result := (_wyr32(p) shl 32) or _wyr32(p + 4);
  99.   end;
  100.  
  101. // to avoid attacks, seed should be initialized as a secret
  102. function wyhash(const key :Pointer; len, seed :UInt64) :UInt64; inline;
  103.   var i, len1 :UInt64; p :PUInt8;
  104.   begin
  105.  
  106.     p    := key;
  107.     i    :=   0;
  108.     len1 := len;
  109.  
  110.     while (i + 32 <= len) do
  111.     begin
  112.       seed :=  _wymix0(_wyr64(p     ), _wyr64(p +  8), seed)
  113.            xor _wymix1(_wyr64(p + 16), _wyr64(p + 24), seed);
  114.  
  115.       i := i + 32;
  116.       p := p + 32;
  117.     end;
  118.  
  119.     case (len and 31) of
  120.        0: len1 := _wymix0(      len1,                                                   0, seed);
  121.        1: seed := _wymix0( _wyr08(p),                                                   0, seed);
  122.        2: seed := _wymix0( _wyr16(p),                                                   0, seed);
  123.        3: seed := _wymix0((_wyr16(p) shl  8) or  _wyr08(p + 2),                         0, seed);
  124.        4: seed := _wymix0( _wyr32(p),                                                   0, seed);
  125.        5: seed := _wymix0((_wyr32(p) shl  8) or  _wyr08(p + 4),                         0, seed);
  126.        6: seed := _wymix0((_wyr32(p) shl 16) or  _wyr16(p + 4),                         0, seed);
  127.        7: seed := _wymix0((_wyr32(p) shl 24) or (_wyr16(p + 4) shl 8) or _wyr08(p + 6), 0, seed);
  128.        8: seed := _wymix0(__wyr64(p),                                                   0, seed);
  129.  
  130.        9: seed := _wymix0(__wyr64(p),  _wyr08(p + 8),                                                                                                   seed);
  131.       10: seed := _wymix0(__wyr64(p),  _wyr16(p + 8),                                                                                                   seed);
  132.       11: seed := _wymix0(__wyr64(p), (_wyr16(p + 8) shl  8) or  _wyr08(p + 8 + 2),                                                                     seed);
  133.       12: seed := _wymix0(__wyr64(p),  _wyr32(p + 8),                                                                                                   seed);
  134.       13: seed := _wymix0(__wyr64(p), (_wyr32(p + 8) shl  8) or  _wyr08(p + 8 + 4),                                                                     seed);
  135.       14: seed := _wymix0(__wyr64(p), (_wyr32(p + 8) shl 16) or  _wyr16(p + 8 + 4),                                                                     seed);
  136.       15: seed := _wymix0(__wyr64(p), (_wyr32(p + 8) shl 24) or (_wyr16(p + 8 + 4) shl 8) or _wyr08(p + 8 + 6),                                         seed);
  137.       16: seed := _wymix0(__wyr64(p), __wyr64(p + 8),                                                                                                   seed);
  138.  
  139.       17: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1( _wyr08(p + 16),                                                             0, seed);
  140.       18: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1( _wyr16(p + 16),                                                             0, seed);
  141.       19: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1((_wyr16(p + 16) shl  8) or  _wyr08(p + 16 + 2),                              0, seed);
  142.       20: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1( _wyr32(p + 16),                                                             0, seed);
  143.       21: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1((_wyr32(p + 16) shl  8) or  _wyr08(p + 16 + 4),                              0, seed);
  144.       22: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1((_wyr32(p + 16) shl 16) or  _wyr16(p + 16 + 4),                              0, seed);
  145.       23: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1((_wyr32(p + 16) shl 24) or (_wyr16(p + 16 + 4) shl 8) or _wyr08(p + 16 + 6), 0, seed);
  146.       24: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16),                                                             0, seed);
  147.  
  148.       25: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16),  _wyr08(p + 24),                                               seed);
  149.       26: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16),  _wyr16(p + 24),                                               seed);
  150.       27: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16), (_wyr16(p + 24) shl  8) or _wyr08(p + 24 + 2),                 seed);
  151.       28: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16),  _wyr32(p + 24),                                               seed);
  152.       29: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16), (_wyr32(p + 24) shl  8) or _wyr08(p + 24 + 4),                 seed);
  153.       30: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16), (_wyr32(p + 24) shl 16) or _wyr16(p + 24 + 4),                 seed);
  154.  
  155.       31: seed := _wymix0(__wyr64(p), __wyr64(p + 8), seed) xor _wymix1(__wyr64(p + 16), (_wyr32(p + 24) shl 24) or (_wyr16(p + 24 + 4) shl 8) or _wyr08(p + 24 + 6), seed);
  156.     end;
  157.  
  158.     result := _wymum(seed xor len1, _wyp4);
  159.   end;
  160.  
  161. function wyrand(seed :UInt64) :UInt64; inline;
  162.   begin
  163.     seed := seed + _wyp0;
  164.     result := _wymum(seed xor _wyp1, seed);
  165.   end;
  166.  
  167. function wyhash64(AString :String) :UInt64; inline;
  168.   begin
  169.     result := wyhash(@AString[1], Length(AString), wyseed);
  170.   end;
  171.  
  172. initialization
  173.   wyseed := wyrand(33);
  174.  
  175. end.
  176.  
Logged

julkas

  • Guest
Re: Fast hash functions
« Reply #3 on: June 15, 2020, 02:20:35 pm »
Logged
Pages: [1]
« previous next »
 

TinyPortal © 2005-2018