Common — library colibrilib.bv_sem — module Sem

The interpretation of the bit–vector builtins

The code of RealValue.Check.compute_ground (realValue.ml) for the integer bitwise builtins of colibri2 and the SMT–LIB bit–vector operators: code is its specification, written with the same Zarith functions, and eval its implementation (extracted, called by realValue.ml). The values of the arguments and of the result are integers: a bit–vector of size n is 0 <= x < 2^n, a Boolean is -1 (true) or 0 (false).

10
module Sem
11
use int.Int
12
use list.List
13
use int.ComputerDivision as C
14
use int.EuclideanDivision as E
15
use mach.int.Int as MI
16
use mach.int.Int63
17
use colibrilib.zarith.Zbit
18
use colibrilib.zbit.ZbitInt
19
use colibrilib.safe_bits.BitsSpec
20
use colibrilib.safe_bits.SafeBits
21
use colibrilib.zarith.Z

The builtins: colibri_and_int, colibri_ior_int, colibri_xor_int, colibri_not_int, colibri_rshift_int, colibri_extract_int, colibri_signed_extract_int, colibri_update_int, colibri_testbit_int; the conversions sbv_to_int, ubv_to_int (and bv2nat), int_to_bv of a bit–vector of size n; the SMT–LIB bit–vector operators of size n (concat of sizes n and m, extract of the bits lo..hi, repeat k times, zero_extend and sign_extend by k, rotate_left and rotate_right by i)

31
type
builtin
=
32
|
And
|
Or
|
Xor
|
Not
|
Asr
|
Extract
|
SignedExtract
|
Update
|
Test
33
|
Sbv2int
int |
Bv2nat
int |
Int2bv
int
34
|
BvConcat
int int |
BvExtract
int int int |
BvRepeat
int int
35
|
BvZeroExtend
int int |
BvSignExtend
int int
36
|
BvRotl
int int |
BvRotr
int int
37
|
BvNot
int |
BvAnd
int |
BvOr
int |
BvXor
int
38
|
BvNand
int |
BvNor
int |
BvXnor
int |
BvComp
int
39
|
BvNeg
int |
BvAdd
int |
BvSub
int |
BvMul
int
40
|
BvUdiv
int |
BvUrem
int |
BvSdiv
int |
BvSrem
int |
BvSmod
int
41
|
BvShl
int |
BvLshr
int |
BvAshr
int
42
|
BvUlt
int |
BvUle
int |
BvUgt
int |
BvUge
int
43
|
BvSlt
int |
BvSle
int |
BvSgt
int |
BvSge
int

The functions of Zarith

Z.logand, Z.logor, Z.logxor, Z.lognot, Z.shift_left, Z.shift_right and Z.testbit are Zbit.land, Zbit.lor, Zbit.lxor, Zbit.lnot, Zbit.lsl, Zbit.asr and Zbit.bittest (as in zarith.drv); Z.div and Z.rem are C.div and C.mod (truncated), Z.fdiv is fdiv (rounded down).

Z.extract x off len: the bits off..off+len-1 of x. Zarith raises Invalid_argument for len <= 0; here it is 0

55
function
z_extract
(x off len:int) : int =
56
if len <= 0 then 0 else Zbit.land (Zbit.asr x off) (Zbit.mask len)

Z.signed_extract x off len: the same bits, sign extended

59
function
z_signed_extract
(x off len:int) : int =
60
if len <= 0 then 0
61
else if Zbit.bittest x (off + len - 1)
62
then Zbit.lor (z_extract x off len) (Zbit.lnot (Zbit.mask len))
63
else z_extract x off len

Z.fdiv a b, b <> 0

66
function
fdiv
(a b:int) : int = if b > 0 then E.div a b else E.div (- a) (- b)

The code of RealValue.Check.compute_ground

bitv n x: the value of a bit–vector argument of size n, which raises Wrong_arg when x is not 0 <= x < 2^n. It is used only on such values, where it is x itself (bitv below)

73
function
bv
(n x:int) : int = Zbit.land (Zbit.mask n) x

extract n t

76
function
ext
(n t:int) : int = z_extract t 0 n

signed_bitv n x

79
function
signed
(n x:int) : int = z_signed_extract (bv n x) 0 n

A Boolean

82
function
bool
(b:bool) : int = if b then -1 else 0

The loop of repeat: k copies of the n bits a

  Valid (23ms) (colibri2)
85
let rec ghost function
repeat
(n k a:int) : int
86
variant { k }
87
= if k <= 0 then 0 else Zbit.lor (Zbit.lsl (repeat n (k - 1) a) n) a

The value of the builtin b applied to the values l (0 for a wrong number of arguments, and for a rotation of a size n <= 0 or by i < 0: neither is a well–sorted SMT–LIB term)

92
function
code
(b:builtin) (l:list int) : int =
93
match b, l with
94
| And, Cons x (Cons y Nil) -> Zbit.land x y
95
| Or, Cons x (Cons y Nil) -> Zbit.lor x y
96
| Xor, Cons x (Cons y Nil) -> Zbit.lxor x y
97
| Not, Cons x Nil -> Zbit.lnot x
98
| Asr, Cons x (Cons o Nil) -> Zbit.asr x o
99
| Extract, Cons x (Cons o (Cons l Nil)) -> BitsSpec.extract o l x
100
| SignedExtract, Cons x (Cons o (Cons l Nil)) -> BitsSpec.signed_extract o l x
101
| Update, Cons dst (Cons o (Cons l (Cons src Nil))) -> BitsSpec.update o l src dst
102
| Test, Cons x (Cons k Nil) -> bool (Zbit.bittest x k)
103
| Sbv2int n, Cons x Nil -> signed n x
104
| Bv2nat n, Cons x Nil -> bv n x
105
| Int2bv n, Cons x Nil -> ext n x
106
| BvConcat n m, Cons x (Cons y Nil) -> Zbit.lor (Zbit.lsl (bv n x) m) (bv m y)
107
| BvExtract n lo hi, Cons x Nil -> z_extract (bv n x) lo (hi - lo + 1)
108
| BvRepeat n k, Cons x Nil -> repeat n k (bv n x)
109
| BvZeroExtend n _, Cons x Nil -> bv n x
110
| BvSignExtend n k, Cons x Nil ->
111
let a = bv n x in
112
if Zbit.bittest a (n - 1) then ext (n + k) (Zbit.lor (Zbit.lsl (-1) n) a) else a
113
| BvRotl n i, Cons x Nil ->
114
if n <= 0 || i < 0 then 0 else
115
let a = bv n x in
116
let k = C.mod i n in
117
if k = 0 then ext n a
118
else ext n (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k))
119
| BvRotr n i, Cons x Nil ->
120
if n <= 0 || i < 0 then 0 else
121
let a = bv n x in
122
let k = C.mod i n in
123
ext n (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k))
124
| BvNot n, Cons x Nil -> ext n (Zbit.lnot (bv n x))
125
| BvAnd n, Cons x (Cons y Nil) -> Zbit.land (bv n x) (bv n y)
126
| BvOr n, Cons x (Cons y Nil) -> Zbit.lor (bv n x) (bv n y)
127
| BvXor n, Cons x (Cons y Nil) -> ext n (Zbit.lxor (bv n x) (bv n y))
128
| BvNand n, Cons x (Cons y Nil) -> ext n (Zbit.lnot (Zbit.land (bv n x) (bv n y)))
129
| BvNor n, Cons x (Cons y Nil) -> ext n (Zbit.lnot (Zbit.lor (bv n x) (bv n y)))
130
| BvXnor n, Cons x (Cons y Nil) -> ext n (Zbit.lxor (bv n x) (Zbit.lnot (bv n y)))
131
| BvComp n, Cons x (Cons y Nil) -> if bv n x = bv n y then ext 1 (-1) else 0
132
| BvNeg n, Cons x Nil -> z_extract (Zbit.lsl 1 n - bv n x) 0 n
133
| BvAdd n, Cons x (Cons y Nil) -> ext n (bv n x + bv n y)
134
| BvSub n, Cons x (Cons y Nil) -> ext n (bv n x - bv n y)
135
| BvMul n, Cons x (Cons y Nil) -> ext n (bv n x * bv n y)
136
| BvUdiv n, Cons x (Cons y Nil) ->
137
let b = bv n y in
138
if b = 0 then ext n (-1) else ext n (C.div (bv n x) b)
139
| BvUrem n, Cons x (Cons y Nil) ->
140
let b = bv n y in
141
if b = 0 then bv n x else ext n (C.mod (bv n x) b)
142
| BvSdiv n, Cons x (Cons y Nil) ->
143
let b = signed n y in
144
let a = signed n x in
145
if b = 0 then (if a < 0 then ext n 1 else ext n (-1)) else ext n (C.div a b)
146
| BvSrem n, Cons x (Cons y Nil) ->
147
let b = signed n y in
148
if b = 0 then bv n x else ext n (C.mod (signed n x) b)
149
| BvSmod n, Cons x (Cons y Nil) ->
150
let b = signed n y in
151
let a = signed n x in
152
if b = 0 then bv n x else ext n (a - fdiv a b * b)
153
| BvShl n, Cons x (Cons o Nil) ->
154
let b = bv n o in
155
if n <= b then 0 else ext n (Zbit.lsl (bv n x) b)
156
| BvLshr n, Cons x (Cons o Nil) ->
157
let b = bv n o in
158
if n <= b then 0 else ext n (Zbit.asr (bv n x) b)
159
| BvAshr n, Cons x (Cons o Nil) ->
160
let b = bv n o in
161
let b = if n <= b then n else b in
162
ext n (Zbit.asr (signed n x) b)
163
| BvUlt n, Cons x (Cons y Nil) -> bool (bv n x < bv n y)
164
| BvUle n, Cons x (Cons y Nil) -> bool (bv n x <= bv n y)
165
| BvUgt n, Cons x (Cons y Nil) -> bool (bv n x > bv n y)
166
| BvUge n, Cons x (Cons y Nil) -> bool (bv n x >= bv n y)
167
| BvSlt n, Cons x (Cons y Nil) -> bool (signed n x < signed n y)
168
| BvSle n, Cons x (Cons y Nil) -> bool (signed n x <= signed n y)
169
| BvSgt n, Cons x (Cons y Nil) -> bool (signed n x > signed n y)
170
| BvSge n, Cons x (Cons y Nil) -> bool (signed n x >= signed n y)
171
| _ -> 0
172
end

The arguments

x is a bit–vector of size n

177
predicate
in_range
(n x:int) = 0 <= x < Zbit.lsl 1 n

The bit–vector arguments are in range

180
predicate
args_ok
(b:builtin) (l:list int) =
181
match b, l with
182
| (Sbv2int n | Bv2nat n | BvExtract n _ _ | BvRepeat n _ | BvZeroExtend n _
183
| BvSignExtend n _ | BvRotl n _ | BvRotr n _ | BvNot n | BvNeg n), Cons x Nil ->
184
in_range n x
185
| BvConcat n m, Cons x (Cons y Nil) -> in_range n x /\ in_range m y
186
| (BvAnd n | BvOr n | BvXor n | BvNand n | BvNor n | BvXnor n | BvComp n
187
| BvAdd n | BvSub n | BvMul n | BvUdiv n | BvUrem n | BvSdiv n | BvSrem n
188
| BvSmod n | BvShl n | BvLshr n | BvAshr n | BvUlt n | BvUle n | BvUgt n
189
| BvUge n | BvSlt n | BvSle n | BvSgt n | BvSge n), Cons x (Cons y Nil) ->
190
in_range n x /\ in_range n y
191
| _ -> true
192
end

The integer builtins whose result is not too big (SafeBits)

195
predicate
small
(b:builtin) (l:list int) =
196
match b, l with
197
| Asr, Cons x (Cons o Nil) -> shift_ok o x
198
| Extract, Cons x (Cons o (Cons l Nil)) -> extract_ok o l x
199
| SignedExtract, Cons _ (Cons o (Cons l Nil)) -> signed_extract_ok o l
200
| Update, Cons _ (Cons o (Cons l (Cons _ Nil))) -> update_ok o l
201
| _ -> true
202
end

The implementation

The bits of 0 <= x < 2^s from s are zero

  Valid (52ms) (colibri2)
207
let ghost
high_zero
(x s:int) : unit
208
requires { 0 <= s /\ 0 <= x < Zbit.lsl 1 s }
209
ensures { forall i. s <= i -> not (Zbit.bittest x i) }
210
= {proof…} Zbit.numbits_lt_lsl x s;
211
let lemma bit (i:int) : unit
212
requires { s <= i }
213
ensures { not (Zbit.bittest x i) }
214
= if x > 0 then Zbit.numbits_high_clear x i in
215
() {qed}

A bit–vector argument is not in range (Wrong_arg)

218
exception
WrongArg

bitv n x

  Valid (130ms) (colibri2 12) (cvc4) (split_vc) (depth 1)
221
let
bitv
(n x:int) : int
222
ensures { in_range n x /\ 0 <= n }
223
ensures { result = x = bv n x }
224
raises { WrongArg -> not in_range n x }
225
= if 0 <= x && Zbit.numbits x <= n then begin
226
{proof…}
227
Zbit.numbits_ge_pos 0 x;
228
assert { 0 <= n };
229
assert { x < Zbit.lsl 1 n
230
by Zbit.lsl 1 n <= x -> n + 1 = Zbit.numbits (Zbit.lsl 1 n) <= Zbit.numbits x };
231
high_zero x n;
232
let lemma bit (i:int) : unit
233
requires { 0 <= i }
234
ensures { Zbit.bittest (bv n x) i <-> Zbit.bittest x i }
235
= () in
236
Zbit.ext_bittest (bv n x) x;
237
{qed}
238
x
239
end else begin
240
{proof…}
241
assert { not in_range n x by in_range n x -> Zbit.numbits x <= n };
242
{qed}
243
raise WrongArg
244
end

Z.extract x off len (total)

  Valid (50ms) (colibri2)
247
let
z_extract_p
(x off len:int) : int
248
ensures { result = z_extract x off len }
249
= if len <= 0 then 0
250
else begin
251
let y = if off >= 0 then asr_int x off else lsl_int x (- off) in
252
Zbit.land y (mask_int len)
253
end

extract n t

  Valid (25ms) (colibri2)
256
let
ext_p
(n t:int) : int
257
ensures { result = ext n t }
258
= z_extract_p t 0 n

Z.signed_extract x 0 n

  Valid (41ms) (colibri2)
261
let
z_signed_extract0
(x n:int) : int
262
ensures { result = z_signed_extract x 0 n }
263
= if n <= 0 then 0
264
else if test_bit_int x (n - 1) then Zbit.lor (z_extract_p x 0 n) (Zbit.lnot (mask_int n))
265
else z_extract_p x 0 n

signed_bitv n x

  Valid (43ms) (colibri2)
268
let
signed_p
(n x:int) : int
269
ensures { in_range n x /\ 0 <= n }
270
ensures { result = signed n x }
271
raises { WrongArg -> not in_range n x }
272
= z_signed_extract0 (bitv n x) n
273
274
let function
bool_p
(b:bool) : int = if b then -1 else 0

The loop of repeat

  Valid (40ms) (colibri2)
277
let rec
repeat_p
(n k a:int) : int
278
requires { 0 <= n }
279
variant { k }
280
ensures { result = repeat n k a }
281
= if k <= 0 then 0 else Zbit.lor (lsl_int (repeat_p n (k - 1) a) n) a

Z.fdiv a b

  Valid (43ms) (colibri2)
284
let
fdiv_p
(a b:int) : int
285
requires { b <> 0 }
286
ensures { result = fdiv a b }
287
= if b > 0 then Z.fdiv a b else Z.fdiv (- a) (- b)

The value of the builtin b applied to the values l

  Valid (393ms) (colibri2 203) (split_vc) (depth 1)
290
let
eval
(b:builtin) (l:list int) : int
291
ensures { args_ok b l /\ small b l }
292
ensures { result = code b l }
293
raises { WrongArg -> not args_ok b l }
294
raises { TooBig -> args_ok b l /\ not small b l }
295
= match b, l with
296
| And, Cons x (Cons y Nil) -> Zbit.land x y
297
| Or, Cons x (Cons y Nil) -> Zbit.lor x y
298
| Xor, Cons x (Cons y Nil) -> Zbit.lxor x y
299
| Not, Cons x Nil -> Zbit.lnot x
300
| Asr, Cons x (Cons o Nil) ->
301
if shift_ok o x then SafeBits.shift_right o x else raise TooBig
302
| Extract, Cons x (Cons o (Cons l Nil)) ->
303
if extract_ok o l x then SafeBits.extract o l x else raise TooBig
304
| SignedExtract, Cons x (Cons o (Cons l Nil)) ->
305
if signed_extract_ok o l then SafeBits.signed_extract o l x else raise TooBig
306
| Update, Cons dst (Cons o (Cons l (Cons src Nil))) ->
307
if update_ok o l then SafeBits.update o l src dst else raise TooBig
308
| Test, Cons x (Cons k Nil) ->
309
if k < 0 then 0 else bool_p (test_bit_int x k)
310
| Sbv2int n, Cons x Nil -> signed_p n x
311
| Bv2nat n, Cons x Nil -> bitv n x
312
| Int2bv n, Cons x Nil -> ext_p n x
313
| BvConcat n m, Cons x (Cons y Nil) ->
314
let a = bitv n x in
315
let b = bitv m y in
316
Zbit.lor (lsl_int a m) b
317
| BvExtract n lo hi, Cons x Nil -> z_extract_p (bitv n x) lo (hi - lo + 1)
318
| BvRepeat n k, Cons x Nil ->
319
let a = bitv n x in
320
repeat_p n k a
321
| BvZeroExtend n _, Cons x Nil -> bitv n x
322
| BvSignExtend n k, Cons x Nil ->
323
let a = bitv n x in
324
if n <= 0 then a (* no bit-vector of size <= 0 but 0 *)
325
else if test_bit_int a (n - 1) then ext_p (n + k) (Zbit.lor (lsl_int (-1) n) a) else a
326
| BvRotl n i, Cons x Nil ->
327
let a = bitv n x in
328
if n <= 0 || i < 0 then 0 else
329
let k = MI.(%) i n in
330
if k = 0 then ext_p n a
331
else ext_p n (Zbit.lor (lsl_int a k) (z_extract_p a (n - k) k))
332
| BvRotr n i, Cons x Nil ->
333
let a = bitv n x in
334
if n <= 0 || i < 0 then 0 else
335
let k = MI.(%) i n in
336
ext_p n (Zbit.lor (lsl_int a (n - k)) (asr_int a k))
337
| BvNot n, Cons x Nil -> ext_p n (Zbit.lnot (bitv n x))
338
| BvAnd n, Cons x (Cons y Nil) -> let a = bitv n x in Zbit.land a (bitv n y)
339
| BvOr n, Cons x (Cons y Nil) -> let a = bitv n x in Zbit.lor a (bitv n y)
340
| BvXor n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (Zbit.lxor a (bitv n y))
341
| BvNand n, Cons x (Cons y Nil) ->
342
let a = bitv n x in ext_p n (Zbit.lnot (Zbit.land a (bitv n y)))
343
| BvNor n, Cons x (Cons y Nil) ->
344
let a = bitv n x in ext_p n (Zbit.lnot (Zbit.lor a (bitv n y)))
345
| BvXnor n, Cons x (Cons y Nil) ->
346
let a = bitv n x in ext_p n (Zbit.lxor a (Zbit.lnot (bitv n y)))
347
| BvComp n, Cons x (Cons y Nil) ->
348
let a = bitv n x in if a = bitv n y then ext_p 1 (-1) else 0
349
| BvNeg n, Cons x Nil ->
350
let a = bitv n x in
351
z_extract_p (lsl_int 1 n - a) 0 n
352
| BvAdd n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a + bitv n y)
353
| BvSub n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a - bitv n y)
354
| BvMul n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a * bitv n y)
355
| BvUdiv n, Cons x (Cons y Nil) ->
356
let a = bitv n x in
357
let b = bitv n y in
358
if b = 0 then ext_p n (-1) else ext_p n (MI.(/) a b)
359
| BvUrem n, Cons x (Cons y Nil) ->
360
let a = bitv n x in
361
let b = bitv n y in
362
if b = 0 then a else ext_p n (MI.(%) a b)
363
| BvSdiv n, Cons x (Cons y Nil) ->
364
let a = signed_p n x in
365
let b = signed_p n y in
366
if b = 0 then (if a < 0 then ext_p n 1 else ext_p n (-1)) else ext_p n (MI.(/) a b)
367
| BvSrem n, Cons x (Cons y Nil) ->
368
let a = signed_p n x in
369
let b = signed_p n y in
370
if b = 0 then bitv n x else ext_p n (MI.(%) a b)
371
| BvSmod n, Cons x (Cons y Nil) ->
372
let a = signed_p n x in
373
let b = signed_p n y in
374
if b = 0 then bitv n x else ext_p n (a - fdiv_p a b * b)
375
| BvShl n, Cons x (Cons o Nil) ->
376
let a = bitv n x in
377
let b = bitv n o in
378
if n <= b then 0 else ext_p n (lsl_int a b)
379
| BvLshr n, Cons x (Cons o Nil) ->
380
let a = bitv n x in
381
let b = bitv n o in
382
if n <= b then 0 else ext_p n (asr_int a b)
383
| BvAshr n, Cons x (Cons o Nil) ->
384
let a = signed_p n x in
385
let b = bitv n o in
386
let b = if n <= b then n else b in
387
ext_p n (asr_int a b)
388
| BvUlt n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a < bitv n y)
389
| BvUle n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a <= bitv n y)
390
| BvUgt n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a > bitv n y)
391
| BvUge n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a >= bitv n y)
392
| BvSlt n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a < signed_p n y)
393
| BvSle n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a <= signed_p n y)
394
| BvSgt n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a > signed_p n y)
395
| BvSge n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a >= signed_p n y)
396
| _ -> 0
397
end
398
end