We define bitvectors. We choose the Fin representation over others for its relative efficiency (Lean has special support for Nat), alignment with UIntXY types which are also represented with Fin, and the fact that bitwise operations on Fin are already defined. Some other possible representations are List Bool, { l : List Bool // l.length = w }, Fin w → Bool.

We define many of the bitvector operations from the QF_BV logic. of SMT-LIBv2.

structure BitVec (w : Nat) : Type

A bitvector of the specified width.

This is represented as the underlying Nat number in both the runtime and the kernel, inheriting all the special support for Nat.

• ofFin :: (
• toFin : Fin (2 ^ w)

  Interpret a bitvector as a number less than 2^w. O(1), because we use Fin as the internal representation of a bitvector.

• )

def BitVec.decEq {n : Nat} (x : BitVec n) (y : BitVec n) : Decidable (x = y)

Bitvectors have decidable equality. This should be used via the instance DecidableEq (BitVec n).

Equations

• { toFin := n_1 }.decEq { toFin := m } = if h : n_1 = m then isTrue ⋯ else isFalse ⋯

instance instDecidableEqBitVec {n : Nat} : DecidableEq (BitVec n)

Equations

• instDecidableEqBitVec = BitVec.decEq

@[match_pattern]

def BitVec.ofNatLt {n : Nat} (i : Nat) (p : i < 2 ^ n) : BitVec n

The BitVec with value i, given a proof that i < 2^n.

Equations

• i#'p = { toFin := ⟨i, p⟩ }

@[match_pattern]

def BitVec.ofNat (n : Nat) (i : Nat) : BitVec n

The BitVec with value i mod 2^n.

Equations

• BitVec.ofNat n i = { toFin := Fin.ofNat' (2 ^ n) i }

instance BitVec.instOfNat {n : Nat} {i : Nat} : OfNat (BitVec n) i

Equations

• BitVec.instOfNat = { ofNat := BitVec.ofNat n i }

instance BitVec.natCastInst {w : Nat} : NatCast (BitVec w)

Equations

• BitVec.natCastInst = { natCast := BitVec.ofNat w }

def BitVec.toNat {n : Nat} (x : BitVec n) : Nat

Given a bitvector x, return the underlying Nat. This is O(1) because BitVec is a (zero-cost) wrapper around a Nat.

Equations

• x.toNat = ↑x.toFin

theorem BitVec.isLt {w : Nat} (x : BitVec w) : x.toNat < 2 ^ w

Return the bound in terms of toNat.

@[deprecated BitVec.isLt]

theorem BitVec.toNat_lt {n : Nat} (x : BitVec n) : x.toNat < 2 ^ n

@[simp]

theorem BitVec.ofNat_eq_ofNat {n : Nat} {i : Nat} : OfNat.ofNat i = BitVec.ofNat n i

Theorem for normalizing the bit vector literal representation.

@[simp]

theorem BitVec.natCast_eq_ofNat (w : Nat) (x : Nat) : ↑x = BitVec.ofNat w x

instance BitVec.instSubsingletonOfNatNat : Subsingleton (BitVec 0)

All empty bitvectors are equal

Equations

• BitVec.instSubsingletonOfNatNat = ⋯

@[reducible, inline]

abbrev BitVec.nil : BitVec 0

The empty bitvector

Equations

• BitVec.nil = 0

theorem BitVec.eq_nil (x : BitVec 0) : x = BitVec.nil

Every bitvector of length 0 is equal to nil, i.e., there is only one empty bitvector

def BitVec.zero (n : Nat) : BitVec n

Return a bitvector 0 of size n. This is the bitvector with all zero bits.

Equations

• BitVec.zero n = 0#'⋯

instance BitVec.instInhabited {n : Nat} : Inhabited (BitVec n)

Equations

• BitVec.instInhabited = { default := BitVec.zero n }

def BitVec.allOnes (n : Nat) : BitVec n

Bit vector of size n where all bits are 1s

Equations

• BitVec.allOnes n = (2 ^ n - 1)#'⋯

@[inline]

def BitVec.getLsb' {w : Nat} (x : BitVec w) (i : Fin w) : Bool

Return the i-th least significant bit.

This will be renamed getLsb after the existing deprecated alias is removed.

Equations

• x.getLsb' i = x.toNat.testBit ↑i

@[inline]

def BitVec.getLsb? {w : Nat} (x : BitVec w) (i : Nat) : Option Bool

Return the i-th least significant bit or none if i ≥ w.

Equations

• x.getLsb? i = if h : i < w then some (x.getLsb' ⟨i, h⟩) else none

@[inline]

def BitVec.getMsb' {w : Nat} (x : BitVec w) (i : Fin w) : Bool

Return the i-th most significant bit.

This will be renamed getMsb after the existing deprecated alias is removed.

Equations

• x.getMsb' i = x.getLsb' ⟨w - 1 - ↑i, ⋯⟩

@[inline]

def BitVec.getMsb? {w : Nat} (x : BitVec w) (i : Nat) : Option Bool

Return the i-th most significant bit or none if i ≥ w.

Equations

• x.getMsb? i = if h : i < w then some (x.getMsb' ⟨i, h⟩) else none

@[inline]

def BitVec.getLsbD {w : Nat} (x : BitVec w) (i : Nat) : Bool

Return the i-th least significant bit or false if i ≥ w.

Equations

• x.getLsbD i = x.toNat.testBit i

@[deprecated BitVec.getLsbD]

def BitVec.getLsb {w : Nat} (x : BitVec w) (i : Nat) : Bool

Return the i-th least significant bit or false if i ≥ w.

Equations

• x.getLsb i = x.getLsbD i

@[inline]

def BitVec.getMsbD {w : Nat} (x : BitVec w) (i : Nat) : Bool

Return the i-th most significant bit or false if i ≥ w.

Equations

• x.getMsbD i = (decide (i < w) && x.getLsbD (w - 1 - i))

@[deprecated BitVec.getMsbD]

def BitVec.getMsb {w : Nat} (x : BitVec w) (i : Nat) : Bool

Return the i-th most significant bit or false if i ≥ w.

Equations

• x.getMsb i = x.getMsbD i

@[inline]

def BitVec.msb {n : Nat} (x : BitVec n) : Bool

Return most-significant bit in bitvector.

Equations

• x.msb = x.getMsbD 0

instance BitVec.instGetElemNatBoolLt {w : Nat} : GetElem (BitVec w) Nat Bool fun (x : BitVec w) (i : Nat) => i < w

Equations

• BitVec.instGetElemNatBoolLt = { getElem := fun (xs : BitVec w) (i : Nat) (h : i < w) => xs.getLsb' ⟨i, h⟩ }

@[simp]

theorem BitVec.getLsb'_eq_getElem {w : Nat} (x : BitVec w) (i : Fin w) : x.getLsb' i = x[i]

We prefer x[i] as the simp normal form for getLsb'

@[simp]

theorem BitVec.getLsb?_eq_getElem? {w : Nat} (x : BitVec w) (i : Nat) : x.getLsb? i = x[i]?

We prefer x[i]? as the simp normal form for getLsb?

theorem BitVec.getElem_eq_testBit_toNat {w : Nat} (x : BitVec w) (i : Nat) (h : i < w) : x[i] = x.toNat.testBit i

theorem BitVec.getLsbD_eq_getElem {w : Nat} {x : BitVec w} {i : Nat} (h : i < w) : x.getLsbD i = x[i]

def BitVec.toInt {n : Nat} (x : BitVec n) : Int

Interpret the bitvector as an integer stored in two's complement form.

Equations

• x.toInt = if 2 * x.toNat < 2 ^ n then ↑x.toNat else ↑x.toNat - ↑(2 ^ n)

def BitVec.ofInt (n : Nat) (i : Int) : BitVec n

The BitVec with value (2^n + (i mod 2^n)) mod 2^n.

Equations

• BitVec.ofInt n i = (i % Int.ofNat (2 ^ n)).toNat#'⋯

instance BitVec.instIntCast {w : Nat} : IntCast (BitVec w)

Equations

• BitVec.instIntCast = { intCast := BitVec.ofInt w }

def BitVec.«term__#__» : Lean.ParserDescr

Notation for bit vector literals. i#n is a shorthand for BitVec.ofNat n i.

Equations

• One or more equations did not get rendered due to their size.

def BitVec.unexpandBitVecOfNat : Lean.PrettyPrinter.Unexpander

Unexpander for bit vector literals.

Equations

• One or more equations did not get rendered due to their size.

def BitVec.«term__#'__» : Lean.TrailingParserDescr

Notation for bit vector literals without truncation. i#'lt is a shorthand for BitVec.ofNatLt i lt.

Equations

• One or more equations did not get rendered due to their size.

def BitVec.unexpandBitVecOfNatLt : Lean.PrettyPrinter.Unexpander

Unexpander for bit vector literals without truncation.

Equations

• One or more equations did not get rendered due to their size.

def BitVec.toHex {n : Nat} (x : BitVec n) : String

Convert bitvector into a fixed-width hex number.

Equations

• x.toHex = (List.replicate ((n + 3) / 4 - (Nat.toDigits 16 x.toNat).asString.length) '0').asString ++ (Nat.toDigits 16 x.toNat).asString

instance BitVec.instRepr {n : Nat} : Repr (BitVec n)

Equations

• BitVec.instRepr = { reprPrec := fun (a : BitVec n) (x : Nat) => Std.Format.text "0x" ++ Std.Format.text a.toHex ++ Std.Format.text "#" ++ repr n }

instance BitVec.instToString {n : Nat} : ToString (BitVec n)

Equations

• BitVec.instToString = { toString := fun (a : BitVec n) => toString (repr a) }

def BitVec.add {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Addition for bit vectors. This can be interpreted as either signed or unsigned addition modulo 2^n.

SMT-Lib name: bvadd.

Equations

• x.add y = BitVec.ofNat n (x.toNat + y.toNat)

instance BitVec.instAdd {n : Nat} : Add (BitVec n)

Equations

• BitVec.instAdd = { add := BitVec.add }

def BitVec.sub {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Subtraction for bit vectors. This can be interpreted as either signed or unsigned subtraction modulo 2^n.

Equations

• x.sub y = BitVec.ofNat n (2 ^ n - y.toNat + x.toNat)

instance BitVec.instSub {n : Nat} : Sub (BitVec n)

Equations

• BitVec.instSub = { sub := BitVec.sub }

def BitVec.neg {n : Nat} (x : BitVec n) : BitVec n

Negation for bit vectors. This can be interpreted as either signed or unsigned negation modulo 2^n.

SMT-Lib name: bvneg.

Equations

• x.neg = BitVec.ofNat n (2 ^ n - x.toNat)

instance BitVec.instNeg {n : Nat} : Neg (BitVec n)

Equations

• BitVec.instNeg = { neg := BitVec.neg }

def BitVec.abs {n : Nat} (x : BitVec n) : BitVec n

Return the absolute value of a signed bitvector.

Equations

• x.abs = if x.msb = true then x.neg else x

def BitVec.mul {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Multiplication for bit vectors. This can be interpreted as either signed or unsigned multiplication modulo 2^n.

SMT-Lib name: bvmul.

Equations

• x.mul y = BitVec.ofNat n (x.toNat * y.toNat)

instance BitVec.instMul {n : Nat} : Mul (BitVec n)

Equations

• BitVec.instMul = { mul := BitVec.mul }

def BitVec.udiv {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Unsigned division for bit vectors using the Lean convention where division by zero returns zero.

Equations

• x.udiv y = (x.toNat / y.toNat)#'⋯

instance BitVec.instDiv {n : Nat} : Div (BitVec n)

Equations

• BitVec.instDiv = { div := BitVec.udiv }

def BitVec.umod {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Unsigned modulo for bit vectors.

SMT-Lib name: bvurem.

Equations

• x.umod y = (x.toNat % y.toNat)#'⋯

instance BitVec.instMod {n : Nat} : Mod (BitVec n)

Equations

• BitVec.instMod = { mod := BitVec.umod }

def BitVec.smtUDiv {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Unsigned division for bit vectors using the SMT-Lib convention where division by zero returns the allOnes bitvector.

SMT-Lib name: bvudiv.

Equations

• x.smtUDiv y = if y = 0 then BitVec.allOnes n else x.udiv y

def BitVec.sdiv {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Signed t-division for bit vectors using the Lean convention where division by zero returns zero.

sdiv 7#4 2 = 3#4
sdiv (-9#4) 2 = -4#4
sdiv 5#4 -2 = -2#4
sdiv (-7#4) (-2) = 3#4

Equations

• x.sdiv y = match x.msb, y.msb with | false, false => x.udiv y | false, true => (x.udiv y.neg).neg | true, false => (x.neg.udiv y).neg | true, true => x.neg.udiv y.neg

def BitVec.smtSDiv {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Signed division for bit vectors using SMTLIB rules for division by zero.

Specifically, smtSDiv x 0 = if x >= 0 then -1 else 1

SMT-Lib name: bvsdiv.

Equations

• x.smtSDiv y = match x.msb, y.msb with | false, false => x.smtUDiv y | false, true => (x.smtUDiv y.neg).neg | true, false => (x.neg.smtUDiv y).neg | true, true => x.neg.smtUDiv y.neg

def BitVec.srem {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Remainder for signed division rounding to zero.

SMT_Lib name: bvsrem.

Equations

• x.srem y = match x.msb, y.msb with | false, false => x.umod y | false, true => x.umod y.neg | true, false => (x.neg.umod y).neg | true, true => (x.neg.umod y.neg).neg

def BitVec.smod {m : Nat} (x : BitVec m) (y : BitVec m) : BitVec m

Remainder for signed division rounded to negative infinity.

SMT_Lib name: bvsmod.

Equations

• One or more equations did not get rendered due to their size.

def BitVec.ofBool (b : Bool) : BitVec 1

Turn a Bool into a bitvector of length 1

Equations

• BitVec.ofBool b = bif b then 1 else 0

@[simp]

theorem BitVec.ofBool_false : BitVec.ofBool false = 0

@[simp]

theorem BitVec.ofBool_true : BitVec.ofBool true = 1

def BitVec.fill (w : Nat) (b : Bool) : BitVec w

Fills a bitvector with w copies of the bit b.

Equations

• BitVec.fill w b = bif b then -1 else 0

def BitVec.ult {n : Nat} (x : BitVec n) (y : BitVec n) : Bool

Unsigned less-than for bit vectors.

SMT-Lib name: bvult.

Equations

• x.ult y = decide (x.toNat < y.toNat)

instance BitVec.instLT {n : Nat} : LT (BitVec n)

Equations

• BitVec.instLT = { lt := fun (x1 x2 : BitVec n) => x1.toNat < x2.toNat }

instance BitVec.instDecidableLt {n : Nat} (x : BitVec n) (y : BitVec n) : Decidable (x < y)

Equations

• x.instDecidableLt y = inferInstanceAs (Decidable (x.toNat < y.toNat))

def BitVec.ule {n : Nat} (x : BitVec n) (y : BitVec n) : Bool

Unsigned less-than-or-equal-to for bit vectors.

SMT-Lib name: bvule.

Equations

• x.ule y = decide (x.toNat ≤ y.toNat)

instance BitVec.instLE {n : Nat} : LE (BitVec n)

Equations

• BitVec.instLE = { le := fun (x1 x2 : BitVec n) => x1.toNat ≤ x2.toNat }

instance BitVec.instDecidableLe {n : Nat} (x : BitVec n) (y : BitVec n) : Decidable (x ≤ y)

Equations

• x.instDecidableLe y = inferInstanceAs (Decidable (x.toNat ≤ y.toNat))

def BitVec.slt {n : Nat} (x : BitVec n) (y : BitVec n) : Bool

Signed less-than for bit vectors.

BitVec.slt 6#4 7 = true
BitVec.slt 7#4 8 = false

SMT-Lib name: bvslt.

Equations

• x.slt y = decide (x.toInt < y.toInt)

def BitVec.sle {n : Nat} (x : BitVec n) (y : BitVec n) : Bool

Signed less-than-or-equal-to for bit vectors.

SMT-Lib name: bvsle.

Equations

• x.sle y = decide (x.toInt ≤ y.toInt)

@[inline]

def BitVec.cast {n : Nat} {m : Nat} (eq : n = m) (x : BitVec n) : BitVec m

cast eq x embeds x into an equal BitVec type.

Equations

• BitVec.cast eq x = x.toNat#'⋯

@[simp]

theorem BitVec.cast_ofNat {n : Nat} {m : Nat} (h : n = m) (x : Nat) : BitVec.cast h (BitVec.ofNat n x) = BitVec.ofNat m x

@[simp]

theorem BitVec.cast_cast {n : Nat} {m : Nat} {k : Nat} (h₁ : n = m) (h₂ : m = k) (x : BitVec n) : BitVec.cast h₂ (BitVec.cast h₁ x) = BitVec.cast ⋯ x

@[simp]

theorem BitVec.cast_eq {n : Nat} (h : n = n) (x : BitVec n) : BitVec.cast h x = x

def BitVec.extractLsb' {n : Nat} (start : Nat) (len : Nat) (x : BitVec n) : BitVec len

Extraction of bits start to start + len - 1 from a bit vector of size n to yield a new bitvector of size len. If start + len > n, then the vector will be zero-padded in the high bits.

Equations

• BitVec.extractLsb' start len x = BitVec.ofNat len (x.toNat >>> start)

def BitVec.extractLsb {n : Nat} (hi : Nat) (lo : Nat) (x : BitVec n) : BitVec (hi - lo + 1)

Extraction of bits hi (inclusive) down to lo (inclusive) from a bit vector of size n to yield a new bitvector of size hi - lo + 1.

SMT-Lib name: extract.

Equations

• BitVec.extractLsb hi lo x = BitVec.extractLsb' lo (hi - lo + 1) x

def BitVec.setWidth' {n : Nat} {w : Nat} (le : n ≤ w) (x : BitVec n) : BitVec w

A version of setWidth that requires a proof, but is a noop.

Equations

• BitVec.setWidth' le x = x.toNat#'⋯

@[reducible, inline, deprecated BitVec.setWidth']

abbrev BitVec.zeroExtend' {n : Nat} {w : Nat} (le : n ≤ w) (x : BitVec n) : BitVec w

A version of setWidth that requires a proof, but is a noop.

Equations

• @BitVec.zeroExtend' = @BitVec.setWidth'

def BitVec.shiftLeftZeroExtend {w : Nat} (msbs : BitVec w) (m : Nat) : BitVec (w + m)

shiftLeftZeroExtend x n returns zeroExtend (w+n) x <<< n without needing to compute x % 2^(2+n).

Equations

• msbs.shiftLeftZeroExtend m = (msbs.toNat <<< m)#'⋯

def BitVec.setWidth {w : Nat} (v : Nat) (x : BitVec w) : BitVec v

Transform x of length w into a bitvector of length v, by either:

• zero extending, that is, adding zeros in the high bits until it has length v, if v > w, or
• truncating the high bits, if v < w.

SMT-Lib name: zero_extend.

Equations

• BitVec.setWidth v x = if h : w ≤ v then BitVec.setWidth' h x else BitVec.ofNat v x.toNat

@[reducible, inline]

abbrev BitVec.zeroExtend {w : Nat} (v : Nat) (x : BitVec w) : BitVec v

Transform x of length w into a bitvector of length v, by either:

• zero extending, that is, adding zeros in the high bits until it has length v, if v > w, or
• truncating the high bits, if v < w.

SMT-Lib name: zero_extend.

Equations

• @BitVec.zeroExtend = @BitVec.setWidth

@[reducible, inline]

abbrev BitVec.truncate {w : Nat} (v : Nat) (x : BitVec w) : BitVec v

Transform x of length w into a bitvector of length v, by either:

• zero extending, that is, adding zeros in the high bits until it has length v, if v > w, or
• truncating the high bits, if v < w.

SMT-Lib name: zero_extend.

Equations

• @BitVec.truncate = @BitVec.setWidth

def BitVec.signExtend {w : Nat} (v : Nat) (x : BitVec w) : BitVec v

Sign extend a vector of length w, extending with i additional copies of the most significant bit in x. If x is an empty vector, then the sign is treated as zero.

SMT-Lib name: sign_extend.

Equations

• BitVec.signExtend v x = BitVec.ofInt v x.toInt

def BitVec.and {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Bitwise AND for bit vectors.

0b1010#4 &&& 0b0110#4 = 0b0010#4

SMT-Lib name: bvand.

Equations

• x.and y = (x.toNat &&& y.toNat)#'⋯

instance BitVec.instAndOp {w : Nat} : AndOp (BitVec w)

Equations

• BitVec.instAndOp = { and := BitVec.and }

def BitVec.or {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Bitwise OR for bit vectors.

0b1010#4 ||| 0b0110#4 = 0b1110#4

SMT-Lib name: bvor.

Equations

• x.or y = (x.toNat ||| y.toNat)#'⋯

instance BitVec.instOrOp {w : Nat} : OrOp (BitVec w)

Equations

• BitVec.instOrOp = { or := BitVec.or }

def BitVec.xor {n : Nat} (x : BitVec n) (y : BitVec n) : BitVec n

Bitwise XOR for bit vectors.

0b1010#4 ^^^ 0b0110#4 = 0b1100#4

SMT-Lib name: bvxor.

Equations

• x.xor y = (x.toNat ^^^ y.toNat)#'⋯

instance BitVec.instXor {w : Nat} : Xor (BitVec w)

Equations

• BitVec.instXor = { xor := BitVec.xor }

def BitVec.not {n : Nat} (x : BitVec n) : BitVec n

Bitwise NOT for bit vectors.

~~~(0b0101#4) == 0b1010

SMT-Lib name: bvnot.

Equations

• x.not = BitVec.allOnes n ^^^ x

instance BitVec.instComplement {w : Nat} : Complement (BitVec w)

Equations

• BitVec.instComplement = { complement := BitVec.not }

def BitVec.shiftLeft {n : Nat} (x : BitVec n) (s : Nat) : BitVec n

Left shift for bit vectors. The low bits are filled with zeros. As a numeric operation, this is equivalent to x * 2^s, modulo 2^n.

SMT-Lib name: bvshl except this operator uses a Nat shift value.

Equations

• x.shiftLeft s = BitVec.ofNat n (x.toNat <<< s)

instance BitVec.instHShiftLeftNat {w : Nat} : HShiftLeft (BitVec w) Nat (BitVec w)

Equations

• BitVec.instHShiftLeftNat = { hShiftLeft := BitVec.shiftLeft }

def BitVec.ushiftRight {n : Nat} (x : BitVec n) (s : Nat) : BitVec n

(Logical) right shift for bit vectors. The high bits are filled with zeros. As a numeric operation, this is equivalent to x / 2^s, rounding down.

SMT-Lib name: bvlshr except this operator uses a Nat shift value.

Equations

• x.ushiftRight s = (x.toNat >>> s)#'⋯

instance BitVec.instHShiftRightNat {w : Nat} : HShiftRight (BitVec w) Nat (BitVec w)

Equations

• BitVec.instHShiftRightNat = { hShiftRight := BitVec.ushiftRight }

def BitVec.sshiftRight {n : Nat} (x : BitVec n) (s : Nat) : BitVec n

Arithmetic right shift for bit vectors. The high bits are filled with the most-significant bit. As a numeric operation, this is equivalent to x.toInt >>> s.

SMT-Lib name: bvashr except this operator uses a Nat shift value.

Equations

• x.sshiftRight s = BitVec.ofInt n (x.toInt >>> s)

instance BitVec.instHShiftLeft {m : Nat} {n : Nat} : HShiftLeft (BitVec m) (BitVec n) (BitVec m)

Equations

• BitVec.instHShiftLeft = { hShiftLeft := fun (x : BitVec m) (y : BitVec n) => x <<< y.toNat }

instance BitVec.instHShiftRight {m : Nat} {n : Nat} : HShiftRight (BitVec m) (BitVec n) (BitVec m)

Equations

• BitVec.instHShiftRight = { hShiftRight := fun (x : BitVec m) (y : BitVec n) => x >>> y.toNat }

def BitVec.sshiftRight' {n : Nat} {m : Nat} (a : BitVec n) (s : BitVec m) : BitVec n

Arithmetic right shift for bit vectors. The high bits are filled with the most-significant bit. As a numeric operation, this is equivalent to a.toInt >>> s.toNat.

SMT-Lib name: bvashr.

Equations

• a.sshiftRight' s = a.sshiftRight s.toNat

def BitVec.rotateLeftAux {w : Nat} (x : BitVec w) (n : Nat) : BitVec w

Auxiliary function for rotateLeft, which does not take into account the case where the rotation amount is greater than the bitvector width.

Equations

• x.rotateLeftAux n = x <<< n ||| x >>> (w - n)

def BitVec.rotateLeft {w : Nat} (x : BitVec w) (n : Nat) : BitVec w

Rotate left for bit vectors. All the bits of x are shifted to higher positions, with the top n bits wrapping around to fill the low bits.

rotateLeft  0b0011#4 3 = 0b1001

SMT-Lib name: rotate_left except this operator uses a Nat shift amount.

Equations

• x.rotateLeft n = x.rotateLeftAux (n % w)

def BitVec.rotateRightAux {w : Nat} (x : BitVec w) (n : Nat) : BitVec w

Auxiliary function for rotateRight, which does not take into account the case where the rotation amount is greater than the bitvector width.

Equations

• x.rotateRightAux n = x >>> n ||| x <<< (w - n)

def BitVec.rotateRight {w : Nat} (x : BitVec w) (n : Nat) : BitVec w

Rotate right for bit vectors. All the bits of x are shifted to lower positions, with the bottom n bits wrapping around to fill the high bits.

rotateRight 0b01001#5 1 = 0b10100

SMT-Lib name: rotate_right except this operator uses a Nat shift amount.

Equations

• x.rotateRight n = x.rotateRightAux (n % w)

def BitVec.append {n : Nat} {m : Nat} (msbs : BitVec n) (lsbs : BitVec m) : BitVec (n + m)

Concatenation of bitvectors. This uses the "big endian" convention that the more significant input is on the left, so 0xAB#8 ++ 0xCD#8 = 0xABCD#16.

SMT-Lib name: concat.

Equations

• msbs.append lsbs = msbs.shiftLeftZeroExtend m ||| BitVec.setWidth' ⋯ lsbs

instance BitVec.instHAppendHAddNat {w : Nat} {v : Nat} : HAppend (BitVec w) (BitVec v) (BitVec (w + v))

Equations

• BitVec.instHAppendHAddNat = { hAppend := BitVec.append }

def BitVec.replicate {w : Nat} (i : Nat) : BitVec w → BitVec (w * i)

replicate i x concatenates i copies of x into a new vector of length w*i.

Equations

• BitVec.replicate 0 x = 0#0
• BitVec.replicate n.succ x = BitVec.cast ⋯ (x ++ BitVec.replicate n x)

Cons and Concat

We give special names to the operations of adding a single bit to either end of a bitvector. We follow the precedent of Vector.cons/Vector.concat both for the name, and for the decision to have the resulting size be n + 1 for both operations (rather than 1 + n, which would be the result of appending a single bit to the front in the naive implementation).

def BitVec.concat {n : Nat} (msbs : BitVec n) (lsb : Bool) : BitVec (n + 1)

Append a single bit to the end of a bitvector, using big endian order (see append). That is, the new bit is the least significant bit.

Equations

• msbs.concat lsb = msbs ++ BitVec.ofBool lsb

def BitVec.shiftConcat {n : Nat} (x : BitVec n) (b : Bool) : BitVec n

x.shiftConcat b shifts all bits of x to the left by 1 and sets the least significant bit to b. It is a non-dependent version of concat that does not change the total bitwidth.

Equations

• x.shiftConcat b = BitVec.truncate n (x.concat b)

def BitVec.cons {n : Nat} (msb : Bool) (lsbs : BitVec n) : BitVec (n + 1)

Prepend a single bit to the front of a bitvector, using big endian order (see append). That is, the new bit is the most significant bit.

Equations

• BitVec.cons msb lsbs = BitVec.cast ⋯ (BitVec.ofBool msb ++ lsbs)

theorem BitVec.append_ofBool {w : Nat} (msbs : BitVec w) (lsb : Bool) : msbs ++ BitVec.ofBool lsb = msbs.concat lsb

theorem BitVec.ofBool_append {w : Nat} (msb : Bool) (lsbs : BitVec w) : BitVec.ofBool msb ++ lsbs = BitVec.cast ⋯ (BitVec.cons msb lsbs)

def BitVec.twoPow (w : Nat) (i : Nat) : BitVec w

twoPow w i is the bitvector 2^i if i < w, and 0 otherwise. That is, 2 to the power i. For the bitwise point of view, it has the ith bit as 1 and all other bits as 0.

Equations

• BitVec.twoPow w i = 1#w <<< i

We add simp-lemmas that rewrite bitvector operations into the equivalent notation

@[simp]

theorem BitVec.append_eq {w : Nat} {v : Nat} (x : BitVec w) (y : BitVec v) : x.append y = x ++ y

@[simp]

theorem BitVec.shiftLeft_eq {w : Nat} (x : BitVec w) (n : Nat) : x.shiftLeft n = x <<< n

@[simp]

theorem BitVec.ushiftRight_eq {w : Nat} (x : BitVec w) (n : Nat) : x.ushiftRight n = x >>> n

@[simp]

theorem BitVec.not_eq {w : Nat} (x : BitVec w) : x.not = ~~~x

@[simp]

theorem BitVec.and_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.and y = x &&& y

@[simp]

theorem BitVec.or_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.or y = x ||| y

@[simp]

theorem BitVec.xor_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.xor y = x ^^^ y

@[simp]

theorem BitVec.neg_eq {w : Nat} (x : BitVec w) : x.neg = -x

@[simp]

theorem BitVec.add_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.add y = x + y

@[simp]

theorem BitVec.sub_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.sub y = x - y

@[simp]

theorem BitVec.mul_eq {w : Nat} (x : BitVec w) (y : BitVec w) : x.mul y = x * y

@[simp]

theorem BitVec.zero_eq {n : Nat} : BitVec.zero n = 0#n

def BitVec.ofBoolListBE (bs : List Bool) : BitVec bs.length

Converts a list of Bools to a big-endian BitVec.

Equations

• BitVec.ofBoolListBE [] = 0#0
• BitVec.ofBoolListBE (b :: bs) = BitVec.cons b (BitVec.ofBoolListBE bs)

def BitVec.ofBoolListLE (bs : List Bool) : BitVec bs.length

Converts a list of Bools to a little-endian BitVec.

Equations

• BitVec.ofBoolListLE [] = 0#0
• BitVec.ofBoolListLE (b :: bs) = (BitVec.ofBoolListLE bs).concat b