bitwise 0.1.0.2 → 0.1.1
raw patch · 8 files changed
+104/−6 lines, 8 filesdep ~bitwise
Dependency ranges changed: bitwise
Files
- bitwise.cabal +5/−5
- extra/testsuite.hs +5/−0
- ghc70/Compat.hs +5/−0
- ghc74/Compat.hs +2/−0
- hugs98/Compat.hs +5/−0
- src/Data/Array/BitArray.hs +15/−0
- src/Data/Array/BitArray/IO.hs +52/−1
- src/Data/Array/BitArray/ST.hs +15/−0
bitwise.cabal view
@@ -1,5 +1,5 @@ Name: bitwise-Version: 0.1.0.2+Version: 0.1.1 Synopsis: fast multi-dimensional unboxed bit packed Bool arrays Description: Unboxed multidimensional bit packed Bool arrays with fast aggregate@@ -50,7 +50,7 @@ License-file: LICENSE Author: Claude Heiland-Allen Maintainer: claude@mathr.co.uk-Copyright: (c) 2012 Claude Heiland-Allen+Copyright: (c) 2012,2016 Claude Heiland-Allen Category: Data, Data Structures, Bit Vectors Build-type: Simple @@ -91,7 +91,7 @@ type: exitcode-stdio-1.0 main-is: extra/testsuite.hs build-depends:- bitwise == 0.1.0.2,+ bitwise == 0.1.1, base >= 2 && < 4.9, QuickCheck >= 2.4 && < 2.9 @@ -99,7 +99,7 @@ type: exitcode-stdio-1.0 main-is: extra/benchmark.hs build-depends:- bitwise == 0.1.0.2,+ bitwise == 0.1.1, base >= 2 && < 4.9, array, bytestring,@@ -112,4 +112,4 @@ source-repository this type: git location: http://code.mathr.co.uk/bitwise.git- tag: v0.1.0.2+ tag: v0.1.1
extra/testsuite.hs view
@@ -3,6 +3,7 @@ import Prelude hiding (any, all, and, or, map, zipWith) import qualified Prelude as P+import qualified Data.List as P import Data.Ix (inRange, range) import Data.Function (on)@@ -59,6 +60,10 @@ prop_true1 o w = let n = fromW w in Just True == isUniform (true (o, o + n)) prop_false1 o w = let n = fromW w in Just False == isUniform (false (o, o + n))++prop_elemIndex b o es = (fmap (+ o) . P.elemIndex b) es == (elemIndex b . listArray (o, o + length es - 1)) es++prop_popCount o es = (P.length . P.filter id) es == (popCount . listArray (o, o + length es - 1)) es listUniform l | null l = Nothing
ghc70/Compat.hs view
@@ -3,8 +3,13 @@ , uncons , packCStringLen , unsafeUseAsCStringLen+ , popCount ) where import Control.Monad.ST (unsafeIOToST) import Data.ByteString (uncons, packCStringLen) import Data.ByteString.Unsafe (unsafeUseAsCStringLen)+import Data.Bits ((.&.), shiftR)++popCount :: Word64 -> Int+popCount = fromIntegral . sum . map (.&. 1) . take 64 . iterate (`shiftR` 1)
ghc74/Compat.hs view
@@ -3,8 +3,10 @@ , uncons , packCStringLen , unsafeUseAsCStringLen+ , popCount ) where import Control.Monad.ST.Unsafe (unsafeIOToST) import Data.ByteString (uncons, packCStringLen) import Data.ByteString.Unsafe (unsafeUseAsCStringLen)+import Data.Bits (popCount)
hugs98/Compat.hs view
@@ -3,9 +3,11 @@ , uncons , packCStringLen , unsafeUseAsCStringLen+ , popCount ) where import Control.Monad.ST (unsafeIOToST)+import Data.Bits ((.&,), shiftR) import qualified Data.ByteString as BS import Data.Word (Word8) import Foreign.C.String (CStringLen)@@ -18,3 +20,6 @@ packCStringLen :: CStringLen -> IO BS.ByteString packCStringLen = return . BS.packCStringLen++popCount :: Word64 -> Int+popCount = fromIntegral . sum . map (.&. 1) . take 64 . iterate (`shiftR` 1)
src/Data/Array/BitArray.hs view
@@ -37,10 +37,12 @@ , or , and , isUniform+ , elemIndex -- * Aggregate operations. , fold , map , zipWith+ , popCount -- * Bounds-checked indexing. , (!?) -- * Unsafe.@@ -170,6 +172,14 @@ isUniform :: Ix i => BitArray i -> Maybe Bool isUniform a = runST (ST.isUniform =<< ST.unsafeThaw a) +-- | Look up index of first matching bit.+--+-- Note that the index type is limited to Int because there+-- is no 'unindex' method in the 'Ix' class.+{-# INLINE elemIndex #-}+elemIndex :: Bool -> BitArray Int -> Maybe Int+elemIndex b a = runST (ST.elemIndex b =<< ST.unsafeThaw a)+ -- | Bitwise reduction with an associative commutative boolean operator. -- Implementation lifts from 'Bool' to 'Bits' and folds large chunks -- at a time. Each bit is used as a source exactly once.@@ -195,3 +205,8 @@ b' <- ST.unsafeThaw b ST.unsafeFreeze =<< ST.zipWith f a' b') | otherwise = error "zipWith bounds mismatch"++-- | Count set bits.+{-# INLINE popCount #-}+popCount :: Ix i => BitArray i -> Int+popCount a = runST (ST.popCount =<< ST.unsafeThaw a)
src/Data/Array/BitArray/IO.hs view
@@ -34,10 +34,12 @@ , or , and , isUniform+ , elemIndex -- * Aggregate operations. , fold , map , zipWith+ , popCount -- * Unsafe. , unsafeReadArray , unsafeGetElems@@ -48,7 +50,7 @@ import Prelude hiding (and, or, map, zipWith) import Control.Monad (forM_, when)-import Data.Bits (shiftR, testBit, setBit, clearBit, (.&.), complement)+import Data.Bits (shiftL, shiftR, testBit, setBit, clearBit, (.&.), complement) import Data.Ix (Ix, index, inRange, range, rangeSize) import Data.List (foldl1') import Data.Word (Word8, Word64)@@ -59,6 +61,7 @@ import Data.Bits.Bitwise (packWord8LE, mask) import qualified Data.Bits.Bitwise as Bitwise+import qualified Compat as Compat import Data.Array.BitArray.Internal ( IOBitArray(..)@@ -258,6 +261,33 @@ | otherwise = return Nothing withForeignPtr (iobData a) $ \p -> loop p 0 False False +-- | Look up index of first matching bit.+--+-- Note that the index type is limited to Int because there+-- is no 'unindex' method in the 'Ix' class.+{-# INLINE elemIndex #-}+elemIndex :: Bool -> IOBitArray Int -> IO (Maybe Int)+elemIndex which a = do+ bs <- getBounds a+ let skip :: Word64+ skip | which = 0+ | otherwise = complement 0+ total = rangeSize bs+ full = total .&. complement (mask 6)+ count = full `shiftR` 6+ loop :: Ptr Word64 -> Int -> IO (Maybe Int)+ loop p n+ | n < count = do+ w <- peekElemOff p n+ if w /= skip then rest (n `shiftL` 6) else loop p (n + 1)+ | otherwise = rest full+ rest m+ | m < total = do+ b <- readArrayRaw a m+ if b == which then return (Just (fst bs + m)) else rest (m + 1)+ | otherwise = return Nothing+ withForeignPtr (iobData a) $ \p -> loop p 0+ -- | Bitwise reduction with an associative commutative boolean operator. -- Implementation lifts from 'Bool' to 'Bits' and folds large chunks -- at a time. Each bit is used as a source exactly once.@@ -346,3 +376,24 @@ p <- peekElemOff lp n q <- peekElemOff rp n pokeElemOff dp n (g p q)++-- | Count set bits.+{-# INLINE popCount #-}+popCount :: Ix i => IOBitArray i -> IO Int+popCount a = do+ bs <- getBounds a+ let total = rangeSize bs+ full = total .&. complement (mask 6)+ count = full `shiftR` 6+ loop :: Ptr Word64 -> Int -> Int -> IO Int+ loop p n acc+ | n < count = acc `seq` do+ w <- peekElemOff p n+ loop p (n + 1) (acc + Compat.popCount w)+ | otherwise = rest full acc+ rest m acc+ | m < total = acc `seq` do+ b <- readArrayRaw a m+ rest (m + 1) (acc + fromEnum b)+ | otherwise = return acc+ withForeignPtr (iobData a) $ \p -> loop p 0 0
src/Data/Array/BitArray/ST.hs view
@@ -35,10 +35,12 @@ , or , and , isUniform+ , elemIndex -- * Aggregate operations. , fold , map , zipWith+ , popCount -- * Unsafe. , unsafeReadArray , unsafeGetElems@@ -167,6 +169,14 @@ isUniform :: Ix i => STBitArray s i -> ST s (Maybe Bool) isUniform (STB a) = unsafeIOToST (IO.isUniform a) +-- | Look up index of first matching bit.+--+-- Note that the index type is limited to Int because there+-- is no 'unindex' method in the 'Ix' class.+{-# INLINE elemIndex #-}+elemIndex :: Bool -> STBitArray s Int -> ST s (Maybe Int)+elemIndex b (STB a) = unsafeIOToST (IO.elemIndex b a)+ -- | Bitwise reduction with an associative commutative boolean operator. -- Implementation lifts from 'Bool' to 'Bits' and folds large chunks -- at a time. Each bit is used as a source exactly once.@@ -187,3 +197,8 @@ {-# INLINE zipWith #-} zipWith :: Ix i => (Bool -> Bool -> Bool) -> STBitArray s i -> STBitArray s i -> ST s (STBitArray s i) zipWith f (STB a) (STB b) = STB `fmap` unsafeIOToST (IO.zipWith f a b)++-- | Count set bits.+{-# INLINE popCount #-}+popCount :: Ix i => STBitArray s i -> ST s Int+popCount (STB a) = unsafeIOToST (IO.popCount a)