bv-0.4.1: Bit-vector arithmetic library

Copyright(c) 2012-2016 Iago Abal
(c) 2012-2013 HASLab & University of Minho
LicenseBSD3
MaintainerIago Abal <mail@iagoabal.eu>
Safe HaskellNone
LanguageHaskell98

Data.BitVector

Contents

Description

Bit-vector arithmetic inspired by SMT-LIB http://smt-lib.org/ and Cryptol http://cryptol.net/.

Bit-vectors are represented as a pair size and value, where sizes are of type Int and values are Integer.

  • Bit-vectors are interpreted as unsigned integers (i.e. natural numbers) except for some specific signed operations.
  • Most operations are in some way size-polymorphic and, if required, will perform padding to adjust the size of input bit-vectors.

For documentation purposes we will write [n]k to denote a bit-vector of size n representing the natural number k.

Synopsis

Bit-vectors

type BitVector = BV #

An alias for BV.

data BV #

Big-endian pseudo size-polymorphic bit-vectors.

Instances

Enum BV # 

Methods

succ :: BV -> BV #

pred :: BV -> BV #

toEnum :: Int -> BV #

fromEnum :: BV -> Int #

enumFrom :: BV -> [BV] #

enumFromThen :: BV -> BV -> [BV] #

enumFromTo :: BV -> BV -> [BV] #

enumFromThenTo :: BV -> BV -> BV -> [BV] #

Eq BV # 

Methods

(==) :: BV -> BV -> Bool #

(/=) :: BV -> BV -> Bool #

Integral BV # 

Methods

quot :: BV -> BV -> BV #

rem :: BV -> BV -> BV #

div :: BV -> BV -> BV #

mod :: BV -> BV -> BV #

quotRem :: BV -> BV -> (BV, BV) #

divMod :: BV -> BV -> (BV, BV) #

toInteger :: BV -> Integer #

Data BV # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> BV -> c BV #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c BV #

toConstr :: BV -> Constr #

dataTypeOf :: BV -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c BV) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c BV) #

gmapT :: (forall b. Data b => b -> b) -> BV -> BV #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> BV -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> BV -> r #

gmapQ :: (forall d. Data d => d -> u) -> BV -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> BV -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> BV -> m BV #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> BV -> m BV #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> BV -> m BV #

Num BV # 

Methods

(+) :: BV -> BV -> BV #

(-) :: BV -> BV -> BV #

(*) :: BV -> BV -> BV #

negate :: BV -> BV #

abs :: BV -> BV #

signum :: BV -> BV #

fromInteger :: Integer -> BV #

Ord BV # 

Methods

compare :: BV -> BV -> Ordering #

(<) :: BV -> BV -> Bool #

(<=) :: BV -> BV -> Bool #

(>) :: BV -> BV -> Bool #

(>=) :: BV -> BV -> Bool #

max :: BV -> BV -> BV #

min :: BV -> BV -> BV #

Real BV # 

Methods

toRational :: BV -> Rational #

Show BV # 

Methods

showsPrec :: Int -> BV -> ShowS #

show :: BV -> String #

showList :: [BV] -> ShowS #

Monoid BV # 

Methods

mempty :: BV #

mappend :: BV -> BV -> BV #

mconcat :: [BV] -> BV #

Bits BV # 

Methods

(.&.) :: BV -> BV -> BV #

(.|.) :: BV -> BV -> BV #

xor :: BV -> BV -> BV #

complement :: BV -> BV #

shift :: BV -> Int -> BV #

rotate :: BV -> Int -> BV #

zeroBits :: BV #

bit :: Int -> BV #

setBit :: BV -> Int -> BV #

clearBit :: BV -> Int -> BV #

complementBit :: BV -> Int -> BV #

testBit :: BV -> Int -> Bool #

bitSizeMaybe :: BV -> Maybe Int #

bitSize :: BV -> Int #

isSigned :: BV -> Bool #

shiftL :: BV -> Int -> BV #

unsafeShiftL :: BV -> Int -> BV #

shiftR :: BV -> Int -> BV #

unsafeShiftR :: BV -> Int -> BV #

rotateL :: BV -> Int -> BV #

rotateR :: BV -> Int -> BV #

popCount :: BV -> Int #

size :: BV -> Int #

The size of a bit-vector.

width :: BV -> Int #

An alias for size.

nat :: BV -> Integer #

The value of a bit-vector, as a natural number.

uint :: BV -> Integer #

An alias for nat.

int :: BV -> Integer #

2's complement value of a bit-vector.

>>> int [2]3
-1

>>> int [4]12
-4

Creation

nil :: BV #

The empty bit-vector, ie. [0]0.

bitVec :: Integral a => Int -> a -> BV #

Create a bit-vector given a size and an integer value.

>>> bitVec 4 3
[4]3

This function also handles negative values.

>>> bitVec 4 (-1)
[4]15

bitVecs :: Integral a => Int -> [a] -> [BV] #

List of bit-vector literals of the same size

When a list of integer literals is interpreted as a list of bit-vectors, fromInteger is applied to each element invidually:

>>> [1,3,5] :: [BV]
[ [1]1, [2]3, [3]5 ]

Sometimes we want to specify a list of bit-vectors literals of the same size, and for that we can use bitVects:

>>> bitVecs 3 [1,3,5]
[ [3]1, [3]3, [3]5 ]

ones :: Int -> BV #

Create a mask of ones.

zeros :: Int -> BV #

Create a mask of zeros.

Test

isNat :: BV -> Bool #

Test if the signed value of a bit-vector is a natural number.

isPos :: BV -> Bool #

Test if the signed value of a bit-vector is a positive number.

Comparison

(==.) :: BV -> BV -> Bool infix 4 #

Fixed-size equality.

In contrast with ==, which is size-polymorphic, this equality requires both bit-vectors to be of equal size.

>>> [n]k ==. [m]k
False

>>> [n]k ==. [n]k
True

(/=.) :: BV -> BV -> Bool infix 4 #

Fixed-size inequality.

The negated version of ==..

(<.) :: BV -> BV -> Bool infix 4 #

Fixed-size less-than.

(<=.) :: BV -> BV -> Bool infix 4 #

Fixed-size less-than-or-equals.

(>.) :: BV -> BV -> Bool infix 4 #

Fixed-size greater-than.

(>=.) :: BV -> BV -> Bool infix 4 #

Fixed-size greater-than-or-equals.

slt :: BV -> BV -> Bool infix 4 #

Fixed-size signed less-than.

sle :: BV -> BV -> Bool infix 4 #

Fixed-size signed less-than-or-equals.

sgt :: BV -> BV -> Bool infix 4 #

Fixed-size signed greater-than.

sge :: BV -> BV -> Bool infix 4 #

Fixed-size signed greater-than-or-equals.

Indexing

(@.) :: Integral ix => BV -> ix -> Bool infixl 9 #

Bit indexing.

u @. i stands for the i-th bit of u.

>>> [4]2 @. 0
False

>>> [4]2 @. 1
True

index :: Integral ix => ix -> BV -> Bool #

index i a == a @. i

(@@) :: Integral ix => BV -> (ix, ix) -> BV infixl 9 #

Bit-string extraction.

u @@ (j,i) == fromBits (map (u @.) [j,j-1..i])
>>> [4]7 @@ (3,1)
[3]3

extract :: Integral ix => ix -> ix -> BV -> BV #

extract j i a == a @@ (j,i)

(@:) :: Integral ix => BV -> [ix] -> BV infixl 9 #

Bit list indexing.

u @: is ==. fromBits $ List.map (u @.) is

(!.) :: Integral ix => BV -> ix -> Bool infixl 9 #

Reverse bit-indexing.

Index starting from the most significant bit.

u !. i == u @. (size u - i - 1)
>>> [3]3 !. 0
False

least :: Integral ix => ix -> BV -> BV #

Take least significant bits.

least m u == u @@ (m-1,0)

most :: Integral ix => ix -> BV -> BV #

Take most significant bits.

most m u == u @@ (n-1,n-m)

msb :: BV -> Bool #

Most significant bit.

msb u == u !. 0

lsb :: BV -> Bool #

Least significant bit.

lsb u == u @. 0

msb1 :: BV -> Int #

Most significant 1-bit.

Pre: input must be non-zero.

>>> msb1 [4]2
1

>>> msb1 [4]4
2

lsb1 :: BV -> Int #

Least significant 1-bit.

Pre: input must be non-zero.

>>> msb1 [4]3
0

>>> msb1 [4]6
1

Arithmetic

signumI :: Integral a => BV -> a #

Bit-vector signum as an Integral.

pow :: Integral exp => BV -> exp -> BV #

Bit-vector exponentiation.

pow [n]k e computes k raised to e modulo n.

This is faster than Haskell's (^) operator because it performs modulo division just once. Besides, a^0 == [1]0 !!!

sdiv :: BV -> BV -> BV #

2's complement signed division.

srem :: BV -> BV -> BV #

2's complement signed remainder (sign follows dividend).

smod :: BV -> BV -> BV #

2's complement signed remainder (sign follows divisor).

lg2 :: BV -> BV #

Ceiling logarithm base 2.

Pre: input bit-vector must be non-zero.

List-like operations

(#) :: BV -> BV -> BV infixr 5 #

Concatenation of two bit-vectors.

cat :: BV -> BV -> BV #

Deprecated: Use (#) or append instead

Concatenation of two bit-vectors.

append :: BV -> BV -> BV #

Concatenation of two bit-vectors.

concat :: [BV] -> BV #

An alias for join.

zeroExtend :: Integral size => size -> BV -> BV #

Logical extension.

>>> zeroExtend 3 [1]1
[4]1

signExtend :: Integral size => size -> BV -> BV #

Arithmetic extension.

>>> signExtend 2 [2]1
[4]1

>>> signExtend 2 [2]3
[4]15

foldl :: (a -> Bool -> a) -> a -> BV -> a #

foldl f z (fromBits [un, ..., u1, u0]) == ((((z `f` un) `f` ...) `f` u1) `f` u0)
foldl f e = fromBits . foldl f e . toBits

foldl_ :: (a -> Bool -> a) -> a -> BV -> a #

Deprecated: Use corresponding versions without underscore

foldl f z (fromBits [un, ..., u1, u0]) == ((((z `f` un) `f` ...) `f` u1) `f` u0)
foldl f e = fromBits . foldl f e . toBits

foldr :: (Bool -> a -> a) -> a -> BV -> a #

foldr f z (fromBits [un, ..., u1, u0]) == un `f` (... `f` (u1 `f` (u0 `f` z)))
foldr f e = fromBits . foldr f e . toBits

foldr_ :: (Bool -> a -> a) -> a -> BV -> a #

Deprecated: Use corresponding versions without underscore

foldr f z (fromBits [un, ..., u1, u0]) == un `f` (... `f` (u1 `f` (u0 `f` z)))
foldr f e = fromBits . foldr f e . toBits

reverse :: BV -> BV #

reverse == fromBits . reverse . toBits

reverse_ :: BV -> BV #

Deprecated: Use corresponding versions without underscore

reverse == fromBits . reverse . toBits

replicate :: Integral size => size -> BV -> BV #

Pre: if replicate_ n u then n > 0 must hold.

replicate_ n == fromBits . concat . replicate n . toBits

replicate_ :: Integral size => size -> BV -> BV #

Deprecated: Use corresponding versions without underscore

Pre: if replicate_ n u then n > 0 must hold.

replicate_ n == fromBits . concat . replicate n . toBits

and :: [BV] -> BV #

Conjunction.

Essentially, and == foldr1 (.&.).

Returns [1]1 if the input list is empty.

and_ :: [BV] -> BV #

Deprecated: Use corresponding versions without underscore

Conjunction.

Essentially, and == foldr1 (.&.).

Returns [1]1 if the input list is empty.

or :: [BV] -> BV #

Disjunction.

Essentially, or == foldr1 (.|.).

Returns [1]0 if the input list is empty.

or_ :: [BV] -> BV #

Deprecated: Use corresponding versions without underscore

Disjunction.

Essentially, or == foldr1 (.|.).

Returns [1]0 if the input list is empty.

split :: Integral times => times -> BV -> [BV] #

Split a bit-vector k times.

>>> split 3 [4]15
[[2]0,[2]3,[2]3]

group :: Integral size => size -> BV -> [BV] #

Split a bit-vector into n-wide pieces.

>>> group 3 [4]15
[[3]1,[3]7]

group_ :: Integral size => size -> BV -> [BV] #

Deprecated: Use corresponding versions without underscore

Split a bit-vector into n-wide pieces.

>>> group 3 [4]15
[[3]1,[3]7]

join :: [BV] -> BV #

Concatenate a (possibly empty) list of bit-vectors.

>>> join [[2]3,[2]2]
[4]14

Bitwise operations

module Data.Bits

not :: BV -> BV #

An alias for complement.

not_ :: BV -> BV #

Deprecated: Use corresponding versions without underscore

An alias for complement.

nand :: BV -> BV -> BV #

Negated .&..

nor :: BV -> BV -> BV #

Negated .|..

xnor :: BV -> BV -> BV #

Negated xor.

(<<.) :: BV -> BV -> BV infixl 8 #

Left shift.

shl :: BV -> BV -> BV infixl 8 #

Left shift.

(>>.) :: BV -> BV -> BV infixl 8 #

Logical right shift.

shr :: BV -> BV -> BV infixl 8 #

Logical right shift.

ashr :: BV -> BV -> BV infixl 8 #

Arithmetic right shift

(<<<.) :: BV -> BV -> BV infixl 8 #

Rotate left.

rol :: BV -> BV -> BV infixl 8 #

Rotate left.

(>>>.) :: BV -> BV -> BV infixl 8 #

Rotate right.

ror :: BV -> BV -> BV infixl 8 #

Rotate right.

Conversion

fromBool :: Bool -> BV #

Create a bit-vector from a single bit.

fromBits :: [Bool] -> BV #

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

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

toBits :: BV -> [Bool] #

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

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

Pretty-printing

showBin :: BV -> String #

Show a bit-vector in binary form.

showOct :: BV -> String #

Show a bit-vector in octal form.

showHex :: BV -> String #

Show a bit-vector in hexadecimal form.