[sbcl.git] / src / code / target-sxhash.lisp

;;;; hashing functions

;;;; This software is part of the SBCL system. See the README file for
;;;; more information.
;;;;
;;;; This software is derived from the CMU CL system, which was
;;;; written at Carnegie Mellon University and released into the
;;;; public domain. The software is in the public domain and is
;;;; provided with absolutely no warranty. See the COPYING and CREDITS
;;;; files for more information.

(in-package "SB!IMPL")

;;; the depthoid explored when calculating hash values
;;;
;;; "Depthoid" here is a sort of mixture of what Common Lisp ordinarily calls
;;; depth and what Common Lisp ordinarily calls length; it's incremented either
;;; when we descend into a compound object or when we step through elements of
;;; a compound object.
(eval-when (:compile-toplevel :load-toplevel :execute)
(defconstant +max-hash-depthoid+ 4)
) ; EVAL-WHEN
\f
;;;; mixing hash values

;;; a function for mixing hash values
;;;
;;; desiderata:
;;;   * Non-commutativity keeps us from hashing e.g. #(1 5) to the
;;;     same value as #(5 1), and ending up in real trouble in some
;;;     special cases like bit vectors the way that CMUCL SXHASH 18b
;;;     does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
;;;   * We'd like to scatter our hash values the entire possible range
;;;     of values instead of hashing small or common key values (like
;;;     2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
;;;     SXHASH function does, again helping to avoid pathologies like
;;;     hashing all bit vectors to 1.
;;;   * We'd like this to be simple and fast, too.
;;;
;;; FIXME: Should this be INLINE?
(declaim (ftype (function ((and fixnum unsigned-byte)
                           (and fixnum unsigned-byte))
                          (and fixnum unsigned-byte)) mix))
(defun mix (x y)
  ;; FIXME: We wouldn't need the nasty (SAFETY 0) here if the compiler
  ;; were smarter about optimizing ASH. (Without the THE FIXNUM below,
  ;; and the (SAFETY 0) declaration here to get the compiler to trust
  ;; it, the sbcl-0.5.0m cross-compiler running under Debian
  ;; cmucl-2.4.17 turns the ASH into a full call, requiring the
  ;; UNSIGNED-BYTE 32 argument to be coerced to a bignum, requiring
  ;; consing, and thus generally obliterating performance.)
  (declare (optimize (speed 3) (safety 0)))
  (declare (type (and fixnum unsigned-byte) x y))
  ;; the ideas here:
  ;;   * Bits diffuse in both directions (shifted left by up to 2 places
  ;;     in the calculation of XY, and shifted right by up to 5 places
  ;;     by the ASH).
  ;;   * The #'+ and #'LOGXOR operations don't commute with each other,
  ;;     so different bit patterns are mixed together as they shift
  ;;     past each other.
  ;;   * The arbitrary constant in the #'LOGXOR expression is intended
  ;;     to help break up any weird anomalies we might otherwise get
  ;;     when hashing highly regular patterns.
  ;; (These are vaguely like the ideas used in many cryptographic
  ;; algorithms, but we're not pushing them hard enough here for them
  ;; to be cryptographically strong.)
  (let* ((xy (+ (* x 3) y)))
    (declare (type (unsigned-byte 32) xy))
    (the (and fixnum unsigned-byte)
         (logand most-positive-fixnum
                 (logxor 441516657
                         xy
                         (the fixnum (ash xy -5)))))))
\f
;;;; hashing strings
;;;;
;;;; Note that this operation is used in compiler symbol table lookups, so we'd
;;;; like it to be fast.

#!-sb-fluid (declaim (inline %sxhash-substring))
(defun %sxhash-substring (string &optional (count (length string)))
  ;; FIXME: As in MIX above, we wouldn't need (SAFETY 0) here if the
  ;; cross-compiler were smarter about ASH, but we need it for sbcl-0.5.0m.
  (declare (optimize (speed 3) (safety 0)))
  (declare (type string string))
  (declare (type index count))
  (let ((result 408967240))
    (declare (type fixnum result))
    (dotimes (i count)
      (declare (type index i))
      (mixf result
            (the fixnum
                 (ash (char-code (aref string i)) 5))))
    result))
;;; test:
;;;   (let ((ht (make-hash-table :test 'equal)))
;;;     (do-all-symbols (symbol)
;;;       (let* ((string (symbol-name symbol))
;;;           (hash (%sxhash-substring string)))
;;;      (if (gethash hash ht)
;;;          (unless (string= (gethash hash ht) string)
;;;            (format t "collision: ~S ~S~%" string (gethash hash ht)))
;;;          (setf (gethash hash ht) string))))
;;;     (format t "final count=~D~%" (hash-table-count ht)))

(defun %sxhash-simple-string (x)
  (declare (optimize speed))
  (declare (type simple-string x))
  (%sxhash-substring x))

(defun %sxhash-simple-substring (x count)
  (declare (optimize speed))
  (declare (type simple-string x))
  (declare (type index count))
  (%sxhash-substring x count))
\f
;;;; the SXHASH function

(defun sxhash (x)
  (labels ((sxhash-number (x)
             (etypecase x
               (fixnum (sxhash x)) ; through DEFTRANSFORM
               (integer (sb!bignum:sxhash-bignum x))
               (single-float (sxhash x)) ; through DEFTRANSFORM
               (double-float (sxhash x)) ; through DEFTRANSFORM
               #!+long-float (long-float (error "stub: no LONG-FLOAT"))
               (ratio (let ((result 127810327))
                        (declare (type fixnum result))
                        (mixf result (sxhash-number (numerator x)))
                        (mixf result (sxhash-number (denominator x)))
                        result))
               (complex (let ((result 535698211))
                          (declare (type fixnum result))
                          (mixf result (sxhash-number (realpart x)))
                          (mixf result (sxhash-number (imagpart x)))
                          result))))
           (sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
             (declare (type index depthoid))
             (typecase x
               (list
                (if (plusp depthoid)
                    (mix (sxhash-recurse (car x) (1- depthoid))
                         (sxhash-recurse (cdr x) (1- depthoid)))
                    261835505))
               (instance
                (if (typep x 'structure-object)
                    (logxor 422371266
                            (sxhash ; through DEFTRANSFORM
                             (class-name (layout-class (%instance-layout x)))))
                    309518995))
               (symbol (sxhash x)) ; through DEFTRANSFORM
               (number (sxhash-number x))
               (array
                (typecase x
                  (simple-string (sxhash x)) ; through DEFTRANSFORM
                  (string (%sxhash-substring x))
                  (bit-vector (let ((result 410823708))
                                (declare (type fixnum result))
                                (dotimes (i (min depthoid (length x)))
                                  (mixf result (aref x i)))
                                result))
                  (t (logxor 191020317 (sxhash (array-rank x))))))
               (character
                (logxor 72185131
                        (sxhash (char-code x)))) ; through DEFTRANSFORM
               (t 42))))
    (sxhash-recurse x)))
\f
;;;; the PSXHASH function

;;;; FIXME: This code does a lot of unnecessary full calls. It could be made
;;;; more efficient (in both time and space) by rewriting it along the lines
;;;; of the SXHASH code above.

;;; like SXHASH, but for EQUALP hashing instead of EQUAL hashing
(defun psxhash (key &optional (depthoid +max-hash-depthoid+))
  (declare (optimize speed))
  (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
  ;; Note: You might think it would be cleaner to use the ordering given in the
  ;; table from Figure 5-13 in the EQUALP section of the ANSI specification
  ;; here. So did I, but that is a snare for the unwary! Nothing in the ANSI
  ;; spec says that HASH-TABLE can't be a STRUCTURE-OBJECT, and in fact our
  ;; HASH-TABLEs *are* STRUCTURE-OBJECTs, so we need to pick off the special
  ;; HASH-TABLE behavior before we fall through to the generic STRUCTURE-OBJECT
  ;; comparison behavior.
  (typecase key
    (array (array-psxhash key depthoid))
    (hash-table (hash-table-psxhash key))
    (structure-object (structure-object-psxhash key depthoid))
    (list (list-psxhash key depthoid))
    (number (number-psxhash key))
    (character (sxhash (char-upcase key)))
    (t (sxhash key))))

(defun array-psxhash (key depthoid)
  (declare (optimize speed))
  (declare (type array key))
  (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
  (typecase key
    ;; VECTORs have to be treated specially because ANSI specifies
    ;; that we must respect fill pointers.
    (vector
     (macrolet ((frob ()
                  '(let ((result 572539))
                     (declare (type fixnum result))
                     (mixf result (length key))
                     (dotimes (i (min depthoid (length key)))
                       (declare (type fixnum i))
                       (mixf result
                             (psxhash (aref key i)
                                      (- depthoid 1 i))))
                     result)))
       ;; CMU can compile SIMPLE-ARRAY operations so much more efficiently
       ;; than the general case that it's probably worth picking off the
       ;; common special cases.
       (typecase key
         (simple-string
          ;;(format t "~&SIMPLE-STRING special case~%")
          (frob))
         (simple-vector
          ;;(format t "~&SIMPLE-VECTOR special case~%")
          (frob))
         (t (frob)))))
    ;; Any other array can be hashed by working with its underlying
    ;; one-dimensional physical representation.
    (t
     (let ((result 60828))
       (declare (type fixnum result))
       (dotimes (i (min depthoid (array-rank key)))
         (mixf result (array-dimension key i)))
       (dotimes (i (min depthoid (array-total-size key)))
         (mixf result
               (psxhash (row-major-aref key i)
                        (- depthoid 1 i))))
       result))))

(defun structure-object-psxhash (key depthoid)
  (declare (optimize speed))
  (declare (type structure-object key))
  (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
  (let* ((layout (%instance-layout key)) ; i.e. slot #0
         (length (layout-length layout))
         (class (layout-class layout))
         (name (class-name class))
         (result (mix (sxhash name) (the fixnum 79867))))
    (declare (type fixnum result))
    (dotimes (i (min depthoid (1- length)))
      (declare (type fixnum i))
      (let ((j (1+ i))) ; skipping slot #0, which is for LAYOUT
        (declare (type fixnum j))
        (mixf result
              (psxhash (%instance-ref key j)
                       (1- depthoid)))))
    result))

(defun list-psxhash (key depthoid)
  (declare (optimize speed))
  (declare (type list key))
  (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
  (cond ((null key)
         (the fixnum 480929))
        ((zerop depthoid)
         (the fixnum 779578))
        (t
         (mix (psxhash (car key) (1- depthoid))
              (psxhash (cdr key) (1- depthoid))))))

(defun hash-table-psxhash (key)
  (declare (optimize speed))
  (declare (type hash-table key))
  (let ((result 103924836))
    (declare (type fixnum result))
    (mixf result (hash-table-count key))
    (mixf result (sxhash (hash-table-test key)))
    result))

(defun number-psxhash (key)
  (declare (optimize speed))
  (declare (type number key))
  (flet ((sxhash-double-float (val)
           (declare (type double-float val))
           ;; FIXME: Check to make sure that the DEFTRANSFORM kicks in and the
           ;; resulting code works without consing. (In Debian cmucl 2.4.17,
           ;; it didn't.)
           (sxhash val)))
    (etypecase key
      (integer (sxhash key))
      (float (macrolet ((frob (type)
                          (let ((lo (coerce most-negative-fixnum type))
                                (hi (coerce most-positive-fixnum type)))
                            `(cond (;; This clause allows FIXNUM-sized integer
                                    ;; values to be handled without consing.
                                    (<= ,lo key ,hi)
                                    (multiple-value-bind (q r)
                                        (floor (the (,type ,lo ,hi) key))
                                      (if (zerop (the ,type r))
                                          (sxhash q)
                                          (sxhash-double-float
                                           (coerce key 'double-float)))))
                                   (t
                                    (multiple-value-bind (q r) (floor key)
                                      (if (zerop (the ,type r))
                                          (sxhash q)
                                          (sxhash-double-float
                                           (coerce key 'double-float)))))))))
               (etypecase key
                 (single-float (frob single-float))
                 (double-float (frob double-float))
                 (short-float (frob short-float))
                 (long-float (error "LONG-FLOAT not currently supported")))))
      (rational (if (and (<= most-negative-double-float
                             key
                             most-positive-double-float)
                         (= (coerce key 'double-float) key))
                    (sxhash-double-float (coerce key 'double-float))
                    (sxhash key)))
      (complex (if (zerop (imagpart key))
                   (number-psxhash (realpart key))
                   (let ((result 330231))
                     (declare (type fixnum result))
                     (mixf result (number-psxhash (realpart key)))
                     (mixf result (number-psxhash (imagpart key)))
                     result))))))

;;; SXHASH and PSXHASH should distribute hash values well over the
;;; space of possible values, so that collisions between the hash values
;;; of unequal objects should be very uncommon.
;;;
;;; FIXME: These tests should be enabled once the rest of the system is
;;; stable. (For now, I don't want to mess with things like making sure
;;; that bignums are hashed uniquely.)
;;;#!+sb-test
#+nil
(let* ((test-cases `((0 . 1)
                     (0 . 1)
                     (1 . 0)
                     ((1 . 0) (0 . 0))
                     ((0 . 1) (0 . 0))
                     ((0 . 0) (1 . 0))
                     ((0 . 0) (0 . 1))
                     #((1 . 0) (0 . 0))
                     #((0 . 1) (0 . 0))
                     #((0 . 0) (1 . 0))
                     #((0 . 0) (0 . 1))
                     #((1 . 0) (0 . 0))
                     #((0 1) (0 0))
                     #((0 0) (1 0))
                     #((0 0) (0 1))
                     #(#(1 0) (0 0))
                     #(#(0 1) (0 0))
                     #(#(0 0) (1 0))
                     #(#(0 0) (0 1))
                     #(#*00 #*10)
                     #(#(0 0) (0 1.0d0))
                     #(#(-0.0d0 0) (1.0 0))
                     ;; KLUDGE: Some multi-dimensional array test cases would
                     ;; be good here too, but currently SBCL isn't smart enough
                     ;; to dump them as literals, and I'm too lazy to make
                     ;; code to create them at run time. -- WHN 20000111
                     44 44.0 44.0d0
                     44 44.0 44.0d0
                     -44 -44.0 -44.0d0
                     0 0.0 0.0d0
                     -0 -0.0 -0.0d0
                     -121 -121.0 -121.0d0
                     3/4 0.75 0.75d0
                     -3/4 -0.75 -0.75d0
                     44.1 44.1d0
                     45 45.0 45.0d0
                     ,(expt 2 33) ,(expt 2.0 33) ,(expt 2.0d0 33)
                     ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
                     ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
                     #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
                     #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
                     ,(make-hash-table)
                     ,(make-hash-table :test 'equal)
                     "abc" "ABC" "aBc" 'abc #(#\a #\b #\c) #(a b c) #("A" b c)
                     "abcc"
                     "" #* #() () (()) #(()) (#())
                     "" #* #() () (()) #(()) (#())
                     #\x #\X #\*
                     #\x #\X #\*)))
  (dolist (i test-cases)
    (unless (typep (sxhash i) '(and fixnum unsigned-byte))
      (error "bad SXHASH behavior for ~S" i))
    (unless (typep (psxhash i) '(and fixnum unsigned-byte))
      (error "bad PSXHASH behavior for ~S" i))
    (dolist (j test-cases)
      (flet ((t->boolean (x) (if x t nil)))
        ;; Note: It's possible that a change to the hashing algorithm could
        ;; leave it correct but still cause this test to bomb by causing an
        ;; unlucky random collision. That's not very likely (since there are
        ;; (EXPT 2 29) possible hash values and only on the order of 100 test
        ;; cases, but it's probably worth checking if you are getting a
        ;; mystifying error from this test.
        (unless (eq (t->boolean (equal i j))
                    (t->boolean (= (sxhash i) (sxhash j))))
          (error "bad SXHASH behavior for ~S ~S" i j))
        (unless (eq (t->boolean (equalp i j))
                    (t->boolean (= (psxhash i) (psxhash j))))
          (error "bad PSXHASH behavior for ~S ~S" i j))))))

;;; FIXME: Test that the the hash functions can deal with common cases without
;;; consing.
;(defun consless-test ()
;  (dotimes (j 100000)
;    (dolist (i '("yo" #(1 2 3) #2A((1 2) (1 2)) (1 2 (3)) 1 1.0 1.0d0))
;      (psxhash i))))