library colibrilib.pbdd — module PBDD2module PBDD2 : PBDD2_intf1113
Implemented
use int.MinMax1114use mach.int.Int631115use int.Int1116use set.Set1117use bool.Bool1118use colibrilib.sbdd.SNode1119use colibrilib.zarith.Zbit1120use PBDD11211122type env = int -> snodes11231124function shift_env (sn:env) (w:int) : env = fun q -> sn (q + w)11251126function v (x:PBDD.t) (s:int) (sn:env) : int =1127of_bits (fun i -> x.PBDD.v i (sn i)) (lsl 1 s)11281129function snode_mask (nd:snode) (s:int) (sn:env) : int =1130of_bits (fun i -> sn i nd) (lsl 1 s)1131Valid (33ms) (colibri2)1132let lemma v_nonneg (x:PBDD.t) (s:int) (sn:env) : unit1133ensures { 0 <= v x s sn }1134= ()1135
Positions of the window s
Valid (57ms) (colibri2)
1138 let lemma window (i s:int) : unit
1139 requires { 0 <= i }
1140 ensures { i < lsl 1 s <-> numbits i <= s }
1141 =
1142 numbits_ge_pos 0 i;
1143 if s < 0 then begin
1144 ext_bittest (lsl 1 s) 0
1145 end else begin
1146 mask_nonneg s;
1147 if i < lsl 1 s then numbits_lt_lsl i s
1148 else begin
1149 numbits_lsl s;
1150 numbits_ge_pos (lsl 1 s) i
1151 end
1152 end
1153
Valid (79ms) (colibri2)
1154 let lemma def_v (x:PBDD.t) (s:int) (sn:env) (i:int) : unit
1155 ensures { bittest (v x s sn) i <-> (0 <= i /\ numbits i <= s /\ x.PBDD.v i (sn i)) }
1156 = if 0 <= i then window i s
1157
Valid (27ms) (colibri2)
1158 let lemma snode_mask_nonneg (nd:snode) (s:int) (sn:env) : unit
1159 ensures { 0 <= snode_mask nd s sn }
1160 = ()
1161
Valid (74ms) (colibri2)
1162 let lemma def_snode_mask (nd:snode) (s:int) (sn:env) (i:int) : unit
1163 ensures { bittest (snode_mask nd s sn) i <-> (0 <= i /\ numbits i <= s /\ sn i nd) }
1164 = if 0 <= i then window i s
Above the support, the value only depends on the position modulo 2^s
Valid (384ms) (colibri2)
1167 let lemma v_shift (x:PBDD.t) (s p:int) (sn:snodes) : unit
1168 requires { 0 <= s }
1169 requires { numbits x.dom_indexes <= s }
1170 requires { lsl 1 s <= p }
1171 ensures { x.PBDD.v p sn = x.PBDD.v (p - lsl 1 s) sn }
1172 =
1173 PBDD.support_v x p (p - lsl 1 s) sn
1174
Valid (1.8s) (colibri2 11) (split_vc 2) (depth 2)
1175 let lemma v_split (x:PBDD.t) (s:int) (sn:env) : unit
1176 requires { 0 <= s }
1177 requires { numbits x.dom_indexes <= s }
1178 ensures { v x (s+1) sn = lor (v x s sn) (lsl (v x s (shift_env sn (lsl 1 s))) (lsl 1 s)) }
1179 =
1180 let w = lsl 1 s in
1181 let sn' = shift_env sn w in
1182 let lemma bit (i:int) : unit
1183 requires { 0 <= i }
1184 ensures { bittest (v x (s+1) sn) i <-> bittest (lor (v x s sn) (lsl (v x s sn') w)) i }
1185 =
1186 window i s;
1187 window i (s+1);
1188 if w <= i then begin
1189 window (i - w) s;
1190 assert { sn' (i - w) = sn i };
1191 v_shift x s i (sn i)
1192 end
1193 in
1194 ext_bittest (v x (s+1) sn) (lor (v x s sn) (lsl (v x s sn') w))
1195
Valid (362ms) (cvc4)
1196 let lemma v_window (x:PBDD.t) (s t:int) (sn:env) : unit
1197 requires { 0 <= s /\ 0 <= t }
1198 ensures { land (v x t sn) (mask (lsl 1 s)) = v x (min s t) sn }
1199 =
1200 mask_nonneg s;
1201 let lemma bit (i:int) : unit
1202 requires { 0 <= i }
1203 ensures { bittest (land (v x t sn) (mask (lsl 1 s))) i <-> bittest (v x (min s t) sn) i }
1204 = window i s; window i t
1205 in
1206 ext_bittest (land (v x t sn) (mask (lsl 1 s))) (v x (min s t) sn)
1207
Valid (342ms) (cvc4)
1208 let tfalse () : PBDD.t
1209 ensures { result.dom_indexes = 0 }
1210 ensures { result.dom_snodes = Set.empty }
1211 ensures { result.PBDD.v = (fun _ _ -> False) }
1212 ensures { forall s sn. v result s sn = 0 }
1213 =
1214 let r = PBDD.tfalse () in
1215 let lemma eq (s:int) (sn:env) : unit
1216 ensures { v r s sn = 0 }
1217 = ext_bittest (v r s sn) 0
1218 in
1219 r
1220
Valid (340ms) (cvc4)
1221 let ttrue () : PBDD.t
1222 ensures { result.dom_indexes = 0 }
1223 ensures { result.dom_snodes = Set.empty }
1224 ensures { result.PBDD.v = (fun _ _ -> True) }
1225 ensures { forall s sn. 0 <= s -> v result s sn = mask (lsl 1 s) }
1226 =
1227 let r = PBDD.ttrue () in
1228 let lemma eq (s:int) (sn:env) : unit
1229 requires { 0 <= s }
1230 ensures { v r s sn = mask (lsl 1 s) }
1231 =
1232 mask_nonneg s;
1233 ext_bittest (v r s sn) (mask (lsl 1 s))
1234 in
1235 r
1236
Valid (334ms) (cvc4)
1237 let dand (x y: PBDD.t) : PBDD.t
1238 ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1239 ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1240 ensures { result.PBDD.v = (fun id sn -> andb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1241 ensures { forall s sn. v result s sn = land (v x s sn) (v y s sn) }
1242 =
1243 let r = PBDD.dand x y in
1244 let lemma eq (s:int) (sn:env) : unit
1245 ensures { v r s sn = land (v x s sn) (v y s sn) }
1246 = ext_bittest (v r s sn) (land (v x s sn) (v y s sn))
1247 in
1248 r
1249
Valid (347ms) (cvc4)
1250 let dor (x y: PBDD.t) : PBDD.t
1251 ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1252 ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1253 ensures { result.PBDD.v = (fun id sn -> orb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1254 ensures { forall s sn. v result s sn = lor (v x s sn) (v y s sn) }
1255 =
1256 let r = PBDD.dor x y in
1257 let lemma eq (s:int) (sn:env) : unit
1258 ensures { v r s sn = lor (v x s sn) (v y s sn) }
1259 = ext_bittest (v r s sn) (lor (v x s sn) (v y s sn))
1260 in
1261 r
1262
Valid (255ms) (cvc4)
1263 let dxor (x y: PBDD.t) : PBDD.t
1264 ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1265 ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1266 ensures { result.PBDD.v = (fun id sn -> xorb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1267 ensures { forall s sn. v result s sn = lxor (v x s sn) (v y s sn) }
1268 =
1269 let r = PBDD.dxor x y in
1270 let lemma eq (s:int) (sn:env) : unit
1271 ensures { v r s sn = lxor (v x s sn) (v y s sn) }
1272 = ext_bittest (v r s sn) (lxor (v x s sn) (v y s sn))
1273 in
1274 r
1275
Valid (440ms) (cvc4)
1276 let dnot (a: PBDD.t) : PBDD.t
1277 ensures { result.dom_indexes = a.dom_indexes }
1278 ensures { result.dom_snodes = a.dom_snodes }
1279 ensures { result.PBDD.v = (fun id sn -> notb (a.PBDD.v id sn)) }
1280 ensures { forall s sn. 0 <= s -> v result s sn = land (lnot (v a s sn)) (mask (lsl 1 s)) }
1281 =
1282 let r = PBDD.dnot a in
1283 let lemma eq (s:int) (sn:env) : unit
1284 requires { 0 <= s }
1285 ensures { v r s sn = land (lnot (v a s sn)) (mask (lsl 1 s)) }
1286 =
1287 mask_nonneg s;
1288 let lemma bit (i:int) : unit
1289 requires { 0 <= i }
1290 ensures { bittest (v r s sn) i <-> bittest (land (lnot (v a s sn)) (mask (lsl 1 s))) i }
1291 =
1292 window i s
1293 in
1294 ext_bittest (v r s sn) (land (lnot (v a s sn)) (mask (lsl 1 s)))
1295 in
1296 r
1297
Valid (327ms) (cvc4)
1298 let partial bdd_of_snode (nd: snode) : PBDD.t
1299 ensures { result.dom_indexes = 0 }
1300 ensures { result.dom_snodes = Set.singleton nd }
1301 ensures { result.PBDD.v = (fun _ sn -> sn nd) }
1302 ensures { forall s sn. v result s sn = snode_mask nd s sn }
1303 =
1304 let r = PBDD.bdd_of_snode nd in
1305 let lemma eq (s:int) (sn:env) : unit
1306 ensures { v r s sn = snode_mask nd s sn }
1307 = ext_bittest (v r s sn) (snode_mask nd s sn)
1308 in
1309 r
1310
Valid (2.0s) (colibri2 5) (cvc4 2) (split_vc 2) (depth 2)
1311 let partial ite_snode (n: snode) (aa bb: PBDD.t) : PBDD.t
1312 ensures { result.dom_indexes = lor aa.dom_indexes bb.dom_indexes }
1313 ensures { result.dom_snodes = Set.add n (Set.union aa.dom_snodes bb.dom_snodes) }
1314 ensures { result.PBDD.v = (fun id sn -> if sn n then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1315 ensures { forall s sn. v result s sn =
1316 lor (land (snode_mask n s sn) (v aa s sn))
1317 (land (lnot (snode_mask n s sn)) (v bb s sn)) }
1318 =
1319 let r = PBDD.ite_snode n aa bb in
1320 let lemma eq (s:int) (sn:env) : unit
1321 ensures { v r s sn = lor (land (snode_mask n s sn) (v aa s sn))
1322 (land (lnot (snode_mask n s sn)) (v bb s sn)) }
1323 = ext_bittest (v r s sn) (lor (land (snode_mask n s sn) (v aa s sn))
1324 (land (lnot (snode_mask n s sn)) (v bb s sn)))
1325 in
1326 r
1327
Valid (1.1s) (colibri2 22) (cvc4 4) (split_vc 4) (depth 4)
1328 let partial ite_index (i: int63) (aa bb: PBDD.t) : PBDD.t
1329 requires { 0 <= to_int i }
1330 requires { numbits aa.dom_indexes <= to_int i }
1331 requires { numbits bb.dom_indexes <= to_int i }
1332 ensures { result.dom_indexes = set (lor aa.dom_indexes bb.dom_indexes) i }
1333 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1334 ensures { result.PBDD.v = (fun id sn -> if bittest id i then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1335 ensures { forall sn. v result (to_int i + 1) sn =
1336 lor (v bb i sn) (lsl (v aa i (shift_env sn (lsl 1 i))) (lsl 1 i)) }
1337 =
1338 let r = PBDD.ite_index i aa bb in
1339 let ghost k = to_int i in
1340 let ghost w = lsl 1 k in
1341 numbits_lsl k;
1342 let lemma eq (sn:env) : unit
1343 ensures { v r (k + 1) sn = lor (v bb k sn) (lsl (v aa k (shift_env sn w)) w) }
1344 =
1345 let sn' = shift_env sn w in
1346 let lemma bit (p:int) : unit
1347 requires { 0 <= p }
1348 ensures { bittest (v r (k+1) sn) p <-> bittest (lor (v bb k sn) (lsl (v aa k sn') w)) p }
1349 =
1350 window p k;
1351 window p (k+1);
1352 assert { bittest (lsl (v aa k sn') w) p <-> bittest (v aa k sn') (p - w) };
1353 if p < w then begin
1354 if p > 0 then assert { numbits p <= k }
1355 end else if p < 2 * w then begin
1356 numbits_ge_pos w p;
1357 numbits_lt_lsl p (k+1);
1358 window (p - w) k;
1359 assert { sn' (p - w) = sn p };
1360 v_shift aa k p (sn p)
1361 end
1362 in
1363 ext_bittest (v r (k+1) sn) (lor (v bb k sn) (lsl (v aa k sn') w))
1364 in
1365 r
1366
1367
Valid (755ms) (colibri2 23) (cvc4 3) (split_vc 4) (depth 4)
1368 let ghost ite_index_g (i: int63) (aa bb: PBDD.t) : PBDD.t
1369 requires { 0 <= to_int i < 3 }
1370 requires { numbits aa.dom_indexes <= to_int i }
1371 requires { numbits bb.dom_indexes <= to_int i }
1372 ensures { result.dom_indexes = set (lor aa.dom_indexes bb.dom_indexes) i }
1373 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1374 ensures { result.PBDD.v = (fun id sn -> if bittest id i then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1375 ensures { forall sn. v result (to_int i + 1) sn =
1376 lor (v bb i sn) (lsl (v aa i (shift_env sn (lsl 1 i))) (lsl 1 i)) }
1377 =
1378 let r = PBDD.ite_index_g i aa bb in
1379 let k = to_int i in
1380 let w = lsl 1 k in
1381 numbits_lsl k;
1382 let lemma eq (sn:env) : unit
1383 ensures { v r (k + 1) sn = lor (v bb k sn) (lsl (v aa k (shift_env sn w)) w) }
1384 =
1385 let sn' = shift_env sn w in
1386 let lemma bit (p:int) : unit
1387 requires { 0 <= p }
1388 ensures { bittest (v r (k+1) sn) p <-> bittest (lor (v bb k sn) (lsl (v aa k sn') w)) p }
1389 =
1390 window p k;
1391 window p (k+1);
1392 assert { bittest (lsl (v aa k sn') w) p <-> bittest (v aa k sn') (p - w) };
1393 if p < w then begin
1394 if p > 0 then assert { numbits p <= k }
1395 end else if p < 2 * w then begin
1396 numbits_ge_pos w p;
1397 numbits_lt_lsl p (k+1);
1398 window (p - w) k;
1399 assert { sn' (p - w) = sn p };
1400 v_shift aa k p (sn p)
1401 end
1402 in
1403 ext_bittest (v r (k+1) sn) (lor (v bb k sn) (lsl (v aa k sn') w))
1404 in
1405 r
1406
1407
Valid (403ms) (colibri2 10) (cvc4 5) (split_vc) (depth 1)
1408 let partial upper_empty (x: PBDD.t) (k: int63) : bool
1409 requires { 0 <= to_int k }
1410 requires { numbits x.dom_indexes <= to_int k + 1 }
1411 ensures { result <-> forall sn. v x (to_int k + 1) sn = v x k sn }
1412 =
1413 let ghost ki = to_int k in
1414 let (r, ghost _wi, ghost _ws) = PBDD.is_inter_empty x (PBDD.bdd_of_index k) in
1415 if r then begin
1416 let lemma eq (sn:env) : unit
1417 ensures { v x (ki + 1) sn = v x ki sn }
1418 =
1419 let lemma bit (p:int) : unit
1420 requires { 0 <= p }
1421 ensures { bittest (v x (ki + 1) sn) p <-> bittest (v x ki sn) p }
1422 = if numbits p = ki + 1 then numbits_top_bit p
1423 in
1424 ext_bittest (v x (ki + 1) sn) (v x ki sn)
1425 in ()
1426 end else begin
1427 let lemma not_eq (id:int) (sn:snodes) : unit
1428 requires { x.PBDD.v id sn /\ bittest id ki }
1429 ensures { v x (ki + 1) (fun _ -> sn) <> v x ki (fun _ -> sn) }
1430 =
1431 let id' = of_bits (fun i -> bittest id i) (ki + 1) in
1432 numbits_high_clear id' (numbits id');
1433 if numbits id' > ki + 1 then numbits_top_bit id';
1434 PBDD.support_v x id id' sn;
1435 assert { bittest (v x (ki + 1) (fun _ -> sn)) id' }
1436 in ()
1437 end;
1438 r
1439
Valid (688ms) (colibri2 13) (cvc4 4) (split_vc) (depth 1)
1440 let partial cofactor_low (x: PBDD.t) (k: int63) : PBDD.t
1441 requires { 0 <= to_int k }
1442 requires { numbits x.dom_indexes <= to_int k + 1 }
1443 ensures { numbits result.dom_indexes <= to_int k }
1444 ensures { result.dom_snodes = x.dom_snodes }
1445 ensures { forall sn. v result k sn = v x k sn }
1446 =
1447 let ghost ki = to_int k in
1448 let r = PBDD.compose_index k (PBDD.tfalse ()) x in
1449 let ghost u = unset x.dom_indexes ki in
1450 unset_nonneg x.dom_indexes ki;
1451 numbits_unset_le x.dom_indexes ki;
1452 if u > 0 && numbits u = ki + 1 then numbits_top_bit u;
1453 ext_bittest (lor 0 u) u;
1454 let lemma eq (sn:env) : unit
1455 ensures { v r ki sn = v x ki sn }
1456 =
1457 let lemma bit (p:int) : unit
1458 requires { 0 <= p }
1459 ensures { bittest (v r ki sn) p <-> bittest (v x ki sn) p }
1460 =
1461 if numbits p <= ki then begin
1462 if p > 0 then numbits_high_clear p ki;
1463 ext_bittest (change p ki False) p
1464 end
1465 in
1466 ext_bittest (v r ki sn) (v x ki sn)
1467 in
1468 r
1469
1470end