source: project/wiki/eggref/5/srfi-178 @ 39323

Last change on this file since 39323 was 39323, checked in by Zipheir, 2 months ago

Add srfi-141 egg dependency.

File size: 20.6 KB
Line 
1== SRFI-178: Bitvector library
2
3This SRFI describes a set of operations on homogeneous bitvectors. Operations
4analogous to those provided on the other homogeneous vector types described in
5[[https://srfi.schemers.org/srfi-160|SRFI 160]] are provided,
6along with operations analogous to the bitwise operations of
7[[https://srfi.schemers.org/srfi-151|SRFI 151]].
8
9Bitvectors are implemented as wrapped [[srfi-160]] u8vectors; for
10simplicity and possibly for speed, they use a whole byte to represent each
11bit, as Java and C# do.
12
13[[toc:]]
14
15== SRFI Description
16
17This page includes excerpts from the SRFI document, but is primarily
18intended to document the forms exported by this egg.  For a full
19description of the SRFI, see the full
20[[https://srfi.schemers.org/srfi-160/srfi-160.html|SRFI document]].
21
22== Authors
23
24John Cowan (text) and Wolfgang Corcoran-Mathe (implementation)
25
26== Specification
27
28Bitvectors are disjoint from all other Scheme types with the possible
29exception of u1vectors, if the Scheme implementation supports them.
30
31The procedures of this SRFI that accept single bits or lists of bits can be
32passed any of the values {{0, 1, #f, #t}}. Procedures that return a bit or a
33list of bits come in two flavors: one ending in {{/int}} that returns an exact
34integer, and one ending in {{/bool}} that returns a boolean.
35
36Mapping and folding procedures also come in two flavors: those ending in
37{{/int}} pass exact integers to their procedure arguments, whereas those ending
38in {{/bool}} pass booleans to theirs.
39
40Procedures whose names end in {{!}} are the same as the corresponding procedures
41without {{!}}, except that the first bitvector argument is mutated and an
42unspecified result is returned. Consequently, only the non-{{!}} version is
43documented below.
44
45It is an error unless all ''bitvector'' arguments passed to procedures that
46accept more than one are of the same length (except as otherwise noted).
47
48== Notation
49
50In the section containing specifications of procedures, the following notation
51is used to specify parameters and return values:
52
53; ''(f arg₁ arg₂ ...)'' → ''something'' : A procedure ''f'' that takes the parameters ''arg₁ arg₂ ...'' and returns a value of the type ''something''. If two values are returned, two types are specified. If ''something'' is {{unspecified}}, then ''f'' returns a single implementation-dependent value; this SRFI does not specify what it returns, and in order to write portable code, the return value should be ignored.
54; ''vec'' : A heterogeneous vector; that is, it must satisfy the predicate {{vector?}}.
55; ''bvec, to, from'' : A bitvector, i.e. it must satisfy the predicate {{bitvector?}}. In {{bitvector-copy!}} and {{reverse-bitvector-copy!}}, ''to'' is the destination and ''from'' is the source.
56; ''i, j, start, at'' : An exact nonnegative integer less than the length of the bitvector. In {{bitvector-copy!}} and {{reverse-bitvector-copy!}}, ''at'' refers to the destination and ''start'' to the source.
57; ''end'' : An exact nonnegative integer not less than ''start''. This indicates the index directly before which traversal will stop--processing will occur until the index of the vector is one less than ''end''. It is the open right side of a range.
58; ''f'' : A procedure taking one or more arguments, which returns (except as noted otherwise) exactly one value.
59; ''='' : An equivalence procedure.
60; ''obj, seed, knil'' : Any Scheme object.
61; ''[something]'' : An optional argument; it needn't necessarily be applied. ''Something'' needn't necessarily be one thing; for example, this usage of it is perfectly valid: {{[start [end]]}} and is indeed used quite often.
62; ''something ...'' : Zero or more {{something}}s are allowed to be arguments.
63; ''something₁ something₂ ...'' : One or more {{something}}s must be arguments.
64
65All procedures that return bitvectors, vectors, or lists newly allocate their
66results, except those that end in {{!}}. However, a zero-length value need not
67be separately allocated.
68
69Except as otherwise noted, the semantics of each procedure are those of the
70corresponding SRFI 133 or SRFI 151 procedure.
71
72== Procedures
73
74=== Bit conversion
75
76<procedure>(bit->integer bit) → exact integer</procedure>
77
78Returns 0 if ''bit'' is 0 or {{#f}} and 1 if ''bit'' is 1 or {{#t}}.
79
80<procedure>(bit->boolean bit) → exact integer</procedure>
81
82Returns {{#f}} if ''bit'' is 0 or {{#f}} and {{#t}} if ''bit'' is 1 or {{#t}}.
83
84=== Constructors
85
86<procedure>(make-bitvector size [bit]) → bitvector </procedure>
87
88Returns a bitvector whose length is ''size''. If ''bit'' is provided, all the
89elements of the bitvector are initialized to it.
90
91<procedure>(bitvector value ...) → bitvector </procedure>
92
93Returns a bitvector initialized with ''values''.
94
95<procedure>(bitvector-unfold f length seed ...) → bitvector</procedure>
96
97Creates a vector whose length is ''length'' and iterates across each index ''k''
98between 0 and ''length'', applying ''f'' at each iteration to the current index
99and current states, in that order, to receive ''n'' + 1 values: the bit to put in
100the ''k''th slot of the new vector and new states for the next iteration. On the
101first call to ''f'', the states' values are the ''seeds''.
102
103<procedure>(bitvector-unfold-right f length seed) → bitvector</procedure>
104
105The same as {{bitvector-unfold}}, but initializes the bitvector from right to
106left.
107
108<procedure>(bitvector-copy bvec [start [end]]) → bitvector</procedure>
109
110Makes a copy of the portion of ''bvec'' from ''start'' to ''end'' and returns it.
111
112<procedure>(bitvector-reverse-copy bvec [start [end]]) → bitvector</procedure>
113
114The same as {{bitvector-copy}}, but in reverse order.
115
116<procedure>(bitvector-append bvec ...) → bitvector</procedure>
117
118Returns a bitvector containing all the elements of the ''bvecs'' in order.
119
120<procedure> (bitvector-concatenate list-of-bitvectors) → bitvector</procedure>
121
122The same as {{bitvector-append}}, but takes a list of bitvectors rather than
123multiple arguments.
124
125<procedure>(bitvector-append-subbitvectors [bvec start end] ...) → bitvector</procedure>
126
127Concatenates the result of applying {{bitvector-copy}} to each triplet of
128''bvec, start, end'' arguments, but may be implemented more efficiently.
129
130=== Predicates
131
132<procedure>(bitvector? obj) → boolean</procedure>
133
134Returns {{#t}} if ''obj'' is a bitvector, and {{#f}} otherwise.
135
136<procedure>(bitvector-empty? bvec) → boolean</procedure>
137
138Returns {{#t}} if ''bvec'' has a length of zero, and {{#f}} otherwise.
139
140<procedure>(bitvector=? bvec ...) → boolean</procedure>
141
142Compares the ''bvecs'' for element-wise equality, using {{eqv?}} to do the
143comparisons, and returns {{#t}} or {{#f}} accordingly.
144
145=== Selectors
146
147<procedure>(bitvector-ref/int bvec i) → integer</procedure>
148<procedure>(bitvector-ref/bool bvec i) → boolean</procedure>
149
150Returns the ''i''th element of ''bvec'' as an exact integer or boolean
151respectively.
152
153<procedure>(bitvector-length bvec) → exact nonnegative integer</procedure>
154
155Returns the length of ''bvec''.
156
157=== Iteration
158
159<procedure>(bitvector-take bvec n) → bitvector</procedure>
160
161<procedure>(bitvector-take-right bvec n) → bitvector</procedure>
162
163Returns a bitvector containing the first/last ''n'' elements of ''bvec''.
164
165<procedure>(bitvector-drop bvec n) → bitvector</procedure>
166
167<procedure>(bitvector-drop-right bvec n) → bitvector</procedure>
168
169Returns a bitvector containing all except the first/last ''n'' elements
170of ''bvec''.
171
172<procedure>(bitvector-segment bvec n) → list</procedure>
173
174Returns a list of bitvectors, each of which contains ''n'' consecutive
175elements of ''bvec''. The last bitvector may be shorter than ''n''.
176
177<procedure>(bitvector-fold/int kons knil bvec1 bvec2 ...) → object</procedure>
178<procedure>(bitvector-fold/bool kons knil bvec1 bvec2 ...) → object</procedure>
179<procedure>(bitvector-fold-right/int kons knil bvec1 bvec2 ...) → object</procedure>
180<procedure>(bitvector-fold-right/bool kons knil bvec1 bvec2 ...) → object</procedure>
181
182Folds ''kons'' over the elements of ''bvec'' in increasing/decreasing order using
183''knil'' as the initial value. The kons procedure is called with the states
184first and the new element last, as in SRFIs 43, 133, and 160.
185
186<procedure>(bitvector-map/int f bvec1 bvec2 ...) → bitvector</procedure>
187<procedure>(bitvector-map/bool f bvec1 bvec2 ...) → bitvector</procedure>
188<procedure>(bitvector-map!/int f bvec1 bvec2 ...) → unspecified</procedure>
189<procedure>(bitvector-map!/bool f bvec1 bvec2 ...) → unspecified</procedure>
190<procedure>(bitvector-map->list/int f bvec1 bvec2 ...) → list</procedure>
191<procedure>(bitvector-map->list/bool f bvec1 bvec2 ...) → list</procedure>
192<procedure>(bitvector-for-each/int f bvec1 bvec2 ...) → unspecified</procedure>
193<procedure>(bitvector-for-each/bool f bvec1 bvec2 ...) → unspecified</procedure>
194
195Iterate over the corresponding elements of the ''bvecs'' and apply ''f'' to each,
196returning respectively: a bitvector of the results, an undefined value with
197the results placed back in ''bvec1'', a list of the results, and an undefined
198value with no change to ''bvec1''.
199
200=== Prefixes, suffixes, trimming, padding
201
202<procedure>(bitvector-prefix-length bvec1 bvec2) → index</procedure>
203<procedure>(bitvector-suffix-length bvec1 bvec2) → index</procedure>
204
205Return the number of elements that are equal in the prefix/suffix of the two
206''bvecs'', which are allowed to be of different lengths.
207
208<procedure>(bitvector-prefix? bvec1 bvec2) → boolean</procedure>
209
210<procedure>(bitvector-suffix? bvec1 bvec2) → boolean</procedure>
211
212Returns {{#t}} if ''bvec1'' is a prefix/suffix of ''bvec2'', and {{#f}}
213otherwise. The arguments are allowed to be of different lengths.
214
215<procedure>(bitvector-pad  bit bvec length) → bvec</procedure>
216<procedure>(bitvector-pad-right  bit bvec length) → bvec</procedure>
217
218Returns a copy of ''bvec'' with leading/trailing elements equal to
219''bit'' added (if necessary) so that the length of the result is ''length''.
220
221<procedure>(bitvector-trim bit bvec) → bvec</procedure>
222<procedure>(bitvector-trim-right bit bvec) → bvec</procedure>
223<procedure>(bitvector-trim-both bit bvec) → bvec</procedure>
224
225Returns a copy of ''bvec'' with leading/trailing/both elements equal
226to ''bit'' removed.
227
228=== Mutators
229
230<procedure>(bitvector-set! bvec i bit) → unspecified</procedure>
231
232Sets the ''i''th element of ''bvec'' to ''bit''.
233
234<procedure>(bitvector-swap! bvec i j) → unspecified</procedure>
235
236Interchanges the ''i''th and ''j''th elements of ''bvec''.
237
238<procedure>(bitvector-reverse! bvec [start [end]]) → unspecified</procedure>
239
240Reverses the portion of ''bvec'' from ''start'' to ''end''.
241
242<procedure>(bitvector-copy! to at from [start [end]]) → unspecified</procedure>
243
244Copies the portion of ''from'' from ''start'' to ''end'' onto ''to'',
245starting at index ''at''.
246
247<procedure>(bitvector-reverse-copy! to at from [start [end]]) → unspecified</procedure>
248
249The same as {{bitvector-copy!}}, but copies in reverse.
250
251=== Conversion
252
253<procedure>(bitvector->list/int bvec [start [end]]) → list of integers</procedure>
254<procedure>(bitvector->list/bool bvec [start [end]]) → list of booleans</procedure>
255
256<procedure>(reverse-bitvector->list/int bvec [start [end]]) → list of integers</procedure>
257<procedure>(reverse-bitvector->list/bool bvec [start [end]]) → list of booleans</procedure>
258
259<procedure>(list->bitvector list) → bitvector</procedure>
260<procedure>(reverse-list->bitvector list) → bitvector</procedure>
261
262<procedure>(bitvector->vector/int bvec [start [end]]) → vector of integers</procedure>
263<procedure>(bitvector->vector/bool bvec [start [end]]) → vector of booleans</procedure>
264
265<procedure>(reverse-bitvector->vector/int bvec [start [end]]) → vector of integers</procedure>
266<procedure>(reverse-bitvector->vector/bool bvec [start [end]]) → vector of booleans</procedure>
267<procedure>(vector->bitvector vec [start [end]]) → bitvector</procedure>
268<procedure>(reverse-vector->bitvector vec [start [end]]) → bitvector</procedure>
269
270Returns a list, bitvector, or heterogeneous vector with the same
271elements as the argument, in reverse order where specified.
272
273<procedure>(bitvector->string bvec) → string</procedure>
274
275Returns a string beginning with "#*" and followed by the values of ''bvec''
276represented as 0 and 1 characters. This is the Common Lisp representation of a
277bitvector.
278
279<procedure>(string->bitvector string) → bitvector</procedure>
280
281Parses a string in the format generated by {{bitvector->string}} and returns the
282corresponding bitvector, or {{#f}} if the string is not in this format.
283
284<procedure>(bitvector->integer bitvector)</procedure>
285
286Returns a non-negative exact integer whose bits, starting with the least
287significant bit as bit 0, correspond to the values in ''bitvector''. This
288ensures compatibility with the integers-as-bits operations of
289[[https://srfi.schemers.org/srfi-151/srfi-151.html|SRFI 151]].
290
291<procedure>(integer->bitvector integer [len])</procedure>
292
293Returns a bitvector whose length is ''len'' whose values correspond to the bits
294of ''integer'', a non-negative exact integer, starting with the least
295significant bit as bit 0. This ensures compatibility with the integers-as-bits
296operations of [[https://srfi.schemers.org/srfi-151/srfi-151.html|SRFI 151]].
297
298The default value of ''len'' is {{(integer-length}} ''integer''{{)}}.
299If the value of ''len'' is less than the default, the resulting bitvector
300cannot be converted back by {{bitvector->integer}} correctly.
301
302=== Generators
303
304<procedure>(make-bitvector/int-generator bitvector)</procedure>
305<procedure>(make-bitvector/bool-generator bitvector)</procedure>
306
307Returns a [[srfi-158]]
308generator that generates all the values of ''bitvector'' in order. Note that the
309generator is finite.
310
311<procedure>(make-bitvector-accumulator)</procedure>
312
313Returns a [[srfi-158]]
314accumulator that collects all the bits it is invoked on. When invoked on an
315end-of-file object, returns a bitvector containing all the bits in order.
316
317=== Basic operations
318
319<procedure>(bitvector-not bvec)</procedure>
320<procedure>(bitvector-not! bvec)</procedure>
321
322Returns the element-wise complement of ''bvec''; that is, each value is changed
323to the opposite value.
324
325The following ten procedures correspond to the useful set of non-trivial
326two-argument boolean functions. For each such function, the corresponding
327bitvector operator maps that function across two or more bitvectors in an
328element-wise fashion. The core idea of this group of functions is this
329element-wise "lifting" of the set of dyadic boolean functions to bitvector
330parameters.
331
332<procedure>(bitvector-and bvec1 bvec2 bvec ...)</procedure>
333<procedure>(bitvector-and! bvec1 bvec2 bvec ...)</procedure>
334<procedure>(bitvector-ior bvec1 bvec2 bvec ...)</procedure>
335<procedure>(bitvector-ior! bvec1 bvec2 bvec ...)</procedure>
336<procedure>(bitvector-xor bvec1 bvec2 bvec ...)</procedure>
337<procedure>(bitvector-xor! bvec1 bvec2 bvec ...)</procedure>
338<procedure>(bitvector-eqv bvec1 bvec2 bvec ...)</procedure>
339<procedure>(bitvector-eqv! bvec1 bvec2 bvec ...)</procedure>
340
341These operations are associative.
342
343The {{bitvector-eqv}} procedure produces the complement of the {{bitvector-xor}}
344procedure. When applied to three arguments, it does ''not'' produce a {{#t}} value
345everywhere that a, b and c all agree. That is, it does ''not'' produce
346
347<enscript highlight="scheme">
348(bitvector-ior (bitvector-and a b c)
349               (bitvector-and (bitvector-not a)
350                              (bitvector-not b)
351                              (bitvector-not c)))
352</enscript>
353
354Rather, it produces {{(bitvector-eqv a (bitvector-eqv b c))}} or the equivalent
355{{(bitvector-eqv (bitvector-eqv a b) c)}}.
356
357<procedure>(bitvector-nand bvec1 bvec2)</procedure>
358<procedure>(bitvector-nand! bvec1 bvec2)</procedure>
359<procedure>(bitvector-nor bvec1 bvec2)</procedure>
360<procedure>(bitvector-nor! bvec1 bvec2)</procedure>
361<procedure>(bitvector-andc1 bvec1 bvec2)</procedure>
362<procedure>(bitvector-andc1! bvec1 bvec2)</procedure>
363<procedure>(bitvector-andc2 bvec1 bvec2)</procedure>
364<procedure>(bitvector-andc2! bvec1 bvec2)</procedure>
365<procedure>(bitvector-orc1 bvec1 bvec2)</procedure>
366<procedure>(bitvector-orc1! bvec1 bvec2)</procedure>
367<procedure>(bitvector-orc2 bvec1 bvec2)</procedure>
368<procedure>(bitvector-orc2! bvec1 bvec2)</procedure>
369
370These operations are not associative.
371
372=== Quasi-integer operations
373
374<procedure>(bitvector-logical-shift bvec count bit)</procedure>
375
376Returns a bitvector equal in length to ''bvec'' containing the logical left
377shift (toward lower indices) when ''count'' ≥ 0 or the right shift (toward upper
378indices) when ''count'' < 0. Newly vacated elements are filled with ''bit''.
379
380<procedure>(bitvector-count bit bvec)</procedure>
381
382Returns the number of ''bit'' values in ''bvec''.
383
384<procedure>(bitvector-count-run bit bvec i)</procedure>
385
386Returns the number of consecutive ''bit'' values in ''bvec'', starting at
387index ''i''.
388
389<procedure>(bitvector-if if-bitvector then-bitvector else-bitvector)</procedure>
390
391Returns a bitvector that merges the bitvectors ''then-bitvector'' and ''else-
392bitvector'', with the bitvector ''if-bitvector'' determining from which bitvector
393to take each value. That is, if the ''k''th value of ''if-bitvector'' is {{#t}} (or
3941, depending in how you look at it), then the ''k''th bit of the result is the
395''k''th bit of ''then-bitvector'', otherwise the ''k''th bit of ''else-bitvector''.
396
397<procedure>(bitvector-first-bit bit bvec)</procedure>
398
399Returns the index of the first (smallest index) ''bit'' value in ''bvec''.
400Returns -1 if ''bvec'' contains no values equal to ''bit''.
401
402=== Bit field operations
403
404These procedures operate on a contiguous field of bits (a "byte" in Common
405Lisp parlance) in a given bitvector. The ''start'' and ''end'' arguments, which
406are not optional, are non-negative exact integers specifying the field: it is
407the ''end'' − ''start'' bits running from bit ''start'' to bit ''end'' − 1.
408
409<procedure>(bitvector-field-any? bvec start end)</procedure>
410
411Returns {{#t}} if any of the field's bits are set in ''bvec'', and {{#f}} otherwise.
412
413<procedure>(bitvector-field-every? bvec start end)</procedure>
414
415Returns {{#f}} if any of the field's bits are not set in ''bvec'', and {{#t}}
416otherwise.
417
418<procedure>(bitvector-field-clear bvec start end)</procedure>
419<procedure>(bitvector-field-clear! bvec start end)</procedure>
420<procedure>(bitvector-field-set bvec start end)</procedure>
421<procedure>(bitvector-field-set! bvec start end)</procedure>
422
423Returns a bitvector containing ''bvec'' with the field's bits set appropriately.
424
425<procedure>(bitvector-field-replace dest source start end)</procedure>
426<procedure>(bitvector-field-replace! dest source start end)</procedure>
427
428Returns a bitvector containing ''dest'' with the field replaced by the first
429''end-start'' bits in ''source''.
430
431<procedure>(bitvector-field-replace-same dest source start end)</procedure>
432<procedure>(bitvector-field-replace-same! dest source start end)</procedure>
433
434Returns a bitvector containing ''dest'' with its field replaced by the
435corresponding field in ''source''.
436
437<procedure>(bitvector-field-rotate bvec count start end)</procedure>
438
439Returns ''bvec'' with the field cyclically permuted by ''count'' bits towards
440higher indices when ''count'' is negative, and toward lower indices otherwise.
441
442<procedure>(bitvector-field-flip bvec start end)</procedure>
443<procedure>(bitvector-field-flip! bvec start end)</procedure>
444
445Returns ''bvec'' with the bits in the field flipped: that is, each value is
446replaced by the opposite value. There is no SRFI 151 equivalent.
447
448== About This Egg
449
450=== Dependencies
451
452The [[srfi-160]], [[srfi-141], and [[srfi-151]] eggs are required.
453
454=== Maintainer
455
456Wolfgang Corcoran-Mathe <wcm at sigwinch dot xyzzy without the zy>
457
458=== Repository
459
460[[https://github.com/Zipheir/srfi-178-chicken|GitHub]]
461
462=== Version History
463
464; 0.1 : Initial release.
465
466== License
467
468(C) 2018 John Cowan, 2020 Wolfgang Corcoran-Mathe
469
470Permission is hereby granted, free of charge, to any person obtaining a copy
471of this software and associated documentation files (the "Software"), to deal
472in the Software without restriction, including without limitation the rights
473to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
474copies of the Software, and to permit persons to whom the Software is
475furnished to do so, subject to the following conditions:
476
477The above copyright notice and this permission notice (including the next
478paragraph) shall be included in all copies or substantial portions of the
479Software.
480
481THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
482IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
483FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
484AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
485LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
486OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
487SOFTWARE.
Note: See TracBrowser for help on using the repository browser.