Common — library colibrilib.safe_bits — module SafeBits

Total versions. Each operation has a core version that requires that the result is not too big (a predicate whose name ends with ok) and the exported version that raises TooBig exactly when this predicate is false.

105
module SafeBits
106
use int.Int
107
use int.MinMax
108
use colibrilib.zarith.Zbit
109
use colibrilib.zbit.ZbitInt
110
use BitsSpec
111
use colibrilib.spec.Value
112
113
exception
TooBig

Largest left shift or field length we agree to build

116
let constant
bound
: int = 1073741824

lnot x is non negative when x is negative

  Valid (67ms) (colibri2)
119
let lemma
lnot_nonneg
(x:int) : unit
120
requires { x < 0 }
121
ensures { 0 <= Zbit.lnot x }
122
= let s = Zbit.numbits (-x) in
123
Zbit.numbits_top_bit (-x);
124
if s < 1 then Zbit.bittest_neg (-x) (s-1);
125
assert { s >= 1 };
126
Zbit.numbits_lsl_lt (-x);
127
let z = x + Zbit.lsl 1 s in
128
assert { z - Zbit.lsl 1 s = x };
129
Zbit.mask_nonneg s;
130
let w = Zbit.land (Zbit.mask s) (Zbit.lnot x) in
131
Zbit.land_nonneg_l (Zbit.mask s) (Zbit.lnot x);
132
let lemma bit (i:int) : unit
133
requires { 0 <= i }
134
ensures { Zbit.bittest (Zbit.lnot x) i <-> Zbit.bittest w i }
135
= if i < s then Zbit.mask_bits s i
136
else begin
137
Zbit.mask_bits_high s i;
138
Zbit.bittest_sub_lsl_high z s i
139
end in
140
Zbit.ext_bittest (Zbit.lnot x) w

Number of bits that are not the sign extension

  Valid (28ms) (colibri2)
143
let function
nb
(x:int) : int
144
= if x < 0 then (lnot_nonneg x; Zbit.numbits (Zbit.lnot x)) else Zbit.numbits x

Above nb x all the bits are the sign

  Valid (81ms) (colibri2)
147
let lemma
bittest_high
(x i:int) : unit
148
requires { 0 <= i }
149
requires { nb x <= i }
150
ensures { Zbit.bittest x i <-> x < 0 }
151
= if x > 0 then Zbit.numbits_high_clear x i
152
else if x = 0 then ()
153
else begin
154
lnot_nonneg x;
155
let y = Zbit.lnot x in
156
if y > 0 then Zbit.numbits_high_clear y i
157
end
158
Valid (36ms) (colibri2)
159
let lemma
minus_one_bits
(j:int) : unit
160
requires { 0 <= j }
161
ensures { Zbit.bittest (-1) j }
162
= Zbit.asr_eq 1;
163
Zbit.bittest_sub_lsl_high 0 0 j

Shifting does not change the sign

  Valid (360ms) (cvc5)
166
let lemma
sign_shift
(off a y:int) : unit
167
requires { forall i. 0 <= i -> Zbit.bittest y i <-> Zbit.bittest a (i + off) }
168
ensures { y < 0 <-> a < 0 }
169
= let n = max (nb y) (nb a) + (if off < 0 then - off else off) in
170
bittest_high y n;
171
bittest_high a (n + off)

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

175
let predicate
shift_ok
(off a:int) = off >= - bound || a = 0
176
Valid (470ms) (colibri2)
177
let
shift_right
(off a:int) : int
178
requires { shift_ok off a }
179
ensures { value_is (Zbit.asr a off) result }
180
= let r =
181
if off >= 0 then begin
182
if off >= nb a then (if a < 0 then -1 else 0) else ZbitInt.asr_int a off
183
end
184
else if a = 0 then 0
185
else ZbitInt.lsl_int a (-off) in
186
let lemma bit (i:int) : unit
187
requires { 0 <= i }
188
ensures { Zbit.bittest r i <-> Zbit.bittest (Zbit.asr a off) i }
189
= if off >= 0 && off >= nb a then bittest_high a (i + off) in
190
Zbit.ext_bittest r (Zbit.asr a off);
191
r

BitsSpec.extract

195
let predicate
extract_ok
(off len a:int) =
196
len <= 0 || off <= - len || (shift_ok off a && (len <= bound || a >= 0))
197
Valid (65ms) (colibri2 10) (split_vc) (depth 1)
198
let
extract
(off len a:int) : int
199
requires { extract_ok off len a }
200
ensures { value_is (BitsSpec.extract off len a) result }
201
= if len <= 0 then 0
202
else if off <= - len then begin
203
let lemma bit (i:int) : unit
204
requires { 0 <= i }
205
ensures { Zbit.bittest (BitsSpec.extract off len a) i <-> Zbit.bittest 0 i }
206
= () in
207
Zbit.ext_bittest 0 (BitsSpec.extract off len a);
208
0
209
end
210
else begin
211
let y = shift_right off a in
212
sign_shift off a y;
213
if y >= 0 && len >= nb y then begin
214
let lemma bit (i:int) : unit
215
requires { 0 <= i }
216
ensures { Zbit.bittest y i <-> Zbit.bittest (BitsSpec.extract off len a) i }
217
= if i >= len then bittest_high y i in
218
Zbit.ext_bittest y (BitsSpec.extract off len a);
219
y
220
end else Zbit.land y (ZbitInt.mask_int len)
221
end

BitsSpec.sext

  Valid (409ms) (colibri2)
225
let
sext
(y n:int) : int
226
requires { n > 0 }
227
ensures { value_is (BitsSpec.sext y n) result }
228
= if n > nb y then begin
229
let lemma bit (i:int) : unit
230
requires { 0 <= i }
231
ensures { Zbit.bittest y i <-> Zbit.bittest (BitsSpec.sext y n) i }
232
= if i >= n - 1 then (bittest_high y i; bittest_high y (n - 1)) in
233
Zbit.ext_bittest y (BitsSpec.sext y n);
234
y
235
end else begin
236
let m = ZbitInt.mask_int n in
237
if ZbitInt.test_bit_int y (n - 1) then Zbit.lor (Zbit.land y m) (Zbit.lnot m)
238
else Zbit.land y m
239
end

Signed extraction of the specification BitsSpec

242
let predicate
signed_extract_ok
(off len:int) =
243
(if off < 0 then len + off else len) <= 0 || off >= - bound
244
Valid (341ms) (colibri2)
245
let
signed_extract
(off len a:int) : int
246
requires { signed_extract_ok off len }
247
ensures { value_is (BitsSpec.signed_extract off len a) result }
248
= BitsSpec.signed_extract_alg_eq off len a;
249
let n = if off < 0 then len + off else len in
250
if n <= 0 then 0
251
else begin
252
let y = shift_right (if off < 0 then 0 else off) a in
253
let s = sext y n in
254
if off >= 0 then (Zbit.asr_eq s; s) else ZbitInt.lsl_int s (- off)
255
end

BitsSpec.update

259
let predicate
update_ok
(off len:int) = len <= 0 || (len <= bound && off <= bound)
260
Valid (45ms) (colibri2)
261
let
update
(off len src dst:int) : int
262
requires { update_ok off len }
263
ensures { value_is (BitsSpec.update off len src dst) result }
264
= if len <= 0 then dst
265
else begin
266
let m = ZbitInt.mask_int len in
267
let hole = shift_right (- off) m in
268
let part = shift_right (- off) (Zbit.land src m) in
269
Zbit.lor (Zbit.land dst (Zbit.lnot hole)) part
270
end
271
272
end