Common — library colibrilib.kb_interval — module KbInterval
9
module KbInterval
10
use int.Int
11
use real.RealInfix
12
use real.FromInt
13
use option.Option
14
use set.Set as S
15
use colibrilib.bound.Bound
16
use colibrilib.q.Real as Real
17
use colibrilib.stda.StdA as A
18
use colibrilib.union.Union
19
use colibrilib.congruence.Congruence as C
20
use colibrilib.union_congr.UnionCongr as UC
21
use colibrilib.known_bits.KnownBits as KB
22
use colibrilib.known_bits.Range as R

k has the bits of the real x when it is an integer

25
predicate
has_bits
(x: real) (k: KB.t) =
26
forall n:int. x = from_int n -> KB.mem n k

From the intervals to the known bits

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)
33
let
of_interval
(i: Make.Map.interval) : KB.t
34
ensures { forall x. Make.Map.mem_interval x i -> has_bits x result }
35
= match i with
36
| Make.Map.Singleton a ->
37
if A.is_integer a then KB.cst (A.to_z a) else KB.top
38
| Make.Map.Inter lo hi ->
39
let int_of (b: Make.Map.qbound) : option A.t
40
ensures { match result with
41
| Some a -> Real.is_integer (A.real a) /\
42
(b = Make.Map.BLarge a \/ b = Make.Map.BStrict a)
43
| None -> true end }
44
= match b with
45
| Make.Map.BLarge a | Make.Map.BStrict a ->
46
if A.is_integer a then Some a else None
47
| Make.Map.BInf -> None
48
end in
49
match int_of lo, int_of hi with
50
| Some a, Some b -> R.of_range (A.to_z a) (A.to_z b)
51
| _ -> KB.top
52
end
53
end

The known bits of the integers of a union of intervals

  Valid (263ms) (colibri2 4) (split_vc) (depth 1)
56
let
of_union
(u: Make.t) : KB.t
57
ensures { forall x. Make.memt x u -> has_bits x result }
58
= let union (a b: KB.t) : KB.t
59
ensures { forall x. has_bits x a \/ has_bits x b -> has_bits x result }
60
= KB.union a b in
61
Make.Map.UnaryFold.map
62
{ Make.Map.UnaryFold.f = of_interval; Make.Map.UnaryFold.union = union;
63
Make.Map.UnaryFold.inv = has_bits } u

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)
68
let
known_bits
(use_domain: bool) (t: UC.t) : option KB.t
69
ensures { match result with
70
| Some k -> forall x. UC.mem x t -> has_bits x k
71
| None -> forall x. UC.mem x t -> not Real.is_integer x end }
72
= match UC.reduce_integers t with
73
| None -> None
74
| Some t' ->
75
let ku = if use_domain then of_union t'.UC.u else KB.top in
76
let kc = match t'.UC.c with
77
| Some c -> if use_domain then C.to_knownbits c else KB.top
78
| None -> KB.top
79
end in
80
{proof…}
81
let lemma in_both (x: real) (n: int) : unit
82
requires { UC.mem x t }
83
requires { x = from_int n }
84
ensures { KB.mem n ku /\ KB.mem n kc }
85
= assert { Real.is_integer x };
86
assert { UC.mem x t' };
87
assert { Make.memt x t'.UC.u };
88
match t'.UC.c with
89
| None -> ()
90
| Some c -> assert { C.member x c }; assert { S.mem x (C.gamma c) }
91
end in
92
{qed}
93
match KB.inter ku kc with
94
| None ->
95
{proof…}
96
assert { forall x n. UC.mem x t -> x = from_int n ->
97
KB.mem n ku && KB.mem n kc && false };
98
{qed}
99
None
100
| Some k ->
101
{proof…}
102
assert { forall x n. UC.mem x t -> x = from_int n ->
103
KB.mem n ku && KB.mem n kc && KB.mem n k };
104
{qed}
105
Some k
106
end
107
end

From the known bits to an interval domain

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)
113
let
of_known_bits
(k: KB.t) : option UC.t
114
ensures { match result with
115
| Some t -> forall n. KB.mem n k -> UC.mem (from_int n) t
116
| None -> forall n. not KB.mem n k end }
117
= let c = C.of_knownbits k in
118
let i = UC.of_congruence c in
119
match R.bounds k with
120
| None -> Some i
121
| Some (lo, hi) ->
122
let hull = (Some (A.of_bigint lo, Bound.Large),
123
Some (A.of_bigint hi, Bound.Large)) in
124
match UC.from_convex_hull hull with
125
| None ->
126
{proof…}
127
assert { forall n. KB.mem n k -> Make.in_hull (from_int n) hull };
128
{qed}
129
None
130
| Some h ->
131
{proof…}
132
assert { forall n. KB.mem n k -> S.mem (from_int n) (C.gamma c) };
133
assert { forall n. KB.mem n k -> UC.mem (from_int n) i };
134
assert { forall n. KB.mem n k -> UC.mem (from_int n) h };
135
{qed}
136
UC.inter h i
137
end
138
end

The propagation of the bitwise operators to the interval

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.

146
use colibrilib.zarith.Zbit
147
use colibrilib.safe_bits.BitsSpec
148
use colibrilib.safe_bits.SafeBits

r holds the results f x y of the integers of va and vb

151
predicate
prop2
(f: int -> int -> int) (va vb: UC.t) (r: option UC.t) =
152
forall x y. UC.mem (from_int x) va -> UC.mem (from_int y) vb ->
153
match r with Some u -> UC.mem (from_int (f x y)) u | None -> false end

The known bits of the integers of va and vb, None if one has no integer

  Valid (235ms) (cvc4)
157
let
known_bits2
(use_domain: bool) (va vb: UC.t) : option (KB.t, KB.t)
158
ensures { match result with
159
| Some (ka, kb) -> forall x y. UC.mem (from_int x) va ->
160
UC.mem (from_int y) vb -> KB.mem x ka /\ KB.mem y kb
161
| None -> forall x y. UC.mem (from_int x) va ->
162
UC.mem (from_int y) vb -> false end }
163
= match known_bits use_domain va, known_bits use_domain vb with
164
| Some ka, Some kb -> Some (ka, kb)
165
| _ -> None
166
end
167
Valid (173ms) (colibri2)
168
let
logand
(use_domain: bool) (va vb: UC.t) : option UC.t
169
ensures { prop2 Zbit.land va vb result }
170
= match known_bits2 use_domain va vb with
171
| None -> None
172
| Some (ka, kb) -> of_known_bits (KB.logand ka kb)
173
end
174
Valid (173ms) (colibri2)
175
let
logor
(use_domain: bool) (va vb: UC.t) : option UC.t
176
ensures { prop2 Zbit.lor va vb result }
177
= match known_bits2 use_domain va vb with
178
| None -> None
179
| Some (ka, kb) -> of_known_bits (KB.logor ka kb)
180
end
181
Valid (194ms) (colibri2)
182
let
logxor
(use_domain: bool) (va vb: UC.t) : option UC.t
183
ensures { prop2 Zbit.lxor va vb result }
184
= match known_bits2 use_domain va vb with
185
| None -> None
186
| Some (ka, kb) -> of_known_bits (KB.logxor ka kb)
187
end

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)
191
let
update
(use_domain: bool) (off len: int) (vsrc vdst: UC.t) : option UC.t
192
ensures { prop2 (fun xs xd -> BitsSpec.update off len xs xd) vsrc vdst result }
193
= if SafeBits.update_ok off len then
194
match known_bits2 use_domain vsrc vdst with
195
| None -> None
196
| Some (ks, kd) -> of_known_bits (KB.update off len ks kd)
197
end
198
else begin
199
{proof…}
200
let lemma int (n: int) : unit ensures { Real.is_integer (from_int n) } = () in
201
{qed}
202
Some (UC.integers ())
203
end

r holds the results f x of the integers of va

206
predicate
prop1
(f: int -> int) (va: UC.t) (r: option UC.t) =
207
forall x. UC.mem (from_int x) va ->
208
match r with Some u -> UC.mem (from_int (f x)) u | None -> false end

The known bits of the integers of va, None if it has none

  Valid (92ms) (colibri2)
211
let
known_bits1
(use_domain: bool) (va: UC.t) : option KB.t
212
ensures { match result with
213
| Some ka -> forall x. UC.mem (from_int x) va -> KB.mem x ka
214
| None -> forall x. UC.mem (from_int x) va -> false end }
215
= known_bits use_domain va

The domain of the results, from their known bits k

  Valid (87ms) (colibri2)
218
let
of_bits1
(ghost f: int -> int) (ghost va: UC.t) (k: KB.t) : option UC.t
219
requires { forall x. UC.mem (from_int x) va -> KB.mem (f x) k }
220
ensures { prop1 f va result }
221
= of_known_bits k

All the integers: the result when the known bits are too big

  Valid (401ms) (colibri2)
224
let
all_integers
(ghost f: int -> int) (ghost va: UC.t) : option UC.t
225
ensures { prop1 f va result }
226
= {proof…}
227
let lemma int (n: int) : unit ensures { Real.is_integer (from_int n) } = () in
228
{qed}
229
Some (UC.integers ())
230
Valid (124ms) (colibri2)
231
let
lognot
(use_domain: bool) (va: UC.t) : option UC.t
232
ensures { prop1 Zbit.lnot va result }
233
= match known_bits1 use_domain va with
234
| None -> None
235
| Some ka -> of_known_bits (KB.lognot ka)
236
end

asr x off (colibri_rshift_int)

  Valid (737ms) (colibri2 6) (split_vc 4) (depth 3)
239
let
shift_right
(use_domain: bool) (off: int) (va: UC.t) : option UC.t
240
ensures { prop1 (fun x -> Zbit.asr x off) va result }
241
= match known_bits1 use_domain va with
242
| None -> None
243
| Some ka ->
244
if SafeBits.shift_ok off ka.KB.l && SafeBits.shift_ok off ka.KB.u
245
then begin
246
let k = KB.shift_right off ka in
247
of_bits1 (fun x -> Zbit.asr x off) va k
248
end
249
else all_integers (fun x -> Zbit.asr x off) va
250
end

extract off len x (colibri_extract_int)

  Valid (231ms) (colibri2 5) (cvc4) (split_vc 4) (depth 3)
253
let
extract
(use_domain: bool) (off len: int) (va: UC.t) : option UC.t
254
ensures { prop1 (fun x -> BitsSpec.extract off len x) va result }
255
= match known_bits1 use_domain va with
256
| None -> None
257
| Some ka ->
258
if SafeBits.extract_ok off len ka.KB.l && SafeBits.extract_ok off len ka.KB.u
259
then begin
260
let k = KB.extract off len ka in
261
of_bits1 (fun x -> BitsSpec.extract off len x) va k
262
end
263
else all_integers (fun x -> BitsSpec.extract off len x) va
264
end

signed_extract off len x (colibri_signed_extract_int)

  Valid (429ms) (colibri2 5) (split_vc 4) (depth 3)
267
let
signed_extract
(use_domain: bool) (off len: int) (va: UC.t) : option UC.t
268
ensures { prop1 (fun x -> BitsSpec.signed_extract off len x) va result }
269
= match known_bits1 use_domain va with
270
| None -> None
271
| Some ka ->
272
if SafeBits.signed_extract_ok off len
273
then begin
274
let k = KB.signed_extract off len ka in
275
of_bits1 (fun x -> BitsSpec.signed_extract off len x) va k
276
end
277
else all_integers (fun x -> BitsSpec.signed_extract off len x) va
278
end

The bit i of the integers of va (colibri_testbit_int): None if va has no integer

  Valid (116ms) (colibri2)
282
let
testbit
(use_domain: bool) (va: UC.t) (i: int) : option KB.kind
283
ensures { match result with
284
| Some k -> forall x. UC.mem (from_int x) va ->
285
(k = KB.One -> Zbit.bittest x i) /\ (k = KB.Zero -> not Zbit.bittest x i)
286
| None -> forall x. UC.mem (from_int x) va -> false end }
287
= match known_bits1 use_domain va with
288
| None -> None
289
| Some ka -> Some (KB.testbit ka i)
290
end
291
end