# bv

Bit-vector arithmetic library https://github.com/iagoabal/haskell-bv

LTS Haskell 11.6: | 0.5 |

Stackage Nightly 2018-04-27: | 0.5 |

Latest on Hackage: | 0.5 |

**Iago Abal**

#### Module documentation for 0.5

- Data

# A library for bit-vector arithmetic in Haskell

Bit-vectors are represented as a pair of a *size* and a *value*,
where sizes are of type *Int* and values are *Integer*.
Operations on bit-vectors are translated into operations on integers.
Remarkably, most operations taking two or more bit-vectors, will
perform zero-padding to adjust the size of the input bit-vectors
when needed (eg. when adding bit-vectors of different sizes).
Indexing operators don't do this, to avoid masking *out of bounds*
errors.

## Other libraries

There exist many Haskell libraries to handle bit-vectors, but to the
best of my knowledge *bv* is the only one that adequately supports
bit-vector arithmetic.

If you do not need bit-vector arithmetic, then you may consider using any of these other libraries, which could offer more compact and efficient implementations of bit arrays.

## Importing and name clashes

Many exported functions name-clash with Prelude functions, it is therefore recommended to do a qualified import:

```
import Data.BitVector ( BV )
import qualified Data.BitVector as BV
```

## Running the test suite

If you wish to run the test suite simply:

```
cabal configure -ftest
cabal build
```

Then run:

`dist/build/bv-tester/bv-tester`

## Performance

**Tip:** For best performance compile with *-fgmp*.

**Tip:** If you are brave enough, compile with *-f -check-bounds* (disables index bounds checking).

The *BV* datatype is simply a pair of an *Int*, to represent the
*size*, and an arbitrary-precision *Integer*, to represent the
*value* of a bit-vector.
Both fields are strict, and we instruct GHC to unbox strict fields.
Further, we ask GHC to inline virtually all bit-vector operations.
When inlined, GHC should be able to remove any overhead associated
with the *BV* data type, and unbox bit-vector sizes.
Performance should depend mostly on the *Integer* data type
implementation.

## Changes

# 0.5.0

Note that changes in `fromInteger`

and `toInteger`

implementations break backwards compatibility.
I hope this will not cause major problems, let me know otherwise.

- Make
*bv*with compatible with GHC 8.4.1 (*base*4.11). Thanks to Kosyrev Serge! - Define
`toInteger`

as`int`

rather than`nat`

. - Make
`fromInteger`

consistent and always encode in two's complement, also positive integers. - As a result of the two previous changes, now
`toInteger . fromInteger == id`

, as it should be. - Add
`Read BV`

instance (based on`Text.Read`

, so GHC-only). - Fix a few bugs in the non-GMP implementation. (Fortunately, GMP is the default.)
- Remove upper bounds on testing dependencies.

# 0.4.1

Another maintenance release:

- Fix compilation error with GHC 8.0.1.
- Add `check-bounds' flag so the user decides whether to perform bounds checking.

# 0.4.0

This is a maintenance release, but it introduces changes to the API that required a new major version. In summary, I have fixed a few bugs, optimized a few functions, and added a few more properties (tests). Apart from that, and the usual clean up, there are also a handful of new API functions that I judged useful.

For performance reasons, this release introduces GMP specific optimizations.
The GMP-based backend is automatically used if available, unless *-f -gmp* is specified.

## Dependencies

Only if the library is compiled with *-fgmp* (it will, by default, if possible):

- Depend on the
*ghc-prim*package, the GHC's internal representation of primitive types. - Depend on the
*integer-gmp*package, the Haskell bindings for GNU's GMP library. - Use
*MagicHash*extension to work with unboxed machine integers.

## Interface

- Added
*bitVecs*(list of bit-vector literals). - Added
*@:*(indexing of multiple bits). - Added
*pow*as an optimized exponentiation function. - Fixed
*bitVec*(value must fit bit-with). - Fixed
*negate*(wrong on zero bit-vector). - Define
*and*and*or*for the case of an empty list. - Declared Monoid instance for bit-vector (monoid under concanetation).
- Define
*join*for the case of an empty list (it must be equivalent to*mconcat*). - Optimized when using the GMP backend:
*fromBits*,*fromInteger*, and*lg2*. - Remove uninteresting
*maxNat*function from export list.

# 0.3.0

This is a maintenance release, but it introduces changes to the API that required a new major version.

## Dependencies

- Increase base version to 4.6.
- Support base 4.7 (new methods were added to the
*Bits*type-class). - Use of
*CPP*extension for conditional compilation.

## Interface

- Replace assertions by errors when checking preconditions of exported functions.
- Use proper names for functions and encourage qualified import, names ended with underscore are now deprecated.
- Add
*lsb1*function to complement*msb1*. - Tweak code and documentation.