Common — library colibrilib.zbit — module ZbitInt

Total versions of the bit operations, for an index or an offset that is not known to fit in an int63 (a number of bits, for example). They never overflow: beyond max_int63, x has become 0 or -1 for asr, and lsl can only run out of memory, as any operation of Zarith.

6
module ZbitInt

Implemented

7
use int.Int
8
use mach.int.Int63
9
use colibrilib.zarith.Zbit
10
Valid (29ms) (colibri2)
11
let ghost
asr_asr
(x a b:int) : unit
12
requires { 0 <= a /\ 0 <= b }
13
ensures { asr (asr x a) b = asr x (a + b) }
14
= let lemma bit (i:int) : unit
15
requires { i >= 0 }
16
ensures { bittest (asr (asr x a) b) i = bittest (asr x (a + b)) i }
17
= def_asr (asr x a) b i; def_asr x a (i + b); def_asr x (a + b) i in
18
ext_bittest (asr (asr x a) b) (asr x (a + b))
19
Valid (27ms) (colibri2)
20
let rec ghost
minus_one_bits
(j:int) : unit
21
requires { 0 <= j }
22
ensures { bittest (-1) j }
23
variant { j }
24
= odd_bittest (-1) j; if j > 0 then minus_one_bits (j - 1)
25
Valid (40ms) (colibri2)
26
let ghost
asr_fix
(x k:int) : unit
27
requires { x = 0 \/ x = -1 }
28
requires { 0 <= k }
29
ensures { asr x k = x }
30
= let lemma bit (i:int) : unit
31
requires { 0 <= i }
32
ensures { bittest (asr x k) i = bittest x i }
33
= def_asr x k i;
34
if x = -1 then (minus_one_bits i; minus_one_bits (i + k)) in
35
ext_bittest (asr x k) x
36
Valid (40ms) (colibri2)
37
let rec
asr_int
(x offset:int) : int
38
requires { 0 <= offset }
39
ensures { result = asr x offset }
40
variant { offset }
41
= if offset <= max_int63 then asr63 x (of_int offset)
42
else if x = 0 || x = -1 then begin asr_fix x offset; x end
43
else begin
44
asr_asr x max_int63 (offset - max_int63);
45
asr_int (asr63 x max_int) (offset - max_int63)
46
end
47
Valid (42ms) (colibri2)
48
let ghost
lsl_lsl
(x a b:int) : unit
49
requires { 0 <= a /\ 0 <= b }
50
ensures { lsl (lsl x a) b = lsl x (a + b) }
51
= let lemma bit (i:int) : unit
52
requires { i >= 0 }
53
ensures { bittest (lsl (lsl x a) b) i = bittest (lsl x (a + b)) i }
54
= def_asr (lsl x a) (-b) i; def_asr x (-(a + b)) i;
55
if i - b >= 0 then def_asr x (-a) (i - b)
56
else (bittest_neg (lsl x a) (i - b); bittest_neg x (i - b - a)) in
57
ext_bittest (lsl (lsl x a) b) (lsl x (a + b))
58
Valid (311ms) (cvc4)
59
let rec
lsl_int
(x offset:int) : int
60
requires { 0 <= offset }
61
ensures { result = lsl x offset }
62
variant { offset }
63
= if offset <= max_int63 then lsl63 x (of_int offset)
64
else if x = 0 then 0
65
else begin
66
lsl_lsl x max_int63 (offset - max_int63);
67
lsl_int (lsl63 x max_int) (offset - max_int63)
68
end
69
Valid (20ms) (colibri2)
70
let
mask_int
(k:int) : int
71
requires { 0 <= k }
72
ensures { result = mask k }
73
= lsl_int 1 k - 1
74
Valid (33ms) (colibri2)
75
let
test_bit_int
(x i:int) : bool
76
requires { 0 <= i }
77
ensures { result <-> bittest x i }
78
= if i <= max_int63 then test_bit x (of_int i)
79
else begin
80
def_asr x (i - max_int63) max_int63;
81
test_bit (asr_int x (i - max_int63)) max_int
82
end
83
end