Documentation

Init.Data.BitVec.Basic

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) :

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.

  • )
Instances For
    @[inline, reducible, deprecated]
    abbrev Std.BitVec (w : Nat) :
    Equations
    Instances For
      def BitVec.decEq {n : Nat} (a : BitVec n) (b : BitVec n) :
      Decidable (a = b)
      Equations
      Instances For
        Equations
        • instDecidableEqBitVec = BitVec.decEq
        @[match_pattern]
        def BitVec.ofNatLt {n : Nat} (i : Nat) (p : i < 2 ^ n) :

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

        Equations
        • i#'p = { toFin := { val := i, isLt := p } }
        Instances For
          @[match_pattern]
          def BitVec.ofNat (n : Nat) (i : Nat) :

          The BitVec with value i mod 2^n.

          Equations
          Instances For
            instance BitVec.instOfNat {n : Nat} {i : Nat} :
            Equations
            • BitVec.instOfNat = { ofNat := i#n }
            instance BitVec.natCastInst {w : Nat} :
            Equations
            def BitVec.toNat {n : Nat} (a : BitVec n) :

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

            Equations
            Instances For
              theorem BitVec.isLt {w : Nat} (x : BitVec w) :

              Return the bound in terms of toNat.

              @[simp]
              theorem BitVec.ofNat_eq_ofNat {n : Nat} {i : Nat} :

              Theorem for normalizing the bit vector literal representation.

              @[simp]
              theorem BitVec.natCast_eq_ofNat (w : Nat) (x : Nat) :
              x = x#w
              @[inline, reducible]
              abbrev BitVec.nil :

              The empty bitvector

              Equations
              Instances For
                theorem BitVec.eq_nil (x : BitVec 0) :

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

                def BitVec.zero (n : Nat) :

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

                Equations
                Instances For
                  Equations

                  Bit vector of size n where all bits are 1s

                  Equations
                  Instances For
                    @[inline]
                    def BitVec.getLsb {w : Nat} (x : BitVec w) (i : Nat) :

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

                    Equations
                    Instances For
                      @[inline]
                      def BitVec.getMsb {w : Nat} (x : BitVec w) (i : Nat) :

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

                      Equations
                      Instances For
                        @[inline]
                        def BitVec.msb {n : Nat} (a : BitVec n) :

                        Return most-significant bit in bitvector.

                        Equations
                        Instances For
                          def BitVec.toInt {n : Nat} (a : BitVec n) :

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

                          Equations
                          Instances For
                            def BitVec.ofInt (n : Nat) (i : Int) :

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

                            Equations
                            Instances For
                              Equations

                              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.
                              Instances For

                                Unexpander for bit vector literals.

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

                                  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.
                                  Instances For

                                    Unexpander for bit vector literals without truncation.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      def BitVec.toHex {n : Nat} (x : BitVec n) :

                                      Convert bitvector into a fixed-width hex number.

                                      Equations
                                      Instances For
                                        instance BitVec.instReprBitVec {n : Nat} :
                                        Equations
                                        Equations
                                        def BitVec.add {n : Nat} (x : BitVec n) (y : BitVec n) :

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

                                        SMT-Lib name: bvadd.

                                        Equations
                                        Instances For
                                          instance BitVec.instAddBitVec {n : Nat} :
                                          Equations
                                          • BitVec.instAddBitVec = { add := BitVec.add }
                                          def BitVec.sub {n : Nat} (x : BitVec n) (y : BitVec n) :

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

                                          Equations
                                          Instances For
                                            instance BitVec.instSubBitVec {n : Nat} :
                                            Equations
                                            • BitVec.instSubBitVec = { sub := BitVec.sub }
                                            def BitVec.neg {n : Nat} (x : BitVec n) :

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

                                            SMT-Lib name: bvneg.

                                            Equations
                                            Instances For
                                              instance BitVec.instNegBitVec {n : Nat} :
                                              Equations
                                              • BitVec.instNegBitVec = { neg := BitVec.neg }
                                              def BitVec.abs {n : Nat} (s : BitVec n) :

                                              Return the absolute value of a signed bitvector.

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

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

                                                SMT-Lib name: bvmul.

                                                Equations
                                                Instances For
                                                  instance BitVec.instMulBitVec {n : Nat} :
                                                  Equations
                                                  • BitVec.instMulBitVec = { mul := BitVec.mul }
                                                  def BitVec.udiv {n : Nat} (x : BitVec n) (y : BitVec n) :

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

                                                  Equations
                                                  Instances For
                                                    instance BitVec.instDivBitVec {n : Nat} :
                                                    Equations
                                                    • BitVec.instDivBitVec = { div := BitVec.udiv }
                                                    def BitVec.umod {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                    Unsigned modulo for bit vectors.

                                                    SMT-Lib name: bvurem.

                                                    Equations
                                                    Instances For
                                                      instance BitVec.instModBitVec {n : Nat} :
                                                      Equations
                                                      • BitVec.instModBitVec = { mod := BitVec.umod }
                                                      def BitVec.smtUDiv {n : Nat} (x : BitVec n) (y : 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
                                                      Instances For
                                                        def BitVec.sdiv {n : Nat} (s : BitVec n) (t : 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
                                                        • One or more equations did not get rendered due to their size.
                                                        Instances For
                                                          def BitVec.smtSDiv {n : Nat} (s : BitVec n) (t : 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
                                                          • One or more equations did not get rendered due to their size.
                                                          Instances For
                                                            def BitVec.srem {n : Nat} (s : BitVec n) (t : BitVec n) :

                                                            Remainder for signed division rounding to zero.

                                                            SMT_Lib name: bvsrem.

                                                            Equations
                                                            • One or more equations did not get rendered due to their size.
                                                            Instances For
                                                              def BitVec.smod {m : Nat} (s : BitVec m) (t : 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.
                                                              Instances For

                                                                Turn a Bool into a bitvector of length 1

                                                                Equations
                                                                Instances For
                                                                  def BitVec.fill (w : Nat) (b : Bool) :

                                                                  Fills a bitvector with w copies of the bit b.

                                                                  Equations
                                                                  Instances For
                                                                    def BitVec.ult {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                                    Unsigned less-than for bit vectors.

                                                                    SMT-Lib name: bvult.

                                                                    Equations
                                                                    Instances For
                                                                      instance BitVec.instLTBitVec {n : Nat} :
                                                                      Equations
                                                                      def BitVec.ule {n : Nat} (x : BitVec n) (y : BitVec n) :

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

                                                                      SMT-Lib name: bvule.

                                                                      Equations
                                                                      Instances For
                                                                        instance BitVec.instLEBitVec {n : Nat} :
                                                                        Equations
                                                                        def BitVec.slt {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                                        Signed less-than for bit vectors.

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

                                                                        SMT-Lib name: bvslt.

                                                                        Equations
                                                                        Instances For
                                                                          def BitVec.sle {n : Nat} (x : BitVec n) (y : BitVec n) :

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

                                                                          SMT-Lib name: bvsle.

                                                                          Equations
                                                                          Instances For
                                                                            @[inline]
                                                                            def BitVec.cast {n : Nat} {m : Nat} (eq : n = m) (i : BitVec n) :

                                                                            cast eq i embeds i into an equal BitVec type.

                                                                            Equations
                                                                            Instances For
                                                                              @[simp]
                                                                              theorem BitVec.cast_ofNat {n : Nat} {m : Nat} (h : n = m) (x : Nat) :
                                                                              BitVec.cast h x#n = x#m
                                                                              @[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) :
                                                                              def BitVec.extractLsb' {n : Nat} (start : Nat) (len : Nat) (a : 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
                                                                              Instances For
                                                                                def BitVec.extractLsb {n : Nat} (hi : Nat) (lo : Nat) (a : 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
                                                                                Instances For
                                                                                  def BitVec.zeroExtend' {n : Nat} {w : Nat} (le : n w) (x : BitVec n) :

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

                                                                                  Equations
                                                                                  Instances For
                                                                                    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
                                                                                    Instances For
                                                                                      def BitVec.zeroExtend {w : Nat} (v : Nat) (x : BitVec w) :

                                                                                      Zero extend vector x of length w by adding zeros in the high bits until it has length v. If v < w then it truncates the high bits instead.

                                                                                      SMT-Lib name: zero_extend.

                                                                                      Equations
                                                                                      Instances For
                                                                                        @[inline, reducible]
                                                                                        abbrev BitVec.truncate {w : Nat} (v : Nat) (x : BitVec w) :

                                                                                        Truncate the high bits of bitvector x of length w, resulting in a vector of length v. If v > w then it zero-extends the vector instead.

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

                                                                                          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
                                                                                          Instances For
                                                                                            def BitVec.and {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                                                            Bitwise AND for bit vectors.

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

                                                                                            SMT-Lib name: bvand.

                                                                                            Equations
                                                                                            Instances For
                                                                                              Equations
                                                                                              • BitVec.instAndOpBitVec = { and := BitVec.and }
                                                                                              def BitVec.or {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                                                              Bitwise OR for bit vectors.

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

                                                                                              SMT-Lib name: bvor.

                                                                                              Equations
                                                                                              Instances For
                                                                                                instance BitVec.instOrOpBitVec {w : Nat} :
                                                                                                Equations
                                                                                                • BitVec.instOrOpBitVec = { or := BitVec.or }
                                                                                                def BitVec.xor {n : Nat} (x : BitVec n) (y : BitVec n) :

                                                                                                Bitwise XOR for bit vectors.

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

                                                                                                SMT-Lib name: bvxor.

                                                                                                Equations
                                                                                                Instances For
                                                                                                  instance BitVec.instXorBitVec {w : Nat} :
                                                                                                  Equations
                                                                                                  • BitVec.instXorBitVec = { xor := BitVec.xor }
                                                                                                  def BitVec.not {n : Nat} (x : BitVec n) :

                                                                                                  Bitwise NOT for bit vectors.

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

                                                                                                  SMT-Lib name: bvnot.

                                                                                                  Equations
                                                                                                  Instances For
                                                                                                    Equations
                                                                                                    • BitVec.instComplementBitVec = { complement := BitVec.not }
                                                                                                    def BitVec.shiftLeft {n : Nat} (a : BitVec n) (s : Nat) :

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

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

                                                                                                    Equations
                                                                                                    Instances For
                                                                                                      Equations
                                                                                                      • BitVec.instHShiftLeftBitVecNat = { hShiftLeft := BitVec.shiftLeft }
                                                                                                      def BitVec.ushiftRight {n : Nat} (a : BitVec n) (s : Nat) :

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

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

                                                                                                      Equations
                                                                                                      Instances For
                                                                                                        Equations
                                                                                                        • BitVec.instHShiftRightBitVecNat = { hShiftRight := BitVec.ushiftRight }
                                                                                                        def BitVec.sshiftRight {n : Nat} (a : BitVec n) (s : Nat) :

                                                                                                        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.

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

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

                                                                                                          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
                                                                                                          Instances For
                                                                                                            def BitVec.rotateRight {w : Nat} (x : BitVec w) (n : Nat) :

                                                                                                            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
                                                                                                            Instances For
                                                                                                              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
                                                                                                              Instances For
                                                                                                                Equations
                                                                                                                • BitVec.instHAppendBitVecHAddNatInstHAddInstAddNat = { hAppend := BitVec.append }
                                                                                                                def BitVec.replicate {w : Nat} (i : Nat) :
                                                                                                                BitVec wBitVec (w * i)

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

                                                                                                                Equations
                                                                                                                Instances For

                                                                                                                  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
                                                                                                                  Instances For
                                                                                                                    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
                                                                                                                    Instances For
                                                                                                                      theorem BitVec.append_ofBool {w : Nat} (msbs : BitVec w) (lsb : Bool) :
                                                                                                                      msbs ++ BitVec.ofBool lsb = BitVec.concat msbs lsb
                                                                                                                      theorem BitVec.ofBool_append {w : Nat} (msb : Bool) (lsbs : BitVec w) :
                                                                                                                      BitVec.ofBool msb ++ lsbs = BitVec.cast (BitVec.cons msb lsbs)

                                                                                                                      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) :
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.shiftLeft_eq {w : Nat} (x : BitVec w) (n : Nat) :
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.ushiftRight_eq {w : Nat} (x : BitVec w) (n : Nat) :
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.not_eq {w : Nat} (x : BitVec w) :
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.and_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.and x y = x &&& y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.or_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.or x y = x ||| y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.xor_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.xor x y = x ^^^ y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.neg_eq {w : Nat} (x : BitVec w) :
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.add_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.add x y = x + y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.sub_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.sub x y = x - y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.mul_eq {w : Nat} (x : BitVec w) (y : BitVec w) :
                                                                                                                      BitVec.mul x y = x * y
                                                                                                                      @[simp]
                                                                                                                      theorem BitVec.zero_eq {n : Nat} :