Common — library colibrilib.ibdd — module IBDD
1
module IBDD

Implemented: the bitwise layer, specified with the integer view

2
use bool.Bool
3
use colibrilib.bdd.Node
4
use colibrilib.bdd.NodeSet
5
use colibrilib.bdd.NodeH
6
use colibrilib.bdd.Key
7
use list.List
8
use list.Mem
9
use option.Option
10
use ref.Ref
11
use colibrilib.sbdd.SNode
12
use colibrilib.bdd.IArray63
13
use int.Int
14
use colibrilib.int63.Int63
15
use set.Set
16
use colibrilib.pbdd.PBDD
17
use colibrilib.pbdd.PBDD2
18
use colibrilib.zarith.Zbit
19
use colibrilib.zbit.ZbitInt
20
use seq.Seq
21
use mach.array.Array63
22
use int.MinMax
23
use int.Power
24
use list.Append as Lists
25
Valid (68ms) (colibri2)
26
let rec lemma
lsl_power
(n:int) : unit
27
requires { 0 <= n }
28
variant { n }
29
ensures { lsl 1 n = power 2 n }
30
= if n > 0 then begin lsl_power (n-1); lsl_succ 1 (n-1) end
31
Valid (7.4s) (colibri2 6) (cvc4 2) (cvc5) (split_vc 3) (depth 2)
32
let lemma
power_2_61
(_:unit) : unit
33
ensures { power 2 61 = 2305843009213693952 }
34
=
35
assert { power 2 2 = 4 };
36
assert { power 2 4 = 16 by power 2 4 = power 2 2 * power 2 2 };
37
assert { power 2 8 = 256 by power 2 8 = power 2 4 * power 2 4 };
38
assert { power 2 16 = 65536 by power 2 16 = power 2 8 * power 2 8 };
39
assert { power 2 32 = 4294967296 by power 2 32 = power 2 16 * power 2 16 };
40
assert { power 2 61 = 2305843009213693952 by
41
power 2 61 = power 2 32 * power 2 16 * power 2 8 * power 2 4 * power 2 1 };
42
()
43
Valid (86ms) (colibri2)
44
let lemma
lsl_le_2_60
(n:int) : unit
45
requires { 0 <= n <= 60 }
46
ensures { lsl 1 n <= 0x1000_0000_0000_0000 }
47
=
48
power_2_61 ();
49
assert { power 2 61 = 2 * power 2 60 };
50
Power_monotonic 2 n 60

The window sizes whose number of positions is an int63

  Valid (75ms) (colibri2)
53
let lemma
lsl_le_max_int
(n:int) : unit
54
requires { 0 <= n }
55
ensures { lsl 1 n <= Int63.max_int <-> n <= 61 }
56
=
57
power_2_61 ();
58
if n <= 61 then Power_monotonic 2 n 61
59
else Power_monotonic 2 62 n

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

63
predicate
reads_at
(p: int) (nd: snode) = nd.SNode.scal \/ 0 <= p + to_int nd.SNode.s

sn1 and sn2 agree on the snodes that read a non–negative bit at p

66
predicate
agree
(p: int) (sn1 sn2: snodes) =
67
forall nd. reads_at p nd -> (Set.mem nd sn1 <-> Set.mem nd sn2)

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)

71
predicate
no_neg
(b: PBDD.t) (s: int) =
72
forall p sn1 sn2. 0 <= p -> numbits p <= s -> agree p sn1 sn2 ->
73
(b.PBDD.v p sn1 <-> b.PBDD.v p sn2)

no_neg on the positions 0..m

76
predicate
no_neg_le
(b: PBDD.t) (m: int) =
77
forall p sn1 sn2. 0 <= p <= m -> agree p sn1 sn2 -> (b.PBDD.v p sn1 <-> b.PBDD.v p sn2)

The window s is minimal: its upper half is not empty

80
predicate
minimal
(b: PBDD.t) (s: int) =
81
s = 0 \/ exists p sn. 0 <= p /\ numbits p = s /\ b.PBDD.v p sn

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

86
predicate
no_neg_tail
(t: PBDD.t) (s: int) =
87
forall sn1 sn2. agree (lsl 1 s) sn1 sn2 -> (t.PBDD.v 0 sn1 <-> t.PBDD.v 0 sn2)

The window s is minimal for the tail t: its upper half is not the tail

90
predicate
minimal_t
(b t: PBDD.t) (s: int) =
91
s = 0 \/ exists p sn. 0 <= p /\ numbits p = s /\ not (b.PBDD.v p sn <-> t.PBDD.v 0 sn)

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)
98
type
ibdd
= {
99
bdd
: PBDD.t;
100
size
: int63;
101
tail
: PBDD.t;
102
} invariant { Zbit.numbits bdd.dom_indexes <= size }
103
invariant { tail.dom_indexes = 0 }
104
invariant { no_neg bdd size }
105
invariant { no_neg_tail tail size }
106
invariant { minimal_t bdd tail size }
107
by { bdd = PBDD.tfalse (); size = 0; tail = PBDD.tfalse () }
108
109
type
t
= ibdd
110
111
function
isize
(t: ibdd) : int63 = t.size
112
function
ibdd_bdd
(t: ibdd) : PBDD.t = t.bdd

The bit p >= 0 of a term, for the snodes sn read at p

115
function
bit
(t: t) (p: int) (sn: snodes) : bool =
116
if numbits p <= t.size then t.bdd.PBDD.v p sn else t.tail.PBDD.v 0 sn

The term has a tail that is not false

119
predicate
tailed
(t: ibdd) = exists sn. t.tail.PBDD.v 0 sn

The snodes in the domain of a term

122
function
all_snodes
(t: ibdd) : snodes = Set.union t.bdd.PBDD.dom_snodes t.tail.PBDD.dom_snodes

A term with a false tail (minimal is minimal_t for it)

  Valid (68ms) (colibri2)
125
let ghost
minimal_false
(b t: PBDD.t) (s: int) : unit
126
requires { minimal b s }
127
requires { forall sn. not (t.PBDD.v 0 sn) }
128
ensures { minimal_t b t s }
129
= ()
130
Valid (58ms) (colibri2)
131
let ghost
no_neg_tail_false
(t: PBDD.t) (s: int) : unit
132
requires { forall sn. not (t.PBDD.v 0 sn) }
133
ensures { no_neg_tail t s }
134
= ()

The value of an IBDD: positions represented with more than size bits are false

138
function
v
(b:t) (sn:PBDD2.env) : int = PBDD2.v b.bdd b.size sn

Valuation of the snodes from a valuation of the nodes: Var {n; shift} at position p is the bit p + shift of n

142
function
sem
(env: Node.t -> int) : PBDD2.env =
143
fun p nd -> if nd.SNode.scal then env nd.SNode.n < 0 else bittest (env nd.SNode.n) (p + nd.SNode.s)
144
Valid (72ms) (colibri2)
145
let ghost
sem_def
(env: Node.t -> int) (p: int) (nd: snode) : unit
146
ensures { sem env p nd <-> if nd.SNode.scal then env nd.SNode.n < 0 else bittest (env nd.SNode.n) (p + nd.SNode.s) }
147
= ()

The value of an IBDD for a valuation of the nodes

150
function
value
(b:t) (env: Node.t -> int) : int = v b (sem env)
151
Valid (80ms) (colibri2)
152
let lemma
numbits_subset
(a b:int) : unit
153
requires { 0 <= a /\ 0 <= b /\ Zbit.subset a b }
154
ensures { numbits a <= numbits b }
155
=
156
if a > 0 && numbits a > numbits b then begin
157
numbits_top_bit a;
158
if b > 0 then numbits_high_clear b (numbits a - 1)
159
end

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

209
predicate
wf_cst
(result:IArray63.t PBDD.t) (s:int) =
210
result.IArray63.length = lsl 1 (lsl 1 s) /\
211
(forall j. 0 <= j < result.IArray63.length -> Zbit.numbits (result j).dom_indexes <= s) /\
212
(forall j. 0 <= j < result.IArray63.length -> (result j).dom_snodes = Set.empty) /\
213
(forall j sn. 0 <= j < result.IArray63.length -> PBDD2.v (result j) s sn = j)
214
Valid (1.7s) (colibri2 85) (cvc4 11) (cvc5 2) (split_vc 7) (depth 2)
215
let partial
mk_cst256
() : IArray63.t (IArray63.t PBDD.t)
216
ensures { result.IArray63.length = 4 }
217
ensures { forall s. 0 <= s < 4 -> wf_cst (result s) s }
218
=
219
let partial aux (s:int63) (arr_prev:IArray63.t PBDD.t) : IArray63.t PBDD.t
220
requires { 1 <= s <= 3 }
221
requires { wf_cst arr_prev (s-1) }
222
ensures { wf_cst result s }
223
=
224
lsl_power (to_int s);
225
Power_monotonic 2 (to_int s) 3;
226
lsl_power pure { lsl 1 s };
227
Power_monotonic 2 pure { lsl 1 s } 8;
228
let half = Int63.lsl 1 (s-1) in
229
lsl_succ 1 (to_int s - 1);
230
assert { lsl 1 s = 2 * half };
231
mask_nonneg (to_int s - 1);
232
mask_nonneg (to_int s);
233
mask_nonneg pure { Zbit.lsl 1 s };
234
let len = Int63.lsl 1 (Int63.lsl 1 s) in
235
let arr = Array63.make len (PBDD.tfalse ()) in
236
for i = 0 to Int63.mask (Int63.lsl 1 s) do
237
invariant { forall j. 0 <= j < i -> Zbit.numbits (arr[j]).dom_indexes <= s }
238
invariant { forall j. 0 <= j < i -> (arr[j]).dom_snodes = Set.empty }
239
invariant { forall j sn. 0 <= j < i -> PBDD2.v (arr[j]) s sn = j }
240
let high = Int63.asr i half in
241
let low = Int63.land i (Int63.mask half) in
242
numbits_lt_lsl pure { i : int } pure { lsl 1 s : int };
243
if i > 0 then asr_numbits pure { i : int } pure { half : int };
244
asr_nonneg pure { i : int } pure { half : int };
245
lt_lsl_of_numbits pure { high : int } pure { half : int };
246
land_nonneg pure { i : int } pure { mask half : int };
247
land_le pure { i : int } pure { mask half : int };
248
split_concat pure { i : int } pure { half : int };
249
let bhi = IArray63.get arr_prev high in
250
let blo = IArray63.get arr_prev low in
251
let r = PBDD2.ite_index (s-1) bhi blo in
252
Zbit.numbits_set (Zbit.lor (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes)) (to_int s - 1);
253
Zbit.lor_numbits (bhi.PBDD.dom_indexes) (blo.PBDD.dom_indexes);
254
assert { forall sn. PBDD2.v bhi (s-1) sn = high };
255
assert { forall sn. PBDD2.v blo (s-1) sn = low };
256
let lemma vr (sn: PBDD2.env) : unit
257
ensures { PBDD2.v r s sn = lor low (lsl high half) }
258
= assert { PBDD2.v r s sn = lor (PBDD2.v blo (s-1) sn)
259
(lsl (PBDD2.v bhi (s-1) (PBDD2.shift_env sn half)) half) };
260
assert { PBDD2.v bhi (s-1) (PBDD2.shift_env sn half) = high } in
261
assert { forall sn. PBDD2.v r s sn = i };
262
assert { Zbit.numbits r.PBDD.dom_indexes <= s };
263
assert { bhi.PBDD.dom_snodes = Set.empty };
264
assert { blo.PBDD.dom_snodes = Set.empty };
265
assert { r.PBDD.dom_snodes = Set.empty };
266
label L in
267
arr[i] <- r;
268
assert { arr[i] = r };
269
assert { forall j. 0 <= j < i -> arr[j] = (arr at L)[j] };
270
assert { forall j. 0 <= j < i + 1 -> Zbit.numbits (arr[j]).dom_indexes <= s
271
by j = i \/ j < i };
272
assert { forall j. 0 <= j < i + 1 -> (arr[j]).dom_snodes = Set.empty
273
by j = i \/ j < i }
274
done;
275
assert { Zbit.mask (Zbit.lsl 1 s) + 1 = len };
276
let res = IArray63.of_array arr in
277
assert { res.IArray63.length = len };
278
assert { forall j. 0 <= j < len -> res j = arr[j] };
279
assert { res.IArray63.length = lsl 1 (lsl 1 s) };
280
assert { forall j. 0 <= j < res.IArray63.length ->
281
Zbit.numbits (res j).dom_indexes <= s };
282
assert { forall j. 0 <= j < res.IArray63.length ->
283
(res j).dom_snodes = Set.empty };
284
assert { forall j sn. 0 <= j < res.IArray63.length ->
285
PBDD2.v (res j) s sn = j };
286
res
287
in
288
let arr0 = Array63.make (2:int63) (PBDD2.tfalse ()) in
289
arr0[0] <- PBDD2.tfalse ();
290
arr0[1] <- PBDD2.ttrue ();
291
assert { lsl 1 0 = 1 };
292
assert { lsl 1 1 = 2 };
293
assert { mask 1 = 1 };
294
let res = Array63.make 4 (IArray63.of_array arr0) in
295
for i = 1 to 3 do
296
invariant { forall s. 0 <= s < i -> wf_cst (res[s]) s }
297
res[i] <- aux i res[i-1];
298
done;
299
IArray63.of_array res

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

459
function
cenv
(sn: snodes) : PBDD2.env = fun _ -> sn
460
Valid (101ms) (colibri2)
461
let lemma
bit_cenv
(x: PBDD.t) (s p: int) (sn: snodes) : unit
462
requires { 0 <= p /\ numbits p <= s }
463
ensures { bittest (PBDD2.v x s (cenv sn)) p <-> x.PBDD.v p sn }
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

800
predicate
no_scal
(b: PBDD.t) = forall nd. Set.mem nd (support_snodes b) -> not nd.SNode.scal

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

895
function
clear_neg
(p: int) (sn: snodes) : snodes = fun nd -> reads_at p nd /\ Set.mem nd sn

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

918
predicate
scal0
(b: PBDD.t) =
919
forall nd. Set.mem nd (support_snodes b) -> nd.SNode.scal -> nd.SNode.s = 0

The bits below b of the valuation realizing sn at the position p

922
function
rbits
(p: int) (sn: snodes) (b: int) (n: Node.t) : int =
923
of_bits (fun i -> exists nd. nd.SNode.n = n /\ not nd.SNode.scal /\ to_int nd.SNode.s = i - p /\ Set.mem nd sn) b

The sign of the node n in sn

926
predicate
rsign
(sn: snodes) (n: Node.t) =
927
exists nd. nd.SNode.n = n /\ nd.SNode.scal /\ nd.SNode.s = 0 /\ Set.mem nd sn

The valuation of the nodes that realizes sn at the position p: the bits below b, then the sign

931
function
realize
(p: int) (sn: snodes) (b: int) : Node.t -> int =
932
fun n -> if rsign sn n then rbits p sn b n - lsl 1 b else rbits p sn b n
933
Valid (68ms) (colibri2)
934
let ghost
realize_bit
(p: int) (sn: snodes) (b: int) (n: Node.t) (i: int) : unit
935
requires { 0 <= i < b }
936
ensures { bittest (realize p sn b n) i <-> bittest (rbits p sn b n) i }
937
= if pure { rsign sn n } then bittest_sub_lsl pure { rbits p sn b n } b i
938
Valid (378ms) (cvc4)
939
let ghost
realize_sign
(p: int) (sn: snodes) (b: int) (n: Node.t) : unit
940
requires { 0 <= b }
941
ensures { realize p sn b n < 0 <-> rsign sn n }
942
=
943
let x = pure { rbits p sn b n } in
944
if x > 0 then begin
945
numbits_top_bit x;
946
assert { numbits x <= b };
947
lt_lsl_of_numbits x b
948
end
949
Valid (1.8s) (colibri2 9) (cvc5) (split_vc 3) (depth 3)
950
let lemma
realize_sem
(p: int) (sn: snodes) (l: list snode) (nd: snode) : unit
951
requires { Mem.mem nd l /\ reads_at p nd /\ (nd.SNode.scal -> nd.SNode.s = 0) }
952
ensures { sem (realize p sn (bound p l)) p nd <-> Set.mem nd sn }
953
=
954
if nd.SNode.scal then begin
955
realize_sign p sn (bound p l) nd.SNode.n;
956
let lemma uniq (nd': snode) : unit
957
requires { nd'.SNode.n = nd.SNode.n /\ nd'.SNode.scal /\ nd'.SNode.s = 0 }
958
ensures { nd' = nd }
959
= assert { nd'.SNode.s = nd.SNode.s }
960
in ()
961
end else begin
962
let ghost i = p + to_int nd.SNode.s in
963
realize_bit p sn (bound p l) nd.SNode.n i;
964
let lemma uniq (nd': snode) : unit
965
requires { nd'.SNode.n = nd.SNode.n /\ not nd'.SNode.scal /\ to_int nd'.SNode.s = i - p }
966
ensures { nd' = nd }
967
= assert { nd'.SNode.s = nd.SNode.s }
968
in
969
assert { sem (realize p sn (bound p l)) p nd <->
970
bittest (realize p sn (bound p l) nd.SNode.n) i }
971
end

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

1204
function
pbit
(b tl: PBDD.t) (s: int) (p: int) (sn: snodes) : bool =
1205
if numbits p <= s then b.PBDD.v p sn else tl.PBDD.v 0 sn

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)

1510
predicate
is_value
(t: t) (env: Node.t -> int) (z: int) =
1511
forall p. 0 <= p -> (bittest z p <-> bit t p (sem env p))
1512
Valid (355ms) (colibri2 12) (split_vc) (depth 1)
1513
let ghost
value_exists
(t: t) (env: Node.t -> int) : int
1514
ensures { is_value t env result }
1515
=
1516
let l = snodes_of (PBDD.vars t.tail) in
1517
assert { forall nd. Set.mem nd (support_snodes t.tail) -> Mem.mem nd l };
1518
let n = pure { lsl 1 t.size } + stab_bound env l in
1519
mask_nonneg (to_int t.size);
1520
of_bits_lt pure { fun q -> bit t q (sem env q) } n;
1521
let z = pure { of_bits (fun q -> bit t q (sem env q)) n
1522
- (if bit t n (sem env n) then lsl 1 n else 0) } in
1523
let lemma bitz (p: int) : unit
1524
requires { 0 <= p }
1525
ensures { bittest z p <-> bit t p (sem env p) }
1526
=
1527
if p >= n then stream_stable t env l p;
1528
if pure { bit t n (sem env n) } then begin
1529
if p < n then bittest_sub_lsl (pure { of_bits (fun q -> bit t q (sem env q)) n }) n p
1530
else bittest_sub_lsl_high (pure { of_bits (fun q -> bit t q (sem env q)) n }) n p
1531
end
1532
in
1533
assert { is_value t env z };
1534
z

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

1543
function
sem_inf
(env: Node.t -> int) : snodes = fun nd -> env nd.SNode.n < 0

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