library colibrilib.kb_interval — module KbIntervalmodule KbInterval9use int.Int10use real.RealInfix11use real.FromInt12use option.Option13use set.Set as S14use colibrilib.bound.Bound15use colibrilib.q.Real as Real16use colibrilib.stda.StdA as A17use colibrilib.union.Union18use colibrilib.congruence.Congruence as C19use colibrilib.union_congr.UnionCongr as UC20use colibrilib.known_bits.KnownBits as KB21use colibrilib.known_bits.Range as R22
k has the bits of the real x when it is an integer
predicate has_bits (x: real) (k: KB.t) =25forall n:int. x = from_int n -> KB.mem n k26
The known bits of the integers of one interval: a strict bound is taken as large (of_range of the closure); a bound that is not an integer, or infinite, gives top
Valid (1.2s) (colibri2 5) (split_vc) (depth 1)let of_interval (i: Make.Map.interval) : KB.t33ensures { forall x. Make.Map.mem_interval x i -> has_bits x result }34= match i with35| Make.Map.Singleton a ->36if A.is_integer a then KB.cst (A.to_z a) else KB.top37| Make.Map.Inter lo hi ->38let int_of (b: Make.Map.qbound) : option A.t39ensures { match result with40| Some a -> Real.is_integer (A.real a) /\41(b = Make.Map.BLarge a \/ b = Make.Map.BStrict a)42| None -> true end }43= match b with44| Make.Map.BLarge a | Make.Map.BStrict a ->45if A.is_integer a then Some a else None46| Make.Map.BInf -> None47end in48match int_of lo, int_of hi with49| Some a, Some b -> R.of_range (A.to_z a) (A.to_z b)50| _ -> KB.top51end52end53
The known bits of the integers of a union of intervals
Valid (263ms) (colibri2 4) (split_vc) (depth 1)let of_union (u: Make.t) : KB.t56ensures { forall x. Make.memt x u -> has_bits x result }57= let union (a b: KB.t) : KB.t58ensures { forall x. has_bits x a \/ has_bits x b -> has_bits x result }59= KB.union a b in60Make.Map.UnaryFold.map61{ Make.Map.UnaryFold.f = of_interval; Make.Map.UnaryFold.union = union;62Make.Map.UnaryFold.inv = has_bits } u63
The known bits of the integers of a domain (bitmask_of_interval). None: the domain has no integer. With use_domain false (--lra-no-int-to-bv), only its emptiness is read: top.
Valid (510ms) (colibri2 13) (cvc4) (split_vc 4) (depth 3)let known_bits (use_domain: bool) (t: UC.t) : option KB.t68ensures { match result with69| Some k -> forall x. UC.mem x t -> has_bits x k70| None -> forall x. UC.mem x t -> not Real.is_integer x end }71= match UC.reduce_integers t with72| None -> None73| Some t' ->74let ku = if use_domain then of_union t'.UC.u else KB.top in75let kc = match t'.UC.c with76| Some c -> if use_domain then C.to_knownbits c else KB.top77| None -> KB.top78end in79{proof…}80let lemma in_both (x: real) (n: int) : unit81requires { UC.mem x t }82requires { x = from_int n }83ensures { KB.mem n ku /\ KB.mem n kc }84= assert { Real.is_integer x };85assert { UC.mem x t' };86assert { Make.memt x t'.UC.u };87match t'.UC.c with88| None -> ()89| Some c -> assert { C.member x c }; assert { S.mem x (C.gamma c) }90end in91{qed}92match KB.inter ku kc with93| None ->94{proof…}95assert { forall x n. UC.mem x t -> x = from_int n ->96KB.mem n ku && KB.mem n kc && false };97{qed}98None99| Some k ->100{proof…}101assert { forall x n. UC.mem x t -> x = from_int n ->102KB.mem n ku && KB.mem n kc && KB.mem n k };103{qed}104Some k105end106end107
The domain of the integers of k (interval_of_bitmask): their congruence, within their bounds. None: k has no integer
Valid (820ms) (colibri2 6) (split_vc 3) (depth 2)let of_known_bits (k: KB.t) : option UC.t113ensures { match result with114| Some t -> forall n. KB.mem n k -> UC.mem (from_int n) t115| None -> forall n. not KB.mem n k end }116= let c = C.of_knownbits k in117let i = UC.of_congruence c in118match R.bounds k with119| None -> Some i120| Some (lo, hi) ->121let hull = (Some (A.of_bigint lo, Bound.Large),122Some (A.of_bigint hi, Bound.Large)) in123match UC.from_convex_hull hull with124| None ->125{proof…}126assert { forall n. KB.mem n k -> Make.in_hull (from_int n) hull };127{qed}128None129| Some h ->130{proof…}131assert { forall n. KB.mem n k -> S.mem (from_int n) (C.gamma c) };132assert { forall n. KB.mem n k -> UC.mem (from_int n) i };133assert { forall n. KB.mem n k -> UC.mem (from_int n) h };134{qed}135UC.inter h i136end137end138
Converter.propagate_interval_using_knownbits2: the domain of the result of a bitwise operator from the domains of its arguments, by their known bits. None: no integer can be the result.
use colibrilib.zarith.Zbit146use colibrilib.safe_bits.BitsSpec147use colibrilib.safe_bits.SafeBits148
r holds the results f x y of the integers of va and vb
predicate prop2 (f: int -> int -> int) (va vb: UC.t) (r: option UC.t) =151forall x y. UC.mem (from_int x) va -> UC.mem (from_int y) vb ->152match r with Some u -> UC.mem (from_int (f x y)) u | None -> false end153
The known bits of the integers of va and vb, None if one has no integer
Valid (235ms) (cvc4)let known_bits2 (use_domain: bool) (va vb: UC.t) : option (KB.t, KB.t)157ensures { match result with158| Some (ka, kb) -> forall x y. UC.mem (from_int x) va ->159UC.mem (from_int y) vb -> KB.mem x ka /\ KB.mem y kb160| None -> forall x y. UC.mem (from_int x) va ->161UC.mem (from_int y) vb -> false end }162= match known_bits use_domain va, known_bits use_domain vb with163| Some ka, Some kb -> Some (ka, kb)164| _ -> None165end166Valid (173ms) (colibri2)167let logand (use_domain: bool) (va vb: UC.t) : option UC.t168ensures { prop2 Zbit.land va vb result }169= match known_bits2 use_domain va vb with170| None -> None171| Some (ka, kb) -> of_known_bits (KB.logand ka kb)172end173Valid (173ms) (colibri2)174let logor (use_domain: bool) (va vb: UC.t) : option UC.t175ensures { prop2 Zbit.lor va vb result }176= match known_bits2 use_domain va vb with177| None -> None178| Some (ka, kb) -> of_known_bits (KB.logor ka kb)179end180Valid (194ms) (colibri2)181let logxor (use_domain: bool) (va vb: UC.t) : option UC.t182ensures { prop2 Zbit.lxor va vb result }183= match known_bits2 use_domain va vb with184| None -> None185| Some (ka, kb) -> of_known_bits (KB.logxor ka kb)186end187
update off len src dst (colibri_update_int); the integers when off or len is too big for the known bits
Valid (1.0s) (colibri2 4) (split_vc 2) (depth 2)let update (use_domain: bool) (off len: int) (vsrc vdst: UC.t) : option UC.t191ensures { prop2 (fun xs xd -> BitsSpec.update off len xs xd) vsrc vdst result }192= if SafeBits.update_ok off len then193match known_bits2 use_domain vsrc vdst with194| None -> None195| Some (ks, kd) -> of_known_bits (KB.update off len ks kd)196end197else begin198{proof…}199let lemma int (n: int) : unit ensures { Real.is_integer (from_int n) } = () in200{qed}201Some (UC.integers ())202end203
r holds the results f x of the integers of va
predicate prop1 (f: int -> int) (va: UC.t) (r: option UC.t) =206forall x. UC.mem (from_int x) va ->207match r with Some u -> UC.mem (from_int (f x)) u | None -> false end208
The known bits of the integers of va, None if it has none
Valid (92ms) (colibri2)let known_bits1 (use_domain: bool) (va: UC.t) : option KB.t211ensures { match result with212| Some ka -> forall x. UC.mem (from_int x) va -> KB.mem x ka213| None -> forall x. UC.mem (from_int x) va -> false end }214= known_bits use_domain va215
The domain of the results, from their known bits k
Valid (87ms) (colibri2)let of_bits1 (ghost f: int -> int) (ghost va: UC.t) (k: KB.t) : option UC.t218requires { forall x. UC.mem (from_int x) va -> KB.mem (f x) k }219ensures { prop1 f va result }220= of_known_bits k221
All the integers: the result when the known bits are too big
Valid (401ms) (colibri2)let all_integers (ghost f: int -> int) (ghost va: UC.t) : option UC.t224ensures { prop1 f va result }225= {proof…}226let lemma int (n: int) : unit ensures { Real.is_integer (from_int n) } = () in227{qed}228Some (UC.integers ())229Valid (124ms) (colibri2)230let lognot (use_domain: bool) (va: UC.t) : option UC.t231ensures { prop1 Zbit.lnot va result }232= match known_bits1 use_domain va with233| None -> None234| Some ka -> of_known_bits (KB.lognot ka)235end236
asr x off (colibri_rshift_int)
Valid (737ms) (colibri2 6) (split_vc 4) (depth 3)let shift_right (use_domain: bool) (off: int) (va: UC.t) : option UC.t239ensures { prop1 (fun x -> Zbit.asr x off) va result }240= match known_bits1 use_domain va with241| None -> None242| Some ka ->243if SafeBits.shift_ok off ka.KB.l && SafeBits.shift_ok off ka.KB.u244then begin245let k = KB.shift_right off ka in246of_bits1 (fun x -> Zbit.asr x off) va k247end248else all_integers (fun x -> Zbit.asr x off) va249end250
extract off len x (colibri_extract_int)
Valid (231ms) (colibri2 5) (cvc4) (split_vc 4) (depth 3)let extract (use_domain: bool) (off len: int) (va: UC.t) : option UC.t253ensures { prop1 (fun x -> BitsSpec.extract off len x) va result }254= match known_bits1 use_domain va with255| None -> None256| Some ka ->257if SafeBits.extract_ok off len ka.KB.l && SafeBits.extract_ok off len ka.KB.u258then begin259let k = KB.extract off len ka in260of_bits1 (fun x -> BitsSpec.extract off len x) va k261end262else all_integers (fun x -> BitsSpec.extract off len x) va263end264
signed_extract off len x (colibri_signed_extract_int)
Valid (429ms) (colibri2 5) (split_vc 4) (depth 3)let signed_extract (use_domain: bool) (off len: int) (va: UC.t) : option UC.t267ensures { prop1 (fun x -> BitsSpec.signed_extract off len x) va result }268= match known_bits1 use_domain va with269| None -> None270| Some ka ->271if SafeBits.signed_extract_ok off len272then begin273let k = KB.signed_extract off len ka in274of_bits1 (fun x -> BitsSpec.signed_extract off len x) va k275end276else all_integers (fun x -> BitsSpec.signed_extract off len x) va277end278
The bit i of the integers of va (colibri_testbit_int): None if va has no integer
Valid (116ms) (colibri2)let testbit (use_domain: bool) (va: UC.t) (i: int) : option KB.kind282ensures { match result with283| Some k -> forall x. UC.mem (from_int x) va ->284(k = KB.One -> Zbit.bittest x i) /\ (k = KB.Zero -> not Zbit.bittest x i)285| None -> forall x. UC.mem (from_int x) va -> false end }286= match known_bits1 use_domain va with287| None -> None288| Some ka -> Some (KB.testbit ka i)289end290end291