Common — library colibrilib.lowbits — module LowBits

Low bits of integers (two's complement): two integers differ by a multiple of 2^i iff they have the same i lowest bits.

The facts are let ghost functions that a proof calls, not let lemma (see colibrilib/dv.mlw).

6
module LowBits
7
use int.Int
8
use colibrilib.zarith.Zbit

Shifting by one more bit doubles, for every integer

  Valid (138ms) (colibri2)
11
let ghost
lsl_dbl
(k i:int) : unit
12
requires { 0 <= i }
13
ensures { Zbit.lsl k (i + 1) = 2 * Zbit.lsl k i }
14
= {proof…} let lemma bit (j:int) : unit
15
requires { 0 <= j }
16
ensures { Zbit.bittest (Zbit.lsl k (i + 1)) j <-> Zbit.bittest (2 * Zbit.lsl k i) j }
17
= () in
18
Zbit.ext_bittest (Zbit.lsl k (i + 1)) (2 * Zbit.lsl k i) {qed}

lsl k i is the product by lsl 1 i = 2^i

  Valid (4.5s) (colibri2 6) (split_vc 2) (depth 2)
21
let rec ghost
lsl_mul
(k i:int) : unit
22
requires { 0 <= i }
23
variant { i }
24
ensures { Zbit.lsl k i = k * Zbit.lsl 1 i }
25
= {proof…} if i > 0 then begin
26
lsl_dbl k (i - 1);
27
lsl_dbl 1 (i - 1);
28
lsl_mul k (i - 1)
29
end {qed}

No carry reaches i when the i low bits of t are zero

  Valid (52ms) (colibri2)
32
let rec ghost
no_carry
(r t i:int) : unit
33
requires { 0 <= i }
34
requires { forall j. 0 <= j < i -> not (Zbit.bittest t j) }
35
variant { i }
36
ensures { not (Zbit.carry r t i) }
37
= if i > 0 then no_carry r t (i - 1)

Adding a number whose i low bits are zero does not change the i low bits

  Valid (41ms) (colibri2)
41
let ghost
add_low
(r t i:int) : unit
42
requires { 0 <= i }
43
requires { forall j. 0 <= j < i -> not (Zbit.bittest t j) }
44
ensures { forall j. 0 <= j < i -> (Zbit.bittest (r + t) j <-> Zbit.bittest r j) }
45
= {proof…} let lemma bit (j:int) : unit
46
requires { 0 <= j < i }
47
ensures { Zbit.bittest (r + t) j <-> Zbit.bittest r j }
48
= no_carry r t j in () {qed}

n - r is a multiple of 2^i: n and r have the same i lowest bits

  Valid (52ms) (colibri2)
52
let ghost
same_low
(n r m i:int) : unit
53
requires { 0 <= i }
54
requires { n - r = m * Zbit.lsl 1 i }
55
ensures { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }
56
= {proof…} lsl_mul m i;
57
assert { n = r + Zbit.lsl m i };
58
let lemma zero (j:int) : unit
59
requires { 0 <= j < i }
60
ensures { not (Zbit.bittest (Zbit.lsl m i) j) }
61
= () in
62
add_low r (Zbit.lsl m i) i {qed}
63
Valid (402ms) (cvc5)
64
let rec ghost
sub_low_aux
(n r t i:int) : unit
65
requires { 0 <= i }
66
requires { n = r + t }
67
requires { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }
68
variant { i }
69
ensures { forall j. 0 <= j < i -> not (Zbit.bittest t j) }
70
ensures { not (Zbit.carry r t i) }
71
= {proof…} if i > 0 then begin
72
sub_low_aux n r t (i - 1);
73
assert { not (Zbit.bittest t (i - 1)) }
74
end {qed}

Conversely, n - r is a multiple of 2^i when the i low bits of n and r agree

  Valid (166ms) (colibri2)
78
let ghost
sub_low
(n r i:int) : unit
79
requires { 0 <= i }
80
requires { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }
81
ensures { exists m:int. n - r = m * Zbit.lsl 1 i }
82
= {proof…} let t = n - r in
83
sub_low_aux n r t i;
84
let m = Zbit.asr t i in
85
let lemma bit (j:int) : unit
86
requires { 0 <= j }
87
ensures { Zbit.bittest t j <-> Zbit.bittest (Zbit.lsl m i) j }
88
= () in
89
Zbit.ext_bittest t (Zbit.lsl m i);
90
lsl_mul m i {qed}
91
end