| 1 |
;;; |
| 2 |
;;; scheme.bitwise - Bitwise operations (R7RS Tangerine) |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2017-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;; Originally SRFI-151 |
| 35 |
|
| 36 |
(define-module scheme.bitwise |
| 37 |
(use scheme.list) |
| 38 |
(use scheme.vector) |
| 39 |
(use srfi.60) |
| 40 |
(use gauche.generator) |
| 41 |
(export bitwise-not ; SRFI-60 |
| 42 |
bitwise-and ; SRFI-60 |
| 43 |
bitwise-ior ; SRFI-60 |
| 44 |
bitwise-xor ; SRFI-60 |
| 45 |
bitwise-eqv |
| 46 |
bitwise-nand bitwise-nor |
| 47 |
bitwise-andc1 bitwise-andc2 |
| 48 |
bitwise-orc1 bitwise-orc2 |
| 49 |
|
| 50 |
arithmetic-shift ; SRFI-60 |
| 51 |
bit-count ; builtin |
| 52 |
integer-length ; builtin |
| 53 |
|
| 54 |
bitwise-if ; SRFI-60 |
| 55 |
bit-set? ; builtin |
| 56 |
copy-bit ; builtin |
| 57 |
bit-swap |
| 58 |
any-bit-set? |
| 59 |
every-bit-set? |
| 60 |
first-set-bit ; builtin |
| 61 |
|
| 62 |
bit-field ; builtin |
| 63 |
bit-field-any? |
| 64 |
bit-field-every? |
| 65 |
bit-field-clear |
| 66 |
bit-field-set |
| 67 |
bit-field-replace |
| 68 |
bit-field-replace-same |
| 69 |
bit-field-rotate |
| 70 |
bit-field-reverse |
| 71 |
|
| 72 |
bits->list |
| 73 |
list->bits |
| 74 |
bits->vector |
| 75 |
vector->bits |
| 76 |
bits |
| 77 |
bitwise-fold |
| 78 |
bitwise-for-each |
| 79 |
bitwise-unfold |
| 80 |
make-bitwise-generator)) |
| 81 |
(select-module scheme.bitwise) |
| 82 |
|
| 83 |
(define (%bitwise-eqv-2 a b) (lognot (logxor a b))) |
| 84 |
|
| 85 |
(define bitwise-eqv |
| 86 |
(case-lambda |
| 87 |
[() -1] |
| 88 |
[(a) a] |
| 89 |
[(a b) (%bitwise-eqv-2 a b)] |
| 90 |
[(a b . args) (apply bitwise-eqv (%bitwise-eqv-2 a b) args)])) |
| 91 |
|
| 92 |
;; TODO: These can be a lot more efficiently implemented natively, and |
| 93 |
;; eventually, we'd rather optimize expressons like (lognot (logand a b)) |
| 94 |
;; into built-in bitwise-nand etc. |
| 95 |
(define (bitwise-nand a b) (lognot (logand a b))) |
| 96 |
(define (bitwise-nor a b) (lognot (logior a b))) |
| 97 |
(define (bitwise-andc1 a b) (logand (lognot a) b)) |
| 98 |
(define (bitwise-andc2 a b) (logand a (lognot b))) |
| 99 |
(define (bitwise-orc1 a b) (logior (lognot a) b)) |
| 100 |
(define (bitwise-orc2 a b) (logior a (lognot b))) |
| 101 |
|
| 102 |
(define (bit-swap index1 index2 n) |
| 103 |
(let ([a (bit-set? index1 n)] |
| 104 |
[b (bit-set? index2 n)]) |
| 105 |
(copy-bit index1 (copy-bit index2 n a) b))) |
| 106 |
|
| 107 |
(define (any-bit-set? test-bits n) (not (zero? (logand test-bits n)))) |
| 108 |
(define (every-bit-set? test-bits n) (= (logand test-bits n) test-bits)) |
| 109 |
|
| 110 |
(define (bit-field-any? n start end) (not (zero? (bit-field n start end)))) |
| 111 |
(define (bit-field-every? n start end) (zero? (bit-field (lognot n) start end))) |
| 112 |
|
| 113 |
(define (bit-field-clear n start end) (copy-bit-field n 0 start end)) |
| 114 |
(define (bit-field-set n start end) (copy-bit-field n -1 start end)) |
| 115 |
|
| 116 |
(define bit-field-replace copy-bit-field) |
| 117 |
|
| 118 |
(define (bit-field-replace-same dst src start end) |
| 119 |
(copy-bit-field dst (bit-field src start end) start end)) |
| 120 |
|
| 121 |
(define bit-field-rotate rotate-bit-field) ;SRFI-60 |
| 122 |
(define bit-field-reverse reverse-bit-field) ;SRFI-60 |
| 123 |
|
| 124 |
(define (bits->list n . opts) |
| 125 |
(assume (not (negative? n))) |
| 126 |
(reverse (apply integer->list n opts))) |
| 127 |
|
| 128 |
(define (bits->vector n :optional len) |
| 129 |
(assume (not (negative? n))) |
| 130 |
(vector-unfold (cut bit-set? <> n) |
| 131 |
(if (undefined? len) (integer-length n) len))) |
| 132 |
|
| 133 |
(define (list->bits bs) (list->integer (reverse bs))) |
| 134 |
(define (vector->bits bs) (list->integer (reverse-vector->list bs))) |
| 135 |
(define (bits . bs) (list->bits bs)) |
| 136 |
|
| 137 |
(define (bitwise-fold proc seed n) |
| 138 |
(define len (integer-length n)) |
| 139 |
(do ([len len (- len 1)] |
| 140 |
[n n (ash n -1)] |
| 141 |
[seed seed (proc (odd? n) seed)]) |
| 142 |
[(<= len 0) seed])) |
| 143 |
|
| 144 |
(define (bitwise-for-each proc n) |
| 145 |
(bitwise-fold (^[b _] (proc b)) 0 n)) |
| 146 |
|
| 147 |
(define (bitwise-unfold p f g seed) |
| 148 |
(do ([seed seed (g seed)] |
| 149 |
[i 0 (+ i 1)] |
| 150 |
[r 0 (copy-bit i r (f seed))]) |
| 151 |
[(p seed) r])) |
| 152 |
|
| 153 |
;; Unlike bits->generator in gauche.generator, this one is infinite. |
| 154 |
(define (make-bitwise-generator n) |
| 155 |
(^[] (begin0 (odd? n) (set! n (ash n -1))))) |