library colibrilib.known_bits — module KnownBitsThe domain of known bits of an integer (two's complement, infinitely many bits). A record with fields l and u stands for the integers x with u ⊆ x ⊆ l bitwise: l holds the bits that may be 1 and u the bits that must be 1. The domain is empty when u ⊄ l.
Every exported function is total. mem is the concretization. Bitwise operations are exact (they give the smallest element of the domain containing the image), inter is exact and union is the smallest element containing the union. Among the operations that move bits, shiftright, extract and update are exact as well, and signedextract is only sound.
module KnownBits12use int.Int13use int.MinMax14use colibrilib.zarith.Zbit15use colibrilib.zbit.ZbitInt16use option.Option17use colibrilib.safe_bits.BitsSpec18use colibrilib.safe_bits.SafeBits19use colibrilib.spec.Sound2021type t = { l : int; u : int } Valid (62ms) (colibri2)22invariant { Zbit.subset u l }23by { l = -1; u = 0 }24type kind = One | Zero | Unknown2526predicate mem (x:int) (a:t) = Zbit.subset a.u x /\ Zbit.subset x a.l27Valid (61ms) (colibri2)28let lemma subset_pos (a b:int) : unit29requires { forall i. 0 <= i -> Zbit.bittest a i -> Zbit.bittest b i }30ensures { Zbit.subset a b }31= ()32
t is never empty
Valid (62ms) (colibri2)let lemma exists_mem (a:t) : unit35ensures { mem a.u a /\ mem a.l a }36= ()37
mem in terms of the bits
Valid (54ms) (colibri2)let lemma mem_bits (x:int) (a:t) (i:int) : unit40requires { mem x a }41requires { 0 <= i }42ensures { Zbit.bittest a.u i -> Zbit.bittest x i }43ensures { Zbit.bittest x i -> Zbit.bittest a.l i }44= ()45Valid (67ms) (colibri2)46let lemma mem_of_bits (x:int) (a:t) : unit47requires { forall i. 0 <= i -> Zbit.bittest a.u i -> Zbit.bittest x i }48requires { forall i. 0 <= i -> Zbit.bittest x i -> Zbit.bittest a.l i }49ensures { mem x a }50= ()51
the invariant, bit by bit
Valid (126ms) (colibri2)let lemma inv_bit (a:t) (i:int) : unit54requires { 0 <= i }55ensures { Zbit.bittest a.u i -> Zbit.bittest a.l i }56= ()57Valid (56ms) (colibri2)58let constant top : t = { l = -1; u = 0 }59Valid (85ms) (colibri2)60let lemma top_all (x:int) : unit61ensures { mem x top }62= let lemma b (i:int) : unit63requires { 0 <= i }64ensures { Zbit.bittest x i -> Zbit.bittest top.l i }65= SafeBits.minus_one_bits i in66()67Valid (82ms) (cvc5)68let lemma is_top_iff (a:t) : unit69ensures { (a.l = -1 /\ a.u = 0) <-> (forall x. mem x a) }70= if a.l = -1 && a.u = 0 then begin71let lemma all (x:int) : unit ensures { mem x a } = top_all x in ()72end else if pure { forall x. mem x a } then begin73let lemma l_bit (i:int) : unit74requires { 0 <= i }75ensures { Zbit.bittest a.l i <-> Zbit.bittest (-1) i }76= SafeBits.minus_one_bits i in77let lemma u_bit (i:int) : unit78requires { 0 <= i }79ensures { Zbit.bittest a.u i <-> Zbit.bittest 0 i }80= () in81Zbit.ext_bittest a.l (-1);82Zbit.ext_bittest a.u 083end84
a contains all the integers
Valid (77ms) (colibri2)let is_top (a:t) : bool87ensures { result <-> forall x. mem x a }88= a.l = -1 && a.u = 089
The single integer a
Valid (94ms) (colibri2)let cst (a:int) : t92ensures { exact mem (fun x -> x = a) result }93= let r = { l = a; u = a } in94let lemma back (x:int) : unit95requires { mem x r }96ensures { x = a }97= Zbit.ext_bittest x a in98r99
The integers that have the bits of a on the positions of mask
Valid (404ms) (colibri2 11) (cvc4) (split_vc) (depth 1)let cst_mask (a mask:int) : t102ensures { exact mem (fun x -> forall i. 0 <= i -> Zbit.bittest mask i ->103(Zbit.bittest x i <-> Zbit.bittest a i)) result }104= let rl = Zbit.lor a (Zbit.lnot mask) in105let ru = Zbit.land a mask in106let lemma bit (i:int) : unit107requires { 0 <= i }108ensures { Zbit.bittest ru i -> Zbit.bittest rl i }109= () in110let r = { l = rl; u = ru } in111let lemma fwd (x:int) : unit112requires { mem x r }113ensures { forall i. 0 <= i -> Zbit.bittest mask i ->114(Zbit.bittest x i <-> Zbit.bittest a i) }115= let lemma b (i:int) : unit116requires { 0 <= i } requires { Zbit.bittest mask i }117ensures { Zbit.bittest x i <-> Zbit.bittest a i }118= mem_bits x r i in119() in120let lemma bwd (x:int) : unit121requires { forall i. 0 <= i -> Zbit.bittest mask i ->122(Zbit.bittest x i <-> Zbit.bittest a i) }123ensures { mem x r }124= let lemma bu (i:int) : unit125requires { 0 <= i } ensures { Zbit.bittest r.u i -> Zbit.bittest x i }126= () in127let lemma bl (i:int) : unit128requires { 0 <= i } ensures { Zbit.bittest x i -> Zbit.bittest r.l i }129= () in130mem_of_bits x r in131r132
The intersection of the concretizations is exact; None is the empty intersection
Valid (333ms) (colibri2 13) (cvc4 2) (cvc5) (split_vc 2) (depth 2)let inter (a b:t) : option t136ensures { exact_opt mem (fun x -> mem x a /\ mem x b) result }137= let rl = Zbit.land a.l b.l in138let ru = Zbit.lor a.u b.u in139let d = Zbit.land ru (Zbit.lnot rl) in140let lemma d_bit (i:int) : unit141requires { 0 <= i }142ensures { Zbit.bittest d i <-> (Zbit.bittest ru i /\ not (Zbit.bittest rl i)) }143= () in144if d <> 0 then begin145let lemma empty (x:int) : unit146requires { mem x a /\ mem x b }147ensures { false }148= let lemma bit (i:int) : unit149requires { 0 <= i }150ensures { Zbit.bittest ru i -> Zbit.bittest rl i }151= mem_bits x a i; mem_bits x b i in152Zbit.ext_bittest d 0 in153assert { forall x. (mem x a /\ mem x b) <-> false };154None155end else begin156Zbit.ext_bittest d 0;157let lemma sub (i:int) : unit158requires { 0 <= i }159ensures { Zbit.bittest ru i -> Zbit.bittest rl i }160= () in161let r = { l = rl; u = ru } in162assert { forall x. (mem x a /\ mem x b) <-> mem x r };163Some r164end165
Introduction of join mem, in a small context: the provers are slow on the closure of mem
Valid (2.9s) (cvc5) (split_vc) (depth 1)let ghost join_mem (a b r: t) : unit169requires { forall x. mem x a \/ mem x b -> mem x r }170requires { forall c. (forall x. mem x a -> mem x c) ->171(forall x. mem x b -> mem x c) -> forall x. mem x r -> mem x c }172ensures { join mem a b r }173= ()174
The smallest element containing the union of two elements
Valid (396ms) (colibri2 15) (cvc5 5) (split_vc) (depth 1)let union (a b:t) : t177ensures { join mem a b result }178= let rl = Zbit.lor a.l b.l in179let ru = Zbit.land a.u b.u in180let lemma sub (i:int) : unit181requires { 0 <= i }182ensures { Zbit.bittest ru i -> Zbit.bittest rl i }183= () in184let r = { l = rl; u = ru } in185let lemma lub (c:t) : unit186requires { forall x. mem x a -> mem x c }187requires { forall x. mem x b -> mem x c }188ensures { forall x. mem x r -> mem x c }189= exists_mem a; exists_mem b;190assert { mem a.u c /\ mem a.l c /\ mem b.u c /\ mem b.l c };191let lemma mem_r (x:int) : unit192requires { mem x r }193ensures { mem x c }194= let lemma bit (i:int) : unit195requires { 0 <= i }196ensures { Zbit.bittest c.u i -> Zbit.bittest x i }197ensures { Zbit.bittest x i -> Zbit.bittest c.l i }198= mem_bits a.u c i; mem_bits a.l c i; mem_bits b.u c i; mem_bits b.l c i;199mem_bits x r i in200() in201() in202join_mem a b r;203r204
The element whose bits that may be 1 are known0 and bits that must be 1 are known1; None if some bit must be 1 and cannot be 1
Valid (125ms) (colibri2 6) (split_vc) (depth 1)let mk (known0 known1:int) : option t208ensures { match result with209| None -> not (Zbit.subset known1 known0)210| Some r -> r.l = known0 /\ r.u = known1211end }212= let d = Zbit.land known1 (Zbit.lnot known0) in213let lemma d_bit (i:int) : unit214requires { 0 <= i }215ensures { Zbit.bittest d i <-> (Zbit.bittest known1 i /\ not (Zbit.bittest known0 i)) }216= () in217if d <> 0 then begin218if pure { Zbit.subset known1 known0 } then Zbit.ext_bittest d 0;219None220end else begin221let lemma sub (i:int) : unit222requires { 0 <= i }223ensures { Zbit.bittest known1 i -> Zbit.bittest known0 i }224= () in225Zbit.ext_bittest d 0;226Some { l = known0; u = known1 }227end228
Exact: x is in a iff lnot x is in the result
Valid (463ms) (colibri2 14) (cvc4) (cvc5) (split_vc 2) (depth 2)let lognot (a:t) : t231ensures { forall x. mem (Zbit.lnot x) result <-> mem x a }232ensures { sound1 mem Zbit.lnot a result }233ensures { complete1 mem Zbit.lnot a result }234= let rl = Zbit.lnot a.u in235let ru = Zbit.lnot a.l in236let lemma sub (i:int) : unit237requires { 0 <= i }238ensures { Zbit.bittest ru i -> Zbit.bittest rl i }239= inv_bit a i in240let r = { l = rl; u = ru } in241let lemma ln (x:int) : unit242ensures { mem (Zbit.lnot x) r <-> mem x a }243= let lemma bit (i:int) : unit244requires { 0 <= i }245ensures { Zbit.bittest r.u i <-> not (Zbit.bittest a.l i) }246ensures { Zbit.bittest r.l i <-> not (Zbit.bittest a.u i) }247ensures { Zbit.bittest (Zbit.lnot x) i <-> not (Zbit.bittest x i) }248= () in249() in250let lemma back (s:int) : unit251requires { mem s r }252ensures { exists x. mem x a /\ s = Zbit.lnot x }253= let ghost x = pure { Zbit.lnot s } in254ln x;255Zbit.ext_bittest s (pure { Zbit.lnot x });256assert { mem x a /\ s = Zbit.lnot x } in257assert { sound1 mem Zbit.lnot a r };258assert { complete1 mem Zbit.lnot a r };259r260
Exact: every element of the result is the land of an element of a and of an element of b
Valid (406ms) (colibri2 18) (cvc4 2) (cvc5 3) (split_vc) (depth 1)let logand (a b:t) : t264ensures { sound2 mem Zbit.land a b result }265ensures { complete2 mem Zbit.land a b result }266= let rl = Zbit.land a.l b.l in267let ru = Zbit.land a.u b.u in268let lemma sub (i:int) : unit269requires { 0 <= i }270ensures { Zbit.bittest ru i -> Zbit.bittest rl i }271= inv_bit a i; inv_bit b i in272let r = { l = rl; u = ru } in273let lemma sound (x y:int) : unit274requires { mem x a /\ mem y b }275ensures { mem (Zbit.land x y) r }276= let lemma bit (i:int) : unit277requires { 0 <= i }278ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.land x y) i }279ensures { Zbit.bittest (Zbit.land x y) i -> Zbit.bittest r.l i }280= mem_bits x a i; mem_bits y b i in () in281let lemma exact (z:int) : unit282requires { mem z r }283ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.land x y }284= let x = Zbit.lor a.u z in285let y = Zbit.lor b.u z in286let lemma bit (i:int) : unit287requires { 0 <= i }288ensures { Zbit.bittest (Zbit.land x y) i <-> Zbit.bittest z i }289ensures { Zbit.bittest a.u i -> Zbit.bittest x i }290ensures { Zbit.bittest x i -> Zbit.bittest a.l i }291ensures { Zbit.bittest b.u i -> Zbit.bittest y i }292ensures { Zbit.bittest y i -> Zbit.bittest b.l i }293= mem_bits z r i in294Zbit.ext_bittest (Zbit.land x y) z;295assert { mem x a /\ mem y b /\ z = Zbit.land x y } in296r297
Exact
Valid (524ms) (colibri2 16) (cvc4 3) (cvc5 4) (split_vc) (depth 1)let logor (a b:t) : t300ensures { sound2 mem Zbit.lor a b result }301ensures { complete2 mem Zbit.lor a b result }302= let rl = Zbit.lor a.l b.l in303let ru = Zbit.lor a.u b.u in304let lemma sub (i:int) : unit305requires { 0 <= i }306ensures { Zbit.bittest ru i -> Zbit.bittest rl i }307= inv_bit a i; inv_bit b i in308let r = { l = rl; u = ru } in309let lemma sound (x y:int) : unit310requires { mem x a /\ mem y b }311ensures { mem (Zbit.lor x y) r }312= let lemma bit (i:int) : unit313requires { 0 <= i }314ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.lor x y) i }315ensures { Zbit.bittest (Zbit.lor x y) i -> Zbit.bittest r.l i }316= mem_bits x a i; mem_bits y b i in () in317let lemma exact (z:int) : unit318requires { mem z r }319ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.lor x y }320= let x = Zbit.land z a.l in321let y = Zbit.land z b.l in322let lemma bit (i:int) : unit323requires { 0 <= i }324ensures { Zbit.bittest (Zbit.lor x y) i <-> Zbit.bittest z i }325ensures { Zbit.bittest a.u i -> Zbit.bittest x i }326ensures { Zbit.bittest x i -> Zbit.bittest a.l i }327ensures { Zbit.bittest b.u i -> Zbit.bittest y i }328ensures { Zbit.bittest y i -> Zbit.bittest b.l i }329= mem_bits z r i in330Zbit.ext_bittest (Zbit.lor x y) z;331assert { mem x a /\ mem y b /\ z = Zbit.lor x y } in332r333Valid (230ms) (colibri2)334let lemma lxor_bit (x y i:int) : unit335requires { 0 <= i }336ensures { Zbit.bittest (Zbit.lxor x y) i <-> not (Zbit.bittest x i <-> Zbit.bittest y i) }337= ()338
Exact
Valid (563ms) (colibri2 29) (cvc4 3) (cvc5 12) (split_vc 5) (depth 2)let logxor (a b:t) : t341ensures { sound2 mem Zbit.lxor a b result }342ensures { complete2 mem Zbit.lxor a b result }343= let rl = Zbit.lor (Zbit.land a.l (Zbit.lnot b.u)) (Zbit.land b.l (Zbit.lnot a.u)) in344let ru = Zbit.lor (Zbit.land a.u (Zbit.lnot b.l)) (Zbit.land b.u (Zbit.lnot a.l)) in345let lemma xbits (i:int) : unit346requires { 0 <= i }347ensures { Zbit.bittest ru i <-> ((Zbit.bittest a.u i /\ not Zbit.bittest b.l i) \/ (Zbit.bittest b.u i /\ not Zbit.bittest a.l i)) }348ensures { Zbit.bittest rl i <-> ((Zbit.bittest a.l i /\ not Zbit.bittest b.u i) \/ (Zbit.bittest b.l i /\ not Zbit.bittest a.u i)) }349= () in350let lemma sub (i:int) : unit351requires { 0 <= i }352ensures { Zbit.bittest ru i -> Zbit.bittest rl i }353= inv_bit a i; inv_bit b i in354let r = { l = rl; u = ru } in355let lemma sound (x y:int) : unit356requires { mem x a /\ mem y b }357ensures { mem (Zbit.lxor x y) r }358= let lemma bit (i:int) : unit359requires { 0 <= i }360ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.lxor x y) i }361ensures { Zbit.bittest (Zbit.lxor x y) i -> Zbit.bittest r.l i }362= mem_bits x a i; mem_bits y b i in () in363let lemma exact (z:int) : unit364requires { mem z r }365ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.lxor x y }366= let ua = Zbit.land a.l (Zbit.lnot a.u) in367let kb = Zbit.lor b.u (Zbit.lnot b.l) in368let w = Zbit.lxor z b.u in369let t = Zbit.land ua (Zbit.land kb w) in370let x = Zbit.lor a.u t in371let ub = Zbit.land b.l (Zbit.lnot b.u) in372let w2 = Zbit.lxor z x in373let y = Zbit.lor b.u (Zbit.land ub w2) in374let lemma bit (i:int) : unit375requires { 0 <= i }376ensures { Zbit.bittest (Zbit.lxor x y) i <-> Zbit.bittest z i }377ensures { Zbit.bittest a.u i -> Zbit.bittest x i }378ensures { Zbit.bittest x i -> Zbit.bittest a.l i }379ensures { Zbit.bittest b.u i -> Zbit.bittest y i }380ensures { Zbit.bittest y i -> Zbit.bittest b.l i }381= mem_bits z r i;382lxor_bit x y i; lxor_bit z b.u i; lxor_bit z x i;383assert { Zbit.bittest ua i <-> (Zbit.bittest a.l i /\ not Zbit.bittest a.u i) };384assert { Zbit.bittest kb i <-> (Zbit.bittest b.u i \/ not Zbit.bittest b.l i) };385assert { Zbit.bittest t i <-> (Zbit.bittest ua i /\ Zbit.bittest kb i /\ Zbit.bittest w i) };386assert { Zbit.bittest x i <-> (Zbit.bittest a.u i \/ Zbit.bittest t i) };387assert { Zbit.bittest ub i <-> (Zbit.bittest b.l i /\ not Zbit.bittest b.u i) };388assert { Zbit.bittest y i <-> (Zbit.bittest b.u i \/ (Zbit.bittest ub i /\ Zbit.bittest w2 i)) };389assert { Zbit.bittest r.u i <-> ((Zbit.bittest a.u i /\ not Zbit.bittest b.l i) \/ (Zbit.bittest b.u i /\ not Zbit.bittest a.l i)) };390assert { Zbit.bittest r.l i <-> ((Zbit.bittest a.l i /\ not Zbit.bittest b.u i) \/ (Zbit.bittest b.l i /\ not Zbit.bittest a.u i)) };391assert { Zbit.bittest a.u i -> Zbit.bittest a.l i };392assert { Zbit.bittest b.u i -> Zbit.bittest b.l i } in393Zbit.ext_bittest (Zbit.lxor x y) z;394assert { mem x a /\ mem y b /\ z = Zbit.lxor x y } in395r396
The value of the bit i
Valid (292ms) (colibri2)let testbit (a:t) (i:int) : kind399ensures { forall x. mem x a -> (result = One -> Zbit.bittest x i) /\400(result = Zero -> not (Zbit.bittest x i)) }401ensures { result = Unknown ->4020 <= i /\ mem a.l a /\ mem a.u a /\ Zbit.bittest a.l i /\ not (Zbit.bittest a.u i) }403= if i < 0 then begin404Zbit.bittest_neg i i;405Zero406end else begin407let bl = if i >= SafeBits.nb a.l then (SafeBits.bittest_high a.l i; a.l < 0)408else ZbitInt.test_bit_int a.l i in409let bu = if i >= SafeBits.nb a.u then (SafeBits.bittest_high a.u i; a.u < 0)410else ZbitInt.test_bit_int a.u i in411if bl && bu then One412else if not bl && not bu then Zero413else begin414exists_mem a;415inv_bit a i;416Unknown417end418end419
If the bits of r are those of a moved by the position map pos (and masked by cond), the image of mem x a is in r
Valid (180ms) (cvc4)let lemma sound_map (cond: int -> bool) (pos: int -> int) (a r: t) (x s: int) : unit423requires { forall i. 0 <= i -> (Zbit.bittest r.u i <-> (cond i /\ Zbit.bittest a.u (pos i))) }424requires { forall i. 0 <= i -> (Zbit.bittest r.l i <-> (cond i /\ Zbit.bittest a.l (pos i))) }425requires { forall i. 0 <= i -> (Zbit.bittest s i <-> (cond i /\ Zbit.bittest x (pos i))) }426requires { mem x a }427ensures { mem s r }428= let lemma bit (i:int) : unit429requires { 0 <= i }430ensures { Zbit.bittest r.u i -> Zbit.bittest s i }431ensures { Zbit.bittest s i -> Zbit.bittest r.l i }432= if 0 <= pos i then mem_bits x a (pos i)433else begin434Zbit.bittest_neg a.u (pos i); Zbit.bittest_neg x (pos i)435end in436()437Valid (144ms) (colibri2)438let lemma image_subset (cond: int -> bool) (pos: int -> int) (a: t) (rl ru: int) : unit439requires { forall i. 0 <= i -> (Zbit.bittest ru i <-> (cond i /\ Zbit.bittest a.u (pos i))) }440requires { forall i. 0 <= i -> (Zbit.bittest rl i <-> (cond i /\ Zbit.bittest a.l (pos i))) }441ensures { Zbit.subset ru rl }442= let lemma bit (i:int) : unit443requires { 0 <= i }444ensures { Zbit.bittest ru i -> Zbit.bittest rl i }445= if 0 <= pos i then inv_bit a (pos i) else Zbit.bittest_neg a.u (pos i) in446()447
Shift right (Zbit.asr), to the left if off is negative
Valid (689ms) (colibri2 29) (cvc4) (cvc5 2) (split_vc) (depth 1)let shift_right (off:int) (a:t) : t450requires { SafeBits.shift_ok off a.l /\ SafeBits.shift_ok off a.u }451ensures { sound1 mem (fun x -> Zbit.asr x off) a result }452ensures { complete1 mem (fun x -> Zbit.asr x off) a result }453= let rl = SafeBits.shift_right off a.l in454let ru = SafeBits.shift_right off a.u in455let lemma bits (x i:int) : unit456requires { 0 <= i }457ensures { Zbit.bittest ru i <-> Zbit.bittest a.u (i + off) }458ensures { Zbit.bittest rl i <-> Zbit.bittest a.l (i + off) }459ensures { Zbit.bittest (Zbit.asr x off) i <-> Zbit.bittest x (i + off) }460= () in461image_subset (fun _ -> true) (fun i -> i + off) a rl ru;462let r = { l = rl; u = ru } in463let lemma sound (x:int) : unit464requires { mem x a }465ensures { mem (Zbit.asr x off) r }466= sound_map (fun _ -> true) (fun i -> i + off) a r x (Zbit.asr x off) in467let lemma exact (s:int) : unit468requires { mem s r }469ensures { exists x. mem x a /\ s = Zbit.asr x off }470= let x = Zbit.lor (Zbit.land a.u (Zbit.mask (max off 0))) (Zbit.lsl s off) in471let lemma bit (p:int) : unit472requires { 0 <= p }473ensures { Zbit.bittest x p <-> ((p < off /\ Zbit.bittest a.u p) \/ Zbit.bittest s (p - off)) }474ensures { Zbit.bittest a.u p -> Zbit.bittest x p }475ensures { Zbit.bittest x p -> Zbit.bittest a.l p }476= BitsSpec.mask_field (max off 0) p;477inv_bit a p;478if p - off >= 0 then begin479mem_bits s r (p - off); bits 0 (p - off)480end in481let lemma back (i:int) : unit482requires { 0 <= i }483ensures { Zbit.bittest (Zbit.asr x off) i <-> Zbit.bittest s i }484= mem_bits s r i; bits 0 i;485if i + off < 0 then Zbit.bittest_neg x (i + off)486else bit (i + off) in487Zbit.ext_bittest s (Zbit.asr x off);488assert { mem x a /\ s = Zbit.asr x off } in489r490
BitsSpec.extract
Valid (1.2s) (colibri2 34) (cvc4) (split_vc) (depth 1)let extract (off len:int) (a:t) : t494requires { SafeBits.extract_ok off len a.l /\ SafeBits.extract_ok off len a.u }495ensures { sound1 mem (fun x -> BitsSpec.extract off len x) a result }496ensures { complete1 mem (fun x -> BitsSpec.extract off len x) a result }497= let rl = SafeBits.extract off len a.l in498let ru = SafeBits.extract off len a.u in499let lemma bits (x i:int) : unit500requires { 0 <= i }501ensures { Zbit.bittest ru i <-> (i < len /\ Zbit.bittest a.u (i + off)) }502ensures { Zbit.bittest rl i <-> (i < len /\ Zbit.bittest a.l (i + off)) }503ensures { Zbit.bittest (BitsSpec.extract off len x) i <-> (i < len /\ Zbit.bittest x (i + off)) }504= BitsSpec.bit_extract off len a.u i; BitsSpec.bit_extract off len a.l i;505BitsSpec.bit_extract off len x i in506image_subset (fun i -> i < len) (fun i -> i + off) a rl ru;507let r = { l = rl; u = ru } in508let lemma sound (x:int) : unit509requires { mem x a }510ensures { mem (BitsSpec.extract off len x) r }511= sound_map (fun i -> i < len) (fun i -> i + off) a r x (BitsSpec.extract off len x) in512let lemma exact (s:int) : unit513requires { mem s r }514ensures { exists x. mem x a /\ s = BitsSpec.extract off len x }515= let x = BitsSpec.update off len s a.u in516let lemma bit (p:int) : unit517requires { 0 <= p }518ensures { Zbit.bittest a.u p -> Zbit.bittest x p }519ensures { Zbit.bittest x p -> Zbit.bittest a.l p }520= BitsSpec.bit_update off len s a.u p; inv_bit a p;521if len > 0 && off <= p && p < off + len then begin522mem_bits s r (p - off); bits 0 (p - off)523end in524let lemma back (i:int) : unit525requires { 0 <= i }526ensures { Zbit.bittest (BitsSpec.extract off len x) i <-> Zbit.bittest s i }527= bits x i; mem_bits s r i;528if i < len then begin529if i + off < 0 then begin530Zbit.bittest_neg a.l (i + off); Zbit.bittest_neg x (i + off)531end else BitsSpec.bit_update off len s a.u (i + off)532end in533Zbit.ext_bittest s (BitsSpec.extract off len x);534assert { mem x a /\ s = BitsSpec.extract off len x } in535r536
Signed extraction of the specification BitsSpec. Sound but not exact: the high bits all copy the sign bit, which the domain cannot say. For the top element, offset 0 and length 1, the image is 0 and –1 but the result is top, and 1 is in top.
Valid (114ms) (colibri2 17) (split_vc) (depth 1)let signed_extract (off len:int) (a:t) : t543requires { SafeBits.signed_extract_ok off len }544ensures { sound1 mem (fun x -> BitsSpec.signed_extract off len x) a result }545= let rl = SafeBits.signed_extract off len a.l in546let ru = SafeBits.signed_extract off len a.u in547let lemma bits (x i:int) : unit548requires { 0 <= i }549ensures { Zbit.bittest ru i <-> (len > 0 /\ Zbit.bittest a.u (off + min i (len - 1))) }550ensures { Zbit.bittest rl i <-> (len > 0 /\ Zbit.bittest a.l (off + min i (len - 1))) }551ensures { Zbit.bittest (BitsSpec.signed_extract off len x) i <->552(len > 0 /\ Zbit.bittest x (off + min i (len - 1))) }553= BitsSpec.bit_signed_extract off len a.u i; BitsSpec.bit_signed_extract off len a.l i;554BitsSpec.bit_signed_extract off len x i in555image_subset (fun _ -> len > 0) (fun i -> off + min i (len - 1)) a rl ru;556let r = { l = rl; u = ru } in557let lemma sound (x:int) : unit558requires { mem x a }559ensures { mem (BitsSpec.signed_extract off len x) r }560= sound_map (fun _ -> len > 0) (fun i -> off + min i (len - 1)) a r x561(BitsSpec.signed_extract off len x) in562r563
BitsSpec.update
Valid (3.4s) (colibri2 48) (cvc5 4) (split_vc 2) (depth 2)let update (off len:int) (src dst:t) : t567requires { SafeBits.update_ok off len }568ensures { sound2 mem (fun xs xd -> BitsSpec.update off len xs xd) src dst result }569ensures { complete2 mem (fun xs xd -> BitsSpec.update off len xs xd) src dst result }570= let rl = SafeBits.update off len src.l dst.l in571let ru = SafeBits.update off len src.u dst.u in572let lemma sub (i:int) : unit573requires { 0 <= i }574ensures { Zbit.bittest ru i -> Zbit.bittest rl i }575= BitsSpec.bit_update off len src.u dst.u i; BitsSpec.bit_update off len src.l dst.l i;576if len > 0 && off <= i && i < off + len then inv_bit src (i - off) else inv_bit dst i in577let r = { l = rl; u = ru } in578let lemma bit (xs xd i:int) : unit579requires { 0 <= i }580requires { mem xs src /\ mem xd dst }581ensures { Zbit.bittest r.u i -> Zbit.bittest (BitsSpec.update off len xs xd) i }582ensures { Zbit.bittest (BitsSpec.update off len xs xd) i -> Zbit.bittest r.l i }583= BitsSpec.bit_update off len src.u dst.u i; BitsSpec.bit_update off len src.l dst.l i;584BitsSpec.bit_update off len xs xd i;585if len > 0 && off <= i && i < off + len then mem_bits xs src (i - off)586else mem_bits xd dst i in587let lemma exact (s:int) : unit588requires { mem s r }589ensures { exists xs xd. mem xs src /\ mem xd dst /\ s = BitsSpec.update off len xs xd }590= let xs1 = BitsSpec.update 0 len (BitsSpec.extract off len s) src.u in591let xs = BitsSpec.update 0 (max (- off) 0) src.u xs1 in592let xd = BitsSpec.update off len (Zbit.asr dst.u off) s in593let lemma xbits (p:int) : unit594requires { 0 <= p }595ensures { Zbit.bittest xs1 p <-> (if len > 0 /\ p < len then Zbit.bittest s (p + off) else Zbit.bittest src.u p) }596ensures { Zbit.bittest xs p <-> (if p < max (- off) 0 then Zbit.bittest src.u p else Zbit.bittest xs1 p) }597ensures { Zbit.bittest xd p <-> (if len > 0 /\ off <= p < off + len then Zbit.bittest dst.u p else Zbit.bittest s p) }598= BitsSpec.bit_update 0 len (BitsSpec.extract off len s) src.u p;599BitsSpec.bit_extract off len s p;600BitsSpec.bit_update 0 (max (- off) 0) src.u xs1 p;601BitsSpec.bit_update off len (Zbit.asr dst.u off) s p in602let lemma src_bits (i:int) : unit603requires { 0 <= i }604ensures { Zbit.bittest src.u i -> Zbit.bittest xs i }605ensures { Zbit.bittest xs i -> Zbit.bittest src.l i }606= xbits i; inv_bit src i;607if i >= max (- off) 0 && len > 0 && i < len then begin608BitsSpec.bit_update off len src.u dst.u (i + off);609BitsSpec.bit_update off len src.l dst.l (i + off);610mem_bits s r (i + off)611end in612let lemma dst_bits (p:int) : unit613requires { 0 <= p }614ensures { Zbit.bittest dst.u p -> Zbit.bittest xd p }615ensures { Zbit.bittest xd p -> Zbit.bittest dst.l p }616= xbits p; inv_bit dst p;617BitsSpec.bit_update off len src.u dst.u p; BitsSpec.bit_update off len src.l dst.l p;618mem_bits s r p;619if len > 0 && off <= p && p < off + len then Zbit.def_asr dst.u off (p - off) in620let lemma back (p:int) : unit621requires { 0 <= p }622ensures { Zbit.bittest (BitsSpec.update off len xs xd) p <-> Zbit.bittest s p }623= BitsSpec.bit_update off len xs xd p; xbits p;624if len > 0 && off <= p && p < off + len then xbits (p - off) in625Zbit.ext_bittest s (BitsSpec.update off len xs xd);626assert { mem xs src /\ mem xd dst /\ s = BitsSpec.update off len xs xd } in627r628629end630