helpme.lisp

(defun bit-prefix (byte-vector length)
  (loop
     for i from length above 0 by 8
     for idx from 0
     when (> i 8)
     sum (ash (aref byte-vector idx) (- i 8))
     else sum (ldb (byte i (- 8 i)) (aref byte-vector idx))))

(defun prefix-buckets (prefix-length)
  (declare (type (mod 32) prefix-length))
  (let ((hashers (make-array (expt 2 prefix-length))))
    (map-into hashers (lambda () (ironclad:make-digest +hash+)))
    (iterate:iterate (iterate:for (hash) in-sqlite-query
                                  "SELECT hash FROM chunks ORDER BY hash"
                                  on-database
                                  *connection*)
                     (ironclad:update-digest (aref hashers (bit-prefix hash prefix-length))
                                             hash))
    (let ((result (make-array (expt 2 prefix-length))))
      (map-into result #'ironclad:produce-digest hashers))))


(defconstant +hash-tree-bits-per-level+ 4)

(defun hash-tree (depth)
  (declare
   ;;(optimize (Debug 3) (speed 0))
   (type (mod 16) depth))
  (loop
     with result =
       (list (prefix-buckets (* +hash-tree-bits-per-level+ depth)))
     for current-depth from (1- depth) downto 0
     for new-level = (make-array (expt 2 (* +hash-tree-bits-per-level+ current-depth)))
                 ;;   ^ Unreachable code
     do
       (map-into new-level (lambda () (ironclad:make-digest +hash+)))
       (loop for item across (car result)
          for idx from 0
            ;do (print idx)
          do (ironclad:update-digest
              (aref new-level (floor idx
                                     (expt 2 +hash-tree-bits-per-level+)))
              item))
       (push
        (map-into (make-array (length new-level)) #'ironclad:produce-digest new-level)
        result)
     finally (return result)))