[m-rev.] for review: reimpelement the hash_pred for ints in Mercury

[Julien Fischer]

For review by anyone.


---------------------------

Reimplement the hash_pred for ints in Mercury.

library/hash_pred.m:
     As above: implementing this in Mercury means that we now have a working
     implementation for the non-C backends as well.   (I have kept Ralph's
     original C implementation about for now.)  Also use this implementation
     for the uint type.

     Provide a link to the archived version of Thomas Wang's website.

Julien.

diff --git a/library/hash_table.m b/library/hash_table.m
index 204082a99..4e97f37ec 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -266,6 +266,7 @@
      % Default hash_preds for ints and strings and everything (buwahahaha!)
      %
  :- pred int_hash(int::in, int::out) is det.
+:- pred uint_hash(uint::in, int::out) is det.
  :- pred float_hash(float::in, int::out) is det.
  :- pred char_hash(char::in, int::out) is det.
  :- pred string_hash(string::in, int::out) is det.
@@ -274,6 +275,14 @@
  %---------------------------------------------------------------------------%
  %---------------------------------------------------------------------------%

+:- implementation.
+:- interface.
+
+% For the purposes of comparison I've left Ralph's foreign_proc version
+% of the integer hash functions intact (for now).
+
+:- pred cint_hash(int::in, int::out) is det.
+
  :- implementation.

  :- import_module bool.
@@ -284,8 +293,11 @@
  :- import_module list.
  :- import_module pair.
  :- import_module string.
+:- import_module uint.
  :- import_module univ.

+
+
  %---------------------------------------------------------------------------%

  :- interface.
@@ -789,15 +801,24 @@ fold3_p(P, List, !A, !B, !C) :-

  %---------------------------------------------------------------------------%

-    % From http://www.concentric.net/~Ttwang/tech/inthash.htm
-    %   public int hash32shift(int key)
-    %   public long hash64shift(long key)
-    %
+% The integer hash functions below are originally from:
+%
+%  http://www.concentric.net/~Ttwang/tech/inthash.htm
+%
+% The above link is now dead; the last version can be found at:
+%
+%  https://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm
+%
+% The algorithms from that page that we use are:
+%
+%   public int hash32shiftmult(int key)
+%   public long hash64shift(long key)
+
  :- pragma foreign_proc("C",
-    int_hash(N::in, H::out),
-    [will_not_call_mercury, promise_pure, thread_safe, tabled_for_io],
+    cint_hash(N::in, H::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
  "
-    const int c2 = 0x27d4eb2d; /* a prime or an odd constant */
+    const int c2 = 0x27d4eb2d; // a prime or an odd constant
      MR_Unsigned key;

      key = N;
@@ -809,11 +830,11 @@ fold3_p(P, List, !A, !B, !C) :-
          key = key * c2;
          key = key ^ (key >> 15);
      } else {
-        key = (~key) + (key << 21); /* key = (key << 21) - key - 1; */
+        key = (~key) + (key << 21); // key = (key << 21) - key - 1;
          key = key ^ (key >> 24);
-        key = (key + (key << 3)) + (key << 8); /* key * 265 */
+        key = (key + (key << 3)) + (key << 8);  //  key * 265
          key = key ^ (key >> 14);
-        key = (key + (key << 2)) + (key << 4); /* key * 21 */
+        key = (key + (key << 2)) + (key << 4);  // key * 21
          key = key ^ (key >> 28);
          key = key + (key << 31);
      }
@@ -821,9 +842,28 @@ fold3_p(P, List, !A, !B, !C) :-
      H = key;
  ").

-int_hash(N, N).
-    % For use on non-C backends.
-    % There are almost certainly better ones out there...
+int_hash(Key, Hash) :-
+    UKey = uint.cast_from_int(Key),
+    uint_hash(UKey, Hash).
+
+uint_hash(!.Key, Hash) :-
+    C2 = 0x_27d4_eb2d_u,
+    ( if bits_per_uint = 4 then
+        !:Key = (!.Key `xor` 61_u) `xor` (!.Key >> 16),
+        !:Key = !.Key + (!.Key << 3),
+        !:Key = !.Key `xor` (!.Key >> 4),
+        !:Key = !.Key * C2,
+        !:Key = !.Key `xor` (!.Key >> 15)
+    else
+        !:Key = (\ !.Key) + (!.Key << 21),
+        !:Key = !.Key `xor` (!.Key >> 24),
+        !:Key = (!.Key + (!.Key << 3)) + (!.Key << 8),
+        !:Key = !.Key `xor` (!.Key >> 14),
+        !:Key = (!.Key + (!.Key << 2)) + (!.Key << 4),
+        !:Key = !.Key `xor` (!.Key >> 28),
+        !:Key = !.Key + (!.Key << 31)
+    ),
+    Hash = uint.cast_to_int(!.Key).

  float_hash(F, float.hash(F)).
      % There are almost certainly better ones out there...