package bitv

  1. Overview
  2. Docs
A bit vector library for OCaml

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (6)

Authors

  1. J
    Jean-Christophe Filliâtre

Maintainers

  1. F
    filliatr@lri.fr

Sources

bitv-1.5.tbz
sha256=17f57fa726dcb92f146442884e2a69f3e5515fc1fd7318f0eee920cf65bfc64c
sha512=b04b145983e675ed6f5be7ed11017abc2e2188e81df26ac3d77922898db06a9c9540269da055fc49cc5b9f015b85a719156e1ec5997b31f0f775ae5bf7178081

doc/bitv/Bitv/index.html

Module BitvSource

This module implements bit vectors, as an abstract datatype t. Since bit vectors are particular cases of arrays, this module provides the same operations as module Array. It also provides bitwise operations and conversions to/from integer types.

In the following, false stands for bit 0 and true for bit 1.

Sourcetype t

the type of bit vectors

Creation, access and assignment.

Sourceval create : int -> bool -> t

(Bitv.create n b) creates a new bit vector of length n, initialized with b.

Sourceval init : int -> (int -> bool) -> t

(Bitv.init n f) returns a fresh vector of length n, with bit number i initialized to the result of (f i).

Sourceval set : t -> int -> bool -> unit

(Bitv.set v n b) sets the nth bit of v to the value b.

Sourceval get : t -> int -> bool

(Bitv.get v n) returns the nth bit of v.

Sourceval length : t -> int

Bitv.length returns the length (number of elements) of the given vector.

Sourceval max_length : int

max_length is the maximum length of a bit vector (System dependent).

Copies and concatenations.

Sourceval copy : t -> t

(Bitv.copy v) returns a copy of v, that is, a fresh vector containing the same elements as v.

Sourceval append : t -> t -> t

(Bitv.append v1 v2) returns a fresh vector containing the concatenation of the vectors v1 and v2.

Sourceval concat : t list -> t

Bitv.concat is similar to Bitv.append, but catenates a list of vectors.

Sub-vectors and filling.

Sourceval sub : t -> int -> int -> t

(Bitv.sub v start len) returns a fresh vector of length len, containing the bits number start to start + len - 1 of vector v. Raise Invalid_argument "Bitv.sub" if start and len do not designate a valid subvector of v; that is, if start < 0, or len < 0, or start + len > Bitv.length a.

Sourceval fill : t -> int -> int -> bool -> unit

(Bitv.fill v ofs len b) modifies the vector v in place, storing b in elements number ofs to ofs + len - 1. Raise Invalid_argument "Bitv.fill" if ofs and len do not designate a valid subvector of v.

Sourceval blit : t -> int -> t -> int -> int -> unit

(Bitv.blit v1 o1 v2 o2 len) copies len elements from vector v1, starting at element number o1, to vector v2, starting at element number o2. It does not work correctly if v1 and v2 are the same vector with the source and destination chunks overlapping. Raise Invalid_argument "Bitv.blit" if o1 and len do not designate a valid subvector of v1, or if o2 and len do not designate a valid subvector of v2.

Iterators

Sourceval iter : (bool -> unit) -> t -> unit

(Bitv.iter f v) applies function f in turn to all the elements of v.

Sourceval map : (bool -> bool) -> t -> t

Given a function f, (Bitv.map f v) applies f to all the elements of v, and builds a vector with the results returned by f.

Sourceval iteri : (int -> bool -> unit) -> t -> unit
Sourceval mapi : (int -> bool -> bool) -> t -> t

Bitv.iteri and Bitv.mapi are similar to Bitv.iter and Bitv.map respectively, but the function is applied to the index of the element as first argument, and the element itself as second argument.

Sourceval fold_left : ('a -> bool -> 'a) -> 'a -> t -> 'a

(Bitv.fold_left f x v) computes f (... (f (f x (get v 0)) (get v 1)) ...) (get v (n-1)), where n is the length of the vector v.

Sourceval fold_right : (bool -> 'a -> 'a) -> t -> 'a -> 'a

(Bitv.fold_right f a x) computes f (get v 0) (f (get v 1) ( ... (f (get v (n-1)) x) ...)), where n is the length of the vector v.

Sourceval foldi_left : ('a -> int -> bool -> 'a) -> 'a -> t -> 'a
Sourceval foldi_right : (int -> bool -> 'a -> 'a) -> t -> 'a -> 'a

Pop count and other iterations

Sourceval pop : t -> int

Population count, i.e., number of 1 bits

Sourceval iteri_true : (int -> unit) -> t -> unit

iteri_true f v applies function f in turn to all indexes of the elements of v which are set (i.e. true); indexes are visited from least significant to most significant.

Sourceval gray_iter : (t -> unit) -> int -> unit

gray_iter f n iterates function f on all bit vectors of length n, once each, using a Gray code. The order in which bit vectors are processed is unspecified.

Bitwise operations.

All the bitwise operations return fresh vectors.

Sourceval bw_and : t -> t -> t

bitwise AND; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_or : t -> t -> t

bitwise OR; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_xor : t -> t -> t

bitwise XOR; raises Invalid_argument if the two vectors do not have the same length

Sourceval bw_not : t -> t

bitwise NOT

Sourceval shiftl : t -> int -> t

moves bits from least to most significant; introduces zeros

Sourceval shiftr : t -> int -> t

moves bits from most to least significant; introduces zeros

Sourceval rotatel : t -> int -> t

moves bits from least to most significant with wraparound

Sourceval rotater : t -> int -> t

moves bits from most to least significant with wraparound

Test functions

Sourceval all_zeros : t -> bool

returns true if and only if the vector only contains zeros

Sourceval all_ones : t -> bool

returns true if and only if the vector only contains ones

Conversions to and from strings

Sourcemodule L : sig ... end

With least significant bits first.

Sourcemodule M : sig ... end

With most significant bits first.

Input/output in a machine-independent format

The following functions export/import a bit vector to/from a channel or bytes, in a way that is compact, independent of the machine architecture, and independent of the OCaml version. For a bit vector of length n, the number of bytes of this external representation is 4+ceil(n/8) on a 32-bit machine and 8+ceil(n/8) on a 64-bit machine.

Sourceval output_bin : out_channel -> t -> unit
Sourceval input_bin : in_channel -> t
Sourceval to_bytes : t -> bytes
Sourceval of_bytes : bytes -> t

Conversions to and from lists of integers

The list gives the indices of bits which are set (ie true).

Sourceval to_list : t -> int list
Sourceval of_list : int list -> t
Sourceval of_list_with_length : int list -> int -> t

Interpretation of bit vectors as integers

Least significant bit comes first (ie is at index 0 in the bit vector). to_xxx functions truncate when the bit vector is too wide, and raise Invalid_argument when it is too short. Suffix _s means that sign bit is kept, and _us that it is discarded.

type int (length 31/63 with sign, 30/62 without)

Sourceval of_int_s : int -> t
Sourceval to_int_s : t -> int
Sourceval of_int_us : int -> t
Sourceval to_int_us : t -> int

type Int32.t (length 32 with sign, 31 without)

Sourceval of_int32_s : Int32.t -> t
Sourceval to_int32_s : t -> Int32.t
Sourceval of_int32_us : Int32.t -> t
Sourceval to_int32_us : t -> Int32.t

type Int64.t (length 64 with sign, 63 without)

Sourceval of_int64_s : Int64.t -> t
Sourceval to_int64_s : t -> Int64.t
Sourceval of_int64_us : Int64.t -> t
Sourceval to_int64_us : t -> Int64.t

type Nativeint.t (length 32/64 with sign, 31/63 without)

Sourceval of_nativeint_s : Nativeint.t -> t
Sourceval to_nativeint_s : t -> Nativeint.t
Sourceval of_nativeint_us : Nativeint.t -> t
Sourceval to_nativeint_us : t -> Nativeint.t

Only if you know what you are doing...

Sourceval unsafe_set : t -> int -> bool -> unit
Sourceval unsafe_get : t -> int -> bool