Debian Codegraph @

lib/scheme/bitwise.scm

raw
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)))))