Copyright	(c) Alex Washburn 2018
License	BSD-style
Maintainer	github@recursion.ninja
Stability	provisional
Portability	portable
Safe Haskell	Trustworthy
Language	Haskell2010

Data.BitVector.LittleEndian

Contents

Bit-stream conversion
Numeric conversion
Queries

Description

A bit vector similar to Data.BitVector from the bv, however the endianness is reversed. This module defines little-endian pseudo–size-polymorphic bit vectors.

Little-endian bit vectors are isomorphic to a [Bool] with the least significant bit at the head of the list and the most significant bit at the end of the list. Consequently, the endianness of a bit vector affects the semantics of the following typeclasses:

For an implementation of bit vectors which are isomorphic to a [Bool] with the most significant bit at the head of the list and the least significant bit at the end of the list, use the bv package.

This module does not define numeric instances for BitVector. This is intentional! To interact with a bit vector as an Integral value, convert the BitVector using either toSignedNumber or toUnsignedNumber.

Synopsis

Documentation

data BitVector Source #

A little-endian bit vector of non-negative dimension.

Instances

Eq BitVector Source #	Since: 0.1.0.0
Methods (==) :: BitVector -> BitVector -> Bool # (/=) :: BitVector -> BitVector -> Bool #
Data BitVector Source #
Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> BitVector -> c BitVector # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c BitVector # toConstr :: BitVector -> Constr # dataTypeOf :: BitVector -> DataType # dataCast1 :: Typeable (* -> ) t => (forall d. Data d => c (t d)) -> Maybe (c BitVector) # dataCast2 :: Typeable ( -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c BitVector) # gmapT :: (forall b. Data b => b -> b) -> BitVector -> BitVector # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> BitVector -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> BitVector -> r # gmapQ :: (forall d. Data d => d -> u) -> BitVector -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> BitVector -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> BitVector -> m BitVector # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> BitVector -> m BitVector # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> BitVector -> m BitVector #
Ord BitVector Source #	Since: 0.1.0.0
Methods compare :: BitVector -> BitVector -> Ordering # (<) :: BitVector -> BitVector -> Bool # (<=) :: BitVector -> BitVector -> Bool # (>) :: BitVector -> BitVector -> Bool # (>=) :: BitVector -> BitVector -> Bool # max :: BitVector -> BitVector -> BitVector # min :: BitVector -> BitVector -> BitVector #
Show BitVector Source #	Since: 0.1.0.0
Methods showsPrec :: Int -> BitVector -> ShowS # show :: BitVector -> String # showList :: [BitVector] -> ShowS #
Generic BitVector Source #
Associated Types type Rep BitVector :: * -> * # Methods from :: BitVector -> Rep BitVector x # to :: Rep BitVector x -> BitVector #
Semigroup BitVector Source #	Since: 0.1.0.0
Methods (<>) :: BitVector -> BitVector -> BitVector # sconcat :: NonEmpty BitVector -> BitVector # stimes :: Integral b => b -> BitVector -> BitVector #
Monoid BitVector Source #	Since: 0.1.0.0
Methods mempty :: BitVector # mappend :: BitVector -> BitVector -> BitVector # mconcat :: [BitVector] -> BitVector #
Arbitrary BitVector Source #	Since: 0.1.0.0
Methods arbitrary :: Gen BitVector # shrink :: BitVector -> [BitVector] #
CoArbitrary BitVector Source #	Since: 0.1.0.0
Methods coarbitrary :: BitVector -> Gen b -> Gen b #
Bits BitVector Source #	Since: 0.1.0.0
Methods (.&.) :: BitVector -> BitVector -> BitVector # (.\|.) :: BitVector -> BitVector -> BitVector # xor :: BitVector -> BitVector -> BitVector # complement :: BitVector -> BitVector # shift :: BitVector -> Int -> BitVector # rotate :: BitVector -> Int -> BitVector # zeroBits :: BitVector # bit :: Int -> BitVector # setBit :: BitVector -> Int -> BitVector # clearBit :: BitVector -> Int -> BitVector # complementBit :: BitVector -> Int -> BitVector # testBit :: BitVector -> Int -> Bool # bitSizeMaybe :: BitVector -> Maybe Int # bitSize :: BitVector -> Int # isSigned :: BitVector -> Bool # shiftL :: BitVector -> Int -> BitVector # unsafeShiftL :: BitVector -> Int -> BitVector # shiftR :: BitVector -> Int -> BitVector # unsafeShiftR :: BitVector -> Int -> BitVector # rotateL :: BitVector -> Int -> BitVector # rotateR :: BitVector -> Int -> BitVector # popCount :: BitVector -> Int #
FiniteBits BitVector Source #	Since: 0.1.0.0
Methods finiteBitSize :: BitVector -> Int # countLeadingZeros :: BitVector -> Int # countTrailingZeros :: BitVector -> Int #
NFData BitVector Source #	Since: 0.1.0.0
Methods rnf :: BitVector -> () #
Hashable BitVector Source #	Since: 0.1.0.0
Methods hashWithSalt :: Int -> BitVector -> Int # hash :: BitVector -> Int #
MonoFunctor BitVector Source #	Since: 0.1.0.0
Methods omap :: (Element BitVector -> Element BitVector) -> BitVector -> BitVector #
MonoFoldable BitVector Source #	Since: 0.1.0.0
Methods ofoldMap :: Monoid m => (Element BitVector -> m) -> BitVector -> m # ofoldr :: (Element BitVector -> b -> b) -> b -> BitVector -> b # ofoldl' :: (a -> Element BitVector -> a) -> a -> BitVector -> a # otoList :: BitVector -> [Element BitVector] # oall :: (Element BitVector -> Bool) -> BitVector -> Bool # oany :: (Element BitVector -> Bool) -> BitVector -> Bool # onull :: BitVector -> Bool # olength :: BitVector -> Int # olength64 :: BitVector -> Int64 # ocompareLength :: Integral i => BitVector -> i -> Ordering # otraverse_ :: Applicative f => (Element BitVector -> f b) -> BitVector -> f () # ofor_ :: Applicative f => BitVector -> (Element BitVector -> f b) -> f () # omapM_ :: Applicative m => (Element BitVector -> m ()) -> BitVector -> m () # oforM_ :: Applicative m => BitVector -> (Element BitVector -> m ()) -> m () # ofoldlM :: Monad m => (a -> Element BitVector -> m a) -> a -> BitVector -> m a # ofoldMap1Ex :: Semigroup m => (Element BitVector -> m) -> BitVector -> m # ofoldr1Ex :: (Element BitVector -> Element BitVector -> Element BitVector) -> BitVector -> Element BitVector # ofoldl1Ex' :: (Element BitVector -> Element BitVector -> Element BitVector) -> BitVector -> Element BitVector # headEx :: BitVector -> Element BitVector # lastEx :: BitVector -> Element BitVector # unsafeHead :: BitVector -> Element BitVector # unsafeLast :: BitVector -> Element BitVector # maximumByEx :: (Element BitVector -> Element BitVector -> Ordering) -> BitVector -> Element BitVector # minimumByEx :: (Element BitVector -> Element BitVector -> Ordering) -> BitVector -> Element BitVector # oelem :: Element BitVector -> BitVector -> Bool # onotElem :: Element BitVector -> BitVector -> Bool #
MonoTraversable BitVector Source #	Since: 0.1.0.0
Methods otraverse :: Applicative f => (Element BitVector -> f (Element BitVector)) -> BitVector -> f BitVector # omapM :: Applicative m => (Element BitVector -> m (Element BitVector)) -> BitVector -> m BitVector #
type Rep BitVector Source #
type Rep BitVector = D1 * (MetaData "BitVector" "Data.BitVector.LittleEndian" "bv-little-0.1.1-5yvsx0TiDQxtgPQRdM2YE" False) (C1 * (MetaCons "BV" PrefixI True) ((::) (S1 * (MetaSel (Just Symbol "dim") SourceUnpack SourceStrict DecidedStrict) (Rec0 * Word)) (S1 * (MetaSel (Just Symbol "nat") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * Natural))))
type Element BitVector Source #
type Element BitVector = Bool

Bit-stream conversion

fromBits :: Foldable f => f Bool -> BitVector Source #

Create a bit vector from a little-endian list of bits.

The following will hold:

length . takeWhile not === countLeadingZeros . fromBits
length . takeWhile not . reverse === countTrailingZeros . fromBits

Time: \(\, \mathcal{O} \left( n \right) \)

Since: 0.1.0.0

Examples

>>> fromBits [True, False, False]
[3]1

toBits :: BitVector -> [Bool] Source #

Create a little-endian list of bits from a bit vector.

The following will hold:

length . takeWhile not . toBits === countLeadingZeros
length . takeWhile not . reverse . toBits === countTrailingZeros

Time: \(\, \mathcal{O} \left( n \right) \)

Since: 0.1.0.0

Examples

>>> toBits [4]11
[True, True, False, True]

Numeric conversion

fromNumber Source #

Arguments

:: Integral v
=> Word	dimension of bit vector
-> v	signed, little-endian integral value
-> BitVector

Create a bit vector of non-negative dimension from an integral value.

The integral value will be treated as an signed number and the resulting bit vector will contain the two's complement bit representation of the number.

The integral value will be interpreted as little-endian so that the least significant bit of the integral value will be the value of the 0th index of the resulting bit vector and the most significant bit of the integral value will be at index dimension − 1.

Note that if the bit representation of the integral value exceeds the supplied dimension, then the most significant bits will be truncated in the resulting bit vector.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> fromNumber 8 96
[8]96

>>> fromNumber 8 -96
[8]160

>>> fromNumber 6 96
[6]32

toSignedNumber :: Num a => BitVector -> a Source #

Two's complement value of a bit vector.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> toSignedNumber [4]0
0

>>> toSignedNumber [4]3
3

>>> toSignedNumber [4]7
7

>>> toSignedNumber [4]8
-8

>>> toSignedNumber [4]12
-4

>>> toSignedNumber [4]15
-1

toUnsignedNumber :: Num a => BitVector -> a Source #

Unsigned value of a bit vector.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> toSignedNumber [4]0
0

>>> toSignedNumber [4]3
3

>>> toSignedNumber [4]7
7

>>> toSignedNumber [4]8
8

>>> toSignedNumber [4]12
12

>>> toSignedNumber [4]15
15

Queries

dimension :: BitVector -> Word Source #

Get the dimension of a BitVector. Preferable to finiteBitSize as it returns a type which cannot represent a non-negative value and a BitVector must have a non-negative dimension.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> dimension [2]3
2

>>> dimension [4]12
4

isZeroVector :: BitVector -> Bool Source #

Determine if any bits are set in the BitVector. Faster than (0 ==) . popCount.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> isZeroVector [2]3
False

>>> isZeroVector [4]0
True

subRange :: (Word, Word) -> BitVector -> BitVector Source #

Get the inclusive range of bits in BitVector as a new BitVector.

If either of the bounds of the subrange exceed the bit vector's dimension, the resulting subrange will append an infinite number of zeroes to the end of the bit vector in order to satisfy the subrange request.

Time: \(\, \mathcal{O} \left( 1 \right) \)

Since: 0.1.0.0

Examples

>>> subRange (0,2) [4]7
[3]7

>>> subRange (1, 3) [4]7
[3]3

>>> subRange (2, 4) [4]7
[3]1

>>> subRange (3, 5) [4]7
[3]0

>>> subRange (10, 20) [4]7
[10]0