A Clojure port of https://github.com/jenssegers/optimus

integer_hashing.clj

"Encode and decode integers (such as database identifiers) using Knuth's multiplicative hashing
algorithm. Based on https://github.com/jenssegers/optimus."

;; Permission is hereby granted, free of charge, to any person obtaining a copy
;; of this software and associated documentation files (the "Software"), to deal
;; in the Software without restriction, including without limitation the rights
;; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
;; copies of the Software, and to permit persons to whom the Software is
;; furnished to do so, subject to the following conditions:
;; 
;; The above copyright notice and this permission notice shall be included in all
;; copies or substantial portions of the Software.
;; 
;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
;; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
;; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
;; SOFTWARE.

(import '(java.security SecureRandom))

(set! *warn-on-reflection* true)

(comment (set! *unchecked-math* :warn-on-boxed) ,,,)

(def ^:private ^SecureRandom secure-random (SecureRandom.))

(def ^:private ^:const modulus (-> Integer/MAX_VALUE inc biginteger))

(defn ^:private make-spec
  "Given a prime number greater than 2 (e.g. from https://primes.utm.edu/lists/small/millions/),
  return a spec map for encoding and decoding integers using Knuth's multiplicative hashing
  algorithm.

  Keys:

    - :prime -- the prime number given as argument (long)
    - :mod-inverse -- the modular multiplicative inverse of :prime (long)
    - :rand-n -- a cryptographically secure random number (long)"
  [^long prime]
  (assert (< 0 prime Integer/MAX_VALUE) (format "Prime number must be a positive integer less than %d." Integer/MAX_VALUE))
  (assert (.isProbablePrime (biginteger prime) 100) (format "%d is (probably) not a prime." prime))
  (assert (= 1 (.gcd (biginteger prime) modulus)) (format "Prime number %d and modulus %d are not co-prime." prime modulus))
  {:prime prime
   :mod-inverse (long (.modInverse (biginteger prime) modulus))
   :rand-n (-> secure-random .nextInt abs)})

(comment
  (make-spec -2)
  (make-spec 1)
  (make-spec 2)
  (make-spec Integer/MAX_VALUE)
  (make-spec (dec Integer/MAX_VALUE))
  (make-spec 44560482149)
  (make-spec 472882027)
  ,,,)

(defn encode
  "Given a spec map and a natural integer n to encode, encode n and return it."
  [{:keys [^long prime ^long rand-n]} ^long n]
  (bit-xor (bit-and (unchecked-multiply n prime) Integer/MAX_VALUE) rand-n))

(comment
  (encode (make-spec 5) 1)
  ,,,)

(defn decode
  "Given the spec map used to encode natural integer n using encode, decode n and
  return it."
  [{:keys [^long mod-inverse ^long rand-n]} ^long n]
  (bit-and (unchecked-multiply (bit-xor n rand-n) mod-inverse) Integer/MAX_VALUE))

(comment
  (def spec (make-spec 472882027))
  (encode spec 1)
  (encode spec (inc Integer/MAX_VALUE))
  (->> 1 (encode spec) (decode spec))

  (let [spec {:prime 1580030173 :mod-inverse 59260789 :rand-n 1163945558}]
    (->> 15 (encode spec) (decode spec)))
  ,,,)

(comment
  (require '[clojure.test.check :as test.check])
  (require '[clojure.test.check.properties :as prop])
  (require '[clojure.test.check.generators :as gen])

  (let [spec (make-spec 472882027)]
    (test.check/quick-check 1000000
      (prop/for-all [n gen/nat]
        (= n (->> n (encode spec) (decode spec))))))

  (require '[criterium.core :as criterium])

  (let [spec (make-spec 472882027)]
    (criterium/quick-bench
      (mapv #(->> % (encode spec) (decode spec)) (range 100)))))