Common — library colibrilib.pbdd — module PBDD2
1113
module PBDD2 : PBDD2_intf

Implemented

1114
use int.MinMax
1115
use mach.int.Int63
1116
use int.Int
1117
use set.Set
1118
use bool.Bool
1119
use colibrilib.sbdd.SNode
1120
use colibrilib.zarith.Zbit
1121
use PBDD
1122
1123
type
env
= int -> snodes
1124
1125
function
shift_env
(sn:env) (w:int) : env = fun q -> sn (q + w)
1126
1127
function
v
(x:PBDD.t) (s:int) (sn:env) : int =
1128
of_bits (fun i -> x.PBDD.v i (sn i)) (lsl 1 s)
1129
1130
function
snode_mask
(nd:snode) (s:int) (sn:env) : int =
1131
of_bits (fun i -> sn i nd) (lsl 1 s)
1132
Valid (33ms) (colibri2)
1133
let lemma
v_nonneg
(x:PBDD.t) (s:int) (sn:env) : unit
1134
ensures { 0 <= v x s sn }
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
1470
end