Friday, March 20, 2009

Some common Hash Functions in Common Lisp

Here are some common hash functions in C I found online here and here. I have done the menial task of translating them to CL. I have a lot of excuses for such a lame post : blah blah blah. I made a big booper by forgetting that these functions return unsigned-byte 32 ints. After some simple pointing to this by good denizens of #lisp I changed it - that too after reading some literature. duh. If you have any suggestions how daft I am, lemme know.

;;; 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))))

;;; Hash Function by Dan Bernstein (newer)
(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))))

;;; 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))))

;;; 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))))

4 comments:

Chaitanya Gupta said...

Hehe, so you did some CL again ;)

quasi said...

I am just starting dude, just starting back... beware the dragon :)

Vivek Rao said...

(declare (type 2 geeks near orgasmic due to nonsense coding chatter) haha)

Vivek Rao said...

and "beware the dragon"??? really dude.... (shaking my head sadly here)
:-D