▼binaryio:   Functions for Reading and Writing Binary Data
On this page:
SBV-LENGTH-BITS
SBV-LENGTH-BOUND
sbv?
canonical-sbv?
make-sbv
make-be-sbv
empty-sbv
sbv-empty?
sbv-length
sbv-bits
sbv-bit-field
sbv-slice
sbv-shift
sbv-bit-set?
sbv-ref
sbv-car
sbv-cdr
sbv-append
sbv-cons
sbv-reverse
sbv-prefix?
sbv->string
string->sbv
8.12
  top  contents    up   

6 Short Bitvectors🔗ℹ

 (require binaryio/bitvector) package: binaryio-lib

Added in version 1.2 of package binaryio-lib.

A short bitvector is an immutable bitvector represented as a Racket exact nonnegative integer. The bitvector [b_0 b_1 b_2 ... b_L-1] is represented as the integer
(+ L
   (* b_0 (arithmetic-shift 1 (+ 0 SBV-LENGTH-BITS)))
   (* b_1 (arithmetic-shift 1 (+ 1 SBV-LENGTH-BITS)))
   (* b_2 (arithmetic-shift 1 (+ 2 SBV-LENGTH-BITS)))
   ...
   (* b_L-1 (arithmetic-shift 1 (+ L-1 SBV-LENGTH-BITS))))
where SBV-LENGTH-BITS is currently 16. That is, a bitvector is represented as a length field plus a shifted, nonnegative integer encoding of its contents. Note that the first bit of the bitvector corresponds to the least significant bit of the “payload” integer. This is roughly analogous to the relationship between an integer and its encoding using little-endian byte order. (See also least significant first bit order.)

Consequently, bitvectors up to about 46 bits are represented using fixnums (on 64-bit versions of Racket), and only bitvectors up to (sub1 (expt 2 SBV-LENGTH-BITS)) bits are representable.

value

SBV-LENGTH-BITS : exact-nonnegative-integer? = 16

Number of bits used to represent the length of a bitvector.

value

SBV-LENGTH-BOUND : exact-nonnegative-integer? = 65536

Bound for representable bitvector lengths. Specifically, a bitvector’s length must be strictly less than SBV-LENGTH-BOUND to be representable.

procedure

(sbv? v) → boolean?

  v : any/c
Returns #t if v represents a short bitvector, #f otherwise.

Equivalent to exact-nonnegative-integer?. See also canonical-sbv?.

procedure

(canonical-sbv? v) → boolean?

  v : any/c
Returns #t if v is a canonical representation of a short bitvector, #f otherwise.

For example, (make-sbv #b1011 2) is not canonical because it has a bit set after the first two bits.

Warning: In general, the functions in this library may produce bad results if given non-canonical bitvector values.

procedure

(make-sbv le-bits bitlength) → sbv?

  le-bits : exact-nonnegative-integer?
  bitlength : exact-nonnegative-integer?
Returns a short bitvector whose length is bitlength and whose elements are the bits representing the integer le-bits, starting with the least significant bit.

If le-bits has a bit set after the first bitlength bits, then the result is non-canonical (see canonical-sbv?). If bitlength is not less then SBV-LENGTH-BOUND, an error is raised.

Example:
> (sbv->string (make-sbv 6 3))

"011"

procedure

(make-be-sbv be-bits bitlength) → sbv?

  be-bits : exact-nonnegative-integer?
  bitlength : exact-nonnegative-integer?
Like make-sbv, but the elements of the bitvector are the bits representing the integer be-bits starting with the most significant bit (as a bitlength-bit number). This is roughly analogous to the relationship between an integer and its encoding using big-endian byte order, thus the name make-be-sbv.

Equivalent to (sbv-reverse (make-sbv be-bits bitlength)).

Example:
> (sbv->string (make-be-sbv 6 3))

"110"

value

empty-sbv : sbv? = (make-sbv 0 0)

The empty bitvector.

procedure

(sbv-empty? sbv) → boolean?

  sbv : sbv?
Returns #t if v is the empty bitvector, #f otherwise.

procedure

(sbv-length sbv) → exact-nonnegative-integer?

  sbv : sbv?
Returns the length of the bitvector.

procedure

(sbv-bits sbv) → exact-nonnegative-integer?

  sbv : sbv?
Returns the bitvector’s contents, encoded as a nonnegative integer. The first element of the bitvector corresponds to the integer’s least significant bit.

Example:
> (sbv-bits (string->sbv "1011"))

13

procedure

(sbv-bit-field sbv start end) → exact-nonnegative-integer?

  sbv : sbv?
  start : exact-nonnegative-integer?
  end : exact-nonnegative-integer?
Returns the bitvector’s contents from start (inclusive) to end (exclusive), encoded as a nonnegative integer. The element of sbv at index start corresponds to the integer’s least significant bit.

If end is greater than (sbv-length sbv), then the “out of range” bits are set to zero.

Examples:
> (sbv-bit-field (string->sbv "11100") 1 4)

3

> (sbv-bit-field (string->sbv "11100") 1 10)

3

procedure

(sbv-slice sbv start end) → sbv?

  sbv : sbv?
  start : exact-nonnegative-integer?
  end : exact-nonnegative-integer?
Returns the bitvector containing the subsequence of bits from sbv from indexes start (inclusive) to end (exclusive).

If end is greater than (sbv-length sbv), then the “out of range” bits are set to zero.

Examples:
> (sbv->string (sbv-slice (string->sbv "11100") 1 4))

"110"

> (sbv->string (sbv-slice (string->sbv "11100") 1 10))

"110000000"

procedure

(sbv-shift sbv lshift) → sbv?

  sbv : sbv?
  lshift : exact-integer?
If lshift is positive, adds lshift zero bits to the beginning of the bitvector. If lshift is negative, removes (- lshift) bits from the beginning of the bitvector.

Examples:
> (sbv->string (sbv-shift (string->sbv "11100") 3))

"00011100"

> (sbv->string (sbv-shift (string->sbv "11100") -2))

"100"

procedure

(sbv-bit-set? sbv index) → boolean?

  sbv : sbv?
  index : exact-nonnegative-integer?
Returns #t if the bit at index index of sbv is set (1), #f if it is unset (0). If index is not less than (sbv-length sbv), and sbv is canonical, then #f is returned.

Examples:
> (sbv-bit-set? (string->sbv "1101") 0)

#t

> (sbv-bit-set? (string->sbv "1101") 1)

#t

> (sbv-bit-set? (string->sbv "1101") 2)

#f

procedure

(sbv-ref sbv index) → (or/c 0 1)

  sbv : sbv?
  index : exact-nonnegative-integer?
Like sbv-bit-set?, but returns the bit at the given index.

Examples:
> (sbv-ref (string->sbv "1101") 0)

1

> (sbv-ref (string->sbv "1101") 1)

1

> (sbv-ref (string->sbv "1101") 2)

0

procedure

(sbv-car sbv) → (or/c 0 1)

  sbv : sbv?

procedure

(sbv-cdr sbv) → sbv?

  sbv : sbv?
Returns the first bit of the bitvector and the rest of the bitvector, respectively.

Equivalent to (sbv-ref sbv 0) and (sbv-shift sbv -1).

Examples:
> (sbv-car (string->sbv "110"))

1

> (sbv->string (sbv-cdr (string->sbv "110")))

"10"

procedure

(sbv-append sbv ...) → sbv?

  sbv : sbv?
Returns the concatenation of the given bitvectors.

Example:
> (sbv->string (sbv-append (string->sbv "1011") (string->sbv "00")))

"101100"

procedure

(sbv-cons bit sbv) → sbv?

  bit : (or/c 0 1)
  sbv : sbv?
Adds a bit to the beginning of the bitvector.

Equivalent to (sbv-append (make-sbv bit 1) sbv).

procedure

(sbv-reverse sbv) → sbv?

  sbv : sbv?
Reverses the bits of the bitvector.

Example:
> (sbv->string (sbv-reverse (string->sbv "1101")))

"1011"

procedure

(sbv-prefix? sbv1 sbv2) → boolean?

  sbv1 : sbv?
  sbv2 : sbv?
Returns #t if sbv1 is a prefix of sbv2.

Examples:
> (sbv-prefix? (string->sbv "110") (string->sbv "110"))

#t

> (sbv-prefix? (string->sbv "110") (string->sbv "1100"))

#t

> (sbv-prefix? (string->sbv "110") (string->sbv "100110"))

#f

> (sbv-prefix? (string->sbv "110") (string->sbv "11"))

#f

procedure

(sbv->string sbv) → string?

  sbv : sbv?
Returns a string of 0 and 1 characters representing the bits of sbv.

Example:
> (sbv->string (sbv-append (make-sbv 1 1) (make-sbv 1 1) (make-sbv 0 1)))

"110"

If sbv is canonical, then sbv is equal to

(make-be-sbv (string->number (sbv->string sbv) 2) (sbv-length sbv))

procedure

(string->sbv s) → sbv?

  s : (and/c string? #rx"^[01]*$")
Parses s, which should consist of 0 and 1 characters, and returns the corresponding bitvector.

  top  contents    up