Common — library colibrilib.known_bits — module KnownBits

The 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.

12
module KnownBits
13
use int.Int
14
use int.MinMax
15
use colibrilib.zarith.Zbit
16
use colibrilib.zbit.ZbitInt
17
use option.Option
18
use colibrilib.safe_bits.BitsSpec
19
use colibrilib.safe_bits.SafeBits
20
use colibrilib.spec.Sound
21
22
type
t
= {
l
: int;
u
: int } Valid (62ms) (colibri2)
23
invariant { Zbit.subset u l }
24
by { l = -1; u = 0 }
25
type
kind
=
One
|
Zero
|
Unknown
26
27
predicate
mem
(x:int) (a:t) = Zbit.subset a.u x /\ Zbit.subset x a.l
28
Valid (61ms) (colibri2)
29
let lemma
subset_pos
(a b:int) : unit
30
requires { forall i. 0 <= i -> Zbit.bittest a i -> Zbit.bittest b i }
31
ensures { Zbit.subset a b }
32
= ()

t is never empty

  Valid (62ms) (colibri2)
35
let lemma
exists_mem
(a:t) : unit
36
ensures { mem a.u a /\ mem a.l a }
37
= ()

mem in terms of the bits

  Valid (54ms) (colibri2)
40
let lemma
mem_bits
(x:int) (a:t) (i:int) : unit
41
requires { mem x a }
42
requires { 0 <= i }
43
ensures { Zbit.bittest a.u i -> Zbit.bittest x i }
44
ensures { Zbit.bittest x i -> Zbit.bittest a.l i }
45
= ()
46
Valid (67ms) (colibri2)
47
let lemma
mem_of_bits
(x:int) (a:t) : unit
48
requires { forall i. 0 <= i -> Zbit.bittest a.u i -> Zbit.bittest x i }
49
requires { forall i. 0 <= i -> Zbit.bittest x i -> Zbit.bittest a.l i }
50
ensures { mem x a }
51
= ()

the invariant, bit by bit

  Valid (126ms) (colibri2)
54
let lemma
inv_bit
(a:t) (i:int) : unit
55
requires { 0 <= i }
56
ensures { Zbit.bittest a.u i -> Zbit.bittest a.l i }
57
= ()
58
Valid (56ms) (colibri2)
59
let constant
top
: t = { l = -1; u = 0 }
60
Valid (85ms) (colibri2)
61
let lemma
top_all
(x:int) : unit
62
ensures { mem x top }
63
= let lemma b (i:int) : unit
64
requires { 0 <= i }
65
ensures { Zbit.bittest x i -> Zbit.bittest top.l i }
66
= SafeBits.minus_one_bits i in
67
()
68
Valid (82ms) (cvc5)
69
let lemma
is_top_iff
(a:t) : unit
70
ensures { (a.l = -1 /\ a.u = 0) <-> (forall x. mem x a) }
71
= if a.l = -1 && a.u = 0 then begin
72
let lemma all (x:int) : unit ensures { mem x a } = top_all x in ()
73
end else if pure { forall x. mem x a } then begin
74
let lemma l_bit (i:int) : unit
75
requires { 0 <= i }
76
ensures { Zbit.bittest a.l i <-> Zbit.bittest (-1) i }
77
= SafeBits.minus_one_bits i in
78
let lemma u_bit (i:int) : unit
79
requires { 0 <= i }
80
ensures { Zbit.bittest a.u i <-> Zbit.bittest 0 i }
81
= () in
82
Zbit.ext_bittest a.l (-1);
83
Zbit.ext_bittest a.u 0
84
end

a contains all the integers

  Valid (77ms) (colibri2)
87
let
is_top
(a:t) : bool
88
ensures { result <-> forall x. mem x a }
89
= a.l = -1 && a.u = 0

The single integer a

  Valid (94ms) (colibri2)
92
let
cst
(a:int) : t
93
ensures { exact mem (fun x -> x = a) result }
94
= let r = { l = a; u = a } in
95
let lemma back (x:int) : unit
96
requires { mem x r }
97
ensures { x = a }
98
= Zbit.ext_bittest x a in
99
r

The integers that have the bits of a on the positions of mask

  Valid (404ms) (colibri2 11) (cvc4) (split_vc) (depth 1)
102
let
cst_mask
(a mask:int) : t
103
ensures { exact mem (fun x -> forall i. 0 <= i -> Zbit.bittest mask i ->
104
(Zbit.bittest x i <-> Zbit.bittest a i)) result }
105
= let rl = Zbit.lor a (Zbit.lnot mask) in
106
let ru = Zbit.land a mask in
107
let lemma bit (i:int) : unit
108
requires { 0 <= i }
109
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
110
= () in
111
let r = { l = rl; u = ru } in
112
let lemma fwd (x:int) : unit
113
requires { mem x r }
114
ensures { forall i. 0 <= i -> Zbit.bittest mask i ->
115
(Zbit.bittest x i <-> Zbit.bittest a i) }
116
= let lemma b (i:int) : unit
117
requires { 0 <= i } requires { Zbit.bittest mask i }
118
ensures { Zbit.bittest x i <-> Zbit.bittest a i }
119
= mem_bits x r i in
120
() in
121
let lemma bwd (x:int) : unit
122
requires { forall i. 0 <= i -> Zbit.bittest mask i ->
123
(Zbit.bittest x i <-> Zbit.bittest a i) }
124
ensures { mem x r }
125
= let lemma bu (i:int) : unit
126
requires { 0 <= i } ensures { Zbit.bittest r.u i -> Zbit.bittest x i }
127
= () in
128
let lemma bl (i:int) : unit
129
requires { 0 <= i } ensures { Zbit.bittest x i -> Zbit.bittest r.l i }
130
= () in
131
mem_of_bits x r in
132
r

The intersection of the concretizations is exact; None is the empty intersection

  Valid (333ms) (colibri2 13) (cvc4 2) (cvc5) (split_vc 2) (depth 2)
136
let
inter
(a b:t) : option t
137
ensures { exact_opt mem (fun x -> mem x a /\ mem x b) result }
138
= let rl = Zbit.land a.l b.l in
139
let ru = Zbit.lor a.u b.u in
140
let d = Zbit.land ru (Zbit.lnot rl) in
141
let lemma d_bit (i:int) : unit
142
requires { 0 <= i }
143
ensures { Zbit.bittest d i <-> (Zbit.bittest ru i /\ not (Zbit.bittest rl i)) }
144
= () in
145
if d <> 0 then begin
146
let lemma empty (x:int) : unit
147
requires { mem x a /\ mem x b }
148
ensures { false }
149
= let lemma bit (i:int) : unit
150
requires { 0 <= i }
151
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
152
= mem_bits x a i; mem_bits x b i in
153
Zbit.ext_bittest d 0 in
154
assert { forall x. (mem x a /\ mem x b) <-> false };
155
None
156
end else begin
157
Zbit.ext_bittest d 0;
158
let lemma sub (i:int) : unit
159
requires { 0 <= i }
160
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
161
= () in
162
let r = { l = rl; u = ru } in
163
assert { forall x. (mem x a /\ mem x b) <-> mem x r };
164
Some r
165
end

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)
169
let ghost
join_mem
(a b r: t) : unit
170
requires { forall x. mem x a \/ mem x b -> mem x r }
171
requires { forall c. (forall x. mem x a -> mem x c) ->
172
(forall x. mem x b -> mem x c) -> forall x. mem x r -> mem x c }
173
ensures { join mem a b r }
174
= ()

The smallest element containing the union of two elements

  Valid (396ms) (colibri2 15) (cvc5 5) (split_vc) (depth 1)
177
let
union
(a b:t) : t
178
ensures { join mem a b result }
179
= let rl = Zbit.lor a.l b.l in
180
let ru = Zbit.land a.u b.u in
181
let lemma sub (i:int) : unit
182
requires { 0 <= i }
183
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
184
= () in
185
let r = { l = rl; u = ru } in
186
let lemma lub (c:t) : unit
187
requires { forall x. mem x a -> mem x c }
188
requires { forall x. mem x b -> mem x c }
189
ensures { forall x. mem x r -> mem x c }
190
= exists_mem a; exists_mem b;
191
assert { mem a.u c /\ mem a.l c /\ mem b.u c /\ mem b.l c };
192
let lemma mem_r (x:int) : unit
193
requires { mem x r }
194
ensures { mem x c }
195
= let lemma bit (i:int) : unit
196
requires { 0 <= i }
197
ensures { Zbit.bittest c.u i -> Zbit.bittest x i }
198
ensures { Zbit.bittest x i -> Zbit.bittest c.l i }
199
= mem_bits a.u c i; mem_bits a.l c i; mem_bits b.u c i; mem_bits b.l c i;
200
mem_bits x r i in
201
() in
202
() in
203
join_mem a b r;
204
r

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)
208
let
mk
(known0 known1:int) : option t
209
ensures { match result with
210
| None -> not (Zbit.subset known1 known0)
211
| Some r -> r.l = known0 /\ r.u = known1
212
end }
213
= let d = Zbit.land known1 (Zbit.lnot known0) in
214
let lemma d_bit (i:int) : unit
215
requires { 0 <= i }
216
ensures { Zbit.bittest d i <-> (Zbit.bittest known1 i /\ not (Zbit.bittest known0 i)) }
217
= () in
218
if d <> 0 then begin
219
if pure { Zbit.subset known1 known0 } then Zbit.ext_bittest d 0;
220
None
221
end else begin
222
let lemma sub (i:int) : unit
223
requires { 0 <= i }
224
ensures { Zbit.bittest known1 i -> Zbit.bittest known0 i }
225
= () in
226
Zbit.ext_bittest d 0;
227
Some { l = known0; u = known1 }
228
end

Exact: x is in a iff lnot x is in the result

  Valid (463ms) (colibri2 14) (cvc4) (cvc5) (split_vc 2) (depth 2)
231
let
lognot
(a:t) : t
232
ensures { forall x. mem (Zbit.lnot x) result <-> mem x a }
233
ensures { sound1 mem Zbit.lnot a result }
234
ensures { complete1 mem Zbit.lnot a result }
235
= let rl = Zbit.lnot a.u in
236
let ru = Zbit.lnot a.l in
237
let lemma sub (i:int) : unit
238
requires { 0 <= i }
239
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
240
= inv_bit a i in
241
let r = { l = rl; u = ru } in
242
let lemma ln (x:int) : unit
243
ensures { mem (Zbit.lnot x) r <-> mem x a }
244
= let lemma bit (i:int) : unit
245
requires { 0 <= i }
246
ensures { Zbit.bittest r.u i <-> not (Zbit.bittest a.l i) }
247
ensures { Zbit.bittest r.l i <-> not (Zbit.bittest a.u i) }
248
ensures { Zbit.bittest (Zbit.lnot x) i <-> not (Zbit.bittest x i) }
249
= () in
250
() in
251
let lemma back (s:int) : unit
252
requires { mem s r }
253
ensures { exists x. mem x a /\ s = Zbit.lnot x }
254
= let ghost x = pure { Zbit.lnot s } in
255
ln x;
256
Zbit.ext_bittest s (pure { Zbit.lnot x });
257
assert { mem x a /\ s = Zbit.lnot x } in
258
assert { sound1 mem Zbit.lnot a r };
259
assert { complete1 mem Zbit.lnot a r };
260
r

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)
264
let
logand
(a b:t) : t
265
ensures { sound2 mem Zbit.land a b result }
266
ensures { complete2 mem Zbit.land a b result }
267
= let rl = Zbit.land a.l b.l in
268
let ru = Zbit.land a.u b.u in
269
let lemma sub (i:int) : unit
270
requires { 0 <= i }
271
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
272
= inv_bit a i; inv_bit b i in
273
let r = { l = rl; u = ru } in
274
let lemma sound (x y:int) : unit
275
requires { mem x a /\ mem y b }
276
ensures { mem (Zbit.land x y) r }
277
= let lemma bit (i:int) : unit
278
requires { 0 <= i }
279
ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.land x y) i }
280
ensures { Zbit.bittest (Zbit.land x y) i -> Zbit.bittest r.l i }
281
= mem_bits x a i; mem_bits y b i in () in
282
let lemma exact (z:int) : unit
283
requires { mem z r }
284
ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.land x y }
285
= let x = Zbit.lor a.u z in
286
let y = Zbit.lor b.u z in
287
let lemma bit (i:int) : unit
288
requires { 0 <= i }
289
ensures { Zbit.bittest (Zbit.land x y) i <-> Zbit.bittest z i }
290
ensures { Zbit.bittest a.u i -> Zbit.bittest x i }
291
ensures { Zbit.bittest x i -> Zbit.bittest a.l i }
292
ensures { Zbit.bittest b.u i -> Zbit.bittest y i }
293
ensures { Zbit.bittest y i -> Zbit.bittest b.l i }
294
= mem_bits z r i in
295
Zbit.ext_bittest (Zbit.land x y) z;
296
assert { mem x a /\ mem y b /\ z = Zbit.land x y } in
297
r

Exact

  Valid (524ms) (colibri2 16) (cvc4 3) (cvc5 4) (split_vc) (depth 1)
300
let
logor
(a b:t) : t
301
ensures { sound2 mem Zbit.lor a b result }
302
ensures { complete2 mem Zbit.lor a b result }
303
= let rl = Zbit.lor a.l b.l in
304
let ru = Zbit.lor a.u b.u in
305
let lemma sub (i:int) : unit
306
requires { 0 <= i }
307
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
308
= inv_bit a i; inv_bit b i in
309
let r = { l = rl; u = ru } in
310
let lemma sound (x y:int) : unit
311
requires { mem x a /\ mem y b }
312
ensures { mem (Zbit.lor x y) r }
313
= let lemma bit (i:int) : unit
314
requires { 0 <= i }
315
ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.lor x y) i }
316
ensures { Zbit.bittest (Zbit.lor x y) i -> Zbit.bittest r.l i }
317
= mem_bits x a i; mem_bits y b i in () in
318
let lemma exact (z:int) : unit
319
requires { mem z r }
320
ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.lor x y }
321
= let x = Zbit.land z a.l in
322
let y = Zbit.land z b.l in
323
let lemma bit (i:int) : unit
324
requires { 0 <= i }
325
ensures { Zbit.bittest (Zbit.lor x y) i <-> Zbit.bittest z i }
326
ensures { Zbit.bittest a.u i -> Zbit.bittest x i }
327
ensures { Zbit.bittest x i -> Zbit.bittest a.l i }
328
ensures { Zbit.bittest b.u i -> Zbit.bittest y i }
329
ensures { Zbit.bittest y i -> Zbit.bittest b.l i }
330
= mem_bits z r i in
331
Zbit.ext_bittest (Zbit.lor x y) z;
332
assert { mem x a /\ mem y b /\ z = Zbit.lor x y } in
333
r
334
Valid (230ms) (colibri2)
335
let lemma
lxor_bit
(x y i:int) : unit
336
requires { 0 <= i }
337
ensures { Zbit.bittest (Zbit.lxor x y) i <-> not (Zbit.bittest x i <-> Zbit.bittest y i) }
338
= ()

Exact

  Valid (563ms) (colibri2 29) (cvc4 3) (cvc5 12) (split_vc 5) (depth 2)
341
let
logxor
(a b:t) : t
342
ensures { sound2 mem Zbit.lxor a b result }
343
ensures { complete2 mem Zbit.lxor a b result }
344
= let rl = Zbit.lor (Zbit.land a.l (Zbit.lnot b.u)) (Zbit.land b.l (Zbit.lnot a.u)) in
345
let ru = Zbit.lor (Zbit.land a.u (Zbit.lnot b.l)) (Zbit.land b.u (Zbit.lnot a.l)) in
346
let lemma xbits (i:int) : unit
347
requires { 0 <= i }
348
ensures { 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)) }
349
ensures { 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)) }
350
= () in
351
let lemma sub (i:int) : unit
352
requires { 0 <= i }
353
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
354
= inv_bit a i; inv_bit b i in
355
let r = { l = rl; u = ru } in
356
let lemma sound (x y:int) : unit
357
requires { mem x a /\ mem y b }
358
ensures { mem (Zbit.lxor x y) r }
359
= let lemma bit (i:int) : unit
360
requires { 0 <= i }
361
ensures { Zbit.bittest r.u i -> Zbit.bittest (Zbit.lxor x y) i }
362
ensures { Zbit.bittest (Zbit.lxor x y) i -> Zbit.bittest r.l i }
363
= mem_bits x a i; mem_bits y b i in () in
364
let lemma exact (z:int) : unit
365
requires { mem z r }
366
ensures { exists x y. mem x a /\ mem y b /\ z = Zbit.lxor x y }
367
= let ua = Zbit.land a.l (Zbit.lnot a.u) in
368
let kb = Zbit.lor b.u (Zbit.lnot b.l) in
369
let w = Zbit.lxor z b.u in
370
let t = Zbit.land ua (Zbit.land kb w) in
371
let x = Zbit.lor a.u t in
372
let ub = Zbit.land b.l (Zbit.lnot b.u) in
373
let w2 = Zbit.lxor z x in
374
let y = Zbit.lor b.u (Zbit.land ub w2) in
375
let lemma bit (i:int) : unit
376
requires { 0 <= i }
377
ensures { Zbit.bittest (Zbit.lxor x y) i <-> Zbit.bittest z i }
378
ensures { Zbit.bittest a.u i -> Zbit.bittest x i }
379
ensures { Zbit.bittest x i -> Zbit.bittest a.l i }
380
ensures { Zbit.bittest b.u i -> Zbit.bittest y i }
381
ensures { Zbit.bittest y i -> Zbit.bittest b.l i }
382
= mem_bits z r i;
383
lxor_bit x y i; lxor_bit z b.u i; lxor_bit z x i;
384
assert { Zbit.bittest ua i <-> (Zbit.bittest a.l i /\ not Zbit.bittest a.u i) };
385
assert { Zbit.bittest kb i <-> (Zbit.bittest b.u i \/ not Zbit.bittest b.l i) };
386
assert { Zbit.bittest t i <-> (Zbit.bittest ua i /\ Zbit.bittest kb i /\ Zbit.bittest w i) };
387
assert { Zbit.bittest x i <-> (Zbit.bittest a.u i \/ Zbit.bittest t i) };
388
assert { Zbit.bittest ub i <-> (Zbit.bittest b.l i /\ not Zbit.bittest b.u i) };
389
assert { Zbit.bittest y i <-> (Zbit.bittest b.u i \/ (Zbit.bittest ub i /\ Zbit.bittest w2 i)) };
390
assert { 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)) };
391
assert { 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)) };
392
assert { Zbit.bittest a.u i -> Zbit.bittest a.l i };
393
assert { Zbit.bittest b.u i -> Zbit.bittest b.l i } in
394
Zbit.ext_bittest (Zbit.lxor x y) z;
395
assert { mem x a /\ mem y b /\ z = Zbit.lxor x y } in
396
r

The value of the bit i

  Valid (292ms) (colibri2)
399
let
testbit
(a:t) (i:int) : kind
400
ensures { forall x. mem x a -> (result = One -> Zbit.bittest x i) /\
401
(result = Zero -> not (Zbit.bittest x i)) }
402
ensures { result = Unknown ->
403
0 <= i /\ mem a.l a /\ mem a.u a /\ Zbit.bittest a.l i /\ not (Zbit.bittest a.u i) }
404
= if i < 0 then begin
405
Zbit.bittest_neg i i;
406
Zero
407
end else begin
408
let bl = if i >= SafeBits.nb a.l then (SafeBits.bittest_high a.l i; a.l < 0)
409
else ZbitInt.test_bit_int a.l i in
410
let bu = if i >= SafeBits.nb a.u then (SafeBits.bittest_high a.u i; a.u < 0)
411
else ZbitInt.test_bit_int a.u i in
412
if bl && bu then One
413
else if not bl && not bu then Zero
414
else begin
415
exists_mem a;
416
inv_bit a i;
417
Unknown
418
end
419
end

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)
423
let lemma
sound_map
(cond: int -> bool) (pos: int -> int) (a r: t) (x s: int) : unit
424
requires { forall i. 0 <= i -> (Zbit.bittest r.u i <-> (cond i /\ Zbit.bittest a.u (pos i))) }
425
requires { forall i. 0 <= i -> (Zbit.bittest r.l i <-> (cond i /\ Zbit.bittest a.l (pos i))) }
426
requires { forall i. 0 <= i -> (Zbit.bittest s i <-> (cond i /\ Zbit.bittest x (pos i))) }
427
requires { mem x a }
428
ensures { mem s r }
429
= let lemma bit (i:int) : unit
430
requires { 0 <= i }
431
ensures { Zbit.bittest r.u i -> Zbit.bittest s i }
432
ensures { Zbit.bittest s i -> Zbit.bittest r.l i }
433
= if 0 <= pos i then mem_bits x a (pos i)
434
else begin
435
Zbit.bittest_neg a.u (pos i); Zbit.bittest_neg x (pos i)
436
end in
437
()
438
Valid (144ms) (colibri2)
439
let lemma
image_subset
(cond: int -> bool) (pos: int -> int) (a: t) (rl ru: int) : unit
440
requires { forall i. 0 <= i -> (Zbit.bittest ru i <-> (cond i /\ Zbit.bittest a.u (pos i))) }
441
requires { forall i. 0 <= i -> (Zbit.bittest rl i <-> (cond i /\ Zbit.bittest a.l (pos i))) }
442
ensures { Zbit.subset ru rl }
443
= let lemma bit (i:int) : unit
444
requires { 0 <= i }
445
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
446
= if 0 <= pos i then inv_bit a (pos i) else Zbit.bittest_neg a.u (pos i) in
447
()

Shift right (Zbit.asr), to the left if off is negative

  Valid (689ms) (colibri2 29) (cvc4) (cvc5 2) (split_vc) (depth 1)
450
let
shift_right
(off:int) (a:t) : t
451
requires { SafeBits.shift_ok off a.l /\ SafeBits.shift_ok off a.u }
452
ensures { sound1 mem (fun x -> Zbit.asr x off) a result }
453
ensures { complete1 mem (fun x -> Zbit.asr x off) a result }
454
= let rl = SafeBits.shift_right off a.l in
455
let ru = SafeBits.shift_right off a.u in
456
let lemma bits (x i:int) : unit
457
requires { 0 <= i }
458
ensures { Zbit.bittest ru i <-> Zbit.bittest a.u (i + off) }
459
ensures { Zbit.bittest rl i <-> Zbit.bittest a.l (i + off) }
460
ensures { Zbit.bittest (Zbit.asr x off) i <-> Zbit.bittest x (i + off) }
461
= () in
462
image_subset (fun _ -> true) (fun i -> i + off) a rl ru;
463
let r = { l = rl; u = ru } in
464
let lemma sound (x:int) : unit
465
requires { mem x a }
466
ensures { mem (Zbit.asr x off) r }
467
= sound_map (fun _ -> true) (fun i -> i + off) a r x (Zbit.asr x off) in
468
let lemma exact (s:int) : unit
469
requires { mem s r }
470
ensures { exists x. mem x a /\ s = Zbit.asr x off }
471
= let x = Zbit.lor (Zbit.land a.u (Zbit.mask (max off 0))) (Zbit.lsl s off) in
472
let lemma bit (p:int) : unit
473
requires { 0 <= p }
474
ensures { Zbit.bittest x p <-> ((p < off /\ Zbit.bittest a.u p) \/ Zbit.bittest s (p - off)) }
475
ensures { Zbit.bittest a.u p -> Zbit.bittest x p }
476
ensures { Zbit.bittest x p -> Zbit.bittest a.l p }
477
= BitsSpec.mask_field (max off 0) p;
478
inv_bit a p;
479
if p - off >= 0 then begin
480
mem_bits s r (p - off); bits 0 (p - off)
481
end in
482
let lemma back (i:int) : unit
483
requires { 0 <= i }
484
ensures { Zbit.bittest (Zbit.asr x off) i <-> Zbit.bittest s i }
485
= mem_bits s r i; bits 0 i;
486
if i + off < 0 then Zbit.bittest_neg x (i + off)
487
else bit (i + off) in
488
Zbit.ext_bittest s (Zbit.asr x off);
489
assert { mem x a /\ s = Zbit.asr x off } in
490
r

BitsSpec.extract

  Valid (1.2s) (colibri2 34) (cvc4) (split_vc) (depth 1)
494
let
extract
(off len:int) (a:t) : t
495
requires { SafeBits.extract_ok off len a.l /\ SafeBits.extract_ok off len a.u }
496
ensures { sound1 mem (fun x -> BitsSpec.extract off len x) a result }
497
ensures { complete1 mem (fun x -> BitsSpec.extract off len x) a result }
498
= let rl = SafeBits.extract off len a.l in
499
let ru = SafeBits.extract off len a.u in
500
let lemma bits (x i:int) : unit
501
requires { 0 <= i }
502
ensures { Zbit.bittest ru i <-> (i < len /\ Zbit.bittest a.u (i + off)) }
503
ensures { Zbit.bittest rl i <-> (i < len /\ Zbit.bittest a.l (i + off)) }
504
ensures { Zbit.bittest (BitsSpec.extract off len x) i <-> (i < len /\ Zbit.bittest x (i + off)) }
505
= BitsSpec.bit_extract off len a.u i; BitsSpec.bit_extract off len a.l i;
506
BitsSpec.bit_extract off len x i in
507
image_subset (fun i -> i < len) (fun i -> i + off) a rl ru;
508
let r = { l = rl; u = ru } in
509
let lemma sound (x:int) : unit
510
requires { mem x a }
511
ensures { mem (BitsSpec.extract off len x) r }
512
= sound_map (fun i -> i < len) (fun i -> i + off) a r x (BitsSpec.extract off len x) in
513
let lemma exact (s:int) : unit
514
requires { mem s r }
515
ensures { exists x. mem x a /\ s = BitsSpec.extract off len x }
516
= let x = BitsSpec.update off len s a.u in
517
let lemma bit (p:int) : unit
518
requires { 0 <= p }
519
ensures { Zbit.bittest a.u p -> Zbit.bittest x p }
520
ensures { Zbit.bittest x p -> Zbit.bittest a.l p }
521
= BitsSpec.bit_update off len s a.u p; inv_bit a p;
522
if len > 0 && off <= p && p < off + len then begin
523
mem_bits s r (p - off); bits 0 (p - off)
524
end in
525
let lemma back (i:int) : unit
526
requires { 0 <= i }
527
ensures { Zbit.bittest (BitsSpec.extract off len x) i <-> Zbit.bittest s i }
528
= bits x i; mem_bits s r i;
529
if i < len then begin
530
if i + off < 0 then begin
531
Zbit.bittest_neg a.l (i + off); Zbit.bittest_neg x (i + off)
532
end else BitsSpec.bit_update off len s a.u (i + off)
533
end in
534
Zbit.ext_bittest s (BitsSpec.extract off len x);
535
assert { mem x a /\ s = BitsSpec.extract off len x } in
536
r

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)
543
let
signed_extract
(off len:int) (a:t) : t
544
requires { SafeBits.signed_extract_ok off len }
545
ensures { sound1 mem (fun x -> BitsSpec.signed_extract off len x) a result }
546
= let rl = SafeBits.signed_extract off len a.l in
547
let ru = SafeBits.signed_extract off len a.u in
548
let lemma bits (x i:int) : unit
549
requires { 0 <= i }
550
ensures { Zbit.bittest ru i <-> (len > 0 /\ Zbit.bittest a.u (off + min i (len - 1))) }
551
ensures { Zbit.bittest rl i <-> (len > 0 /\ Zbit.bittest a.l (off + min i (len - 1))) }
552
ensures { Zbit.bittest (BitsSpec.signed_extract off len x) i <->
553
(len > 0 /\ Zbit.bittest x (off + min i (len - 1))) }
554
= BitsSpec.bit_signed_extract off len a.u i; BitsSpec.bit_signed_extract off len a.l i;
555
BitsSpec.bit_signed_extract off len x i in
556
image_subset (fun _ -> len > 0) (fun i -> off + min i (len - 1)) a rl ru;
557
let r = { l = rl; u = ru } in
558
let lemma sound (x:int) : unit
559
requires { mem x a }
560
ensures { mem (BitsSpec.signed_extract off len x) r }
561
= sound_map (fun _ -> len > 0) (fun i -> off + min i (len - 1)) a r x
562
(BitsSpec.signed_extract off len x) in
563
r

BitsSpec.update

  Valid (3.4s) (colibri2 48) (cvc5 4) (split_vc 2) (depth 2)
567
let
update
(off len:int) (src dst:t) : t
568
requires { SafeBits.update_ok off len }
569
ensures { sound2 mem (fun xs xd -> BitsSpec.update off len xs xd) src dst result }
570
ensures { complete2 mem (fun xs xd -> BitsSpec.update off len xs xd) src dst result }
571
= let rl = SafeBits.update off len src.l dst.l in
572
let ru = SafeBits.update off len src.u dst.u in
573
let lemma sub (i:int) : unit
574
requires { 0 <= i }
575
ensures { Zbit.bittest ru i -> Zbit.bittest rl i }
576
= BitsSpec.bit_update off len src.u dst.u i; BitsSpec.bit_update off len src.l dst.l i;
577
if len > 0 && off <= i && i < off + len then inv_bit src (i - off) else inv_bit dst i in
578
let r = { l = rl; u = ru } in
579
let lemma bit (xs xd i:int) : unit
580
requires { 0 <= i }
581
requires { mem xs src /\ mem xd dst }
582
ensures { Zbit.bittest r.u i -> Zbit.bittest (BitsSpec.update off len xs xd) i }
583
ensures { Zbit.bittest (BitsSpec.update off len xs xd) i -> Zbit.bittest r.l i }
584
= BitsSpec.bit_update off len src.u dst.u i; BitsSpec.bit_update off len src.l dst.l i;
585
BitsSpec.bit_update off len xs xd i;
586
if len > 0 && off <= i && i < off + len then mem_bits xs src (i - off)
587
else mem_bits xd dst i in
588
let lemma exact (s:int) : unit
589
requires { mem s r }
590
ensures { exists xs xd. mem xs src /\ mem xd dst /\ s = BitsSpec.update off len xs xd }
591
= let xs1 = BitsSpec.update 0 len (BitsSpec.extract off len s) src.u in
592
let xs = BitsSpec.update 0 (max (- off) 0) src.u xs1 in
593
let xd = BitsSpec.update off len (Zbit.asr dst.u off) s in
594
let lemma xbits (p:int) : unit
595
requires { 0 <= p }
596
ensures { Zbit.bittest xs1 p <-> (if len > 0 /\ p < len then Zbit.bittest s (p + off) else Zbit.bittest src.u p) }
597
ensures { Zbit.bittest xs p <-> (if p < max (- off) 0 then Zbit.bittest src.u p else Zbit.bittest xs1 p) }
598
ensures { Zbit.bittest xd p <-> (if len > 0 /\ off <= p < off + len then Zbit.bittest dst.u p else Zbit.bittest s p) }
599
= BitsSpec.bit_update 0 len (BitsSpec.extract off len s) src.u p;
600
BitsSpec.bit_extract off len s p;
601
BitsSpec.bit_update 0 (max (- off) 0) src.u xs1 p;
602
BitsSpec.bit_update off len (Zbit.asr dst.u off) s p in
603
let lemma src_bits (i:int) : unit
604
requires { 0 <= i }
605
ensures { Zbit.bittest src.u i -> Zbit.bittest xs i }
606
ensures { Zbit.bittest xs i -> Zbit.bittest src.l i }
607
= xbits i; inv_bit src i;
608
if i >= max (- off) 0 && len > 0 && i < len then begin
609
BitsSpec.bit_update off len src.u dst.u (i + off);
610
BitsSpec.bit_update off len src.l dst.l (i + off);
611
mem_bits s r (i + off)
612
end in
613
let lemma dst_bits (p:int) : unit
614
requires { 0 <= p }
615
ensures { Zbit.bittest dst.u p -> Zbit.bittest xd p }
616
ensures { Zbit.bittest xd p -> Zbit.bittest dst.l p }
617
= xbits p; inv_bit dst p;
618
BitsSpec.bit_update off len src.u dst.u p; BitsSpec.bit_update off len src.l dst.l p;
619
mem_bits s r p;
620
if len > 0 && off <= p && p < off + len then Zbit.def_asr dst.u off (p - off) in
621
let lemma back (p:int) : unit
622
requires { 0 <= p }
623
ensures { Zbit.bittest (BitsSpec.update off len xs xd) p <-> Zbit.bittest s p }
624
= BitsSpec.bit_update off len xs xd p; xbits p;
625
if len > 0 && off <= p && p < off + len then xbits (p - off) in
626
Zbit.ext_bittest s (BitsSpec.update off len xs xd);
627
assert { mem xs src /\ mem xd dst /\ s = BitsSpec.update off len xs xd } in
628
r
629
630
end