Common — library colibrilib.zbit_model — module ZbitModel
6
module ZbitModel : colibrilib.zarith.Zbit

Implemented

7
use int.Int
8
use int.MinMax
9
use int.EuclideanDivision
10
use int.Power
11
12
function
pow2
(n:int) : int = power 2 n
13
14
predicate
bittest
(x i:int) = 0 <= i /\ (mod x (pow2 (i+1))) >= pow2 i
15
16
predicate
subset
(a:int) (b:int) = forall i. bittest a i -> bittest b i
17
Valid (24ms) (colibri2)
18
lemma
pow2_pos
: forall i. 0 <= i -> 0 < pow2 i Valid (26ms) (colibri2)
19
lemma
pow2_s
: forall i. 0 <= i -> pow2 (i+1) = 2 * pow2 i Valid (16ms) (colibri2)
20
lemma
pow2_ge_2
: forall i. 1 <= i -> 2 <= pow2 i Valid (40ms) (colibri2)
21
let rec lemma
pow2_add
(a b:int) : unit
22
requires { 0 <= a }
23
requires { 0 <= b }
24
ensures { pow2 (a+b) = pow2 a * pow2 b }
25
variant { b }
26
=
27
if b = 0 then assert { pow2 0 = 1 }
28
else begin
29
pow2_s (a+b-1);
30
pow2_add a (b-1);
31
pow2_s (b-1)
32
end Valid (26ms) (colibri2)
33
let rec lemma
pow2_le
(a b:int) : unit
34
requires { 0 <= a <= b }
35
ensures { pow2 a <= pow2 b }
36
variant { b - a }
37
=
38
if a = b then ()
39
else begin
40
pow2_s (b-1);
41
pow2_le a (b-1)
42
end Valid (1.1s) (cvc5) (split_vc) (depth 1)
43
lemma
mod_twice
: forall x y. 0 < y -> mod (2*x) (2*y) = 2 * mod x y
44
Valid (59ms) (colibri2)
45
let lemma
even_bittest
(x i:int) : unit
46
requires { 0 <= i }
47
ensures { bittest (2*x) i = (if i = 0 then False else bittest x (i-1)) }
48
=
49
if i = 0 then ()
50
else begin
51
pow2_s i;
52
mod_twice x (pow2 i);
53
pow2_s (i-1)
54
end
55
Valid (249ms) (colibri2)
56
let lemma
odd_bittest
(x i:int) : unit
57
requires { 0 <= i }
58
ensures { bittest (2*x+1) i = (if i = 0 then True else bittest x (i-1)) }
59
=
60
if i = 0 then ()
61
else begin
62
pow2_s i;
63
mod_twice x (pow2 i);
64
pow2_s (i-1)
65
end
66
Valid (24ms) (colibri2)
67
lemma
bittest_neg
: forall x i. i < 0 -> not (bittest x i) Valid (32ms) (colibri2)
68
lemma
bittest_0
: forall i. not (bittest 0 i) Valid (39ms) (colibri2)
69
lemma
bittest_1
: forall i. bittest 1 i = (i = 0)
70
Valid (56ms) (colibri2)
71
let lemma
bittest_div2
(x i:int) : unit
72
requires { 0 <= i }
73
ensures { bittest (div x 2) i = bittest x (i+1) }
74
=
75
let r = mod x 2 in
76
if r = 0 then begin
77
even_bittest (div x 2) (i+1);
78
end else begin
79
odd_bittest (div x 2) (i+1);
80
end
81
Valid (64ms) (colibri2)
82
let rec lemma
bits_zero
(z:int) : unit
83
requires { forall i. 0 <= i -> not (bittest z i) }
84
ensures { z = 0 }
85
variant { if z >= 0 then z else -z }
86
=
87
if z = 0 then ()
88
else begin
89
assert { not (bittest z 0) };
90
bits_zero (div z 2)
91
end
92
Valid (32ms) (colibri2)
93
let lemma
bittest_parity
(x:int) : unit
94
ensures { bittest x 0 <-> (mod x 2 = 1) }
95
=
96
()
97
Valid (2.5s) (colibri2 7) (split_vc) (depth 1)
98
let rec lemma
ext_bittest_pos
(x y:int) : unit
99
requires { 0 < x }
100
requires { forall i. 0 <= i -> bittest x i = bittest y i }
101
ensures { x = y }
102
variant { x }
103
=
104
let xh = div x 2 in
105
let yh = div y 2 in
106
bittest_parity x;
107
bittest_parity y;
108
if xh > 0 then begin
109
ext_bittest_pos xh yh
110
end else begin
111
bits_zero yh
112
end
113
Valid (395ms) (colibri2)
114
let rec lemma
bits_minus_one
(z:int) : unit
115
requires { forall i. 0 <= i -> bittest z i }
116
ensures { z = -1 }
117
variant { if z >= 0 then z else -z }
118
=
119
bittest_parity z;
120
if div z 2 <> z then bits_minus_one (div z 2)
121
Valid (309ms) (colibri2 7) (split_vc) (depth 1)
122
let rec lemma
ext_bittest_neg
(x y:int) : unit
123
requires { x < 0 }
124
requires { forall i. 0 <= i -> bittest x i = bittest y i }
125
ensures { x = y }
126
variant { -x }
127
=
128
let xh = div x 2 in
129
let yh = div y 2 in
130
bittest_parity x;
131
bittest_parity y;
132
if xh <> x then begin
133
ext_bittest_neg xh yh
134
end else begin
135
bits_minus_one y
136
end
137
Valid (46ms) (colibri2)
138
let lemma
ext_bittest
(x y:int) : unit
139
requires { forall i. 0 <= i -> bittest x i = bittest y i }
140
ensures { x = y }
141
=
142
if x > 0 then ext_bittest_pos x y
143
else if x = 0 then begin
144
bits_zero y
145
end
146
else ext_bittest_neg x y
147
148
function
asr
(x offset:int) : int =
149
if 0 <= offset then div x (pow2 offset) else x * pow2 (-offset)
150
151
function
lsl
(x offset:int) : int = asr x (-offset)
152
153
function
mask
(k:int) : int = lsl 1 k - 1
154
Valid (32ms) (colibri2)
155
let rec function
numbits
(x:int) : int =
156
variant { if x < 0 then -x else x }
157
if x = 0 then 0
158
else if x < 0 then 1 + numbits (div (-x) 2)
159
else 1 + numbits (div x 2)
160
Valid (29ms) (colibri2)
161
lemma
asr_eq
: forall x. asr x 0 = x
162
Valid (19ms) (colibri2)
163
let ghost
asr_div
(x n:int) : unit
164
requires { 0 <= n }
165
ensures { asr x n = div x (power 2 n) }
166
= ()
167
Valid (32ms) (colibri2)
168
let ghost
lsl_mul
(x n:int) : unit
169
requires { 0 <= n }
170
ensures { lsl x n = x * power 2 n }
171
= if n = 0 then assert { div x (pow2 0) = x }
172
Valid (25ms) (colibri2)
173
let lemma
asr_gt
(x offset:int) : unit
174
requires { 0 < x /\ offset < 0 }
175
ensures { x < asr x offset }
176
=
177
pow2_ge_2 (-offset);
178
assert { x * 2 <= x * pow2 (-offset) }
179
Valid (753ms) (colibri2)
180
let lemma
div_twice
(x y:int) : unit
181
requires { 0 < y }
182
ensures { div x (2*y) = div (div x y) 2 }
183
=
184
let q = div x y in
185
let r = mod x y in
186
assert { x = 2*y*(div q 2) + y*(mod q 2) + r }
187
Valid (132ms) (colibri2)
188
let rec lemma
bittest_div_pow2
(x k i:int) : unit
189
requires { 0 <= k }
190
requires { 0 <= i }
191
ensures { bittest (div x (pow2 k)) i = bittest x (i+k) }
192
variant { k }
193
=
194
if k = 0 then ()
195
else begin
196
pow2_s (k-1);
197
div_twice x (pow2 (k-1));
198
bittest_div2 (div x (pow2 (k-1))) i;
199
bittest_div_pow2 x (k-1) (i+1)
200
end
201
Valid (134ms) (colibri2)
202
let rec lemma
bittest_mul_pow2
(x k i:int) : unit
203
requires { 0 <= k }
204
ensures { bittest (x * pow2 k) i <-> (i >= k /\ bittest x (i-k)) }
205
variant { k }
206
=
207
if k = 0 then ()
208
else begin
209
pow2_s (k-1);
210
bittest_mul_pow2 (x*2) (k-1) i;
211
let j = i - (k-1) in
212
if j >= 0 then even_bittest x j
213
end
214
Valid (49ms) (colibri2)
215
let lemma
def_asr
(x offset i:int) : unit
216
requires { i >= 0 }
217
ensures { bittest (asr x offset) i = bittest x (i+offset) }
218
=
219
if 0 <= offset then begin
220
bittest_div_pow2 x offset i
221
end else begin
222
bittest_mul_pow2 x (-offset) i
223
end
224
Valid (24ms) (colibri2)
225
let lemma
mask_pow2
(k:int) : unit
226
requires { 0 <= k }
227
ensures { mask k = pow2 k - 1 }
228
=
229
()
230
Valid (28ms) (colibri2)
231
let lemma
mask_nonneg
(k:int) : ()
232
requires { 0 <= k }
233
ensures { 0 <= mask k } =
234
if k = 0 then asr_eq 1
235
else asr_gt 1 (-k)
236
237
Valid (229ms) (colibri2)
238
let lemma
bittest_pred_pow2
(k i:int) : unit
239
requires { 0 <= i < k }
240
ensures { bittest (pow2 k - 1) i }
241
=
242
pow2_add (i+1) (k - i - 1);
243
assert { pow2 k - 1 = pow2 (i+1) * (pow2 (k - i - 1) - 1) + (pow2 (i+1) - 1) };
244
pow2_s i
245
Valid (1.1s) (colibri2)
246
let lemma
bittest_pred_pow2_high
(k i:int) : unit
247
requires { 0 <= k <= i }
248
ensures { not (bittest (pow2 k - 1) i) }
249
=
250
pow2_le k (i+1);
251
pow2_le k i
252
Valid (26ms) (colibri2)
253
let lemma
mask_bits
(k i:int) : unit
254
requires { 0 <= k }
255
requires { 0 <= i < k }
256
ensures { bittest (mask k) i }
257
=
258
mask_pow2 k;
259
bittest_pred_pow2 k i
260
Valid (19ms) (colibri2)
261
let lemma
mask_bits_high
(k i:int) : unit
262
requires { 0 <= k }
263
requires { i >= k }
264
ensures { not (bittest (mask k) i) }
265
=
266
mask_pow2 k;
267
bittest_pred_pow2_high k i
268
Valid (37ms) (colibri2)
269
let lemma
numbits_neg
(x:int) : unit
270
requires { x < 0 }
271
ensures { numbits x = numbits (-x) }
272
=
273
()
274
Valid (36ms) (colibri2)
275
let rec lemma
numbits_nonneg
(x:int) : unit
276
requires { 0 <= x }
277
ensures { 0 <= numbits x }
278
variant { x }
279
=
280
if x = 0 then assert { numbits 0 = 0 }
281
else begin
282
numbits_nonneg (div x 2)
283
end
284
Valid (51ms) (colibri2)
285
let rec lemma
numbits_ge_1
(x:int) : unit
286
requires { 1 <= x }
287
ensures { 1 <= numbits x }
288
variant { x }
289
=
290
if x = 1 then assert { numbits 1 = 1 }
291
else begin
292
numbits_ge_1 (div x 2)
293
end
294
Valid (67ms) (colibri2)
295
let rec lemma
numbits_bound
(x:int) : unit
296
requires { 0 <= x }
297
ensures { x < pow2 (numbits x) }
298
variant { x }
299
=
300
if x = 0 then assert { numbits 0 = 0 }
301
else begin
302
numbits_bound (div x 2);
303
numbits_nonneg (div x 2);
304
pow2_s (numbits (div x 2))
305
end
306
Valid (130ms) (colibri2)
307
let rec lemma
numbits_lower
(x:int) : unit
308
requires { x > 0 }
309
ensures { pow2 (numbits x - 1) <= x }
310
variant { x }
311
=
312
if x = 1 then assert { numbits 1 = 1 }
313
else begin
314
numbits_lower (div x 2);
315
numbits_ge_1 (div x 2);
316
pow2_s (numbits (div x 2) - 1)
317
end
318
Valid (98ms) (colibri2)
319
let rec lemma
numbits_pow2
(n:int) : unit
320
requires { 0 <= n }
321
ensures { numbits (pow2 n) = n + 1 }
322
variant { n }
323
=
324
if n = 0 then assert { numbits 1 = 1 }
325
else begin
326
pow2_s (n-1);
327
numbits_pow2 (n-1)
328
end
329
Valid (32ms) (colibri2)
330
let lemma
numbits_top_bit
(x:int) : unit
331
requires { x > 0 }
332
ensures { bittest x (numbits x - 1) }
333
=
334
numbits_ge_1 x;
335
numbits_lower x;
336
numbits_bound x
337
Valid (1.1s) (colibri2)
338
let lemma
numbits_high_clear
(x i:int) : unit
339
requires { x > 0 }
340
requires { i >= numbits x }
341
ensures { not (bittest x i) }
342
=
343
numbits_bound x;
344
pow2_le (numbits x) i;
345
pow2_le (numbits x) (i+1)
346
Valid (78ms) (colibri2)
347
let rec lemma
numbits_le
(x n:int) : unit
348
requires { 0 <= x }
349
requires { 0 <= n }
350
requires { x < pow2 n }
351
ensures { numbits x <= n }
352
variant { x }
353
=
354
if x = 0 then assert { numbits 0 = 0 }
355
else begin
356
pow2_s (n-1);
357
numbits_le (div x 2) (n-1)
358
end
359
Valid (70ms) (colibri2)
360
let rec lemma
numbits_ge
(x n:int) : unit
361
requires { 0 <= x }
362
requires { 0 <= n }
363
requires { pow2 n <= x }
364
ensures { n + 1 <= numbits x }
365
variant { x }
366
=
367
if n = 0 then begin
368
numbits_ge_1 x
369
end else begin
370
pow2_s (n-1);
371
numbits_ge (div x 2) (n-1)
372
end
373
Valid (34ms) (colibri2)
374
lemma
numbits_pos
: forall x. x > 0 ->
375
bittest x (numbits x - 1) /\
376
(forall i. i >= numbits x -> not (bittest x i))
377
Valid (42ms) (colibri2)
378
let lemma
numbits_lsl
(n:int) : unit
379
requires { 0 <= n }
380
ensures { numbits (lsl 1 n) = n + 1 }
381
=
382
()
383
Valid (37ms) (colibri2)
384
let lemma
mask_numbits
(k:int) : unit
385
requires { 0 <= k }
386
ensures { numbits (mask k) = k }
387
=
388
mask_pow2 k;
389
if k = 0 then assert { mask 0 = 0 }
390
else begin
391
pow2_pos k;
392
numbits_le (pow2 k - 1) k;
393
pow2_s (k-1);
394
pow2_pos (k-1);
395
numbits_ge (pow2 k - 1) (k-1)
396
end
397
Valid (33ms) (colibri2)
398
let lemma
numbits_ge_pos
(x y:int) : unit
399
requires { 0 <= x }
400
requires { 0 <= y }
401
requires { x <= y }
402
ensures { numbits x <= numbits y }
403
=
404
numbits_bound y;
405
numbits_nonneg y;
406
numbits_le x (numbits y)
407
Valid (29ms) (colibri2)
408
let lemma
numbits_gt_pos
(x y:int) : unit
409
requires { 0 <= x }
410
requires { 0 <= y }
411
requires { numbits x < numbits y }
412
ensures { x < y }
413
=
414
if not (x < y) then begin
415
numbits_ge_pos y x
416
end
417
Valid (48ms) (colibri2)
418
let lemma
numbits_lt_lsl
(x n:int) : unit
419
requires { 0 <= x }
420
requires { x < lsl 1 n }
421
ensures { numbits x <= n }
422
=
423
if n < 0 then begin
424
pow2_ge_2 (-n)
425
end;
426
numbits_le x n
427
Valid (58ms) (colibri2)
428
let lemma
numbits_mul_pow2
(x k:int) : unit
429
requires { 0 < x }
430
requires { 0 <= k }
431
ensures { numbits (x * pow2 k) = numbits x + k }
432
=
433
numbits_lower x;
434
numbits_bound x;
435
numbits_nonneg x;
436
pow2_add (numbits x - 1) k;
437
assert { pow2 (numbits x - 1) * pow2 k <= x * pow2 k };
438
pow2_add (numbits x) k;
439
numbits_ge (x * pow2 k) (numbits x - 1 + k);
440
numbits_le (x * pow2 k) (numbits x + k)
441
Valid (15ms) (colibri2)
442
let lemma
div_lt
(a b q:int) : unit
443
requires { 0 < b /\ a < b * q }
444
ensures { div a b < q }
445
=
446
if div a b >= q then assert { b * div a b >= b * q }
447
Valid (36ms) (colibri2)
448
let lemma
div_ge
(a b q:int) : unit
449
requires { 0 < b /\ b * q <= a }
450
ensures { q <= div a b }
451
=
452
if div a b < q then assert { b * div a b <= b * q - b }
453
Valid (121ms) (colibri2)
454
let lemma
numbits_asr_pow2
(x k:int) : unit
455
requires { 0 < x }
456
requires { 0 <= k }
457
ensures { numbits (div x (pow2 k)) = max 0 (numbits x - k) }
458
=
459
numbits_bound x;
460
numbits_lower x;
461
numbits_nonneg x;
462
if numbits x - k <= 0 then begin
463
pow2_le (numbits x) k
464
end else begin
465
pow2_add k (numbits x - 1 - k);
466
div_ge x (pow2 k) (pow2 (numbits x - 1 - k));
467
pow2_add k (numbits x - k);
468
div_lt x (pow2 k) (pow2 (numbits x - k));
469
numbits_ge (div x (pow2 k)) (numbits x - 1 - k);
470
numbits_le (div x (pow2 k)) (numbits x - k)
471
end
472
Valid (27ms) (colibri2)
473
let lemma
asr_nonneg
(x offset:int) : unit
474
requires { 0 <= x }
475
ensures { 0 <= asr x offset }
476
=
477
()
478
Valid (227ms) (colibri2)
479
let lemma
asr_numbits
(x offset:int) : unit
480
requires { 0 < x }
481
ensures { numbits (asr x offset) = max 0 (numbits x - offset) }
482
=
483
()
484
Valid (380ms) (cvc4)
485
let rec function
land
(x y:int) : int
486
variant { max (if x < 0 then -x else x) (if y < 0 then -y else y) }
487
= if x = -1 then y
488
else if y = -1 then x
489
else if x = 0 || y = 0 then 0
490
else let xh = div x 2 in
491
let yh = div y 2 in
492
let b = if mod x 2 = 1 && mod y 2 = 1 then 1 else 0 in
493
b + 2 * land xh yh
494
Valid (2.0s) (colibri2 21) (split_vc 5) (depth 4)
495
let rec lemma
def_land
(x y i:int) : unit
496
requires { 0 <= i }
497
ensures { bittest (land x y) i <-> (bittest x i /\ bittest y i) }
498
variant { i }
499
=
500
if x = -1 then ()
501
else if y = -1 then ()
502
else if x = 0 || y = 0 then ()
503
else begin
504
let xh = div x 2 in
505
let yh = div y 2 in
506
let b = if mod x 2 = 1 && mod y 2 = 1 then 1 else 0 in
507
assert { land x y = b + 2 * land xh yh };
508
if i = 0 then begin
509
bittest_parity (land x y);
510
bittest_parity x;
511
bittest_parity y
512
end else begin
513
if b = 1 then odd_bittest (land xh yh) i else even_bittest (land xh yh) i;
514
if mod x 2 = 1 then odd_bittest xh i else even_bittest xh i;
515
if mod y 2 = 1 then odd_bittest yh i else even_bittest yh i;
516
def_land xh yh (i-1)
517
end
518
end
519
Valid (665ms) (cvc5)
520
let rec lemma
land_nonneg
(x y:int) : unit
521
requires { 0 <= x /\ 0 <= y }
522
ensures { 0 <= land x y }
523
variant { max x y }
524
=
525
if x = 0 || y = 0 then ()
526
else begin
527
let xh = div x 2 in
528
let yh = div y 2 in
529
land_nonneg xh yh
530
end
531
Valid (108ms) (colibri2)
532
let rec lemma
land_nonneg_l
(x y:int) : unit
533
requires { 0 <= x }
534
ensures { 0 <= land x y }
535
variant { x }
536
=
537
if x = 0 || y = -1 || y = 0 then ()
538
else begin
539
let xh = div x 2 in
540
let yh = div y 2 in
541
land_nonneg_l xh yh
542
end
543
Valid (697ms) (cvc5)
544
let rec lemma
land_le
(x y:int) : unit
545
requires { 0 <= x /\ 0 <= y }
546
ensures { land x y <= y }
547
variant { max x y }
548
=
549
if x = 0 || y = 0 then ()
550
else begin
551
let xh = div x 2 in
552
let yh = div y 2 in
553
land_le xh yh
554
end
555
Valid (393ms) (colibri2)
556
let rec function
lor
(x y:int) : int
557
variant { max (if x < 0 then -x else x) (if y < 0 then -y else y) }
558
= if x = -1 || y = -1 then -1
559
else if x = 0 then y
560
else if y = 0 then x
561
else let xh = div x 2 in
562
let yh = div y 2 in
563
let b = if mod x 2 = 1 || mod y 2 = 1 then 1 else 0 in
564
b + 2 * lor xh yh
565
Valid (502ms) (colibri2)
566
let rec lemma
def_lor
(x y i:int) : unit
567
requires { 0 <= i }
568
ensures { bittest (lor x y) i <-> (bittest x i \/ bittest y i) }
569
variant { i }
570
=
571
if x = -1 then ()
572
else if y = -1 then ()
573
else if x = 0 then ()
574
else if y = 0 then ()
575
else begin
576
let xh = div x 2 in
577
let yh = div y 2 in
578
let b = if mod x 2 = 1 || mod y 2 = 1 then 1 else 0 in
579
if i = 0 then begin
580
bittest_parity (lor x y);
581
bittest_parity x;
582
bittest_parity y
583
end else begin
584
if b = 1 then odd_bittest (lor xh yh) i else even_bittest (lor xh yh) i;
585
if mod x 2 = 1 then odd_bittest xh i else even_bittest xh i;
586
if mod y 2 = 1 then odd_bittest yh i else even_bittest yh i;
587
def_lor xh yh (i-1)
588
end
589
end
590
Valid (671ms) (cvc5)
591
let rec lemma
lor_nonneg
(x y:int) : unit
592
requires { 0 <= x /\ 0 <= y }
593
ensures { 0 <= lor x y }
594
variant { max x y }
595
=
596
if x = 0 || y = 0 then ()
597
else begin
598
let xh = div x 2 in
599
let yh = div y 2 in
600
lor_nonneg xh yh
601
end
602
Valid (169ms) (cvc5)
603
let rec lemma
lor_le
(x y:int) : unit
604
requires { 0 <= x /\ 0 <= y }
605
ensures { y <= lor x y }
606
variant { max x y }
607
=
608
if x = 0 || y = 0 then ()
609
else begin
610
let xh = div x 2 in
611
let yh = div y 2 in
612
lor_le xh yh
613
end
614
Valid (1.2s) (colibri2 5) (split_vc) (depth 1)
615
let rec lemma
lor_numbits
(x y:int) : unit
616
requires { 0 <= x /\ 0 <= y }
617
ensures { numbits (lor x y) = max (numbits x) (numbits y) }
618
variant { max x y }
619
=
620
if x = 0 then ()
621
else if y = 0 then ()
622
else begin
623
let xh = div x 2 in
624
let yh = div y 2 in
625
lor_numbits xh yh
626
end
627
628
let function
lnot
(x:int) : int = -x - 1
629
Valid (184ms) (colibri2)
630
let rec lemma
def_lnot
(x i:int) : unit
631
requires { 0 <= i }
632
ensures { bittest (lnot x) i <-> not (bittest x i) }
633
variant { i }
634
=
635
if i = 0 then begin
636
bittest_parity x;
637
bittest_parity (lnot x)
638
end else begin
639
let q = div x 2 in
640
if mod x 2 = 0 then begin
641
odd_bittest (-q-1) i;
642
even_bittest q i;
643
def_lnot q (i-1)
644
end else begin
645
even_bittest (-q-1) i;
646
odd_bittest q i;
647
def_lnot q (i-1)
648
end
649
end
650
651
function
set
(x:int) (offset:int) : int =
652
lor x (lsl 1 offset)
653
Valid (263ms) (colibri2)
654
let lemma
def_set
(x offset i:int) : unit
655
requires { 0 <= i }
656
ensures { bittest (set x offset) i = (i = offset \/ bittest x i) }
657
=
658
def_lor x (lsl 1 offset) i;
659
assert { bittest (lsl 1 offset) i <-> i = offset }
660
661
662
function
unset
(x:int) (offset:int) : int = land x (lnot (lsl 1 offset))
663
let function
lxor
(x y:int) : int = lor (land x (lnot y)) (land (lnot x) y)
664
665
function
change
(x:int) (offset:int) (v:bool) : int =
666
if v then set x offset else unset x offset
667
Valid (215ms) (colibri2)
668
let lemma
def_change
(x offset i:int) (v:bool) : unit
669
requires { 0 <= i }
670
ensures { bittest (change x offset v) i <-> (if i = offset then v else bittest x i) }
671
=
672
def_asr 1 (- offset) i;
673
if v then def_lor x (lsl 1 offset) i
674
else begin
675
def_land x (lnot (lsl 1 offset)) i;
676
def_lnot (lsl 1 offset) i
677
end
678
Valid (46ms) (colibri2)
679
let lemma
change_nonneg
(x offset:int) (v:bool) : unit
680
requires { 0 <= x }
681
ensures { 0 <= change x offset v }
682
=
683
if v then begin
684
lor_nonneg x (lsl 1 offset)
685
end else begin
686
land_nonneg_l x (lnot (lsl 1 offset))
687
end
688
Valid (176ms) (colibri2)
689
let rec ghost function
of_bits
(f: int -> bool) (n:int) : int
690
variant { n }
691
ensures { 0 <= result }
692
ensures { forall i. 0 <= i -> (bittest result i <-> (i < n /\ f i)) }
693
= if n <= 0 then 0
694
else begin
695
let r = of_bits f (n-1) in
696
change_nonneg r (n-1) (f (n-1));
697
change r (n-1) (f (n-1))
698
end
699
Valid (48ms) (colibri2)
700
let lemma
of_bits_nonneg
(f: int -> bool) (n:int) : unit
701
ensures { 0 <= of_bits f n }
702
= ()
703
Valid (62ms) (colibri2)
704
let lemma
def_of_bits
(f: int -> bool) (n i:int) : unit
705
requires { 0 <= i }
706
ensures { bittest (of_bits f n) i <-> (i < n /\ f i) }
707
= ()
708
Valid (39ms) (colibri2)
709
let lemma
unset_nonneg
(x offset:int) : unit
710
requires { 0 <= x }
711
ensures { 0 <= unset x offset }
712
=
713
land_nonneg_l x (lnot (lsl 1 offset))
714
Valid (800ms) (colibri2 7) (split_vc) (depth 1)
715
let lemma
numbits_unset_le
(x offset:int) : unit
716
requires { 0 <= x }
717
requires { 0 <= offset }
718
ensures { numbits (unset x offset) <= numbits x }
719
=
720
if x = 0 then ()
721
else begin
722
assert { forall j. 0 <= j -> bittest (unset x offset) j -> bittest x j };
723
if numbits (unset x offset) > numbits x then begin
724
assert { unset x offset > 0 };
725
assert { numbits (unset x offset) - 1 >= numbits x };
726
assert { bittest (unset x offset) (numbits (unset x offset) - 1) };
727
assert { bittest x (numbits (unset x offset) - 1) };
728
assert { not bittest x (numbits (unset x offset) - 1) }
729
end
730
end
731
Valid (268ms) (colibri2)
732
let lemma
land_numbits
(x y:int) : unit
733
requires { 0 <= x /\ 0 <= y }
734
ensures { numbits (land x y) <= min (numbits x) (numbits y) }
735
=
736
land_nonneg x y;
737
land_le x y;
738
land_le y x;
739
ext_bittest (land y x) (land x y);
740
numbits_ge_pos (land x y) y;
741
numbits_ge_pos (land x y) x
742
Valid (58ms) (colibri2)
743
let lemma
numbits_set
(x offset:int) : unit
744
requires { 0 <= x /\ 0 <= offset }
745
ensures { numbits (set x offset) = max (numbits x) (offset+1) }
746
=
747
numbits_lsl offset;
748
lor_numbits x (lsl 1 offset)
749
Valid (51ms) (colibri2)
750
let lemma
numbits_change_true
(x offset:int) : unit
751
requires { 0 <= x /\ 0 <= offset }
752
ensures { numbits (change x offset True) = max (numbits x) (offset+1) }
753
=
754
numbits_set x offset
755
Valid (60ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
756
let lemma
bittest_sub_lsl
(x s j:int) : unit
757
requires { 0 <= j < s }
758
ensures { bittest (x - lsl 1 s) j <-> bittest x j }
759
=
760
mask_pow2 s;
761
pow2_add (j+1) (s-j-1);
762
pow2_pos (j+1);
763
assert { x - lsl 1 s = pow2 (j+1) * (- pow2 (s-j-1)) + x }
764
Valid (76ms) (colibri2)
765
let lemma
bittest_sub_lsl_high
(x s j:int) : unit
766
requires { 0 <= x /\ 0 <= s <= j }
767
requires { x < lsl 1 s }
768
ensures { bittest (x - lsl 1 s) j }
769
=
770
mask_pow2 s;
771
pow2_le s j;
772
pow2_s j;
773
pow2_pos s;
774
let y = x - pow2 s in
775
assert { - pow2 (j+1) <= y < 0 };
776
assert { pow2 (j+1) * (-1) <= y < pow2 (j+1) * (-1) + pow2 (j+1) };
777
assert { div y (pow2 (j+1)) = -1 };
778
assert { mod y (pow2 (j+1)) = y + pow2 (j+1) }
779
780
predicate
carry
(x y i: int) = mod x (pow2 i) + mod y (pow2 i) >= pow2 i
781
Valid (58ms) (colibri2)
782
let lemma
carry_0
(x y: int) : unit
783
ensures { not (carry x y 0) }
784
= assert { pow2 0 = 1 }

The bit i is the parity of the quotient by 2^i

    Valid (57ms) (colibri2)
787
let lemma
bittest_quot
(x i: int) : unit
788
requires { 0 <= i }
789
ensures { bittest x i <-> mod (div x (pow2 i)) 2 = 1 }
790
=
791
bittest_div_pow2 x i 0;
792
bittest_parity (div x (pow2 i))
793
Valid (56ms) (colibri2)
794
let lemma
mod_split
(x p: int) : unit
795
requires { 0 < p }
796
ensures { mod x (2 * p) = mod x p + p * mod (div x p) 2 }
797
=
798
let q = div x p in
799
assert { x = p * q + mod x p };
800
assert { q = 2 * div q 2 + mod q 2 };
801
assert { p * q = 2 * p * div q 2 + p * mod q 2 };
802
assert { x = 2 * p * div q 2 + (mod x p + p * mod q 2) };
803
assert { 0 <= mod x p + p * mod q 2 < 2 * p }
804
Valid (703ms) (cvc5)
805
let lemma
div_add
(x y p: int) : unit
806
requires { 0 < p }
807
ensures { div (x + y) p = div x p + div y p + (if mod x p + mod y p >= p then 1 else 0) }
808
=
809
let c = if mod x p + mod y p >= p then 1 else 0 in
810
let q = div x p + div y p + c in
811
Div_mod x p;
812
Div_mod y p;
813
assert { x + y = q * p + (mod x p + mod y p - p * c) };
814
assert { 0 <= mod x p + mod y p - p * c < p };
815
Div_unique (x + y) p q
816
Valid (86ms) (colibri2)
817
let lemma
carry_succ
(x y i: int) : unit
818
requires { 0 <= i }
819
ensures { carry x y (i+1) <-> ((bittest x i /\ bittest y i) \/ ((bittest x i \/ bittest y i) /\ carry x y i)) }
820
=
821
let p = pow2 i in
822
pow2_s i;
823
mod_split x p;
824
mod_split y p;
825
bittest_quot x i;
826
bittest_quot y i
827
Valid (148ms) (colibri2)
828
let lemma
bittest_add
(x y i: int) : unit
829
requires { 0 <= i }
830
ensures { bittest (x + y) i <-> ((bittest x i <-> bittest y i) <-> carry x y i) }
831
=
832
let p = pow2 i in
833
div_add x y p;
834
bittest_quot x i;
835
bittest_quot y i;
836
bittest_quot (x + y) i;
837
let dx = div x p in
838
let dy = div y p in
839
assert { mod (dx + dy) 2 = mod (mod dx 2 + mod dy 2) 2 };
840
assert { mod (dx + dy + 1) 2 = mod (mod dx 2 + mod dy 2 + 1) 2 }
841
842
use mach.int.Int63
844
845
(* 2^n for the bodies below, which the driver replaces: int.Power.power has no precondition, so it is not extracted *) Valid (60ms) (colibri2)
846
let rec
pow2_body
(n:int) : int
847
requires { 0 <= n }
848
variant { n }
849
ensures { result = pow2 n }
850
= if n = 0 then 1 else 2 * pow2_body (n - 1)
851
Valid (43ms) (colibri2)
852
let
test_bit
(x:int) (i:int63) : bool
853
requires { 0 <= i }
854
ensures { result <-> bittest x i }
855
= let i = to_int i in mod x (pow2_body (i+1)) >= pow2_body i
856
Valid (35ms) (colibri2)
857
let
lsl63
(x:int) (offset:int63) : int
858
requires { 0 <= offset }
859
ensures { result = lsl x offset }
860
= x * pow2_body (to_int offset)
861
Valid (36ms) (colibri2)
862
let
asr63
(x:int) (offset:int63) : int
863
requires { 0 <= offset }
864
ensures { result = asr x offset }
865
= div x (pow2_body (to_int offset))
866
Valid (41ms) (colibri2)
867
let
mask63
(k:int63) : int
868
requires { 0 <= k }
869
ensures { result = mask k }
870
= pow2_body (to_int k) - 1
871
872
Valid (109ms) (colibri2)
873
let rec
trailing_zeros
(x:int) : int
874
requires { x <> 0 }
875
ensures { 0 <= result }
876
ensures { bittest x result }
877
ensures { forall j. 0 <= j < result -> not (bittest x j) }
878
variant { if x < 0 then -x else x }
879
= if mod x 2 <> 0 then begin
880
assert { x = 2 * div x 2 + 1 };
881
odd_bittest (div x 2) 0;
882
0
883
end else begin
884
let y = div x 2 in
885
assert { x = 2 * y /\ y <> 0 };
886
let r = trailing_zeros y in
887
even_bittest y (r + 1);
888
let lemma low (j:int) : unit
889
requires { 0 <= j < r + 1 }
890
ensures { not (bittest x j) }
891
= even_bittest y j in
892
r + 1
893
end
894
end