(* This structure has the "Jenkins.hash" function that calculates the
 * Jenkins One-at-a-Time hash. *)
structure Jenkins : sig

    (* Calculate the 32-bit Jenkins One-at-a-Time hash from a string. *)
    val hashString : string -> Word32.word

    (* Calculate the 32-bit Jenkins One-at-a-Time hash from a list of
     * Word32.word integers. *)
    val hashWord32List : Word32.word list -> Word32.word

end = struct

    (*
     * NOTE: The SML/NJ implementation uses 31-bit [sic] signed
     * integers.  The Jenkins One-at-a-Time hash is an unsigned 32-bit
     * value.  So to get the correct results, we have to use Word32.
     *)

    (* Bias used when calculating the hash value. *)
    val bias = valOf (Word32.fromString "0xaa87231f")

    (* The amount to shift needs to be specified as a Word. *)
    val word03 = Word.fromInt 03
    val word06 = Word.fromInt 06
    val word10 = Word.fromInt 10
    val word11 = Word.fromInt 11
    val word15 = Word.fromInt 15

    (* Return the 32-bit Jenkins One-at-a-Time hash for the list of
     * non-negative integers "lst". *)
    fun hashWord32List (lst : Word32.word list) = let
        fun hashRec lst acc =
            (* If the list is empty, calculate the final return value. *)
            if null lst then
                let
                    val acc0 = Word32.+    ( acc, (Word32.<< ( acc, word03)))
                    val acc1 = Word32.xorb (acc0, (Word32.>> (acc0, word11)))
                    val acc2 = Word32.+    (acc1, (Word32.<< (acc1, word15)))
                in
                    acc2
                end
            (* Adjust the hash value based on this element. *)
            else
                let
                    val acc0 = Word32.+    ( acc, (hd lst))
                    val acc1 = Word32.+    (acc0, (Word32.<< (acc0, word10)))
                    val acc2 = Word32.xorb (acc1, (Word32.>> (acc1, word06)))
                in
                    hashRec (tl lst) acc2
                end
    in
        hashRec lst bias
    end

    (* Return the 32-bit Jenkins One-at-a-Time hash for the string "s". *)
    fun hashString (s : string) =
        hashWord32List (map (Word32.fromInt o ord) (explode s))

end