unsigned-prod.lisp

(sb-c::defknown modular* ((unsigned-byte 64) (unsigned-byte 64)) (unsigned-byte 64)
    (sb-c::movable sb-c::foldable sb-c::flushable sb-c::commutative)
  :overwrite-fndb-silently t)

;; same as fast-*/unsigned=>unsigned
(sb-c::define-vop (fast-mult sb-vm::fast-safe-arith-op)
  (:translate modular*)
  (:args (x :scs (sb-vm::unsigned-reg) :target eax)
         (y :scs (sb-vm::unsigned-reg sb-vm::unsigned-stack)))
  (:arg-types sb-vm::unsigned-num sb-vm::unsigned-num)
  (:temporary (:sc sb-vm::unsigned-reg :offset sb-vm::rax-offset :target r
               :from (:argument 0) :to :result) eax)
  (:temporary (:sc sb-vm::unsigned-reg :offset sb-vm::rdx-offset
               :from :eval :to :result) edx)
  (:ignore edx)
  (:results (r :scs (sb-vm::unsigned-reg)))
  (:result-types sb-vm::unsigned-num)
  (:note "inline (unsigned-byte 64) arithmetic")
  (:vop-var vop)
  (:save-p :compute-only)
  (:generator 6
              (sb-c:move eax x)
              (sb-assem::inst sb-x86-64-asm::mul eax y)
              (sb-c:move r eax)))

(defun test1 (n)
  (declare (optimize (speed 3) (safety 0))
           ((integer 0 #.most-positive-fixnum) n))
  (let ((res 0))
    (declare (bit res))
    (dotimes (x n res)
      (let ((bit (ldb (byte 1 63) (modular* x (+ 7 (expt 10 15))))))
        (setq res (logxor bit res))))))

(disassemble #'test1)
(time (test1 4000000000))

;; same as fast-*-c/unsigned=>unsigned
(sb-c::define-vop (fast-mult-c sb-vm::fast-safe-arith-op)
  (:translate modular*)
  (:args (x :scs (sb-vm::unsigned-reg) :target eax))
  (:info y)
  (:arg-types sb-vm::unsigned-num (:constant (unsigned-byte 64)))
  (:temporary (:sc sb-vm::unsigned-reg :offset sb-vm::rax-offset :target r
               :from (:argument 0) :to :result) eax)
  (:temporary (:sc sb-vm::unsigned-reg :offset sb-vm::rdx-offset
               :from :eval :to :result) edx)
  (:ignore edx)
  (:results (r :scs (sb-vm::unsigned-reg)))
  (:result-types sb-vm::unsigned-num)
  (:note "inline (unsigned-byte 64) arithmetic")
  (:vop-var vop)
  (:save-p :compute-only)
  (:generator
   5
   (sb-c:move eax x)
   (sb-assem::inst sb-x86-64-asm::mul eax (sb-c:register-inline-constant :qword y))
   (sb-c:move r eax)))

(defun test2 (n)
  (declare (optimize (speed 3) (safety 0))
           ((integer 0 #.most-positive-fixnum) n))
  (let ((res 0))
    (declare (bit res))
    (dotimes (x n res)
      (let ((bit (ldb (byte 1 63) (modular* x (+ 7 (expt 10 15))))))
        (setq res (logxor bit res))))))

(disassemble #'test2)
(time (test2 4000000000))