bv 0.4.0 → 0.4.1
raw patch · 4 files changed
+178/−24 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- CHANGES.md +62/−0
- README.md +61/−0
- bv.cabal +23/−5
- src/Data/BitVector.hs +32/−19
+ CHANGES.md view
@@ -0,0 +1,62 @@++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.+
+ README.md view
@@ -0,0 +1,61 @@+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.+
bv.cabal view
@@ -1,10 +1,10 @@ Name: bv-Version: 0.4.0+Version: 0.4.1 Synopsis: Bit-vector arithmetic library Description: Bit-vectors implemented as a thin wrapper over integers.-Homepage: http://bitbucket.org/iago/bv-haskell-Bug-reports: http://bitbucket.org/iago/bv-haskell/issues+Homepage: https://github.com/iagoabal/haskell-bv+Bug-reports: https://github.com/iagoabal/haskell-bv/issues License: BSD3 License-file: LICENSE Author: Iago Abal <mail@iagoabal.eu>@@ -14,9 +14,11 @@ Build-type: Simple Cabal-version: >=1.6 +Extra-source-files: README.md CHANGES.md+ source-repository head- type: mercurial- location: https://bitbucket.org/iago/bv-haskell+ type: git+ location: https://github.com/iagoabal/haskell-bv.git Flag gmp Description: Using Integer GMP backend.@@ -27,11 +29,25 @@ Default: False Manual: True +Flag check-bounds+ Description: Bounds checking.+ Default: True+ Manual: True++Flag dev+ Description: Development options.+ Default: False+ Manual: True+ Library Exposed-modules: Data.BitVector -- Other-modules: Hs-Source-Dirs: src+ if flag(check-bounds)+ cpp-options: -DCHECK_BOUNDS ghc-options: -Wall -O2+ if flag(dev)+ ghc-options: -Werror Extensions: CPP Other-Extensions: BangPatterns, DeriveDataTypeable, MagicHash Build-depends: base >=4.6 && <5@@ -51,6 +67,8 @@ Main-Is: Properties.hs Hs-Source-Dirs: src, test ghc-options: -Wall+ if flag(dev)+ ghc-options: -Werror Extensions: CPP Other-Extensions: BangPatterns, DeriveDataTypeable, MagicHash
src/Data/BitVector.hs view
@@ -89,7 +89,7 @@ import Control.Exception ( assert ) import Data.Bits-import Data.Bool ( Bool(..), otherwise, (&&))+import Data.Bool ( Bool(..), otherwise, (&&), (||)) import qualified Data.Bool as Bool import Data.Data ( Data ) import qualified Data.List as List@@ -163,6 +163,20 @@ show (BV n a) = "[" ++ show n ++ "]" ++ show a ----------------------------------------------------------------------+--- Safety checking & Errors++checkBounds :: Bool+#if CHECK_BOUNDS+checkBounds = True+#else+checkBounds = False+#endif++check :: Bool -> Bool+check c = checkBounds && c+{-# INLINE check #-}++---------------------------------------------------------------------- --- Construction -- | The /empty/ bit-vector, ie. @[0]0@.@@ -318,8 +332,8 @@ -- >>> [4]2 @. 1 -- True (@.) :: Integral ix => BV -> ix -> Bool-(BV n a) @. i | 0 <= i' && i' < n = testBit a i'- | otherwise = error "Data.BitVector.(@.): index of out bounds"+(BV n a) @. i | check(i' < 0 || n <= i') = error "Data.BitVector.(@.): index of out bounds"+ | otherwise = testBit a i' where i' = fromIntegral i {-# INLINE (@.) #-} @@ -335,8 +349,8 @@ -- >>> [4]7 @@ (3,1) -- [3]3 (@@) :: Integral ix => BV -> (ix,ix) -> BV-(BV _ a) @@ (j,i) | 0 <= i && i <= j = BV m $ (a `shiftR` i') `mod` 2^m- | otherwise = error "Data.BitVector.(@@): invalid range"+(BV _ a) @@ (j,i) | check(i < 0 || j < i) = error "Data.BitVector.(@@): invalid range"+ | otherwise = BV m $ (a `shiftR` i') `mod` 2^m where i' = fromIntegral i m = fromIntegral $ j - i + 1 {-# INLINE (@@) #-}@@ -355,8 +369,8 @@ -- duplicating calls to 'fromIntegral' **and** this code should allow GHC -- to fuse 'fodlr' (from inlining 'frombits') with 'map'. where testBitAux i- | i' >= 0 && i' < n = testBit a i'- | otherwise = error "Data.BitVector.(@:): index out of bounds"+ | check(i' < 0 || n <= i') = error "Data.BitVector.(@:): index out of bounds"+ | otherwise = testBit a i' where i' = fromIntegral i {-# INLINE (@:) #-} @@ -369,8 +383,8 @@ -- >>> [3]3 !. 0 -- False (!.) :: Integral ix => BV -> ix -> Bool-(BV n a) !. i | 0 <= i' && i' < n = testBit a (n-i'-1)- | otherwise = error "Data.BitVector.(!.): index out of bounds"+(BV n a) !. i | check(i' < 0 || n <= i') = error "Data.BitVector.(!.): index out of bounds"+ | otherwise = testBit a (n-i'-1) where i' = fromIntegral i {-# INLINE (!.) #-} @@ -378,8 +392,8 @@ -- -- @least m u == u \@\@ (m-1,0)@ least :: Integral ix => ix -> BV -> BV-least m (BV _ a) | m' < 1 = error "Data.BitVector.least: non-positive index"- | otherwise = BV m' $ a `mod` 2^m+least m (BV _ a) | check(m' < 1) = error "Data.BitVector.least: non-positive index"+ | otherwise = BV m' $ a `mod` 2^m where m' = fromIntegral m {-# INLINE least #-} @@ -387,9 +401,9 @@ -- -- @most m u == u \@\@ (n-1,n-m)@ most :: Integral ix => ix -> BV -> BV-most m (BV n a) | m' < 1 = error "Data.BitVector.most: non-positive index"- | m' > n = error "Data.BitVector.most: index out of bounds"- | otherwise = BV m' $ a `shiftR` (n-m')+most m (BV n a) | check(m' < 1) = error "Data.BitVector.most: non-positive index"+ | check(m' > n) = error "Data.BitVector.most: index out of bounds"+ | otherwise = BV m' $ a `shiftR` (n-m') where m' = fromIntegral m {-# INLINE most #-} @@ -444,7 +458,6 @@ (BV n1 a) + (BV n2 b) = BV n $ (a + b) `mod` 2^n where n = max n1 n2 {-# INLINE (+) #-}- {-# INLINE (-) #-} (BV n1 a) * (BV n2 b) = BV n $ (a * b) `mod` 2^n where n = max n1 n2 {-# INLINE (*) #-}@@ -657,8 +670,8 @@ -- >>> split 3 [4]15 -- [[2]0,[2]3,[2]3] split :: Integral times => times -> BV -> [BV]-split k (BV n a) | k > 0 = List.map (BV s) $ splitInteger s k' a- | otherwise = error "Data.BitVector.split: non-positive splits"+split k (BV n a) | k <= 0 = error "Data.BitVector.split: non-positive splits"+ | otherwise = List.map (BV s) $ splitInteger s k' a where k' = fromIntegral k (q,r) = divMod n k' s = q + signum r@@ -669,8 +682,8 @@ -- >>> group 3 [4]15 -- [[3]1,[3]7] group, group_ :: Integral size => size -> BV -> [BV]-group s (BV n a) | s > 0 = List.map (BV s') $ splitInteger s' k a- | otherwise = error "Data.BitVector.group: non-positive size"+group s (BV n a) | s <= 0 = error "Data.BitVector.group: non-positive size"+ | otherwise = List.map (BV s') $ splitInteger s' k a where s' = fromIntegral s (q,r) = divMod n s' k = q + signum r