knothash.lisp

(load "~/quicklisp/setup.lisp")
(ql:quickload "bit-smasher" :silent t)
(defun reverseip (l len)
  (if (not (= len 0))
      (loop
         for i from (1- len) downto 0
         for j upto (1- len)
         do (if (or (< i j)
                    (= i j))
                (return)
                (rotatef (nth j l) (nth i l))))))

(defun hash (str)
  (let* ((lens (append (map 'list #'char-code str)
                      '(17 31 73 47 23)))
         (list (loop for i upto 255 collect i))
         (lh list)
         (skp 0)
         (denseh '()))

    (rplacd (last list) list)
    (dotimes (i 64)
      (dolist (len lens)
        (reverseip list len)
        (setf list (nthcdr (+ len skp) list))
        (incf skp)))

    (dotimes (i 16)
      (setf denseh
            (nconc denseh
                   (list
                    (reduce #'bit-xor
                            (mapcar #'bit-smasher:bits<-
                                    (subseq lh (* 16 i) (+ (* 16 i) 16))))))))
    (apply #'concatenate '(vector bit) denseh)))