library colibrilib.pbdd — module PBDD_intfmodule PBDD_intf1
Abstract
use mach.int.Int632use list.List3use list.Mem4use list.Distinct5use colibrilib.bdd.Key6use int.Int7use set.Set8use bool.Bool9use colibrilib.bdd.Node10use colibrilib.zarith.Zbit11use colibrilib.sbdd.SNode12use colibrilib.bdd.IArray631314type t15type indexes = int16type snodes = Set.set snode17function dom_indexes (x:t) : indexes Valid (40ms) (colibri2)18axiom dom_indexes_pos : forall x:t. 0 <= dom_indexes x19function dom_snodes (x:t) : snodes20function v (x:t): indexes -> snodes -> bool21Valid (45ms) (colibri2)22axiom support_v: forall x id1 id2 sn.23(forall i. 0 <= i -> Zbit.bittest x.dom_indexes i -> (Zbit.bittest id1 i <-> Zbit.bittest id2 i)) ->24x.v id1 sn = x.v id2 sn2526(* axiom false_after_numbits: forall x id sn. x.dom_numbits <= id -> x.v id sn = False *)27Valid (36ms) (colibri2)28val dand (x y: t) : t29ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }30ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }31ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) }32Valid (39ms) (colibri2)33val dor (x y: t) : t34ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }35ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }36ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) }37Valid (33ms) (colibri2)38val dxor (x y: t) : t39ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }40ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }41ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) }42Valid (33ms) (colibri2)43val tfalse () : t44ensures { result.dom_indexes = 0 }45ensures { result.dom_snodes = Set.empty }46ensures { result.v = (fun _ _ -> False) }47Valid (29ms) (colibri2)48val ttrue () : t49ensures { result.dom_indexes = 0 }50ensures { result.dom_snodes = Set.empty }51ensures { result.v = (fun _ _ -> True) }5253Valid (35ms) (colibri2)54val dnot (a: t) : t55ensures { result.dom_indexes = a.dom_indexes }56ensures { result.dom_snodes = a.dom_snodes }57ensures { result.v = (fun id sn -> notb (a.v id sn)) }58Valid (35ms) (colibri2)59val is_equal (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)60ensures { result = (forall id sn. x.v id sn = y.v id sn) }61ensures { not result ->620 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\63(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\64(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\65x.v wid wsn <> y.v wid wsn }66Valid (62ms) (colibri2)67val is_inter_empty (x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)68ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }69ensures { not result ->70(forall i. Zbit.bittest wid i -> Zbit.bittest (Zbit.lor x.dom_indexes y.dom_indexes) i) /\71(forall i. Set.mem i wsn -> Set.mem i (Set.union x.dom_snodes y.dom_snodes)) /\72x.v wid wsn /\ y.v wid wsn }73Valid (31ms) (colibri2)74val partial bdd_of_index (i: int63) : t75requires { 0 <= to_int i }76ensures { result.dom_indexes = Zbit.lsl 1 (to_int i) }77ensures { result.dom_snodes = Set.empty }78ensures { result.v = (fun id _ -> Zbit.bittest id (to_int i)) }79Valid (36ms) (colibri2)80val partial bdd_of_snode (v: snode) : t81ensures { result.dom_indexes = 0 }82ensures { result.dom_snodes = Set.singleton v }83ensures { result.v = (fun _ sn -> sn v) }84Valid (33ms) (colibri2)85val partial bdd_not_snode (v: snode) : t86ensures { result.dom_indexes = 0 }87ensures { result.dom_snodes = Set.singleton v }88ensures { result.v = (fun _ sn -> not (sn v)) }89Valid (84ms) (cvc4)90val partial ite_index (i: int63) (aa bb: t) : t91requires { 0 <= to_int i }92ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }93ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }94ensures { result.v = (fun id sn -> if Zbit.bittest id i then aa.v id sn else bb.v id sn) }95
ite_index for the indexes 0, 1, 2, in ghost code
Valid (103ms) (colibri2)
98 val ghost ite_index_g (i: int63) (aa bb: t) : t
99 requires { 0 <= to_int i < 3 }
100 ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }
101 ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
102 ensures { result.v = (fun id sn -> if Zbit.bittest id i then aa.v id sn else bb.v id sn) }
103
Valid (35ms) (colibri2)
104 val partial ite_snode (v: snode) (aa bb: t) : t
105 ensures { result.dom_indexes = (Zbit.lor aa.dom_indexes bb.dom_indexes) }
106 ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }
107 ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) }
108
109 function nb_nodes (a:t) : int
The snodes of the BDD, included in the domain
function support_snodes (a:t) : snodes113Valid (33ms) (colibri2)114axiom support_snodes_dom: forall x. Set.subset (support_snodes x) x.dom_snodes115
A snode of the support changes the value
Valid (70ms) (colibri2)
118 axiom support_snodes_dep: forall x nd. Set.mem nd (support_snodes x) ->
119 exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn)
120
Valid (49ms) (colibri2)
121 axiom support_snodes_v: forall x id sn1 sn2.
122 (forall nd. Set.mem nd (support_snodes x) -> sn1 nd = sn2 nd) ->
123 x.v id sn1 = x.v id sn2
124
Valid (36ms) (colibri2)
125 val vars (a:t) : list Key.t
126 ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }
127 ensures { Distinct.distinct result }
128
129 type inspect = Bool bool | IteIndex int63 t t | IteSnode snode t t
The bits of the substitution subst on the valuation id, sn
function subst_bits (subst: IArray63.t t) (id: indexes) (sn: snodes) : int -> bool =132fun i -> (subst i).v id sn133
Substitution of shift_left_gen: the index i by subst i and the snode nd by shift_snode nd off
Valid (42ms) (colibri2)
137 val partial compose_shift (subst: IArray63.t t) (off: int63) (x: t) : t
138 requires { numbits x.dom_indexes <= subst.IArray63.length }
139 ensures { forall nd. Set.mem nd (support_snodes x) -> nd.scal \/ in_bounds (to_int nd.s - to_int off) }
140 raises { Overflow -> exists nd. Set.mem nd (support_snodes x) /\ not nd.scal /\ not (in_bounds (to_int nd.s - to_int off)) }
141 ensures { (forall j. 0 <= j < subst.IArray63.length ->
142 numbits (subst j).dom_indexes <= subst.IArray63.length) ->
143 numbits result.dom_indexes <= subst.IArray63.length }
144 ensures { forall id sn. result.v id sn =
145 x.v (of_bits (subst_bits subst id sn) subst.IArray63.length)
146 (shifted sn (to_int off)) }
147 ensures { forall nd''. Set.mem nd'' (support_snodes result) ->
148 (exists j. 0 <= j < subst.IArray63.length /\ Set.mem nd'' (support_snodes (subst j))) \/
149 (exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }
150
Valid (30ms) (colibri2)
151 val partial cofactors_snode (nd: snode) (a: t) : (t, t)
152 returns { (p, n) ->
153 p.dom_indexes = a.dom_indexes /\
154 n.dom_indexes = a.dom_indexes /\
155 p.dom_snodes = Set.remove nd a.dom_snodes /\
156 n.dom_snodes = Set.remove nd a.dom_snodes /\
157 p.v = (fun id sn -> a.v id (Set.add nd sn)) /\
158 n.v = (fun id sn -> a.v id (Set.remove nd sn)) }
a at the position pos (a cofactor by the cube of the index pos on s bits: get_bit of bddbitv.ml)
Valid (33ms) (colibri2)
162 val partial get_pos (a: t) (pos s: int63) : t
163 requires { 0 <= s /\ numbits a.dom_indexes <= s }
164 requires { 0 <= pos /\ numbits pos <= s }
165 ensures { result.dom_indexes = 0 }
166 ensures { Set.subset result.dom_snodes a.dom_snodes }
167 ensures { forall id sn. result.v id sn <-> a.v pos sn }
Existential (resp. universal) quantification over all the snodes (Cudd.Bdd.exist (resp. forall) with the cube of the snodes of the support, as in to_knownbits)
Valid (39ms) (colibri2)
172 val partial exist_snodes (x: t) : t
173 ensures { result.dom_indexes = x.dom_indexes }
174 ensures { support_snodes result = Set.empty }
175 ensures { forall id sn. result.v id sn <-> exists sn'. x.v id sn' }
Existential quantification over the positions of the window s (Cudd.Bdd.exist with the cube of the indexes 0..s-1)
Valid (38ms) (colibri2)
179 val partial exist_window (x: t) (s: int63) : t
180 requires { 0 <= s /\ numbits x.dom_indexes <= s }
181 ensures { result.dom_indexes = 0 }
182 ensures { Set.subset result.dom_snodes x.dom_snodes }
183 ensures { forall id sn. result.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
184
Valid (38ms) (colibri2)
185 val partial forall_snodes (x: t) : t
186 ensures { result.dom_indexes = x.dom_indexes }
187 ensures { support_snodes result = Set.empty }
188 ensures { forall id sn. result.v id sn <-> forall sn'. x.v id sn' }
Substitution of snodes by BDDs
predicate mem_key (nd: snode) (l: list (snode, t)) =191match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end192193predicate distinct_keys (l: list (snode, t)) =194match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end195196function subst_sn (l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =197match l with198| Nil -> sn199| Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)200end201
The simultaneous substitution of the snodes of l (one Var.subst); w bounds the indexes
Valid (34ms) (colibri2)
205 val partial compose_snodes (ghost w: int) (l: list (snode, t)) (x: t) : t
206 requires { distinct_keys l }
207 requires { 0 <= w <= Int63.max_int + 1 /\ numbits x.dom_indexes <= w }
208 requires { forall nd f. Mem.mem (nd, f) l -> numbits f.dom_indexes <= w }
209 ensures { numbits result.dom_indexes <= w }
210 ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }
Top node of the BDD
Valid (33ms) (colibri2)
213 val inspect (a:t) : inspect
214 ensures { match result with
215 | Bool b -> a.v = (fun _ _ -> b) /\ support_snodes a = Set.empty
216 | IteIndex i th el ->
217 Set.subset (support_snodes th) (support_snodes a) /\
218 Set.subset (support_snodes el) (support_snodes a) /\
219 0 <= to_int i /\ Zbit.bittest a.dom_indexes i /\
220 Zbit.subset th.dom_indexes (Zbit.unset a.dom_indexes i) /\
221 Zbit.subset el.dom_indexes (Zbit.unset a.dom_indexes i) /\
222 Set.subset th.dom_snodes a.dom_snodes /\
223 Set.subset el.dom_snodes a.dom_snodes /\
224 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
225 a.v = (fun id sn -> if Zbit.bittest id i then th.v id sn else el.v id sn)
226 | IteSnode nd th el ->
227 Set.mem nd (support_snodes a) /\
228 Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
229 Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
230 Set.mem nd a.dom_snodes /\
231 Zbit.subset th.dom_indexes a.dom_indexes /\
232 Zbit.subset el.dom_indexes a.dom_indexes /\
233 Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
234 Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
235 0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
236 a.v = (fun id sn -> if sn nd then th.v id sn else el.v id sn)
237 end }
238
Valid (87ms) (cvc4)
239 val partial compose_index (i: int63) (f a: t) : t
240 requires { 0 <= to_int i }
241 ensures { result.dom_indexes = (Zbit.lor f.dom_indexes (Zbit.unset a.dom_indexes i)) }
242 ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
243 ensures { result.v = (fun id sn -> a.v (Zbit.change id i (f.v id sn)) sn) }
244
245
246end