Common — library colibrilib.safe_bits — module BitsSpec

The definitions. A negative offset shifts to the left

7
module BitsSpec
8
use int.Int
9
use int.MinMax
10
use colibrilib.zarith.Zbit

The len bits of x from the position off, as a non negative integer

13
function
extract
(off len x:int) : int =
14
if len <= 0 then 0 else Zbit.land (Zbit.asr x off) (Zbit.mask len)

The n lowest bits of y, sign extended from the highest one

17
function
sext
(y n:int) : int =
18
if Zbit.bittest y (n - 1) then Zbit.lor (Zbit.land y (Zbit.mask n)) (Zbit.lnot (Zbit.mask n))
19
else Zbit.land y (Zbit.mask n)

The len bits of x from the position off (the bits at negative positions are 0, as for Zbit.bittest), sign extended from the highest one

24
function
signed_extract
(off len x:int) : int =
25
if len <= 0 then 0
26
else if Zbit.bittest x (off + len - 1) then Zbit.lor (extract off len x) (Zbit.lnot (Zbit.mask len))
27
else extract off len x

The algorithm of the implementation (equal to the specification by a lemma below).

30
function
signed_extract_alg
(off len x:int) : int =
31
let n = if off < 0 then len + off else len in
32
if n <= 0 then 0 else Zbit.lsl (sext (Zbit.asr x (max off 0)) n) (max (- off) 0)

dst where the len bits from the position off are replaced by the len lowest bits of src

36
function
update
(off len src dst:int) : int =
37
if len <= 0 then dst
38
else Zbit.lor (Zbit.land dst (Zbit.lnot (Zbit.lsl (Zbit.mask len) off)))
39
(Zbit.lsl (Zbit.land src (Zbit.mask len)) off)
40
Valid (33ms) (colibri2)
41
let lemma
mask_field
(len i:int) : unit
42
requires { 0 <= len }
43
ensures { Zbit.bittest (Zbit.mask len) i <-> 0 <= i < len }
44
= if i < 0 then Zbit.bittest_neg (Zbit.mask len) i
45
else if i < len then Zbit.mask_bits len i
46
else Zbit.mask_bits_high len i
47
Valid (48ms) (colibri2)
48
let lemma
bit_extract
(off len x i:int) : unit
49
requires { 0 <= i }
50
ensures { Zbit.bittest (extract off len x) i <-> (i < len /\ Zbit.bittest x (i + off)) }
51
= if len > 0 then mask_field len i
52
Valid (148ms) (colibri2)
53
let lemma
bit_sext
(y n i:int) : unit
54
requires { 0 <= i /\ 0 < n }
55
ensures { Zbit.bittest (sext y n) i <-> Zbit.bittest y (min i (n - 1)) }
56
= mask_field n i
57
Valid (221ms) (colibri2)
58
let lemma
bit_signed_extract
(off len x i:int) : unit
59
requires { 0 <= i }
60
ensures { Zbit.bittest (signed_extract off len x) i <->
61
(len > 0 /\ Zbit.bittest x (off + min i (len - 1))) }
62
= if len > 0 then begin
63
mask_field len i;
64
bit_extract off len x i;
65
if i >= len then bit_extract off len x (len - 1)
66
end
67
68
function
sx_len
(off len:int) : int = if off < 0 then len + off else len
69
function
sx_pos
(off len i:int) : int =
70
if off >= 0 then off + min i (len - 1) else min (i + off) (len + off - 1)
71
predicate
sx_on
(off len i:int) = sx_len off len > 0 /\ (off >= 0 \/ i >= - off)
72
Valid (166ms) (cvc5)
73
let lemma
bit_signed_extract_alg
(off len x i:int) : unit
74
requires { 0 <= i }
75
ensures { Zbit.bittest (signed_extract_alg off len x) i <->
76
(sx_on off len i /\ Zbit.bittest x (sx_pos off len i)) }
77
= let n = sx_len off len in
78
if n > 0 then begin
79
let y = Zbit.asr x (max off 0) in
80
let s = sext y n in
81
if i >= max (- off) 0 then bit_sext y n (i - max (- off) 0)
82
else Zbit.bittest_neg s (i - max (- off) 0)
83
end

The algorithm of the implementation computes the specification

  Valid (790ms) (colibri2)
86
let lemma
signed_extract_alg_eq
(off len x:int) : unit
87
ensures { signed_extract_alg off len x = signed_extract off len x }
88
= let lemma bit (i:int) : unit
89
requires { 0 <= i }
90
ensures { Zbit.bittest (signed_extract_alg off len x) i <-> Zbit.bittest (signed_extract off len x) i }
91
= bit_signed_extract off len x i; bit_signed_extract_alg off len x i;
92
if off < 0 && len > 0 && len + off <= 0 then Zbit.bittest_neg x (off + min i (len - 1)) in
93
Zbit.ext_bittest (signed_extract_alg off len x) (signed_extract off len x)
94
Valid (1.6s) (cvc4)
95
let lemma
bit_update
(off len src dst i:int) : unit
96
requires { 0 <= i }
97
ensures { Zbit.bittest (update off len src dst) i <->
98
(if len > 0 /\ off <= i < off + len then Zbit.bittest src (i - off) else Zbit.bittest dst i) }
99
= if len > 0 then mask_field len (i - off)
100
end