library colibrilib.bv_sem — module Agreemodule Agree557use int.Int558use int.Power559use int.EuclideanDivision as E560use int.ComputerDivision as C561use list.List562use colibrilib.zarith.Zbit563use colibrilib.safe_bits.SafeBits as SB564use colibrilib.known_bits.Range565use Sem566use Smtlib567
2^n
Valid (45ms) (colibri2)let ghost pow_lsl (n:int) : unit572requires { 0 <= n }573ensures { power 2 n = Zbit.lsl 1 n }574= Zbit.lsl_mul 1 n575Valid (43ms) (colibri2)576let ghost pow_pos (n:int) : unit577requires { 0 <= n }578ensures { 0 < power 2 n }579= ()580
The bits of ext n y
Valid (55ms) (colibri2)let ghost ext_bits (n y:int) : unit583ensures { forall i. 0 <= i -> (Zbit.bittest (ext n y) i <-> i < n /\ Zbit.bittest y i) }584= {proof…} Zbit.asr_eq y;585if n > 0 then begin586let lemma bit (i:int) : unit587requires { 0 <= i }588ensures { Zbit.bittest (ext n y) i <-> i < n /\ Zbit.bittest y i }589= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in ()590end {qed}591
A non–negative integer without bits from m is below 2^m
Valid (71ms) (colibri2)let ghost bits_lt (m v:int) : unit594requires { 0 <= m /\ 0 <= v }595requires { forall i. m <= i -> not (Zbit.bittest v i) }596ensures { v < Zbit.lsl 1 m }597= {proof…} if v > 0 then begin598Zbit.numbits_top_bit v;599Zbit.numbits_lsl_lt v;600let k = Zbit.numbits v in601assert { k <= m };602pow_lsl k; pow_lsl m;603assert { power 2 k <= power 2 m by power 2 m = power 2 k * power 2 (m - k) }604end else begin605pow_lsl m606end {qed}607
in_range from the bits
Valid (56ms) (colibri2)let ghost in_range_bits (m v:int) : unit610requires { 0 <= m /\ 0 <= v }611requires { forall i. m <= i -> not (Zbit.bittest v i) }612ensures { in_range m v }613= bits_lt m v614
lam m f is a bit–vector of size m
Valid (349ms) (colibri2)let ghost lam_range (m:int) (f:int -> bool) : unit617requires { 0 <= m }618ensures { in_range m (lam m f) }619= in_range_bits m (lam m f)620
ext n y is a bit–vector of size n
Valid (134ms) (cvc4)let ghost ext_range (n y:int) : unit623requires { 0 <= n }624ensures { in_range n (ext n y) }625= {proof…} ext_bits n y;626if n > 0 then begin627Zbit.mask_nonneg n; Zbit.land_nonneg_l (Zbit.mask n) (Zbit.asr y 0);628Zbit.ext_bittest (ext n y) (Zbit.land (Zbit.mask n) (Zbit.asr y 0))629end;630in_range_bits n (ext n y) {qed}631
The bits from n of a bit–vector of size n are zero
Valid (41ms) (colibri2)let ghost range_high (n x:int) : unit634requires { in_range n x }635ensures { 0 <= n }636ensures { forall i. n <= i -> not (Zbit.bittest x i) }637= {proof…} Zbit.numbits_lt_lsl x n; Zbit.numbits_ge_pos 0 x; Sem.high_zero x n {qed}638
Equal bits
Valid (44ms) (colibri2)let ghost same_bits (n x y:int) : unit641requires { in_range n x /\ in_range n y }642requires { forall i. 0 <= i < n -> (Zbit.bittest x i <-> Zbit.bittest y i) }643ensures { x = y }644= {proof…} range_high n x; range_high n y;645let lemma bit (i:int) : unit646requires { 0 <= i }647ensures { Zbit.bittest x i <-> Zbit.bittest y i }648= () in649Zbit.ext_bittest x y {qed}650
bv n x of a bit–vector of size n
Valid (64ms) (colibri2)let ghost bv_id (n x:int) : unit653requires { in_range n x }654ensures { bv n x = x }655= {proof…} range_high n x;656let lemma bit (i:int) : unit657requires { 0 <= i }658ensures { Zbit.bittest (bv n x) i <-> Zbit.bittest x i }659= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in660Zbit.ext_bittest (bv n x) x {qed}661
ext n y is y mod 2^n
Valid (364ms) (colibri2 10) (split_vc) (depth 1)let ghost ext_mod (n y:int) : unit664requires { 0 <= n }665ensures { ext n y = E.mod y (power 2 n) }666= {proof…} pow_lsl n;667split y n;668let r = Zbit.land (Zbit.mask n) y in669ext_bits n y;670let lemma bit (i:int) : unit671requires { 0 <= i }672ensures { Zbit.bittest (ext n y) i <-> Zbit.bittest r i }673= if i >= n then Zbit.mask_bits_high n i in674Zbit.ext_bittest (ext n y) r;675let q = Zbit.asr y n in676assert { y = q * power 2 n + r };677assert { E.div y (power 2 n) = q678by q * power 2 n <= y < q * power 2 n + power 2 n };679assert { E.mod y (power 2 n) = r } {qed}680
nat2bv is ext
Valid (48ms) (colibri2)let ghost nat2bv_ext (m n:int) : unit683requires { 0 <= m }684ensures { nat2bv m n = ext m n }685= ext_mod m n686
A bit–vector is its own ext
Valid (58ms) (colibri2)let ghost ext_id (n x:int) : unit689requires { in_range n x }690ensures { ext n x = x }691= {proof…} range_high n x; ext_range n x; ext_bits n x;692same_bits n (ext n x) x {qed}693
lam 1 f
Valid (51ms) (colibri2)let ghost lam1 (f:int -> bool) : unit696ensures { lam 1 f = if f 0 then 1 else 0 }697= {proof…} lam_range 1 f;698pow_lsl 1;699assert { Zbit.bittest 1 0 };700if f 0 then same_bits 1 (lam 1 f) 1701else same_bits 1 (lam 1 f) 0 {qed}702
A bit of s as a bit–vector of size 1
Valid (340ms) (colibri2 14) (split_vc 3) (depth 2)let ghost extract1 (j s:int) : unit705ensures { extract j j s = if Zbit.bittest s j then 1 else 0 }706= {proof…} let e = extract j j s in707assert { forall i. 0 <= i -> (Zbit.bittest e i <-> i < 1 /\ Zbit.bittest s (j + i)) };708assert { Zbit.bittest e 0 <-> Zbit.bittest s j };709in_range_bits 1 e;710pow_lsl 1;711assert { power 2 1 = 2 };712assert { Zbit.bittest 1 0 };713assert { forall i. 0 < i -> not (Zbit.bittest 1 i) };714if Zbit.bittest s j then same_bits 1 e 1 else same_bits 1 e 0 {qed}715
The most significant bit
Valid (40ms) (colibri2)let ghost msb_val (m s:int) : unit718ensures { msb m s = if Zbit.bittest s (m - 1) then 1 else 0 }719= extract1 (m - 1) s720
bv2int: a bit–vector of size n as a signed integer
Valid (118ms) (cvc4)let ghost signed_val (n x:int) : unit723requires { 1 <= n /\ in_range n x }724ensures { signed n x = bv2int n x }725= {proof…} bv_id n x;726range_high n x;727Zbit.asr_eq x;728ext_id n x;729assert { z_extract x 0 n = x };730pow_lsl n;731if Zbit.bittest x (n - 1) then begin732let w = Zbit.lor x (Zbit.lnot (Zbit.mask n)) in733let lemma bit (i:int) : unit734requires { 0 <= i }735ensures { Zbit.bittest w i <-> Zbit.bittest (x - Zbit.lsl 1 n) i }736= if i < n then (Zbit.mask_bits n i; Zbit.bittest_sub_lsl x n i)737else (Zbit.mask_bits_high n i; Zbit.bittest_sub_lsl_high x n i) in738Zbit.ext_bittest w (x - Zbit.lsl 1 n)739end {qed}740
E.mod of a sum
Valid (44ms) (colibri2 5) (split_vc) (depth 1)let ghost mod_add (x y p:int) : unit743requires { 0 < p }744ensures { E.mod (x + E.mod y p) p = E.mod (x + y) p }745= {proof…} let q = E.div y p in746assert { y = p * q + E.mod y p };747assert { x + y = p * q + (x + E.mod y p) };748assert { E.mod (p * q + (x + E.mod y p)) p = E.mod (x + E.mod y p) p } {qed}749
The non–negative divisions
Valid (87ms) (colibri2)let ghost cdiv_pos (a b:int) : unit752requires { 0 <= a /\ 0 < b }753ensures { C.div a b = E.div a b /\ C.mod a b = E.mod a b }754= {proof…} assert { 0 <= C.mod a b < b };755assert { a = C.div a b * b + C.mod a b };756assert { E.div a b = C.div a b by C.div a b * b <= a < C.div a b * b + b } {qed}757
Valid (812ms) (cvc5)let ghost op_not (n x:int) : unit761requires { 1 <= n /\ in_range n x }762ensures { code (BvNot n) (Cons x Nil) = bvnot n x }763= {proof…} bv_id n x; ext_bits n (Zbit.lnot x); ext_range n (Zbit.lnot x);764in_range_bits n (bvnot n x);765same_bits n (ext n (Zbit.lnot x)) (bvnot n x) {qed}766Valid (955ms) (cvc5)767let ghost op_and (n x y:int) : unit768requires { 1 <= n /\ in_range n x /\ in_range n y }769ensures { code (BvAnd n) (Cons x (Cons y Nil)) = bvand n x y }770= {proof…} bv_id n x; bv_id n y; range_high n x; range_high n y;771in_range_bits n (Zbit.land x y);772in_range_bits n (bvand n x y);773same_bits n (Zbit.land x y) (bvand n x y) {qed}774Valid (88ms) (colibri2 11) (split_vc) (depth 1)775let ghost op_or (n x y:int) : unit776requires { 1 <= n /\ in_range n x /\ in_range n y }777ensures { code (BvOr n) (Cons x (Cons y Nil)) = bvor n x y }778= {proof…} bv_id n x; bv_id n y; range_high n x; range_high n y;779in_range_bits n (Zbit.lor x y);780in_range_bits n (bvor n x y);781same_bits n (Zbit.lor x y) (bvor n x y) {qed}782Valid (530ms) (colibri2 11) (cvc4) (cvc5) (split_vc) (depth 1)783let ghost op_xor (n x y:int) : unit784requires { 1 <= n /\ in_range n x /\ in_range n y }785ensures { code (BvXor n) (Cons x (Cons y Nil)) = bvxor n x y }786= {proof…} bv_id n x; bv_id n y;787let c = ext n (Zbit.lxor x y) in788ext_bits n (Zbit.lxor x y); ext_range n (Zbit.lxor x y);789in_range_bits n (bvxor n x y);790let lemma bit (i:int) : unit791requires { 0 <= i < n }792ensures { Zbit.bittest c i <-> Zbit.bittest (bvxor n x y) i }793= assert { Zbit.bittest (bvnot n y) i <-> not (Zbit.bittest y i) };794assert { Zbit.bittest (bvnot n x) i <-> not (Zbit.bittest x i) };795assert { Zbit.bittest (bvand n x (bvnot n y)) i <-> Zbit.bittest x i /\ not (Zbit.bittest y i) };796assert { Zbit.bittest (bvand n (bvnot n x) y) i <-> not (Zbit.bittest x i) /\ Zbit.bittest y i } in797same_bits n c (bvxor n x y) {qed}798Valid (827ms) (colibri2 7) (cvc5) (split_vc) (depth 1)799let ghost op_nand (n x y:int) : unit800requires { 1 <= n /\ in_range n x /\ in_range n y }801ensures { code (BvNand n) (Cons x (Cons y Nil)) = bvnand n x y }802= {proof…} bv_id n x; bv_id n y;803let c = ext n (Zbit.lnot (Zbit.land x y)) in804ext_bits n (Zbit.lnot (Zbit.land x y)); ext_range n (Zbit.lnot (Zbit.land x y));805in_range_bits n (bvnand n x y);806same_bits n c (bvnand n x y) {qed}807Valid (1.1s) (colibri2 7) (cvc5) (split_vc) (depth 1)808let ghost op_nor (n x y:int) : unit809requires { 1 <= n /\ in_range n x /\ in_range n y }810ensures { code (BvNor n) (Cons x (Cons y Nil)) = bvnor n x y }811= {proof…} bv_id n x; bv_id n y;812let c = ext n (Zbit.lnot (Zbit.lor x y)) in813ext_bits n (Zbit.lnot (Zbit.lor x y)); ext_range n (Zbit.lnot (Zbit.lor x y));814in_range_bits n (bvnor n x y);815same_bits n c (bvnor n x y) {qed}816Valid (1.0s) (colibri2 11) (cvc4) (cvc5) (split_vc) (depth 1)817let ghost op_xnor (n x y:int) : unit818requires { 1 <= n /\ in_range n x /\ in_range n y }819ensures { code (BvXnor n) (Cons x (Cons y Nil)) = bvxnor n x y }820= {proof…} bv_id n x; bv_id n y;821let c = ext n (Zbit.lxor x (Zbit.lnot y)) in822ext_bits n (Zbit.lxor x (Zbit.lnot y)); ext_range n (Zbit.lxor x (Zbit.lnot y));823in_range_bits n (bvxnor n x y);824let lemma bit (i:int) : unit825requires { 0 <= i < n }826ensures { Zbit.bittest c i <-> Zbit.bittest (bvxnor n x y) i }827= assert { Zbit.bittest (bvnot n y) i <-> not (Zbit.bittest y i) };828assert { Zbit.bittest (bvnot n x) i <-> not (Zbit.bittest x i) };829assert { Zbit.bittest (bvand n x y) i <-> Zbit.bittest x i /\ Zbit.bittest y i };830assert { Zbit.bittest (bvand n (bvnot n x) (bvnot n y)) i <->831not (Zbit.bittest x i) /\ not (Zbit.bittest y i) } in832same_bits n c (bvxnor n x y) {qed}833Valid (389ms) (colibri2 15) (cvc4) (split_vc) (depth 1)834let ghost op_concat (n m x y:int) : unit835requires { 1 <= n /\ 1 <= m /\ in_range n x /\ in_range m y }836ensures { code (BvConcat n m) (Cons x (Cons y Nil)) = concat n m x y }837= {proof…} bv_id n x; bv_id m y; range_high n x; range_high m y;838let c = Zbit.lor (Zbit.lsl x m) y in839let lemma bit (i:int) : unit840requires { 0 <= i }841ensures { Zbit.bittest c i <-> (i < n + m /\ if i < m then Zbit.bittest y i else Zbit.bittest x (i - m)) }842= Zbit.def_asr x (- m) i;843if i - m < 0 then Zbit.bittest_neg x (i - m) in844Zbit.lsl_mul x m;845assert { 0 <= c };846in_range_bits (n + m) c;847in_range_bits (n + m) (concat n m x y);848same_bits (n + m) c (concat n m x y) {qed}849Valid (400ms) (colibri2 18) (split_vc) (depth 1)850let ghost op_extract (n lo hi x:int) : unit851requires { 0 <= lo <= hi < n /\ in_range n x }852ensures { code (BvExtract n lo hi) (Cons x Nil) = extract hi lo x }853= {proof…} bv_id n x;854let l = hi - lo + 1 in855let c = z_extract x lo l in856Zbit.mask_nonneg l;857Zbit.land_nonneg_l (Zbit.mask l) (Zbit.asr x lo);858assert { 0 <= c };859let lemma bit (i:int) : unit860requires { 0 <= i }861ensures { Zbit.bittest c i <-> (i < l /\ Zbit.bittest x (lo + i)) }862= Zbit.def_asr x lo i;863if i < l then Zbit.mask_bits l i else Zbit.mask_bits_high l i in864in_range_bits l c;865assert { forall i. 0 <= i -> (Zbit.bittest (extract hi lo x) i <-> i < l /\ Zbit.bittest x (lo + i)) };866in_range_bits l (extract hi lo x);867same_bits l c (extract hi lo x) {qed}868Valid (61ms) (colibri2)869let ghost op_neg (n x:int) : unit870requires { 1 <= n /\ in_range n x }871ensures { code (BvNeg n) (Cons x Nil) = bvneg n x }872= {proof…} bv_id n x; pow_lsl n; nat2bv_ext n (power 2 n - x) {qed}873Valid (66ms) (colibri2)874let ghost op_add (n x y:int) : unit875requires { 1 <= n /\ in_range n x /\ in_range n y }876ensures { code (BvAdd n) (Cons x (Cons y Nil)) = bvadd n x y }877= {proof…} bv_id n x; bv_id n y; nat2bv_ext n (x + y) {qed}878Valid (77ms) (colibri2)879let ghost op_mul (n x y:int) : unit880requires { 1 <= n /\ in_range n x /\ in_range n y }881ensures { code (BvMul n) (Cons x (Cons y Nil)) = bvmul n x y }882= {proof…} bv_id n x; bv_id n y; nat2bv_ext n (x * y) {qed}883Valid (79ms) (colibri2)884let ghost op_sub (n x y:int) : unit885requires { 1 <= n /\ in_range n x /\ in_range n y }886ensures { code (BvSub n) (Cons x (Cons y Nil)) = bvsub n x y }887= {proof…} bv_id n x; bv_id n y;888let p = power 2 n in889pow_pos n;890mod_add x (p - y) p;891assert { x + (p - y) = p * 1 + (x - y) };892assert { E.mod (p * 1 + (x - y)) p = E.mod (x - y) p };893ext_mod n (x - y) {qed}894
All ones
Valid (127ms) (cvc4)let ghost ones (n:int) : unit897requires { 1 <= n }898ensures { ext n (-1) = lam n (fun _ -> true) }899= {proof…} ext_bits n (-1); ext_range n (-1);900let lemma bit (i:int) : unit901requires { 0 <= i }902ensures { Zbit.bittest (-1) i }903= SB.minus_one_bits i in904in_range_bits n (lam n (fun _ -> true));905same_bits n (ext n (-1)) (lam n (fun _ -> true)) {qed}906Valid (68ms) (colibri2)907let ghost op_udiv (n x y:int) : unit908requires { 1 <= n /\ in_range n x /\ in_range n y }909ensures { code (BvUdiv n) (Cons x (Cons y Nil)) = bvudiv n x y }910= {proof…} bv_id n x; bv_id n y;911if y = 0 then ones n912else begin cdiv_pos x y; nat2bv_ext n (E.div x y) end {qed}913Valid (70ms) (colibri2)914let ghost op_urem (n x y:int) : unit915requires { 1 <= n /\ in_range n x /\ in_range n y }916ensures { code (BvUrem n) (Cons x (Cons y Nil)) = bvurem n x y }917= {proof…} bv_id n x; bv_id n y;918if y <> 0 then begin cdiv_pos x y; nat2bv_ext n (E.mod x y) end {qed}919Valid (398ms) (colibri2 12) (split_vc) (depth 1)920let ghost op_shl (n x y:int) : unit921requires { 1 <= n /\ in_range n x /\ in_range n y }922ensures { code (BvShl n) (Cons x (Cons y Nil)) = bvshl n x y }923= {proof…} bv_id n x; bv_id n y; range_high n y;924Zbit.lsl_mul x y;925nat2bv_ext n (x * power 2 y);926if n <= y then begin927let p = power 2 n in928pow_pos n;929assert { power 2 y = p * power 2 (y - n) };930assert { x * power 2 y = p * (x * power 2 (y - n)) + 0 };931assert { E.mod (p * (x * power 2 (y - n)) + 0) p = E.mod 0 p };932ext_mod n (x * power 2 y)933end else ext_mod n (Zbit.lsl x y) {qed}934
bvlshr is asr
Valid (149ms) (colibri2)let ghost lshr_asr (n x y:int) : unit937requires { 1 <= n /\ in_range n x /\ 0 <= y }938ensures { bvlshr n x y = Zbit.asr x y }939ensures { in_range n (Zbit.asr x y) }940= {proof…} Zbit.asr_div x y;941range_high n x;942nat2bv_ext n (E.div x (power 2 y));943Zbit.asr_nonneg x y;944in_range_bits n (Zbit.asr x y);945ext_id n (Zbit.asr x y) {qed}946Valid (791ms) (colibri2)947let ghost op_lshr (n x y:int) : unit948requires { 1 <= n /\ in_range n x /\ in_range n y }949ensures { code (BvLshr n) (Cons x (Cons y Nil)) = bvlshr n x y }950= {proof…} bv_id n x; bv_id n y; range_high n y;951lshr_asr n x y;952range_high n x;953if n <= y then begin954let lemma bit (i:int) : unit955requires { 0 <= i }956ensures { not (Zbit.bittest (Zbit.asr x y) i) }957= () in958Zbit.ext_bittest (Zbit.asr x y) 0959end else ext_id n (Zbit.asr x y) {qed}960
The bits of bvnot
Valid (123ms) (cvc4)let ghost not_bits (n x:int) : unit963requires { 1 <= n }964ensures { in_range n (bvnot n x) }965ensures { forall i. 0 <= i -> (Zbit.bittest (bvnot n x) i <-> i < n /\ not (Zbit.bittest x i)) }966= in_range_bits n (bvnot n x)967
The bits of signed
Valid (151ms) (cvc5)let ghost signed_bits (n x:int) : unit970requires { 1 <= n /\ in_range n x }971ensures { forall i. 0 <= i ->972(Zbit.bittest (signed n x) i <-> if i < n then Zbit.bittest x i else Zbit.bittest x (n - 1)) }973= {proof…} signed_val n x; range_high n x; pow_lsl n;974let lemma bit (i:int) : unit975requires { 0 <= i }976ensures { Zbit.bittest (signed n x) i <-> if i < n then Zbit.bittest x i else Zbit.bittest x (n - 1) }977= if Zbit.bittest x (n - 1) then begin978if i < n then Zbit.bittest_sub_lsl x n i else Zbit.bittest_sub_lsl_high x n i979end in () {qed}980Valid (1.6s) (colibri2 21) (cvc4) (split_vc 3) (depth 3)981let ghost op_ashr (n x y:int) : unit982requires { 1 <= n /\ in_range n x /\ in_range n y }983ensures { code (BvAshr n) (Cons x (Cons y Nil)) = bvashr n x y }984= {proof…} bv_id n y; range_high n y; range_high n x;985msb_val n x;986signed_bits n x;987let b = if n <= y then n else y in988let c = ext n (Zbit.asr (signed n x) b) in989ext_bits n (Zbit.asr (signed n x) b); ext_range n (Zbit.asr (signed n x) b);990if Zbit.bittest x (n - 1) then begin991not_bits n x;992lshr_asr n (bvnot n x) y;993not_bits n (bvlshr n (bvnot n x) y);994let lemma bit (i:int) : unit995requires { 0 <= i < n }996ensures { Zbit.bittest c i <-> Zbit.bittest (bvashr n x y) i }997= Zbit.def_asr (signed n x) b i; Zbit.def_asr (bvnot n x) y i in998same_bits n c (bvashr n x y)999end else begin1000lshr_asr n x y;1001let lemma bit (i:int) : unit1002requires { 0 <= i < n }1003ensures { Zbit.bittest c i <-> Zbit.bittest (bvashr n x y) i }1004= Zbit.def_asr (signed n x) b i; Zbit.def_asr x y i in1005same_bits n c (bvashr n x y)1006end {qed}1007Valid (1.5s) (colibri2 3) (cvc4) (cvc5 6) (split_vc) (depth 1)1008let ghost op_cmp (op:builtin) (n x y:int) : unit1009requires { 1 <= n /\ in_range n x /\ in_range n y }1010requires { match op with1011| BvUlt m | BvUle m | BvUgt m | BvUge m | BvSlt m | BvSle m | BvSgt m | BvSge m -> m = n1012| _ -> false end }1013ensures { code op (Cons x (Cons y Nil)) = match op with1014| BvUlt _ -> bool (bvult x y)1015| BvUle _ -> bool (bvule x y)1016| BvUgt _ -> bool (bvugt x y)1017| BvUge _ -> bool (bvuge x y)1018| BvSlt _ -> bool (bvslt n x y)1019| BvSle _ -> bool (bvsle n x y)1020| BvSgt _ -> bool (bvsgt n x y)1021| _ -> bool (bvsge n x y) end }1022= {proof…} bv_id n x; bv_id n y;1023signed_val n x; signed_val n y; msb_val n x; msb_val n y;1024pow_lsl n;1025assert { signed n x < signed n y <-> bvslt n x y };1026assert { signed n y < signed n x <-> bvslt n y x };1027assert { signed n x <= signed n y <-> bvsle n x y };1028assert { signed n y <= signed n x <-> bvsle n y x } {qed}1029Valid (54ms) (colibri2)1030let ghost op_bv2nat (n x:int) : unit1031requires { 1 <= n /\ in_range n x }1032ensures { code (Bv2nat n) (Cons x Nil) = ubv_to_int x }1033= bv_id n x1034Valid (126ms) (cvc5)1035let ghost op_sbv2int (n x:int) : unit1036requires { 1 <= n /\ in_range n x }1037ensures { code (Sbv2int n) (Cons x Nil) = sbv_to_int n x }1038= signed_val n x1039Valid (80ms) (colibri2)1040let ghost op_int2bv (n x:int) : unit1041requires { 1 <= n }1042ensures { code (Int2bv n) (Cons x Nil) = int_to_bv n x }1043= {proof…} pow_pos n;1044ext_mod n x;1045nat2bv_ext n (E.mod x (power 2 n));1046ext_mod n (E.mod x (power 2 n)) {qed}1047
The truncated division is unique
Valid (352ms) (colibri2 10) (cvc5 3) (split_vc 3) (depth 3)let ghost cdiv_unique (a b q r:int) : unit1052requires { b <> 0 }1053requires { a = q * b + r }1054requires { 0 <= r < b \/ b < r <= 0 \/ 0 <= r < - b \/ - b < r <= 0 }1055requires { a >= 0 -> r >= 0 }1056requires { a <= 0 -> r <= 0 }1057ensures { C.div a b = q /\ C.mod a b = r }1058= {proof…} let q' = C.div a b in1059let r' = C.mod a b in1060assert { a = q' * b + r' };1061assert { (a >= 0 -> r' >= 0) /\ (a <= 0 -> r' <= 0) };1062assert { - (if b < 0 then - b else b) < r' < (if b < 0 then - b else b) };1063assert { (q - q') * b = r' - r };1064if q <> q' then begin1065if b > 0 then begin1066if q > q' then assert { (q - q') * b >= b } else assert { (q' - q) * b >= b }1067end else begin1068if q > q' then assert { (q - q') * (- b) >= - b } else assert { (q' - q) * (- b) >= - b }1069end1070end {qed}1071
The truncated division by the signs of the absolute values
Valid (402ms) (colibri2 26) (cvc5) (split_vc) (depth 1)let ghost cdiv_signs (a b:int) : unit1074requires { 0 <= a /\ 0 < b }1075ensures { C.div a b = E.div a b /\ C.mod a b = E.mod a b }1076ensures { C.div (- a) b = - E.div a b /\ C.mod (- a) b = - E.mod a b }1077ensures { C.div a (- b) = - E.div a b /\ C.mod a (- b) = E.mod a b }1078ensures { C.div (- a) (- b) = E.div a b /\ C.mod (- a) (- b) = - E.mod a b }1079= {proof…} let q = E.div a b in1080let r = E.mod a b in1081assert { a = q * b + r /\ 0 <= r < b };1082cdiv_unique a b q r;1083cdiv_unique (- a) b (- q) (- r);1084cdiv_unique a (- b) (- q) r;1085cdiv_unique (- a) (- b) q (- r) {qed}1086
The Euclidean remainder of - a
Valid (403ms) (colibri2 7) (cvc5) (split_vc) (depth 1)let ghost emod_neg (a b:int) : unit1089requires { 0 <= a /\ 0 < b }1090ensures { E.mod (- a) b = if E.mod a b = 0 then 0 else b - E.mod a b }1091= {proof…} let q = E.div a b in1092let r = E.mod a b in1093assert { a = q * b + r /\ 0 <= r < b };1094if r = 0 then begin1095assert { - a = (- q) * b + 0 };1096assert { E.div (- a) b = - q by (- q) * b <= - a < (- q) * b + b }1097end else begin1098assert { - a = (- q - 1) * b + (b - r) };1099assert { E.div (- a) b = - q - 1 by (- q - 1) * b <= - a < (- q - 1) * b + b }1100end {qed}1101
The floor remainder
Valid (1.4s) (colibri2 3) (split_vc) (depth 1)let ghost fmod_val (a b:int) : unit1104requires { b <> 0 }1105ensures { a - fdiv a b * b = if b > 0 then E.mod a b else - E.mod (- a) (- b) }1106= {proof…} if b > 0 then assert { a = b * E.div a b + E.mod a b }1107else assert { - a = (- b) * E.div (- a) (- b) + E.mod (- a) (- b) } {qed}1108
E.mod of a small value
Valid (37ms) (colibri2)let ghost small_mod (d p:int) : unit1111requires { 0 <= d < p }1112ensures { E.mod d p = d }1113= assert { E.div d p = 0 }1114
The absolute value of a signed bit–vector: abs_s of bvsmod
Valid (372ms) (colibri2) (cvc5 12) (split_vc 2) (depth 2)let ghost abs_val (n x:int) : unit1117requires { 1 <= n /\ in_range n x }1118ensures { msb n x = 0 \/ msb n x = 1 }1119ensures { msb n x = 0 -> signed n x = x }1120ensures { msb n x = 1 -> bvneg n x = - signed n x /\ 0 < bvneg n x < power 2 n }1121ensures { 0 <= x < power 2 n }1122ensures { msb n x = 1 -> 0 < x }1123= {proof…} msb_val n x; signed_val n x; pow_lsl n; pow_pos n;1124if Zbit.bittest x (n - 1) then begin1125assert { x <> 0 by not (Zbit.bittest 0 (n - 1)) };1126assert { 0 < power 2 n - x < power 2 n };1127small_mod (power 2 n - x) (power 2 n);1128assert { E.mod (power 2 n - x) (power 2 n) = power 2 n - x }1129end {qed}1130
bvneg of a non–negative value below 2^n
Valid (47ms) (colibri2)let ghost neg_val (n u:int) : unit1133requires { 1 <= n /\ 0 <= u < power 2 n }1134ensures { bvneg n u = E.mod (- u) (power 2 n) }1135= {proof…} pow_pos n;1136assert { power 2 n - u = power 2 n * 1 + (- u) };1137assert { E.mod (power 2 n * 1 + (- u)) (power 2 n) = E.mod (- u) (power 2 n) } {qed}1138
A value below 2^n is its own nat2bv
Valid (41ms) (colibri2)let ghost nat2bv_id (n u:int) : unit1141requires { 1 <= n /\ 0 <= u < power 2 n }1142ensures { nat2bv n u = u }1143= ()1144Valid (1.7s) (colibri2 26) (cvc5) (split_vc 2) (depth 2)1145let ghost op_sdiv (n x y:int) : unit1146requires { 1 <= n /\ in_range n x /\ in_range n y }1147ensures { code (BvSdiv n) (Cons x (Cons y Nil)) = bvsdiv n x y }1148= {proof…} abs_val n x; abs_val n y;1149let p = power 2 n in1150pow_pos n; pow_lsl n;1151assert { p >= 2 by power 2 n = 2 * power 2 (n - 1) };1152let sa = signed n x in1153let sb = signed n y in1154ext_mod n 1; ext_mod n (-1);1155assert { E.mod 1 p = 1 /\ E.mod (-1) p = p - 1 };1156ones n;1157if y = 0 then begin1158msb_val n y;1159assert { msb n y = 0 };1160if msb n x = 1 then begin1161neg_val n (p - 1);1162assert { bvudiv n (bvneg n x) y = p - 1 };1163assert { sa < 0 }1164end1165end else begin1166let a = if msb n x = 0 then x else bvneg n x in1167let b = if msb n y = 0 then y else bvneg n y in1168assert { 0 <= a < p /\ 0 < b < p };1169assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };1170cdiv_signs a b;1171let q = E.div a b in1172assert { 0 <= q <= a by a = b * q + E.mod a b };1173nat2bv_ext n q; ext_mod n q;1174assert { bvudiv n a b = q };1175neg_val n q;1176ext_mod n (C.div sa sb);1177ext_mod n q1178end {qed}1179Valid (2.0s) (colibri2 22) (cvc4) (split_vc 4) (depth 3)1180let ghost op_srem (n x y:int) : unit1181requires { 1 <= n /\ in_range n x /\ in_range n y }1182ensures { code (BvSrem n) (Cons x (Cons y Nil)) = bvsrem n x y }1183= {proof…} abs_val n x; abs_val n y; bv_id n x;1184let p = power 2 n in1185pow_pos n;1186let sa = signed n x in1187let sb = signed n y in1188if y = 0 then begin1189msb_val n y;1190assert { msb n y = 0 };1191if msb n x = 1 then begin1192neg_val n (bvneg n x);1193assert { E.mod (- (p - x)) p = x by - (p - x) = p * (-1) + x }1194end1195end else begin1196let a = if msb n x = 0 then x else bvneg n x in1197let b = if msb n y = 0 then y else bvneg n y in1198assert { 0 <= a < p /\ 0 < b < p };1199assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };1200cdiv_signs a b;1201let r = E.mod a b in1202assert { 0 <= r < b };1203nat2bv_ext n r; ext_mod n r;1204assert { bvurem n a b = r };1205neg_val n r;1206ext_mod n (C.mod sa sb);1207ext_mod n r1208end {qed}1209Valid (2.3s) (colibri2 44) (cvc5 2) (split_vc 7) (depth 4)1210let ghost op_smod (n x y:int) : unit1211requires { 1 <= n /\ in_range n x /\ in_range n y }1212ensures { code (BvSmod n) (Cons x (Cons y Nil)) = bvsmod n x y }1213= {proof…} abs_val n x; abs_val n y; bv_id n x; bv_id n y;1214let p = power 2 n in1215pow_pos n;1216let sa = signed n x in1217let sb = signed n y in1218if y = 0 then begin1219msb_val n y;1220assert { msb n y = 0 };1221if msb n x = 1 then begin1222let a = bvneg n x in1223assert { bvurem n a y = a };1224neg_val n a;1225assert { E.mod (- (p - x)) p = x by - (p - x) = p * (-1) + x };1226nat2bv_id n x;1227assert { bvadd n (bvneg n a) y = x }1228end1229end else begin1230let a = if msb n x = 0 then x else bvneg n x in1231let b = if msb n y = 0 then y else bvneg n y in1232assert { 0 <= a < p /\ 0 < b < p };1233assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };1234assert { sb <> 0 };1235fmod_val sa sb;1236emod_neg a b;1237let r = E.mod a b in1238assert { 0 <= r < b };1239nat2bv_ext n r; ext_mod n r;1240assert { bvurem n a b = r };1241let f = sa - fdiv sa sb * sb in1242ext_mod n f;1243if r = 0 then begin1244assert { f = 0 };1245assert { E.mod 0 p = 0 }1246end else begin1247neg_val n r;1248if msb n x = 0 then begin1249if msb n y = 0 then begin1250assert { f = r }; nat2bv_id n r1251end else begin1252assert { f = r - b };1253assert { y = p - b by sb = y - p };1254assert { bvadd n r y = r - b + p by1255E.mod (r + y) p = r - b + p by r + y = p * 0 + (r - b + p) };1256assert { E.mod (r - b) p = r - b + p by r - b = p * (-1) + (r - b + p) }1257end1258end else begin1259if msb n y = 0 then begin1260assert { f = b - r };1261assert { bvneg n r = p - r by E.mod (- r) p = p - r by - r = p * (-1) + (p - r) };1262assert { bvadd n (bvneg n r) y = b - r by1263E.mod (p - r + b) p = b - r by p - r + b = p * 1 + (b - r) };1264nat2bv_id n (b - r)1265end else begin1266assert { f = - r };1267assert { bvneg n r = p - r by E.mod (- r) p = p - r by - r = p * (-1) + (p - r) };1268assert { E.mod (- r) p = p - r by - r = p * (-1) + (p - r) }1269end1270end1271end1272end {qed}1273
A bit–vector of size 1 is 0 or 1
Valid (60ms) (colibri2)let ghost range1 (a:int) : unit1278requires { in_range 1 a }1279ensures { a = 0 \/ a = 1 }1280ensures { Zbit.bittest a 0 <-> a = 1 }1281= {proof…} pow_lsl 1; assert { power 2 1 = 2 };1282assert { Zbit.bittest 1 0 };1283assert { not (Zbit.bittest 0 0) } {qed}1284Valid (694ms) (cvc4)1285let ghost xnor1 (a b:int) : unit1286requires { in_range 1 a /\ in_range 1 b }1287ensures { bvxnor 1 a b = if a = b then 1 else 0 }1288= {proof…} range1 a; range1 b;1289let v = bvxnor 1 a b in1290assert { Zbit.bittest (bvnot 1 a) 0 <-> not (Zbit.bittest a 0) };1291assert { Zbit.bittest (bvnot 1 b) 0 <-> not (Zbit.bittest b 0) };1292assert { Zbit.bittest (bvand 1 a b) 0 <-> Zbit.bittest a 0 /\ Zbit.bittest b 0 };1293assert { Zbit.bittest (bvand 1 (bvnot 1 a) (bvnot 1 b)) 0 <->1294not (Zbit.bittest a 0) /\ not (Zbit.bittest b 0) };1295assert { Zbit.bittest v 0 <-> (Zbit.bittest a 0 <-> Zbit.bittest b 0) };1296in_range_bits 1 v;1297range1 v {qed}1298Valid (383ms) (colibri2)1299let ghost and1 (a b:int) : unit1300requires { in_range 1 a /\ in_range 1 b }1301ensures { bvand 1 a b = if a = 1 /\ b = 1 then 1 else 0 }1302= {proof…} range1 a; range1 b;1303let v = bvand 1 a b in1304assert { Zbit.bittest v 0 <-> Zbit.bittest a 0 /\ Zbit.bittest b 0 };1305in_range_bits 1 v;1306range1 v {qed}1307
The low bits 0..i of s
Valid (738ms) (cvc5)let ghost low_bits (i s:int) : unit1310requires { 0 <= i }1311ensures { in_range (i + 1) (extract i 0 s) }1312ensures { forall k. 0 <= k -> (Zbit.bittest (extract i 0 s) k <-> k <= i /\ Zbit.bittest s k) }1313= in_range_bits (i + 1) (extract i 0 s)1314Valid (364ms) (colibri2 22) (split_vc) (depth 1)1315let rec ghost comp_val (m s t:int) : unit1316requires { 1 <= m /\ in_range m s /\ in_range m t }1317variant { m }1318ensures { bvcomp m s t = if s = t then 1 else 0 }1319= {proof…} if m = 1 then begin1320range1 s; range1 t; xnor1 s t1321end else begin1322let hs = extract (m - 1) (m - 1) s in1323let ht = extract (m - 1) (m - 1) t in1324extract1 (m - 1) s; extract1 (m - 1) t;1325pow_lsl 1; assert { power 2 1 = 2 };1326assert { in_range 1 hs /\ in_range 1 ht };1327let ls = extract (m - 2) 0 s in1328let lt = extract (m - 2) 0 t in1329low_bits (m - 2) s; low_bits (m - 2) t;1330comp_val (m - 1) ls lt;1331xnor1 hs ht;1332let c = bvcomp (m - 1) ls lt in1333assert { in_range 1 c by c = 0 \/ c = 1 };1334and1 (bvxnor 1 hs ht) c;1335assert { bvcomp m s t = bvand 1 (bvxnor 1 hs ht) c };1336range_high m s; range_high m t;1337if hs = ht && ls = lt then begin1338let lemma bit (k:int) : unit1339requires { 0 <= k < m }1340ensures { Zbit.bittest s k <-> Zbit.bittest t k }1341= if k = m - 1 then () else1342assert { Zbit.bittest ls k <-> Zbit.bittest lt k } in1343same_bits m s t1344end else begin1345if s = t then absurd1346end1347end {qed}1348Valid (60ms) (colibri2)1349let ghost op_comp (n x y:int) : unit1350requires { 1 <= n /\ in_range n x /\ in_range n y }1351ensures { code (BvComp n) (Cons x (Cons y Nil)) = bvcomp n x y }1352= {proof…} bv_id n x; bv_id n y; comp_val n x y;1353ext_mod 1 (-1); assert { power 2 1 = 2 } {qed}1354
The bits of the loop of Sem.repeat
Valid (163ms) (colibri2 10) (cvc5 2) (split_vc) (depth 1)let rec ghost sem_repeat_bits (n k a:int) : unit1357requires { 1 <= n /\ 0 <= k /\ in_range n a }1358variant { k }1359ensures { 0 <= Sem.repeat n k a }1360ensures { forall i. 0 <= i ->1361(Zbit.bittest (Sem.repeat n k a) i <-> i < n * k /\ Zbit.bittest a (E.mod i n)) }1362= {proof…} range_high n a;1363if k > 0 then begin1364sem_repeat_bits n (k - 1) a;1365let r = Sem.repeat n (k - 1) a in1366Zbit.lsl_mul r n;1367let lemma bit (i:int) : unit1368requires { 0 <= i }1369ensures { Zbit.bittest (Sem.repeat n k a) i <-> i < n * k /\ Zbit.bittest a (E.mod i n) }1370= Zbit.def_asr r (- n) i;1371if i < n then begin1372small_mod i n;1373Zbit.bittest_neg r (i - n)1374end else begin1375assert { i = n * 1 + (i - n) };1376assert { E.mod (n * 1 + (i - n)) n = E.mod (i - n) n }1377end in ()1378end {qed}1379
The bits of repeat
Valid (702ms) (colibri2 15) (cvc5) (split_vc 3) (depth 3)let rec ghost repeat_bits (j m t:int) : unit1382requires { 1 <= m /\ 1 <= j /\ in_range m t }1383variant { j }1384ensures { in_range (m * j) (Smtlib.repeat j m t) }1385ensures { forall i. 0 <= i ->1386(Zbit.bittest (Smtlib.repeat j m t) i <-> i < m * j /\ Zbit.bittest t (E.mod i m)) }1387= {proof…} range_high m t;1388if j = 1 then begin1389let lemma bit (i:int) : unit1390requires { 0 <= i < m }1391ensures { E.mod i m = i }1392= small_mod i m in ()1393end else begin1394repeat_bits (j - 1) m t;1395let r = Smtlib.repeat (j - 1) m t in1396let c = concat m (m * (j - 1)) t r in1397let lemma bit (i:int) : unit1398requires { 0 <= i }1399ensures { Zbit.bittest c i <-> i < m * j /\ Zbit.bittest t (E.mod i m) }1400= if m * (j - 1) <= i < m * j then begin1401small_mod (i - m * (j - 1)) m;1402assert { i = m * (j - 1) + (i - m * (j - 1)) };1403assert { E.mod (m * (j - 1) + (i - m * (j - 1))) m = E.mod (i - m * (j - 1)) m }1404end in1405in_range_bits (m * j) c1406end {qed}1407Valid (685ms) (cvc5)1408let ghost op_repeat (n k x:int) : unit1409requires { 1 <= n /\ 1 <= k /\ in_range n x }1410ensures { code (BvRepeat n k) (Cons x Nil) = Smtlib.repeat k n x }1411= {proof…} bv_id n x;1412sem_repeat_bits n k x; repeat_bits k n x;1413in_range_bits (n * k) (Sem.repeat n k x);1414same_bits (n * k) (Sem.repeat n k x) (Smtlib.repeat k n x) {qed}1415
A bit–vector of size n is one of size n + k
Valid (42ms) (colibri2)let ghost range_up (n k x:int) : unit1418requires { in_range n x /\ 0 <= k }1419ensures { in_range (n + k) x }1420= range_high n x; in_range_bits (n + k) x1421Valid (846ms) (colibri2 11) (cvc5) (split_vc) (depth 1)1422let ghost op_zero_extend (n k x:int) : unit1423requires { 1 <= n /\ 0 <= k /\ in_range n x }1424ensures { code (BvZeroExtend n k) (Cons x Nil) = zero_extend k n x }1425= {proof…} bv_id n x;1426if k > 0 then begin1427pow_lsl 1; assert { power 2 1 = 2 };1428repeat_bits k 1 0;1429let z = Smtlib.repeat k 1 0 in1430let c = concat k n z x in1431range_high n x;1432in_range_bits (k + n) c;1433range_up n k x;1434assert { not (Zbit.bittest 0 0) };1435same_bits (n + k) x c1436end {qed}1437Valid (1.2s) (colibri2 20) (cvc4) (cvc5 2) (split_vc) (depth 1)1438let ghost op_sign_extend (n k x:int) : unit1439requires { 1 <= n /\ 0 <= k /\ in_range n x }1440ensures { code (BvSignExtend n k) (Cons x Nil) = sign_extend k n x }1441= {proof…} bv_id n x; range_high n x;1442let e = extract (n - 1) (n - 1) x in1443extract1 (n - 1) x;1444let w = Zbit.lor (Zbit.lsl (-1) n) x in1445ext_bits (n + k) w; ext_range (n + k) w;1446let lemma wbit (i:int) : unit1447requires { 0 <= i }1448ensures { Zbit.bittest w i <-> if i < n then Zbit.bittest x i else true }1449= Zbit.def_asr (-1) (- n) i;1450if i >= n then SB.minus_one_bits (i - n) else Zbit.bittest_neg (-1) (i - n) in1451if k = 0 then begin1452if Zbit.bittest x (n - 1) then same_bits n (ext n w) x1453end else begin1454pow_lsl 1; assert { power 2 1 = 2 };1455assert { in_range 1 e };1456repeat_bits k 1 e;1457let c = concat k n (Smtlib.repeat k 1 e) x in1458in_range_bits (k + n) c;1459let lemma mod1 (i:int) : unit ensures { E.mod i 1 = 0 } = () in1460assert { Zbit.bittest e 0 <-> Zbit.bittest x (n - 1) };1461if Zbit.bittest x (n - 1) then same_bits (n + k) (ext (n + k) w) c1462else begin range_up n k x; same_bits (n + k) x c end1463end {qed}1464
The rotations, by the bits
Valid (6.0s) (colibri2 20) (cvc4) (cvc5 2) (split_vc 4) (depth 3)let rec ghost rotl_bits (i m t:int) : unit1467requires { 1 <= m /\ 0 <= i /\ in_range m t }1468variant { i }1469ensures { in_range m (rotate_left i m t) }1470ensures { forall p. 0 <= p < m ->1471(Zbit.bittest (rotate_left i m t) p <-> Zbit.bittest t (E.mod (p - i) m)) }1472= {proof…} if i = 0 then begin1473let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p - i) m = p }1474= small_mod p m in ()1475end else if m = 1 then begin1476let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p - i) m = 0 = p }1477= () in ()1478end else begin1479let lo = extract (m - 2) 0 t in1480let hi = extract (m - 1) (m - 1) t in1481let u = concat (m - 1) 1 lo hi in1482low_bits (m - 2) t;1483in_range_bits m u;1484let lemma ubit (p:int) : unit1485requires { 0 <= p < m }1486ensures { Zbit.bittest u p <-> Zbit.bittest t (E.mod (p - 1) m) }1487= if p = 0 then begin1488assert { E.mod (-1) m = m - 1 by - 1 = m * (-1) + (m - 1) };1489small_mod (m - 1) m;1490assert { E.mod (m * (-1) + (m - 1)) m = E.mod (m - 1) m }1491end else small_mod (p - 1) m in1492rotl_bits (i - 1) m u;1493let lemma bit (p:int) : unit1494requires { 0 <= p < m }1495ensures { Zbit.bittest (rotate_left i m t) p <-> Zbit.bittest t (E.mod (p - i) m) }1496= let q = E.mod (p - (i - 1)) m in1497assert { 0 <= q < m };1498ubit q;1499mod_add (-1) (p - (i - 1)) m in ()1500end {qed}1501Valid (1.2s) (colibri2 18) (cvc5 4) (split_vc 4) (depth 3)1502let rec ghost rotr_bits (i m t:int) : unit1503requires { 1 <= m /\ 0 <= i /\ in_range m t }1504variant { i }1505ensures { in_range m (rotate_right i m t) }1506ensures { forall p. 0 <= p < m ->1507(Zbit.bittest (rotate_right i m t) p <-> Zbit.bittest t (E.mod (p + i) m)) }1508= {proof…} if i = 0 then begin1509let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p + i) m = p }1510= small_mod p m in ()1511end else if m = 1 then begin1512let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p + i) m = 0 = p }1513= () in ()1514end else begin1515let lo = extract 0 0 t in1516let hi = extract (m - 1) 1 t in1517let u = concat 1 (m - 1) lo hi in1518assert { forall k. 0 <= k -> (Zbit.bittest hi k <-> k < m - 1 /\ Zbit.bittest t (1 + k)) };1519assert { forall k. 0 <= k -> (Zbit.bittest lo k <-> k < 1 /\ Zbit.bittest t k) };1520in_range_bits m u;1521let lemma ubit (p:int) : unit1522requires { 0 <= p < m }1523ensures { Zbit.bittest u p <-> Zbit.bittest t (E.mod (p + 1) m) }1524= if p = m - 1 then begin1525assert { E.mod m m = 0 by m = m * 1 + 0 }1526end else small_mod (p + 1) m in1527rotr_bits (i - 1) m u;1528let lemma bit (p:int) : unit1529requires { 0 <= p < m }1530ensures { Zbit.bittest (rotate_right i m t) p <-> Zbit.bittest t (E.mod (p + i) m) }1531= let q = E.mod (p + (i - 1)) m in1532assert { 0 <= q < m };1533ubit q;1534mod_add 1 (p + (i - 1)) m in ()1535end {qed}1536Valid (2.4s) (colibri2 34) (split_vc 3) (depth 3)1537let ghost op_rotl (n i x:int) : unit1538requires { 1 <= n /\ 0 <= i /\ in_range n x }1539ensures { code (BvRotl n i) (Cons x Nil) = rotate_left i n x }1540= {proof…} bv_id n x; range_high n x;1541rotl_bits i n x;1542let k = C.mod i n in1543cdiv_pos i n;1544assert { 0 <= k < n };1545let lemma md (p:int) : unit1546requires { 0 <= p < n }1547ensures { E.mod (p - i) n = E.mod (p - k) n }1548= assert { p - i = n * (- E.div i n) + (p - k) };1549assert { E.mod (n * (- E.div i n) + (p - k)) n = E.mod (p - k) n } in1550if k = 0 then begin1551ext_id n x;1552let lemma bit (p:int) : unit1553requires { 0 <= p < n }1554ensures { Zbit.bittest x p <-> Zbit.bittest (rotate_left i n x) p }1555= md p; small_mod p n in1556same_bits n x (rotate_left i n x)1557end else begin1558let w = Zbit.lor (Zbit.lsl x k) (z_extract x (n - k) k) in1559ext_bits n w; ext_range n w;1560let lemma bit (p:int) : unit1561requires { 0 <= p < n }1562ensures { Zbit.bittest (ext n w) p <-> Zbit.bittest (rotate_left i n x) p }1563= md p;1564Zbit.def_asr x (- k) p;1565Zbit.def_asr x (n - k) p;1566if p < k then begin1567Zbit.bittest_neg x (p - k);1568Zbit.mask_bits k p;1569assert { p - k = n * (-1) + (p - k + n) };1570assert { E.mod (n * (-1) + (p - k + n)) n = E.mod (p - k + n) n };1571small_mod (p - k + n) n1572end else begin1573Zbit.mask_bits_high k p;1574small_mod (p - k) n1575end in1576same_bits n (ext n w) (rotate_left i n x)1577end {qed}1578Valid (1.4s) (colibri2)1579let ghost op_rotr (n i x:int) : unit1580requires { 1 <= n /\ 0 <= i /\ in_range n x }1581ensures { code (BvRotr n i) (Cons x Nil) = rotate_right i n x }1582= {proof…} bv_id n x; range_high n x;1583rotr_bits i n x;1584let k = C.mod i n in1585cdiv_pos i n;1586assert { 0 <= k < n };1587let w = Zbit.lor (Zbit.lsl x (n - k)) (Zbit.asr x k) in1588ext_bits n w; ext_range n w;1589let lemma bit (p:int) : unit1590requires { 0 <= p < n }1591ensures { Zbit.bittest (ext n w) p <-> Zbit.bittest (rotate_right i n x) p }1592= assert { p + i = n * E.div i n + (p + k) };1593assert { E.mod (n * E.div i n + (p + k)) n = E.mod (p + k) n };1594Zbit.def_asr x (k - n) p;1595Zbit.def_asr x k p;1596if p + k < n then begin1597small_mod (p + k) n;1598Zbit.bittest_neg x (p + k - n)1599end else begin1600assert { p + k = n * 1 + (p + k - n) };1601assert { E.mod (n * 1 + (p + k - n)) n = E.mod (p + k - n) n };1602small_mod (p + k - n) n1603end in1604same_bits n (ext n w) (rotate_right i n x) {qed}1605
The SMT–LIB terms: sizes > 0, extract with 0 <= lo <= hi < n, repeat at least once, extensions and rotations by >= 0
predicate well_sorted (b:builtin) =1611match b with1612| And | Or | Xor | Not | Asr | Extract | SignedExtract | Update | Test -> false1613| BvConcat n m -> 0 < n /\ 0 < m1614| BvExtract n lo hi -> 0 <= lo <= hi < n1615| BvRepeat n k -> 0 < n /\ 1 <= k1616| BvZeroExtend n k | BvSignExtend n k | BvRotl n k | BvRotr n k -> 0 < n /\ 0 <= k1617| Sbv2int n | Bv2nat n | Int2bv n1618| BvNot n | BvAnd n | BvOr n | BvXor n | BvNand n | BvNor n | BvXnor n | BvComp n1619| BvNeg n | BvAdd n | BvSub n | BvMul n | BvUdiv n | BvUrem n | BvSdiv n | BvSrem n1620| BvSmod n | BvShl n | BvLshr n | BvAshr n | BvUlt n | BvUle n | BvUgt n | BvUge n1621| BvSlt n | BvSle n | BvSgt n | BvSge n -> 0 < n1622end1623
The SMT–LIB semantics of a builtin applied to the values l (a Boolean is -1 or 0, as in code)
function smt (b:builtin) (l:list int) : int =1627match b, l with1628| Sbv2int n, Cons x Nil -> sbv_to_int n x1629| Bv2nat _, Cons x Nil -> ubv_to_int x1630| Int2bv n, Cons x Nil -> int_to_bv n x1631| BvConcat n m, Cons x (Cons y Nil) -> concat n m x y1632| BvExtract _ lo hi, Cons x Nil -> extract hi lo x1633| BvRepeat n k, Cons x Nil -> Smtlib.repeat k n x1634| BvZeroExtend n k, Cons x Nil -> zero_extend k n x1635| BvSignExtend n k, Cons x Nil -> sign_extend k n x1636| BvRotl n i, Cons x Nil -> rotate_left i n x1637| BvRotr n i, Cons x Nil -> rotate_right i n x1638| BvNot n, Cons x Nil -> bvnot n x1639| BvAnd n, Cons x (Cons y Nil) -> bvand n x y1640| BvOr n, Cons x (Cons y Nil) -> bvor n x y1641| BvXor n, Cons x (Cons y Nil) -> bvxor n x y1642| BvNand n, Cons x (Cons y Nil) -> bvnand n x y1643| BvNor n, Cons x (Cons y Nil) -> bvnor n x y1644| BvXnor n, Cons x (Cons y Nil) -> bvxnor n x y1645| BvComp n, Cons x (Cons y Nil) -> bvcomp n x y1646| BvNeg n, Cons x Nil -> bvneg n x1647| BvAdd n, Cons x (Cons y Nil) -> bvadd n x y1648| BvSub n, Cons x (Cons y Nil) -> bvsub n x y1649| BvMul n, Cons x (Cons y Nil) -> bvmul n x y1650| BvUdiv n, Cons x (Cons y Nil) -> bvudiv n x y1651| BvUrem n, Cons x (Cons y Nil) -> bvurem n x y1652| BvSdiv n, Cons x (Cons y Nil) -> bvsdiv n x y1653| BvSrem n, Cons x (Cons y Nil) -> bvsrem n x y1654| BvSmod n, Cons x (Cons y Nil) -> bvsmod n x y1655| BvShl n, Cons x (Cons y Nil) -> bvshl n x y1656| BvLshr n, Cons x (Cons y Nil) -> bvlshr n x y1657| BvAshr n, Cons x (Cons y Nil) -> bvashr n x y1658| BvUlt _, Cons x (Cons y Nil) -> bool (bvult x y)1659| BvUle _, Cons x (Cons y Nil) -> bool (bvule x y)1660| BvUgt _, Cons x (Cons y Nil) -> bool (bvugt x y)1661| BvUge _, Cons x (Cons y Nil) -> bool (bvuge x y)1662| BvSlt n, Cons x (Cons y Nil) -> bool (bvslt n x y)1663| BvSle n, Cons x (Cons y Nil) -> bool (bvsle n x y)1664| BvSgt n, Cons x (Cons y Nil) -> bool (bvsgt n x y)1665| BvSge n, Cons x (Cons y Nil) -> bool (bvsge n x y)1666| _ -> code b l1667end1668
Sem.code, so the model check (Sem.eval), computes the SMT–LIB semantics of the well–sorted terms whose bit–vector arguments are in range
Valid (1.7s) (cvc5)let ghost code_is_smtlib (b:builtin) (l:list int) : unit1673requires { well_sorted b /\ args_ok b l }1674ensures { code b l = smt b l }1675= {proof…} match b, l with1676| Sbv2int n, Cons x Nil -> op_sbv2int n x1677| Bv2nat n, Cons x Nil -> op_bv2nat n x1678| Int2bv n, Cons x Nil -> op_int2bv n x1679| BvConcat n m, Cons x (Cons y Nil) -> op_concat n m x y1680| BvExtract n lo hi, Cons x Nil -> op_extract n lo hi x1681| BvRepeat n k, Cons x Nil -> op_repeat n k x1682| BvZeroExtend n k, Cons x Nil -> op_zero_extend n k x1683| BvSignExtend n k, Cons x Nil -> op_sign_extend n k x1684| BvRotl n i, Cons x Nil -> op_rotl n i x1685| BvRotr n i, Cons x Nil -> op_rotr n i x1686| BvNot n, Cons x Nil -> op_not n x1687| BvAnd n, Cons x (Cons y Nil) -> op_and n x y1688| BvOr n, Cons x (Cons y Nil) -> op_or n x y1689| BvXor n, Cons x (Cons y Nil) -> op_xor n x y1690| BvNand n, Cons x (Cons y Nil) -> op_nand n x y1691| BvNor n, Cons x (Cons y Nil) -> op_nor n x y1692| BvXnor n, Cons x (Cons y Nil) -> op_xnor n x y1693| BvComp n, Cons x (Cons y Nil) -> op_comp n x y1694| BvNeg n, Cons x Nil -> op_neg n x1695| BvAdd n, Cons x (Cons y Nil) -> op_add n x y1696| BvSub n, Cons x (Cons y Nil) -> op_sub n x y1697| BvMul n, Cons x (Cons y Nil) -> op_mul n x y1698| BvUdiv n, Cons x (Cons y Nil) -> op_udiv n x y1699| BvUrem n, Cons x (Cons y Nil) -> op_urem n x y1700| BvSdiv n, Cons x (Cons y Nil) -> op_sdiv n x y1701| BvSrem n, Cons x (Cons y Nil) -> op_srem n x y1702| BvSmod n, Cons x (Cons y Nil) -> op_smod n x y1703| BvShl n, Cons x (Cons y Nil) -> op_shl n x y1704| BvLshr n, Cons x (Cons y Nil) -> op_lshr n x y1705| BvAshr n, Cons x (Cons y Nil) -> op_ashr n x y1706| (BvUlt n | BvUle n | BvUgt n | BvUge n | BvSlt n | BvSle n | BvSgt n | BvSge n),1707Cons x (Cons y Nil) -> op_cmp b n x y1708| _ -> ()1709end {qed}1710end1711