quasiTech

experiments

Some Hash Functions

Here are some common hash functions in C I found online here and here. I have done the menial task of translating them to Common Lisp.

1
2
3
4
5
6
7
8
9
10
11
12
13

;;; Hash Function by Dan Bernstein
(defun hash-DJB (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381))
    (loop for x across str
     do (setf hash (ldb (byte 32 0)
                        (+ (ldb (byte 32 0)
                                (+ (ldb (byte 32 0)
                                        (ash hash 5)) hash))
                           (char-int x))))
     finally (return hash))))

1
2
3
4
5
6
7
8
9
10

;;; Hash Function by Dan Bernstein
(defun hash-DJB2 (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (logxor (char-int x) (* hash 33))))
       finally (return hash))))

1
2
3
4
5
6
7
8
9
10
11
12
13

;;; Hash Function from GAWK, a variation from the verwion from SDBM
(defun hash-SDBM (str)
  (declare (type simple-string str)
           (type (unsigned-byte 32) hash)
           (optimize speed (debug 0)))
  (let ((hash 0))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (+ (char-int x)
                             (ldb (byte 32 0) (ash hash 6))
                             (ldb (byte 32 0) (ash hash 16))
                             (- hash))))
       finally (return hash))))

1
2
3
4
5
6
7
8
9
10
11
12

;;; An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3
(defun hash-DEK (str)
  (declare (type simple-string str)
     (type (unsigned-byte 32) hash)
     (optimize speed (debug 0)))
  (let ((hash (length str)))
    (loop for x across str
       do (setf hash (ldb (byte 32 0)
                          (logxor (char-int x)
                                  (logxor (ldb (byte 32 0) (ash hash 5))
                                          (ash hash -27)))))
       finally (return hash))))

Comments