gauche.bitvector - Bitvector utilities ¶This module adds more operations on bitvectors.
This module and built-in bitvector procedures covers SRFI-178
Bitvector library interface (see srfi.178 - Bitvector library)
Gauche supports bitvectors as a native type, but the core library only offers a handful of primitives (see Bitvectors). This module provides the comprehensive operations on bitvectors.
[SRFI-178]{gauche.bitvector}
Creates a bitvector of length length, and fill its contents by
repeatedly applying f. The procedure f must take one more
than the number of seeds, and must return the same number
of values. First, f is applied to the index and seed …,
then its first return value (which must be a bit, i.e. 0, 1 or a boolean
value) is used to initialize the index-th element of the bitvector,
and the rest of the return value is used as the next argument to f.
It is repeated length times.
While bitvector-unfold fills the bits from left to right,
bitvector-unfold-right does from right to left.
(use math.prime)
(bitvector-unfold (^[index n]
(values (small-prime? n) (+ n 1)))
20 0)
⇒ #*00110101000101000101
(bitvector-unfold-right (^[index n]
(values (small-prime? n) (+ n 1)))
20 0)
⇒ #*10100010100010101100
Note: This procedure follows the protocol of vector-unfold
(see scheme.vector - R7RS vectors), and has a different protocol from other
unfold procedures (see scheme.list - R7RS lists).
[SRFI-178]{gauche.bitvector}
Copies a bitvector bv in reverse order. Optional start
and end arguments limits the range of the input.
(bitvector-reverse-copy #*10110011100011110000 4 16) ⇒ #*111100011100
[SRFI-178]{gauche.bitvector}
All arguments must be bytevectors. Returns a fresh bytevector
which is concatenation of all arguments.
[SRFI-178]{gauche.bitvector}
The argument must be a list of bitvectors. Returns a fresh bytevector
which is concatenation of all bitvectors.
[SRFI-178]{gauche.bitvector}
The number of arguments must be a multiple of 3. Each triplet of
the arguments is a bytevector followed by start and end index,
specifying the input bytevector range. Returns a fresh bytevector
which is concatenation of all the subvectors.
(bitvector-append-subbitvectors #*11100011 2 6 #*01010101 3 8) ⇒ #*100010101
[SRFI-178]{gauche.bitvector}
Returns #t if bv is an empty bytevector,
#f if it is a non-empty bitvector.
An error is thrown if bv is not a bitvector.
[SRFI-178]{gauche.bitvector}
All arguments must be bitvectors.
Returns #t iff all the bitvectors have the same length and content.
If there’s zero or one argument, it returns #t.
[SRFI-178]{gauche.bitvector}
Returns a new bitvector with the first/last n bits of a bitvector bv.
An error is thrown if length of bv is less than n.
In Gauche, you can also use generic (subseq bv 0 n) to take the
first n bits. See gauche.sequence - Sequence framework.
[SRFI-178]{gauche.bitvector}
Returns a new bitvector with bits except first/last n bits of
a bitvector bv.
An error is thrown if length of bv is less than n.
In Gauche, you can also use generic (subseq bv n)
to drop the first n bits. See gauche.sequence - Sequence framework.
[SRFI-178]{gauche.bitvector}
Slices a bitvector bv with n-bits each, and returns
a list of bitvectors. If the length of bv isn’t a multiple
of n, the last bitvector may be shorter.
[SRFI-178]{gauche.bitvector}
Fold kons over the elements of bitvectors with knil as
the initial state value.
The kons procedure is always called as
(kons state e1 e2 …), where e1 e2 …
are elements from each bitvectors, as integer 0/1 (for /int procdures)
or boolean #f/#t (for /bool procedures).
This is the same order as vector-fold in
scheme.vector module (see scheme.vector - R7RS vectors).
(Note that list fold procedure calls the kons procedure
with different order; see Walking over lists).
All bitvectors must have the same length; otherwise, an error is thrown.
[SRFI-178]{gauche.bitvector}
Apply a procedure f over each element taken from given bitvectors.
The result of the procedure is gathered as a fresh bitvector and returned.
(bitvector-map/int logand #*10101 #*00111) ⇒ #*00101
All bitvectors must have the same length; otherwise, an error is thrown.
[SRFI-178]{gauche.bitvector}
Apply a procedure f over each element taken from given bitvectors.
The result of the procedure is set into bv1.
These procedure returns undefined value; you should count on the side effect onto bv1. In other words, they are not linear-updating procedures.
All bitvectors must have the same length; otherwise, an error is thrown.
[SRFI-178]{gauche.bitvector}
Apply a procedure f over each element taken from given bitvectors.
The result of the procedure is gathered as a list and returned.
All bitvectors must have the same length; otherwise, an error is thrown.
{gauche.bitvector}
Apply a procedure f over each index such that the index-th element
of bv is val, which must be either a boolean value or 0
or 1. The result of applications are gathered into a list,
from smaller index.
For example, the following returns a list of indices where the bit is true.
(bitvector-value-map-index->list identity #*10011 #t) ⇒ (0 3 4)
[SRFI-178]{gauche.bitvector}
Apply a procedure f over each element taken from given bitvectors.
The result of the procedure is discarded.
All bitvectors must have the same length; otherwise, an error is thrown.
(bitvector-for-each/int print #*11100 #*01110 #00111)
⇒ prints
100
110
111
011
001
{gauche.bitvector}
Apply a procedure f over each index such that the index-th element
of bv is val, which must be either a boolean value or 0
or 1. The result of f is discarded.
(bitvector-value-for-each-index print #*1101111010 #f)
⇒ prints
2
7
9
See also bitvector-value-map-index->list above.
[SRFI-178]{gauche.bitvector}
Returns the length of common prefix/suffix of two bitvectors
bv1 and bv2.
(bitvector-prefix-length #*1100101001 #*110001101) ⇒ 4 (bitvector-suffix-length #*1100101001 #*110001101) ⇒ 2
[SRFI-178]{gauche.bitvector}
Both arguments must be bitvectors. Returns #t
iff needle is a prefix/suffix of haystack.
(bitvector-prefix? #*101 #*1010100) ⇒ #t (bitvector-prefix? #*101 #*1000110) ⇒ #f (bitvector-suffix? #*110 #*1000110) ⇒ #t (bitvector-suffix? #*110 #*1010100) ⇒ #f
[SRFI-178]{gauche.bitvector}
If the length of a bitvector bv is smaller than len,
returns a bitvector of length len by adding bit before/after
bv. If the length of bv is greater than len,
returns a bitvector of length len such that
bv left/right bits of bv are trimmed.
If the length of bv is equal to len,
a copy of bv is returned as is.
(bitvector-pad 1 #*00010 10) ⇒ #*1111100010 (bitvector-pad-right 1 #*00010 10) ⇒ #*0001011111 (bitvector-pad 1 #*0100011 3) ⇒ #*011 (bitvector-pad-right 1 #*0100011 3) ⇒ #*010
[SRFI-178]{gauche.bitvector}
Returns a fresh bitvector without preceding and/or trailing consecutive
bit from bv.
(bitvector-trim 0 #*000101000) ⇒ #*101000 (bitvector-trim-right 0 #*000101000) ⇒ #*000101 (bitvector-trim-both 0 #*000101000) ⇒ #*101
[SRFI-178]{gauche.bitvector}
Swap the i-th value and j-th value of a bitvector bv.
Returns an undefined value.
If the index is out of range, an error is thrown.
[SRFI-178]{gauche.bitvector}
Reverse the order of the content of a bitvector bv destructively.
The optional start/end indexes limit the range of the operation;
elements outside of the range won’t be affected.
Returns an undefined value.
[SRFI-178]{gauche.bitvector}
Same as (bitvector-copy! to start (bitvector-reverse-copy from start end)),
but potentially more efficient.
Returns an undefined value.
[SRFI-178]{gauche.bitvector}
Returns a list of integers (0 or 1) or boolean values of bitvector
bv. The first two procedures returns the leftmost bit first,
while the reverse- variations returns the rightmost bit first.
The optional start/end arguments limit the range of bv
to be extracted.
(bitvector->list/int #*010011000111 2 10) ⇒ (0 0 1 1 0 0 0 1) (reverse-bitvector->list/int #*010011000111 2 10) ⇒ (1 0 0 0 1 1 0 0)
[SRFI-178]{gauche.bitvector}
Like list->bitvector (see Bitvectors), but pack bits
from right to left.
(reverse-list->bitvector '(1 0 #f #f #t #t)) ⇒ #*110001
[SRFI-178]{gauche.bitvector}
Returns a vector of integers (0 or 1) or boolean values of
bitvector bv. The first two procedures returns the leftmost bit first,
while the reverse- variations returns the rightmost bit first.
The optional start/end arguments limit the range of bv
to be extracted.
[SRFI-178]{gauche.bitvector}
Converts vec to a fresh bitvector;
vec must be a vector of 0/1 or boolean values.
The first procedure packs bits in the same left to right order,
while the reverse- version reverses the order.
The optional start/end arguments limit the range of vec
to be extracted.
(vector->bitvector #(0 0 1 1 #t #f #t #t) 2 7) ⇒ #*11101 (reverse-vector->bitvector #(0 0 1 1 #t #f #t #t) 2 7) ⇒ #*10111
[SRFI-178]{gauche.bitvector}
Convert between bitvectors and exact nonnegative integers.
Note that the leftmost bit of
bv corresponds to the least significant bit.
(bitvector->integer #*1000) ⇒ 1 (bitvector->integer #*0001) ⇒ 8
This is consistent with bits->list etc. of SRFI-151
(see scheme.bitwise - R7RS bitwise operations), where least significant bit
corresponts to the first element of the list.
integer->bitvector takes an optional argument len to
specify the number of bits in n (count from the least siginificant
bit) to be taken. When omitted, (integer-length n) is used
(see Basic bitwise operations).
(integer->bitvector 11) ⇒ #*1101 (integer->bitvector 11 8) ⇒ #*11010000
{gauche.bitvector}
Returns a generator of integers (0 or 1) and boolean values, respectively.
The value is taken from a bitvector bv from left to right.
The optional start/end arguments limits the range of
the bitvector to be used.
(generator->list (bitvector->int-generator #*10111000)) ⇒ (1 0 1 1 1 0 0 0)
The names are consistent with Gauche convention.
SRFI-178 defines these procedures with the name
make-bitvector/int-generator and make-bitvector/bool-generator.
See gauche.generator - Generators, for the details of generators.
[SRFI-178]{gauche.bitvector}
These are same as bitvector->int-generator and
bitvector->bool-generator except the optional arguments,
and defined in SRFI-178.
{gauche.bitvector}
Returns a generator that generates indexes of bv such that
the index-th value of bv matches val, which must
be either 0, 1 or a boolean value. The bitvector is scanned from
left to right.
The optional start/end arguments limits the range of
the bitvector to be used.
This is handy when you have a bitvector as a bitmap, and want to process something where bit is set (or reset).
(generator->list (bitvector->index-generator #*101110001 1)) ⇒ (0 2 3 4 8)
[SRFI-178]{gauche.bitvector}
Returns an accumulator that collects given bits, and returns
a bitvector at the end of accumulation.
(let ((a (make-bitvector-accumulator))) (a 1) (a 0) (a 0) (a 1) (a 1) (a (eof-object))) ⇒ #*10011
See scheme.generator - R7RS generators, for the details of accumulators.
[SRFI-178]{gauche.bitvector}
Returns a bitvector whose bits are logical negation of bv.
The linear updating version bitvector-not! may reuse bv to
produce the result.
(bitvector-not #*10100) ⇒ #*01011
[SRFI-178]{gauche.bitvector}
Returns a bitvector whose bits are the result of logical operaion of
corresponding bits of the given bitvectors. All bitvectors must be
the same length.
The linear updating version (procedures with !) may reuse bv1 to
produce the result.
When more than two bitvectors are given to xor and eqv operation, it works left-associatively, that is,
(bitvector-xor a b c) ≡ (bitvector-xor (bitvector-xor a b) c) (bitvector-eqv a b c) ≡ (bitvector-eqv (bitvector-eqv a b) c)
[SRFI-178]{gauche.bitvector}
Returns a bitvector, where each bit is the result of
logical operation of corresponding bits of bv1 and bv2.
Two bitvectors must be the same length.
nand : (not (and bv1 bv2)) nor : (not (or bv1 bv2) andc1 : (and (not bv1) bv2) andc2 : (and bv1 (not bv2)) orc1 : (or (not bv1) bv2) orc2 : (or bv1 (not bv2))
The linear updating version (procedures with !) may reuse bv1 to
produce the result.
[SRFI-178]{gauche.bitvector}
Returns a bitvector with the same length of bv, but the
content is shifted count bits to the left (when count >= 0)
or -count bits to the right (when count < 0).
The spilled bits are discarded.
The vacated bits are filled with bit.
(bitvector-logical-shift #*101100111000 4 1) ⇒ #*001110001111 (bitvector-logical-shift #*101100111000 -4 0) ⇒ #*000010110011
[SRFI-178]{gauche.bitvector}
Returns the number of bit values in bv.
[SRFI-178]{gauche.bitvector}
Returns the number of consecutive bit values in bv, starting
from index i.
(bitvector-count-run 1 #*11111111100 0) ⇒ 9
[SRFI-178]{gauche.bitvector}
All bitvectors must be the same length.
Returns a new bitvector with the same length, composed as follows.
The k-th bit of resulting vector is the same as k-th bit
of bv-then if k-th bit of bv-if is #t (1),
otherwise the same as k-th bit of bv-else
[SRFI-178]{gauche.bitvector}
Returns the index of the leftmost bit in bv.
If bv doesn’t have bit, returns -1.
(bitvector-first-bit 1 #*0010011) ⇒ 2 (bitvector-first-bit 0 #*1111111) ⇒ -1
Those procedures operates on a partial field of a bitvector, between start-th bit (inclusive) and end-th bit (exclusive).
[SRFI-178]{gauche.bitvector}
Returns #t iff at least one bit between start and end
in bv is 1.
This is equivalent to (bitvector-any-value? bv 1 start end),
using Gauche’s built-in procedure (see Bitvectors).
[SRFI-178]{gauche.bitvector}
Returns #t iff every bit between start and end
in bv is 1.
This is equivalent to (bitvector-every-value? bv 1 start end),
using Gauche’s built-in procedure (see Bitvectors).
[SRFI-178]{gauche.bitvector}
Returns a bitvector with the same content as bv, except
the bits between start (inclusive) and end (exclusive)
are cleared or set, respectively.
The liner-updating version may mutate bv to produce the result.
(bitvector-field-clear #*10010010101001 2 7) ⇒ #*10000000101001 (bitvector-field-set #*10010010101001 2 7) ⇒ #*10111110101001
[SRFI-178]{gauche.bitvector}
Returns a bitvector with the same content as to-bv, except
its bits between start (inclusive) and end (exclusive)
are replaced with the content of from-bv.
The length of from-bv must be at least end-start. If it is longer, the exceeding bits are ignored.
The liner-updating version may mutate to-bv to produce the result.
(bitvector-field-replace #*10010010101001 #*110011 2 8) ⇒ #*10110011101001
See also bitvector-field-replace-same below.
[SRFI-178]{gauche.bitvector}
Returns a bitvector with the same content as to-bv, except
its bits between start (inclusive) and end (exclusive)
are replaced with the content of from-bv between start and
end.
The length of from-bv must be greater than or equal to end.
The liner-updating version may mutate to-bv to produce the result.
(bitvector-field-replace-same #*10010010101001 #*11001100 2 8) ⇒ #*10001100101001
See also bitvector-field-replace above.
[SRFI-178]{gauche.bitvector}
Returns a bitvector whose content is the same as bv except
the range between start-th bit (inclusive) and
end-th bit (exclusive) being rotated by count bits toward
right. You can give a negative count to rotate towards left.
(bitvector-field-rotate #*001100110011 1 4 8) ⇒ #*001101100011 (bitvector-field-rotate #*001100110011 -1 4 8) ⇒ #*001110010011
[SRFI-178]{gauche.bitvector}
Returns a bitvector whose content is the same as bv
except the bits in the range
between start-th bit (inclusive) and
end-th bit (exclusive) are inverted.
The liner-updating version may mutate to-bv to produce the result.
(bitvector-field-flip #*001100110011 4 8) ⇒ #*001111000011