library colibrilib.pbdd — module PBDD2_intfmodule PBDD2_intf981
Abstract
use int.MinMax982use mach.int.Int63983use int.Int984use set.Set985use bool.Bool986use colibrilib.sbdd.SNode987use colibrilib.zarith.Zbit988use PBDD989
Valuation of the snodes at each position: in bddbitv.ml the variable Var {n; shift} at position p is the bit p + shift of n, so it depends on the position.
type env = int -> snodes994
The env seen from position w
function shift_env (sn:env) (w:int) : env = fun q -> sn (q + w)997
Integer view of a PBDD on the window s: the non–negative integer whose bit p is the value of the BDD at position p (with the valuation sn p), for the positions representable on s bits (numbits p <= s, i.e. p < 2^s).
function v (x:PBDD.t) (s:int) (sn:env) : int1003Valid (30ms) (colibri2)1004axiom v_nonneg: forall x s sn. 0 <= v x s sn Valid (42ms) (colibri2)1005axiom def_v: forall x s sn i.1006bittest (v x s sn) i <-> (0 <= i /\ numbits i <= s /\ x.PBDD.v i (sn i))1007
Above the support, the upper half of the window s+1 is the window s seen from position 2^s
Valid (41ms) (colibri2)
1010 axiom v_split: forall x s sn. 0 <= s -> numbits x.dom_indexes <= s ->
1011 v x (s+1) sn = lor (v x s sn) (lsl (v x s (shift_env sn (lsl 1 s))) (lsl 1 s))
Restricting a window t to a window s
Valid (46ms) (colibri2)
1014 axiom v_window: forall x s t sn. 0 <= s -> 0 <= t ->
1015 land (v x t sn) (mask (lsl 1 s)) = v x (min s t) sn
The positions of the window s where the snode nd is true
function snode_mask (nd:snode) (s:int) (sn:env) : int1018Valid (33ms) (colibri2)1019axiom snode_mask_nonneg: forall nd s sn. 0 <= snode_mask nd s sn Valid (42ms) (colibri2)1020axiom def_snode_mask: forall nd s sn i.1021bittest (snode_mask nd s sn) i <-> (0 <= i /\ numbits i <= s /\ sn i nd)1022Valid (33ms) (colibri2)1023val tfalse () : PBDD.t1024ensures { result.dom_indexes = 0 }1025ensures { result.dom_snodes = Set.empty }1026ensures { result.PBDD.v = (fun _ _ -> False) }1027ensures { forall s sn. v result s sn = 0 }1028Valid (25ms) (colibri2)1029val ttrue () : PBDD.t1030ensures { result.dom_indexes = 0 }1031ensures { result.dom_snodes = Set.empty }1032ensures { result.PBDD.v = (fun _ _ -> True) }1033ensures { forall s sn. 0 <= s -> v result s sn = mask (lsl 1 s) }1034Valid (34ms) (colibri2)1035val dand (x y: PBDD.t) : PBDD.t1036ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }1037ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }1038ensures { result.PBDD.v = (fun id sn -> andb (x.PBDD.v id sn) (y.PBDD.v id sn)) }1039ensures { forall s sn. v result s sn = land (v x s sn) (v y s sn) }1040Valid (31ms) (colibri2)1041val dor (x y: PBDD.t) : PBDD.t1042ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }1043ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }1044ensures { result.PBDD.v = (fun id sn -> orb (x.PBDD.v id sn) (y.PBDD.v id sn)) }1045ensures { forall s sn. v result s sn = lor (v x s sn) (v y s sn) }1046Valid (29ms) (colibri2)1047val dxor (x y: PBDD.t) : PBDD.t1048ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }1049ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }1050ensures { result.PBDD.v = (fun id sn -> xorb (x.PBDD.v id sn) (y.PBDD.v id sn)) }1051ensures { forall s sn. v result s sn = lxor (v x s sn) (v y s sn) }1052Valid (24ms) (colibri2)1053val dnot (a: PBDD.t) : PBDD.t1054ensures { result.dom_indexes = a.dom_indexes }1055ensures { result.dom_snodes = a.dom_snodes }1056ensures { result.PBDD.v = (fun id sn -> notb (a.PBDD.v id sn)) }1057ensures { forall s sn. 0 <= s -> v result s sn = land (lnot (v a s sn)) (mask (lsl 1 s)) }1058Valid (35ms) (colibri2)1059val partial ite_snode (n: snode) (aa bb: PBDD.t) : PBDD.t1060ensures { result.dom_indexes = lor aa.dom_indexes bb.dom_indexes }1061ensures { result.dom_snodes = Set.add n (Set.union aa.dom_snodes bb.dom_snodes) }1062ensures { result.PBDD.v = (fun id sn -> if sn n then aa.PBDD.v id sn else bb.PBDD.v id sn) }1063ensures { forall s sn. v result s sn =1064lor (land (snode_mask n s sn) (v aa s sn))1065(land (lnot (snode_mask n s sn)) (v bb s sn)) }1066Valid (33ms) (colibri2)1067val partial bdd_of_snode (nd: snode) : PBDD.t1068ensures { result.dom_indexes = 0 }1069ensures { result.dom_snodes = Set.singleton nd }1070ensures { result.PBDD.v = (fun _ sn -> sn nd) }1071ensures { forall s sn. v result s sn = snode_mask nd s sn }1072
Concatenation: aa gives the upper half and bb the lower half of the window i+1.
Valid (30ms) (colibri2)
1076 val partial ite_index (i: int63) (aa bb: PBDD.t) : PBDD.t
1077 requires { 0 <= to_int i }
1078 requires { numbits aa.dom_indexes <= to_int i }
1079 requires { numbits bb.dom_indexes <= to_int i }
1080 ensures { result.dom_indexes = set (lor aa.dom_indexes bb.dom_indexes) i }
1081 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1082 ensures { result.PBDD.v = (fun id sn -> if bittest id i then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1083 ensures { forall sn. v result (to_int i + 1) sn =
1084 lor (v bb i sn) (lsl (v aa i (shift_env sn (lsl 1 i))) (lsl 1 i)) }
ite_index for the indexes 0, 1, 2, in ghost code
Valid (29ms) (colibri2)
1087 val ghost ite_index_g (i: int63) (aa bb: PBDD.t) : PBDD.t
1088 requires { 0 <= to_int i < 3 }
1089 requires { numbits aa.dom_indexes <= to_int i }
1090 requires { numbits bb.dom_indexes <= to_int i }
1091 ensures { result.dom_indexes = set (lor aa.dom_indexes bb.dom_indexes) i }
1092 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
1093 ensures { result.PBDD.v = (fun id sn -> if bittest id i then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1094 ensures { forall sn. v result (to_int i + 1) sn =
1095 lor (v bb i sn) (lsl (v aa i (shift_env sn (lsl 1 i))) (lsl 1 i)) }
The upper half of the window k+1 is empty
Valid (38ms) (colibri2)
1098 val partial upper_empty (x: PBDD.t) (k: int63) : bool
1099 requires { 0 <= to_int k }
1100 requires { numbits x.dom_indexes <= to_int k + 1 }
1101 ensures { result <-> forall sn. v x (to_int k + 1) sn = v x k sn }
Restriction to the lower half of the window k+1
Valid (30ms) (colibri2)
1104 val partial cofactor_low (x: PBDD.t) (k: int63) : PBDD.t
1105 requires { 0 <= to_int k }
1106 requires { numbits x.dom_indexes <= to_int k + 1 }
1107 ensures { numbits result.dom_indexes <= to_int k }
1108 ensures { result.dom_snodes = x.dom_snodes }
1109 ensures { forall sn. v result k sn = v x k sn }
1110
1111end