Common — library colibrilib.pbdd — module PBDD2_intf
981
module PBDD2_intf

Abstract

982
use int.MinMax
983
use mach.int.Int63
984
use int.Int
985
use set.Set
986
use bool.Bool
987
use colibrilib.sbdd.SNode
988
use colibrilib.zarith.Zbit
989
use PBDD

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.

994
type
env
= int -> snodes

The env seen from position w

997
function
shift_env
(sn:env) (w:int) : env = fun q -> sn (q + w)

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).

1003
function
v
(x:PBDD.t) (s:int) (sn:env) : int
1004
Valid (30ms) (colibri2)
1005
axiom
v_nonneg
: forall x s sn. 0 <= v x s sn Valid (42ms) (colibri2)
1006
axiom
def_v
: forall x s sn i.
1007
bittest (v x s sn) i <-> (0 <= i /\ numbits i <= s /\ x.PBDD.v i (sn i))

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

1018
function
snode_mask
(nd:snode) (s:int) (sn:env) : int
1019
Valid (33ms) (colibri2)
1020
axiom
snode_mask_nonneg
: forall nd s sn. 0 <= snode_mask nd s sn Valid (42ms) (colibri2)
1021
axiom
def_snode_mask
: forall nd s sn i.
1022
bittest (snode_mask nd s sn) i <-> (0 <= i /\ numbits i <= s /\ sn i nd)
1023
Valid (33ms) (colibri2)
1024
val
tfalse
() : PBDD.t
1025
ensures { result.dom_indexes = 0 }
1026
ensures { result.dom_snodes = Set.empty }
1027
ensures { result.PBDD.v = (fun _ _ -> False) }
1028
ensures { forall s sn. v result s sn = 0 }
1029
Valid (25ms) (colibri2)
1030
val
ttrue
() : PBDD.t
1031
ensures { result.dom_indexes = 0 }
1032
ensures { result.dom_snodes = Set.empty }
1033
ensures { result.PBDD.v = (fun _ _ -> True) }
1034
ensures { forall s sn. 0 <= s -> v result s sn = mask (lsl 1 s) }
1035
Valid (34ms) (colibri2)
1036
val
dand
(x y: PBDD.t) : PBDD.t
1037
ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1038
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1039
ensures { result.PBDD.v = (fun id sn -> andb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1040
ensures { forall s sn. v result s sn = land (v x s sn) (v y s sn) }
1041
Valid (31ms) (colibri2)
1042
val
dor
(x y: PBDD.t) : PBDD.t
1043
ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1044
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1045
ensures { result.PBDD.v = (fun id sn -> orb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1046
ensures { forall s sn. v result s sn = lor (v x s sn) (v y s sn) }
1047
Valid (29ms) (colibri2)
1048
val
dxor
(x y: PBDD.t) : PBDD.t
1049
ensures { result.dom_indexes = lor x.dom_indexes y.dom_indexes }
1050
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
1051
ensures { result.PBDD.v = (fun id sn -> xorb (x.PBDD.v id sn) (y.PBDD.v id sn)) }
1052
ensures { forall s sn. v result s sn = lxor (v x s sn) (v y s sn) }
1053
Valid (24ms) (colibri2)
1054
val
dnot
(a: PBDD.t) : PBDD.t
1055
ensures { result.dom_indexes = a.dom_indexes }
1056
ensures { result.dom_snodes = a.dom_snodes }
1057
ensures { result.PBDD.v = (fun id sn -> notb (a.PBDD.v id sn)) }
1058
ensures { forall s sn. 0 <= s -> v result s sn = land (lnot (v a s sn)) (mask (lsl 1 s)) }
1059
Valid (35ms) (colibri2)
1060
val partial
ite_snode
(n: snode) (aa bb: PBDD.t) : PBDD.t
1061
ensures { result.dom_indexes = lor aa.dom_indexes bb.dom_indexes }
1062
ensures { result.dom_snodes = Set.add n (Set.union aa.dom_snodes bb.dom_snodes) }
1063
ensures { result.PBDD.v = (fun id sn -> if sn n then aa.PBDD.v id sn else bb.PBDD.v id sn) }
1064
ensures { forall s sn. v result s sn =
1065
lor (land (snode_mask n s sn) (v aa s sn))
1066
(land (lnot (snode_mask n s sn)) (v bb s sn)) }
1067
Valid (33ms) (colibri2)
1068
val partial
bdd_of_snode
(nd: snode) : PBDD.t
1069
ensures { result.dom_indexes = 0 }
1070
ensures { result.dom_snodes = Set.singleton nd }
1071
ensures { result.PBDD.v = (fun _ sn -> sn nd) }
1072
ensures { forall s sn. v result s sn = snode_mask nd s sn }

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
1111
end