From 7118efc35a64ece0d37d801f9f59e886402b0d22 Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Mon, 26 Jul 2004 10:24:40 +0000 Subject: [PATCH] 0.8.13.3: Improve BIGNUM-GCD ever so slightly ... BIGNUM-INDEX isn't actually usefully INDEX, because we require the ability to index individual bits. Divide the type by 32, then. ... rearrange bignum.lisp slightly to declare types of functions before their use. (Aside: I'm not sure why I need the type declaration, given that the final compiler can derive the type fine. Maybe the cross-compiler is lobotomized in some significant way here?) --- src/code/bignum.lisp | 33 ++++++++++++++++++++------------- src/compiler/generic/vm-type.lisp | 5 ++++- version.lisp-expr | 2 +- 3 files changed, 25 insertions(+), 15 deletions(-) diff --git a/src/code/bignum.lisp b/src/code/bignum.lisp index c0606e6..c188965 100644 --- a/src/code/bignum.lisp +++ b/src/code/bignum.lisp @@ -519,6 +519,26 @@ ;;;; GCD +;;; I'm not sure why I need this FTYPE declaration. Compiled by the +;;; target compiler, it can deduce the return type fine, but without +;;; it, we pay a heavy price in BIGNUM-GCD when compiled by the +;;; cross-compiler. -- CSR, 2004-07-19 +(declaim (ftype (sfunction (bignum-type bignum-index bignum-type bignum-index) + (unsigned-byte 29)) + bignum-factors-of-two)) +(defun bignum-factors-of-two (a len-a b len-b) + (declare (type bignum-index len-a len-b) (type bignum-type a b)) + (do ((i 0 (1+ i)) + (end (min len-a len-b))) + ((= i end) (error "Unexpected zero bignums?")) + (declare (type bignum-index i end)) + (let ((or-digits (%logior (%bignum-ref a i) (%bignum-ref b i)))) + (unless (zerop or-digits) + (return (do ((j 0 (1+ j)) + (or-digits or-digits (%ashr or-digits 1))) + ((oddp or-digits) (+ (* i digit-size) j)) + (declare (type (mod 32) j)))))))) + (defun bignum-gcd (a b) (declare (type bignum-type a b)) (let* ((a (if (%bignum-0-or-plusp a (%bignum-length a)) @@ -605,19 +625,6 @@ (bignum-buffer-ashift-right a len-a (+ (* index digit-size) increment))))))) - -(defun bignum-factors-of-two (a len-a b len-b) - (declare (type bignum-index len-a len-b) (type bignum-type a)) - (do ((i 0 (1+ i)) - (end (min len-a len-b))) - ((= i end) (error "Unexpected zero bignums?")) - (declare (type bignum-index i end)) - (let ((or-digits (%logior (%bignum-ref a i) (%bignum-ref b i)))) - (unless (zerop or-digits) - (return (do ((j 0 (1+ j)) - (or-digits or-digits (%ashr or-digits 1))) - ((oddp or-digits) (+ (* i digit-size) j)) - (declare (type (mod 32) j)))))))) ;;;; negation diff --git a/src/compiler/generic/vm-type.lisp b/src/compiler/generic/vm-type.lisp index e43b2d4..fc763a3 100644 --- a/src/compiler/generic/vm-type.lisp +++ b/src/compiler/generic/vm-type.lisp @@ -73,7 +73,10 @@ (sb!xc:deftype bignum-element-type () `(unsigned-byte ,sb!vm:n-word-bits)) (sb!xc:deftype bignum-type () 'bignum) -(sb!xc:deftype bignum-index () 'index) +;;; FIXME: see also DEFCONSTANT MAXIMUM-BIGNUM-LENGTH in +;;; src/code/bignum.lisp. -- CSR, 2004-07-19 +(sb!xc:deftype bignum-index () + '(integer 0 #.(1- (ash 1 (- 32 sb!vm:n-widetag-bits))))) ;;;; hooks into the type system diff --git a/version.lisp-expr b/version.lisp-expr index 5d498bf..6c5211b 100644 --- a/version.lisp-expr +++ b/version.lisp-expr @@ -17,4 +17,4 @@ ;;; checkins which aren't released. (And occasionally for internal ;;; versions, especially for internal versions off the main CVS ;;; branch, it gets hairier, e.g. "0.pre7.14.flaky4.13".) -"0.8.13.2" +"0.8.13.3" -- 1.7.10.4