Common — library colibrilib.fp_conv — module BvConv

The conversions between floats and bit–vectors

to_fp of the IEEE encoding, on the domains: the encoding is the integer node of the bit–vector.

1191
module BvConv
1192
use int.Int
1193
use int.Power
1194
use list.List
1195
use option.Option
1196
use real.RealInfix
1197
use real.FromInt
1198
use real.Truncate
1199
use colibrilib.ring.Atom
1200
use colibrilib.fbin.Fp
1201
use colibrilib.fp_facts.Facts
1202
use colibrilib.stda.StdA as A
1203
use colibrilib.fp_interval.Intervals
1204
use colibrilib.fp_interval.FpInterval
1205
use Env
1206
use RealConv

The encodings of the negative floats start at half_bits fm (the sign bit)

1210
function
half_bits
(fm: format) : int = power 2 (eb fm + sb fm - 1)

The float of the encoding b (0 <= b < 2 * half_bits fm), as in SMT–LIB (fp.Intf: on the floats that are not negative, the index is the encoding): the sign bit, then the biased exponent and the significand; the encodings above an infinity are NaNs

1216
predicate
of_bits
(fm: format) (b: int) (x: t) =
1217
if 0 <= b < nb_sign fm then x = of_index fm b
1218
else if half_bits fm <= b < half_bits fm + nb_sign fm then
1219
x = of_index fm (half_bits fm - 1 - b)
1220
else fmt x = fm /\ is_nan x
1221
Valid (103ms) (colibri2)
1222
let ghost
nb_sign_half
(fm: format) : unit
1223
ensures { 0 < nb_sign fm <= half_bits fm }
1224
= {proof…}
1225
assert { power 2 (eb fm + sb fm - 1) = power 2 (eb fm) * power 2 (sb fm - 1) };
1226
assert { 2 <= power 2 (sb fm - 1) /\ 2 <= power 2 (eb fm) }
1227
{qed}
1228
Valid (36ms) (colibri2)
1229
let rec
pow2
(n: int) : int
1230
requires { 0 <= n }
1231
ensures { result = power 2 n }
1232
variant { n }
1233
= if n = 0 then 1 else 2 * pow2 (n - 1)

Unions of integer intervals

1236
type
ivs
= list (int, int)
1237
1238
predicate
imem
(z: int) (l: ivs) =
1239
match l with Nil -> false | Cons (x, y) l' -> x <= z <= y \/ imem z l' end
1240
1241
predicate
in_rng
(lo hi: int) (l: ivs) =
1242
match l with Nil -> true | Cons (x, y) l' -> lo <= x /\ y <= hi /\ in_rng lo hi l' end
1243
Valid (36ms) (colibri2)
1244
let rec
ivs_app
(l1 l2: ivs) : ivs
1245
ensures { forall z. imem z l1 \/ imem z l2 -> imem z result }
1246
variant { l1 }
1247
= match l1 with Nil -> l2 | Cons i l' -> Cons i (ivs_app l' l2) end

The least integer of the bound, or dflt

  Valid (34ms) (colibri2)
1250
let
int_lo
(b: bnd) (dflt: int) : int
1251
ensures { forall z. dflt <= z -> rmem_lo (from_int z) b -> result <= z }
1252
= match b with
1253
| BInf -> dflt
1254
| BLarge a -> a_ceil a
1255
| BStrict a ->
1256
{proof…} let lemma pt (z: int) : unit
1257
requires { A.real a <. from_int z } ensures { floor (A.real a) + 1 <= z }
1258
= assert { from_int (floor (A.real a)) <=. A.real a };
1259
assert { floor (A.real a) < z } in {qed}
1260
a_floor a + 1
1261
end
1262
Valid (35ms) (colibri2)
1263
let
int_hi
(b: bnd) (dflt: int) : int
1264
ensures { forall z. z <= dflt -> rmem_hi (from_int z) b -> z <= result }
1265
= match b with
1266
| BInf -> dflt
1267
| BLarge a -> a_floor a
1268
| BStrict a ->
1269
{proof…} let lemma pt (z: int) : unit
1270
requires { from_int z <. A.real a } ensures { z <= ceil (A.real a) - 1 }
1271
= assert { A.real a <=. from_int (ceil (A.real a)) };
1272
assert { z < ceil (A.real a) } in {qed}
1273
a_ceil a - 1
1274
end

The integers of l in [lo, hi]

  Valid (381ms) (colibri2)
1277
let rec
to_ivs
(l: rdom) (lo hi: int) : ivs
1278
ensures { forall z. lo <= z <= hi -> rmem (from_int z) l -> imem z result }
1279
ensures { in_rng lo hi result }
1280
variant { l }
1281
= match l with
1282
| Nil -> Nil
1283
| Cons i l' ->
1284
let (x, y) = match i with
1285
| RSing a -> (a_ceil a, a_floor a)
1286
| RInter bl bh -> (int_lo bl lo, int_hi bh hi)
1287
end in
1288
let x = if x < lo then lo else x in
1289
let y = if hi < y then hi else y in
1290
let r = to_ivs l' lo hi in
1291
if x <= y then Cons (x, y) r else r
1292
end
1293
Valid (36ms) (colibri2)
1294
let rec
of_ivs
(l: ivs) : rdom
1295
ensures { forall z. imem z l -> rmem (from_int z) result }
1296
variant { l }
1297
= match l with
1298
| Nil -> Nil
1299
| Cons (x, y) l' -> Cons (RInter (BLarge (a_of_int x)) (BLarge (a_of_int y))) (of_ivs l')
1300
end

Forward

The floats of the encodings in [x, y]

  Valid (3.9s) (colibri2 21) (cvc5 2) (split_vc 6) (depth 5)
1305
let
bits_iv
(fm: format) (h ns: int) (x y: int) : dom
1306
requires { h = half_bits fm /\ ns = nb_sign fm }
1307
requires { 0 <= x /\ y < 2 * h }
1308
ensures { result.fm = fm }
1309
ensures { forall b v. x <= b <= y -> of_bits fm b v -> mem v result }
1310
= {proof…} nb_sign_half fm; {qed}
1311
if y < x then empty_dom fm
1312
else begin
1313
let p =
1314
if x < ns then begin
1315
let y' = if y < ns - 1 then y else ns - 1 in
1316
let l = of_index_f fm x in let u = of_index_f fm y' in
1317
{proof…} of_index_range fm x; of_index_range fm y'; {qed}
1318
let r = interval_o fm l u in
1319
{proof…}
1320
let lemma pt (b: int) : unit requires { x <= b <= y' }
1321
ensures { mem (of_index fm b) r }
1322
= of_index_range fm b in
1323
{qed}
1324
r
1325
end else empty_dom fm in
1326
let x' = if x < h then h else x in
1327
let y' = if y < h + ns - 1 then y else h + ns - 1 in
1328
let n =
1329
if x' <= y' then begin
1330
let l = of_index_f fm (h - 1 - y') in let u = of_index_f fm (h - 1 - x') in
1331
{proof…} of_index_range fm (h - 1 - y'); of_index_range fm (h - 1 - x'); {qed}
1332
let r = interval_o fm l u in
1333
{proof…}
1334
let lemma pt (b: int) : unit requires { x' <= b <= y' }
1335
ensures { mem (of_index fm (h - 1 - b)) r }
1336
= of_index_range fm (h - 1 - b) in
1337
{qed}
1338
r
1339
end else empty_dom fm in
1340
let r = union fm p n in
1341
if y < ns || (h <= x && y < h + ns) then r else union fm r (nan_dom fm)
1342
end
1343
Valid (438ms) (cvc5)
1344
let rec
bits_fwd_l
(fm: format) (h ns: int) (l: ivs) : dom
1345
requires { h = half_bits fm /\ ns = nb_sign fm }
1346
requires { in_rng 0 (2 * h - 1) l }
1347
ensures { result.fm = fm }
1348
ensures { forall b v. imem b l -> of_bits fm b v -> mem v result }
1349
variant { l }
1350
= match l with
1351
| Nil -> empty_dom fm
1352
| Cons (x, y) l' -> union fm (bits_iv fm h ns x y) (bits_fwd_l fm h ns l')
1353
end

The floats of the encodings of l

  Valid (619ms) (colibri2)
1356
let
of_bits_fwd
(fm: format) (l: rdom) : dom
1357
ensures { result.fm = fm }
1358
ensures { forall b v. 0 <= b < 2 * half_bits fm -> rmem (from_int b) l ->
1359
of_bits fm b v -> mem v result }
1360
= let eb = fmt_eb fm in let sb = fmt_sb fm in
1361
let h = pow2 (eb + sb - 1) in
1362
let ns = (pow2 eb - 1) * pow2 (sb - 1) + 1 in
1363
bits_fwd_l fm h ns (to_ivs l 0 (2 * h - 1))

Backward

The encodings of the floats of [a, c]

  Valid (550ms) (cvc4)
1368
let
bits_of_iv
(fm: format) (h: int) (a c: t) : ivs
1369
requires { h = half_bits fm /\ fmt a = fm /\ fmt c = fm }
1370
requires { is_not_nan a /\ is_not_nan c }
1371
ensures { forall b v. of_bits fm b v -> is_not_nan v -> in_iv v a c -> imem b result }
1372
= let ia = index_f a in let ic = index_f c in
1373
{proof…}
1374
nb_sign_half fm;
1375
let lemma pt (b: int) (v: t) : unit
1376
requires { of_bits fm b v /\ is_not_nan v /\ in_iv v a c }
1377
ensures { ia <= index v <= ic }
1378
ensures { 0 <= b < nb_sign fm -> index v = b }
1379
ensures { half_bits fm <= b < half_bits fm + nb_sign fm -> index v = half_bits fm - 1 - b }
1380
= if 0 <= b < nb_sign fm then of_index_range fm b
1381
else if half_bits fm <= b < half_bits fm + nb_sign fm then
1382
of_index_range fm (half_bits fm - 1 - b) in
1383
{qed}
1384
let p = if 0 <= ic then Cons ((if ia < 0 then 0 else ia), ic) Nil else Nil in
1385
let n = if ia <= -1 then Cons (h - 1 - (if ic < -1 then ic else -1), h - 1 - ia) Nil else Nil in
1386
ivs_app p n
1387
Valid (92ms) (cvc5)
1388
let rec
bits_back_u
(fm: format) (h: int) (l: list (t, t)) : ivs
1389
requires { h = half_bits fm /\ ok_u l /\ fmt_u fm l }
1390
ensures { forall b v. of_bits fm b v -> is_not_nan v -> mem_u v l -> imem b result }
1391
variant { l }
1392
= match l with
1393
| Nil -> Nil
1394
| Cons (a, c) l' -> ivs_app (bits_of_iv fm h a c) (bits_back_u fm h l')
1395
end

The encodings of the floats of d

  Valid (342ms) (colibri2 15) (cvc5) (split_vc 2) (depth 2)
1398
let
of_bits_back
(fm: format) (d: dom) : rdom
1399
requires { d.fm = fm }
1400
ensures { forall b v. 0 <= b < 2 * half_bits fm -> of_bits fm b v -> mem v d ->
1401
rmem (from_int b) result }
1402
= let eb = fmt_eb fm in let sb = fmt_sb fm in
1403
let h = pow2 (eb + sb - 1) in
1404
let ns = (pow2 eb - 1) * pow2 (sb - 1) + 1 in
1405
let bu = bits_back_u fm h d.u in
1406
let l = if d.nan then ivs_app (Cons (ns, h - 1) (Cons (h + ns, 2 * h - 1) Nil)) bu else bu in
1407
{proof…}
1408
let lemma pt (b: int) (v: t) : unit
1409
requires { 0 <= b < 2 * h /\ of_bits fm b v /\ mem v d }
1410
ensures { imem b l }
1411
= assert { ns = nb_sign fm /\ h = half_bits fm };
1412
if 0 <= b < ns then begin
1413
of_index_range fm b;
1414
assert { is_not_nan v /\ mem_u v d.u };
1415
assert { imem b bu }
1416
end else if h <= b < h + ns then begin
1417
of_index_range fm (h - 1 - b);
1418
assert { is_not_nan v /\ mem_u v d.u };
1419
assert { imem b bu }
1420
end else begin
1421
assert { is_nan v /\ d.nan };
1422
assert { imem b (Cons (ns, h - 1) (Cons (h + ns, 2 * h - 1) Nil)) }
1423
end in
1424
{qed}
1425
of_ivs l

fp.to_sbv and fp.to_ubv

The reals of the floats of d, when they are finite and in [lo, hi]

  Valid (466ms) (cvc5)
1431
let
in_range
(lo hi: int) (l: rdom) : bool
1432
ensures { result -> forall x. rmem x l -> from_int lo <=. x <=. from_int hi }
1433
= let al = a_of_int lo in let ah = a_of_int hi in
1434
let rec ok (l: rdom) : bool
1435
ensures { result -> forall x. rmem x l -> from_int lo <=. x <=. from_int hi }
1436
variant { l }
1437
= match l with
1438
| Nil -> true
1439
| Cons (RSing a) l' -> a_le al a && a_le a ah && ok l'
1440
| Cons (RInter (BLarge a | BStrict a) (BLarge b | BStrict b)) l' ->
1441
a_le al a && a_le b ah && ok l'
1442
| Cons _ _ -> false
1443
end in
1444
ok l

The reals of l are in [al, ah]

  Valid (606ms) (cvc5)
1447
let rec
in_range_a
(al ah: A.t) (l: rdom) : bool
1448
ensures { result -> forall x. rmem x l -> A.real al <=. x <=. A.real ah }
1449
variant { l }
1450
= match l with
1451
| Nil -> true
1452
| Cons (RSing a) l' -> a_le al a && a_le a ah && in_range_a al ah l'
1453
| Cons (RInter (BLarge a | BStrict a) (BLarge b | BStrict b)) l' ->
1454
a_le al a && a_le b ah && in_range_a al ah l'
1455
| Cons _ _ -> false
1456
end
1457
end