library colibrilib.bv_sem — module SmtlibThe definitions of the theory FixedSizeBitVectors (SMT–LIB 2.7, Theories/FixedSizeBitVectors.smt2, last updated 2025–09–09) and the abbreviations of the logic QF_BV (Logics/QF_BV.smt2), as written there (trusted). A bit–vector b: [0, m) → {0, 1} is the integer 0 <= v < 2^m whose bit x is b(x) (b(x) = 1 is bittest v x): λx:[0, m). f(x) is Zbit.of_bits f m, bv2nat(b) is v.
module Smtlib408use int.Int409use int.Power410use int.EuclideanDivision as E411use colibrilib.zarith.Zbit412
λx:[0, m). f(x)
function lam (m:int) (f:int -> bool) : int = Zbit.of_bits f m415
b(x) = 1
predicate bit (b x:int) = Zbit.bittest b x418419function bv2nat (b:int) : int = b420421function bv2int (m b:int) : int = if not (bit b (m - 1)) then bv2nat b else bv2nat b - power 2 m422423function nat2bv (m n:int) : int = E.mod n (power 2 m)424
s of size n, t of size m
function concat (n m s t:int) : int =429lam (n + m) (fun x -> if x < m then bit t x else bit s (x - m))430431function extract (i j s:int) : int = lam (i - j + 1) (fun x -> bit s (j + x))432433function bvnot (m s:int) : int = lam m (fun x -> not (bit s x))434435function bvand (m s t:int) : int = lam m (fun x -> if not (bit s x) then false else bit t x)436437function bvor (m s t:int) : int = lam m (fun x -> if bit s x then true else bit t x)438439function bvneg (m s:int) : int = nat2bv m (power 2 m - bv2nat s)440441function bvadd (m s t:int) : int = nat2bv m (bv2nat s + bv2nat t)442443function bvmul (m s t:int) : int = nat2bv m (bv2nat s * bv2nat t)444445function bvudiv (m s t:int) : int =446if bv2nat t = 0 then lam m (fun _ -> true) else nat2bv m (E.div (bv2nat s) (bv2nat t))447448function bvurem (m s t:int) : int =449if bv2nat t = 0 then s else nat2bv m (E.mod (bv2nat s) (bv2nat t))450451function bvshl (m s t:int) : int = nat2bv m (bv2nat s * power 2 (bv2nat t))452453function bvlshr (m s t:int) : int = nat2bv m (E.div (bv2nat s) (power 2 (bv2nat t)))454455predicate bvult (s t:int) = bv2nat s < bv2nat t456457function ubv_to_int (s:int) : int = bv2nat s458459function sbv_to_int (m s:int) : int = bv2int m s460461function int_to_bv (n x:int) : int = nat2bv n (E.mod x (power 2 n))462
function bvnand (m s t:int) : int = bvnot m (bvand m s t)466467function bvnor (m s t:int) : int = bvnot m (bvor m s t)468469function bvxor (m s t:int) : int = bvor m (bvand m s (bvnot m t)) (bvand m (bvnot m s) t)470471function bvxnor (m s t:int) : int = bvor m (bvand m s t) (bvand m (bvnot m s) (bvnot m t))472Valid (27ms) (colibri2)473let rec ghost function bvcomp (m s t:int) : int474variant { m }475= if m <= 1 then bvxnor m s t476else bvand 1 (bvxnor 1 (extract (m - 1) (m - 1) s) (extract (m - 1) (m - 1) t))477(bvcomp (m - 1) (extract (m - 2) 0 s) (extract (m - 2) 0 t))478479function bvsub (m s t:int) : int = bvadd m s (bvneg m t)480
((_ extract |m-1| |m-1|) s)
function msb (m s:int) : int = extract (m - 1) (m - 1) s483484function bvsdiv (m s t:int) : int =485let msb_s = msb m s in486let msb_t = msb m t in487if msb_s = 0 /\ msb_t = 0 then bvudiv m s t488else if msb_s = 1 /\ msb_t = 0 then bvneg m (bvudiv m (bvneg m s) t)489else if msb_s = 0 /\ msb_t = 1 then bvneg m (bvudiv m s (bvneg m t))490else bvudiv m (bvneg m s) (bvneg m t)491492function bvsrem (m s t:int) : int =493let msb_s = msb m s in494let msb_t = msb m t in495if msb_s = 0 /\ msb_t = 0 then bvurem m s t496else if msb_s = 1 /\ msb_t = 0 then bvneg m (bvurem m (bvneg m s) t)497else if msb_s = 0 /\ msb_t = 1 then bvurem m s (bvneg m t)498else bvneg m (bvurem m (bvneg m s) (bvneg m t))499500function bvsmod (m s t:int) : int =501let msb_s = msb m s in502let msb_t = msb m t in503let abs_s = if msb_s = 0 then s else bvneg m s in504let abs_t = if msb_t = 0 then t else bvneg m t in505let u = bvurem m abs_s abs_t in506if u = 0 then u507else if msb_s = 0 /\ msb_t = 0 then u508else if msb_s = 1 /\ msb_t = 0 then bvadd m (bvneg m u) t509else if msb_s = 0 /\ msb_t = 1 then bvadd m u t510else bvneg m u511512predicate bvule (s t:int) = bvult s t \/ s = t513514predicate bvugt (s t:int) = bvult t s515516predicate bvuge (s t:int) = bvult t s \/ s = t517518predicate bvslt (m s t:int) =519(msb m s = 1 /\ msb m t = 0) \/ (msb m s = msb m t /\ bvult s t)520521predicate bvsle (m s t:int) =522(msb m s = 1 /\ msb m t = 0) \/ (msb m s = msb m t /\ bvule s t)523524predicate bvsgt (m s t:int) = bvslt m t s525526predicate bvsge (m s t:int) = bvsle m t s527528function bvashr (m s t:int) : int =529if msb m s = 0 then bvlshr m s t else bvnot m (bvlshr m (bvnot m s) t)530
((_ repeat j) t), t of size m
Valid (30ms) (colibri2)let rec ghost function repeat (j m t:int) : int533variant { j }534= if j <= 1 then t else concat m (m * (j - 1)) t (repeat (j - 1) m t)535536function zero_extend (i m t:int) : int =537if i = 0 then t else concat i m (repeat i 1 0) t538539function sign_extend (i m t:int) : int =540if i = 0 then t else concat i m (repeat i 1 (extract (m - 1) (m - 1) t)) t541Valid (32ms) (colibri2)542let rec ghost function rotate_left (i m t:int) : int543variant { i }544= if i <= 0 then t545else if m = 1 then t546else rotate_left (i - 1) m (concat (m - 1) 1 (extract (m - 2) 0 t) (extract (m - 1) (m - 1) t))547Valid (29ms) (colibri2)548let rec ghost function rotate_right (i m t:int) : int549variant { i }550= if i <= 0 then t551else if m = 1 then t552else rotate_right (i - 1) m (concat 1 (m - 1) (extract 0 0 t) (extract (m - 1) 1 t))553end554