hash.rkt

;; Hash a vector of numbers (all interpreted to be unsigned 64-bit
;; values) based on the first `len` entries in u64-vector. This uses
;; the same hash function as the backend's tuple_hash.
(define (tuple-hash u64-vector prefix-len)
  (define base 14695981039346656037)
  (define prime 1099511628211)
  (define resulting-hash
    (foldl
     (lambda (i cur-hash)
       (let* ([chunk (vector-ref u64-vector i)]
              [h0 (bitwise-xor cur-hash (bitwise-and chunk 255))]
              [h1 (* h0 prime)])
         ;; Fold accumulates (cons chunk hash)
         (cdr
          (foldl (lambda (j chunk-hash)
                   (let* ([next-chunk (arithmetic-shift (car chunk-hash) -8)]
                          [h0 (bitwise-xor (cdr chunk-hash) (bitwise-and next-chunk 255))]
                          [h1 (* h0 prime)])
                     (cons next-chunk h1)))
                 (cons chunk h1)
                 (range 8))))) base (range prefix-len)))
  (modulo resulting-hash (expt 2 64)))