bitvec 1.1.2.0 → 1.1.3.0
raw patch · 14 files changed
+289/−150 lines, 14 filesdep −tasty-hunitdep ~vectorPVP ok
version bump matches the API change (PVP)
Dependencies removed: tasty-hunit
Dependency ranges changed: vector
API changes (from Hackage documentation)
Files
- LICENSE +1/−1
- README.md +17/−17
- bitvec.cabal +8/−9
- changelog.md +4/−0
- src/Data/Bit.hs +2/−2
- src/Data/Bit/F2Poly.hs +34/−10
- src/Data/Bit/Immutable.hs +49/−13
- src/Data/Bit/Internal.hs +81/−22
- src/Data/Bit/Mutable.hs +25/−9
- src/Data/Bit/PdepPext.hs +1/−1
- src/Data/Bit/Utils.hs +2/−1
- test/Tests/Conc.hs +13/−13
- test/Tests/F2Poly.hs +1/−0
- test/Tests/MVector.hs +51/−52
LICENSE view
@@ -1,4 +1,4 @@-Copyright (c) 2019-2020 Andrew Lelechenko, 2012-2016 James Cook+Copyright (c) 2019-2022 Andrew Lelechenko, 2012-2016 James Cook All rights reserved.
README.md view
@@ -1,13 +1,13 @@-# bitvec [](https://hackage.haskell.org/package/bitvec) [](http://stackage.org/lts/package/bitvec) [](http://stackage.org/nightly/package/bitvec)+# bitvec [](https://hackage.haskell.org/package/bitvec) [](https://www.stackage.org/lts/package/bitvec) [](https://www.stackage.org/nightly/package/bitvec) A newtype over `Bool` with a better `Vector` instance: 8x less memory, up to 1000x faster. The [`vector`](https://hackage.haskell.org/package/vector)-package represents unboxed arrays of `Bool`+package represents unboxed arrays of `Bool`s spending 1 byte (8 bits) per boolean. This library provides a newtype wrapper `Bit` and a custom instance-of unboxed `Vector`, which packs bits densely,-achieving __8x less memory footprint.__+of an unboxed `Vector`, which packs bits densely,+achieving an __8x smaller memory footprint.__ The performance stays mostly the same; the most significant degradation happens for random writes (up to 10% slower).@@ -18,7 +18,7 @@ * `Data.Bit` is faster, but writes and flips are thread-unsafe. This is because naive updates are not atomic:- read the whole word from memory,+ they read the whole word from memory, then modify a bit, then write the whole word back. * `Data.Bit.ThreadSafe` is slower (up to 20%), but writes and flips are thread-safe.@@ -73,7 +73,7 @@ U.unsafeFreeze sieve ``` -`Bit`-based implementation requires 8x less memory to store+The `Bit`-based implementation requires 8x less memory to store the vector. For large sizes it allows to crunch more data in RAM without swapping. For smaller arrays it helps to fit into CPU caches.@@ -84,8 +84,8 @@ ``` There are several high-level helpers, digesting bits in bulk,-which makes them up to 64x faster than respective counterparts-for `Vector Bool`. One can query population count (popcount)+which makes them up to 64x faster than the respective counterparts+for `Vector Bool`. One can query the population count (popcount) of a vector (giving us [the prime-counting function](https://en.wikipedia.org/wiki/Prime-counting_function)): ```haskell@@ -110,7 +110,7 @@ ## Sets -Bit vectors can be used as a blazingly fast representation of sets+Bit vectors can be used as a blazingly fast representation of sets, as long as their elements are `Enum`eratable and sufficiently dense, leaving `IntSet` far behind. @@ -120,24 +120,24 @@ * As a 64k-long unboxed `Vector Bool`, implementing union as `zipWith (||)`. * As a 64k-long unboxed `Vector Bit`, implementing union as `zipBits (.|.)`. -When flag `libgmp` is enabled,-according to our benchmarks (see `bench` folder)+When the `libgmp` flag is enabled,+according to our benchmarks (see `bench` folder), the union of `Vector Bit` evaluates 24x-36x faster-than the union of not-too-sparse `IntSet`-and stunningly outperforms `Vector Bool` 500x-1000x.+than the union of not-too-sparse `IntSet`s+and stunningly outperforms `Vector Bool` by 500x-1000x. ## Binary polynomials Binary polynomials are polynomials with coefficients modulo 2. Their applications include coding theory and cryptography.-While one can successfully implement them with `poly` package,+While one can successfully implement them with the [`poly`](https://hackage.haskell.org/package/poly) package, operating on `UPoly Bit`, this package provides even faster arithmetic routines-exposed via `F2Poly` data type and its instances.+exposed via the `F2Poly` data type and its instances. ```haskell > :set -XBinaryLiterals-> -- (1 + x) (1 + x + x^2) = 1 + x^3 (mod 2)+> -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2) > 0b11 * 0b111 :: F2Poly F2Poly {unF2Poly = [1,0,0,1]} ```@@ -149,7 +149,7 @@ * Flag `libgmp`, disabled by default. - Link against [GMP](https://gmplib.org/) library for the ultimate performance of+ Link against the [GMP](https://gmplib.org/) library for the ultimate performance of `zipBits`, `invertBits` and `countBits`. GMP is readily available on most machines ([`apt-get install libgmp-dev`](https://packages.ubuntu.com/focal/libgmp-dev) on Ubuntu, [`brew install gmp`](https://formulae.brew.sh/formula/gmp)
bitvec.cabal view
@@ -1,10 +1,10 @@ name: bitvec-version: 1.1.2.0+version: 1.1.3.0 cabal-version: >=1.10 build-type: Simple license: BSD3 license-file: LICENSE-copyright: 2019-2021 Andrew Lelechenko, 2012-2016 James Cook+copyright: 2019-2022 Andrew Lelechenko, 2012-2016 James Cook maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com> homepage: https://github.com/Bodigrim/bitvec synopsis: Space-efficient bit vectors@@ -12,11 +12,11 @@ A newtype over 'Bool' with a better 'Vector' instance: 8x less memory, up to 1000x faster. . The <https://hackage.haskell.org/package/vector vector>- package represents unboxed arrays of 'Bool'+ package represents unboxed arrays of 'Bool's spending 1 byte (8 bits) per boolean. This library provides a newtype wrapper 'Bit' and a custom instance- of unboxed 'Vector', which packs bits densely,- achieving __8x less memory footprint.__+ of an unboxed 'Vector', which packs bits densely,+ achieving an __8x smaller memory footprint.__ The performance stays mostly the same; the most significant degradation happens for random writes (up to 10% slower).@@ -27,7 +27,7 @@ . * "Data.Bit" is faster, but writes and flips are thread-unsafe. This is because naive updates are not atomic:- read the whole word from memory,+ they read the whole word from memory, then modify a bit, then write the whole word back. * "Data.Bit.ThreadSafe" is slower (up to 20%), but writes and flips are thread-safe.@@ -57,7 +57,7 @@ flag libgmp description:- Link against GMP library for the ultimate performance of+ Link against the GMP library for the ultimate performance of `zipBits`, `invertBits` and `countBits`. Users are strongly encouraged to enable this flag whenever possible. default: False@@ -72,7 +72,7 @@ bytestring >=0.10, deepseq, primitive >=0.5,- vector >=0.11+ vector >=0.11 && <0.14 default-language: Haskell2010 hs-source-dirs: src other-modules:@@ -110,7 +110,6 @@ quickcheck-classes >=0.6.1, vector >=0.11, tasty,- tasty-hunit, tasty-quickcheck default-language: Haskell2010 hs-source-dirs: test
changelog.md view
@@ -1,3 +1,7 @@+# 1.1.3.0++* Fix malformed `signum` for `F2Poly`.+ # 1.1.2.0 * Fix `setBit`, `clearBit`, `complementBit` to preserve vector's length.
src/Data/Bit.hs view
@@ -4,7 +4,7 @@ #ifndef BITVEC_THREADSAFE -- | -- Module: Data.Bit--- Copyright: (c) 2019-2020 Andrew Lelechenko, 2012-2016 James Cook+-- Copyright: (c) 2019-2022 Andrew Lelechenko, 2012-2016 James Cook -- Licence: BSD3 -- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com> --@@ -14,7 +14,7 @@ #else -- | -- Module: Data.Bit.ThreadSafe--- Copyright: (c) 2019-2020 Andrew Lelechenko, 2012-2016 James Cook+-- Copyright: (c) 2019-2022 Andrew Lelechenko, 2012-2016 James Cook -- Licence: BSD3 -- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com> --
src/Data/Bit/F2Poly.hs view
@@ -57,34 +57,56 @@ -- -- Polynomials are stored normalized, without leading zero coefficients. ----- 'Ord' instance does not make much sense mathematically,+-- The 'Ord' instance does not make much sense mathematically, -- it is defined only for the sake of 'Data.Set.Set', 'Data.Map.Map', etc. -- -- >>> :set -XBinaryLiterals--- >>> -- (1 + x) (1 + x + x^2) = 1 + x^3 (mod 2)+-- >>> -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2) -- >>> 0b11 * 0b111 :: F2Poly -- 0b1001+--+-- @since 1.0.1.0 newtype F2Poly = F2Poly { unF2Poly :: U.Vector Bit- -- ^ Convert 'F2Poly' to a vector of coefficients+ -- ^ Convert an 'F2Poly' to a vector of coefficients -- (first element corresponds to a constant term). -- -- >>> :set -XBinaryLiterals -- >>> unF2Poly 0b1101 -- [1,0,1,1]+ --+ -- @since 1.0.1.0 } deriving (Eq, Ord, Typeable, Generic, NFData) --- | Make 'F2Poly' from a list of coefficients+-- | Make an 'F2Poly' from a list of coefficients -- (first element corresponds to a constant term). -- -- >>> :set -XOverloadedLists -- >>> toF2Poly [1,0,1,1,0,0] -- 0b1101+--+-- @since 1.0.1.0 toF2Poly :: U.Vector Bit -> F2Poly toF2Poly xs = F2Poly $ dropWhileEnd $ castFromWords $ cloneToWords xs --- -- | Valid 'F2Poly' has offset 0 and no trailing garbage.+zero :: F2Poly+zero = F2Poly $ BitVec 0 0 $+#ifdef MIN_VERSION_ghc_bignum+ ByteArray (unBigNat bigNatZero)+#else+ fromBigNat zeroBigNat+#endif++one :: F2Poly+one = F2Poly $ BitVec 0 1 $+#ifdef MIN_VERSION_ghc_bignum+ ByteArray (unBigNat bigNatOne)+#else+ fromBigNat oneBigNat+#endif++-- -- | A valid 'F2Poly' has offset 0 and no trailing garbage. -- _isValid :: F2Poly -> Bool -- _isValid (F2Poly (BitVec o l arr)) = o == 0 && l == l' -- where@@ -101,7 +123,7 @@ (-) = coerce xorBits negate = id abs = id- signum = const (F2Poly (U.singleton (Bit True)))+ signum = const one (*) = coerce ((dropWhileEnd .) . karatsuba) #ifdef MIN_VERSION_ghc_bignum fromInteger !n = case n of@@ -144,7 +166,7 @@ toRational = fromIntegral -- | 'toInteger' converts a binary polynomial, encoded as 'F2Poly',--- to 'Integer' encoding.+-- to an 'Integer' encoding. instance Integral F2Poly where #ifdef MIN_VERSION_ghc_bignum toInteger xs = integerFromBigNat# (bitsToByteArray (unF2Poly xs))@@ -306,7 +328,7 @@ bitsToByteArray :: U.Vector Bit -> ByteArray# bitsToByteArray xs = arr where- ys = if U.null xs then U.singleton 0 else cloneToWords xs+ ys = if U.null xs then U.singleton (0 :: Word) else cloneToWords xs !(P.Vector _ _ (ByteArray arr)) = toPrimVector ys #ifdef MIN_VERSION_ghc_bignum@@ -320,15 +342,17 @@ -- | Execute the extended Euclidean algorithm. -- For polynomials @a@ and @b@, compute their unique greatest common divisor @g@--- and the unique coefficient polynomial @s@ satisfying @as + bt = g@.+-- and the unique coefficient polynomial @s@ satisfying \( a \cdot s + b \cdot t = g \). -- -- >>> :set -XBinaryLiterals -- >>> gcdExt 0b101 0b0101 -- (0b101,0b0) -- >>> gcdExt 0b11 0b111 -- (0b1,0b10)+--+-- @since 1.0.2.0 gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)-gcdExt = go 1 0+gcdExt = go one zero where go s s' r r' | r' == 0 = (r, s)
src/Data/Bit/Immutable.hs view
@@ -154,6 +154,8 @@ -- >>> :set -XOverloadedLists -- >>> castFromWords [123] -- [1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]+--+-- @since 1.0.0.0 castFromWords :: U.Vector Word -> U.Vector Bit castFromWords ws = BitVec (mulWordSize off) (mulWordSize len) arr where@@ -161,11 +163,13 @@ -- | Try to cast an unboxed vector of bits -- to an unboxed vector of words.--- It succeeds if a vector of bits is aligned.+-- It succeeds if the vector of bits is aligned. -- Use 'cloneToWords' otherwise. -- Cf. 'Data.Bit.castToWordsM'. -- -- > castToWords (castFromWords v) == Just v+--+-- @since 1.0.0.0 castToWords :: U.Vector Bit -> Maybe (U.Vector Word) castToWords (BitVec s n ws) | aligned s, aligned n =@@ -182,6 +186,8 @@ -- >>> :set -XOverloadedLists -- >>> cloneToWords [1,1,0,1,1,1,1] -- [123]+--+-- @since 1.0.0.0 cloneToWords :: U.Vector Bit -> U.Vector Word cloneToWords v = runST $ do v' <- U.unsafeThaw v@@ -189,15 +195,17 @@ U.unsafeFreeze w {-# INLINE cloneToWords #-} --- | Cast a unboxed vector of 'Word8'+-- | Cast an unboxed vector of 'Word8' -- to an unboxed vector of bits. -- -- On big-endian architectures 'castFromWords8'--- resorts to copying instead of aliasing underlying arrays.+-- resorts to copying instead of aliasing the underlying array. -- -- >>> :set -XOverloadedLists -- >>> castFromWords8 [123] -- [1,1,0,1,1,1,1,0]+--+-- @since 1.0.3.0 castFromWords8 :: U.Vector Word8 -> U.Vector Bit castFromWords8 ws = BitVec (off `shiftL` 3) (len `shiftL` 3) arr where@@ -220,10 +228,12 @@ -- | Try to cast an unboxed vector of bits -- to an unboxed vector of 'Word8'.--- It succeeds if a vector of bits is aligned.+-- It succeeds if the vector of bits is aligned. -- Use 'Data.Bit.cloneToWords8' otherwise. -- -- > castToWords8 (castFromWords8 v) == Just v+--+-- @since 1.0.3.0 castToWords8 :: U.Vector Bit -> Maybe (U.Vector Word8) #ifdef WORDS_BIGENDIAN castToWords8 = const Nothing@@ -242,6 +252,8 @@ -- >>> :set -XOverloadedLists -- >>> cloneToWords8 [1,1,0,1,1,1,1] -- [123]+--+-- @since 1.0.3.0 cloneToWords8 :: U.Vector Bit -> U.Vector Word8 cloneToWords8 v = runST $ do v' <- U.unsafeThaw v@@ -254,6 +266,8 @@ -- >>> :set -XOverloadedStrings -- >>> cloneFromByteString "abc" -- [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]+--+-- @since 1.1.0.0 cloneFromByteString :: BS.ByteString -> U.Vector Bit cloneFromByteString = castFromWords8@@ -268,6 +282,8 @@ -- >>> :set -XOverloadedLists -- >>> cloneToByteString [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1] -- "ab#"+--+-- @since 1.1.0.0 cloneToByteString :: U.Vector Bit -> BS.ByteString cloneToByteString = uncurry3 BS.fromForeignPtr@@ -286,8 +302,8 @@ -- 'zipBits' is up to 32x faster than -- 'Data.IntSet.union', 'Data.IntSet.intersection', etc. ----- Users are strongly encouraged to enable--- flag @libgmp@ for the ultimate performance of 'zipBits'.+-- Users are strongly encouraged to enable the+-- @libgmp@ flag for the ultimate performance of 'zipBits'. -- -- >>> :set -XOverloadedLists -- >>> import Data.Bits@@ -299,6 +315,8 @@ -- [1,0,0] -- >>> zipBits xor [1,1,0] [0,1,1] -- symmetric difference -- [1,0,1]+--+-- @since 1.0.0.0 zipBits :: (forall a . Bits a => a -> a -> a) -> U.Vector Bit@@ -351,6 +369,8 @@ -- >>> import Data.Bits -- >>> mapBits complement [0,1,1] -- [1,0,0]+--+-- @since 1.1.0.0 mapBits :: (forall a . Bits a => a -> a) -> U.Vector Bit@@ -364,12 +384,14 @@ -- | Invert (flip) all bits. ----- Users are strongly encouraged to enable--- flag @libgmp@ for the ultimate performance of 'invertBits'.+-- Users are strongly encouraged to enable the+-- @libgmp@ flag for the ultimate performance of 'invertBits'. -- -- >>> :set -XOverloadedLists -- >>> invertBits [0,1,0,1,0] -- [1,0,1,0,1]+--+-- @since 1.0.1.0 invertBits :: U.Vector Bit -> U.Vector Bit@@ -399,7 +421,9 @@ -- Here is a reference (but slow) implementation: -- -- > import qualified Data.Vector.Unboxed as U--- > selectBits mask ws == U.map snd (U.filter (unBit . fst) (U.zip mask ws))+-- > selectBits mask ws = U.map snd (U.filter (unBit . fst) (U.zip mask ws))+--+-- @since 0.1 selectBits :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit selectBits is xs = runST $ do xs1 <- U.thaw xs@@ -417,7 +441,9 @@ -- Here is a reference (but slow) implementation: -- -- > import qualified Data.Vector.Unboxed as U--- > excludeBits mask ws == U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))+-- > excludeBits mask ws = U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))+--+-- @since 0.1 excludeBits :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit excludeBits is xs = runST $ do xs1 <- U.thaw xs@@ -430,8 +456,10 @@ -- >>> reverseBits [1,1,0,1,0] -- [0,1,0,1,1] ----- Consider using @vector-rotcev@ package+-- Consider using the [vector-rotcev](https://hackage.haskell.org/package/vector-rotcev) package -- to reverse vectors in O(1) time.+--+-- @since 1.0.1.0 reverseBits :: U.Vector Bit -> U.Vector Bit reverseBits xs = runST $ do let n = U.length xs@@ -473,6 +501,8 @@ -- > import Data.Maybe -- > isAnyBitSet = isJust . bitIndex 1 -- > areAllBitsSet = isNothing . bitIndex 0+--+-- @since 1.0.0.0 bitIndex :: Bit -> U.Vector Bit -> Maybe Int bitIndex b (BitVec off len arr) | len == 0 = Nothing@@ -554,6 +584,8 @@ -- One can use 'nthBitIndex' to implement -- to implement @select{0,1}@ queries -- for <https://en.wikipedia.org/wiki/Succinct_data_structure succinct dictionaries>.+--+-- @since 1.0.0.0 nthBitIndex :: Bit -> Int -> U.Vector Bit -> Maybe Int nthBitIndex _ k _ | k <= 0 = error "nthBitIndex: n must be positive" nthBitIndex b k (BitVec off len arr)@@ -633,8 +665,8 @@ -- | Return the number of set bits in a vector (population count, popcount). ----- Users are strongly encouraged to enable--- flag @libgmp@ for the ultimate performance of 'countBits'.+-- Users are strongly encouraged to enable the+-- @libgmp@ flag for the ultimate performance of 'countBits'. -- -- >>> :set -XOverloadedLists -- >>> countBits [1,1,0,1,0,1]@@ -643,6 +675,8 @@ -- One can combine 'countBits' with 'Data.Vector.Unboxed.take' -- to implement @rank{0,1}@ queries -- for <https://en.wikipedia.org/wiki/Succinct_data_structure succinct dictionaries>.+--+-- @since 0.1 countBits :: U.Vector Bit -> Int countBits (BitVec _ 0 _) = 0 #if UseLibGmp@@ -680,6 +714,8 @@ -- >>> :set -XOverloadedLists -- >>> listBits [1,1,0,1,0,1] -- [0,1,3,5]+--+-- @since 0.1 listBits :: U.Vector Bit -> [Int] listBits (BitVec _ 0 _) = [] listBits (BitVec off len arr) | offBits == 0 = case modWordSize len of
src/Data/Bit/Internal.hs view
@@ -27,7 +27,11 @@ , modifyByteArray ) where +#if MIN_VERSION_vector(0,13,0)+import Data.Vector.Internal.Check (checkIndex, Checks(..))+#else #include "vector.h"+#endif import Control.DeepSeq import Control.Exception@@ -49,27 +53,45 @@ #ifndef BITVEC_THREADSAFE -- | A newtype wrapper with a custom instance--- of "Data.Vector.Unboxed", which packs booleans+-- for "Data.Vector.Unboxed", which packs booleans -- as efficient as possible (8 values per byte).--- Vectors of `Bit` use 8x less memory--- than vectors of 'Bool' (which stores one value per byte).+-- Unboxed vectors of `Bit` use 8x less memory+-- than unboxed vectors of 'Bool' (which store one value per byte), -- but random writes are up to 10% slower.-newtype Bit = Bit { unBit :: Bool }- deriving (Bounded, Enum, Eq, Ord, FiniteBits, Bits, Typeable, Generic, NFData)+--+-- @since 0.1+newtype Bit = Bit {+ unBit :: Bool -- ^ @since 0.2.0.0+ } deriving+ (Bounded, Enum, Eq, Ord+ , FiniteBits -- ^ @since 0.2.0.0+ , Bits, Typeable+ , Generic -- ^ @since 1.0.1.0+ , NFData -- ^ @since 1.0.1.0+ ) #else -- | A newtype wrapper with a custom instance--- of "Data.Vector.Unboxed", which packs booleans+-- for "Data.Vector.Unboxed", which packs booleans -- as efficient as possible (8 values per byte).--- Vectors of `Bit` use 8x less memory--- than vectors of 'Bool' (which stores one value per byte).+-- Unboxed vectors of `Bit` use 8x less memory+-- than unboxed vectors of 'Bool' (which store one value per byte), -- but random writes are up to 20% slower.-newtype Bit = Bit { unBit :: Bool }- deriving (Bounded, Enum, Eq, Ord, FiniteBits, Bits, Typeable, Generic, NFData)+newtype Bit = Bit {+ unBit :: Bool -- ^ @since 0.2.0.0+ } deriving+ (Bounded, Enum, Eq, Ord+ , FiniteBits -- ^ @since 0.2.0.0+ , Bits, Typeable+ , Generic -- ^ @since 1.0.1.0+ , NFData -- ^ @since 1.0.1.0+ ) #endif -- | There is only one lawful 'Num' instance possible -- with '+' = 'xor' and -- 'fromInteger' = 'Bit' . 'odd'.+--+-- @since 1.0.1.0 instance Num Bit where Bit a * Bit b = Bit (a && b) Bit a + Bit b = Bit (a /= b)@@ -79,15 +101,18 @@ signum = id fromInteger = Bit . odd +-- | @since 1.0.1.0 instance Real Bit where toRational = fromIntegral +-- | @since 1.0.1.0 instance Integral Bit where quotRem _ (Bit False) = throw DivideByZero quotRem x (Bit True) = (x, Bit False) toInteger (Bit False) = 0 toInteger (Bit True) = 1 +-- | @since 1.0.1.0 instance Fractional Bit where fromRational x = fromInteger (numerator x) / fromInteger (denominator x) (/) = quot@@ -116,7 +141,7 @@ extendToWord (Bit False) = 0 extendToWord (Bit True ) = complement 0 --- | read a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the result is padded with memory garbage.+-- | Read a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the result is padded with memory garbage. indexWord :: U.Vector Bit -> Int -> Word indexWord (BitVec _ 0 _) _ = 0 indexWord (BitVec off len' arr) !i' = word@@ -137,7 +162,7 @@ = (loWord `unsafeShiftR` nMod) .|. (hiWord `unsafeShiftL` (wordSize - nMod)) {-# INLINE indexWord #-} --- | read a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the result is padded with memory garbage.+-- | Read a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the result is padded with memory garbage. readWord :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m Word readWord (BitMVec _ 0 _) _ = pure 0 readWord (BitMVec off len' arr) !i' = do@@ -187,7 +212,7 @@ #endif --- | write a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the word is truncated and as many low-order bits as possible are written.+-- | Write a word at the given bit offset in little-endian order (i.e., the LSB will correspond to the bit at the given address, the 2's bit will correspond to the address + 1, etc.). If the offset is such that the word extends past the end of the vector, the word is truncated and as many low-order bits as possible are written. writeWord :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> Word -> m () writeWord (BitMVec _ 0 _) _ _ = pure () writeWord (BitMVec off len' arr) !i' !x@@ -404,7 +429,7 @@ #ifndef BITVEC_THREADSAFE -- | Flip the bit at the given position.--- No bounds checks are performed.+-- No bound checks are performed. -- Equivalent to 'flip' 'Data.Vector.Unboxed.Mutable.unsafeModify' 'Data.Bits.complement', -- but up to 2x faster. --@@ -415,15 +440,27 @@ -- >>> :set -XOverloadedLists -- >>> Data.Vector.Unboxed.modify (`unsafeFlipBit` 2) [1,1,1,1] -- [1,1,0,1]+--+-- @since 1.0.0.0 unsafeFlipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m ()-unsafeFlipBit (BitMVec off _ arr) !i' = do+unsafeFlipBit v i =+#if MIN_VERSION_vector(0,13,0)+ checkIndex Unsafe+#else+ UNSAFE_CHECK(checkIndex) "flipBit"+#endif+ i (MV.length v) $ basicFlipBit v i+{-# INLINE unsafeFlipBit #-}++basicFlipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m ()+basicFlipBit (BitMVec off _ arr) !i' = do let i = off + i' j = divWordSize i k = modWordSize i kk = 1 `unsafeShiftL` k :: Word word <- readByteArray arr j writeByteArray arr j (word `xor` kk)-{-# INLINE unsafeFlipBit #-}+{-# INLINE basicFlipBit #-} -- | Flip the bit at the given position. -- Equivalent to 'flip' 'Data.Vector.Unboxed.Mutable.modify' 'Data.Bits.complement',@@ -436,16 +473,23 @@ -- >>> :set -XOverloadedLists -- >>> Data.Vector.Unboxed.modify (`flipBit` 2) [1,1,1,1] -- [1,1,0,1]+--+-- @since 1.0.0.0 flipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m () flipBit v i =- BOUNDS_CHECK(checkIndex) "flipBit" i (MV.length v) $- unsafeFlipBit v i+#if MIN_VERSION_vector(0,13,0)+ checkIndex Bounds+#else+ BOUNDS_CHECK(checkIndex) "flipBit"+#endif+ i (MV.length v) $+ unsafeFlipBit v i {-# INLINE flipBit #-} #else -- | Flip the bit at the given position.--- No bounds checks are performed.+-- No bound checks are performed. -- Equivalent to 'flip' 'Data.Vector.Unboxed.Mutable.unsafeModify' 'Data.Bits.complement', -- but up to 33% faster and atomic. --@@ -456,13 +500,23 @@ -- >>> Data.Vector.Unboxed.modify (\v -> unsafeFlipBit v 1) (read "[1,1,1]") -- [1,0,1] unsafeFlipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m ()-unsafeFlipBit (BitMVec off _ (MutableByteArray mba)) !i' = do+unsafeFlipBit v i =+#if MIN_VERSION_vector(0,13,0)+ checkIndex Unsafe+#else+ UNSAFE_CHECK(checkIndex) "flipBit"+#endif+ i (MV.length v) $ basicFlipBit v i+{-# INLINE unsafeFlipBit #-}++basicFlipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m ()+basicFlipBit (BitMVec off _ (MutableByteArray mba)) !i' = do let i = off + i' !(I# j) = divWordSize i !(I# k) = 1 `unsafeShiftL` modWordSize i primitive $ \state -> let !(# state', _ #) = fetchXorIntArray# mba j k state in (# state', () #)-{-# INLINE unsafeFlipBit #-}+{-# INLINE basicFlipBit #-} -- | Flip the bit at the given position. -- Equivalent to 'flip' 'Data.Vector.Unboxed.Mutable.modify' 'Data.Bits.complement',@@ -476,7 +530,12 @@ -- [1,0,1] flipBit :: PrimMonad m => U.MVector (PrimState m) Bit -> Int -> m () flipBit v i =- BOUNDS_CHECK(checkIndex) "flipBit" i (MV.length v) $ unsafeFlipBit v i+#if MIN_VERSION_vector(0,13,0)+ checkIndex Bounds+#else+ BOUNDS_CHECK(checkIndex) "flipBit"+#endif+ i (MV.length v) $ basicFlipBit v i {-# INLINE flipBit #-} #endif
src/Data/Bit/Mutable.hs view
@@ -51,14 +51,18 @@ -- | Cast a vector of words to a vector of bits. -- Cf. 'Data.Bit.castFromWords'.+--+-- @since 1.0.0.0 castFromWordsM :: MVector s Word -> MVector s Bit castFromWordsM (MU.MV_Word (P.MVector off len ws)) = BitMVec (mulWordSize off) (mulWordSize len) ws -- | Try to cast a vector of bits to a vector of words.--- It succeeds if a vector of bits is aligned.+-- It succeeds if the vector of bits is aligned. -- Use 'cloneToWordsM' otherwise. -- Cf. 'Data.Bit.castToWords'.+--+-- @since 1.0.0.0 castToWordsM :: MVector s Bit -> Maybe (MVector s Word) castToWordsM (BitMVec s n ws) | aligned s, aligned n@@ -68,6 +72,8 @@ -- | Clone a vector of bits to a new unboxed vector of words. -- If the bits don't completely fill the words, the last word will be zero-padded. -- Cf. 'Data.Bit.cloneToWords'.+--+-- @since 1.0.0.0 cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit@@ -106,8 +112,8 @@ pure $ MU.MV_Word8 $ P.MVector 0 actualLenBytes arr {-# INLINE cloneToWords8M #-} --- | Zip two vectors with the given function.--- rewriting contents of the second argument.+-- | Zip two vectors with the given function,+-- rewriting the contents of the second argument. -- Cf. 'Data.Bit.zipBits'. -- -- >>> :set -XOverloadedLists@@ -116,12 +122,14 @@ -- [0,1,0] -- -- __Warning__: if the immutable vector is shorter than the mutable one,--- it is a caller's responsibility to trim the result:+-- it is the caller's responsibility to trim the result: -- -- >>> :set -XOverloadedLists -- >>> import Data.Bits -- >>> Data.Vector.Unboxed.modify (zipInPlace (.&.) [1,1,0]) [0,1,1,1,1,1] -- [0,1,0,1,1,1] -- note trailing garbage+--+-- @since 1.0.0.0 zipInPlace :: forall m. PrimMonad m@@ -202,6 +210,8 @@ -- >>> import Data.Bits -- >>> Data.Vector.Unboxed.modify (mapInPlace complement) [0,1,1] -- [1,0,0]+--+-- @since 1.1.0.0 mapInPlace :: PrimMonad m => (forall a . Bits a => a -> a)@@ -220,6 +230,8 @@ -- >>> :set -XOverloadedLists -- >>> Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0] -- [1,0,1,0,1]+--+-- @since 0.1 invertInPlace :: PrimMonad m => U.MVector (PrimState m) Bit -> m () invertInPlace xs = do let n = MU.length xs@@ -229,8 +241,8 @@ {-# SPECIALIZE invertInPlace :: U.MVector s Bit -> ST s () #-} -- | Same as 'Data.Bit.selectBits', but deposit--- selected bits in-place. Returns a number of selected bits.--- It is caller's responsibility to trim the result to this number.+-- selected bits in-place. Returns the number of selected bits.+-- It is the caller's responsibility to trim the result to this number. -- -- >>> :set -XOverloadedLists -- >>> import Control.Monad.ST (runST)@@ -238,6 +250,7 @@ -- >>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- selectBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec } -- [1,0,1] --+-- @since 0.1 selectBitsInPlace :: PrimMonad m => U.Vector Bit -> U.MVector (PrimState m) Bit -> m Int selectBitsInPlace is xs = loop 0 0@@ -252,8 +265,8 @@ loop (i + wordSize) (ct + nSet) -- | Same as 'Data.Bit.excludeBits', but deposit--- excluded bits in-place. Returns a number of excluded bits.--- It is caller's responsibility to trim the result to this number.+-- excluded bits in-place. Returns the number of excluded bits.+-- It is the caller's responsibility to trim the result to this number. -- -- >>> :set -XOverloadedLists -- >>> import Control.Monad.ST (runST)@@ -261,6 +274,7 @@ -- >>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- excludeBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec } -- [1,0] --+-- @since 0.1 excludeBitsInPlace :: PrimMonad m => U.Vector Bit -> U.MVector (PrimState m) Bit -> m Int excludeBitsInPlace is xs = loop 0 0@@ -281,8 +295,10 @@ -- >>> Data.Vector.Unboxed.modify reverseInPlace [1,1,0,1,0] -- [0,1,0,1,1] ----- Consider using @vector-rotcev@ package+-- Consider using the [vector-rotcev](https://hackage.haskell.org/package/vector-rotcev) package -- to reverse vectors in O(1) time.+--+-- @since 0.1 reverseInPlace :: PrimMonad m => U.MVector (PrimState m) Bit -> m () reverseInPlace xs | len == 0 = pure ()
src/Data/Bit/PdepPext.hs view
@@ -1,6 +1,6 @@ -- | -- Module: Data.Bit.PdepPext--- Copyright: (c) 2020 Andrew Lelechenko+-- Copyright: (c) 2022 Andrew Lelechenko -- Licence: BSD3 -- -- | Parallel bit deposit and extract instructions.
src/Data/Bit/Utils.hs view
@@ -35,10 +35,11 @@ import Data.Bit.PdepPext --- |The number of bits in a 'Word'. A handy constant to have around when defining 'Word'-based bulk operations on bit vectors.+-- | The number of bits in a 'Word'. A handy constant to have around when defining 'Word'-based bulk operations on bit vectors. wordSize :: Int wordSize = finiteBitSize (0 :: Word) +-- | The base 2 logarithm of 'wordSize'. lgWordSize :: Int lgWordSize = case wordSize of 32 -> 5
test/Tests/Conc.hs view
@@ -10,13 +10,13 @@ import qualified Data.Vector.Generic.Mutable as M import qualified Data.Vector.Unboxed as U import Test.Tasty-import Test.Tasty.HUnit+import Test.Tasty.QuickCheck concTests :: TestTree concTests = testGroup "Concurrency"- [ testCase "invertInPlace" case_conc_invert- , testCase "reverseInPlace" case_conc_reverse- , testCase "zipInPlace" case_conc_zip+ [ testProperty "invertInPlace" case_conc_invert+ , testProperty "reverseInPlace" case_conc_reverse+ , testProperty "zipInPlace" case_conc_zip ] runConcurrently :: IO () -> IO () -> IO ()@@ -28,8 +28,8 @@ action2 takeMVar m -case_conc_invert :: IO ()-case_conc_invert = replicateM_ 1000 $ do+case_conc_invert :: Property+case_conc_invert = ioProperty $ replicateM_ 1000 $ do let len = 64 len' = 37 vec <- M.replicate len (Bit True)@@ -38,10 +38,10 @@ (replicateM_ 1000 $ invertInPlace (M.take len' vec)) (replicateM_ 1000 $ invertInPlace (M.drop len' vec)) wec <- V.unsafeFreeze vec- assertEqual "should be equal" ref wec+ pure $ ref === wec -case_conc_reverse :: IO ()-case_conc_reverse = replicateM_ 1000 $ do+case_conc_reverse :: Property+case_conc_reverse = ioProperty $ replicateM_ 1000 $ do let len = 128 len' = 66 vec <- M.new len@@ -51,10 +51,10 @@ (replicateM_ 1000 $ reverseInPlace (M.take len' vec)) (replicateM_ 1000 $ reverseInPlace (M.drop len' vec)) wec <- V.unsafeFreeze vec- assertEqual "should be equal" ref wec+ pure $ ref === wec -case_conc_zip :: IO ()-case_conc_zip = replicateM_ 1000 $ do+case_conc_zip :: Property+case_conc_zip = ioProperty $ replicateM_ 1000 $ do let len = 128 len' = 37 vec <- M.replicate len (Bit True)@@ -63,4 +63,4 @@ (replicateM_ 1001 $ zipInPlace (const complement) ref (M.take len' vec)) (replicateM_ 1001 $ zipInPlace (const complement) ref (M.drop len' vec)) wec <- V.unsafeFreeze vec- assertEqual "should be equal" ref wec+ pure $ ref === wec
test/Tests/F2Poly.hs view
@@ -50,6 +50,7 @@ , testProperty "fromNegative" prop_f2polyFromNegative , testProperty "divideByZero" prop_f2polyDivideByZero , testProperty "toRational" prop_f2polyToRational+ , testProperty "signum" $ \x -> x + signum x === (x + 1 :: F2Poly) ] prop_f2polyAdd :: F2Poly -> F2Poly -> Property
test/Tests/MVector.hs view
@@ -22,7 +22,6 @@ import qualified Data.Vector.Unboxed as U import qualified Data.Vector.Unboxed.Mutable as M import Test.Tasty-import Test.Tasty.HUnit import Test.Tasty.QuickCheck #ifdef MIN_VERSION_quickcheck_classes@@ -49,23 +48,23 @@ #ifdef MIN_VERSION_quickcheck_classes , lawsToTest' $ muvectorLaws (Proxy :: Proxy Bit) #endif- , testCase "basicInitialize 1" case_write_init_read1- , testCase "basicInitialize 2" case_write_init_read2- , testCase "basicInitialize 3" case_write_init_read3- , testCase "basicInitialize 4" case_write_init_read4- , testCase "basicSet 1" case_write_set_read1- , testCase "basicSet 2" case_write_set_read2- , testCase "basicSet 3" case_write_set_read3- , testCase "basicSet 4" case_write_set_read4- , testCase "basicSet 5" case_set_read1- , testCase "basicSet 6" case_set_read2- , testCase "basicSet 7" case_set_read3- , testCase "basicSet 8" case_set_read4- , testCase "basicUnsafeCopy1" case_write_copy_read1- , testCase "basicUnsafeCopy2" case_write_copy_read2- , testCase "basicUnsafeCopy3" case_write_copy_read3- , testCase "basicUnsafeCopy4" case_write_copy_read4- , testCase "basicUnsafeCopy5" case_write_copy_read5+ , testProperty "basicInitialize 1" case_write_init_read1+ , testProperty "basicInitialize 2" case_write_init_read2+ , testProperty "basicInitialize 3" case_write_init_read3+ , testProperty "basicInitialize 4" case_write_init_read4+ , testProperty "basicSet 1" case_write_set_read1+ , testProperty "basicSet 2" case_write_set_read2+ , testProperty "basicSet 3" case_write_set_read3+ , testProperty "basicSet 4" case_write_set_read4+ , testProperty "basicSet 5" case_set_read1+ , testProperty "basicSet 6" case_set_read2+ , testProperty "basicSet 7" case_set_read3+ , testProperty "basicSet 8" case_set_read4+ , testProperty "basicUnsafeCopy1" case_write_copy_read1+ , testProperty "basicUnsafeCopy2" case_write_copy_read2+ , testProperty "basicUnsafeCopy3" case_write_copy_read3+ , testProperty "basicUnsafeCopy4" case_write_copy_read4+ , testProperty "basicUnsafeCopy5" case_write_copy_read5 , tenTimesLess $ testProperty "flipBit" prop_flipBit , testProperty "new negative" prop_new_neg@@ -79,128 +78,128 @@ ys = U.modify (\v -> M.modify v complement k') xs ys' = U.modify (\v -> flipBit v k') xs -case_write_init_read1 :: IO ()-case_write_init_read1 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_init_read1 :: Property+case_write_init_read1 = (=== Bit True) $ runST $ do arr <- M.new 2 M.write arr 0 (Bit True) MG.basicInitialize (M.slice 1 1 arr) M.read arr 0 -case_write_init_read2 :: IO ()-case_write_init_read2 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_init_read2 :: Property+case_write_init_read2 = (=== Bit True) $ runST $ do arr <- M.new 2 M.write arr 1 (Bit True) MG.basicInitialize (M.slice 0 1 arr) M.read arr 1 -case_write_init_read3 :: IO ()+case_write_init_read3 :: Property case_write_init_read3 =- assertEqual "should be equal" (Bit True, Bit True) $ runST $ do+ (=== (Bit True, Bit True)) $ runST $ do arr <- M.new 2 M.write arr 0 (Bit True) M.write arr 1 (Bit True) MG.basicInitialize (M.slice 1 0 arr) (,) <$> M.read arr 0 <*> M.read arr 1 -case_write_init_read4 :: IO ()+case_write_init_read4 :: Property case_write_init_read4 =- assertEqual "should be equal" (Bit True, Bit True) $ runST $ do+ (=== (Bit True, Bit True)) $ runST $ do arr <- M.new 3 M.write arr 0 (Bit True) M.write arr 2 (Bit True) MG.basicInitialize (M.slice 1 1 arr) (,) <$> M.read arr 0 <*> M.read arr 2 -case_write_set_read1 :: IO ()-case_write_set_read1 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_set_read1 :: Property+case_write_set_read1 = (=== Bit True) $ runST $ do arr <- M.new 2 M.write arr 0 (Bit True) MG.basicSet (M.slice 1 1 arr) (Bit False) M.read arr 0 -case_write_set_read2 :: IO ()-case_write_set_read2 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_set_read2 :: Property+case_write_set_read2 = (=== Bit True) $ runST $ do arr <- M.new 2 M.write arr 1 (Bit True) MG.basicSet (M.slice 0 1 arr) (Bit False) M.read arr 1 -case_write_set_read3 :: IO ()+case_write_set_read3 :: Property case_write_set_read3 =- assertEqual "should be equal" (Bit True, Bit True) $ runST $ do+ (=== (Bit True, Bit True)) $ runST $ do arr <- M.new 2 M.write arr 0 (Bit True) M.write arr 1 (Bit True) MG.basicSet (M.slice 1 0 arr) (Bit False) (,) <$> M.read arr 0 <*> M.read arr 1 -case_write_set_read4 :: IO ()+case_write_set_read4 :: Property case_write_set_read4 =- assertEqual "should be equal" (Bit True, Bit True) $ runST $ do+ (=== (Bit True, Bit True)) $ runST $ do arr <- M.new 3 M.write arr 0 (Bit True) M.write arr 2 (Bit True) MG.basicSet (M.slice 1 1 arr) (Bit False) (,) <$> M.read arr 0 <*> M.read arr 2 -case_set_read1 :: IO ()-case_set_read1 = assertEqual "should be equal" (Bit True) $ runST $ do+case_set_read1 :: Property+case_set_read1 = (=== Bit True) $ runST $ do arr <- M.new 1 MG.basicSet arr (Bit True) M.read arr 0 -case_set_read2 :: IO ()-case_set_read2 = assertEqual "should be equal" (Bit True) $ runST $ do+case_set_read2 :: Property+case_set_read2 = (=== Bit True) $ runST $ do arr <- M.new 2 MG.basicSet (M.slice 1 1 arr) (Bit True) M.read arr 1 -case_set_read3 :: IO ()-case_set_read3 = assertEqual "should be equal" (Bit True) $ runST $ do+case_set_read3 :: Property+case_set_read3 = (=== Bit True) $ runST $ do arr <- M.new 192 MG.basicSet (M.slice 71 121 arr) (Bit True) M.read arr 145 -case_set_read4 :: IO ()-case_set_read4 = assertEqual "should be equal" (Bit True) $ runST $ do+case_set_read4 :: Property+case_set_read4 = (=== Bit True) $ runST $ do arr <- M.slice 27 38 <$> M.new 65 MG.basicSet arr (Bit True) M.read arr 21 -case_write_copy_read1 :: IO ()-case_write_copy_read1 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_copy_read1 :: Property+case_write_copy_read1 = (=== Bit True) $ runST $ do src <- M.slice 37 28 <$> M.new 65 M.write src 27 (Bit True) dst <- M.slice 37 28 <$> M.new 65 M.copy dst src M.read dst 27 -case_write_copy_read2 :: IO ()-case_write_copy_read2 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_copy_read2 :: Property+case_write_copy_read2 = (=== Bit True) $ runST $ do src <- M.slice 32 33 <$> M.new 65 M.write src 0 (Bit True) dst <- M.slice 32 33 <$> M.new 65 M.copy dst src M.read dst 0 -case_write_copy_read3 :: IO ()-case_write_copy_read3 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_copy_read3 :: Property+case_write_copy_read3 = (=== Bit True) $ runST $ do src <- M.slice 1 1 <$> M.new 2 M.write src 0 (Bit True) dst <- M.slice 1 1 <$> M.new 2 M.copy dst src M.read dst 0 -case_write_copy_read4 :: IO ()-case_write_copy_read4 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_copy_read4 :: Property+case_write_copy_read4 = (=== Bit True) $ runST $ do src <- M.slice 12 52 <$> M.new 64 M.write src 22 (Bit True) dst <- M.slice 12 52 <$> M.new 64 M.copy dst src M.read dst 22 -case_write_copy_read5 :: IO ()-case_write_copy_read5 = assertEqual "should be equal" (Bit True) $ runST $ do+case_write_copy_read5 :: Property+case_write_copy_read5 = (=== Bit True) $ runST $ do src <- M.slice 48 80 <$> M.new 128 M.write src 46 (Bit True) dst <- M.slice 48 80 <$> M.new 128