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.
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
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.
Note that changes in
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!
fromIntegerconsistent 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.
Read BVinstance (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.
Another maintenance release:
- Fix compilation error with GHC 8.0.1.
- Add `check-bounds’ flag so the user decides whether to perform bounds checking.
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.
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.
- 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.
This is a maintenance release, but it introduces changes to the API that required a new major version.
- 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.
- 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.