library colibrilib.ibdd — module IBDDmodule IBDD1
Implemented: the bitwise layer, specified with the integer view
use bool.Bool2use colibrilib.bdd.Node3use colibrilib.bdd.NodeSet4use colibrilib.bdd.NodeH5use colibrilib.bdd.Key6use list.List7use list.Mem8use option.Option9use ref.Ref10use colibrilib.sbdd.SNode11use colibrilib.bdd.IArray6312use int.Int13use colibrilib.int63.Int6314use set.Set15use colibrilib.pbdd.PBDD16use colibrilib.pbdd.PBDD217use colibrilib.zarith.Zbit18use colibrilib.zbit.ZbitInt19use seq.Seq20use mach.array.Array6321use int.MinMax22use int.Power23use list.Append as Lists24Valid (68ms) (colibri2)25let rec lemma lsl_power (n:int) : unit26requires { 0 <= n }27variant { n }28ensures { lsl 1 n = power 2 n }29= if n > 0 then begin lsl_power (n-1); lsl_succ 1 (n-1) end30Valid (7.4s) (colibri2 6) (cvc4 2) (cvc5) (split_vc 3) (depth 2)31let lemma power_2_61 (_:unit) : unit32ensures { power 2 61 = 2305843009213693952 }33=34assert { power 2 2 = 4 };35assert { power 2 4 = 16 by power 2 4 = power 2 2 * power 2 2 };36assert { power 2 8 = 256 by power 2 8 = power 2 4 * power 2 4 };37assert { power 2 16 = 65536 by power 2 16 = power 2 8 * power 2 8 };38assert { power 2 32 = 4294967296 by power 2 32 = power 2 16 * power 2 16 };39assert { power 2 61 = 2305843009213693952 by40power 2 61 = power 2 32 * power 2 16 * power 2 8 * power 2 4 * power 2 1 };41()42Valid (86ms) (colibri2)43let lemma lsl_le_2_60 (n:int) : unit44requires { 0 <= n <= 60 }45ensures { lsl 1 n <= 0x1000_0000_0000_0000 }46=47power_2_61 ();48assert { power 2 61 = 2 * power 2 60 };49Power_monotonic 2 n 6050
The window sizes whose number of positions is an int63
Valid (75ms) (colibri2)let lemma lsl_le_max_int (n:int) : unit53requires { 0 <= n }54ensures { lsl 1 n <= Int63.max_int <-> n <= 61 }55=56power_2_61 ();57if n <= 61 then Power_monotonic 2 n 6158else Power_monotonic 2 62 n59
The snode nd is read at the position p: a scalar (the sign of its node), or a relative snode reading a non–negative bit
predicate reads_at (p: int) (nd: snode) = nd.SNode.scal \/ 0 <= p + to_int nd.SNode.s63
sn1 and sn2 agree on the snodes that read a non–negative bit at p
predicate agree (p: int) (sn1 sn2: snodes) =66forall nd. reads_at p nd -> (Set.mem nd sn1 <-> Set.mem nd sn2)67
At the positions p of the window s, the BDD does not depend on the snodes that read a negative bit there (p + nd.s < 0)
predicate no_neg (b: PBDD.t) (s: int) =71forall p sn1 sn2. 0 <= p -> numbits p <= s -> agree p sn1 sn2 ->72(b.PBDD.v p sn1 <-> b.PBDD.v p sn2)73
no_neg on the positions 0..m
predicate no_neg_le (b: PBDD.t) (m: int) =76forall p sn1 sn2. 0 <= p <= m -> agree p sn1 sn2 -> (b.PBDD.v p sn1 <-> b.PBDD.v p sn2)77
The window s is minimal: its upper half is not empty
predicate minimal (b: PBDD.t) (s: int) =80s = 0 \/ exists p sn. 0 <= p /\ numbits p = s /\ b.PBDD.v p sn81
The tail is a function of the snodes read at the position p (the same for all the positions p >= 2^s): it does not depend on the snodes that read a negative bit at 2^s
predicate no_neg_tail (t: PBDD.t) (s: int) =86forall sn1 sn2. agree (lsl 1 s) sn1 sn2 -> (t.PBDD.v 0 sn1 <-> t.PBDD.v 0 sn2)87
The window s is minimal for the tail t: its upper half is not the tail
predicate minimal_t (b t: PBDD.t) (s: int) =90s = 0 \/ exists p sn. 0 <= p /\ numbits p = s /\ not (b.PBDD.v p sn <-> t.PBDD.v 0 sn)91
ibdd is a unique name for the extracted code. The bit p of a term is bdd.v p on its window (p < 2^size) and tail.v 0 above (the tail has no index). With no_neg, no_neg_tail and minimal_t, the equality of the bits is the equality of the BDDs (lemma canonical)
Valid (89ms) (colibri2)type ibdd = {98bdd : PBDD.t;99size : int63;100tail : PBDD.t;101} invariant { Zbit.numbits bdd.dom_indexes <= size }102invariant { tail.dom_indexes = 0 }103invariant { no_neg bdd size }104invariant { no_neg_tail tail size }105invariant { minimal_t bdd tail size }106by { bdd = PBDD.tfalse (); size = 0; tail = PBDD.tfalse () }107108type t = ibdd109110function isize (t: ibdd) : int63 = t.size111function ibdd_bdd (t: ibdd) : PBDD.t = t.bdd112
The bit p >= 0 of a term, for the snodes sn read at p
function bit (t: t) (p: int) (sn: snodes) : bool =115if numbits p <= t.size then t.bdd.PBDD.v p sn else t.tail.PBDD.v 0 sn116
The term has a tail that is not false
predicate tailed (t: ibdd) = exists sn. t.tail.PBDD.v 0 sn119
The snodes in the domain of a term
function all_snodes (t: ibdd) : snodes = Set.union t.bdd.PBDD.dom_snodes t.tail.PBDD.dom_snodes122
A term with a false tail (minimal is minimal_t for it)
Valid (68ms) (colibri2)let ghost minimal_false (b t: PBDD.t) (s: int) : unit125requires { minimal b s }126requires { forall sn. not (t.PBDD.v 0 sn) }127ensures { minimal_t b t s }128= ()129Valid (58ms) (colibri2)130let ghost no_neg_tail_false (t: PBDD.t) (s: int) : unit131requires { forall sn. not (t.PBDD.v 0 sn) }132ensures { no_neg_tail t s }133= ()134
The value of an IBDD: positions represented with more than size bits are false
function v (b:t) (sn:PBDD2.env) : int = PBDD2.v b.bdd b.size sn138
Valuation of the snodes from a valuation of the nodes: Var {n; shift} at position p is the bit p + shift of n
function sem (env: Node.t -> int) : PBDD2.env =142fun p nd -> if nd.SNode.scal then env nd.SNode.n < 0 else bittest (env nd.SNode.n) (p + nd.SNode.s)143Valid (72ms) (colibri2)144let ghost sem_def (env: Node.t -> int) (p: int) (nd: snode) : unit145ensures { sem env p nd <-> if nd.SNode.scal then env nd.SNode.n < 0 else bittest (env nd.SNode.n) (p + nd.SNode.s) }146= ()147
The value of an IBDD for a valuation of the nodes
function value (b:t) (env: Node.t -> int) : int = v b (sem env)150Valid (80ms) (colibri2)151let lemma numbits_subset (a b:int) : unit152requires { 0 <= a /\ 0 <= b /\ Zbit.subset a b }153ensures { numbits a <= numbits b }154=155if a > 0 && numbits a > numbits b then begin156numbits_top_bit a;157if b > 0 then numbits_high_clear b (numbits a - 1)158end159
A BDD whose index domain fits in the window s only depends on the snodes it depends on at the positions of the window
Valid (386ms) (colibri2 6) (cvc4 3) (split_vc) (depth 1)
163 let ghost supp_win (b: PBDD.t) (s: int) (sx: snodes) : unit
164 requires { 0 <= s /\ numbits b.dom_indexes <= s }
165 requires { forall nd p sn. not (Set.mem nd sx) -> 0 <= p -> numbits p <= s ->
166 (b.PBDD.v p (Set.add nd sn) <-> b.PBDD.v p (Set.remove nd sn)) }
167 ensures { Set.subset (support_snodes b) sx }
168 =
169 let lemma pt (nd: snode) : unit
170 requires { Set.mem nd (support_snodes b) }
171 ensures { Set.mem nd sx }
172 =
173 if pure { not (Set.mem nd sx) } then begin
174 let ghost (id, sn) = PBDD.support_snodes_dep b nd in
175 let ghost p = pure { land (mask s) id } in
176 mask_nonneg s;
177 land_nonneg_l pure { mask s } id;
178 numbits_subset p pure { mask s };
179 mask_numbits s;
180 PBDD.support_v b id p (Set.add nd sn);
181 PBDD.support_v b id p (Set.remove nd sn)
182 end
183 in ()
184
Valid (47ms) (colibri2)
185 let function z_maxpos (z:int) : int
186 requires { 0 <= z }
187 = max 0 (Zbit.numbits z - 1)
Splitting an integer in a low part of off bits and a high part
Valid (626ms) (cvc5)
190 let lemma split_concat (x off:int) : unit
191 requires { 0 <= x /\ 0 <= off }
192 ensures { lor (land x (mask off)) (lsl (asr x off) off) = x }
193 =
194 let ghost y = lor (land x (Zbit.mask off)) (Zbit.lsl (Zbit.asr x off) off) in
195 ext_bittest y x
196
197
Valid (66ms) (colibri2)
198 let lemma lt_lsl_of_numbits (x n:int) : unit
199 requires { 0 <= x /\ 0 <= n /\ numbits x <= n }
200 ensures { x < lsl 1 n }
201 =
202 mask_nonneg n;
203 if x >= Zbit.lsl 1 n then begin
204 numbits_lsl n;
205 numbits_ge_pos (Zbit.lsl 1 n) x
206 end
result j is the BDD of the constant j of size s
predicate wf_cst (result:IArray63.t PBDD.t) (s:int) =209result.IArray63.length = lsl 1 (lsl 1 s) /\210(forall j. 0 <= j < result.IArray63.length -> Zbit.numbits (result j).dom_indexes <= s) /\211(forall j. 0 <= j < result.IArray63.length -> (result j).dom_snodes = Set.empty) /\212(forall j sn. 0 <= j < result.IArray63.length -> PBDD2.v (result j) s sn = j)213Valid (1.7s) (colibri2 85) (cvc4 11) (cvc5 2) (split_vc 7) (depth 2)214let partial mk_cst256 () : IArray63.t (IArray63.t PBDD.t)215ensures { result.IArray63.length = 4 }216ensures { forall s. 0 <= s < 4 -> wf_cst (result s) s }217=218let partial aux (s:int63) (arr_prev:IArray63.t PBDD.t) : IArray63.t PBDD.t219requires { 1 <= s <= 3 }220requires { wf_cst arr_prev (s-1) }221ensures { wf_cst result s }222=223lsl_power (to_int s);224Power_monotonic 2 (to_int s) 3;225lsl_power pure { lsl 1 s };226Power_monotonic 2 pure { lsl 1 s } 8;227let half = Int63.lsl 1 (s-1) in228lsl_succ 1 (to_int s - 1);229assert { lsl 1 s = 2 * half };230mask_nonneg (to_int s - 1);231mask_nonneg (to_int s);232mask_nonneg pure { Zbit.lsl 1 s };233let len = Int63.lsl 1 (Int63.lsl 1 s) in234let arr = Array63.make len (PBDD.tfalse ()) in235for i = 0 to Int63.mask (Int63.lsl 1 s) do236invariant { forall j. 0 <= j < i -> Zbit.numbits (arr[j]).dom_indexes <= s }237invariant { forall j. 0 <= j < i -> (arr[j]).dom_snodes = Set.empty }238invariant { forall j sn. 0 <= j < i -> PBDD2.v (arr[j]) s sn = j }239let high = Int63.asr i half in240let low = Int63.land i (Int63.mask half) in241numbits_lt_lsl pure { i : int } pure { lsl 1 s : int };242if i > 0 then asr_numbits pure { i : int } pure { half : int };243asr_nonneg pure { i : int } pure { half : int };244lt_lsl_of_numbits pure { high : int } pure { half : int };245land_nonneg pure { i : int } pure { mask half : int };246land_le pure { i : int } pure { mask half : int };247split_concat pure { i : int } pure { half : int };248let bhi = IArray63.get arr_prev high in249let blo = IArray63.get arr_prev low in250let r = PBDD2.ite_index (s-1) bhi blo in251Zbit.numbits_set (Zbit.lor (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes)) (to_int s - 1);252Zbit.lor_numbits (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes);253assert { forall sn. PBDD2.v bhi (s-1) sn = high };254assert { forall sn. PBDD2.v blo (s-1) sn = low };255let lemma vr (sn: PBDD2.env) : unit256ensures { PBDD2.v r s sn = lor low (lsl high half) }257= assert { PBDD2.v r s sn = lor (PBDD2.v blo (s-1) sn)258(lsl (PBDD2.v bhi (s-1) (PBDD2.shift_env sn half)) half) };259assert { PBDD2.v bhi (s-1) (PBDD2.shift_env sn half) = high } in260assert { forall sn. PBDD2.v r s sn = i };261assert { Zbit.numbits r.PBDD.dom_indexes <= s };262assert { bhi.PBDD.dom_snodes = Set.empty };263assert { blo.PBDD.dom_snodes = Set.empty };264assert { r.PBDD.dom_snodes = Set.empty };265label L in266arr[i] <- r;267assert { arr[i] = r };268assert { forall j. 0 <= j < i -> arr[j] = (arr at L)[j] };269assert { forall j. 0 <= j < i + 1 -> Zbit.numbits (arr[j]).dom_indexes <= s270by j = i \/ j < i };271assert { forall j. 0 <= j < i + 1 -> (arr[j]).dom_snodes = Set.empty272by j = i \/ j < i }273done;274assert { Zbit.mask (Zbit.lsl 1 s) + 1 = len };275let res = IArray63.of_array arr in276assert { res.IArray63.length = len };277assert { forall j. 0 <= j < len -> res j = arr[j] };278assert { res.IArray63.length = lsl 1 (lsl 1 s) };279assert { forall j. 0 <= j < res.IArray63.length ->280Zbit.numbits (res j).dom_indexes <= s };281assert { forall j. 0 <= j < res.IArray63.length ->282(res j).dom_snodes = Set.empty };283assert { forall j sn. 0 <= j < res.IArray63.length ->284PBDD2.v (res j) s sn = j };285res286in287let arr0 = Array63.make (2:int63) (PBDD2.tfalse ()) in288arr0[0] <- PBDD2.tfalse ();289arr0[1] <- PBDD2.ttrue ();290assert { lsl 1 0 = 1 };291assert { lsl 1 1 = 2 };292assert { mask 1 = 1 };293let res = Array63.make 4 (IArray63.of_array arr0) in294for i = 1 to 3 do295invariant { forall s. 0 <= s < i -> wf_cst (res[s]) s }296res[i] <- aux i res[i-1];297done;298IArray63.of_array res299
mk_cst256 in ghost code: the witness of the invariant of cst_table
Valid (1.9s) (colibri2 82) (cvc4 11) (cvc5 3) (split_vc 5) (depth 2)
304 let ghost mk_cst256_g () : IArray63.t (IArray63.t PBDD.t)
305 ensures { result.IArray63.length = 4 }
306 ensures { forall s. 0 <= s < 4 -> wf_cst (result s) s }
307 =
308 let aux (s:int63) (arr_prev:IArray63.t PBDD.t) : IArray63.t PBDD.t
309 requires { 1 <= s <= 3 }
310 requires { wf_cst arr_prev (s-1) }
311 ensures { wf_cst result s }
312 =
313 lsl_power (to_int s);
314 Power_monotonic 2 (to_int s) 3;
315 lsl_power pure { lsl 1 s };
316 Power_monotonic 2 pure { lsl 1 s } 8;
317 let half = Int63.lsl 1 (s-1) in
318 lsl_succ 1 (to_int s - 1);
319 assert { lsl 1 s = 2 * half };
320 mask_nonneg (to_int s - 1);
321 mask_nonneg (to_int s);
322 mask_nonneg pure { Zbit.lsl 1 s };
323 let len = Int63.lsl 1 (Int63.lsl 1 s) in
324 let arr = Array63.make len (PBDD.tfalse ()) in
325 for i = 0 to Int63.mask (Int63.lsl 1 s) do
326 invariant { forall j. 0 <= j < i -> Zbit.numbits (arr[j]).dom_indexes <= s }
327 invariant { forall j. 0 <= j < i -> (arr[j]).dom_snodes = Set.empty }
328 invariant { forall j sn. 0 <= j < i -> PBDD2.v (arr[j]) s sn = j }
329 let high = Int63.asr i half in
330 let low = Int63.land i (Int63.mask half) in
331 numbits_lt_lsl pure { i : int } pure { lsl 1 s : int };
332 if i > 0 then asr_numbits pure { i : int } pure { half : int };
333 asr_nonneg pure { i : int } pure { half : int };
334 lt_lsl_of_numbits pure { high : int } pure { half : int };
335 land_nonneg pure { i : int } pure { mask half : int };
336 land_le pure { i : int } pure { mask half : int };
337 split_concat pure { i : int } pure { half : int };
338 let bhi = IArray63.get arr_prev high in
339 let blo = IArray63.get arr_prev low in
340 let r = PBDD2.ite_index_g (s-1) bhi blo in
341 Zbit.numbits_set (Zbit.lor (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes)) (to_int s - 1);
342 Zbit.lor_numbits (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes);
343 assert { forall sn. PBDD2.v bhi (s-1) sn = high };
344 assert { forall sn. PBDD2.v blo (s-1) sn = low };
345 let lemma vr (sn: PBDD2.env) : unit
346 ensures { PBDD2.v r s sn = lor low (lsl high half) }
347 = assert { PBDD2.v r s sn = lor (PBDD2.v blo (s-1) sn)
348 (lsl (PBDD2.v bhi (s-1) (PBDD2.shift_env sn half)) half) };
349 assert { PBDD2.v bhi (s-1) (PBDD2.shift_env sn half) = high } in
350 assert { forall sn. PBDD2.v r s sn = i };
351 assert { Zbit.numbits r.PBDD.dom_indexes <= s };
352 assert { bhi.PBDD.dom_snodes = Set.empty };
353 assert { blo.PBDD.dom_snodes = Set.empty };
354 assert { r.PBDD.dom_snodes = Set.empty };
355 label L in
356 arr[i] <- r;
357 assert { arr[i] = r };
358 assert { forall j. 0 <= j < i -> arr[j] = (arr at L)[j] };
359 assert { forall j. 0 <= j < i + 1 -> Zbit.numbits (arr[j]).dom_indexes <= s
360 by j = i \/ j < i };
361 assert { forall j. 0 <= j < i + 1 -> (arr[j]).dom_snodes = Set.empty
362 by j = i \/ j < i }
363 done;
364 assert { Zbit.mask (Zbit.lsl 1 s) + 1 = len };
365 let res = IArray63.of_array arr in
366 assert { res.IArray63.length = len };
367 assert { forall j. 0 <= j < len -> res j = arr[j] };
368 assert { res.IArray63.length = lsl 1 (lsl 1 s) };
369 assert { forall j. 0 <= j < res.IArray63.length ->
370 Zbit.numbits (res j).dom_indexes <= s };
371 assert { forall j. 0 <= j < res.IArray63.length ->
372 (res j).dom_snodes = Set.empty };
373 assert { forall j sn. 0 <= j < res.IArray63.length ->
374 PBDD2.v (res j) s sn = j };
375 res
376 in
377 let arr0 = Array63.make (2:int63) (PBDD2.tfalse ()) in
378 arr0[0] <- PBDD2.tfalse ();
379 arr0[1] <- PBDD2.ttrue ();
380 assert { lsl 1 0 = 1 };
381 assert { lsl 1 1 = 2 };
382 assert { mask 1 = 1 };
383 let res = Array63.make 4 (IArray63.of_array arr0) in
384 for i = 1 to 3 do
385 invariant { forall s. 0 <= s < i -> wf_cst (res[s]) s }
386 res[i] <- aux i res[i-1];
387 done;
388 IArray63.of_array res
The table of the constants of the windows of fewer than 4 bits. A value of a type with an invariant, since a constant cannot be computed by partial code: its invariant is known where it is used (witness: mk_cst256_g, with the axiom bdd.Var.small_indexes).
Valid (23ms) (colibri2)
395 type cst_table = {
396 tbl: IArray63.t (IArray63.t PBDD.t);
397 } invariant { tbl.IArray63.length = 4 /\
398 forall s. 0 <= s < 4 -> wf_cst (tbl s) s }
399 by { tbl = mk_cst256_g () }
400
Valid (32ms) (colibri2)
401 let cst256 : cst_table = { tbl = mk_cst256 () }
The BDD of the constant x on the window n (split in cst)
Valid (1.1s) (colibri2 29) (cvc4 11) (cvc5 5) (split_vc 2) (depth 2)
404 let rec partial cst_bdd (n:int63) (x:int) : PBDD.t
405 requires { 0 <= n /\ 0 <= x /\ Zbit.numbits (z_maxpos x) <= n }
406 variant { n }
407 ensures { Zbit.numbits result.PBDD.dom_indexes <= n }
408 ensures { result.PBDD.dom_snodes = Set.empty }
409 ensures { forall sn. PBDD2.v result n sn = x }
410 = if n < 4 then begin
411 let t = IArray63.get cst256.tbl n in
412 assert { wf_cst t n };
413 lt_lsl_of_numbits (z_maxpos x) (to_int n);
414 mask_nonneg (to_int n);
415 assert { numbits x <= Zbit.lsl 1 n };
416 if x > 0 then lt_lsl_of_numbits x pure { Zbit.lsl 1 (to_int n) };
417 assert { x < t.IArray63.length <= Int63.max_int };
418 IArray63.get t (Int63.of_int x)
419 end else
420 let k = n - 1 in
421 let off = ZbitInt.lsl_int 1 (to_int k) in
422 let hi = ZbitInt.asr_int x off in
423 if x > 0 then numbits_lsl_lt (Zbit.numbits x - 1);
424 lsl_succ 1 (to_int n-1);
425 Zbit.numbits_ge_pos (z_maxpos hi) (Zbit.mask (to_int k));
426 let lo = Zbit.land x (ZbitInt.mask_int off) in
427 Zbit.numbits_ge_pos (z_maxpos lo) (Zbit.mask (to_int k));
428 let bhi = (cst_bdd k hi) in
429 let blo = (cst_bdd k lo) in
430 let r = PBDD2.ite_index k bhi blo in
431 Zbit.numbits_set (Zbit.lor (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes)) (to_int k);
432 Zbit.lor_numbits (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes);
433 split_concat x off;
434 r
435
Valid (66ms) (colibri2)
436 let rec lemma succ_le_lsl (k:int) : unit
437 requires { 0 <= k }
438 ensures { k + 1 <= lsl 1 k }
439 variant { k }
440 = if k = 0 then assert { lsl 1 0 = 1 }
441 else begin
442 succ_le_lsl (k-1);
443 lsl_succ 1 (k-1)
444 end
445
Valid (65ms) (colibri2)
446 let lemma numbits_le_self (y:int) : unit
447 requires { 0 <= y }
448 ensures { numbits y <= y }
449 = if y > 0 then begin
450 numbits_lsl_le y;
451 numbits_ge_pos 1 y;
452 succ_le_lsl (numbits y - 1)
453 end
454
455 (* [size] is the field projection *)
The constant x
The constant environment
function cenv (sn: snodes) : PBDD2.env = fun _ -> sn459Valid (101ms) (colibri2)460let lemma bit_cenv (x: PBDD.t) (s p: int) (sn: snodes) : unit461requires { 0 <= p /\ numbits p <= s }462ensures { bittest (PBDD2.v x s (cenv sn)) p <-> x.PBDD.v p sn }463= ()464
A BDD without snode in its domain does not depend on the snodes
Valid (88ms) (colibri2)
467 let lemma no_snode_no_neg (b: PBDD.t) (s: int) : unit
468 requires { b.dom_snodes = Set.empty }
469 ensures { no_neg b s }
470 =
471 let lemma pt (p: int) (sn1 sn2: snodes) : unit
472 ensures { b.PBDD.v p sn1 <-> b.PBDD.v p sn2 }
473 = PBDD.support_snodes_dom b;
474 PBDD.support_snodes_v b p sn1 sn2
475 in ()
476
Valid (1.0s) (cvc4)
477 let partial cst (x:int) : t
478 requires { 0 <= x }
479 requires { numbits x <= Int63.max_int }
480 ensures { result.bdd.dom_snodes = Set.empty }
481 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
482 ensures { result.tail.dom_snodes = Set.empty }
483 ensures { forall sn. v result sn = x }
484 ensures { to_int result.size <= numbits (numbits x) }
485 =
486 numbits_ge_pos 0 x;
487 numbits_ge_pos (z_maxpos x) (numbits x);
488 numbits_le_self (z_maxpos x);
489 let size = Int63.of_int (Zbit.numbits (z_maxpos x)) in
490 let b = cst_bdd size x in
491 no_snode_no_neg b (to_int size);
492 if x > 0 then begin
493 let ghost p = z_maxpos x in
494 numbits_top_bit x;
495 bit_cenv b (to_int size) p Set.empty;
496 assert { minimal b size }
497 end;
498 let tl = PBDD.tfalse () in
499 minimal_false b tl (to_int size);
500 no_neg_tail_false tl (to_int size);
501 { bdd = b; size = size; tail = tl }
502
Valid (646ms) (colibri2 43) (cvc4 8) (split_vc) (depth 1)
503 let partial mk (bdd: PBDD.t) (size: int63) : t
504 requires { 0 <= size }
505 requires { numbits bdd.dom_indexes <= size }
506 requires { no_neg bdd size }
507 ensures { result.bdd.dom_snodes = bdd.dom_snodes }
508 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
509 ensures { forall sn. v result sn = PBDD2.v bdd size sn }
510 ensures { result.size <= size }
511 =
512 let tl = PBDD.tfalse () in
513 let rec partial aux (bdd: PBDD.t) (size: int63) : t
514 requires { 0 <= size }
515 requires { numbits bdd.dom_indexes <= size }
516 requires { no_neg bdd size }
517 variant { size }
518 ensures { result.bdd.dom_snodes = bdd.dom_snodes }
519 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
520 ensures { forall sn. v result sn = PBDD2.v bdd size sn }
521 ensures { result.size <= size }
522 = no_neg_tail_false tl (to_int size);
523 if size = 0 then { bdd = bdd; size = size; tail = tl }
524 else
525 let k = size - 1 in
526 if PBDD2.upper_empty bdd k then begin
527 let r = PBDD2.cofactor_low bdd k in
528 let lemma same (p: int) (sn: snodes) : unit
529 requires { 0 <= p /\ numbits p <= to_int k }
530 ensures { r.PBDD.v p sn <-> bdd.PBDD.v p sn }
531 = bit_cenv r (to_int k) p sn; bit_cenv bdd (to_int k) p sn
532 in
533 aux r k
534 end else begin
535 let lemma upper (_: unit) : unit
536 ensures { minimal bdd size }
537 =
538 if pure { not (minimal bdd size) } then begin
539 let lemma eq (sn: PBDD2.env) : unit
540 ensures { PBDD2.v bdd (k + 1) sn = PBDD2.v bdd k sn }
541 =
542 let lemma bit (p: int) : unit
543 ensures { bittest (PBDD2.v bdd (k + 1) sn) p <-> bittest (PBDD2.v bdd k sn) p }
544 = if 0 <= p && numbits p = to_int k + 1 then
545 assert { not (bdd.PBDD.v p (sn p)) }
546 in
547 ext_bittest pure { PBDD2.v bdd (k + 1) sn } pure { PBDD2.v bdd k sn }
548 in
549 assert { false }
550 end
551 in
552 minimal_false bdd tl (to_int size);
553 { bdd = bdd; size = size; tail = tl }
554 end
555 in
556 aux bdd size
557
Valid (355ms) (cvc4)
558 let zero () : t
559 ensures { result.bdd.dom_snodes = Set.empty }
560 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
561 ensures { result.size = 0 }
562 ensures { forall sn. v result sn = 0 }
563 =
564 let b = PBDD2.tfalse () in
565 no_snode_no_neg b 0;
566 let tl = PBDD.tfalse () in
567 minimal_false b tl 0;
568 no_neg_tail_false tl 0;
569 { bdd = b; size = 0; tail = tl }
Same value on a bigger window: the new positions are false
Valid (1.9s) (colibri2 21) (cvc4 14) (split_vc 3) (depth 2)
572 let partial grow (bdd: PBDD.t) (from_ to_: int63) : PBDD.t
573 requires { 0 <= from_ <= to_ }
574 requires { numbits bdd.dom_indexes <= from_ }
575 ensures { numbits result.dom_indexes <= to_ }
576 ensures { result.dom_snodes = bdd.dom_snodes }
577 ensures { forall sn. PBDD2.v result to_ sn = PBDD2.v bdd from_ sn }
578 =
579 let rec partial aux (acc: PBDD.t) (n: int63) : PBDD.t
580 requires { from_ <= n <= to_ }
581 requires { numbits acc.dom_indexes <= n }
582 requires { acc.dom_snodes = Set.empty }
583 requires { acc.PBDD.v = (fun (id:indexes) (_:snodes) -> exists m: int63. from_ <= m < n /\ bittest id m) }
584 variant { to_ - n }
585 ensures { numbits result.dom_indexes <= to_ }
586 ensures { result.dom_snodes = Set.empty }
587 ensures { result.PBDD.v = (fun (id:indexes) (_:snodes) -> exists m: int63. from_ <= m < to_ /\ bittest id m) }
588 = if n = to_ then acc
589 else begin
590 let acc' = PBDD.dor acc (PBDD.bdd_of_index n) in
591 lor_numbits acc.dom_indexes pure { lsl 1 (to_int n) };
592 let lemma step (id:indexes) (sn:snodes) : unit
593 ensures { acc'.PBDD.v id sn <-> exists m: int63. from_ <= m < n+1 /\ bittest id m }
594 = ()
595 in
596 aux acc' (n+1)
597 end
598 in
599 let cond = aux (PBDD.tfalse ()) from_ in
600 let r = PBDD.dand (PBDD.dnot cond) bdd in
601 lor_numbits cond.dom_indexes bdd.dom_indexes;
602 let lemma same (id:int) (sn:snodes) : unit
603 requires { 0 <= id }
604 ensures { (numbits id <= to_ /\ r.PBDD.v id sn) <-> (numbits id <= from_ /\ bdd.PBDD.v id sn) }
605 =
606 if numbits id > to_int from_ && numbits id <= to_int to_ then
607 let ghost m = Int63.of_int (numbits id - 1) in
608 assert { bittest id m };
609 assert { cond.PBDD.v id sn }
610 in
611 let lemma eq (sn:PBDD2.env) : unit
612 ensures { PBDD2.v r to_ sn = PBDD2.v bdd from_ sn }
613 = ext_bittest pure { PBDD2.v r to_ sn } pure { PBDD2.v bdd from_ sn }
614 in
615 r
Restriction to a smaller window. Differs from bddbitv.ml, less efficient: iterated cofactor_low (one BDD traversal per removed bit) instead of a single cofactor.
Valid (477ms) (cvc4)
620 let rec partial shrink (bdd: PBDD.t) (from_ to_: int63) : PBDD.t
621 requires { 0 <= to_ <= from_ }
622 requires { numbits bdd.dom_indexes <= from_ }
623 variant { from_ }
624 ensures { numbits result.dom_indexes <= to_ }
625 ensures { result.dom_snodes = bdd.dom_snodes }
626 ensures { forall sn. PBDD2.v result to_ sn = PBDD2.v bdd to_ sn }
627 =
628 if from_ = to_ then bdd
629 else begin
630 let k = from_ - 1 in
631 let r = PBDD2.cofactor_low bdd k in
632 let lemma eq (sn:PBDD2.env) : unit
633 ensures { PBDD2.v r to_ sn = PBDD2.v bdd to_ sn }
634 =
635 PBDD2.v_window r (to_int to_) (to_int k) sn;
636 PBDD2.v_window bdd (to_int to_) (to_int k) sn
637 in
638 shrink r k to_
639 end
The window from_ seen on the window to_
Valid (459ms) (colibri2 53) (cvc4 2) (split_vc) (depth 1)
642 let partial resize (bdd: PBDD.t) (from_ to_: int63) : PBDD.t
643 requires { 0 <= from_ /\ 0 <= to_ }
644 requires { numbits bdd.dom_indexes <= from_ }
645 ensures { numbits result.dom_indexes <= to_ }
646 ensures { result.dom_snodes = bdd.dom_snodes }
647 ensures { forall sn. PBDD2.v result to_ sn = land (PBDD2.v bdd from_ sn) (mask (lsl 1 to_)) }
648 ensures { forall p sn. 0 <= p -> numbits p <= to_ ->
649 (result.PBDD.v p sn <-> (numbits p <= from_ /\ bdd.PBDD.v p sn)) }
650 ensures { Set.subset (support_snodes result) (support_snodes bdd) }
651 =
652 let r = if to_ = from_ then bdd
653 else if to_ > from_ then grow bdd from_ to_
654 else shrink bdd from_ to_ in
655 let lemma pt (p: int) (sn: snodes) : unit
656 requires { 0 <= p /\ numbits p <= to_ }
657 ensures { r.PBDD.v p sn <-> (numbits p <= from_ /\ bdd.PBDD.v p sn) }
658 =
659 bit_cenv r (to_int to_) p sn;
660 lt_lsl_of_numbits p (to_int to_);
661 assert { bittest (mask (lsl 1 to_)) p };
662 if numbits p <= to_int from_ then bit_cenv bdd (to_int from_) p sn
663 in
664 let lemma ind (nd: snode) (p: int) (sn: snodes) : unit
665 requires { not (Set.mem nd (support_snodes bdd)) /\ 0 <= p /\ numbits p <= to_ }
666 ensures { r.PBDD.v p (Set.add nd sn) <-> r.PBDD.v p (Set.remove nd sn) }
667 = pt p (Set.add nd sn); pt p (Set.remove nd sn);
668 PBDD.support_snodes_v bdd p (Set.add nd sn) (Set.remove nd sn)
669 in
670 supp_win r (to_int to_) (support_snodes bdd);
671 r
The BDD of x on the window s
Valid (1.2s) (cvc4)
674 let partial get (x: t) (s: int63) : PBDD.t
675 requires { 0 <= s }
676 ensures { numbits result.dom_indexes <= s }
677 ensures { result.dom_snodes = x.bdd.dom_snodes }
678 ensures { forall sn. PBDD2.v result s sn = land (v x sn) (mask (lsl 1 s)) }
679 ensures { x.size <= s -> forall sn. PBDD2.v result s sn = v x sn }
680 ensures { forall p sn. 0 <= p -> numbits p <= s ->
681 (result.PBDD.v p sn <-> (numbits p <= x.size /\ x.bdd.PBDD.v p sn)) }
682 ensures { no_neg result s }
683 =
684 numbits_ge_pos 0 x.bdd.dom_indexes;
685 let r = resize x.bdd x.size s in
686 let lemma pt (p: int) (sn: snodes) : unit
687 requires { 0 <= p /\ numbits p <= s }
688 ensures { r.PBDD.v p sn <-> (numbits p <= x.size /\ x.bdd.PBDD.v p sn) }
689 =
690 bit_cenv r (to_int s) p sn;
691 lt_lsl_of_numbits p (to_int s);
692 assert { bittest (mask (lsl 1 s)) p };
693 if numbits p <= to_int x.size then bit_cenv x.bdd (to_int x.size) p sn
694 in
695 r
The positions of the window s whose bit i is set (masks in get_cst')
Valid (1.1s) (cvc4)
699 let index_mask (s i: int63) : int
700 requires { 0 <= s /\ 0 <= i }
701 requires { lsl 1 s <= Int63.max_int }
702 ensures { 0 <= result }
703 ensures { forall p. bittest result p <-> (0 <= p /\ numbits p <= s /\ bittest p i) }
704 =
705 let r = ref 0 in
706 lsl_le_max_int (to_int s);
707 let n = Int63.lsl 1 s in
708 for p = 0 to n - 1 do
709 invariant { 0 <= !r }
710 invariant { forall q. bittest !r q <-> (0 <= q < p /\ bittest q i) }
711 if Zbit.test_bit (to_int p) i then begin
712 mask_nonneg (to_int p);
713 r := Zbit.lor !r (ZbitInt.lsl_int 1 (to_int p))
714 end
715 done;
716 let lemma window (p:int) : unit
717 requires { 0 <= p }
718 ensures { p < n <-> numbits p <= s }
719 = if p < to_int n then numbits_lt_lsl p (to_int s)
720 else if numbits p <= to_int s then lt_lsl_of_numbits p (to_int s)
721 in
722 !r
The integer value of a BDD without snode on the window s (aux2 of get_cst' with handle_node = Error). Differs from bddbitv.ml, less efficient: no memo table, so the recursion is exponential on BDDs with shared nodes.
Valid (412ms) (colibri2 25) (cvc4 8) (split_vc) (depth 1)
729 let rec cst_value (s: int63) (t: PBDD.t) : int
730 requires { 0 <= s /\ lsl 1 s <= Int63.max_int }
731 requires { numbits t.dom_indexes <= s }
732 requires { Set.is_empty (PBDD.support_snodes t) }
733 variant { PBDD.nb_nodes t }
734 ensures { forall sn. result = PBDD2.v t s sn }
735 =
736 match PBDD.inspect t with
737 | PBDD.Bool b ->
738 mask_nonneg (to_int s);
739 let r = if b then ZbitInt.mask_int (ZbitInt.lsl_int 1 (to_int s)) else 0 in
740 let lemma eq (sn: PBDD2.env) : unit
741 ensures { r = PBDD2.v t s sn }
742 =
743 let lemma bit (p:int) : unit
744 requires { 0 <= p }
745 ensures { bittest r p <-> bittest (PBDD2.v t s sn) p }
746 = if numbits p <= to_int s then lt_lsl_of_numbits p (to_int s)
747 else if p < pure { lsl 1 s } then numbits_lt_lsl p (to_int s)
748 in
749 ext_bittest r pure { PBDD2.v t s sn }
750 in
751 r
752 | PBDD.IteIndex i th el ->
753 assert { Zbit.subset th.dom_indexes t.dom_indexes };
754 assert { Zbit.subset el.dom_indexes t.dom_indexes };
755 numbits_subset th.dom_indexes t.dom_indexes;
756 numbits_subset el.dom_indexes t.dom_indexes;
757 let m = index_mask s i in
758 let r1 = cst_value s th in
759 let r2 = cst_value s el in
760 let r = Zbit.lor (Zbit.land m r1) (Zbit.land (Zbit.lnot m) r2) in
761 let lemma eq (sn: PBDD2.env) : unit
762 ensures { r = PBDD2.v t s sn }
763 =
764 let lemma bit (p:int) : unit
765 requires { 0 <= p }
766 ensures { bittest r p <-> bittest (PBDD2.v t s sn) p }
767 =
768 assert { r1 = PBDD2.v th s sn /\ r2 = PBDD2.v el s sn };
769 PBDD2.def_v th (to_int s) sn p;
770 PBDD2.def_v el (to_int s) sn p;
771 assert { bittest r1 p <-> (numbits p <= s /\ th.PBDD.v p (sn p)) };
772 assert { bittest r2 p <-> (numbits p <= s /\ el.PBDD.v p (sn p)) };
773 assert { t.PBDD.v p (sn p) = if bittest p i then th.PBDD.v p (sn p) else el.PBDD.v p (sn p) }
774 in
775 ext_bittest r pure { PBDD2.v t s sn }
776 in
777 r
778 | PBDD.IteSnode _ _ _ -> absurd
779 end
The constant value of an IBDD without snode
Valid (105ms) (colibri2)
782 let get_cst_value (x: t) : int
783 requires { Set.is_empty (PBDD.support_snodes x.bdd) }
784 requires { lsl 1 x.size <= Int63.max_int }
785 ensures { forall sn. result = v x sn }
786 =
787 numbits_ge_pos 0 x.bdd.dom_indexes;
788 cst_value x.size x.bdd
789
Valid (126ms) (cvc5)
790 let rec no_var (l: list Key.t) : bool
791 variant { l }
792 ensures { result <-> forall n s a. not (Mem.mem (Key.Var n s a) l) }
793 = match l with
794 | Nil -> true
795 | Cons (Key.Var _ _ _) _ -> false
796 | Cons _ l -> no_var l
797 end
The BDD reads no scalar snode
predicate no_scal (b: PBDD.t) = forall nd. Set.mem nd (support_snodes b) -> not nd.SNode.scal800
A scalar snode in the keys
Valid (106ms) (cvc5)
803 let rec has_scal_key (l: list Key.t) : bool
804 variant { l }
805 ensures { result <-> exists n s. Mem.mem (Key.Var n s True) l }
806 = match l with
807 | Nil -> false
808 | Cons (Key.Var _ _ a) l' -> a || has_scal_key l'
809 | Cons (Key.Index _) l' -> has_scal_key l'
810 end
The BDD reads a scalar snode
Valid (785ms) (cvc5)
813 let has_scal_bdd (b: PBDD.t) : bool
814 ensures { result <-> not (no_scal b) }
815 = has_scal_key (PBDD.vars b)
No snode in the BDD
Valid (737ms) (cvc5)
818 let test_cst (x: t) : bool
819 ensures { result <-> Set.is_empty (PBDD.support_snodes x.bdd) }
820 =
821 no_var (PBDD.vars x.bdd)
822
Valid (92ms) (colibri2)
823 let is_cst (x: t) : option int
824 requires { lsl 1 x.size <= Int63.max_int }
825 ensures { match result with
826 | Some z -> forall sn. v x sn = z
827 | None -> not (Set.is_empty (PBDD.support_snodes x.bdd))
828 end }
829 = if test_cst x then Some (get_cst_value x) else None
830
Valid (1.8s) (cvc5)
831 let rec nodes_of (l: list Key.t) (acc: NodeSet.t) : NodeSet.t
832 variant { l }
833 ensures { forall n. Set.mem n result.NodeSet.elts <->
834 (Set.mem n acc.NodeSet.elts \/ exists s a. Mem.mem (Key.Var n s a) l) }
835 = match l with
836 | Nil -> acc
837 | Cons (Key.Var n _ _) l -> nodes_of l (NodeSet.add n acc)
838 | Cons _ l -> nodes_of l acc
839 end
The nodes of the snodes of the BDD
Valid (1.4s) (colibri2) (split_vc) (depth 1)
842 let nodes (p: t) : NodeSet.t
843 ensures { forall n. Set.mem n result.NodeSet.elts <->
844 exists s a. Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (PBDD.support_snodes p.bdd) \/
845 Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (PBDD.support_snodes p.tail) }
846 = nodes_of (PBDD.vars p.tail) (nodes_of (PBDD.vars p.bdd) (NodeSet.empty ()))
land (v t sn) (mask size) (mask in bddbitv.ml)
Valid (1.2s) (colibri2 13) (cvc4 6) (split_vc) (depth 1)
849 let partial mask_bdd (size maxpos: int63) (t: PBDD.t) : PBDD.t
850 requires { 0 <= size /\ 0 <= maxpos }
851 requires { numbits t.dom_indexes <= size }
852 requires { maxpos + 1 <= Int63.max_int }
853 ensures { numbits result.dom_indexes <= size }
854 ensures { result.dom_snodes = t.dom_snodes }
855 ensures { forall sn. PBDD2.v result size sn = land (mask (maxpos+1)) (PBDD2.v t size sn) }
856 ensures { forall p sn. 0 <= p -> numbits p <= size ->
857 (result.PBDD.v p sn <-> (p <= maxpos /\ t.PBDD.v p sn)) }
858 =
859 mask_nonneg (to_int maxpos + 1);
860 mask_numbits (to_int maxpos + 1);
861 let z = get (cst (ZbitInt.mask_int (to_int maxpos + 1))) size in
862 lor_numbits z.dom_indexes t.dom_indexes;
863 let r = PBDD2.dand z t in
864 let lemma eq (sn:PBDD2.env) : unit
865 ensures { PBDD2.v r size sn = land (mask (maxpos+1)) (PBDD2.v t size sn) }
866 =
867 PBDD2.v_window t (to_int size) (to_int size) sn;
868 ext_bittest pure { PBDD2.v r size sn } pure { land (mask (maxpos+1)) (PBDD2.v t size sn) }
869 in
870 let lemma pt (p: int) (sn: snodes) : unit
871 requires { 0 <= p /\ numbits p <= size }
872 ensures { r.PBDD.v p sn <-> (p <= maxpos /\ t.PBDD.v p sn) }
873 =
874 bit_cenv r (to_int size) p sn; bit_cenv t (to_int size) p sn;
875 eq (cenv sn)
876 in
877 r
878
Valid (1.2s) (cvc4)
879 let is_zero (t: t) : bool
880 ensures { result <-> forall sn. v t sn = 0 }
881 =
882 let (r, ghost wid, ghost wsn) = PBDD.is_equal t.bdd (PBDD2.tfalse ()) in
883 if r then begin
884 let lemma eq (sn:PBDD2.env) : unit
885 ensures { v t sn = 0 }
886 = ext_bittest (v t sn) 0
887 in ()
888 end else begin
889 ext_bittest (lor t.bdd.dom_indexes 0) t.bdd.dom_indexes;
890 assert { bittest (v t (fun _ -> wsn)) wid }
891 end;
892 r
sn where the snodes that read a negative bit at p are false
function clear_neg (p: int) (sn: snodes) : snodes = fun nd -> reads_at p nd /\ Set.mem nd sn895
The snodes of a list of keys
Valid (108ms) (colibri2)
898 let rec ghost function snodes_of (l: list Key.t) : list snode
899 variant { l }
900 ensures { forall nd. Mem.mem nd result <-> Mem.mem (Key.Var nd.SNode.n nd.SNode.s nd.SNode.scal) l }
901 = match l with
902 | Nil -> Nil
903 | Cons (Key.Var n s a) l' -> Cons { SNode.n = n; SNode.s = s; SNode.scal = a } (snodes_of l')
904 | Cons (Key.Index _) l' -> snodes_of l'
905 end
A bound on the bits read at the position p by the snodes of l
Valid (104ms) (colibri2)
908 let rec ghost function bound (p: int) (l: list snode) : int
909 variant { l }
910 ensures { 0 <= result }
911 ensures { forall nd. Mem.mem nd l -> p + nd.SNode.s < result }
912 = match l with
913 | Nil -> 0
914 | Cons nd l' -> let b = bound p l' in if p + to_int nd.SNode.s < b then b else p + to_int nd.SNode.s + 1
915 end
The scalar snodes of the BDD are the ones of shift 0
predicate scal0 (b: PBDD.t) =918forall nd. Set.mem nd (support_snodes b) -> nd.SNode.scal -> nd.SNode.s = 0919
The bits below b of the valuation realizing sn at the position p
function rbits (p: int) (sn: snodes) (b: int) (n: Node.t) : int =922of_bits (fun i -> exists nd. nd.SNode.n = n /\ not nd.SNode.scal /\ to_int nd.SNode.s = i - p /\ Set.mem nd sn) b923
The sign of the node n in sn
predicate rsign (sn: snodes) (n: Node.t) =926exists nd. nd.SNode.n = n /\ nd.SNode.scal /\ nd.SNode.s = 0 /\ Set.mem nd sn927
The valuation of the nodes that realizes sn at the position p: the bits below b, then the sign
function realize (p: int) (sn: snodes) (b: int) : Node.t -> int =931fun n -> if rsign sn n then rbits p sn b n - lsl 1 b else rbits p sn b n932Valid (68ms) (colibri2)933let ghost realize_bit (p: int) (sn: snodes) (b: int) (n: Node.t) (i: int) : unit934requires { 0 <= i < b }935ensures { bittest (realize p sn b n) i <-> bittest (rbits p sn b n) i }936= if pure { rsign sn n } then bittest_sub_lsl pure { rbits p sn b n } b i937Valid (378ms) (cvc4)938let ghost realize_sign (p: int) (sn: snodes) (b: int) (n: Node.t) : unit939requires { 0 <= b }940ensures { realize p sn b n < 0 <-> rsign sn n }941=942let x = pure { rbits p sn b n } in943if x > 0 then begin944numbits_top_bit x;945assert { numbits x <= b };946lt_lsl_of_numbits x b947end948Valid (1.8s) (colibri2 9) (cvc5) (split_vc 3) (depth 3)949let lemma realize_sem (p: int) (sn: snodes) (l: list snode) (nd: snode) : unit950requires { Mem.mem nd l /\ reads_at p nd /\ (nd.SNode.scal -> nd.SNode.s = 0) }951ensures { sem (realize p sn (bound p l)) p nd <-> Set.mem nd sn }952=953if nd.SNode.scal then begin954realize_sign p sn (bound p l) nd.SNode.n;955let lemma uniq (nd': snode) : unit956requires { nd'.SNode.n = nd.SNode.n /\ nd'.SNode.scal /\ nd'.SNode.s = 0 }957ensures { nd' = nd }958= assert { nd'.SNode.s = nd.SNode.s }959in ()960end else begin961let ghost i = p + to_int nd.SNode.s in962realize_bit p sn (bound p l) nd.SNode.n i;963let lemma uniq (nd': snode) : unit964requires { nd'.SNode.n = nd.SNode.n /\ not nd'.SNode.scal /\ to_int nd'.SNode.s = i - p }965ensures { nd' = nd }966= assert { nd'.SNode.s = nd.SNode.s }967in968assert { sem (realize p sn (bound p l)) p nd <->969bittest (realize p sn (bound p l) nd.SNode.n) i }970end971
The snodes of the tail read non–negative bits from the position 2^size on
Valid (404ms) (colibri2 4) (cvc4) (split_vc) (depth 1)
974 let ghost tail_support_nonneg (t: t) (nd: snode) : unit
975 requires { Set.mem nd (support_snodes t.tail) }
976 ensures { reads_at (lsl 1 t.size) nd }
977 =
978 let ghost (id, sn) = PBDD.support_snodes_dep t.tail nd in
979 if pure { not (reads_at (lsl 1 t.size) nd) } then begin
980 PBDD.support_v t.tail id 0 (Set.add nd sn);
981 PBDD.support_v t.tail id 0 (Set.remove nd sn);
982 assert { agree (lsl 1 t.size) (Set.add nd sn) (Set.remove nd sn) }
983 end
A BDD without index does not depend on the position
Valid (47ms) (colibri2)
986 let ghost tail_v (t: PBDD.t) (p: int) (sn: snodes) : unit
987 requires { t.PBDD.dom_indexes = 0 }
988 ensures { t.PBDD.v p sn = t.PBDD.v 0 sn }
989 = PBDD.support_v t p 0 sn
agree is monotone in the position
Valid (62ms) (colibri2)
992 let ghost agree_mono (p q: int) (sn1 sn2: snodes) : unit
993 requires { p <= q /\ agree q sn1 sn2 }
994 ensures { agree p sn1 sn2 }
995 = ()
The snodes of the supports of a term
Valid (1.3s) (colibri2)
998 let ghost cover (t: t) : list snode
999 ensures { forall nd. Set.mem nd (support_snodes t.bdd) -> Mem.mem nd result }
1000 ensures { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd result }
1001 = Lists.(++) (snodes_of (PBDD.vars t.bdd)) (snodes_of (PBDD.vars t.tail))
The bit p of b for the snodes realized by sn
Valid (398ms) (colibri2 5) (cvc5) (split_vc 3) (depth 3)
1004 let ghost env_ok_g (l: list snode) (b: PBDD.t) (p: int) (sn: snodes) : unit
1005 requires { 0 <= p /\ scal0 b }
1006 requires { forall nd. Set.mem nd (support_snodes b) -> Mem.mem nd l }
1007 ensures { b.PBDD.v p (sem (realize p (clear_neg p sn) (bound p l)) p) <-> b.PBDD.v p (clear_neg p sn) }
1008 =
1009 let ghost env = realize p (clear_neg p sn) (bound p l) in
1010 let lemma agree (nd: snode) : unit
1011 requires { Set.mem nd (support_snodes b) }
1012 ensures { Set.mem nd (sem env p) <-> Set.mem nd (clear_neg p sn) }
1013 = if pure { reads_at p nd } then realize_sem p (clear_neg p sn) l nd
1014 in
1015 PBDD.support_snodes_v b p (sem env p) (clear_neg p sn)
The bit p of a term for the snodes realized by sn is its bit for sn
Valid (101ms) (colibri2 12) (cvc4 2) (split_vc) (depth 1)
1018 let ghost bit_env_g (l: list snode) (t: t) (p: int) (sn: snodes) : unit
1019 requires { 0 <= p /\ scal0 t.bdd /\ scal0 t.tail }
1020 requires { forall nd. Set.mem nd (support_snodes t.bdd) -> Mem.mem nd l }
1021 requires { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l }
1022 ensures { bit t p (sem (realize p (clear_neg p sn) (bound p l)) p) <-> bit t p sn }
1023 =
1024 env_ok_g l t.bdd p sn;
1025 env_ok_g l t.tail p sn;
1026 tail_v t.tail p sn;
1027 tail_v t.tail p (clear_neg p sn);
1028 assert { agree p (clear_neg p sn) sn };
1029 if numbits p <= to_int t.size then
1030 assert { t.bdd.PBDD.v p (clear_neg p sn) <-> t.bdd.PBDD.v p sn }
1031 else begin
1032 if p < pure { lsl 1 t.size } then numbits_lt_lsl p (to_int t.size);
1033 agree_mono pure { lsl 1 t.size } p (clear_neg p sn) sn;
1034 assert { t.tail.PBDD.v 0 (clear_neg p sn) <-> t.tail.PBDD.v 0 sn }
1035 end
Two realizations of valuations that differ only at nd'' differ only at the bit p + nd''.s of the node of nd''
Valid (1.7s) (colibri2 5) (cvc4 2) (split_vc 3) (depth 3)
1039 let ghost realize_diff (p: int) (s1 s2: snodes) (b: int) (nd'': snode) (m: Node.t) (i: int) : unit
1040 requires { forall nd. nd <> nd'' -> (Set.mem nd s1 <-> Set.mem nd s2) }
1041 requires { not (m = nd''.SNode.n /\ not nd''.SNode.scal /\ i = p + to_int nd''.SNode.s) }
1042 requires { i < b }
1043 ensures { bittest (realize p s1 b m) i <-> bittest (realize p s2 b m) i }
1044 =
1045 if i >= 0 then begin
1046 realize_bit p s1 b m i; realize_bit p s2 b m i;
1047 let lemma uniq (nd1 nd2: snode) : unit
1048 requires { nd1.SNode.n = nd2.SNode.n /\ not nd1.SNode.scal /\ not nd2.SNode.scal /\ to_int nd1.SNode.s = to_int nd2.SNode.s }
1049 ensures { nd1 = nd2 }
1050 = assert { nd1.SNode.s = nd2.SNode.s }
1051 in ()
1052 end
A snode of the support changes the bit of the term for some position
Valid (920ms) (cvc4)
1055 let ghost support_wit (t: t) (nd'': snode) : (int, snodes)
1056 requires { Set.mem nd'' (support_snodes t.bdd) \/ Set.mem nd'' (support_snodes t.tail) }
1057 ensures { let (p, sn) = result in 0 <= p /\
1058 not (bit t p (Set.add nd'' sn) <-> bit t p (Set.remove nd'' sn)) }
1059 =
1060 if pure { Set.mem nd'' (support_snodes t.bdd) } then begin
1061 let ghost (id, sn) = PBDD.support_snodes_dep t.bdd nd'' in
1062 let ghost p = pure { land (mask t.size) id } in
1063 mask_nonneg (to_int t.size);
1064 land_nonneg_l pure { mask t.size } id;
1065 numbits_subset p pure { mask t.size };
1066 mask_numbits (to_int t.size);
1067 PBDD.support_v t.bdd id p (Set.add nd'' sn);
1068 PBDD.support_v t.bdd id p (Set.remove nd'' sn);
1069 (p, sn)
1070 end else begin
1071 let ghost (id, sn) = PBDD.support_snodes_dep t.tail nd'' in
1072 let ghost p = pure { lsl 1 t.size } in
1073 numbits_lsl (to_int t.size);
1074 mask_nonneg (to_int t.size);
1075 tail_v t.tail id (Set.add nd'' sn); tail_v t.tail id (Set.remove nd'' sn);
1076 tail_v t.tail p (Set.add nd'' sn); tail_v t.tail p (Set.remove nd'' sn);
1077 (p, sn)
1078 end
A snode of the support reads a non–negative bit at some position of the window or of the tail: its shift is not below -2^size
Valid (204ms) (colibri2 9) (split_vc 2) (depth 2)
1082 let ghost shift_bound (t: t) (nd: snode) : unit
1083 requires { Set.mem nd (support_snodes t.bdd) \/ Set.mem nd (support_snodes t.tail) }
1084 ensures { reads_at (lsl 1 t.size) nd }
1085 =
1086 if pure { not (reads_at (lsl 1 t.size) nd) } then begin
1087 let ghost (p, sn) = support_wit t nd in
1088 if numbits p <= to_int t.size then begin
1089 if p < pure { lsl 1 t.size } then () else lt_lsl_of_numbits p (to_int t.size);
1090 assert { agree p (Set.add nd sn) (Set.remove nd sn) }
1091 end else begin
1092 tail_v t.tail p (Set.add nd sn); tail_v t.tail p (Set.remove nd sn);
1093 assert { agree (lsl 1 t.size) (Set.add nd sn) (Set.remove nd sn) }
1094 end
1095 end
Equal bit streams are equal IBDDs (Shostak: the equalities are discovered by comparing the BDDs)
Valid (1.6s) (colibri2 63) (cvc4 6) (cvc5 3) (split_vc 9) (depth 3)
1099 let lemma canonical (t1 t2: t) : unit
1100 requires { scal0 t1.bdd /\ scal0 t1.tail /\ scal0 t2.bdd /\ scal0 t2.tail }
1101 requires { forall env p. 0 <= p -> (bit t1 p (sem env p) <-> bit t2 p (sem env p)) }
1102 ensures { t1.size = t2.size }
1103 ensures { forall p sn. t1.bdd.PBDD.v p sn <-> t2.bdd.PBDD.v p sn }
1104 ensures { forall sn. t1.tail.PBDD.v 0 sn <-> t2.tail.PBDD.v 0 sn }
1105 =
1106 let ghost l = Lists.(++) (Lists.(++) (snodes_of (PBDD.vars t1.bdd)) (snodes_of (PBDD.vars t2.bdd)))
1107 (Lists.(++) (snodes_of (PBDD.vars t1.tail)) (snodes_of (PBDD.vars t2.tail))) in
1108 let lemma env_ok (b: PBDD.t) (p: int) (sn: snodes) : unit
1109 requires { 0 <= p /\ scal0 b }
1110 requires { forall nd. Set.mem nd (support_snodes b) -> Mem.mem nd l }
1111 ensures { b.PBDD.v p (sem (realize p (clear_neg p sn) (bound p l)) p) <-> b.PBDD.v p (clear_neg p sn) }
1112 =
1113 let ghost env = realize p (clear_neg p sn) (bound p l) in
1114 let lemma agree (nd: snode) : unit
1115 requires { Set.mem nd (support_snodes b) }
1116 ensures { Set.mem nd (sem env p) <-> Set.mem nd (clear_neg p sn) }
1117 = if pure { reads_at p nd } then realize_sem p (clear_neg p sn) l nd
1118 in
1119 PBDD.support_snodes_v b p (sem env p) (clear_neg p sn)
1120 in
1121 let lemma in_l (t: t) : unit
1122 requires { t = t1 \/ t = t2 }
1123 ensures { forall nd. Set.mem nd (support_snodes t.bdd) -> Mem.mem nd l }
1124 ensures { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l }
1125 = ()
1126 in
1127 (* the bit [p] for the snodes realized by [sn] is the bit [p] for [sn] *)
1128 let lemma bit_env (t: t) (p: int) (sn: snodes) : unit
1129 requires { t = t1 \/ t = t2 }
1130 requires { 0 <= p }
1131 ensures { bit t p (sem (realize p (clear_neg p sn) (bound p l)) p) <-> bit t p sn }
1132 =
1133 in_l t;
1134 env_ok t.bdd p sn;
1135 env_ok t.tail p sn;
1136 tail_v t.tail p sn;
1137 tail_v t.tail p (clear_neg p sn);
1138 assert { agree p (clear_neg p sn) sn };
1139 if numbits p <= to_int t.size then
1140 assert { t.bdd.PBDD.v p (clear_neg p sn) <-> t.bdd.PBDD.v p sn }
1141 else begin
1142 if p < pure { lsl 1 t.size } then numbits_lt_lsl p (to_int t.size);
1143 agree_mono pure { lsl 1 t.size } p (clear_neg p sn) sn;
1144 assert { t.tail.PBDD.v 0 (clear_neg p sn) <-> t.tail.PBDD.v 0 sn }
1145 end
1146 in
1147 (* the tails *)
1148 let ghost m = if t1.size <= t2.size then t2.size else t1.size in
1149 let ghost p0 = pure { lsl 1 m } in
1150 numbits_lsl (to_int m);
1151 let lemma tails (sn: snodes) : unit
1152 ensures { t1.tail.PBDD.v 0 sn <-> t2.tail.PBDD.v 0 sn }
1153 =
1154 mask_nonneg (to_int m);
1155 bit_env t1 p0 sn; bit_env t2 p0 sn;
1156 assert { bit t1 p0 sn <-> t1.tail.PBDD.v 0 sn };
1157 assert { bit t2 p0 sn <-> t2.tail.PBDD.v 0 sn }
1158 in
1159 (* the sizes *)
1160 let lemma sizes_le (a b: t) : unit
1161 requires { (a = t1 /\ b = t2) \/ (a = t2 /\ b = t1) }
1162 requires { b.size < a.size }
1163 ensures { false }
1164 =
1165 numbits_ge_pos 0 b.bdd.dom_indexes;
1166 assert { 0 <= b.size < a.size };
1167 assert { minimal_t a.bdd a.tail a.size };
1168 assert { exists p sn. 0 <= p /\ numbits p = a.size /\
1169 not (a.bdd.PBDD.v p sn <-> a.tail.PBDD.v 0 sn) };
1170 let ghost (p, sn) = any (int, snodes)
1171 ensures { let (p, sn) = result in 0 <= p /\ numbits p = a.size /\
1172 not (a.bdd.PBDD.v p sn <-> a.tail.PBDD.v 0 sn) } in
1173 bit_env t1 p sn; bit_env t2 p sn;
1174 tails sn;
1175 assert { bit a p sn <-> a.bdd.PBDD.v p sn };
1176 assert { bit b p sn <-> b.tail.PBDD.v 0 sn }
1177 in
1178 if t1.size < t2.size then sizes_le t2 t1
1179 else if t2.size < t1.size then sizes_le t1 t2;
1180 (* the windows *)
1181 let lemma eqp (p: int) (sn: snodes) : unit
1182 requires { 0 <= p /\ numbits p <= t1.size }
1183 ensures { t1.bdd.PBDD.v p sn <-> t2.bdd.PBDD.v p sn }
1184 =
1185 bit_env t1 p sn; bit_env t2 p sn
1186 in
1187 let lemma all (p: int) (sn: snodes) : unit
1188 ensures { t1.bdd.PBDD.v p sn <-> t2.bdd.PBDD.v p sn }
1189 =
1190 let ghost p' = pure { land (mask t1.size) p } in
1191 mask_nonneg (to_int t1.size);
1192 land_nonneg_l pure { mask t1.size } p;
1193 numbits_subset p' pure { mask t1.size };
1194 mask_numbits (to_int t1.size);
1195 PBDD.support_v t1.bdd p p' sn;
1196 PBDD.support_v t2.bdd p p' sn;
1197 eqp p' sn
1198 in
1199 ()
1200
1201 (* ---- Building terms with a tail ---- *)
The bit p of a window b and a tail tl
function pbit (b tl: PBDD.t) (s: int) (p: int) (sn: snodes) : bool =1204if numbits p <= s then b.PBDD.v p sn else tl.PBDD.v 0 sn1205
The term of the window bdd and the tail tl, the window being reduced while its upper half is the tail
Valid (854ms) (colibri2 60) (cvc4 8) (split_vc) (depth 1)
1209 let partial mk_t (bdd tl: PBDD.t) (size: int63) : t
1210 requires { 0 <= size }
1211 requires { numbits bdd.dom_indexes <= size }
1212 requires { tl.dom_indexes = 0 }
1213 requires { no_neg bdd size }
1214 requires { no_neg_tail tl size }
1215 ensures { result.bdd.dom_snodes = bdd.dom_snodes }
1216 ensures { result.tail = tl }
1217 ensures { forall p sn. 0 <= p -> (bit result p sn <-> pbit bdd tl size p sn) }
1218 ensures { result.size <= size }
1219 ensures { Set.subset (support_snodes result.bdd) (support_snodes bdd) }
1220 =
1221 let rec partial aux (bdd: PBDD.t) (size: int63) : t
1222 requires { 0 <= size }
1223 requires { numbits bdd.dom_indexes <= size }
1224 requires { no_neg bdd size }
1225 requires { no_neg_tail tl size }
1226 variant { size }
1227 ensures { result.bdd.dom_snodes = bdd.dom_snodes }
1228 ensures { result.tail = tl }
1229 ensures { forall p sn. 0 <= p -> (bit result p sn <-> pbit bdd tl size p sn) }
1230 ensures { result.size <= size }
1231 = if size = 0 then { bdd = bdd; size = size; tail = tl }
1232 else begin
1233 let k = size - 1 in
1234 let d = PBDD2.dxor bdd tl in
1235 lor_numbits bdd.dom_indexes tl.dom_indexes;
1236 let lemma dv (p: int) (x: snodes) : unit
1237 ensures { d.PBDD.v p x <-> not (bdd.PBDD.v p x <-> tl.PBDD.v 0 x) }
1238 = tail_v tl p x
1239 in
1240 if PBDD2.upper_empty d k then begin
1241 (* the upper half of the window is the tail *)
1242 let lemma uniform (p: int) (x: snodes) : unit
1243 requires { 0 <= p /\ numbits p = to_int k + 1 }
1244 ensures { bdd.PBDD.v p x <-> tl.PBDD.v 0 x }
1245 =
1246 let sn = cenv x in
1247 let lemma bit (q: int) : unit
1248 requires { 0 <= q }
1249 ensures { bittest (PBDD2.v d (to_int k + 1) sn) q <-> bittest (PBDD2.v d k sn) q }
1250 = ()
1251 in
1252 PBDD2.def_v d (to_int k + 1) sn p;
1253 PBDD2.def_v d (to_int k) sn p;
1254 bit p
1255 in
1256 let r = PBDD2.cofactor_low bdd k in
1257 let lemma same (p: int) (sn: snodes) : unit
1258 requires { 0 <= p /\ numbits p <= to_int k }
1259 ensures { r.PBDD.v p sn <-> bdd.PBDD.v p sn }
1260 = bit_cenv r (to_int k) p sn; bit_cenv bdd (to_int k) p sn
1261 in
1262 let lemma nn (p: int) (sn1 sn2: snodes) : unit
1263 requires { 0 <= p /\ numbits p <= to_int k /\ agree p sn1 sn2 }
1264 ensures { r.PBDD.v p sn1 <-> r.PBDD.v p sn2 }
1265 = ()
1266 in
1267 let lemma nnt (sn1 sn2: snodes) : unit
1268 requires { agree (lsl 1 (to_int k)) sn1 sn2 }
1269 ensures { tl.PBDD.v 0 sn1 <-> tl.PBDD.v 0 sn2 }
1270 =
1271 numbits_lsl (to_int k);
1272 mask_nonneg (to_int k);
1273 uniform pure { lsl 1 (to_int k) } sn1; uniform pure { lsl 1 (to_int k) } sn2
1274 in
1275 aux r k
1276 end else begin
1277 let lemma upper (_: unit) : unit
1278 ensures { minimal_t bdd tl size }
1279 =
1280 if pure { not (minimal_t bdd tl size) } then begin
1281 let lemma eq (sn: PBDD2.env) : unit
1282 ensures { PBDD2.v d (to_int k + 1) sn = PBDD2.v d k sn }
1283 =
1284 let lemma bit (p: int) : unit
1285 ensures { bittest (PBDD2.v d (to_int k + 1) sn) p <-> bittest (PBDD2.v d k sn) p }
1286 = if 0 <= p && numbits p = to_int k + 1 then
1287 assert { not (d.PBDD.v p (sn p)) }
1288 in
1289 ext_bittest pure { PBDD2.v d (to_int k + 1) sn } pure { PBDD2.v d k sn }
1290 in
1291 assert { false }
1292 end
1293 in
1294 { bdd = bdd; size = size; tail = tl }
1295 end
1296 end
1297 in
1298 let res = aux bdd size in
1299 let lemma ind (nd: snode) (p: int) (sn: snodes) : unit
1300 requires { not (Set.mem nd (support_snodes bdd)) /\ 0 <= p /\ numbits p <= isize res }
1301 ensures { (ibdd_bdd res).PBDD.v p (Set.add nd sn) <-> (ibdd_bdd res).PBDD.v p (Set.remove nd sn) }
1302 = PBDD.support_snodes_v bdd p (Set.add nd sn) (Set.remove nd sn)
1303 in
1304 supp_win (ibdd_bdd res) (to_int (isize res)) (support_snodes bdd);
1305 res
1306
Valid (420ms) (cvc4)
1307 let has_tail (t: t) : bool
1308 ensures { result <-> tailed t }
1309 =
1310 let (r, ghost wid, ghost wsn) = PBDD.is_equal t.tail (PBDD2.tfalse ()) in
1311 if not r then tail_v t.tail wid wsn;
1312 not r
The bits of the term are all false
Valid (797ms) (colibri2 12) (cvc4 3) (split_vc 4) (depth 3)
1315 let is_zero_t (t: t) : bool
1316 ensures { result <-> (forall p sn. 0 <= p -> not (bit t p sn)) }
1317 =
1318 let (r, ghost wid, ghost wsn) = PBDD.is_equal t.bdd (PBDD2.tfalse ()) in
1319 if not r then begin
1320 numbits_ge_pos 0 t.bdd.dom_indexes;
1321 lor_numbits t.bdd.dom_indexes 0;
1322 assert { bit t wid wsn }
1323 end;
1324 let tl = has_tail t in
1325 if r && tl then begin
1326 let ghost p = pure { lsl 1 t.size } in
1327 numbits_lsl (to_int t.size);
1328 mask_nonneg (to_int t.size);
1329 assert { 0 <= p /\ numbits p = t.size + 1 };
1330 let ghost sn = any snodes ensures { t.tail.PBDD.v 0 result } in
1331 assert { bit t p sn }
1332 end;
1333 r && not tl
The positions with an index bit in from_..to_-1 set (cond of grow)
Valid (1.8s) (colibri2 16) (cvc4 8) (split_vc 3) (depth 2)
1336 let partial high_cond (from_ to_: int63) : PBDD.t
1337 requires { 0 <= from_ <= to_ }
1338 ensures { numbits result.dom_indexes <= to_ }
1339 ensures { result.dom_snodes = Set.empty }
1340 ensures { result.PBDD.v = (fun (id:indexes) (_:snodes) -> exists m: int63. from_ <= m < to_ /\ bittest id m) }
1341 =
1342 let rec partial aux (acc: PBDD.t) (n: int63) : PBDD.t
1343 requires { from_ <= n <= to_ }
1344 requires { numbits acc.dom_indexes <= n }
1345 requires { acc.dom_snodes = Set.empty }
1346 requires { acc.PBDD.v = (fun (id:indexes) (_:snodes) -> exists m: int63. from_ <= m < n /\ bittest id m) }
1347 variant { to_ - n }
1348 ensures { numbits result.dom_indexes <= to_ }
1349 ensures { result.dom_snodes = Set.empty }
1350 ensures { result.PBDD.v = (fun (id:indexes) (_:snodes) -> exists m: int63. from_ <= m < to_ /\ bittest id m) }
1351 = if n = to_ then acc
1352 else begin
1353 let acc' = PBDD.dor acc (PBDD.bdd_of_index n) in
1354 lor_numbits acc.dom_indexes pure { lsl 1 (to_int n) };
1355 let lemma step (id:indexes) (sn:snodes) : unit
1356 ensures { acc'.PBDD.v id sn <-> exists m: int63. from_ <= m < n+1 /\ bittest id m }
1357 = ()
1358 in
1359 aux acc' (n+1)
1360 end
1361 in
1362 aux (PBDD.tfalse ()) from_
The window s of x: the bits of x on the positions p < 2^s (the window of x completed by its tail when s > x.size)
Valid (1.9s) (colibri2 33) (cvc4 20) (split_vc) (depth 1)
1366 let partial get_t (x: t) (s: int63) : PBDD.t
1367 requires { 0 <= s }
1368 ensures { numbits result.dom_indexes <= s }
1369 ensures { Set.subset result.dom_snodes (Set.union x.bdd.dom_snodes x.tail.dom_snodes) }
1370 ensures { forall p sn. 0 <= p -> numbits p <= s -> (result.PBDD.v p sn <-> bit x p sn) }
1371 ensures { no_neg result s }
1372 ensures { Set.subset (support_snodes result) (Set.union (support_snodes x.bdd) (support_snodes x.tail)) }
1373 =
1374 numbits_ge_pos 0 x.bdd.dom_indexes;
1375 let res = if s <= x.size then begin
1376 let r = get x s in
1377 let lemma pt (p: int) (sn: snodes) : unit
1378 requires { 0 <= p /\ numbits p <= s }
1379 ensures { r.PBDD.v p sn <-> bit x p sn }
1380 = ()
1381 in
1382 r
1383 end else begin
1384 let cond = high_cond x.size s in
1385 let lo = PBDD.dand x.bdd (PBDD.dnot cond) in
1386 let hi = PBDD.dand cond x.tail in
1387 let r = PBDD.dor lo hi in
1388 lor_numbits x.bdd.dom_indexes cond.dom_indexes;
1389 lor_numbits cond.dom_indexes x.tail.dom_indexes;
1390 lor_numbits lo.dom_indexes hi.dom_indexes;
1391 let lemma pt (p: int) (sn: snodes) : unit
1392 requires { 0 <= p /\ numbits p <= s }
1393 ensures { r.PBDD.v p sn <-> bit x p sn }
1394 =
1395 tail_v x.tail p sn;
1396 if numbits p <= to_int x.size then begin
1397 let lemma nocond (m: int63) : unit
1398 requires { x.size <= m < s /\ bittest p m }
1399 ensures { false }
1400 = if p > 0 then numbits_high_clear p (to_int m)
1401 in ()
1402 end else begin
1403 let ghost m = Int63.of_int (numbits p - 1) in
1404 numbits_top_bit p;
1405 assert { x.size <= m < s /\ bittest p m }
1406 end
1407 in
1408 let lemma nn (p: int) (sn1 sn2: snodes) : unit
1409 requires { 0 <= p /\ numbits p <= s /\ agree p sn1 sn2 }
1410 ensures { r.PBDD.v p sn1 <-> r.PBDD.v p sn2 }
1411 =
1412 if numbits p > to_int x.size then begin
1413 if p < pure { lsl 1 x.size } then numbits_lt_lsl p (to_int x.size);
1414 agree_mono pure { lsl 1 x.size } p sn1 sn2
1415 end
1416 in
1417 r
1418 end in
1419 let lemma ind (nd: snode) (p: int) (sn: snodes) : unit
1420 requires { not (Set.mem nd (Set.union (support_snodes x.bdd) (support_snodes x.tail))) /\ 0 <= p /\ numbits p <= s }
1421 ensures { res.PBDD.v p (Set.add nd sn) <-> res.PBDD.v p (Set.remove nd sn) }
1422 =
1423 if numbits p <= to_int x.size then PBDD.support_snodes_v x.bdd p (Set.add nd sn) (Set.remove nd sn)
1424 else begin
1425 tail_v x.tail p (Set.add nd sn); tail_v x.tail p (Set.remove nd sn);
1426 PBDD.support_snodes_v x.tail 0 (Set.add nd sn) (Set.remove nd sn)
1427 end
1428 in
1429 supp_win res (to_int s) (Set.union (support_snodes x.bdd) (support_snodes x.tail));
1430 res
1431
1432 (* ---- The integer value of a bit stream ---- *)
1433
1434 function iabs (x: int) : int = if x < 0 then - x else x
The high bits of a negative integer are set
Valid (54ms) (colibri2)
1437 let ghost neg_high (z i: int) : unit
1438 requires { z < 0 /\ numbits (iabs z) <= i }
1439 ensures { bittest z i }
1440 =
1441 let k = numbits (iabs z) in
1442 numbits_ge_pos 0 (iabs z);
1443 numbits_lsl_lt (iabs z);
1444 assert { 0 <= z + lsl 1 k < lsl 1 k };
1445 bittest_sub_lsl_high (z + Zbit.lsl 1 k) k i
Above numbits |x| the bits of x are all equal (its sign)
Valid (68ms) (colibri2)
1448 let ghost bittest_stable (x i j: int) : unit
1449 requires { numbits (iabs x) <= i /\ numbits (iabs x) <= j }
1450 ensures { bittest x i <-> bittest x j }
1451 =
1452 if x > 0 then begin
1453 numbits_high_clear x i; numbits_high_clear x j
1454 end else if x < 0 then begin
1455 neg_high x i; neg_high x j
1456 end
A position from which the snodes of l no longer change with p
Valid (832ms) (colibri2)
1459 let rec ghost function stab_bound (env: Node.t -> int) (l: list snode) : int
1460 variant { l }
1461 ensures { 0 <= result }
1462 ensures { forall nd p. Mem.mem nd l -> result <= p -> numbits (iabs (env nd.SNode.n)) <= p + nd.SNode.s }
1463 = match l with
1464 | Nil -> 0
1465 | Cons nd l' ->
1466 let b = stab_bound env l' in
1467 let c = numbits (iabs (env nd.SNode.n)) + max 0 (- to_int nd.SNode.s) in
1468 if b <= c then c else b
1469 end
The bits of t from n on are all equal, when n is above the window and above the stabilization bound of the snodes of l
Valid (687ms) (colibri2 10) (cvc4) (split_vc) (depth 1)
1473 let ghost stream_stable (t: t) (env: Node.t -> int) (l: list snode) (p: int) : unit
1474 requires { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l }
1475 requires { lsl 1 t.size + stab_bound env l <= p }
1476 ensures { bit t p (sem env p) <->
1477 bit t (lsl 1 t.size + stab_bound env l) (sem env (lsl 1 t.size + stab_bound env l)) }
1478 =
1479 let n = pure { lsl 1 t.size } + stab_bound env l in
1480 mask_nonneg (to_int t.size);
1481 if p < pure { lsl 1 t.size } then numbits_lt_lsl p (to_int t.size);
1482 if n < pure { lsl 1 t.size } then numbits_lt_lsl n (to_int t.size);
1483 tail_v t.tail p (sem env p);
1484 tail_v t.tail n (sem env n);
1485 let lemma same (nd: snode) : unit
1486 requires { Set.mem nd (support_snodes t.tail) }
1487 ensures { sem env p nd <-> sem env n nd }
1488 =
1489 sem_def env p nd; sem_def env n nd;
1490 bittest_stable (env nd.SNode.n) (p + to_int nd.SNode.s) (n + to_int nd.SNode.s)
1491 in
1492 PBDD.support_snodes_v t.tail 0 (sem env p) (sem env n)
1493
Valid (384ms) (cvc4)
1494 let ghost of_bits_lt (f: int -> bool) (n: int) : unit
1495 requires { 0 <= n }
1496 ensures { of_bits f n < lsl 1 n }
1497 =
1498 let x = of_bits f n in
1499 if x > 0 then begin
1500 numbits_top_bit x;
1501 numbits_lsl_lt x;
1502 assert { numbits x <= n };
1503 lsl_power (numbits x); lsl_power n;
1504 Power_monotonic 2 (numbits x) n
1505 end else mask_nonneg n
z is the integer whose bits are the bits of t (the stream is eventually constant: z is negative when the tail is true at the limit)
predicate is_value (t: t) (env: Node.t -> int) (z: int) =1510forall p. 0 <= p -> (bittest z p <-> bit t p (sem env p))1511Valid (355ms) (colibri2 12) (split_vc) (depth 1)1512let ghost value_exists (t: t) (env: Node.t -> int) : int1513ensures { is_value t env result }1514=1515let l = snodes_of (PBDD.vars t.tail) in1516assert { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l };1517let n = pure { lsl 1 t.size } + stab_bound env l in1518mask_nonneg (to_int t.size);1519of_bits_lt pure { fun q -> bit t q (sem env q) } n;1520let z = pure { of_bits (fun q -> bit t q (sem env q)) n1521- (if bit t n (sem env n) then lsl 1 n else 0) } in1522let lemma bitz (p: int) : unit1523requires { 0 <= p }1524ensures { bittest z p <-> bit t p (sem env p) }1525=1526if p >= n then stream_stable t env l p;1527if pure { bit t n (sem env n) } then begin1528if p < n then bittest_sub_lsl (pure { of_bits (fun q -> bit t q (sem env q)) n }) n p1529else bittest_sub_lsl_high (pure { of_bits (fun q -> bit t q (sem env q)) n }) n p1530end1531in1532assert { is_value t env z };1533z1534
The value is unique
Valid (76ms) (colibri2)
1537 let ghost value_unique (t: t) (env: Node.t -> int) (z1 z2: int) : unit
1538 requires { is_value t env z1 /\ is_value t env z2 }
1539 ensures { z1 = z2 }
1540 = ext_bittest z1 z2
The snodes at infinity: every atom of the node n is its sign
function sem_inf (env: Node.t -> int) : snodes = fun nd -> env nd.SNode.n < 01543
Above numbits |x| the bits of x are its sign
Valid (60ms) (colibri2)
1546 let ghost bittest_sign (x i: int) : unit
1547 requires { numbits (iabs x) <= i }
1548 ensures { bittest x i <-> x < 0 }
1549 =
1550 if x > 0 then numbits_high_clear x i
1551 else if x < 0 then neg_high x i
The sign of the value of t is its tail at infinity
Valid (893ms) (colibri2 14) (cvc4) (split_vc) (depth 1)
1554 let ghost value_sign (t: t) (env: Node.t -> int) (z: int) : unit
1555 requires { is_value t env z }
1556 ensures { z < 0 <-> t.tail.PBDD.v 0 (sem_inf env) }
1557 =
1558 let l = snodes_of (PBDD.vars t.tail) in
1559 assert { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l };
1560 mask_nonneg (to_int t.size);
1561 numbits_ge_pos 0 (iabs z);
1562 let n = pure { lsl 1 t.size } + stab_bound env l + numbits (iabs z) in
1563 bittest_sign z n;
1564 if n < pure { lsl 1 t.size } then numbits_lt_lsl n (to_int t.size);
1565 assert { not (numbits n <= t.size) };
1566 tail_v t.tail n (sem env n);
1567 let lemma same (nd: snode) : unit
1568 requires { Set.mem nd (support_snodes t.tail) }
1569 ensures { sem env n nd <-> sem_inf env nd }
1570 =
1571 sem_def env n nd;
1572 if not nd.SNode.scal then bittest_sign (env nd.SNode.n) (n + to_int nd.SNode.s)
1573 in
1574 PBDD.support_snodes_v t.tail 0 (sem env n) (sem_inf env)
1575
1576 (* ---- Operations on terms with a tail ---- *)
1577
Valid (50ms) (colibri2)
1578 let ghost lor_zero (_: unit) : unit
1579 ensures { lor 0 0 = 0 }
1580 = ext_bittest (lor 0 0) 0
no_neg_tail for a bigger window
Valid (65ms) (colibri2)
1583 let ghost no_neg_tail_mono (tl: PBDD.t) (a b: int) : unit
1584 requires { 0 <= a <= b }
1585 requires { no_neg_tail tl a }
1586 ensures { no_neg_tail tl b }
1587 =
1588 lsl_power a; lsl_power b;
1589 Power_monotonic 2 a b;
1590 let lemma pt (sn1 sn2: snodes) : unit
1591 requires { agree (lsl 1 b) sn1 sn2 }
1592 ensures { tl.PBDD.v 0 sn1 <-> tl.PBDD.v 0 sn2 }
1593 = agree_mono (Zbit.lsl 1 a) (Zbit.lsl 1 b) sn1 sn2
1594 in ()
1595
Valid (886ms) (cvc4)
1596 let partial lognot_i (t: t) : t
1597 ensures { all_snodes result = all_snodes t }
1598 ensures { result.size <= t.size }
1599 ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t p sn)) }
1600 =
1601 let b = PBDD.dnot t.bdd in
1602 let tl = PBDD.dnot t.tail in
1603 mk_t b tl t.size
1604
Valid (1.4s) (colibri2 20) (cvc4 7) (split_vc) (depth 1)
1605 let partial logand_i (t1 t2: t) : t
1606 ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
1607 ensures { to_int result.size <= max (to_int t1.size) (to_int t2.size) }
1608 ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn /\ bit t2 p sn) }
1609 =
1610 let sz = if t1.size <= t2.size then t2.size else t1.size in
1611 let b1 = get_t t1 sz in
1612 let b2 = get_t t2 sz in
1613 lor_numbits b1.dom_indexes b2.dom_indexes;
1614 let b = PBDD.dand b1 b2 in
1615 lor_zero ();
1616 let tl = PBDD.dand t1.tail t2.tail in
1617 no_neg_tail_mono t1.tail (to_int t1.size) (to_int sz);
1618 no_neg_tail_mono t2.tail (to_int t2.size) (to_int sz);
1619 let r = mk_t b tl sz in
1620 let lemma pt (p: int) (sn: snodes) : unit
1621 requires { 0 <= p }
1622 ensures { bit r p sn <-> bit t1 p sn /\ bit t2 p sn }
1623 =
1624 tail_v t1.tail p sn; tail_v t2.tail p sn;
1625 if numbits p <= to_int sz then begin
1626 assert { b.PBDD.v p sn <-> (b1.PBDD.v p sn /\ b2.PBDD.v p sn) };
1627 assert { b1.PBDD.v p sn <-> bit t1 p sn };
1628 assert { b2.PBDD.v p sn <-> bit t2 p sn }
1629 end else begin
1630 assert { numbits p > to_int t1.size /\ numbits p > to_int t2.size };
1631 assert { bit t1 p sn <-> t1.tail.PBDD.v 0 sn };
1632 assert { bit t2 p sn <-> t2.tail.PBDD.v 0 sn };
1633 assert { tl.PBDD.v 0 sn <-> (t1.tail.PBDD.v 0 sn /\ t2.tail.PBDD.v 0 sn) }
1634 end
1635 in
1636 r
1637
Valid (1.4s) (colibri2 18) (cvc4 9) (split_vc) (depth 1)
1638 let partial logor_i (t1 t2: t) : t
1639 ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
1640 ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn \/ bit t2 p sn) }
1641 ensures { forall sn. result.tail.PBDD.v 0 sn <-> (t1.tail.PBDD.v 0 sn \/ t2.tail.PBDD.v 0 sn) }
1642 =
1643 let sz = if t1.size <= t2.size then t2.size else t1.size in
1644 let b1 = get_t t1 sz in
1645 let b2 = get_t t2 sz in
1646 lor_numbits b1.dom_indexes b2.dom_indexes;
1647 let b = PBDD.dor b1 b2 in
1648 lor_zero ();
1649 let tl = PBDD.dor t1.tail t2.tail in
1650 no_neg_tail_mono t1.tail (to_int t1.size) (to_int sz);
1651 no_neg_tail_mono t2.tail (to_int t2.size) (to_int sz);
1652 let r = mk_t b tl sz in
1653 let lemma pt (p: int) (sn: snodes) : unit
1654 requires { 0 <= p }
1655 ensures { bit r p sn <-> bit t1 p sn \/ bit t2 p sn }
1656 =
1657 tail_v t1.tail p sn; tail_v t2.tail p sn;
1658 if numbits p <= to_int sz then begin
1659 assert { b.PBDD.v p sn <-> (b1.PBDD.v p sn \/ b2.PBDD.v p sn) };
1660 assert { b1.PBDD.v p sn <-> bit t1 p sn };
1661 assert { b2.PBDD.v p sn <-> bit t2 p sn }
1662 end else begin
1663 assert { numbits p > to_int t1.size /\ numbits p > to_int t2.size };
1664 assert { bit t1 p sn <-> t1.tail.PBDD.v 0 sn };
1665 assert { bit t2 p sn <-> t2.tail.PBDD.v 0 sn };
1666 assert { tl.PBDD.v 0 sn <-> (t1.tail.PBDD.v 0 sn \/ t2.tail.PBDD.v 0 sn) }
1667 end
1668 in
1669 r
1670
Valid (1.2s) (colibri2 18) (cvc4 8) (split_vc) (depth 1)
1671 let partial xor_i (t1 t2: t) : t
1672 ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
1673 ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t1 p sn <-> bit t2 p sn)) }
1674 =
1675 let sz = if t1.size <= t2.size then t2.size else t1.size in
1676 let b1 = get_t t1 sz in
1677 let b2 = get_t t2 sz in
1678 lor_numbits b1.dom_indexes b2.dom_indexes;
1679 let b = PBDD.dxor b1 b2 in
1680 lor_zero ();
1681 let tl = PBDD.dxor t1.tail t2.tail in
1682 no_neg_tail_mono t1.tail (to_int t1.size) (to_int sz);
1683 no_neg_tail_mono t2.tail (to_int t2.size) (to_int sz);
1684 let r = mk_t b tl sz in
1685 let lemma pt (p: int) (sn: snodes) : unit
1686 requires { 0 <= p }
1687 ensures { bit r p sn <-> not (bit t1 p sn <-> bit t2 p sn) }
1688 =
1689 tail_v t1.tail p sn; tail_v t2.tail p sn;
1690 if numbits p <= to_int sz then begin
1691 assert { b.PBDD.v p sn <-> not (b1.PBDD.v p sn <-> b2.PBDD.v p sn) };
1692 assert { b1.PBDD.v p sn <-> bit t1 p sn };
1693 assert { b2.PBDD.v p sn <-> bit t2 p sn }
1694 end else begin
1695 assert { numbits p > to_int t1.size /\ numbits p > to_int t2.size };
1696 assert { bit t1 p sn <-> t1.tail.PBDD.v 0 sn };
1697 assert { bit t2 p sn <-> t2.tail.PBDD.v 0 sn };
1698 assert { tl.PBDD.v 0 sn <-> not (t1.tail.PBDD.v 0 sn <-> t2.tail.PBDD.v 0 sn) }
1699 end
1700 in
1701 r
lnot of a negative integer is a non–negative integer with fewer bits
Valid (90ms) (colibri2)
1704 let ghost lnot_neg (x: int) : unit
1705 requires { x < 0 }
1706 ensures { 0 <= lnot x /\ numbits (lnot x) <= numbits (iabs x) }
1707 =
1708 let y = lnot x in
1709 let k = numbits (iabs x) in
1710 let lemma hb (i: int) : unit
1711 requires { k <= i }
1712 ensures { not (bittest y i) }
1713 = neg_high x i
1714 in
1715 if y < 0 then begin
1716 let i = max k (numbits (iabs y)) in
1717 neg_high y i; hb i
1718 end;
1719 if y > 0 && numbits y > k then begin
1720 numbits_top_bit y;
1721 hb (numbits y - 1)
1722 end
1723
Valid (1.6s) (colibri2 9) (cvc4 2) (split_vc) (depth 1)
1724 let partial umonome (n: Node.t) : t
1725 ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }
1726 ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = False }) }
1727 =
1728 let nd = { SNode.n = n; SNode.s = 0; SNode.scal = False } in
1729 let b = PBDD2.bdd_of_snode nd in
1730 let lemma nn (p: int) (sn1 sn2: snodes) : unit
1731 requires { 0 <= p /\ numbits p <= 0 /\ agree p sn1 sn2 }
1732 ensures { b.PBDD.v p sn1 <-> b.PBDD.v p sn2 }
1733 = if p > 0 then numbits_ge_pos 1 p
1734 in
1735 mk_t b b 0
The sign of the node n at every position (its scalar atom)
Valid (1.7s) (colibri2 5) (cvc4 2) (split_vc) (depth 1)
1738 let partial uscalar (n: Node.t) : t
1739 ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = True } }
1740 ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = True }) }
1741 =
1742 let nd = { SNode.n = n; SNode.s = 0; SNode.scal = True } in
1743 let b = PBDD2.bdd_of_snode nd in
1744 mk_t b b 0
1745
Valid (691ms) (colibri2 18) (split_vc) (depth 1)
1746 let partial cst_z (x: int) : t
1747 requires { numbits (iabs x) <= Int63.max_int }
1748 ensures { all_snodes result = Set.empty }
1749 ensures { to_int result.size <= numbits (numbits (iabs x)) }
1750 ensures { forall p sn. 0 <= p -> (bit result p sn <-> bittest x p) }
1751 =
1752 let lemma cst_bit (r: t) (y: int) : unit
1753 requires { 0 <= y /\ forall sn. v r sn = y }
1754 requires { forall sn. not (r.tail.PBDD.v 0 sn) }
1755 ensures { forall p sn. 0 <= p -> (bit r p sn <-> bittest y p) }
1756 =
1757 let lemma pt (p: int) (sn: snodes) : unit
1758 requires { 0 <= p }
1759 ensures { bit r p sn <-> bittest y p }
1760 =
1761 assert { v r (cenv sn) = y };
1762 PBDD2.def_v r.bdd (to_int r.size) (cenv sn) p
1763 in ()
1764 in
1765 if x >= 0 then begin
1766 let r = cst x in
1767 cst_bit r x;
1768 r
1769 end else begin
1770 lnot_neg x;
1771 let y = Zbit.lnot x in
1772 let c = cst y in
1773 cst_bit c y;
1774 lognot_i c
1775 end
1776
Valid (101ms) (colibri2 8) (cvc4 2) (split_vc) (depth 1)
1777 let partial logand (t1 t2: t) : t
1778 ensures { result.bdd.dom_snodes = Set.union t1.bdd.dom_snodes t2.bdd.dom_snodes }
1779 ensures { forall sn. v result sn = land (v t1 sn) (v t2 sn) }
1780 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1781 =
1782 let size = if t1.size <= t2.size then t2.size else t1.size in
1783 let b1 = get t1 size in
1784 let b2 = get t2 size in
1785 lor_numbits b1.dom_indexes b2.dom_indexes;
1786 mk (PBDD2.dand b1 b2) size
1787
Valid (104ms) (colibri2 8) (cvc4 2) (split_vc) (depth 1)
1788 let partial logor (t1 t2: t) : t
1789 ensures { result.bdd.dom_snodes = Set.union t1.bdd.dom_snodes t2.bdd.dom_snodes }
1790 ensures { forall sn. v result sn = lor (v t1 sn) (v t2 sn) }
1791 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1792 =
1793 let size = if t1.size <= t2.size then t2.size else t1.size in
1794 let b1 = get t1 size in
1795 let b2 = get t2 size in
1796 lor_numbits b1.dom_indexes b2.dom_indexes;
1797 mk (PBDD2.dor b1 b2) size
1798
Valid (107ms) (colibri2 8) (cvc4 2) (split_vc) (depth 1)
1799 let partial xor (t1 t2: t) : t
1800 ensures { result.bdd.dom_snodes = Set.union t1.bdd.dom_snodes t2.bdd.dom_snodes }
1801 ensures { forall sn. v result sn = lxor (v t1 sn) (v t2 sn) }
1802 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1803 =
1804 let size = if t1.size <= t2.size then t2.size else t1.size in
1805 let b1 = get t1 size in
1806 let b2 = get t2 size in
1807 lor_numbits b1.dom_indexes b2.dom_indexes;
1808 mk (PBDD2.dxor b1 b2) size
1809
Valid (2.6s) (colibri2 14) (cvc4 7) (split_vc 3) (depth 3)
1810 let partial lognot (size: int63) (t: t) : t
1811 requires { 1 <= size }
1812 ensures { result.bdd.dom_snodes = t.bdd.dom_snodes }
1813 ensures { forall sn. v result sn = land (lnot (v t sn)) (mask size) }
1814 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1815 =
1816 let maxpos = size - 1 in
1817 let s = Int63.of_int (Zbit.numbits (to_int maxpos)) in
1818 let ghost w = pure { lsl 1 s } in
1819 numbits_lsl_lt (to_int maxpos);
1820 assert { size <= w };
1821 let g = get t s in
1822 let n = PBDD2.dnot g in
1823 let r = mask_bdd s maxpos n in
1824 let lemma eq (sn:PBDD2.env) : unit
1825 ensures { PBDD2.v r s sn = land (lnot (v t sn)) (mask size) }
1826 =
1827 let lemma bit (i:int) : unit
1828 requires { 0 <= i }
1829 ensures { bittest (PBDD2.v r s sn) i <-> bittest (land (lnot (v t sn)) (mask size)) i }
1830 = if i < to_int size then assert { bittest (mask w) i }
1831 in
1832 ext_bittest pure { PBDD2.v r s sn } pure { land (lnot (v t sn)) (mask size) }
1833 in
1834 mk r s
1835
Valid (4.0s) (colibri2 15) (cvc4 5) (split_vc) (depth 1)
1836 let partial monome (sz: int63) (n: Node.t) : t
1837 requires { 0 <= sz }
1838 ensures { result.bdd.dom_snodes = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }
1839 ensures { forall env. value result env = land (mask sz) (env n) }
1840 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1841 =
1842 mask_nonneg (to_int sz);
1843 mask_numbits (to_int sz);
1844 let z = cst (ZbitInt.mask_int (to_int sz)) in
1845 let nd = { SNode.n = n; SNode.s = 0; SNode.scal = False } in
1846 let b = PBDD2.dand z.bdd (PBDD2.bdd_of_snode nd) in
1847 lor_numbits z.bdd.dom_indexes 0;
1848 let lemma eq (env: Node.t -> int) : unit
1849 ensures { PBDD2.v b z.size (sem env) = land (mask sz) (env n) }
1850 =
1851 let lemma bit (p:int) : unit
1852 requires { 0 <= p }
1853 ensures { bittest (PBDD2.v b z.size (sem env)) p <-> bittest (land (mask sz) (env n)) p }
1854 =
1855 assert { bittest (PBDD2.v z.bdd z.size (sem env)) p <-> bittest (mask sz) p };
1856 assert { bittest (mask sz) p -> numbits p <= z.size };
1857 assert { sem env p nd = bittest (env n) p };
1858 assert { bittest (PBDD2.v b z.size (sem env)) p <->
1859 (bittest (PBDD2.v z.bdd z.size (sem env)) p /\
1860 bittest (snode_mask nd z.size (sem env)) p) }
1861 in
1862 ext_bittest pure { PBDD2.v b z.size (sem env) } pure { land (mask sz) (env n) }
1863 in
1864 mk b z.size
1865
Valid (127ms) (cvc4)
1866 let partial logand_cst (z: int) (t: t) : t
1867 requires { 0 <= z }
1868 requires { numbits z <= Int63.max_int }
1869 ensures { result.bdd.dom_snodes = t.bdd.dom_snodes }
1870 ensures { forall sn. v result sn = land z (v t sn) }
1871 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1872 = logand (cst z) t
1873
Valid (116ms) (cvc4)
1874 let partial logor_cst (z: int) (t: t) : t
1875 requires { 0 <= z }
1876 requires { numbits z <= Int63.max_int }
1877 ensures { result.bdd.dom_snodes = t.bdd.dom_snodes }
1878 ensures { forall sn. v result sn = lor z (v t sn) }
1879 ensures { forall sn. not (result.tail.PBDD.v 0 sn) }
1880 = logor (cst z) t
1881
1882end