For Development HEAD DRAFTSearch (procedure/syntax/module):

Next: , Previous: , Up: Library modules - Gauche extensions   [Contents][Index]

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

Module: gauche.bitvector

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.

Constructors

Function: bitvector-unfold f length seed …
Function: bitvector-unfold-right f length seed …

[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).

Function: bitvector-reverse-copy bv :optional start end

[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
Function: bitvector-append bv …

[SRFI-178] {gauche.bitvector} All arguments must be bytevectors. Returns a fresh bytevector which is concatenation of all arguments.

Function: bitvector-concatenate bvs

[SRFI-178] {gauche.bitvector} The argument must be a list of bitvectors. Returns a fresh bytevector which is concatenation of all bitvectors.

Function: bitvector-append-subbitvectors bv start end …

[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

Predicates

Function: bitvector-emtpy? bv

[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.

Function: bitvector=? bv …

[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.

Iteration

Function: bitvector-take bv n
Function: bitvector-take-right bv n

[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.

Function: bitvector-drop bv n
Function: bitvector-drop-right bv n

[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.

Function: bitvector-segment bv n

[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.

Function: bitvector-fold/int kons knil bv1 bv2 …
Function: bitvector-fold/bool kons knil bv1 bv2 …
Function: bitvector-fold-right/int kons knil bv1 bv2 …
Function: bitvector-fold-right/bool kons knil bv1 bv2 …

[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.

Function: bitvector-map/int f bv1 bv2 …
Function: bitvector-map/bool f bv1 bv2 …

[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.

All bitvectors must have the same length; otherwise, an error is thrown.

Function: bitvector-map!/int f bv1 bv2 …
Function: bitvector-map!/bool f bv1 bv2 …

[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.

All bitvectors must have the same length; otherwise, an error is thrown.

Function: bitvector-map->list/int f bv1 bv2 …
Function: bitvector-map->list/bool f bv1 bv2 …

[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.

Function: bitvector-value-map-index->list f val bv

{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.

Function: bitvector-for-each/int f bv1 bv2 …
Function: bitvector-for-each/bool f bv1 bv2 …

[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.

Function: bitvector-value-for-each-index f val bv

{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.

Prefixes, suffixes, trimming and padding

Function: bitvector-prefix-length bv1 bv2
Function: bitvector-suffix-length bv1 bv2

[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
Function: bitvector-prefix? needle haystack
Function: bitvector-suffix? needle haystack

[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
Function: bitvector-pad bit bv len
Function: bitvector-pad-right bit bv len

[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 equal to or greater than len, bv is returned as is.

(bitvector-pad 1 #*00010 10) ⇒ #*1111100010
(bitvector-pad-right 1 #*00010 10) ⇒ #*0001011111
Function: bitvector-trim bit bv
Function: bitvector-trim-right bit bv
Function: bitvector-trim-both bit bv

[SRFI-178] {gauche.bitvector} Returns a 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

Mutators

Function: bitvector-swap! bv i j

[SRFI-178] {gauche.bitvector} Swap the i-th value and j-th value of a bitvector bv. If the index is out of range, an error is thrown.

Function: bitvector-reverse! bv :optional start end

[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.

Function: bitvector-reverse-copy! to tstart from :optional start end

[SRFI-178] {gauche.bitvector} Same as (bitvector-copy! to start (bitvector-reverse-copy from start end)), but potentially more efficient.

Conversion

Function: bitvector->list/int bv :optional start end
Function: bitvector->list/bool bv :optional start end
Function: reverse-bitvector->list/int bv :optional start end
Function: reverse-bitvector->list/bool bv :optional start end

[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.

Function: reverse-list->bitvector lis

[SRFI-178] {gauche.bitvector} Like list->bitvector (see Bitvectors), but pack bits from right to left.

Function: bitvector->vector/int bv :optional start end
Function: bitvector->vector/bool bv :optional start end
Function: revrese-bitvector->vector/int bv :optional start end
Function: reverse-bitvector->vector/bool bv :optional start end

[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.

Function: vector->bitvetor vec :optional start end
Function: reverse-vector->bitvector vec :optional start end

[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.

Function: bitvector->integer bv
Function: integer->bitvector n :optional len

[SRFI-178] {gauche.bitvector} Convert between bitvectors and integers. Note that the first 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).

Generators

Function: bitvector->int-generator bv :optional start end
Function: bitvector->bool-generator bv :optional start end

{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.

Function: make-bitvector/int-generator bv
Function: make-bitvector/bool-generator bv

[SRFI-178] {gauche.bitvector} These are same as bitvector->int-generator and bitvector->bool-generator except the optional arguments, and defined in SRFI-178.

Function: bitvector->index-generator bv val :optional start end

{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)
Function: make-bitvector-accumulator

[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.

Bitwise operations

Function: bitvector-not bv
Function: bitvector-not! bv

[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
Function: bitvector-and bv1 bv2 bv …
Function: bitvector-and! bv1 bv2 bv …
Function: bitvector-ior bv1 bv2 bv …
Function: bitvector-ior! bv1 bv2 bv …
Function: bitvector-xor bv1 bv2 bv …
Function: bitvector-xor! bv1 bv2 bv …
Function: bitvector-eqv bv1 bv2 bv …
Function: bitvector-eqv! bv1 bv2 bv …

[SRFI-178] {gauche.bitvector} Returns a bitvector whose bits are the result of logical operaion of corresponding bits of the given bitvectors. 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, if works 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)
Function: bitvector-nand bv1 bv2
Function: bitvector-nand! bv1 bv2
Function: bitvector-nor bv1 bv2
Function: bitvector-nor! bv1 bv2
Function: bitvector-andc1 bv1 bv2
Function: bitvector-andc1! bv1 bv2
Function: bitvector-andc2 bv1 bv2
Function: bitvector-andc2! bv1 bv2
Function: bitvector-orc1 bv1 bv2
Function: bitvector-orc1! bv1 bv2
Function: bitvector-orc2 bv1 bv2
Function: bitvector-orc2! bv1 bv2

[SRFI-178] {gauche.bitvector} Returns a bitvector, where each bit is the result of logical operation of corresponding bits of bv1 and bv2.

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.

Quasi-integer operations

Function: bitvector-logical-shift bv count bit

[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 vacated bits are filled with bit.

(bitvector-logical-shift #*101100111000 4 1)
  ⇒ #*001110001111
(bitvector-logical-shift #*101100111000 -4 0)
  ⇒ #*000010110011
Function: bitvector-count bit bv

[SRFI-178] {gauche.bitvector} Returns the number of bit values in bv.

Function: bitvector-count-run bit bv start

[SRFI-178] {gauche.bitvector} Returns the number of consecutive bit values in bv, starting from index i.

Function: bitvector-if bv-if bv-then bv-else

[SRFI-178] {gauche.bitvector}

Function: bitvector-first-bit bit bv

[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

Bit field operations

Those procedures operates on a partial field of a bitvector, between start-th bit (inclusive) and end-th bit (exclusive).

Function: bitvector-field-any? bv start end

[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).

Function: bitvector-field-every? bv start end

[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).

Function: bitvector-field-clear bv start end
Function: bitvector-field-clear! bv start end
Function: bitvector-field-set bv start end
Function: bitvector-field-set! bv start end

[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
Function: bitvector-field-replace to from start end
Function: bitvector-field-replace! to from start end

[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 liner-updating version may mutate to-bv to produce the result.

(bitvector-field-replace #*10010010101001 #*110011 2 8)
 ⇒ #*10110011101001

The length of from-bv must be at least end-start. If it is longer, the exceeding bits are ignored.

See also bitvector-field-replace-same below.

Function: bitvector-field-replace-same to-bv from-bv start end
Function: bitvector-field-replace-same! to-bv from-bv start end

[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 liner-updating version may mutate to-bv to produce the result.

(bitvector-field-replace-same #*10010010101001 #*11001100 2 8)
 ⇒ #*10001100101001

The length of from-bv must be greater than or equal to end.

See also bitvector-field-replace above.

Function: bitvector-field-rotate bv count start end

[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
Function: bitvector-field-flip bv start end
Function: bitvector-field-flip! bv start end

[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.

(bitvector-field-flip #*001100110011 4 8)
 ⇒ #*001111000011

Next: , Previous: , Up: Library modules - Gauche extensions   [Contents][Index]


For Development HEAD DRAFTSearch (procedure/syntax/module):
DRAFT