diff -uNr a/gbw-signer/library/bit-ops.scm b/gbw-signer/library/bit-ops.scm --- a/gbw-signer/library/bit-ops.scm 39b52aba0a9ecc2a6c9f386a63b449b408e399ca3fc2b658f59505af1d3835f1c2b742b0965f7792a3e27555592fe40a47360bd307fd2df9f0295a8b4d3bbb4c +++ b/gbw-signer/library/bit-ops.scm e1a82272490faa005ebb3ab2785dffa511d6b55e0ed59199da2ff4ff2688d384e6334f5d42139a430062a02e609ac2587e1294a796087be6f10d7e720c6aa4b1 @@ -68,27 +68,26 @@ ;; Positive (left) shift: signedness doesn't matter. ;; Assumes 0 <= bits < fz-width . - ;; Constant time w.r.t. words only (NOT bits). - (define (shift-up words bits) - ; XXX slow - maybe provide a fixnum quotient/remainder ? Pass them in from the curried variants ? + (define (shift-up-by bits) + ;; XXX slow - maybe provide a simultaneous fixnum quotient/remainder , or precompute a lookup table (0 to (- fz-width 1)) ? (let ((whole-words (quotient bits *fixnum-width*)) (bits (remainder bits *fixnum-width*))) ;; 0 <= whole-words < word-count ;; 0 <= bits < *fixnum-width* (let ((carry-shift (fx-/wrap bits *fixnum-width*))) ;; (-)*fixnum-width* <= carry-shift < 0 - (do ((words words (cdr words)) + (lambda (a) + (do ((words a (cdr words)) (carry 0 (fxshift/unsigned (car words) carry-shift)) (acc (repeat 0 whole-words) (cons (fxior (fxshift (car words) bits) carry) acc)) (todo (fx-/wrap word-count whole-words) (fx-/wrap todo 1))) ;; 0 <= todo <= word-count - ((fx= 0 todo) (press-fz acc)))))) + ((fx= 0 todo) (press-fz acc))))))) ;; Negative (right) shift without sign extension. ;; Assumes 0 <= bits < fz-width . - ;; Constant time w.r.t. words only (NOT bits). - (define (shift-down-unsigned words bits) + (define (shift-down-by/unsigned bits) ; XXX slow - as above (let ((whole-words (quotient bits *fixnum-width*)) (bits (fx-/wrap (remainder bits *fixnum-width*)))) @@ -96,20 +95,21 @@ ;; (-)*fixnum-width* < bits <= 0 (let ((carry-shift (fx+/wrap bits *fixnum-width*))) ;; 0 < carry-shift <= *fixnum-width* - (do ((words (reverse (list-tail words whole-words)) (cdr words)) + (lambda (a) + (do ((words (reverse (list-tail a whole-words)) (cdr words)) (carry 0 (fxshift (car words) carry-shift)) (acc (repeat 0 whole-words) (cons (fxior (fxshift/unsigned (car words) bits) carry) acc))) - ((null? words) acc))))) + ((null? words) acc)))))) ;; Front-end for unsigned shifts. ;; Constant time w.r.t. FZ value only (NOT bits). (define (ufzshift-by bits) (cond ((zero? bits) (lambda (a) a)) ((>= (abs bits) fz-width) (lambda (a) (fz0))) - ((positive? bits) (lambda (a) (shift-up a bits))) - (else (lambda (a) (shift-down-unsigned a (- bits)))))) + ((fx< 0 bits) (shift-up-by bits)) + (else (shift-down-by/unsigned (fx-/wrap bits))))) ;; Bit rotation: signedness doesn't matter. ;; Rotates to the "left" i.e. more-significant. @@ -120,17 +120,24 @@ (error "fzrot: bits out of range:" bits)) ((fx= 0 bits) a) ;; 0 < bits < fz-width - (else (fzior (shift-up a bits) - (shift-down-unsigned a (fx-/wrap fz-width bits)))))) + ;; XXX slow due to separate shifts + (else (fzior ((shift-up-by bits) a) + ((shift-down-by/unsigned (fx-/wrap fz-width bits)) + a))))) - ;; Curried variant allowing arbitrary integer rotations, pre-reduced. + ;; Curried variant allowing arbitrary integer rotations, pre-reduced. Faster than fzrot if you can reuse the returned procedure for a set shift amount. (define (fzrot-by bits) - (let* ((reduced (modulo bits fz-width)) - (complement (fx-/wrap fz-width reduced))) + (let ((reduced (modulo bits fz-width))) (if (fx= 0 reduced) (lambda (a) a) - (lambda (a) (fzior (shift-up a reduced) - (shift-down-unsigned a complement)))))) + ;; 0 < reduced < fz-width + ;; XXX slow due to separate shifts + (let ((shift-up (shift-up-by reduced)) + (shift-down (shift-down-by/unsigned + (fx-/wrap fz-width reduced)))) + (lambda (a) + (fzior (shift-up a) + (shift-down a))))))) (define (fznot a) (press-fz (reverse-map1 fxnot a))) diff -uNr a/gbw-signer/manifest b/gbw-signer/manifest --- a/gbw-signer/manifest 7b44f92a54e02a27aa8dd3d7e333e7828bd393e5eba6cf501ada221ff6b49dc5e3055cb004f0d5064c490e1db7819853f05c5e40909c4423f4610f1033236539 +++ b/gbw-signer/manifest 56d65bd8fb8856d2da1d230b2182198ff27a62f947ccc0e4ee3b1551cd780f70cbef27dbeeb103ba4911a1d39b164e15cf444eb2d9bcd3d9507aa3fd9007adaa @@ -1,3 +1,4 @@ 711740 gbw-signer_subdir_genesis jfw Offline signer component of gbw, the Gales Bitcoin Wallet. Reissued to follow various conventions: top-level project subdir, lowercase manifest filename, README at project level. (File renaming only; pending content changes are to follow.) 711740 gbw-signer_usrbin jfw Change command symlink from /command/gbw-signer to /usr/bin/gbw-signer and likewise for the referenced gscm binary. Formalize the installed command list at package/commands. Update README and bump version to reflect the packaging changes. 739066 gbw-signer_static_bit_ops_1 jfw Restructure the library of arithmetic and bitwise operators on fixed-width integers to be separately instantiated for given bit widths, rather than tracking the width dynamically in the operand objects (reindenting deliberately suppressed for patch readability). This saves substantial redundant runtime computations, data wrangling and checking, at a cost of less helpful error reporting and slightly more setup for callers. Correct an ass-backwards comment as to which bits are padding; expand comments generally, mainly to note variable ranges. Replace much generic arithmetic with with faster fixnum arithmetic where applicable. Move toward curried forms of bit shift and rotation operators to allow pre-analysis of shift size. Update hash function library for the changes. Bump version and fix "check" script to find the code by relative path rather than globally active version. Hashing speedup on my machine (x86_64, gscm 0.40.6) is around 4x. +739066 gbw-signer_static_bit_ops_2 jfw Further optimize shifts and rotations as hinted in comments by propagating curried arguments to the internals, allowing precomputed divisions. Total hashing speedup for the series increases to 5x.