data.bitvec.core ⟷ Mathlib.Data.BitVec.Defs

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -21,15 +21,15 @@ It is not fully in compliance with mathlib style standards.
 -/
 
 
-#print Std.BitVec /-
+#print BitVec /-
 /-- `bitvec n` is a `vector` of `bool` with length `n`. -/
 @[reducible]
-def Std.BitVec (n : ℕ) :=
+def BitVec (n : ℕ) :=
   Vector Bool n
-#align bitvec Std.BitVec
+#align bitvec BitVec
 -/
 
-namespace Std.BitVec
+namespace BitVec
 
 open Nat
 
@@ -37,35 +37,35 @@ open Vector
 
 local infixl:65 "++ₜ" => Vector.append
 
-#print Std.BitVec.zero /-
+#print BitVec.zero /-
 /-- Create a zero bitvector -/
 @[reducible]
-protected def Std.BitVec.zero (n : ℕ) : Std.BitVec n :=
+protected def zero (n : ℕ) : BitVec n :=
   replicate n false
-#align bitvec.zero Std.BitVec.zero
+#align bitvec.zero BitVec.zero
 -/
 
-#print Std.BitVec.one /-
+#print BitVec.one /-
 /-- Create a bitvector of length `n` whose `n-1`st entry is 1 and other entries are 0. -/
 @[reducible]
-protected def Std.BitVec.one : ∀ n : ℕ, Std.BitVec n
+protected def one : ∀ n : ℕ, BitVec n
   | 0 => nil
   | succ n => replicate n false++ₜtrue ::ᵥ nil
-#align bitvec.one Std.BitVec.one
+#align bitvec.one BitVec.one
 -/
 
-#print Std.BitVec.cast /-
+#print BitVec.cast /-
 /-- Create a bitvector from another with a provably equal length. -/
-protected def Std.BitVec.cast {a b : ℕ} (h : a = b) : Std.BitVec a → Std.BitVec b
+protected def cast {a b : ℕ} (h : a = b) : BitVec a → BitVec b
   | ⟨x, p⟩ => ⟨x, h ▸ p⟩
-#align bitvec.cong Std.BitVec.cast
+#align bitvec.cong BitVec.cast
 -/
 
-#print Std.BitVec.append /-
+#print BitVec.append /-
 /-- `bitvec` specific version of `vector.append` -/
-def Std.BitVec.append {m n} : Std.BitVec m → Std.BitVec n → Std.BitVec (m + n) :=
+def append {m n} : BitVec m → BitVec n → BitVec (m + n) :=
   Vector.append
-#align bitvec.append Std.BitVec.append
+#align bitvec.append BitVec.append
 -/
 
 /-! ### Shift operations -/
@@ -75,19 +75,19 @@ section Shift
 
 variable {n : ℕ}
 
-#print Std.BitVec.shiftLeft /-
+#print BitVec.shiftLeft /-
 /-- `shl x i` is the bitvector obtained by left-shifting `x` `i` times and padding with `ff`.
 If `x.length < i` then this will return the all-`ff`s bitvector. -/
-def Std.BitVec.shiftLeft (x : Std.BitVec n) (i : ℕ) : Std.BitVec n :=
-  Std.BitVec.cast (by simp) <| drop i x++ₜreplicate (min n i) false
-#align bitvec.shl Std.BitVec.shiftLeft
+def shiftLeft (x : BitVec n) (i : ℕ) : BitVec n :=
+  BitVec.cast (by simp) <| drop i x++ₜreplicate (min n i) false
+#align bitvec.shl BitVec.shiftLeft
 -/
 
 /-- `fill_shr x i fill` is the bitvector obtained by right-shifting `x` `i` times and then
 padding with `fill : bool`. If `x.length < i` then this will return the constant `fill`
 bitvector. -/
-def Std.BitVec.fillShr (x : Std.BitVec n) (i : ℕ) (fill : Bool) : Std.BitVec n :=
-  Std.BitVec.cast
+def fillShr (x : BitVec n) (i : ℕ) (fill : Bool) : BitVec n :=
+  BitVec.cast
       (by
         by_cases i ≤ n
         · have h₁ := Nat.sub_le n i
@@ -96,21 +96,21 @@ def Std.BitVec.fillShr (x : Std.BitVec n) (i : ℕ) (fill : Bool) : Std.BitVec n
         · have h₁ := le_of_not_ge h
           rw [min_eq_left h₁, tsub_eq_zero_iff_le.mpr h₁, zero_min, Nat.add_zero]) <|
     replicate (min n i) fill++ₜtake (n - i) x
-#align bitvec.fill_shr Std.BitVec.fillShr
+#align bitvec.fill_shr BitVec.fillShr
 
-#print Std.BitVec.ushiftRight /-
+#print BitVec.ushiftRight /-
 /-- unsigned shift right -/
-def Std.BitVec.ushiftRight (x : Std.BitVec n) (i : ℕ) : Std.BitVec n :=
-  Std.BitVec.fillShr x i false
-#align bitvec.ushr Std.BitVec.ushiftRight
+def ushiftRight (x : BitVec n) (i : ℕ) : BitVec n :=
+  fillShr x i false
+#align bitvec.ushr BitVec.ushiftRight
 -/
 
-#print Std.BitVec.sshiftRight /-
+#print BitVec.sshiftRight /-
 /-- signed shift right -/
-def Std.BitVec.sshiftRight : ∀ {m : ℕ}, Std.BitVec m → ℕ → Std.BitVec m
+def sshiftRight : ∀ {m : ℕ}, BitVec m → ℕ → BitVec m
   | 0, _, _ => nil
-  | succ m, x, i => head x ::ᵥ Std.BitVec.fillShr (tail x) i (head x)
-#align bitvec.sshr Std.BitVec.sshiftRight
+  | succ m, x, i => head x ::ᵥ fillShr (tail x) i (head x)
+#align bitvec.sshr BitVec.sshiftRight
 -/
 
 end Shift
@@ -122,32 +122,32 @@ section Bitwise
 
 variable {n : ℕ}
 
-#print Std.BitVec.not /-
+#print BitVec.not /-
 /-- bitwise not -/
-def Std.BitVec.not : Std.BitVec n → Std.BitVec n :=
+def not : BitVec n → BitVec n :=
   map not
-#align bitvec.not Std.BitVec.not
+#align bitvec.not BitVec.not
 -/
 
-#print Std.BitVec.and /-
+#print BitVec.and /-
 /-- bitwise and -/
-def Std.BitVec.and : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
+def and : BitVec n → BitVec n → BitVec n :=
   map₂ and
-#align bitvec.and Std.BitVec.and
+#align bitvec.and BitVec.and
 -/
 
-#print Std.BitVec.or /-
+#print BitVec.or /-
 /-- bitwise or -/
-def Std.BitVec.or : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
+def or : BitVec n → BitVec n → BitVec n :=
   map₂ or
-#align bitvec.or Std.BitVec.or
+#align bitvec.or BitVec.or
 -/
 
-#print Std.BitVec.xor /-
+#print BitVec.xor /-
 /-- bitwise xor -/
-def Std.BitVec.xor : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
+def xor : BitVec n → BitVec n → BitVec n :=
   map₂ xor
-#align bitvec.xor Std.BitVec.xor
+#align bitvec.xor BitVec.xor
 -/
 
 end Bitwise
@@ -173,70 +173,70 @@ protected def carry (x y c : Bool) :=
 #align bitvec.carry Bool.carry
 -/
 
-#print Std.BitVec.neg /-
+#print BitVec.neg /-
 /-- `neg x` is the two's complement of `x`. -/
-protected def Std.BitVec.neg (x : Std.BitVec n) : Std.BitVec n :=
+protected def neg (x : BitVec n) : BitVec n :=
   let f y c := (y || c, xor y c)
   Prod.snd (mapAccumr f x false)
-#align bitvec.neg Std.BitVec.neg
+#align bitvec.neg BitVec.neg
 -/
 
-#print Std.BitVec.adc /-
+#print BitVec.adc /-
 /-- Add with carry (no overflow) -/
-def Std.BitVec.adc (x y : Std.BitVec n) (c : Bool) : Std.BitVec (n + 1) :=
+def adc (x y : BitVec n) (c : Bool) : BitVec (n + 1) :=
   let f x y c := (Bool.carry x y c, Bool.xor3 x y c)
   let ⟨c, z⟩ := Vector.mapAccumr₂ f x y c
   c ::ᵥ z
-#align bitvec.adc Std.BitVec.adc
+#align bitvec.adc BitVec.adc
 -/
 
-#print Std.BitVec.add /-
+#print BitVec.add /-
 /-- The sum of two bitvectors -/
-protected def Std.BitVec.add (x y : Std.BitVec n) : Std.BitVec n :=
-  tail (Std.BitVec.adc x y false)
-#align bitvec.add Std.BitVec.add
+protected def add (x y : BitVec n) : BitVec n :=
+  tail (adc x y false)
+#align bitvec.add BitVec.add
 -/
 
-#print Std.BitVec.sbb /-
+#print BitVec.sbb /-
 /-- Subtract with borrow -/
-def Std.BitVec.sbb (x y : Std.BitVec n) (b : Bool) : Bool × Std.BitVec n :=
+def sbb (x y : BitVec n) (b : Bool) : Bool × BitVec n :=
   let f x y c := (Bool.carry (not x) y c, Bool.xor3 x y c)
   Vector.mapAccumr₂ f x y b
-#align bitvec.sbb Std.BitVec.sbb
+#align bitvec.sbb BitVec.sbb
 -/
 
-#print Std.BitVec.sub /-
+#print BitVec.sub /-
 /-- The difference of two bitvectors -/
-protected def Std.BitVec.sub (x y : Std.BitVec n) : Std.BitVec n :=
-  Prod.snd (Std.BitVec.sbb x y false)
-#align bitvec.sub Std.BitVec.sub
+protected def sub (x y : BitVec n) : BitVec n :=
+  Prod.snd (sbb x y false)
+#align bitvec.sub BitVec.sub
 -/
 
-instance : Zero (Std.BitVec n) :=
-  ⟨Std.BitVec.zero n⟩
+instance : Zero (BitVec n) :=
+  ⟨BitVec.zero n⟩
 
-instance : One (Std.BitVec n) :=
-  ⟨Std.BitVec.one n⟩
+instance : One (BitVec n) :=
+  ⟨BitVec.one n⟩
 
-instance : Add (Std.BitVec n) :=
-  ⟨Std.BitVec.add⟩
+instance : Add (BitVec n) :=
+  ⟨BitVec.add⟩
 
-instance : Sub (Std.BitVec n) :=
-  ⟨Std.BitVec.sub⟩
+instance : Sub (BitVec n) :=
+  ⟨BitVec.sub⟩
 
-instance : Neg (Std.BitVec n) :=
-  ⟨Std.BitVec.neg⟩
+instance : Neg (BitVec n) :=
+  ⟨BitVec.neg⟩
 
-#print Std.BitVec.mul /-
+#print BitVec.mul /-
 /-- The product of two bitvectors -/
-protected def Std.BitVec.mul (x y : Std.BitVec n) : Std.BitVec n :=
+protected def mul (x y : BitVec n) : BitVec n :=
   let f r b := cond b (r + r + y) (r + r)
   (toList x).foldl f 0
-#align bitvec.mul Std.BitVec.mul
+#align bitvec.mul BitVec.mul
 -/
 
-instance : Mul (Std.BitVec n) :=
-  ⟨Std.BitVec.mul⟩
+instance : Mul (BitVec n) :=
+  ⟨BitVec.mul⟩
 
 end Arith
 
@@ -247,84 +247,84 @@ section Comparison
 
 variable {n : ℕ}
 
-#print Std.BitVec.ult /-
+#print BitVec.ult /-
 /-- `uborrow x y` returns `tt` iff the "subtract with borrow" operation on `x`, `y` and `ff`
 required a borrow. -/
-def Std.BitVec.ult (x y : Std.BitVec n) : Bool :=
-  Prod.fst (Std.BitVec.sbb x y false)
-#align bitvec.uborrow Std.BitVec.ult
+def ult (x y : BitVec n) : Bool :=
+  Prod.fst (sbb x y false)
+#align bitvec.uborrow BitVec.ult
 -/
 
-/- warning: bitvec.ult clashes with bitvec.uborrow -> Std.BitVec.ult
-Case conversion may be inaccurate. Consider using '#align bitvec.ult Std.BitVec.ultₓ'. -/
-#print Std.BitVec.ult /-
+/- warning: bitvec.ult clashes with bitvec.uborrow -> BitVec.ult
+Case conversion may be inaccurate. Consider using '#align bitvec.ult BitVec.ultₓ'. -/
+#print BitVec.ult /-
 /-- unsigned less-than proposition -/
-def Std.BitVec.ult (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.ult x y
-#align bitvec.ult Std.BitVec.ult
+def ult (x y : BitVec n) : Prop :=
+  ult x y
+#align bitvec.ult BitVec.ult
 -/
 
-#print Std.BitVec.ugt /-
+#print BitVec.ugt /-
 /-- unsigned greater-than proposition -/
-def Std.BitVec.ugt (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.ult y x
-#align bitvec.ugt Std.BitVec.ugt
+def ugt (x y : BitVec n) : Prop :=
+  ult y x
+#align bitvec.ugt BitVec.ugt
 -/
 
-#print Std.BitVec.ule /-
+#print BitVec.ule /-
 /-- unsigned less-than-or-equal-to proposition -/
-def Std.BitVec.ule (x y : Std.BitVec n) : Prop :=
-  ¬Std.BitVec.ult y x
-#align bitvec.ule Std.BitVec.ule
+def ule (x y : BitVec n) : Prop :=
+  ¬ult y x
+#align bitvec.ule BitVec.ule
 -/
 
-#print Std.BitVec.uge /-
+#print BitVec.uge /-
 /-- unsigned greater-than-or-equal-to proposition -/
-def Std.BitVec.uge (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.ule y x
-#align bitvec.uge Std.BitVec.uge
+def uge (x y : BitVec n) : Prop :=
+  ule y x
+#align bitvec.uge BitVec.uge
 -/
 
-#print Std.BitVec.slt /-
+#print BitVec.slt /-
 /-- `sborrow x y` returns `tt` iff `x < y` as two's complement integers -/
-def Std.BitVec.slt : ∀ {n : ℕ}, Std.BitVec n → Std.BitVec n → Bool
+def slt : ∀ {n : ℕ}, BitVec n → BitVec n → Bool
   | 0, _, _ => false
   | succ n, x, y =>
     match (head x, head y) with
     | (tt, ff) => true
     | (ff, tt) => false
-    | _ => Std.BitVec.ult (tail x) (tail y)
-#align bitvec.sborrow Std.BitVec.slt
+    | _ => ult (tail x) (tail y)
+#align bitvec.sborrow BitVec.slt
 -/
 
-/- warning: bitvec.slt clashes with bitvec.sborrow -> Std.BitVec.slt
-Case conversion may be inaccurate. Consider using '#align bitvec.slt Std.BitVec.sltₓ'. -/
-#print Std.BitVec.slt /-
+/- warning: bitvec.slt clashes with bitvec.sborrow -> BitVec.slt
+Case conversion may be inaccurate. Consider using '#align bitvec.slt BitVec.sltₓ'. -/
+#print BitVec.slt /-
 /-- signed less-than proposition -/
-def Std.BitVec.slt (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.slt x y
-#align bitvec.slt Std.BitVec.slt
+def slt (x y : BitVec n) : Prop :=
+  slt x y
+#align bitvec.slt BitVec.slt
 -/
 
-#print Std.BitVec.sgt /-
+#print BitVec.sgt /-
 /-- signed greater-than proposition -/
-def Std.BitVec.sgt (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.slt y x
-#align bitvec.sgt Std.BitVec.sgt
+def sgt (x y : BitVec n) : Prop :=
+  slt y x
+#align bitvec.sgt BitVec.sgt
 -/
 
-#print Std.BitVec.sle /-
+#print BitVec.sle /-
 /-- signed less-than-or-equal-to proposition -/
-def Std.BitVec.sle (x y : Std.BitVec n) : Prop :=
-  ¬Std.BitVec.slt y x
-#align bitvec.sle Std.BitVec.sle
+def sle (x y : BitVec n) : Prop :=
+  ¬slt y x
+#align bitvec.sle BitVec.sle
 -/
 
-#print Std.BitVec.sge /-
+#print BitVec.sge /-
 /-- signed greater-than-or-equal-to proposition -/
-def Std.BitVec.sge (x y : Std.BitVec n) : Prop :=
-  Std.BitVec.sle y x
-#align bitvec.sge Std.BitVec.sge
+def sge (x y : BitVec n) : Prop :=
+  sle y x
+#align bitvec.sge BitVec.sge
 -/
 
 end Comparison
@@ -336,54 +336,53 @@ section Conversion
 
 variable {α : Type}
 
-#print Std.BitVec.ofNat /-
+#print BitVec.ofNat /-
 /-- Create a bitvector from a `nat` -/
-protected def Std.BitVec.ofNat : ∀ n : ℕ, Nat → Std.BitVec n
+protected def ofNat : ∀ n : ℕ, Nat → BitVec n
   | 0, x => nil
   | succ n, x => of_nat n (x / 2)++ₜdecide (x % 2 = 1) ::ᵥ nil
-#align bitvec.of_nat Std.BitVec.ofNat
+#align bitvec.of_nat BitVec.ofNat
 -/
 
-#print Std.BitVec.ofInt /-
+#print BitVec.ofInt /-
 /-- Create a bitvector in the two's complement representation from an `int` -/
-protected def Std.BitVec.ofInt : ∀ n : ℕ, Int → Std.BitVec (succ n)
-  | n, Int.ofNat m => false ::ᵥ Std.BitVec.ofNat n m
-  | n, Int.negSucc m => true ::ᵥ Std.BitVec.not (Std.BitVec.ofNat n m)
-#align bitvec.of_int Std.BitVec.ofInt
+protected def ofInt : ∀ n : ℕ, Int → BitVec (succ n)
+  | n, Int.ofNat m => false ::ᵥ BitVec.ofNat n m
+  | n, Int.negSucc m => true ::ᵥ not (BitVec.ofNat n m)
+#align bitvec.of_int BitVec.ofInt
 -/
 
-#print Std.BitVec.addLsb /-
+#print BitVec.addLsb /-
 /-- `add_lsb r b` is `r + r + 1` if `b` is `tt` and `r + r` otherwise. -/
-def Std.BitVec.addLsb (r : ℕ) (b : Bool) :=
+def addLsb (r : ℕ) (b : Bool) :=
   r + r + cond b 1 0
-#align bitvec.add_lsb Std.BitVec.addLsb
+#align bitvec.add_lsb BitVec.addLsb
 -/
 
 /-- Given a `list` of `bool`s, return the `nat` they represent as a list of binary digits. -/
-def Std.BitVec.bitsToNat (v : List Bool) : Nat :=
-  v.foldl Std.BitVec.addLsb 0
-#align bitvec.bits_to_nat Std.BitVec.bitsToNat
+def bitsToNat (v : List Bool) : Nat :=
+  v.foldl addLsb 0
+#align bitvec.bits_to_nat BitVec.bitsToNat
 
-#print Std.BitVec.toNat /-
+#print BitVec.toNat /-
 /-- Return the natural number encoded by the input bitvector -/
-protected def Std.BitVec.toNat {n : Nat} (v : Std.BitVec n) : Nat :=
-  Std.BitVec.bitsToNat (toList v)
-#align bitvec.to_nat Std.BitVec.toNat
+protected def toNat {n : Nat} (v : BitVec n) : Nat :=
+  bitsToNat (toList v)
+#align bitvec.to_nat BitVec.toNat
 -/
 
-theorem Std.BitVec.bitsToNat_toList {n : ℕ} (x : Std.BitVec n) :
-    Std.BitVec.toNat x = Std.BitVec.bitsToNat (Vector.toList x) :=
+theorem bitsToNat_toList {n : ℕ} (x : BitVec n) : BitVec.toNat x = bitsToNat (Vector.toList x) :=
   rfl
-#align bitvec.bits_to_nat_to_list Std.BitVec.bitsToNat_toList
+#align bitvec.bits_to_nat_to_list BitVec.bitsToNat_toList
 
 attribute [local simp] Nat.add_comm Nat.add_assoc Nat.add_left_comm Nat.mul_comm Nat.mul_assoc
 
 attribute [local simp] Nat.zero_add Nat.add_zero Nat.one_mul Nat.mul_one Nat.zero_mul Nat.mul_zero
 
-#print Std.BitVec.toNat_append /-
+#print BitVec.toNat_append /-
 -- mul_left_comm
-theorem Std.BitVec.toNat_append {m : ℕ} (xs : Std.BitVec m) (b : Bool) :
-    Std.BitVec.toNat (xs++ₜb ::ᵥ nil) = Std.BitVec.toNat xs * 2 + Std.BitVec.toNat (b ::ᵥ nil) :=
+theorem toNat_append {m : ℕ} (xs : BitVec m) (b : Bool) :
+    BitVec.toNat (xs++ₜb ::ᵥ nil) = BitVec.toNat xs * 2 + BitVec.toNat (b ::ᵥ nil) :=
   by
   cases' xs with xs P
   simp [bits_to_nat_to_list]; clear P
@@ -395,39 +394,38 @@ theorem Std.BitVec.toNat_append {m : ℕ} (xs : Std.BitVec m) (b : Bool) :
   induction' xs with x xs generalizing x
   · simp; unfold List.foldl add_lsb; simp [Nat.mul_succ]
   · simp; apply xs_ih
-#align bitvec.to_nat_append Std.BitVec.toNat_append
+#align bitvec.to_nat_append BitVec.toNat_append
 -/
 
-theorem Std.BitVec.bits_toNat_decide (n : ℕ) :
-    Std.BitVec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
+theorem bits_toNat_decide (n : ℕ) : BitVec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
   by
   simp [bits_to_nat_to_list]
   unfold bits_to_nat add_lsb List.foldl cond
   simp [cond_to_bool_mod_two]
-#align bitvec.bits_to_nat_to_bool Std.BitVec.bits_toNat_decide
+#align bitvec.bits_to_nat_to_bool BitVec.bits_toNat_decide
 
-theorem Std.BitVec.ofNat_succ {k n : ℕ} :
-    Std.BitVec.ofNat (succ k) n = Std.BitVec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
+theorem ofNat_succ {k n : ℕ} :
+    BitVec.ofNat (succ k) n = BitVec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
   rfl
-#align bitvec.of_nat_succ Std.BitVec.ofNat_succ
+#align bitvec.of_nat_succ BitVec.ofNat_succ
 
-#print Std.BitVec.toNat_ofNat /-
-theorem Std.BitVec.toNat_ofNat {k n : ℕ} : Std.BitVec.toNat (Std.BitVec.ofNat k n) = n % 2 ^ k :=
+#print BitVec.toNat_ofNat /-
+theorem toNat_ofNat {k n : ℕ} : BitVec.toNat (BitVec.ofNat k n) = n % 2 ^ k :=
   by
   induction' k with k ih generalizing n
   · simp [Nat.mod_one]; rfl
   · rw [of_nat_succ, to_nat_append, ih, bits_to_nat_to_bool, mod_pow_succ, Nat.mul_comm]
-#align bitvec.to_nat_of_nat Std.BitVec.toNat_ofNat
+#align bitvec.to_nat_of_nat BitVec.toNat_ofNat
 -/
 
-#print Std.BitVec.toInt /-
+#print BitVec.toInt /-
 /-- Return the integer encoded by the input bitvector -/
-protected def Std.BitVec.toInt : ∀ {n : Nat}, Std.BitVec n → Int
+protected def toInt : ∀ {n : Nat}, BitVec n → Int
   | 0, _ => 0
   | succ n, v =>
-    cond (head v) (Int.negSucc <| Std.BitVec.toNat <| Std.BitVec.not <| tail v)
-      (Int.ofNat <| Std.BitVec.toNat <| tail v)
-#align bitvec.to_int Std.BitVec.toInt
+    cond (head v) (Int.negSucc <| BitVec.toNat <| not <| tail v)
+      (Int.ofNat <| BitVec.toNat <| tail v)
+#align bitvec.to_int BitVec.toInt
 -/
 
 end Conversion
@@ -435,17 +433,17 @@ end Conversion
 /-! ### Miscellaneous instances -/
 
 
-private def repr {n : Nat} : Std.BitVec n → String
+private def repr {n : Nat} : BitVec n → String
   | ⟨bs, p⟩ => "0b" ++ (bs.map fun b : Bool => if b then '1' else '0').asString
 
-instance (n : Nat) : Repr (Std.BitVec n) :=
+instance (n : Nat) : Repr (BitVec n) :=
   ⟨repr⟩
 
-end Std.BitVec
+end BitVec
 
-instance {n} {x y : Std.BitVec n} : Decidable (Std.BitVec.ult x y) :=
+instance {n} {x y : BitVec n} : Decidable (BitVec.ult x y) :=
   Bool.decidableEq _ _
 
-instance {n} {x y : Std.BitVec n} : Decidable (Std.BitVec.ugt x y) :=
+instance {n} {x y : BitVec n} : Decidable (BitVec.ugt x y) :=
   Bool.decidableEq _ _
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -21,15 +21,15 @@ It is not fully in compliance with mathlib style standards.
 -/
 
 
-#print Bitvec /-
+#print Std.BitVec /-
 /-- `bitvec n` is a `vector` of `bool` with length `n`. -/
 @[reducible]
-def Bitvec (n : ℕ) :=
+def Std.BitVec (n : ℕ) :=
   Vector Bool n
-#align bitvec Bitvec
+#align bitvec Std.BitVec
 -/
 
-namespace Bitvec
+namespace Std.BitVec
 
 open Nat
 
@@ -37,35 +37,35 @@ open Vector
 
 local infixl:65 "++ₜ" => Vector.append
 
-#print Bitvec.zero /-
+#print Std.BitVec.zero /-
 /-- Create a zero bitvector -/
 @[reducible]
-protected def zero (n : ℕ) : Bitvec n :=
+protected def Std.BitVec.zero (n : ℕ) : Std.BitVec n :=
   replicate n false
-#align bitvec.zero Bitvec.zero
+#align bitvec.zero Std.BitVec.zero
 -/
 
-#print Bitvec.one /-
+#print Std.BitVec.one /-
 /-- Create a bitvector of length `n` whose `n-1`st entry is 1 and other entries are 0. -/
 @[reducible]
-protected def one : ∀ n : ℕ, Bitvec n
+protected def Std.BitVec.one : ∀ n : ℕ, Std.BitVec n
   | 0 => nil
   | succ n => replicate n false++ₜtrue ::ᵥ nil
-#align bitvec.one Bitvec.one
+#align bitvec.one Std.BitVec.one
 -/
 
-#print Bitvec.cong /-
+#print Std.BitVec.cast /-
 /-- Create a bitvector from another with a provably equal length. -/
-protected def cong {a b : ℕ} (h : a = b) : Bitvec a → Bitvec b
+protected def Std.BitVec.cast {a b : ℕ} (h : a = b) : Std.BitVec a → Std.BitVec b
   | ⟨x, p⟩ => ⟨x, h ▸ p⟩
-#align bitvec.cong Bitvec.cong
+#align bitvec.cong Std.BitVec.cast
 -/
 
-#print Bitvec.append /-
+#print Std.BitVec.append /-
 /-- `bitvec` specific version of `vector.append` -/
-def append {m n} : Bitvec m → Bitvec n → Bitvec (m + n) :=
+def Std.BitVec.append {m n} : Std.BitVec m → Std.BitVec n → Std.BitVec (m + n) :=
   Vector.append
-#align bitvec.append Bitvec.append
+#align bitvec.append Std.BitVec.append
 -/
 
 /-! ### Shift operations -/
@@ -75,19 +75,19 @@ section Shift
 
 variable {n : ℕ}
 
-#print Bitvec.shl /-
+#print Std.BitVec.shiftLeft /-
 /-- `shl x i` is the bitvector obtained by left-shifting `x` `i` times and padding with `ff`.
 If `x.length < i` then this will return the all-`ff`s bitvector. -/
-def shl (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  Bitvec.cong (by simp) <| drop i x++ₜreplicate (min n i) false
-#align bitvec.shl Bitvec.shl
+def Std.BitVec.shiftLeft (x : Std.BitVec n) (i : ℕ) : Std.BitVec n :=
+  Std.BitVec.cast (by simp) <| drop i x++ₜreplicate (min n i) false
+#align bitvec.shl Std.BitVec.shiftLeft
 -/
 
 /-- `fill_shr x i fill` is the bitvector obtained by right-shifting `x` `i` times and then
 padding with `fill : bool`. If `x.length < i` then this will return the constant `fill`
 bitvector. -/
-def fillShr (x : Bitvec n) (i : ℕ) (fill : Bool) : Bitvec n :=
-  Bitvec.cong
+def Std.BitVec.fillShr (x : Std.BitVec n) (i : ℕ) (fill : Bool) : Std.BitVec n :=
+  Std.BitVec.cast
       (by
         by_cases i ≤ n
         · have h₁ := Nat.sub_le n i
@@ -96,21 +96,21 @@ def fillShr (x : Bitvec n) (i : ℕ) (fill : Bool) : Bitvec n :=
         · have h₁ := le_of_not_ge h
           rw [min_eq_left h₁, tsub_eq_zero_iff_le.mpr h₁, zero_min, Nat.add_zero]) <|
     replicate (min n i) fill++ₜtake (n - i) x
-#align bitvec.fill_shr Bitvec.fillShr
+#align bitvec.fill_shr Std.BitVec.fillShr
 
-#print Bitvec.ushr /-
+#print Std.BitVec.ushiftRight /-
 /-- unsigned shift right -/
-def ushr (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  fillShr x i false
-#align bitvec.ushr Bitvec.ushr
+def Std.BitVec.ushiftRight (x : Std.BitVec n) (i : ℕ) : Std.BitVec n :=
+  Std.BitVec.fillShr x i false
+#align bitvec.ushr Std.BitVec.ushiftRight
 -/
 
-#print Bitvec.sshr /-
+#print Std.BitVec.sshiftRight /-
 /-- signed shift right -/
-def sshr : ∀ {m : ℕ}, Bitvec m → ℕ → Bitvec m
+def Std.BitVec.sshiftRight : ∀ {m : ℕ}, Std.BitVec m → ℕ → Std.BitVec m
   | 0, _, _ => nil
-  | succ m, x, i => head x ::ᵥ fillShr (tail x) i (head x)
-#align bitvec.sshr Bitvec.sshr
+  | succ m, x, i => head x ::ᵥ Std.BitVec.fillShr (tail x) i (head x)
+#align bitvec.sshr Std.BitVec.sshiftRight
 -/
 
 end Shift
@@ -122,32 +122,32 @@ section Bitwise
 
 variable {n : ℕ}
 
-#print Bitvec.not /-
+#print Std.BitVec.not /-
 /-- bitwise not -/
-def not : Bitvec n → Bitvec n :=
+def Std.BitVec.not : Std.BitVec n → Std.BitVec n :=
   map not
-#align bitvec.not Bitvec.not
+#align bitvec.not Std.BitVec.not
 -/
 
-#print Bitvec.and /-
+#print Std.BitVec.and /-
 /-- bitwise and -/
-def and : Bitvec n → Bitvec n → Bitvec n :=
+def Std.BitVec.and : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
   map₂ and
-#align bitvec.and Bitvec.and
+#align bitvec.and Std.BitVec.and
 -/
 
-#print Bitvec.or /-
+#print Std.BitVec.or /-
 /-- bitwise or -/
-def or : Bitvec n → Bitvec n → Bitvec n :=
+def Std.BitVec.or : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
   map₂ or
-#align bitvec.or Bitvec.or
+#align bitvec.or Std.BitVec.or
 -/
 
-#print Bitvec.xor /-
+#print Std.BitVec.xor /-
 /-- bitwise xor -/
-def xor : Bitvec n → Bitvec n → Bitvec n :=
+def Std.BitVec.xor : Std.BitVec n → Std.BitVec n → Std.BitVec n :=
   map₂ xor
-#align bitvec.xor Bitvec.xor
+#align bitvec.xor Std.BitVec.xor
 -/
 
 end Bitwise
@@ -173,70 +173,70 @@ protected def carry (x y c : Bool) :=
 #align bitvec.carry Bool.carry
 -/
 
-#print Bitvec.neg /-
+#print Std.BitVec.neg /-
 /-- `neg x` is the two's complement of `x`. -/
-protected def neg (x : Bitvec n) : Bitvec n :=
+protected def Std.BitVec.neg (x : Std.BitVec n) : Std.BitVec n :=
   let f y c := (y || c, xor y c)
   Prod.snd (mapAccumr f x false)
-#align bitvec.neg Bitvec.neg
+#align bitvec.neg Std.BitVec.neg
 -/
 
-#print Bitvec.adc /-
+#print Std.BitVec.adc /-
 /-- Add with carry (no overflow) -/
-def adc (x y : Bitvec n) (c : Bool) : Bitvec (n + 1) :=
+def Std.BitVec.adc (x y : Std.BitVec n) (c : Bool) : Std.BitVec (n + 1) :=
   let f x y c := (Bool.carry x y c, Bool.xor3 x y c)
   let ⟨c, z⟩ := Vector.mapAccumr₂ f x y c
   c ::ᵥ z
-#align bitvec.adc Bitvec.adc
+#align bitvec.adc Std.BitVec.adc
 -/
 
-#print Bitvec.add /-
+#print Std.BitVec.add /-
 /-- The sum of two bitvectors -/
-protected def add (x y : Bitvec n) : Bitvec n :=
-  tail (adc x y false)
-#align bitvec.add Bitvec.add
+protected def Std.BitVec.add (x y : Std.BitVec n) : Std.BitVec n :=
+  tail (Std.BitVec.adc x y false)
+#align bitvec.add Std.BitVec.add
 -/
 
-#print Bitvec.sbb /-
+#print Std.BitVec.sbb /-
 /-- Subtract with borrow -/
-def sbb (x y : Bitvec n) (b : Bool) : Bool × Bitvec n :=
+def Std.BitVec.sbb (x y : Std.BitVec n) (b : Bool) : Bool × Std.BitVec n :=
   let f x y c := (Bool.carry (not x) y c, Bool.xor3 x y c)
   Vector.mapAccumr₂ f x y b
-#align bitvec.sbb Bitvec.sbb
+#align bitvec.sbb Std.BitVec.sbb
 -/
 
-#print Bitvec.sub /-
+#print Std.BitVec.sub /-
 /-- The difference of two bitvectors -/
-protected def sub (x y : Bitvec n) : Bitvec n :=
-  Prod.snd (sbb x y false)
-#align bitvec.sub Bitvec.sub
+protected def Std.BitVec.sub (x y : Std.BitVec n) : Std.BitVec n :=
+  Prod.snd (Std.BitVec.sbb x y false)
+#align bitvec.sub Std.BitVec.sub
 -/
 
-instance : Zero (Bitvec n) :=
-  ⟨Bitvec.zero n⟩
+instance : Zero (Std.BitVec n) :=
+  ⟨Std.BitVec.zero n⟩
 
-instance : One (Bitvec n) :=
-  ⟨Bitvec.one n⟩
+instance : One (Std.BitVec n) :=
+  ⟨Std.BitVec.one n⟩
 
-instance : Add (Bitvec n) :=
-  ⟨Bitvec.add⟩
+instance : Add (Std.BitVec n) :=
+  ⟨Std.BitVec.add⟩
 
-instance : Sub (Bitvec n) :=
-  ⟨Bitvec.sub⟩
+instance : Sub (Std.BitVec n) :=
+  ⟨Std.BitVec.sub⟩
 
-instance : Neg (Bitvec n) :=
-  ⟨Bitvec.neg⟩
+instance : Neg (Std.BitVec n) :=
+  ⟨Std.BitVec.neg⟩
 
-#print Bitvec.mul /-
+#print Std.BitVec.mul /-
 /-- The product of two bitvectors -/
-protected def mul (x y : Bitvec n) : Bitvec n :=
+protected def Std.BitVec.mul (x y : Std.BitVec n) : Std.BitVec n :=
   let f r b := cond b (r + r + y) (r + r)
   (toList x).foldl f 0
-#align bitvec.mul Bitvec.mul
+#align bitvec.mul Std.BitVec.mul
 -/
 
-instance : Mul (Bitvec n) :=
-  ⟨Bitvec.mul⟩
+instance : Mul (Std.BitVec n) :=
+  ⟨Std.BitVec.mul⟩
 
 end Arith
 
@@ -247,80 +247,84 @@ section Comparison
 
 variable {n : ℕ}
 
-#print Bitvec.uborrow /-
+#print Std.BitVec.ult /-
 /-- `uborrow x y` returns `tt` iff the "subtract with borrow" operation on `x`, `y` and `ff`
 required a borrow. -/
-def uborrow (x y : Bitvec n) : Bool :=
-  Prod.fst (sbb x y false)
-#align bitvec.uborrow Bitvec.uborrow
+def Std.BitVec.ult (x y : Std.BitVec n) : Bool :=
+  Prod.fst (Std.BitVec.sbb x y false)
+#align bitvec.uborrow Std.BitVec.ult
 -/
 
-#print Bitvec.Ult /-
+/- warning: bitvec.ult clashes with bitvec.uborrow -> Std.BitVec.ult
+Case conversion may be inaccurate. Consider using '#align bitvec.ult Std.BitVec.ultₓ'. -/
+#print Std.BitVec.ult /-
 /-- unsigned less-than proposition -/
-def Ult (x y : Bitvec n) : Prop :=
-  uborrow x y
-#align bitvec.ult Bitvec.Ult
+def Std.BitVec.ult (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.ult x y
+#align bitvec.ult Std.BitVec.ult
 -/
 
-#print Bitvec.Ugt /-
+#print Std.BitVec.ugt /-
 /-- unsigned greater-than proposition -/
-def Ugt (x y : Bitvec n) : Prop :=
-  Ult y x
-#align bitvec.ugt Bitvec.Ugt
+def Std.BitVec.ugt (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.ult y x
+#align bitvec.ugt Std.BitVec.ugt
 -/
 
-#print Bitvec.Ule /-
+#print Std.BitVec.ule /-
 /-- unsigned less-than-or-equal-to proposition -/
-def Ule (x y : Bitvec n) : Prop :=
-  ¬Ult y x
-#align bitvec.ule Bitvec.Ule
+def Std.BitVec.ule (x y : Std.BitVec n) : Prop :=
+  ¬Std.BitVec.ult y x
+#align bitvec.ule Std.BitVec.ule
 -/
 
-#print Bitvec.Uge /-
+#print Std.BitVec.uge /-
 /-- unsigned greater-than-or-equal-to proposition -/
-def Uge (x y : Bitvec n) : Prop :=
-  Ule y x
-#align bitvec.uge Bitvec.Uge
+def Std.BitVec.uge (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.ule y x
+#align bitvec.uge Std.BitVec.uge
 -/
 
-#print Bitvec.sborrow /-
+#print Std.BitVec.slt /-
 /-- `sborrow x y` returns `tt` iff `x < y` as two's complement integers -/
-def sborrow : ∀ {n : ℕ}, Bitvec n → Bitvec n → Bool
+def Std.BitVec.slt : ∀ {n : ℕ}, Std.BitVec n → Std.BitVec n → Bool
   | 0, _, _ => false
   | succ n, x, y =>
     match (head x, head y) with
     | (tt, ff) => true
     | (ff, tt) => false
-    | _ => uborrow (tail x) (tail y)
-#align bitvec.sborrow Bitvec.sborrow
+    | _ => Std.BitVec.ult (tail x) (tail y)
+#align bitvec.sborrow Std.BitVec.slt
 -/
 
-#print Bitvec.Slt /-
+/- warning: bitvec.slt clashes with bitvec.sborrow -> Std.BitVec.slt
+Case conversion may be inaccurate. Consider using '#align bitvec.slt Std.BitVec.sltₓ'. -/
+#print Std.BitVec.slt /-
 /-- signed less-than proposition -/
-def Slt (x y : Bitvec n) : Prop :=
-  sborrow x y
-#align bitvec.slt Bitvec.Slt
+def Std.BitVec.slt (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.slt x y
+#align bitvec.slt Std.BitVec.slt
 -/
 
-#print Bitvec.Sgt /-
+#print Std.BitVec.sgt /-
 /-- signed greater-than proposition -/
-def Sgt (x y : Bitvec n) : Prop :=
-  Slt y x
-#align bitvec.sgt Bitvec.Sgt
+def Std.BitVec.sgt (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.slt y x
+#align bitvec.sgt Std.BitVec.sgt
 -/
 
-#print Bitvec.Sle /-
+#print Std.BitVec.sle /-
 /-- signed less-than-or-equal-to proposition -/
-def Sle (x y : Bitvec n) : Prop :=
-  ¬Slt y x
-#align bitvec.sle Bitvec.Sle
+def Std.BitVec.sle (x y : Std.BitVec n) : Prop :=
+  ¬Std.BitVec.slt y x
+#align bitvec.sle Std.BitVec.sle
 -/
 
-#print Bitvec.Sge /-
+#print Std.BitVec.sge /-
 /-- signed greater-than-or-equal-to proposition -/
-def Sge (x y : Bitvec n) : Prop :=
-  Sle y x
-#align bitvec.sge Bitvec.Sge
+def Std.BitVec.sge (x y : Std.BitVec n) : Prop :=
+  Std.BitVec.sle y x
+#align bitvec.sge Std.BitVec.sge
 -/
 
 end Comparison
@@ -332,57 +336,54 @@ section Conversion
 
 variable {α : Type}
 
-#print Bitvec.ofNat /-
+#print Std.BitVec.ofNat /-
 /-- Create a bitvector from a `nat` -/
-protected def ofNat : ∀ n : ℕ, Nat → Bitvec n
+protected def Std.BitVec.ofNat : ∀ n : ℕ, Nat → Std.BitVec n
   | 0, x => nil
   | succ n, x => of_nat n (x / 2)++ₜdecide (x % 2 = 1) ::ᵥ nil
-#align bitvec.of_nat Bitvec.ofNat
+#align bitvec.of_nat Std.BitVec.ofNat
 -/
 
-#print Bitvec.ofInt /-
+#print Std.BitVec.ofInt /-
 /-- Create a bitvector in the two's complement representation from an `int` -/
-protected def ofInt : ∀ n : ℕ, Int → Bitvec (succ n)
-  | n, Int.ofNat m => false ::ᵥ Bitvec.ofNat n m
-  | n, Int.negSucc m => true ::ᵥ not (Bitvec.ofNat n m)
-#align bitvec.of_int Bitvec.ofInt
+protected def Std.BitVec.ofInt : ∀ n : ℕ, Int → Std.BitVec (succ n)
+  | n, Int.ofNat m => false ::ᵥ Std.BitVec.ofNat n m
+  | n, Int.negSucc m => true ::ᵥ Std.BitVec.not (Std.BitVec.ofNat n m)
+#align bitvec.of_int Std.BitVec.ofInt
 -/
 
-#print Bitvec.addLsb /-
+#print Std.BitVec.addLsb /-
 /-- `add_lsb r b` is `r + r + 1` if `b` is `tt` and `r + r` otherwise. -/
-def addLsb (r : ℕ) (b : Bool) :=
+def Std.BitVec.addLsb (r : ℕ) (b : Bool) :=
   r + r + cond b 1 0
-#align bitvec.add_lsb Bitvec.addLsb
+#align bitvec.add_lsb Std.BitVec.addLsb
 -/
 
-#print Bitvec.bitsToNat /-
 /-- Given a `list` of `bool`s, return the `nat` they represent as a list of binary digits. -/
-def bitsToNat (v : List Bool) : Nat :=
-  v.foldl addLsb 0
-#align bitvec.bits_to_nat Bitvec.bitsToNat
--/
+def Std.BitVec.bitsToNat (v : List Bool) : Nat :=
+  v.foldl Std.BitVec.addLsb 0
+#align bitvec.bits_to_nat Std.BitVec.bitsToNat
 
-#print Bitvec.toNat /-
+#print Std.BitVec.toNat /-
 /-- Return the natural number encoded by the input bitvector -/
-protected def toNat {n : Nat} (v : Bitvec n) : Nat :=
-  bitsToNat (toList v)
-#align bitvec.to_nat Bitvec.toNat
+protected def Std.BitVec.toNat {n : Nat} (v : Std.BitVec n) : Nat :=
+  Std.BitVec.bitsToNat (toList v)
+#align bitvec.to_nat Std.BitVec.toNat
 -/
 
-#print Bitvec.bitsToNat_toList /-
-theorem bitsToNat_toList {n : ℕ} (x : Bitvec n) : Bitvec.toNat x = bitsToNat (Vector.toList x) :=
+theorem Std.BitVec.bitsToNat_toList {n : ℕ} (x : Std.BitVec n) :
+    Std.BitVec.toNat x = Std.BitVec.bitsToNat (Vector.toList x) :=
   rfl
-#align bitvec.bits_to_nat_to_list Bitvec.bitsToNat_toList
--/
+#align bitvec.bits_to_nat_to_list Std.BitVec.bitsToNat_toList
 
 attribute [local simp] Nat.add_comm Nat.add_assoc Nat.add_left_comm Nat.mul_comm Nat.mul_assoc
 
 attribute [local simp] Nat.zero_add Nat.add_zero Nat.one_mul Nat.mul_one Nat.zero_mul Nat.mul_zero
 
-#print Bitvec.toNat_append /-
+#print Std.BitVec.toNat_append /-
 -- mul_left_comm
-theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
-    Bitvec.toNat (xs++ₜb ::ᵥ nil) = Bitvec.toNat xs * 2 + Bitvec.toNat (b ::ᵥ nil) :=
+theorem Std.BitVec.toNat_append {m : ℕ} (xs : Std.BitVec m) (b : Bool) :
+    Std.BitVec.toNat (xs++ₜb ::ᵥ nil) = Std.BitVec.toNat xs * 2 + Std.BitVec.toNat (b ::ᵥ nil) :=
   by
   cases' xs with xs P
   simp [bits_to_nat_to_list]; clear P
@@ -394,42 +395,39 @@ theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
   induction' xs with x xs generalizing x
   · simp; unfold List.foldl add_lsb; simp [Nat.mul_succ]
   · simp; apply xs_ih
-#align bitvec.to_nat_append Bitvec.toNat_append
+#align bitvec.to_nat_append Std.BitVec.toNat_append
 -/
 
-#print Bitvec.bits_toNat_decide /-
-theorem bits_toNat_decide (n : ℕ) : Bitvec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
+theorem Std.BitVec.bits_toNat_decide (n : ℕ) :
+    Std.BitVec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
   by
   simp [bits_to_nat_to_list]
   unfold bits_to_nat add_lsb List.foldl cond
   simp [cond_to_bool_mod_two]
-#align bitvec.bits_to_nat_to_bool Bitvec.bits_toNat_decide
--/
+#align bitvec.bits_to_nat_to_bool Std.BitVec.bits_toNat_decide
 
-#print Bitvec.ofNat_succ /-
-theorem ofNat_succ {k n : ℕ} :
-    Bitvec.ofNat (succ k) n = Bitvec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
+theorem Std.BitVec.ofNat_succ {k n : ℕ} :
+    Std.BitVec.ofNat (succ k) n = Std.BitVec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
   rfl
-#align bitvec.of_nat_succ Bitvec.ofNat_succ
--/
+#align bitvec.of_nat_succ Std.BitVec.ofNat_succ
 
-#print Bitvec.toNat_ofNat /-
-theorem toNat_ofNat {k n : ℕ} : Bitvec.toNat (Bitvec.ofNat k n) = n % 2 ^ k :=
+#print Std.BitVec.toNat_ofNat /-
+theorem Std.BitVec.toNat_ofNat {k n : ℕ} : Std.BitVec.toNat (Std.BitVec.ofNat k n) = n % 2 ^ k :=
   by
   induction' k with k ih generalizing n
   · simp [Nat.mod_one]; rfl
   · rw [of_nat_succ, to_nat_append, ih, bits_to_nat_to_bool, mod_pow_succ, Nat.mul_comm]
-#align bitvec.to_nat_of_nat Bitvec.toNat_ofNat
+#align bitvec.to_nat_of_nat Std.BitVec.toNat_ofNat
 -/
 
-#print Bitvec.toInt /-
+#print Std.BitVec.toInt /-
 /-- Return the integer encoded by the input bitvector -/
-protected def toInt : ∀ {n : Nat}, Bitvec n → Int
+protected def Std.BitVec.toInt : ∀ {n : Nat}, Std.BitVec n → Int
   | 0, _ => 0
   | succ n, v =>
-    cond (head v) (Int.negSucc <| Bitvec.toNat <| not <| tail v)
-      (Int.ofNat <| Bitvec.toNat <| tail v)
-#align bitvec.to_int Bitvec.toInt
+    cond (head v) (Int.negSucc <| Std.BitVec.toNat <| Std.BitVec.not <| tail v)
+      (Int.ofNat <| Std.BitVec.toNat <| tail v)
+#align bitvec.to_int Std.BitVec.toInt
 -/
 
 end Conversion
@@ -437,17 +435,17 @@ end Conversion
 /-! ### Miscellaneous instances -/
 
 
-private def repr {n : Nat} : Bitvec n → String
+private def repr {n : Nat} : Std.BitVec n → String
   | ⟨bs, p⟩ => "0b" ++ (bs.map fun b : Bool => if b then '1' else '0').asString
 
-instance (n : Nat) : Repr (Bitvec n) :=
+instance (n : Nat) : Repr (Std.BitVec n) :=
   ⟨repr⟩
 
-end Bitvec
+end Std.BitVec
 
-instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ult x y) :=
+instance {n} {x y : Std.BitVec n} : Decidable (Std.BitVec.ult x y) :=
   Bool.decidableEq _ _
 
-instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ugt x y) :=
+instance {n} {x y : Std.BitVec n} : Decidable (Std.BitVec.ugt x y) :=
   Bool.decidableEq _ _
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -3,8 +3,8 @@ Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Joe Hendrix, Sebastian Ullrich
 -/
-import Mathbin.Data.Vector.Basic
-import Mathbin.Data.Nat.Pow
+import Data.Vector.Basic
+import Data.Nat.Pow
 
 #align_import data.bitvec.core from "leanprover-community/mathlib"@"a11f9106a169dd302a285019e5165f8ab32ff433"
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/48a058d7e39a80ed56858505719a0b2197900999

@@ -83,7 +83,6 @@ def shl (x : Bitvec n) (i : ℕ) : Bitvec n :=
 #align bitvec.shl Bitvec.shl
 -/
 
-#print Bitvec.fillShr /-
 /-- `fill_shr x i fill` is the bitvector obtained by right-shifting `x` `i` times and then
 padding with `fill : bool`. If `x.length < i` then this will return the constant `fill`
 bitvector. -/
@@ -98,7 +97,6 @@ def fillShr (x : Bitvec n) (i : ℕ) (fill : Bool) : Bitvec n :=
           rw [min_eq_left h₁, tsub_eq_zero_iff_le.mpr h₁, zero_min, Nat.add_zero]) <|
     replicate (min n i) fill++ₜtake (n - i) x
 #align bitvec.fill_shr Bitvec.fillShr
--/
 
 #print Bitvec.ushr /-
 /-- unsigned shift right -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

@@ -2,15 +2,12 @@
 Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Joe Hendrix, Sebastian Ullrich
-
-! This file was ported from Lean 3 source module data.bitvec.core
-! leanprover-community/mathlib commit a11f9106a169dd302a285019e5165f8ab32ff433
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Vector.Basic
 import Mathbin.Data.Nat.Pow
 
+#align_import data.bitvec.core from "leanprover-community/mathlib"@"a11f9106a169dd302a285019e5165f8ab32ff433"
+
 /-!
 # Basic operations on bitvectors
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9240e8be927a0955b9a82c6c85ef499ee3a626b8

@@ -164,18 +164,18 @@ section Arith
 
 variable {n : ℕ}
 
-#print Bitvec.xor3 /-
+#print Bool.xor3 /-
 /-- `xor3 x y c` is `((x XOR y) XOR c)`. -/
 protected def xor3 (x y c : Bool) :=
   xor (xor x y) c
-#align bitvec.xor3 Bitvec.xor3
+#align bitvec.xor3 Bool.xor3
 -/
 
-#print Bitvec.carry /-
+#print Bool.carry /-
 /-- `carry x y c` is `x && y || x && c || y && c`. -/
 protected def carry (x y c : Bool) :=
   x && y || x && c || y && c
-#align bitvec.carry Bitvec.carry
+#align bitvec.carry Bool.carry
 -/
 
 #print Bitvec.neg /-
@@ -189,7 +189,7 @@ protected def neg (x : Bitvec n) : Bitvec n :=
 #print Bitvec.adc /-
 /-- Add with carry (no overflow) -/
 def adc (x y : Bitvec n) (c : Bool) : Bitvec (n + 1) :=
-  let f x y c := (Bitvec.carry x y c, Bitvec.xor3 x y c)
+  let f x y c := (Bool.carry x y c, Bool.xor3 x y c)
   let ⟨c, z⟩ := Vector.mapAccumr₂ f x y c
   c ::ᵥ z
 #align bitvec.adc Bitvec.adc
@@ -205,7 +205,7 @@ protected def add (x y : Bitvec n) : Bitvec n :=
 #print Bitvec.sbb /-
 /-- Subtract with borrow -/
 def sbb (x y : Bitvec n) (b : Bool) : Bool × Bitvec n :=
-  let f x y c := (Bitvec.carry (not x) y c, Bitvec.xor3 x y c)
+  let f x y c := (Bool.carry (not x) y c, Bool.xor3 x y c)
   Vector.mapAccumr₂ f x y b
 #align bitvec.sbb Bitvec.sbb
 -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -38,7 +38,6 @@ open Nat
 
 open Vector
 
--- mathport name: «expr ++ₜ »
 local infixl:65 "++ₜ" => Vector.append
 
 #print Bitvec.zero /-
@@ -346,11 +345,13 @@ protected def ofNat : ∀ n : ℕ, Nat → Bitvec n
 #align bitvec.of_nat Bitvec.ofNat
 -/
 
+#print Bitvec.ofInt /-
 /-- Create a bitvector in the two's complement representation from an `int` -/
 protected def ofInt : ∀ n : ℕ, Int → Bitvec (succ n)
   | n, Int.ofNat m => false ::ᵥ Bitvec.ofNat n m
   | n, Int.negSucc m => true ::ᵥ not (Bitvec.ofNat n m)
 #align bitvec.of_int Bitvec.ofInt
+-/
 
 #print Bitvec.addLsb /-
 /-- `add_lsb r b` is `r + r + 1` if `b` is `tt` and `r + r` otherwise. -/
@@ -401,17 +402,21 @@ theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
 #align bitvec.to_nat_append Bitvec.toNat_append
 -/
 
+#print Bitvec.bits_toNat_decide /-
 theorem bits_toNat_decide (n : ℕ) : Bitvec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
   by
   simp [bits_to_nat_to_list]
   unfold bits_to_nat add_lsb List.foldl cond
   simp [cond_to_bool_mod_two]
 #align bitvec.bits_to_nat_to_bool Bitvec.bits_toNat_decide
+-/
 
+#print Bitvec.ofNat_succ /-
 theorem ofNat_succ {k n : ℕ} :
     Bitvec.ofNat (succ k) n = Bitvec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
   rfl
 #align bitvec.of_nat_succ Bitvec.ofNat_succ
+-/
 
 #print Bitvec.toNat_ofNat /-
 theorem toNat_ofNat {k n : ℕ} : Bitvec.toNat (Bitvec.ofNat k n) = n % 2 ^ k :=

mathlib commit https://github.com/leanprover-community/mathlib/commit/31c24aa72e7b3e5ed97a8412470e904f82b81004

@@ -346,13 +346,11 @@ protected def ofNat : ∀ n : ℕ, Nat → Bitvec n
 #align bitvec.of_nat Bitvec.ofNat
 -/
 
-#print Bitvec.ofInt /-
 /-- Create a bitvector in the two's complement representation from an `int` -/
 protected def ofInt : ∀ n : ℕ, Int → Bitvec (succ n)
   | n, Int.ofNat m => false ::ᵥ Bitvec.ofNat n m
   | n, Int.negSucc m => true ::ᵥ not (Bitvec.ofNat n m)
 #align bitvec.of_int Bitvec.ofInt
--/
 
 #print Bitvec.addLsb /-
 /-- `add_lsb r b` is `r + r + 1` if `b` is `tt` and `r + r` otherwise. -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -403,12 +403,6 @@ theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
 #align bitvec.to_nat_append Bitvec.toNat_append
 -/
 
-/- warning: bitvec.bits_to_nat_to_bool -> Bitvec.bits_toNat_decide is a dubious translation:
-lean 3 declaration is
-  forall (n : Nat), Eq.{1} Nat (Bitvec.toNat (Nat.succ (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Vector.cons.{0} Bool (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (Decidable.decide (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Nat.decidableEq (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Vector.nil.{0} Bool))) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))
-but is expected to have type
-  forall (n : Nat), Eq.{1} Nat (Bitvec.toNat (Nat.succ (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Vector.cons.{0} Bool (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (Decidable.decide (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (instDecidableEqNat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Vector.nil.{0} Bool))) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)))
-Case conversion may be inaccurate. Consider using '#align bitvec.bits_to_nat_to_bool Bitvec.bits_toNat_decideₓ'. -/
 theorem bits_toNat_decide (n : ℕ) : Bitvec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 :=
   by
   simp [bits_to_nat_to_list]
@@ -416,12 +410,6 @@ theorem bits_toNat_decide (n : ℕ) : Bitvec.toNat (decide (n % 2 = 1) ::ᵥ nil
   simp [cond_to_bool_mod_two]
 #align bitvec.bits_to_nat_to_bool Bitvec.bits_toNat_decide
 
-/- warning: bitvec.of_nat_succ -> Bitvec.ofNat_succ is a dubious translation:
-lean 3 declaration is
-  forall {k : Nat} {n : Nat}, Eq.{1} (Bitvec (Nat.succ k)) (Bitvec.ofNat (Nat.succ k) n) (Vector.append.{0} Bool k (Nat.succ (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) (Bitvec.ofNat k (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) (Vector.cons.{0} Bool (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) (Decidable.decide (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Nat.decidableEq (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) n (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Vector.nil.{0} Bool)))
-but is expected to have type
-  forall {k : Nat} {n : Nat}, Eq.{1} (Bitvec (Nat.succ k)) (Bitvec.ofNat (Nat.succ k) n) (Vector.append.{0} Bool k (Nat.succ (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) (Bitvec.ofNat k (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)))) (Vector.cons.{0} Bool (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) (Decidable.decide (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (instDecidableEqNat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) n (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Vector.nil.{0} Bool)))
-Case conversion may be inaccurate. Consider using '#align bitvec.of_nat_succ Bitvec.ofNat_succₓ'. -/
 theorem ofNat_succ {k n : ℕ} :
     Bitvec.ofNat (succ k) n = Bitvec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
   rfl

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -398,11 +398,8 @@ theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
   conv in add_lsb x b => rw [← h]; clear h
   simp
   induction' xs with x xs generalizing x
-  · simp
-    unfold List.foldl add_lsb
-    simp [Nat.mul_succ]
-  · simp
-    apply xs_ih
+  · simp; unfold List.foldl add_lsb; simp [Nat.mul_succ]
+  · simp; apply xs_ih
 #align bitvec.to_nat_append Bitvec.toNat_append
 -/
 
@@ -434,8 +431,7 @@ theorem ofNat_succ {k n : ℕ} :
 theorem toNat_ofNat {k n : ℕ} : Bitvec.toNat (Bitvec.ofNat k n) = n % 2 ^ k :=
   by
   induction' k with k ih generalizing n
-  · simp [Nat.mod_one]
-    rfl
+  · simp [Nat.mod_one]; rfl
   · rw [of_nat_succ, to_nat_append, ih, bits_to_nat_to_bool, mod_pow_succ, Nat.mul_comm]
 #align bitvec.to_nat_of_nat Bitvec.toNat_ofNat
 -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -457,7 +457,6 @@ end Conversion
 
 private def repr {n : Nat} : Bitvec n → String
   | ⟨bs, p⟩ => "0b" ++ (bs.map fun b : Bool => if b then '1' else '0').asString
-#align bitvec.repr bitvec.repr
 
 instance (n : Nat) : Repr (Bitvec n) :=
   ⟨repr⟩

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

The lemmas can easily be moved to Data.Nat.Bits and Data.Int.Bitwise respectively.

@@ -3,9 +3,9 @@ Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Joe Hendrix, Sebastian Ullrich, Harun Khan, Alex Keizer, Abdalrhman M Mohamed
 -/
+import Mathlib.Data.Nat.Bits
 import Mathlib.Data.Fin.Basic
 import Mathlib.Data.ZMod.Defs
-import Mathlib.Init.Data.Nat.Bitwise
 import Std.Data.BitVec
 
 #align_import data.bitvec.core from "leanprover-community/mathlib"@"1126441d6bccf98c81214a0780c73d499f6721fe"

Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.

Other changes

• Move the last few lemmas left in Data.Nat.Pow to Algebra.GroupPower.Order
• Move the deprecated aliases from Data.Nat.Pow to Algebra.GroupPower.Order
• Move the bit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.Bits
• Fix some fallout from not importing Data.Nat.Order.Basic anymore
• Add a few Nat-specific lemmas to help fix the fallout (look for nolint simpNF)
• Turn Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)
• Make more arguments to Nat.one_lt_pow implicit

@@ -3,9 +3,9 @@ Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Joe Hendrix, Sebastian Ullrich, Harun Khan, Alex Keizer, Abdalrhman M Mohamed
 -/
-
 import Mathlib.Data.Fin.Basic
 import Mathlib.Data.ZMod.Defs
+import Mathlib.Init.Data.Nat.Bitwise
 import Std.Data.BitVec
 
 #align_import data.bitvec.core from "leanprover-community/mathlib"@"1126441d6bccf98c81214a0780c73d499f6721fe"

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

@@ -27,10 +27,10 @@ Here we define a few more operations on these bitvectors
 
 variable {w v : Nat}
 
-namespace Std.BitVec
+namespace BitVec
 
-#align bitvec Std.BitVec
-#align bitvec.zero Std.BitVec.zero
+#align bitvec BitVec
+#align bitvec.zero BitVec.zero
 
 /-!
 ## Constants
@@ -39,84 +39,84 @@ namespace Std.BitVec
 /-- The bitvector representing `1`.
     That is, the bitvector with least-significant bit `1` and all other bits `0` -/
 @[simp] abbrev one (w : ℕ) : BitVec w := 1
-#align bitvec.one Std.BitVec.one
+#align bitvec.one BitVec.one
 
-#align bitvec.cong Std.BitVec.cast
-#align bitvec.append Std.BitVec.append
-#align bitvec.shl Std.BitVec.shiftLeft
-#align bitvec.ushr Std.BitVec.ushiftRight
-#align bitvec.sshr Std.BitVec.sshiftRight
+#align bitvec.cong BitVec.cast
+#align bitvec.append BitVec.append
+#align bitvec.shl BitVec.shiftLeft
+#align bitvec.ushr BitVec.ushiftRight
+#align bitvec.sshr BitVec.sshiftRight
 
 /-! ### Bitwise operations -/
 
-#align bitvec.not Std.BitVec.not
-#align bitvec.and Std.BitVec.and
-#align bitvec.or Std.BitVec.or
-#align bitvec.xor Std.BitVec.xor
+#align bitvec.not BitVec.not
+#align bitvec.and BitVec.and
+#align bitvec.or BitVec.or
+#align bitvec.xor BitVec.xor
 
 /-! ### Arithmetic operators -/
 
-#align bitvec.neg Std.BitVec.neg
+#align bitvec.neg BitVec.neg
 /-- Add with carry (no overflow)
 
 See also `Std.BitVec.adc`, which stores the carry bit separately. -/
 def adc' {n} (x y : BitVec n) (c : Bool) : BitVec (n+1) :=
   let a := x.adc y c; .cons a.1 a.2
-#align bitvec.adc Std.BitVec.adc
+#align bitvec.adc BitVec.adc
 
-#align bitvec.add Std.BitVec.add
+#align bitvec.add BitVec.add
 
 /-- Subtract with borrow -/
 def sbb {n} (x y : BitVec n) (b : Bool) : Bool × BitVec n :=
   let y := y + ofFin b.toNat
   (x < y, x - y)
-#align bitvec.sbb Std.BitVec.sbb
+#align bitvec.sbb BitVec.sbb
 
-#align bitvec.sub Std.BitVec.sub
-#align bitvec.mul Std.BitVec.mul
+#align bitvec.sub BitVec.sub
+#align bitvec.mul BitVec.mul
 
 /-! ### Comparison operators -/
 
-#align bitvec.uborrow Std.BitVec.ult
-#align bitvec.ult Std.BitVec.ult
+#align bitvec.uborrow BitVec.ult
+#align bitvec.ult BitVec.ult
 
 /-- Unsigned greater than for bitvectors. -/
 protected def ugt (x y : BitVec w) : Bool := BitVec.ult y x
-#align bitvec.ugt Std.BitVec.ugt
+#align bitvec.ugt BitVec.ugt
 
-#align bitvec.ule Std.BitVec.ule
+#align bitvec.ule BitVec.ule
 
 /-- Signed greater than or equal to for bitvectors. -/
 protected def uge (x y : BitVec w) : Bool := BitVec.ule y x
-#align bitvec.uge Std.BitVec.uge
+#align bitvec.uge BitVec.uge
 
-#align bitvec.sborrow Std.BitVec.slt
-#align bitvec.slt Std.BitVec.slt
+#align bitvec.sborrow BitVec.slt
+#align bitvec.slt BitVec.slt
 
 /-- Signed greater than for bitvectors. -/
 protected def sgt (x y : BitVec w) : Bool := BitVec.slt y x
-#align bitvec.sgt Std.BitVec.sgt
+#align bitvec.sgt BitVec.sgt
 
-#align bitvec.sle Std.BitVec.sle
+#align bitvec.sle BitVec.sle
 
 /-- Signed greater than or equal to for bitvectors. -/
 protected def sge (x y : BitVec w) : Bool := BitVec.sle y x
-#align bitvec.sge Std.BitVec.sge
+#align bitvec.sge BitVec.sge
 
 /-! ### Conversion to `nat` and `int` -/
 
-#align bitvec.of_nat Std.BitVec.ofNat
+#align bitvec.of_nat BitVec.ofNat
 
 /-- `addLsb r b` is `r + r + 1` if `b` is `true` and `r + r` otherwise. -/
 def addLsb (r : ℕ) (b : Bool) :=
   Nat.bit b r
-#align bitvec.add_lsb Std.BitVec.addLsb
+#align bitvec.add_lsb BitVec.addLsb
 
 #noalign bitvec.bits_to_nat
-#align bitvec.to_nat Std.BitVec.toNat
-#align bitvec.of_fin Std.BitVec.ofFin
-#align bitvec.to_fin Std.BitVec.toFin
-#align bitvec.to_int Std.BitVec.toInt
+#align bitvec.to_nat BitVec.toNat
+#align bitvec.of_fin BitVec.ofFin
+#align bitvec.to_fin BitVec.toFin
+#align bitvec.to_int BitVec.toInt
 
 
 /-- Return the `i`-th least significant bit, where `i` is a statically known in-bounds index -/
@@ -143,4 +143,4 @@ instance : SMul ℕ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
 instance : SMul ℤ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
 instance : Pow (BitVec w) ℕ  := ⟨fun x n => ofFin <| x.toFin ^ n⟩
 
-end Std.BitVec
+end BitVec

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -142,7 +142,5 @@ def toBEList (x : BitVec w) : List Bool :=
 instance : SMul ℕ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
 instance : SMul ℤ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
 instance : Pow (BitVec w) ℕ  := ⟨fun x n => ofFin <| x.toFin ^ n⟩
-instance : NatCast (BitVec w) := ⟨BitVec.ofNat w⟩
-instance : IntCast (BitVec w) := ⟨BitVec.ofInt w⟩
 
 end Std.BitVec

• depends on: #9830
• depends on: #9772
• depends on: #9996

This checks files for unused imports. The output here is piped through gh-problem-matcher-wrap so that it will show up as annotations.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

@@ -5,7 +5,6 @@ Authors: Joe Hendrix, Sebastian Ullrich, Harun Khan, Alex Keizer, Abdalrhman M M
 -/
 
 import Mathlib.Data.Fin.Basic
-import Mathlib.Data.Nat.Bitwise
 import Mathlib.Data.ZMod.Defs
 import Std.Data.BitVec
 

Co-authored-by: Tobias Grosser <tobias@grosser.es> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -140,4 +140,10 @@ def toLEList (x : BitVec w) : List Bool :=
 def toBEList (x : BitVec w) : List Bool :=
   List.ofFn x.getMsb'
 
+instance : SMul ℕ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
+instance : SMul ℤ (BitVec w) := ⟨fun x y => ofFin <| x • y.toFin⟩
+instance : Pow (BitVec w) ℕ  := ⟨fun x n => ofFin <| x.toFin ^ n⟩
+instance : NatCast (BitVec w) := ⟨BitVec.ofNat w⟩
+instance : IntCast (BitVec w) := ⟨BitVec.ofInt w⟩
+
 end Std.BitVec

Notably leanprover/std4#366 changed the definition of testBit (to something equivalent) when upstreaming it, which broke a handful of proofs.

Other conflicting changes in Std, resolved for now by priming the mathlib name:

• Std.BitVec.adc: the type was changed from BitVec (n + 1) to Bool × BitVec w
• Nat.mul_add_mod: the type was changed from (a * b + c) % b = c % b to (b * a + c) % b = c % b

Zulip thread

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Alex Keizer <alex@keizer.dev> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -58,9 +58,11 @@ namespace Std.BitVec
 /-! ### Arithmetic operators -/
 
 #align bitvec.neg Std.BitVec.neg
-/-- Add with carry (no overflow) -/
-def adc {n} (x y : BitVec n) (c : Bool) : BitVec (n+1) :=
-  ofFin (x.toNat + y.toNat + c.toNat)
+/-- Add with carry (no overflow)
+
+See also `Std.BitVec.adc`, which stores the carry bit separately. -/
+def adc' {n} (x y : BitVec n) (c : Bool) : BitVec (n+1) :=
+  let a := x.adc y c; .cons a.1 a.2
 #align bitvec.adc Std.BitVec.adc
 
 #align bitvec.add Std.BitVec.add

re-adding definitions and theorems about bitvectors that mathlib has for Bitvec to the new Std.BitVec type, and getting rid of the former.

In std, the choice was made to define ult (unsigned less than) and related comparisons as Bool-valued, where the corresponding defs for Bitvec in mathlib are Prop-valued. Std does not have definitions for the respective greater-equal or greater-than comparisons, so we add those here, but we choose to be consistent with std and make them Bool-valued as well, breaking with the old API.

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Alex Keizer <alex@keizer.dev> Co-authored-by: Harun Khan <harun19@stanford.edu>

@@ -1,339 +1,141 @@
 /-
 Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
-Authors: Joe Hendrix, Sebastian Ullrich
+Authors: Joe Hendrix, Sebastian Ullrich, Harun Khan, Alex Keizer, Abdalrhman M Mohamed
 -/
-import Mathlib.Data.Vector.Basic
-import Mathlib.Data.Nat.Pow
-import Init.Data.Format.Basic
-import Mathlib.Init.Data.Nat.Lemmas
+
+import Mathlib.Data.Fin.Basic
+import Mathlib.Data.Nat.Bitwise
+import Mathlib.Data.ZMod.Defs
+import Std.Data.BitVec
 
 #align_import data.bitvec.core from "leanprover-community/mathlib"@"1126441d6bccf98c81214a0780c73d499f6721fe"
+
 /-!
 # Basic operations on bitvectors
 
-This is a work-in-progress, and contains additions to other theories.
-
-This file was moved to mathlib from core Lean in the switch to Lean 3.20.0c.
-It is not fully in compliance with mathlib style standards.
--/
-
-/-- `Bitvec n` is a `Vector` of `Bool` with length `n`. -/
-@[reducible]
-def Bitvec (n : ℕ) :=
-  Vector Bool n
-#align bitvec Bitvec
-
-namespace Bitvec
-
-open Nat
+Std has defined bitvector of length `w` as `Fin (2^w)`.
+Here we define a few more operations on these bitvectors
 
-open Vector
+## Main definitions
 
--- mathport name: «expr ++ₜ »
-local infixl:65 "++ₜ" => Vector.append
+* `Std.BitVec.sgt`: Signed greater-than comparison of bitvectors
+* `Std.BitVec.sge`: Signed greater-equals comparison of bitvectors
+* `Std.BitVec.ugt`: Unsigned greater-than comparison of bitvectors
+* `Std.BitVec.uge`: Unsigned greater-equals comparison of bitvectors
 
-/-- Create a zero bitvector -/
-@[reducible]
-protected def zero (n : ℕ) : Bitvec n :=
-  replicate n false
-#align bitvec.zero Bitvec.zero
-
-/-- Create a bitvector of length `n` whose `n-1`st entry is 1 and other entries are 0. -/
-@[reducible]
-protected def one : ∀ n : ℕ, Bitvec n
-  | 0 => nil
-  | succ n => replicate n false++ₜtrue ::ᵥ nil
-#align bitvec.one Bitvec.one
-
-/-- Create a bitvector from another with a provably equal length. -/
-protected def cong {a b : ℕ} : a = b → Bitvec a → Bitvec b :=
-  Vector.congr
-#align bitvec.cong Bitvec.cong
-
-/-- `Bitvec` specific version of `Vector.append` -/
-def append {m n} : Bitvec m → Bitvec n → Bitvec (m + n) :=
-  Vector.append
-#align bitvec.append Bitvec.append
-
-/-! ### Shift operations -/
-
-
-section Shift
+-/
 
-variable {n : ℕ}
+variable {w v : Nat}
 
-/-- `shl x i` is the bitvector obtained by left-shifting `x` `i` times and padding with `false`.
-If `x.length < i` then this will return the all-`false`s bitvector. -/
-def shl (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  shiftLeftFill x i false
-#align bitvec.shl Bitvec.shl
+namespace Std.BitVec
 
-#noalign bitvec.fill_shr
+#align bitvec Std.BitVec
+#align bitvec.zero Std.BitVec.zero
 
-/-- unsigned shift right -/
-def ushr (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  shiftRightFill x i false
-#align bitvec.ushr Bitvec.ushr
+/-!
+## Constants
+-/
 
-/-- signed shift right -/
-def sshr : ∀ {m : ℕ}, Bitvec m → ℕ → Bitvec m
-  | 0, _, _ => nil
-  | succ _, x, i => head x ::ᵥ shiftRightFill (tail x) i (head x)
-#align bitvec.sshr Bitvec.sshr
+/-- The bitvector representing `1`.
+    That is, the bitvector with least-significant bit `1` and all other bits `0` -/
+@[simp] abbrev one (w : ℕ) : BitVec w := 1
+#align bitvec.one Std.BitVec.one
 
-end Shift
+#align bitvec.cong Std.BitVec.cast
+#align bitvec.append Std.BitVec.append
+#align bitvec.shl Std.BitVec.shiftLeft
+#align bitvec.ushr Std.BitVec.ushiftRight
+#align bitvec.sshr Std.BitVec.sshiftRight
 
 /-! ### Bitwise operations -/
 
-
-section Bitwise
-
-variable {n : ℕ}
-
--- porting note: added protected, since now this clashes with `_root_.not` (formerly `bnot`)
-/-- bitwise not -/
-protected def not (bv : Bitvec n) : Bitvec n :=
-  map not bv
-#align bitvec.not Bitvec.not
-
--- porting note: added protected, since now this clashes with `_root_.and` (formerly `band`)
-/-- bitwise and -/
-protected def and : Bitvec n → Bitvec n → Bitvec n :=
-  map₂ and
-#align bitvec.and Bitvec.and
-
--- porting note: added protected, since now this clashes with `_root_.or` (formerly `bor`)
-/-- bitwise or -/
-protected def or : Bitvec n → Bitvec n → Bitvec n :=
-  map₂ or
-#align bitvec.or Bitvec.or
-
--- porting note: added protected, since now this clashes with `_root_.xor` (formerly `bxor`)
-/-- bitwise xor -/
-protected def xor : Bitvec n → Bitvec n → Bitvec n :=
-  map₂ xor
-#align bitvec.xor Bitvec.xor
-
-instance : Complement (Bitvec n) :=
-⟨Bitvec.not⟩
-
-instance : AndOp (Bitvec n) :=
-⟨Bitvec.and⟩
-
-instance : OrOp (Bitvec n) :=
-⟨Bitvec.or⟩
-
-instance : Xor (Bitvec n) :=
-⟨Bitvec.xor⟩
-
-end Bitwise
+#align bitvec.not Std.BitVec.not
+#align bitvec.and Std.BitVec.and
+#align bitvec.or Std.BitVec.or
+#align bitvec.xor Std.BitVec.xor
 
 /-! ### Arithmetic operators -/
 
-
-section Arith
-
-variable {n : ℕ}
-
-/-- `neg x` is the two's complement of `x`. -/
-protected def neg (x : Bitvec n) : Bitvec n :=
-  let f y c := (y || c, xor y c)
-  Prod.snd (mapAccumr f x false)
-#align bitvec.neg Bitvec.neg
-
+#align bitvec.neg Std.BitVec.neg
 /-- Add with carry (no overflow) -/
-def adc (x y : Bitvec n) (c : Bool) : Bitvec (n + 1) :=
-  let f x y c := (Bool.carry x y c, Bool.xor3 x y c)
-  let ⟨c, z⟩ := Vector.mapAccumr₂ f x y c
-  c ::ᵥ z
-#align bitvec.adc Bitvec.adc
+def adc {n} (x y : BitVec n) (c : Bool) : BitVec (n+1) :=
+  ofFin (x.toNat + y.toNat + c.toNat)
+#align bitvec.adc Std.BitVec.adc
 
-/-- The sum of two bitvectors -/
-protected def add (x y : Bitvec n) : Bitvec n :=
-  tail (adc x y false)
-#align bitvec.add Bitvec.add
+#align bitvec.add Std.BitVec.add
 
 /-- Subtract with borrow -/
-def sbb (x y : Bitvec n) (b : Bool) : Bool × Bitvec n :=
-  let f x y c := (Bool.carry (not x) y c, Bool.xor3 x y c)
-  Vector.mapAccumr₂ f x y b
-#align bitvec.sbb Bitvec.sbb
+def sbb {n} (x y : BitVec n) (b : Bool) : Bool × BitVec n :=
+  let y := y + ofFin b.toNat
+  (x < y, x - y)
+#align bitvec.sbb Std.BitVec.sbb
 
-/-- The difference of two bitvectors -/
-protected def sub (x y : Bitvec n) : Bitvec n :=
-  Prod.snd (sbb x y false)
-#align bitvec.sub Bitvec.sub
+#align bitvec.sub Std.BitVec.sub
+#align bitvec.mul Std.BitVec.mul
 
-instance : Zero (Bitvec n) :=
-  ⟨Bitvec.zero n⟩
-
-instance : One (Bitvec n) :=
-  ⟨Bitvec.one n⟩
+/-! ### Comparison operators -/
 
-instance : Add (Bitvec n) :=
-  ⟨Bitvec.add⟩
+#align bitvec.uborrow Std.BitVec.ult
+#align bitvec.ult Std.BitVec.ult
 
-instance : Sub (Bitvec n) :=
-  ⟨Bitvec.sub⟩
+/-- Unsigned greater than for bitvectors. -/
+protected def ugt (x y : BitVec w) : Bool := BitVec.ult y x
+#align bitvec.ugt Std.BitVec.ugt
 
-instance : Neg (Bitvec n) :=
-  ⟨Bitvec.neg⟩
+#align bitvec.ule Std.BitVec.ule
 
-/-- The product of two bitvectors -/
-protected def mul (x y : Bitvec n) : Bitvec n :=
-  let f r b := cond b (r + r + y) (r + r)
-  (toList x).foldl f 0
-#align bitvec.mul Bitvec.mul
+/-- Signed greater than or equal to for bitvectors. -/
+protected def uge (x y : BitVec w) : Bool := BitVec.ule y x
+#align bitvec.uge Std.BitVec.uge
 
-instance : Mul (Bitvec n) :=
-  ⟨Bitvec.mul⟩
+#align bitvec.sborrow Std.BitVec.slt
+#align bitvec.slt Std.BitVec.slt
 
-end Arith
+/-- Signed greater than for bitvectors. -/
+protected def sgt (x y : BitVec w) : Bool := BitVec.slt y x
+#align bitvec.sgt Std.BitVec.sgt
 
-/-! ### Comparison operators -/
+#align bitvec.sle Std.BitVec.sle
 
-
-section Comparison
-
-variable {n : ℕ}
-
-/-- `uborrow x y` returns `true` iff the "subtract with borrow" operation on `x`, `y` and `false`
-required a borrow. -/
-def uborrow (x y : Bitvec n) : Bool :=
-  Prod.fst (sbb x y false)
-#align bitvec.uborrow Bitvec.uborrow
-
-/-- unsigned less-than proposition -/
-def Ult (x y : Bitvec n) : Prop :=
-  uborrow x y
-#align bitvec.ult Bitvec.Ult
-
-/-- unsigned greater-than proposition -/
-def Ugt (x y : Bitvec n) : Prop :=
-  Ult y x
-#align bitvec.ugt Bitvec.Ugt
-
-/-- unsigned less-than-or-equal-to proposition -/
-def Ule (x y : Bitvec n) : Prop :=
-  ¬Ult y x
-#align bitvec.ule Bitvec.Ule
-
-/-- unsigned greater-than-or-equal-to proposition -/
-def Uge (x y : Bitvec n) : Prop :=
-  Ule y x
-#align bitvec.uge Bitvec.Uge
-
-/-- `sborrow x y` returns `true` iff `x < y` as two's complement integers -/
-def sborrow : ∀ {n : ℕ}, Bitvec n → Bitvec n → Bool
-  | 0, _, _ => false
-  | succ _, x, y =>
-    match (head x, head y) with
-    | (true, false) => true
-    | (false, true) => false
-    | _ => uborrow (tail x) (tail y)
-#align bitvec.sborrow Bitvec.sborrow
-
-/-- signed less-than proposition -/
-def Slt (x y : Bitvec n) : Prop :=
-  sborrow x y
-#align bitvec.slt Bitvec.Slt
-
-/-- signed greater-than proposition -/
-def Sgt (x y : Bitvec n) : Prop :=
-  Slt y x
-#align bitvec.sgt Bitvec.Sgt
-
-/-- signed less-than-or-equal-to proposition -/
-def Sle (x y : Bitvec n) : Prop :=
-  ¬Slt y x
-#align bitvec.sle Bitvec.Sle
-
-/-- signed greater-than-or-equal-to proposition -/
-def Sge (x y : Bitvec n) : Prop :=
-  Sle y x
-#align bitvec.sge Bitvec.Sge
-
-end Comparison
+/-- Signed greater than or equal to for bitvectors. -/
+protected def sge (x y : BitVec w) : Bool := BitVec.sle y x
+#align bitvec.sge Std.BitVec.sge
 
 /-! ### Conversion to `nat` and `int` -/
 
+#align bitvec.of_nat Std.BitVec.ofNat
 
-section Conversion
-
-variable {α : Type}
-
-/-- Create a bitvector from a `nat` -/
-protected def ofNat : ∀ n : ℕ, Nat → Bitvec n
-  | 0, _ => nil
-  | succ n, x => Bitvec.ofNat n (x / 2)++ₜdecide (x % 2 = 1) ::ᵥ nil
-#align bitvec.of_nat Bitvec.ofNat
-
-/-- Create a bitvector from an `Int`. The ring homomorphism from Int to bitvectors. -/
-protected def ofInt : ∀ n : ℕ, Int → Bitvec n
-  | n, Int.ofNat m => Bitvec.ofNat n m
-  | n, Int.negSucc m => (Bitvec.ofNat n m).not
-
-/-- `add_lsb r b` is `r + r + 1` if `b` is `true` and `r + r` otherwise. -/
+/-- `addLsb r b` is `r + r + 1` if `b` is `true` and `r + r` otherwise. -/
 def addLsb (r : ℕ) (b : Bool) :=
-  r + r + cond b 1 0
-#align bitvec.add_lsb Bitvec.addLsb
-
-/-- Given a `List` of `Bool`s, return the `nat` they represent as a list of binary digits. -/
-def bitsToNat (v : List Bool) : Nat :=
-  v.foldl addLsb 0
-#align bitvec.bits_to_nat Bitvec.bitsToNat
+  Nat.bit b r
+#align bitvec.add_lsb Std.BitVec.addLsb
 
-/-- Return the natural number encoded by the input bitvector -/
-protected def toNat {n : Nat} (v : Bitvec n) : Nat :=
-  bitsToNat (toList v)
-#align bitvec.to_nat Bitvec.toNat
+#noalign bitvec.bits_to_nat
+#align bitvec.to_nat Std.BitVec.toNat
+#align bitvec.of_fin Std.BitVec.ofFin
+#align bitvec.to_fin Std.BitVec.toFin
+#align bitvec.to_int Std.BitVec.toInt
 
-instance (n : ℕ) : Preorder (Bitvec n) :=
-  Preorder.lift Bitvec.toNat
 
-/-- convert `fin` to `Bitvec` -/
-def ofFin {n : ℕ} (i : Fin <| 2 ^ n) : Bitvec n :=
-  Bitvec.ofNat _ i.val
-#align bitvec.of_fin Bitvec.ofFin
+/-- Return the `i`-th least significant bit, where `i` is a statically known in-bounds index -/
+def getLsb' (x : BitVec w) (i : Fin w) := x.getLsb i
 
-/-- convert `Bitvec` to `fin` -/
-def toFin {n : ℕ} (i : Bitvec n) : Fin (2 ^ n) :=
-  i.toNat
-#align bitvec.to_fin Bitvec.toFin
+/-- Return the `i`-th most significant bit, where `i` is a statically known in-bounds index -/
+def getMsb' (x : BitVec w) (i : Fin w) := x.getMsb i
 
+/--
+  Convert a bitvector to a little-endian list of Booleans.
+  That is, the head of the list is the least significant bit
+-/
+def toLEList (x : BitVec w) : List Bool :=
+  List.ofFn x.getLsb'
 
-/-- Return the integer encoded by the input bitvector -/
-protected def toInt : ∀ {n : Nat}, Bitvec n → Int
-  | 0, _ => 0
-  | succ _, v =>
-    cond (head v) (Int.negSucc <| Bitvec.toNat <| Bitvec.not <| tail v)
-      (Int.ofNat <| Bitvec.toNat <| tail v)
-#align bitvec.to_int Bitvec.toInt
-
-end Conversion
-
-/-! ### Miscellaneous instances -/
-
-
-private def repr {n : Nat} : Bitvec n → String
-  | ⟨bs, _⟩ => "0b" ++ (bs.map fun b : Bool => if b then '1' else '0').asString
-
-instance (n : Nat) : Repr (Bitvec n) where
-  reprPrec (b : Bitvec n) _ := Std.Format.text (repr b)
-
-end Bitvec
-
-instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ult x y) :=
-  decEq _ _
-
-instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ugt x y) :=
-  decEq _ _
-
-instance {n} : HShiftLeft (Bitvec n) Nat (Bitvec n) := ⟨Bitvec.shl⟩
-
-instance {n} : HShiftRight (Bitvec n) Nat (Bitvec n) := ⟨Bitvec.ushr⟩
-
-instance {n} : ShiftLeft (Bitvec n) := ⟨fun x y => x <<< y.toNat⟩
+/--
+  Convert a bitvector to a big-endian list of Booleans.
+  That is, the head of the list is the most significant bit
+-/
+def toBEList (x : BitVec w) : List Bool :=
+  List.ofFn x.getMsb'
 
-instance {n} : ShiftRight (Bitvec n) := ⟨fun x y => x >>> y.toNat⟩
+end Std.BitVec

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -47,8 +47,8 @@ protected def one : ∀ n : ℕ, Bitvec n
 #align bitvec.one Bitvec.one
 
 /-- Create a bitvector from another with a provably equal length. -/
-protected def cong {a b : ℕ} (h : a = b) : Bitvec a → Bitvec b
-  | ⟨x, p⟩ => ⟨x, h ▸ p⟩
+protected def cong {a b : ℕ} : a = b → Bitvec a → Bitvec b :=
+  Vector.congr
 #align bitvec.cong Bitvec.cong
 
 /-- `Bitvec` specific version of `Vector.append` -/
@@ -66,33 +66,20 @@ variable {n : ℕ}
 /-- `shl x i` is the bitvector obtained by left-shifting `x` `i` times and padding with `false`.
 If `x.length < i` then this will return the all-`false`s bitvector. -/
 def shl (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  Bitvec.cong (by simp) <| drop i x++ₜreplicate (min n i) false
+  shiftLeftFill x i false
 #align bitvec.shl Bitvec.shl
 
-/-- `fill_shr x i fill` is the bitvector obtained by right-shifting `x` `i` times and then
-padding with `fill : Bool`. If `x.length < i` then this will return the constant `fill`
-bitvector. -/
-def fillShr (x : Bitvec n) (i : ℕ) (fill : Bool) : Bitvec n :=
-  Bitvec.cong
-      (by
-        by_cases h : i ≤ n
-        · have h₁ := Nat.sub_le n i
-          rw [min_eq_right h]
-          rw [min_eq_left h₁, ← add_tsub_assoc_of_le h, Nat.add_comm, add_tsub_cancel_right]
-        · have h₁ := le_of_not_ge h
-          rw [min_eq_left h₁, tsub_eq_zero_iff_le.mpr h₁, zero_min, Nat.add_zero]) <|
-    replicate (min n i) fill++ₜtake (n - i) x
-#align bitvec.fill_shr Bitvec.fillShr
+#noalign bitvec.fill_shr
 
 /-- unsigned shift right -/
 def ushr (x : Bitvec n) (i : ℕ) : Bitvec n :=
-  fillShr x i false
+  shiftRightFill x i false
 #align bitvec.ushr Bitvec.ushr
 
 /-- signed shift right -/
 def sshr : ∀ {m : ℕ}, Bitvec m → ℕ → Bitvec m
   | 0, _, _ => nil
-  | succ _, x, i => head x ::ᵥ fillShr (tail x) i (head x)
+  | succ _, x, i => head x ::ᵥ shiftRightFill (tail x) i (head x)
 #align bitvec.sshr Bitvec.sshr
 
 end Shift

• depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,16 +2,13 @@
 Copyright (c) 2015 Joe Hendrix. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Joe Hendrix, Sebastian Ullrich
-
-! This file was ported from Lean 3 source module data.bitvec.core
-! leanprover-community/mathlib commit 1126441d6bccf98c81214a0780c73d499f6721fe
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Vector.Basic
 import Mathlib.Data.Nat.Pow
 import Init.Data.Format.Basic
 import Mathlib.Init.Data.Nat.Lemmas
+
+#align_import data.bitvec.core from "leanprover-community/mathlib"@"1126441d6bccf98c81214a0780c73d499f6721fe"
 /-!
 # Basic operations on bitvectors
 

This eliminates an unnecessary dependency from Num.Bitwise to Bitvec.Defs.

@@ -152,16 +152,6 @@ section Arith
 
 variable {n : ℕ}
 
-/-- `xor3 x y c` is `((x XOR y) XOR c)`. -/
-protected def xor3 (x y c : Bool) :=
-  xor (xor x y) c
-#align bitvec.xor3 Bitvec.xor3
-
-/-- `carry x y c` is `x && y || x && c || y && c`. -/
-protected def carry (x y c : Bool) :=
-  x && y || x && c || y && c
-#align bitvec.carry Bitvec.carry
-
 /-- `neg x` is the two's complement of `x`. -/
 protected def neg (x : Bitvec n) : Bitvec n :=
   let f y c := (y || c, xor y c)
@@ -170,7 +160,7 @@ protected def neg (x : Bitvec n) : Bitvec n :=
 
 /-- Add with carry (no overflow) -/
 def adc (x y : Bitvec n) (c : Bool) : Bitvec (n + 1) :=
-  let f x y c := (Bitvec.carry x y c, Bitvec.xor3 x y c)
+  let f x y c := (Bool.carry x y c, Bool.xor3 x y c)
   let ⟨c, z⟩ := Vector.mapAccumr₂ f x y c
   c ::ᵥ z
 #align bitvec.adc Bitvec.adc
@@ -182,7 +172,7 @@ protected def add (x y : Bitvec n) : Bitvec n :=
 
 /-- Subtract with borrow -/
 def sbb (x y : Bitvec n) (b : Bool) : Bool × Bitvec n :=
-  let f x y c := (Bitvec.carry (not x) y c, Bitvec.xor3 x y c)
+  let f x y c := (Bool.carry (not x) y c, Bool.xor3 x y c)
   Vector.mapAccumr₂ f x y b
 #align bitvec.sbb Bitvec.sbb
 

Add shl/shr instances for Bitvec

@@ -355,3 +355,11 @@ instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ult x y) :=
 
 instance {n} {x y : Bitvec n} : Decidable (Bitvec.Ugt x y) :=
   decEq _ _
+
+instance {n} : HShiftLeft (Bitvec n) Nat (Bitvec n) := ⟨Bitvec.shl⟩
+
+instance {n} : HShiftRight (Bitvec n) Nat (Bitvec n) := ⟨Bitvec.ushr⟩
+
+instance {n} : ShiftLeft (Bitvec n) := ⟨fun x y => x <<< y.toNat⟩
+
+instance {n} : ShiftRight (Bitvec n) := ⟨fun x y => x >>> y.toNat⟩

@@ -131,6 +131,18 @@ protected def xor : Bitvec n → Bitvec n → Bitvec n :=
   map₂ xor
 #align bitvec.xor Bitvec.xor
 
+instance : Complement (Bitvec n) :=
+⟨Bitvec.not⟩
+
+instance : AndOp (Bitvec n) :=
+⟨Bitvec.and⟩
+
+instance : OrOp (Bitvec n) :=
+⟨Bitvec.or⟩
+
+instance : Xor (Bitvec n) :=
+⟨Bitvec.xor⟩
+
 end Bitwise
 
 /-! ### Arithmetic operators -/

The Core file was just dumped from Lean3 core. I've split it into Defs and Lemmas in the style of the List folder for example.

@@ -303,57 +303,19 @@ protected def toNat {n : Nat} (v : Bitvec n) : Nat :=
   bitsToNat (toList v)
 #align bitvec.to_nat Bitvec.toNat
 
-theorem bitsToNat_toList {n : ℕ} (x : Bitvec n) : Bitvec.toNat x = bitsToNat (Vector.toList x) :=
-  rfl
-#align bitvec.bits_to_nat_to_list Bitvec.bitsToNat_toList
-
-attribute [local simp] Nat.add_comm Nat.add_assoc Nat.add_left_comm Nat.mul_comm Nat.mul_assoc
-
-attribute [local simp] Nat.zero_add Nat.add_zero Nat.one_mul Nat.mul_one Nat.zero_mul Nat.mul_zero
-
--- mul_left_comm
-theorem toNat_append {m : ℕ} (xs : Bitvec m) (b : Bool) :
-    Bitvec.toNat (xs++ₜb ::ᵥ nil) = Bitvec.toNat xs * 2 + Bitvec.toNat (b ::ᵥ nil) := by
-  cases' xs with xs P
-  simp [bitsToNat_toList]; clear P
-  unfold bitsToNat
-  -- porting note: was `unfold List.foldl`, which now unfolds to an ugly match
-  rw [List.foldl, List.foldl]
-  -- generalize the accumulator of foldl
-  generalize h : 0 = x
-  conv in addLsb x b =>
-    rw [← h]
-  clear h
-  simp
-  induction' xs with x xs xs_ih generalizing x
-  · simp
-    unfold addLsb
-    simp [Nat.mul_succ]
-  · simp
-    apply xs_ih
-#align bitvec.to_nat_append Bitvec.toNat_append
-
--- Porting Note: the mathlib3port version of the proof was :
---  simp [bits_to_nat_to_list]
---  unfold bits_to_nat add_lsb List.foldl cond
---  simp [cond_to_bool_mod_two]
-theorem bits_toNat_decide (n : ℕ) : Bitvec.toNat (decide (n % 2 = 1) ::ᵥ nil) = n % 2 := by
-  simp [bitsToNat_toList]
-  unfold bitsToNat addLsb List.foldl
-  simp [Nat.cond_decide_mod_two, -Bool.cond_decide]
-#align bitvec.bits_to_nat_to_bool Bitvec.bits_toNat_decide
-
-theorem ofNat_succ {k n : ℕ} :
-    Bitvec.ofNat (succ k) n = Bitvec.ofNat k (n / 2)++ₜdecide (n % 2 = 1) ::ᵥ nil :=
-  rfl
-#align bitvec.of_nat_succ Bitvec.ofNat_succ
-
-theorem toNat_ofNat {k n : ℕ} : Bitvec.toNat (Bitvec.ofNat k n) = n % 2 ^ k := by
-  induction' k with k ih generalizing n
-  · simp [Nat.mod_one]
-    rfl
-  · rw [ofNat_succ, toNat_append, ih, bits_toNat_decide, mod_pow_succ, Nat.mul_comm]
-#align bitvec.to_nat_of_nat Bitvec.toNat_ofNat
+instance (n : ℕ) : Preorder (Bitvec n) :=
+  Preorder.lift Bitvec.toNat
+
+/-- convert `fin` to `Bitvec` -/
+def ofFin {n : ℕ} (i : Fin <| 2 ^ n) : Bitvec n :=
+  Bitvec.ofNat _ i.val
+#align bitvec.of_fin Bitvec.ofFin
+
+/-- convert `Bitvec` to `fin` -/
+def toFin {n : ℕ} (i : Bitvec n) : Fin (2 ^ n) :=
+  i.toNat
+#align bitvec.to_fin Bitvec.toFin
+
 
 /-- Return the integer encoded by the input bitvector -/
 protected def toInt : ∀ {n : Nat}, Bitvec n → Int

Co-authored-by: Chris Hughes <33847686+ChrisHughes24@users.noreply.github.com>

@@ -283,11 +283,10 @@ protected def ofNat : ∀ n : ℕ, Nat → Bitvec n
   | succ n, x => Bitvec.ofNat n (x / 2)++ₜdecide (x % 2 = 1) ::ᵥ nil
 #align bitvec.of_nat Bitvec.ofNat
 
-/-- Create a bitvector in the two's complement representation from an `int` -/
-protected def ofInt : ∀ n : ℕ, Int → Bitvec (succ n)
-  | n, Int.ofNat m => false ::ᵥ Bitvec.ofNat n m
-  | n, Int.negSucc m => true ::ᵥ (Bitvec.ofNat n m).not
-#align bitvec.of_int Bitvec.ofInt
+/-- Create a bitvector from an `Int`. The ring homomorphism from Int to bitvectors. -/
+protected def ofInt : ∀ n : ℕ, Int → Bitvec n
+  | n, Int.ofNat m => Bitvec.ofNat n m
+  | n, Int.negSucc m => (Bitvec.ofNat n m).not
 
 /-- `add_lsb r b` is `r + r + 1` if `b` is `true` and `r + r` otherwise. -/
 def addLsb (r : ℕ) (b : Bool) :=

@@ -78,7 +78,7 @@ bitvector. -/
 def fillShr (x : Bitvec n) (i : ℕ) (fill : Bool) : Bitvec n :=
   Bitvec.cong
       (by
-        by_cases i ≤ n
+        by_cases h : i ≤ n
         · have h₁ := Nat.sub_le n i
           rw [min_eq_right h]
           rw [min_eq_left h₁, ← add_tsub_assoc_of_le h, Nat.add_comm, add_tsub_cancel_right]

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Johan Commelin <johan@commelin.net>