library colibrilib.fp_conv — module BvConvto_fp of the IEEE encoding, on the domains: the encoding is the integer node of the bit–vector.
module BvConv1191use int.Int1192use int.Power1193use list.List1194use option.Option1195use real.RealInfix1196use real.FromInt1197use real.Truncate1198use colibrilib.ring.Atom1199use colibrilib.fbin.Fp1200use colibrilib.fp_facts.Facts1201use colibrilib.stda.StdA as A1202use colibrilib.fp_interval.Intervals1203use colibrilib.fp_interval.FpInterval1204use Env1205use RealConv1206
The encodings of the negative floats start at half_bits fm (the sign bit)
function half_bits (fm: format) : int = power 2 (eb fm + sb fm - 1)1210
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
predicate of_bits (fm: format) (b: int) (x: t) =1216if 0 <= b < nb_sign fm then x = of_index fm b1217else if half_bits fm <= b < half_bits fm + nb_sign fm then1218x = of_index fm (half_bits fm - 1 - b)1219else fmt x = fm /\ is_nan x1220Valid (103ms) (colibri2)1221let ghost nb_sign_half (fm: format) : unit1222ensures { 0 < nb_sign fm <= half_bits fm }1223= {proof…}1224assert { power 2 (eb fm + sb fm - 1) = power 2 (eb fm) * power 2 (sb fm - 1) };1225assert { 2 <= power 2 (sb fm - 1) /\ 2 <= power 2 (eb fm) }1226{qed}1227Valid (36ms) (colibri2)1228let rec pow2 (n: int) : int1229requires { 0 <= n }1230ensures { result = power 2 n }1231variant { n }1232= if n = 0 then 1 else 2 * pow2 (n - 1)1233
type ivs = list (int, int)12361237predicate imem (z: int) (l: ivs) =1238match l with Nil -> false | Cons (x, y) l' -> x <= z <= y \/ imem z l' end12391240predicate in_rng (lo hi: int) (l: ivs) =1241match l with Nil -> true | Cons (x, y) l' -> lo <= x /\ y <= hi /\ in_rng lo hi l' end1242Valid (36ms) (colibri2)1243let rec ivs_app (l1 l2: ivs) : ivs1244ensures { forall z. imem z l1 \/ imem z l2 -> imem z result }1245variant { l1 }1246= match l1 with Nil -> l2 | Cons i l' -> Cons i (ivs_app l' l2) end1247
The least integer of the bound, or dflt
Valid (34ms) (colibri2)let int_lo (b: bnd) (dflt: int) : int1250ensures { forall z. dflt <= z -> rmem_lo (from_int z) b -> result <= z }1251= match b with1252| BInf -> dflt1253| BLarge a -> a_ceil a1254| BStrict a ->1255{proof…} let lemma pt (z: int) : unit1256requires { A.real a <. from_int z } ensures { floor (A.real a) + 1 <= z }1257= assert { from_int (floor (A.real a)) <=. A.real a };1258assert { floor (A.real a) < z } in {qed}1259a_floor a + 11260end1261Valid (35ms) (colibri2)1262let int_hi (b: bnd) (dflt: int) : int1263ensures { forall z. z <= dflt -> rmem_hi (from_int z) b -> z <= result }1264= match b with1265| BInf -> dflt1266| BLarge a -> a_floor a1267| BStrict a ->1268{proof…} let lemma pt (z: int) : unit1269requires { from_int z <. A.real a } ensures { z <= ceil (A.real a) - 1 }1270= assert { A.real a <=. from_int (ceil (A.real a)) };1271assert { z < ceil (A.real a) } in {qed}1272a_ceil a - 11273end1274
The integers of l in [lo, hi]
Valid (381ms) (colibri2)let rec to_ivs (l: rdom) (lo hi: int) : ivs1277ensures { forall z. lo <= z <= hi -> rmem (from_int z) l -> imem z result }1278ensures { in_rng lo hi result }1279variant { l }1280= match l with1281| Nil -> Nil1282| Cons i l' ->1283let (x, y) = match i with1284| RSing a -> (a_ceil a, a_floor a)1285| RInter bl bh -> (int_lo bl lo, int_hi bh hi)1286end in1287let x = if x < lo then lo else x in1288let y = if hi < y then hi else y in1289let r = to_ivs l' lo hi in1290if x <= y then Cons (x, y) r else r1291end1292Valid (36ms) (colibri2)1293let rec of_ivs (l: ivs) : rdom1294ensures { forall z. imem z l -> rmem (from_int z) result }1295variant { l }1296= match l with1297| Nil -> Nil1298| Cons (x, y) l' -> Cons (RInter (BLarge (a_of_int x)) (BLarge (a_of_int y))) (of_ivs l')1299end1300
The floats of the encodings in [x, y]
Valid (3.9s) (colibri2 21) (cvc5 2) (split_vc 6) (depth 5)let bits_iv (fm: format) (h ns: int) (x y: int) : dom1305requires { h = half_bits fm /\ ns = nb_sign fm }1306requires { 0 <= x /\ y < 2 * h }1307ensures { result.fm = fm }1308ensures { forall b v. x <= b <= y -> of_bits fm b v -> mem v result }1309= {proof…} nb_sign_half fm; {qed}1310if y < x then empty_dom fm1311else begin1312let p =1313if x < ns then begin1314let y' = if y < ns - 1 then y else ns - 1 in1315let l = of_index_f fm x in let u = of_index_f fm y' in1316{proof…} of_index_range fm x; of_index_range fm y'; {qed}1317let r = interval_o fm l u in1318{proof…}1319let lemma pt (b: int) : unit requires { x <= b <= y' }1320ensures { mem (of_index fm b) r }1321= of_index_range fm b in1322{qed}1323r1324end else empty_dom fm in1325let x' = if x < h then h else x in1326let y' = if y < h + ns - 1 then y else h + ns - 1 in1327let n =1328if x' <= y' then begin1329let l = of_index_f fm (h - 1 - y') in let u = of_index_f fm (h - 1 - x') in1330{proof…} of_index_range fm (h - 1 - y'); of_index_range fm (h - 1 - x'); {qed}1331let r = interval_o fm l u in1332{proof…}1333let lemma pt (b: int) : unit requires { x' <= b <= y' }1334ensures { mem (of_index fm (h - 1 - b)) r }1335= of_index_range fm (h - 1 - b) in1336{qed}1337r1338end else empty_dom fm in1339let r = union fm p n in1340if y < ns || (h <= x && y < h + ns) then r else union fm r (nan_dom fm)1341end1342Valid (438ms) (cvc5)1343let rec bits_fwd_l (fm: format) (h ns: int) (l: ivs) : dom1344requires { h = half_bits fm /\ ns = nb_sign fm }1345requires { in_rng 0 (2 * h - 1) l }1346ensures { result.fm = fm }1347ensures { forall b v. imem b l -> of_bits fm b v -> mem v result }1348variant { l }1349= match l with1350| Nil -> empty_dom fm1351| Cons (x, y) l' -> union fm (bits_iv fm h ns x y) (bits_fwd_l fm h ns l')1352end1353
The floats of the encodings of l
Valid (619ms) (colibri2)let of_bits_fwd (fm: format) (l: rdom) : dom1356ensures { result.fm = fm }1357ensures { forall b v. 0 <= b < 2 * half_bits fm -> rmem (from_int b) l ->1358of_bits fm b v -> mem v result }1359= let eb = fmt_eb fm in let sb = fmt_sb fm in1360let h = pow2 (eb + sb - 1) in1361let ns = (pow2 eb - 1) * pow2 (sb - 1) + 1 in1362bits_fwd_l fm h ns (to_ivs l 0 (2 * h - 1))1363
The encodings of the floats of [a, c]
Valid (550ms) (cvc4)let bits_of_iv (fm: format) (h: int) (a c: t) : ivs1368requires { h = half_bits fm /\ fmt a = fm /\ fmt c = fm }1369requires { is_not_nan a /\ is_not_nan c }1370ensures { forall b v. of_bits fm b v -> is_not_nan v -> in_iv v a c -> imem b result }1371= let ia = index_f a in let ic = index_f c in1372{proof…}1373nb_sign_half fm;1374let lemma pt (b: int) (v: t) : unit1375requires { of_bits fm b v /\ is_not_nan v /\ in_iv v a c }1376ensures { ia <= index v <= ic }1377ensures { 0 <= b < nb_sign fm -> index v = b }1378ensures { half_bits fm <= b < half_bits fm + nb_sign fm -> index v = half_bits fm - 1 - b }1379= if 0 <= b < nb_sign fm then of_index_range fm b1380else if half_bits fm <= b < half_bits fm + nb_sign fm then1381of_index_range fm (half_bits fm - 1 - b) in1382{qed}1383let p = if 0 <= ic then Cons ((if ia < 0 then 0 else ia), ic) Nil else Nil in1384let n = if ia <= -1 then Cons (h - 1 - (if ic < -1 then ic else -1), h - 1 - ia) Nil else Nil in1385ivs_app p n1386Valid (92ms) (cvc5)1387let rec bits_back_u (fm: format) (h: int) (l: list (t, t)) : ivs1388requires { h = half_bits fm /\ ok_u l /\ fmt_u fm l }1389ensures { forall b v. of_bits fm b v -> is_not_nan v -> mem_u v l -> imem b result }1390variant { l }1391= match l with1392| Nil -> Nil1393| Cons (a, c) l' -> ivs_app (bits_of_iv fm h a c) (bits_back_u fm h l')1394end1395
The encodings of the floats of d
Valid (342ms) (colibri2 15) (cvc5) (split_vc 2) (depth 2)let of_bits_back (fm: format) (d: dom) : rdom1398requires { d.fm = fm }1399ensures { forall b v. 0 <= b < 2 * half_bits fm -> of_bits fm b v -> mem v d ->1400rmem (from_int b) result }1401= let eb = fmt_eb fm in let sb = fmt_sb fm in1402let h = pow2 (eb + sb - 1) in1403let ns = (pow2 eb - 1) * pow2 (sb - 1) + 1 in1404let bu = bits_back_u fm h d.u in1405let l = if d.nan then ivs_app (Cons (ns, h - 1) (Cons (h + ns, 2 * h - 1) Nil)) bu else bu in1406{proof…}1407let lemma pt (b: int) (v: t) : unit1408requires { 0 <= b < 2 * h /\ of_bits fm b v /\ mem v d }1409ensures { imem b l }1410= assert { ns = nb_sign fm /\ h = half_bits fm };1411if 0 <= b < ns then begin1412of_index_range fm b;1413assert { is_not_nan v /\ mem_u v d.u };1414assert { imem b bu }1415end else if h <= b < h + ns then begin1416of_index_range fm (h - 1 - b);1417assert { is_not_nan v /\ mem_u v d.u };1418assert { imem b bu }1419end else begin1420assert { is_nan v /\ d.nan };1421assert { imem b (Cons (ns, h - 1) (Cons (h + ns, 2 * h - 1) Nil)) }1422end in1423{qed}1424of_ivs l1425
fp.to_sbv and fp.to_ubvThe reals of the floats of d, when they are finite and in [lo, hi]
Valid (466ms) (cvc5)let in_range (lo hi: int) (l: rdom) : bool1431ensures { result -> forall x. rmem x l -> from_int lo <=. x <=. from_int hi }1432= let al = a_of_int lo in let ah = a_of_int hi in1433let rec ok (l: rdom) : bool1434ensures { result -> forall x. rmem x l -> from_int lo <=. x <=. from_int hi }1435variant { l }1436= match l with1437| Nil -> true1438| Cons (RSing a) l' -> a_le al a && a_le a ah && ok l'1439| Cons (RInter (BLarge a | BStrict a) (BLarge b | BStrict b)) l' ->1440a_le al a && a_le b ah && ok l'1441| Cons _ _ -> false1442end in1443ok l1444
The reals of l are in [al, ah]
Valid (606ms) (cvc5)let rec in_range_a (al ah: A.t) (l: rdom) : bool1447ensures { result -> forall x. rmem x l -> A.real al <=. x <=. A.real ah }1448variant { l }1449= match l with1450| Nil -> true1451| Cons (RSing a) l' -> a_le al a && a_le a ah && in_range_a al ah l'1452| Cons (RInter (BLarge a | BStrict a) (BLarge b | BStrict b)) l' ->1453a_le al a && a_le b ah && in_range_a al ah l'1454| Cons _ _ -> false1455end1456end1457