library colibrilib.bitwise_rules — module RulesThe rules. A rule requires the meaning of the term of r in the model (the interpretation of the builtin in realValue.ml); a term too big for the BDD (Unsupported, Overflow) gives no equation.
module Rules185use int.Int186use option.Option187use colibrilib.known_bits.KnownBits188use colibrilib.zarith.Zbit189use colibrilib.zbit.ZbitInt190use colibrilib.safe_bits.BitsSpec191use colibrilib.safe_bits.SafeBits192use colibrilib.bdd.Node193use colibrilib.sbdd.SNode194use colibrilib.ibdd.IBDD195use colibrilib.bddbitv.Export196use colibrilib.env.Env197use colibrilib.spec.Defines198use list.List199use mach.int.Int63200use int.EuclideanDivision as E201use int.ComputerDivision as C202use colibrilib.bddbitv.IBDDS as S203use colibrilib.bv_sem.Sem204use Term205
The bits of a scalar
Valid (138ms) (colibri2)let ghost scalar_bits (s:int) (c:bool) : unit208requires { s = if c then -1 else 0 }209ensures { forall i. 0 <= i -> (Zbit.bittest s i <-> c) }210= {proof…} let lemma bit (i:int) : unit211requires { 0 <= i }212ensures { Zbit.bittest s i <-> c }213= if c then SafeBits.minus_one_bits i in214() {qed}215
The bits of 2^k
Valid (186ms) (colibri2)let ghost pow_bits (k:int) : unit218requires { 0 <= k }219ensures { forall i. Zbit.bittest (Zbit.lsl 1 k) i <-> i = k }220= {proof…} let lemma bit (i:int) : unit221ensures { Zbit.bittest (Zbit.lsl 1 k) i <-> i = k }222= if i < 0 then Zbit.bittest_neg (Zbit.lsl 1 k) i in223() {qed}224
Converter.testbit_node: the registered node colibri_testbit_int a k
Valid (336ms) (colibri2)let testbit_node (d:env) (a:Node.t) (k:int) : Node.t227ensures { live d -> is_testbit d result a k }228= apply d (testbit_cst ()) (Cons a (Cons (int_node d k) Nil))229
r = a land b
Valid (967ms) (colibri2) (cvc4) (split_vc) (depth 1)let partial logand (d:env) (r a b:Node.t) : unit232requires { live d -> defines2 (ienv d) Zbit.land r a b }233raises { Contradiction -> not live d }234= assume_equality d r (int_logand (monome d a) (monome d b))235
r = a lor b
Valid (341ms) (colibri2)let partial logor (d:env) (r a b:Node.t) : unit238requires { live d -> defines2 (ienv d) Zbit.lor r a b }239raises { Contradiction -> not live d }240= assume_equality d r (int_logor (monome d a) (monome d b))241
r = a lxor b
Valid (101ms) (colibri2)let partial logxor (d:env) (r a b:Node.t) : unit244requires { live d -> defines2 (ienv d) Zbit.lxor r a b }245raises { Contradiction -> not live d }246= assume_equality d r (int_xor (monome d a) (monome d b))247
r = lnot a
Valid (74ms) (colibri2)let partial lognot (d:env) (r a:Node.t) : unit250requires { live d -> defines1 (ienv d) Zbit.lnot r a }251raises { Contradiction -> not live d }252= assume_equality d r (int_lognot (monome d a))253
r = asr a off (colibri_rshift_int)
Valid (177ms) (colibri2 4) (split_vc) (depth 1)let partial shift_right (d:env) (r a:Node.t) (off:int) : unit256requires { live d -> defines1 (ienv d) (fun x -> Zbit.asr x off) r a }257raises { Contradiction -> not live d }258raises { Unsupported -> false }259raises { Overflow -> false }260= try261let x = monome d a in262assume_equality d r263(if off >= 0 then int_shift_right off x else int_shift_left (- off) x)264with Unsupported -> () | Overflow -> () end265
r = extract off len a (colibri_extract_int)
Valid (270ms) (colibri2)let partial extract (d:env) (r a:Node.t) (off len:int) : unit268requires { live d -> defines1 (ienv d) (fun x -> BitsSpec.extract off len x) r a }269raises { Contradiction -> not live d }270raises { Unsupported -> false }271raises { Overflow -> false }272= try assume_equality d r (int_extract off len (monome d a))273with Unsupported -> () | Overflow -> () end274
r = update off len src dst: dst with the bits from off to off+len-1 replaced by the bits of src (colibri_update_int)
Valid (1.1s) (colibri2)let partial update (d:env) (r dst src:Node.t) (off len:int) : unit278requires { live d -> defines2 (ienv d) (fun xs xd -> BitsSpec.update off len xs xd) r src dst }279raises { Contradiction -> not live d }280raises { Unsupported -> false }281raises { Overflow -> false }282= try assume_equality d r (int_update off len (monome d dst) (monome d src))283with Unsupported -> () | Overflow -> () end284
r = signed_extract off len a (colibri_signed_extract_int): the bits of a from off (m = 2^len - 1), and above them the bit off+len-1 of a, the testbit node b: r = ((asr a off) land m) lor (scalar b land lnot m)
Valid (5.7s) (colibri2 49) (cvc4 17) (cvc5) (split_vc 39) (depth 5)let partial signed_extract (d:env) (r a:Node.t) (off len:int) : unit290requires { live d -> defines1 (ienv d) (fun x -> BitsSpec.signed_extract off len x) r a }291raises { Contradiction -> not live d }292raises { Unsupported -> false }293raises { Overflow -> false }294= let k = off + len - 1 in295if 0 < len <= 0x100000 && 0 <= k then begin296let b = testbit_node d a k in297try298let m = ZbitInt.mask_int len in299let xa = monome d a in300let x = if off >= 0 then int_shift_right off xa else int_shift_left (- off) xa in301let cm = int_cst m in302let low = int_logand x cm in303let sb = int_scalar b in304let high = int_logand sb (int_lognot cm) in305let t = int_logor low high in306let lemma ok (_:unit) : unit307requires { live d }308ensures { ienv d r = ivalue t (ienv d) }309= let ea = ienv d a in310let s = if ienv d b < 0 then -1 else 0 in311assert { ivalue x (ienv d) = Zbit.asr ea off };312assert { ivalue cm (ienv d) = m };313assert { ivalue low (ienv d) = Zbit.land (Zbit.asr ea off) m };314assert { ivalue sb (ienv d) = s };315assert { ivalue high (ienv d) = Zbit.land s (Zbit.lnot m) };316let v = Zbit.lor (Zbit.land (Zbit.asr ea off) m) (Zbit.land s (Zbit.lnot m)) in317assert { ivalue t (ienv d) = v };318scalar_bits s (Zbit.bittest ea k);319let lemma bit (i:int) : unit320requires { 0 <= i }321ensures { Zbit.bittest v i <-> Zbit.bittest (BitsSpec.signed_extract off len ea) i }322= BitsSpec.bit_signed_extract off len ea i;323BitsSpec.mask_field len i in324Zbit.ext_bittest v (BitsSpec.signed_extract off len ea) in325assume_equality d r t326with Unsupported -> () | Overflow -> () end327end328
The bit k of a is the scalar of r: a = (a land lnot 2^k) lor (scalar r land 2^k)
Valid (2.5s) (colibri2 21) (cvc4 9) (cvc5) (split_vc 17) (depth 4)let partial testbit (d:env) (r a:Node.t) (k:int) : unit332requires { live d -> is_testbit d r a k }333raises { Contradiction -> not live d }334raises { Unsupported -> false }335raises { Overflow -> false }336= if 0 <= k <= 0x100000 then begin337let bit = ZbitInt.lsl_int 1 k in338try339let x = monome d a in340let cnb = int_cst (Zbit.lnot bit) in341let cb = int_cst bit in342let sr = int_scalar r in343let low = int_logand x cnb in344let high = int_logand sr cb in345let t = int_logor low high in346let lemma ok (_:unit) : unit347requires { live d }348ensures { ienv d a = ivalue t (ienv d) }349= let ea = ienv d a in350let s = if ienv d r < 0 then -1 else 0 in351assert { ivalue x (ienv d) = ea };352assert { ivalue cnb (ienv d) = Zbit.lnot bit };353assert { ivalue cb (ienv d) = bit };354assert { ivalue sr (ienv d) = s };355assert { ivalue low (ienv d) = Zbit.land ea (Zbit.lnot bit) };356assert { ivalue high (ienv d) = Zbit.land s bit };357let v = Zbit.lor (Zbit.land ea (Zbit.lnot bit)) (Zbit.land s bit) in358assert { ivalue t (ienv d) = v };359scalar_bits s (Zbit.bittest ea k);360pow_bits k;361let lemma b (i:int) : unit362requires { 0 <= i }363ensures { Zbit.bittest v i <-> Zbit.bittest ea i }364= () in365Zbit.ext_bittest v ea in366assume_equality d a t367with Unsupported -> () | Overflow -> () end368end369
When the value v of the Boolean node r is known: its scalar is its value, and the bit k of a is v
Valid (1.3s) (colibri2 105) (cvc4 9) (split_vc 10) (depth 4)let partial testbit_value (d:env) (r a:Node.t) (k:int) (v:bool) : unit373requires { live d -> is_testbit d r a k }374requires { has_bool d r v }375raises { Contradiction -> not live d }376= (* the scalar of [r] is its value *)377let x = int_monome r in378let sr = int_scalar r in379let s = int_lognot sr in380let t = if v then int_logor x s else int_logand x s in381let lemma ok_r (_:unit) : unit382requires { live d }383ensures { ienv d r = ivalue t (ienv d) }384= let er = ienv d r in385assert { er = if v then -1 else 0 };386assert { ivalue x (ienv d) = er };387assert { ivalue sr (ienv d) = er };388assert { ivalue s (ienv d) = Zbit.lnot er };389scalar_bits er v;390let lemma bit (i:int) : unit391requires { 0 <= i }392ensures { Zbit.bittest (Zbit.lnot er) i <-> not v }393= () in394let w = if v then Zbit.lor er (Zbit.lnot er) else Zbit.land er (Zbit.lnot er) in395assert { ivalue t (ienv d) = w };396let lemma b (i:int) : unit397requires { 0 <= i }398ensures { Zbit.bittest w i <-> Zbit.bittest er i }399= () in400Zbit.ext_bittest w er in401assume_equality d r t;402(* the bit [k] of [a] *)403if 0 <= k <= 0x100000 then begin404let bit = ZbitInt.lsl_int 1 k in405try406let xa = monome d a in407let c = if v then int_cst bit else int_cst (Zbit.lnot bit) in408let ta = if v then int_logor xa c else int_logand xa c in409let lemma ok_a (_:unit) : unit410requires { live d }411ensures { ienv d a = ivalue ta (ienv d) }412= let ea = ienv d a in413assert { ivalue xa (ienv d) = ea };414assert { ivalue c (ienv d) = if v then bit else Zbit.lnot bit };415pow_bits k;416let w = if v then Zbit.lor ea bit else Zbit.land ea (Zbit.lnot bit) in417assert { ivalue ta (ienv d) = w };418assert { Zbit.bittest ea k <-> v };419let lemma b (i:int) : unit420requires { 0 <= i }421ensures { Zbit.bittest w i <-> Zbit.bittest ea i }422= () in423Zbit.ext_bittest w ea in424assume_equality d a ta425with Unsupported -> () | Overflow -> () end426end427
A bit–vector node of size n has the term bv_monome n a (its bits 0..n-1, without tail); the result is a term without tail, whose integer value is its bounded value (value_untailed). A size too big for the BDD gives no equation.
The bits of bv n x from n are zero
Valid (825ms) (colibri2)let ghost bv_high (n x:int) : unit437requires { 0 <= n }438ensures { forall i. n <= i -> not (Zbit.bittest (bv n x) i) }439ensures { forall i. 0 <= i < n -> (Zbit.bittest (bv n x) i <-> Zbit.bittest x i) }440= ()441
z_extract y 0 n is y when the bits of y from n are zero
Valid (174ms) (colibri2)let ghost extract0 (y n:int) : unit444requires { 0 <= n }445requires { forall i. n <= i -> not (Zbit.bittest y i) }446ensures { z_extract y 0 n = y }447= {proof…} let lemma bit (i:int) : unit448requires { 0 <= i }449ensures { Zbit.bittest (z_extract y 0 n) i <-> Zbit.bittest y i }450= Zbit.def_asr y 0 i in451Zbit.ext_bittest (z_extract y 0 n) y {qed}452
sbv_to_int
Valid (891ms) (colibri2 5) (cvc5) (split_vc) (depth 1)let ghost sbv2int_spec (s x:int) : unit455ensures { signed s x = BitsSpec.signed_extract 0 s x }456= {proof…} if s > 0 then begin457bv_high s x;458let lemma bit (i:int) : unit459requires { 0 <= i }460ensures { Zbit.bittest (z_extract (bv s x) 0 s) i <-> Zbit.bittest (BitsSpec.extract 0 s x) i }461= Zbit.def_asr (bv s x) 0 i; Zbit.def_asr x 0 i in462Zbit.ext_bittest (z_extract (bv s x) 0 s) (BitsSpec.extract 0 s x)463end {qed}464
The values of the SMT–LIB bit–vector operators used by the rules: the results of the bv_* functions of colibrilib.bddbitv.Export
function bv_spec (b:builtin) (x o:int) : int =468match b with469| BvXor n -> Zbit.lxor (bv n x) (bv n o)470| BvNot n -> Zbit.land (Zbit.lnot (bv n x)) (Zbit.mask n)471| BvExtract n lo hi -> Zbit.land (Zbit.asr (bv n x) lo) (Zbit.mask (hi - lo + 1))472| BvSignExtend n k -> Zbit.land (S.sext n (bv n x)) (Zbit.mask (n + k))473| BvRotr n i -> S.rotr n (E.mod i n) (bv n x)474| BvRotl n i -> S.rotr n (E.mod (- i) n) (bv n x)475| BvShl n -> Zbit.land (Zbit.lsl (bv n x) o) (Zbit.mask n)476| BvLshr n -> Zbit.asr (Zbit.land (bv n x) (Zbit.mask n)) o477| BvAshr n -> Zbit.land (Zbit.asr (S.sext n (bv n x)) o) (Zbit.mask n)478| _ -> 0479end480
bvxor
Valid (240ms) (cvc5)let ghost xor_spec (n x y:int) : unit483requires { 0 <= n }484ensures { z_extract (Zbit.lxor (bv n x) (bv n y)) 0 n = bv_spec (BvXor n) x y }485= bv_high n x; bv_high n y; extract0 (Zbit.lxor (bv n x) (bv n y)) n486
bvnot
Valid (66ms) (colibri2)let ghost not_spec (n x:int) : unit489requires { 1 <= n }490ensures { z_extract (Zbit.lnot (bv n x)) 0 n = bv_spec (BvNot n) x 0 }491= ()492
extract
Valid (334ms) (colibri2)let ghost extract_spec (n lo hi x:int) : unit495requires { lo <= hi }496ensures { z_extract (bv n x) lo (hi - lo + 1) = bv_spec (BvExtract n lo hi) x 0 }497= ()498
sign_extend
Valid (1.8s) (colibri2 8) (cvc5) (split_vc 3) (depth 3)let ghost sign_extend_spec (n k x:int) : unit501requires { 1 <= n /\ 0 <= k }502ensures { (let a = bv n x in503if Zbit.bittest a (n - 1) then z_extract (Zbit.lor (Zbit.lsl (-1) n) a) 0 (n + k)504else a) = bv_spec (BvSignExtend n k) x 0 }505= {proof…} let a = bv n x in506bv_high n x;507let w = if Zbit.bittest a (n - 1) then z_extract (Zbit.lor (Zbit.lsl (-1) n) a) 0 (n + k)508else a in509let lemma bit (i:int) : unit510requires { 0 <= i }511ensures { Zbit.bittest w i <-> Zbit.bittest (bv_spec (BvSignExtend n k) x 0) i }512= Zbit.def_asr (Zbit.lor (Zbit.lsl (-1) n) a) 0 i;513Zbit.def_asr (-1) (- n) i;514if i >= n then SafeBits.minus_one_bits (i - n) in515Zbit.ext_bittest w (bv_spec (BvSignExtend n k) x 0) {qed}516
rotate_right
Valid (1.1s) (colibri2 10) (split_vc) (depth 1)let ghost rotr_spec (n i x:int) : unit519requires { 1 <= n /\ 0 <= i }520ensures { (let a = bv n x in let k = C.mod i n in521z_extract (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 n)522= bv_spec (BvRotr n i) x 0 }523= {proof…} let a = bv n x in524let k = C.mod i n in525assert { k = E.mod i n /\ 0 <= k < n };526bv_high n x;527let w = z_extract (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 n in528let lemma bit (p:int) : unit529requires { 0 <= p }530ensures { Zbit.bittest w p <-> Zbit.bittest (S.rotr n k a) p }531= Zbit.def_asr (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 p;532Zbit.def_asr a k p;533Zbit.def_asr a (k - n) p;534if p + k - n < 0 then Zbit.bittest_neg a (p + k - n) in535Zbit.ext_bittest w (S.rotr n k a) {qed}536
rotate_left
Valid (1.4s) (colibri2 21) (cvc5 5) (split_vc 3) (depth 2)let ghost rotl_spec (n i x:int) : unit539requires { 1 <= n /\ 0 <= i }540ensures { C.mod i n = 0 -> z_extract (bv n x) 0 n = bv_spec (BvRotl n i) x 0 }541ensures { C.mod i n <> 0 ->542z_extract (Zbit.lor (Zbit.lsl (bv n x) (C.mod i n))543(z_extract (bv n x) (n - C.mod i n) (C.mod i n))) 0 n544= bv_spec (BvRotl n i) x 0 }545= {proof…} let a = bv n x in546let k = C.mod i n in547assert { k = E.mod i n /\ 0 <= k < n };548bv_high n x;549if k = 0 then begin550assert { E.mod (- i) n = 0 };551extract0 a n;552let lemma bit (p:int) : unit553requires { 0 <= p }554ensures { Zbit.bittest a p <-> Zbit.bittest (S.rotr n 0 a) p }555= () in556Zbit.ext_bittest a (S.rotr n 0 a);557assert { bv_spec (BvRotl n i) x 0 = S.rotr n 0 a }558end else begin559assert { i = E.div i n * n + k };560assert { E.div (- i) n = - E.div i n - 1561by (- E.div i n - 1) * n <= - i < (- E.div i n - 1) * n + n };562let ghost q = E.div i n in563assert { n * (- q - 1) = - (n * q) - n };564assert { n * E.div (- i) n = - (n * q) - n };565assert { E.mod (- i) n = n - k566by E.mod (- i) n = - i - n * E.div (- i) n567so n * E.div (- i) n = - (n * E.div i n) - n };568let w = z_extract (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k)) 0 n in569let lemma bit (p:int) : unit570requires { 0 <= p }571ensures { Zbit.bittest w p <-> Zbit.bittest (S.rotr n (n - k) a) p }572= Zbit.def_asr (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k)) 0 p;573Zbit.def_asr a (- k) p;574Zbit.def_asr a (n - k) p;575if p - k < 0 then Zbit.bittest_neg a (p - k) in576Zbit.ext_bittest w (S.rotr n (n - k) a);577assert { bv_spec (BvRotl n i) x 0 = S.rotr n (n - k) a }578end {qed}579
signed_bitv is the sign extension of the BDD
Valid (644ms) (colibri2)let ghost signed_sext (n x:int) : unit582requires { 1 <= n }583ensures { signed n x = S.sext n (bv n x) }584= {proof…} let a = bv n x in585bv_high n x;586Zbit.asr_eq a;587let lemma bit (i:int) : unit588requires { 0 <= i }589ensures { Zbit.bittest (Zbit.land a (Zbit.mask n)) i <-> Zbit.bittest a i }590= () in591Zbit.ext_bittest (Zbit.land a (Zbit.mask n)) a {qed}592
bvshl, bvlshr, bvashr, for a shift 0 <= o < 2^n
Valid (2.7s) (colibri2 32) (cvc4 3) (cvc5 9) (split_vc 20) (depth 5)let ghost shift_spec (op:builtin) (n x o:int) : unit595requires { op = BvShl n \/ op = BvLshr n \/ op = BvAshr n }596requires { 1 <= n /\ 0 <= o < Zbit.lsl 1 n }597ensures { bv n o = o }598ensures { match op with599| BvShl _ -> (if n <= o then 0 else z_extract (Zbit.lsl (bv n x) o) 0 n)600| BvLshr _ -> (if n <= o then 0 else z_extract (Zbit.asr (bv n x) o) 0 n)601| _ -> z_extract (Zbit.asr (z_signed_extract (bv n x) 0 n) (if n <= o then n else o)) 0 n602end = bv_spec op x o }603= {proof…} high_zero o n;604let lemma bo (i:int) : unit605requires { 0 <= i }606ensures { Zbit.bittest (bv n o) i <-> Zbit.bittest o i }607= () in608Zbit.ext_bittest (bv n o) o;609let a = bv n x in610bv_high n x;611signed_sext n x;612assert { z_signed_extract a 0 n = S.sext n a };613let w = match op with614| BvShl _ -> (if n <= o then 0 else z_extract (Zbit.lsl a o) 0 n)615| BvLshr _ -> (if n <= o then 0 else z_extract (Zbit.asr a o) 0 n)616| _ -> z_extract (Zbit.asr (z_signed_extract a 0 n) (if n <= o then n else o)) 0 n617end in618let lemma bit (p:int) : unit619requires { 0 <= p }620ensures { Zbit.bittest w p <-> Zbit.bittest (bv_spec op x o) p }621= Zbit.def_asr a (- o) p;622Zbit.def_asr a o p;623Zbit.def_asr (Zbit.land a (Zbit.mask n)) o p;624Zbit.def_asr (Zbit.lsl a o) 0 p;625Zbit.def_asr (Zbit.asr a o) 0 p;626Zbit.def_asr (S.sext n a) o p;627Zbit.def_asr (z_signed_extract a 0 n) (if n <= o then n else o) p;628Zbit.def_asr (Zbit.asr (z_signed_extract a 0 n) (if n <= o then n else o)) 0 p;629Zbit.def_asr a 0 (p + o);630Zbit.def_asr a 0 (p + n);631Zbit.def_asr a 0 (n - 1);632if p - o < 0 then Zbit.bittest_neg a (p - o) in633Zbit.ext_bittest w (bv_spec op x o) {qed}634
r = a op b, op one of bvand, bvor, bvxor
Valid (2.9s) (colibri2 26) (split_vc 8) (depth 3)let partial bv_binop (d:env) (r a b:Node.t) (n:int) (op:builtin) : unit637requires { op = BvAnd n \/ op = BvOr n \/ op = BvXor n }638requires { live d -> ienv d r = meaning d op (Cons a (Cons b Nil)) }639raises { Contradiction -> not live d }640= if 0 <= n <= 0x100000 then641try642let sz = Int63.of_int n in643let ta = bv_monome sz a in644let tb = bv_monome sz b in645let t = match op with646| BvAnd _ -> bv_logand ta tb647| BvOr _ -> bv_logor ta tb648| _ -> bv_xor ta tb649end in650let lemma ok (_:unit) : unit651requires { live d }652ensures { ienv d r = ivalue t (ienv d) }653= assert { meaning d op (Cons a (Cons b Nil))654= code op (Cons (ienv d a) (Cons (ienv d b) Nil)) };655(match op with656| BvXor _ -> xor_spec n (pure { ienv d a }) (pure { ienv d b })657| _ -> () end);658value_untailed t (pure { ienv d }) in659assume_equality d r t660with Unsupported -> () | Overflow -> () end661
r = op a, op one of bvnot, extract, sign_extend, rotate_left, rotate_right
Valid (2.4s) (colibri2 120) (cvc4) (cvc5 9) (split_vc 20) (depth 5)let partial bv_unop (d:env) (r a:Node.t) (op:builtin) : unit665requires { match op with666| BvNot _ | BvExtract _ _ _ | BvSignExtend _ _ | BvRotl _ _ | BvRotr _ _ -> true667| _ -> false end }668requires { live d -> ienv d r = meaning d op (Cons a Nil) }669raises { Contradiction -> not live d }670= let n = match op with671| BvNot n | BvExtract n _ _ | BvSignExtend n _ | BvRotl n _ | BvRotr n _ -> n672| _ -> absurd end in673if 0 < n <= 0x100000 then674try675let sz = Int63.of_int n in676let ta = bv_monome sz a in677let t = match op with678| BvNot _ -> bv_lognot sz ta679| BvExtract _ lo hi ->680if 0 <= lo <= hi <= 0x100000 then681bv_extract (Int63.of_int lo) (Int63.of_int hi) ta682else raise Unsupported683| BvSignExtend _ k ->684if 0 <= k <= 0x100000 then bv_sign_extend sz (Int63.of_int (n + k)) ta685else raise Unsupported686| BvRotr _ i ->687if 0 <= i <= 0x100000 then bv_rotate_right (Int63.of_int i) sz ta688else raise Unsupported689| BvRotl _ i ->690if 0 <= i <= 0x100000 then bv_rotate_left (Int63.of_int i) sz ta691else raise Unsupported692| _ -> absurd693end in694let lemma ok (_:unit) : unit695requires { live d }696ensures { ienv d r = ivalue t (ienv d) }697= let ghost x = pure { ienv d a } in698assert { meaning d op (Cons a Nil) = code op (Cons x Nil) };699value_untailed t (pure { ienv d });700(match op with701| BvNot _ -> not_spec n x702| BvExtract _ lo hi -> extract_spec n lo hi x703| BvSignExtend _ k -> sign_extend_spec n k x;704assert { code op (Cons x Nil) = bv_spec op x 0 };705assert { value ta (ienv d) = bv n x };706assert { value t (ienv d) = Zbit.land (S.sext n (bv n x)) (Zbit.mask (n + k)) };707assert { ivalue t (ienv d) = bv_spec op x 0 }708| BvRotr _ i -> rotr_spec n i x709| BvRotl _ i -> rotl_spec n i x;710assert { code op (Cons x Nil) = bv_spec op x 0 };711assert { value ta (ienv d) = bv n x };712assert { value t (ienv d) = S.rotr n (E.mod (- i) n) (bv n x) };713assert { ivalue t (ienv d) = bv_spec op x 0 }714| _ -> () end) in715assume_equality d r t716with Unsupported -> () | Overflow -> () end717
r = op a off, op one of bvshl, bvlshr, bvashr, the shift o of value off; no equation unless 0 <= off < 2^n (true in a model)
Valid (1.7s) (colibri2 33) (cvc5) (split_vc 9) (depth 4)let partial bv_shift (d:env) (r a o:Node.t) (n off:int) (op:builtin) : unit721requires { op = BvShl n \/ op = BvLshr n \/ op = BvAshr n }722requires { live d -> ienv d o = off }723requires { live d -> ienv d r = meaning d op (Cons a (Cons o Nil)) }724raises { Contradiction -> not live d }725= if 0 < n <= 0x100000 && 0 <= off && Zbit.numbits off <= n then726try727let sz = Int63.of_int n in728let ta = bv_monome sz a in729let t = match op with730| BvShl _ -> bv_shift_left off sz ta731| BvLshr _ -> bv_shift_right off sz ta732| _ -> bv_arith_shift_right off sz ta733end in734let lemma ok (_:unit) : unit735requires { live d }736ensures { ienv d r = ivalue t (ienv d) }737= assert { off < Zbit.lsl 1 n738by Zbit.lsl 1 n <= off -> n + 1 = Zbit.numbits (Zbit.lsl 1 n) <= Zbit.numbits off };739assert { meaning d op (Cons a (Cons o Nil))740= code op (Cons (ienv d a) (Cons (ienv d o) Nil)) };741shift_spec op n (pure { ienv d a }) off;742value_untailed t (pure { ienv d }) in743assume_equality d r t744with Unsupported -> () | Overflow -> () end745end746