Common — library colibrilib.bddbitv — module Export
5195
module Export

Implemented

5196
use colibrilib.spec.Eval
5197
use colibrilib.spec.Sound
5198
use colibrilib.spec.Value
5199
use colibrilib.spec.Test
5200
use int.Int
5201
use colibrilib.bdd.NodeSet
5202
use int.EuclideanDivision as E
5203
use int.ComputerDivision as C
5204
use colibrilib.int63.Int63
5205
use option.Option
5206
use set.Set
5207
use colibrilib.bdd.Node
5208
use colibrilib.sbdd.SNode
5209
use colibrilib.pbdd.PBDD
5210
use colibrilib.pbdd.PBDD2
5211
use colibrilib.zarith.Zbit
5212
use colibrilib.zbit.ZbitInt
5213
use colibrilib.ibdd.IBDD
5214
use IBDDS
5215
use Modulo
5216
use list.List
5217
use list.Mem
5218
5219
exception
Unsupported

Vocabulary of the specifications

The aliases below are the definitions of colibrilib/ibdd.mlw and colibrilib/bddbitv.mlw: go to their definition to stay in this module. The integers are the infinite integers of Why3, with two's complement bits: the functions Zbit.land, Zbit.lor, Zbit.lxor, Zbit.lnot, Zbit.lsl, Zbit.asr, Zbit.mask and the predicate bittest are the bitwise operations of the (mathematical) integers, Zbit.numbits x is the number of bits of |x|.

A term (an ibdd): the bits of a window of 2^size positions and a tail giving the bits above. Its bit p is a function of the snodes read at p.

The snode {n; s} read at the position p is the bit p + s of the integer env n (false below 0): sem env p is the valuation of the snodes at p for the values env of the nodes.

5238
function
sem
(env: Node.t -> int) : PBDD2.env = IBDD.sem env

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

5241
function
bit
(t: t) (p: int) (sn: snodes) : bool = IBDD.bit t p sn

The value of a term without tail (a bounded bit–vector, non–negative) for the values env of the nodes: its bit p is bit t p (sem env p)

5245
function
value
(t: t) (env: Node.t -> int) : int = IBDD.value t env

z is the (possibly negative) integer whose bits are the bits of t, for the values env of the nodes

5249
predicate
is_value
(t: t) (env: Node.t -> int) (z: int) = IBDD.is_value t env z

The value of a term for the values env of the nodes. It exists and is unique (is_value_iff): two integers with the same bits are equal

  Valid (41ms) (colibri2) (split_vc) (depth 1)
5253
let ghost function
ivalue
(t: t) (env: Node.t -> int) : int
5254
ensures { is_value t env result } =
5255
IBDD.value_exists t env
5256
Valid (67ms) (colibri2 2) (split_vc) (depth 1)
5257
let lemma
is_value_iff
(t: t) (env: Node.t -> int) (z: int) : unit
5258
ensures { is_value t env z <-> z = ivalue t env }
5259
= if pure { is_value t env z } then Zbit.ext_bittest z (ivalue t env)

SMT–LIB extract and update on integers (total)

5262
function
iextract
(x pos len: int) : int =
5263
if len <= 0 then 0 else Zbit.land (Zbit.asr x pos) (Zbit.mask len)
5264
function
iupdate
(dst pos len src: int) : int =
5265
if len <= 0 then dst
5266
else Zbit.lor (Zbit.land dst (Zbit.lnot (Zbit.lsl (Zbit.mask len) pos)))
5267
(Zbit.lsl (Zbit.land src (Zbit.mask len)) pos)
5268
Valid (888ms) (colibri2)
5269
let lemma
bittest_iextract
(x pos len i: int) : unit
5270
requires { 0 <= i }
5271
ensures { Zbit.bittest (iextract x pos len) i <-> (i < len /\ Zbit.bittest x (pos + i)) }
5272
= if len > 0 then begin
5273
if i < len then Zbit.mask_bits len i else Zbit.mask_bits_high len i
5274
end
5275
Valid (3.4s) (colibri2 12) (cvc5) (split_vc 7) (depth 5)
5276
let lemma
bittest_iupdate
(dst pos len src i: int) : unit
5277
requires { 0 <= i }
5278
ensures { Zbit.bittest (iupdate dst pos len src) i <->
5279
(if pos <= i < pos + len then Zbit.bittest src (i - pos) else Zbit.bittest dst i) }
5280
= if len > 0 then begin
5281
Zbit.mask_nonneg len;
5282
if i >= pos then begin
5283
if i - pos < len then Zbit.mask_bits len (i - pos) else Zbit.mask_bits_high len (i - pos)
5284
end
5285
end

The term has a tail that is not false (it is not a bounded bit–vector)

5288
predicate
tailed
(t: t) = IBDD.tailed t

The snodes ({n; s}) in the window or in the tail of a term

5291
function
all_snodes
(t: t) : snodes = IBDD.all_snodes t

The snodes in the domain of the window, and the snodes on which the window really depends

5295
function
dom_snodes
(t: t) : snodes = t.bdd.PBDD.dom_snodes
5296
function
support
(t: t) : snodes = PBDD.support_snodes t.bdd

Stable name for the extracted type

5299
type
solve_result
= IBDDS.solve
5300
type
int_solve_result
= IBDDS.isolve
5301
Valid (186ms) (colibri2)
5302
let partial
bv_cst
(x:int) : t
5303
ensures { dom_snodes result = Set.empty }
5304
ensures { denotes0 value (fun _ -> x) result }
5305
ensures { not (tailed result) }
5306
raises { Unsupported -> x < 0 \/ Zbit.numbits x > Int63.max_int }
5307
= if 0 <= x && Zbit.numbits x <= to_int Int63.max_int then IBDD.cst x
5308
else raise Unsupported
5309
Valid (110ms) (colibri2)
5310
let
bv_is_cst
(x: t) : option int
5311
ensures { denotes_cst value x result }
5312
ensures { match result with
5313
| Some z -> forall env. value x env = z
5314
| None -> not (Set.is_empty (support x))
5315
end }
5316
raises { Unsupported -> x.size > 61 \/ tailed x }
5317
= if IBDD.has_tail x then raise Unsupported
5318
else if x.size <= 61 then begin
5319
lsl_le_max_int (to_int x.size);
5320
IBDD.is_cst x
5321
end else raise Unsupported
5322
Valid (468ms) (colibri2 10) (split_vc) (depth 1)
5323
let partial
bv_lognot
(size: int63) (t: t) : t
5324
ensures { dom_snodes result = dom_snodes t \/ size = 0 }
5325
ensures { denotes1 value (fun x -> Zbit.land (Zbit.lnot x) (Zbit.mask size)) t result }
5326
ensures { not (tailed result) }
5327
raises { Unsupported -> size < 0 \/ tailed t }
5328
= if size < 0 || IBDD.has_tail t then raise Unsupported
5329
else if size = 0 then begin
5330
let r = IBDD.zero () in
5331
let lemma eq (env: Node.t -> int) : unit
5332
ensures { value r env = Zbit.land (Zbit.lnot (value t env)) (Zbit.mask size) }
5333
= ext_bittest (value r env) pure { land (lnot (value t env)) (mask size) }
5334
in
5335
r
5336
end else IBDD.lognot size t
5337
Valid (218ms) (colibri2)
5338
let partial
bv_monome
(sz: int63) (n: Node.t) : t
5339
ensures { dom_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }
5340
ensures { denotes0 value (fun env -> Zbit.land (Zbit.mask sz) (env n)) result }
5341
ensures { not (tailed result) }
5342
raises { Unsupported -> sz < 0 }
5343
= if sz < 0 then raise Unsupported else IBDD.monome sz n
5344
Valid (112ms) (colibri2 12) (split_vc) (depth 1)
5345
let partial
bv_shift_left
(off: int) (sz: int63) (t: t) : t
5346
ensures { denotes1 value (fun x -> Zbit.land (Zbit.lsl x off) (Zbit.mask sz)) t result }
5347
ensures { not (tailed result) }
5348
raises { Unsupported -> off < 0 \/ sz < 0 \/ tailed t }
5349
raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }
5350
= if off < 0 || sz < 0 || IBDD.has_tail t then raise Unsupported
5351
else if off >= to_int sz then begin
5352
let r = IBDD.zero () in
5353
let lemma eq (env: Node.t -> int) : unit
5354
ensures { value r env = Zbit.land (Zbit.lsl (value t env) off) (Zbit.mask sz) }
5355
=
5356
let lemma bit (p: int) : unit
5357
requires { 0 <= p }
5358
ensures { not (bittest (Zbit.land (Zbit.lsl (value t env) off) (Zbit.mask sz)) p) }
5359
= if p < to_int sz then def_asr (value t env) (- off) p
5360
in
5361
ext_bittest (value r env) pure { land (lsl (value t env) off) (mask sz) }
5362
in
5363
r
5364
end else IBDDS.shift_left (Int63.of_int off) sz t
5365
Valid (812ms) (colibri2 14) (split_vc) (depth 1)
5366
let partial
bv_shift_right
(off: int) (sz: int63) (t: t) : t
5367
ensures { denotes1 value (fun x -> Zbit.asr (Zbit.land x (Zbit.mask sz)) off) t result }
5368
ensures { not (tailed result) }
5369
raises { Unsupported -> off < 0 \/ sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }
5370
raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }
5371
= if off < 0 || sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported
5372
else if off >= to_int sz then begin
5373
let r = IBDD.zero () in
5374
let lemma eq (env: Node.t -> int) : unit
5375
ensures { value r env = Zbit.asr (Zbit.land (value t env) (Zbit.mask sz)) off }
5376
=
5377
let lemma bit (p: int) : unit
5378
requires { 0 <= p }
5379
ensures { not (bittest (Zbit.asr (Zbit.land (value t env) (Zbit.mask sz)) off) p) }
5380
= def_asr pure { land (value t env) (mask sz) } off p
5381
in
5382
ext_bittest (value r env) pure { asr (land (value t env) (mask sz)) off }
5383
in
5384
r
5385
end else IBDDS.shift_right (Int63.of_int off) sz t
5386
Valid (374ms) (colibri2 17) (cvc4) (cvc5) (split_vc) (depth 1)
5387
let partial
bv_arith_shift_right
(off: int) (sz: int63) (t: t) : t
5388
ensures { denotes1 value (fun x -> Zbit.land (Zbit.asr (sext sz x) off) (Zbit.mask sz)) t result }
5389
ensures { not (tailed result) }
5390
raises { Unsupported -> off < 0 \/ sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }
5391
raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ 0 <= k <= off /\
5392
not (in_bounds (to_int nd.s + k)) }
5393
= if off < 0 || sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported
5394
else if sz = 0 then begin
5395
let r = IBDD.zero () in
5396
let lemma eq (env: Node.t -> int) : unit
5397
ensures { value r env = Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz) }
5398
= ext_bittest (value r env) pure { land (asr (sext sz (value t env)) off) (mask sz) }
5399
in
5400
r
5401
end else begin
5402
let off' = if off >= to_int sz then sz else Int63.of_int off in
5403
let r = IBDDS.arith_shift_right off' sz t in
5404
let lemma eq (env: Node.t -> int) : unit
5405
ensures { value r env = Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz) }
5406
=
5407
let lemma bit (p: int) : unit
5408
requires { 0 <= p }
5409
ensures { bittest (Zbit.land (Zbit.asr (sext sz (value t env)) off') (Zbit.mask sz)) p <->
5410
bittest (Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz)) p }
5411
=
5412
def_asr pure { sext sz (value t env) } (to_int off') p;
5413
def_asr pure { sext sz (value t env) } off p;
5414
sext_bit (to_int sz) (value t env) (p + to_int off');
5415
sext_bit (to_int sz) (value t env) (p + off)
5416
in
5417
ext_bittest pure { land (asr (sext sz (value t env)) off') (mask sz) }
5418
pure { land (asr (sext sz (value t env)) off) (mask sz) }
5419
in
5420
r
5421
end
5422
Valid (729ms) (colibri2 11) (split_vc) (depth 1)
5423
let partial
bv_sign_extend
(from sz: int63) (t: t) : t
5424
ensures { denotes1 value (fun x -> Zbit.land (sext from x) (Zbit.mask sz)) t result }
5425
ensures { not (tailed result) }
5426
raises { Unsupported -> from < 0 \/ sz < from \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }
5427
raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ from - sz <= k < 0 /\
5428
not (in_bounds (to_int nd.s + k)) }
5429
= if from < 0 || sz < from || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported
5430
else if from = 0 then begin
5431
let r = IBDD.zero () in
5432
let lemma eq (env: Node.t -> int) : unit
5433
ensures { value r env = Zbit.land (sext from (value t env)) (Zbit.mask sz) }
5434
= ext_bittest (value r env) pure { land (sext from (value t env)) (mask sz) }
5435
in
5436
r
5437
end else IBDDS.sign_extend from sz t
5438
Valid (372ms) (colibri2 12) (split_vc) (depth 1)
5439
let partial
bv_rotate_right
(off sz: int63) (t: t) : t
5440
ensures { denotes1 value (fun x -> rotr sz (E.mod off sz) x) t result }
5441
ensures { not (tailed result) }
5442
raises { Unsupported -> sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }
5443
raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ - sz <= k <= sz /\
5444
not (in_bounds (to_int nd.s - k)) }
5445
= if sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported
5446
else if sz = 0 then begin
5447
let r = IBDD.zero () in
5448
let lemma eq (env: Node.t -> int) : unit
5449
ensures { value r env = rotr sz (E.mod off sz) (value t env) }
5450
= ext_bittest (value r env) pure { rotr sz (E.mod off sz) (value t env) }
5451
in
5452
r
5453
end else IBDDS.rotate_right (bv_modulo off sz) sz t
5454
Valid (709ms) (colibri2 18) (cvc5 3) (split_vc) (depth 1)
5455
let partial
bv_rotate_left
(off sz: int63) (t: t) : t
5456
ensures { denotes1 value (fun x -> rotr sz (E.mod (- to_int off) sz) x) t result }
5457
ensures { not (tailed result) }
5458
raises { Unsupported -> sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }
5459
raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ - sz <= k <= sz /\
5460
not (in_bounds (to_int nd.s - k)) }
5461
= if sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported
5462
else if sz = 0 then begin
5463
let r = IBDD.zero () in
5464
let lemma eq (env: Node.t -> int) : unit
5465
ensures { value r env = rotr sz (E.mod (- to_int off) sz) (value t env) }
5466
= ext_bittest (value r env) pure { rotr sz (E.mod (- to_int off) sz) (value t env) }
5467
in
5468
r
5469
end else begin
5470
let o = bv_modulo off sz in
5471
let ghost o' = if o = 0 then 0 else to_int sz - to_int o in
5472
let ghost d = E.div (to_int off) (to_int sz) in
5473
assert { to_int off = d * sz + o };
5474
if o = 0 then begin
5475
assert { (- d) * sz <= - to_int off < (- d) * sz + sz };
5476
assert { E.div (- to_int off) sz = - d };
5477
assert { - to_int off = sz * (- d) + E.mod (- to_int off) sz }
5478
end else begin
5479
assert { (- d - 1) * sz <= - to_int off < (- d - 1) * sz + sz };
5480
assert { E.div (- to_int off) sz = - d - 1 };
5481
assert { - to_int off = sz * (- d - 1) + E.mod (- to_int off) sz }
5482
end;
5483
assert { E.mod (- to_int off) sz = o' };
5484
IBDDS.rotate_left o sz t
5485
end
5486
Valid (331ms) (cvc4)
5487
let partial
bv_extract
(i j: int63) (t: t) : t
5488
ensures { denotes1 value
5489
(fun x -> if j < i then 0 else Zbit.land (Zbit.asr x i) (Zbit.mask (j - i + 1)))
5490
t result }
5491
ensures { not (tailed result) }
5492
raises { Unsupported -> i < 0 \/ tailed t \/ (i <= j /\ (j = Int63.max_int \/ t.size > 61 \/
5493
Zbit.lsl 1 t.size + to_int i > Int63.max_int)) }
5494
raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + i)) }
5495
= if i < 0 || IBDD.has_tail t then raise Unsupported
5496
else if j < i then begin
5497
let r = IBDD.zero () in
5498
let lemma eq (env: Node.t -> int) : unit
5499
ensures { value r env = 0 }
5500
= ext_bittest (value r env) 0
5501
in
5502
r
5503
end else if j = Int63.max_int || t.size > 61 then raise Unsupported
5504
else begin
5505
lsl_le_max_int (to_int t.size);
5506
if Int63.lsl 1 t.size > Int63.max_int - i then raise Unsupported;
5507
IBDDS.extract i j t
5508
end
5509
Valid (70ms) (cvc5)
5510
let lemma
mul_le
(x y z: int) : unit
5511
requires { x <= y /\ 0 <= z }
5512
ensures { x * z <= y * z }
5513
= ()
5514
Valid (839ms) (colibri2 14) (cvc4) (cvc5) (split_vc) (depth 1)
5515
let partial
bv_repeat
[@spec:none "bit level: the bit p is the bit p - k * from of t, k < n"] (from n: int63) (t: t) : t
5516
ensures { forall env p. bittest (value result env) p <->
5517
exists k. 0 <= k < n /\ k * from <= p < k * from + from /\
5518
bittest (value t env) (p - k * from) }
5519
raises { Unsupported -> from < 0 \/ n < 0 \/ tailed t \/
5520
to_int from * to_int n + to_int from * to_int n > Int63.max_int }
5521
raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ 0 < k < from * n /\
5522
not (in_bounds (to_int nd.s - k)) }
5523
= if from < 0 || n < 0 || IBDD.has_tail t then raise Unsupported
5524
else if from = 0 || n = 0 then begin
5525
let r = IBDD.zero () in
5526
let lemma bit (env: Node.t -> int) (p: int) : unit
5527
ensures { not (bittest (value r env) p) }
5528
= ext_bittest (value r env) 0
5529
in
5530
r
5531
end else begin
5532
let m = Int63.max_int / 2 in
5533
let q = m / n in
5534
assert { to_int m = to_int q * n + C.mod (to_int m) (to_int n) /\
5535
0 <= C.mod (to_int m) (to_int n) < n };
5536
if from > q then begin
5537
assert { (to_int from - to_int q - 1) * n >= 0 };
5538
raise Unsupported
5539
end;
5540
mul_le (to_int from) (to_int q) (to_int n);
5541
IBDDS.repeat from n t
5542
end
5543
Valid (86ms) (colibri2)
5544
let
bv_compute
(env: Node.t -> int) (t: t) : int
5545
ensures { denotes_at value t env result }
5546
raises { Unsupported -> t.size > 61 \/ tailed t }
5547
= if t.size > 61 || IBDD.has_tail t then raise Unsupported;
5548
lsl_le_max_int (to_int t.size);
5549
IBDDS.compute env t

The known bits (known0, known1) hold v: the bits of known1 are set in v, the bits of v are in known0

5553
predicate
kb_mem
(v: int) (k: (int, int)) =
5554
let (k0, k1) = k in Zbit.subset k1 v /\ Zbit.subset v k0
5555
Valid (94ms) (colibri2)
5556
let partial
bv_to_knownbits
(t: t) : (int, int)
5557
ensures { denotes_in value kb_mem t result }
5558
raises { Unsupported -> t.size > 61 \/ tailed t }
5559
= if t.size > 61 || IBDD.has_tail t then raise Unsupported;
5560
lsl_le_max_int (to_int t.size);
5561
IBDDS.to_knownbits t

The functions without precondition

  Valid (104ms) (colibri2)
5564
let
bv_zero
() : t
5565
ensures { denotes0 value (fun _ -> 0) result }
5566
= IBDD.zero ()
5567
Valid (71ms) (colibri2)
5568
let
bv_is_zero
(t: t) : bool
5569
ensures { decides (forall p sn. 0 <= p -> not (bit t p sn)) result }
5570
= IBDD.is_zero_t t
5571
5572
let function
bv_size
(t: t) : int63 = t.size
5573
Valid (80ms) (colibri2) (split_vc) (depth 1)
5574
let
bv_nodes
(t: t) : NodeSet.t
5575
ensures { exact (fun n (r: NodeSet.t) -> Set.mem n r.NodeSet.elts) (fun n -> exists s a. Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (support t) \/
5576
Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (support_snodes t.tail)) result }
5577
= IBDD.nodes t
5578
Valid (964ms) (colibri2)
5579
let partial
bv_logand
(t1 t2: t) : t
5580
ensures { denotes2 value Zbit.land t1 t2 result }
5581
ensures { not (tailed result) }
5582
raises { Unsupported -> tailed t1 \/ tailed t2 }
5583
= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported
5584
else IBDD.logand t1 t2
5585
Valid (983ms) (colibri2)
5586
let partial
bv_logor
(t1 t2: t) : t
5587
ensures { denotes2 value Zbit.lor t1 t2 result }
5588
ensures { not (tailed result) }
5589
raises { Unsupported -> tailed t1 \/ tailed t2 }
5590
= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported
5591
else IBDD.logor t1 t2
5592
Valid (1.0s) (colibri2)
5593
let partial
bv_xor
(t1 t2: t) : t
5594
ensures { denotes2 value Zbit.lxor t1 t2 result }
5595
ensures { not (tailed result) }
5596
raises { Unsupported -> tailed t1 \/ tailed t2 }
5597
= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported
5598
else IBDD.xor t1 t2
5599
Valid (68ms) (colibri2 3) (split_vc) (depth 1)
5600
let partial
bv_solve
[@spec:none "solver: Zero, Unsat, Subst n q r (t = 0 iff r = 0 and n = q) or TryLater"] (sizes: Node.t -> int63) (t: t) : IBDDS.solve
5601
ensures { match result with
5602
| Zero -> forall env. value t env = 0
5603
| Unsat -> forall env. value t env <> 0
5604
| Subst n q r ->
5605
(forall env x. value r (upd_env env n x) = value r env) /\
5606
(forall env. value r env = 0 -> value t (upd_env env n (value q env)) = 0) /\
5607
(forall env. value t env = 0 ->
5608
value r env = 0 /\ (0 <= env n < Zbit.lsl 1 (sizes n) -> value q env = env n))
5609
| TryLater -> IBDDS.solve_later sizes t
5610
end }
5611
raises { Overflow -> (exists nd nd'. Set.mem nd (support t) /\
5612
Set.mem nd' (Set.add nd (dom_snodes t)) /\ not nd'.scal /\ not (in_bounds (to_int nd'.s - nd.s))) \/
5613
(exists nd. Set.mem nd (support t) /\ not (in_bounds (Zbit.lsl 1 t.size - 1 + nd.s))) }
5614
raises { Unsupported -> tailed t }
5615
= (* [TryLater] (no claim: sizes outside of the bounds, overflow of a shift, term too big...) is returned: the caller treats it as unsolved *)
5617
if IBDD.has_tail t then raise Unsupported;
5618
IBDDS.solve sizes t
5619
Valid (283ms) (colibri2)
5620
let partial
bv_logand_cst
(z: int) (t: t) : t
5621
ensures { dom_snodes result = dom_snodes t }
5622
ensures { denotes1 value (fun x -> Zbit.land z x) t result }
5623
ensures { not (tailed result) }
5624
raises { Unsupported -> z < 0 \/ Zbit.numbits z > Int63.max_int }
5625
= if 0 <= z && Zbit.numbits z <= to_int Int63.max_int then IBDD.logand_cst z t
5626
else raise Unsupported
5627
Valid (938ms) (colibri2)
5628
let partial
bv_logor_cst
(z: int) (t: t) : t
5629
ensures { dom_snodes result = dom_snodes t }
5630
ensures { denotes1 value (fun x -> Zbit.lor z x) t result }
5631
ensures { not (tailed result) }
5632
raises { Unsupported -> z < 0 \/ Zbit.numbits z > Int63.max_int }
5633
= if 0 <= z && Zbit.numbits z <= to_int Int63.max_int then IBDD.logor_cst z t
5634
else raise Unsupported

Integers (negative values, unbounded variables)

  Valid (79ms) (colibri2 8) (split_vc) (depth 1)
5638
let partial
int_cst
(x: int) : t
5639
ensures { all_snodes result = Set.empty }
5640
ensures { denotes0 ivalue (fun _ -> x) result }
5641
ensures { to_int result.size <= numbits (numbits (iabs x)) }
5642
ensures { forall p sn. 0 <= p -> (bit result p sn <-> bittest x p) }
5643
raises { Unsupported -> Zbit.numbits (iabs x) > Int63.max_int }
5644
= if Zbit.numbits (if x < 0 then - x else x) <= to_int Int63.max_int then begin
5645
let r = IBDD.cst_z x in
5646
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = x } = is_value_iff r env x in
5647
r
5648
end else raise Unsupported
5649
Valid (893ms) (colibri2 4) (split_vc) (depth 1)
5650
let partial
int_monome
(n: Node.t) : t
5651
ensures { denotes0 ivalue (fun env -> env n) result }
5652
ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }
5653
ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = False }) }
5654
= let r = IBDD.umonome n in
5655
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = env n } = is_value_iff r env (env n) in
5656
r

The sign of the node n: -1 if n < 0, else 0

  Valid (50ms) (colibri2 9) (split_vc 2) (depth 2)
5659
let partial
int_scalar
(n: Node.t) : t
5660
ensures { denotes0 ivalue (fun env -> if env n < 0 then -1 else 0) result }
5661
ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = True } }
5662
ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = True }) }
5663
= let r = IBDD.uscalar n in
5664
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = if env n < 0 then -1 else 0 }
5665
= let z = if env n < 0 then -1 else 0 in
5666
let lemma bp (p: int) : unit
5667
requires { 0 <= p }
5668
ensures { bittest z p <-> bit r p (sem env p) }
5669
= IBDD.sem_def env p { SNode.n = n; SNode.s = (0:int63); SNode.scal = True };
5670
assert { Zbit.lsl 1 0 = 1 };
5671
assert { bittest (0 - Zbit.lsl 1 0) p };
5672
assert { bittest (-1) p /\ not (bittest 0 p) } in
5673
is_value_iff r env z in
5674
r

The sign of the term when it does not depend on the nodes

  Valid (1.6s) (colibri2 8) (split_vc 2) (depth 2)
5677
let partial
int_sign
(t: t) : option bool
5678
ensures { denotes_cst (fun t env -> ivalue t env < 0) t result }
5679
ensures { match result with
5680
| Some b -> forall env. ivalue t env < 0 <-> b
5681
| None -> exists sn1 sn2. not (t.tail.PBDD.v 0 (fun nd -> sn1 (IBDDS.scal_of nd.SNode.n)) <->
5682
t.tail.PBDD.v 0 (fun nd -> sn2 (IBDDS.scal_of nd.SNode.n)))
5683
end }
5684
= let g = IBDDS.sign_bdd t in
5685
let lemma sg (env: Node.t -> int) : unit
5686
ensures { ivalue t env < 0 <-> g.PBDD.v 0 (sem env 0) }
5687
= IBDD.value_sign t env (ivalue t env)
5688
in
5689
let (f, ghost _, ghost sf) = PBDD.is_equal g (PBDD.tfalse ()) in
5690
if f then Some false
5691
else begin
5692
let (tr, ghost _, ghost st) = PBDD.is_equal g (PBDD.ttrue ()) in
5693
if tr then Some true
5694
else begin
5695
tail_v g 0 sf; tail_v g 0 st;
5696
assert { g.PBDD.v 0 sf /\ not (g.PBDD.v 0 st) };
5697
None
5698
end
5699
end
5700
Valid (476ms) (colibri2 4) (split_vc) (depth 1)
5701
let partial
int_lognot
(t: t) : t
5702
ensures { denotes1 ivalue Zbit.lnot t result }
5703
ensures { all_snodes result = all_snodes t }
5704
ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t p sn)) }
5705
= let r = IBDD.lognot_i t in
5706
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.lnot (ivalue t env) }
5707
= is_value_iff r env (Zbit.lnot (ivalue t env)) in
5708
r
5709
Valid (627ms) (colibri2 5) (split_vc) (depth 1)
5710
let partial
int_logand
(t1 t2: t) : t
5711
ensures { denotes2 ivalue Zbit.land t1 t2 result }
5712
ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
5713
ensures { to_int result.size <= to_int t1.size \/ to_int result.size <= to_int t2.size }
5714
ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn /\ bit t2 p sn) }
5715
= let r = IBDD.logand_i t1 t2 in
5716
let lemma lv (env: Node.t -> int) : unit
5717
ensures { ivalue r env = Zbit.land (ivalue t1 env) (ivalue t2 env) }
5718
= is_value_iff r env (Zbit.land (ivalue t1 env) (ivalue t2 env)) in
5719
r
5720
Valid (582ms) (colibri2 4) (split_vc) (depth 1)
5721
let partial
int_logor
(t1 t2: t) : t
5722
ensures { denotes2 ivalue Zbit.lor t1 t2 result }
5723
ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
5724
ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn \/ bit t2 p sn) }
5725
= let r = IBDD.logor_i t1 t2 in
5726
let lemma lv (env: Node.t -> int) : unit
5727
ensures { ivalue r env = Zbit.lor (ivalue t1 env) (ivalue t2 env) }
5728
= is_value_iff r env (Zbit.lor (ivalue t1 env) (ivalue t2 env)) in
5729
r
5730
Valid (713ms) (colibri2 4) (split_vc) (depth 1)
5731
let partial
int_xor
(t1 t2: t) : t
5732
ensures { denotes2 ivalue Zbit.lxor t1 t2 result }
5733
ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }
5734
ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t1 p sn <-> bit t2 p sn)) }
5735
= let r = IBDD.xor_i t1 t2 in
5736
let lemma lv (env: Node.t -> int) : unit
5737
ensures { ivalue r env = Zbit.lxor (ivalue t1 env) (ivalue t2 env) }
5738
= is_value_iff r env (Zbit.lxor (ivalue t1 env) (ivalue t2 env)) in
5739
r
5740
Valid (927ms) (colibri2 9) (cvc4) (split_vc 3) (depth 3)
5741
let partial
int_shift_left
(off: int) (t: t) : t
5742
ensures { denotes1 ivalue (fun x -> Zbit.lsl x off) t result }
5743
ensures { forall env p. 0 <= p ->
5744
(bit result p (sem env p) <-> (off <= p /\ bit t (p - off) (sem env (p - off)))) }
5745
raises { Unsupported -> off < 0 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }
5746
raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }
5747
= if off < 0 || off > 0x1000_0000_0000_0000 || t.size > 60 then raise Unsupported
5748
else begin
5749
let r = IBDDS.shift_i (Int63.of_int off) t in
5750
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.lsl (ivalue t env) off }
5751
= is_value_iff r env (Zbit.lsl (ivalue t env) off) in
5752
r
5753
end
5754
Valid (1.1s) (colibri2 11) (split_vc 3) (depth 3)
5755
let partial
int_shift_right
(off: int) (t: t) : t
5756
ensures { denotes1 ivalue (fun x -> Zbit.asr x off) t result }
5757
ensures { forall env p. 0 <= p ->
5758
(bit result p (sem env p) <-> bit t (p + off) (sem env (p + off))) }
5759
raises { Unsupported -> off < 0 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }
5760
raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }
5761
= if off < 0 || off > 0x1000_0000_0000_0000 || t.size > 60 then raise Unsupported
5762
else begin
5763
let r = IBDDS.shift_i (- (Int63.of_int off)) t in
5764
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.asr (ivalue t env) off }
5765
= is_value_iff r env (Zbit.asr (ivalue t env) off) in
5766
r
5767
end

t << off, a right shift when off is negative

  Valid (126ms) (colibri2 8) (split_vc) (depth 1)
5770
let partial
int_shift
(off: int) (t: t) : t
5771
ensures { denotes1 ivalue (fun x -> Zbit.lsl x off) t result }
5772
ensures { forall env p. 0 <= p ->
5773
(bit result p (sem env p) <-> (0 <= p - off /\ bit t (p - off) (sem env (p - off)))) }
5774
raises { Unsupported -> off < - 0x1000_0000_0000_0000 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }
5775
raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }
5776
= if off >= 0 then int_shift_left off t else int_shift_right (- off) t

SMT–LIB extract: the len bits of t from the position off (total: a negative off reads false below the position 0, a negative len gives 0), as a non–negative integer

  Valid (1.6s) (colibri2 14) (cvc4 4) (split_vc 3) (depth 2)
5781
let partial
int_extract
(off len: int) (t: t) : t
5782
ensures { denotes1 ivalue (fun x -> iextract x off len) t result }
5783
ensures { forall env p. 0 <= p ->
5784
(bit result p (sem env p) <->
5785
(p < len /\ 0 <= p + off /\ bit t (p + off) (sem env (p + off)))) }
5786
raises { Unsupported -> len > 0x100000 \/ off < - 0x1000_0000_0000_0000 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }
5787
raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }
5788
= if len > 0x100000 then raise Unsupported;
5789
let len' = if len < 0 then 0 else len in
5790
let s = int_shift (- off) t in
5791
Zbit.mask_nonneg len';
5792
let m = int_cst (ZbitInt.mask_int len') in
5793
let r = int_logand s m in
5794
let lemma bits (env: Node.t -> int) (p: int) : unit
5795
requires { 0 <= p }
5796
ensures { bit r p (sem env p) <->
5797
(p < len /\ 0 <= p + off /\ bit t (p + off) (sem env (p + off))) }
5798
= if p < len' then Zbit.mask_bits len' p else Zbit.mask_bits_high len' p
5799
in
5800
let lemma lv (env: Node.t -> int) : unit
5801
ensures { ivalue r env = iextract (ivalue t env) off len }
5802
= is_value_iff r env (iextract (ivalue t env) off len) in
5803
r

SMT–LIB update: t where the len bits from the position off are replaced by the low bits of y (total)

  Valid (4.0s) (colibri2 63) (cvc4 36) (cvc5 7) (split_vc 62) (depth 5)
5807
let partial
int_update
(off len: int) (t y: t) : t
5808
ensures { denotes2 ivalue (fun x z -> iupdate x off len z) t y result }
5809
ensures { forall env p. 0 <= p ->
5810
(bit result p (sem env p) <->
5811
(if off <= p /\ p < off + len then bit y (p - off) (sem env (p - off))
5812
else bit t p (sem env p))) }
5813
raises { Unsupported -> len > Zbit.lsl 1 20 \/ off > 0x100000 \/ off < - 0x100000 \/ y.size > 60 }
5814
raises { Overflow -> exists nd. Set.mem nd (all_snodes y) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }
5815
= if len > ZbitInt.lsl_int 1 20 || off > 0x100000 || off < - 0x100000 || y.size > 60 then raise Unsupported;
5816
let len' = if len < 0 then 0 else len in
5817
let o = if off < 0 then 0 else off in
5818
let e = if off + len' < 0 then 0 else off + len' in
5819
Zbit.mask_nonneg len'; Zbit.mask_nonneg o; Zbit.mask_nonneg e;
5820
Zbit.mask_numbits len';
5821
Zbit.mask_nonneg 21; assert { lsl 1 21 = 2 * lsl 1 20 };
5822
Zbit.numbits_lt_lsl len' 21;
5823
let m = int_cst (ZbitInt.mask_int len') in
5824
assert { iabs (Zbit.mask len') = Zbit.mask len' /\ to_int m.size <= 21 };
5825
let ym = int_logand y m in
5826
assert { to_int ym.size <= 60 };
5827
let ys = int_shift off ym in
5828
Zbit.mask_numbits o; Zbit.mask_numbits e;
5829
let ce = int_cst (ZbitInt.mask_int e) in
5830
let co = int_cst (ZbitInt.mask_int o) in
5831
let band = int_logand ce (int_lognot co) in
5832
let hole = int_lognot band in
5833
let tc = int_logand t hole in
5834
let r = int_logor tc ys in
5835
let lemma bits (env: Node.t -> int) (p: int) : unit
5836
requires { 0 <= p }
5837
ensures { bit r p (sem env p) <->
5838
(if off <= p /\ p < off + len then bit y (p - off) (sem env (p - off))
5839
else bit t p (sem env p)) }
5840
= assert { bit band p (sem env p) <-> Zbit.bittest (Zbit.mask e) p /\ not Zbit.bittest (Zbit.mask o) p };
5841
assert { bit hole p (sem env p) <-> not (bit band p (sem env p)) };
5842
assert { bit tc p (sem env p) <-> bit t p (sem env p) /\ bit hole p (sem env p) };
5843
assert { bit ys p (sem env p) <-> 0 <= p - off /\ bit ym (p - off) (sem env (p - off)) };
5844
if 0 <= p - off then assert { bit ym (p - off) (sem env (p - off)) <->
5845
bit y (p - off) (sem env (p - off)) /\ bit m (p - off) (sem env (p - off)) };
5846
if p < o then Zbit.mask_bits o p else Zbit.mask_bits_high o p;
5847
if p < e then Zbit.mask_bits e p else Zbit.mask_bits_high e p;
5848
if 0 <= p - off then (if p - off < len' then Zbit.mask_bits len' (p - off) else Zbit.mask_bits_high len' (p - off))
5849
in
5850
let lemma lv (env: Node.t -> int) : unit
5851
ensures { ivalue r env = iupdate (ivalue t env) off len (ivalue y env) }
5852
= is_value_iff r env (iupdate (ivalue t env) off len (ivalue y env)) in
5853
r

t = 0: ISubst n q r means t = 0 iff r = 0 and n = q (for every value of n); IUnsolved when the term is not solved yet (a node read at several shifts)

  Valid (56ms) (colibri2)
5858
let partial
int_solve
[@spec:none "solver: isolve_ok"] (t: t) : IBDDS.isolve
5859
ensures { isolve_ok t result }
5860
raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ exists sh: int. not (in_bounds (to_int nd.s - sh)) }
5861
= IBDDS.int_solve_t t

t where the node n1 has the value of the term t1

  Valid (2.9s) (colibri2 6) (split_vc 2) (depth 2)
5864
let partial
int_subst
(t: t) (n1: Node.t) (t1: t) : t
5865
ensures { denotes_subst ivalue upd_env n1 t1 t result }
5866
ensures { forall env z. is_value t1 env z ->
5867
forall p. 0 <= p -> (bit result p (sem env p) <-> bit t p (sem (upd_env env n1 z) p)) }
5868
raises { Unsupported -> t.size > 60 \/ exists nd. in_supports t nd /\ nd.SNode.n = n1 /\ not nd.SNode.scal /\ IBDDS.bad_sub t1 (to_int nd.SNode.s) }
5869
= let sel = fun (n: Node.t) ->
5870
ensures { result = (if n = n1 then Some t1 else None) }
5871
if Node.equal n n1 then Some t1 else None in
5872
let r = try IBDDS.compose_i t sel with Overflow -> raise Unsupported end in
5873
{proof…}
5874
let lemma lv (env: Node.t -> int) : unit
5875
ensures { ivalue r env = ivalue t (upd_env env n1 (ivalue t1 env)) }
5876
= is_value_iff r env (ivalue t (upd_env env n1 (ivalue t1 env))) in
5877
{qed}
5878
r

t where each node n has the value of the term f n

  Valid (2.6s) (colibri2 6) (split_vc 2) (depth 2)
5881
let partial
int_normalize
(t: t) (f: Node.t -> t) : t
5882
ensures { denotes_compose ivalue f t result }
5883
ensures { forall env env'. (forall m. is_value (f m) env (env' m)) ->
5884
forall p. 0 <= p -> (bit result p (sem env p) <-> bit t p (sem env' p)) }
5885
raises { Unsupported -> t.size > 60 \/ exists nd. in_supports t nd /\ not nd.SNode.scal /\ IBDDS.bad_sub (f nd.SNode.n) (to_int nd.SNode.s) }
5886
= let sel = fun (n: Node.t) -> ensures { result = Some (f n) } Some (f n) in
5887
let r = try IBDDS.compose_i t sel with Overflow -> raise Unsupported end in
5888
{proof…}
5889
let lemma lv (env env': Node.t -> int) : unit
5890
requires { forall m. env' m = ivalue (f m) env }
5891
ensures { ivalue r env = ivalue t env' }
5892
= is_value_iff r env (ivalue t env') in
5893
{qed}
5894
r

The value of a term without node

  Valid (340ms) (colibri2 4) (split_vc) (depth 1)
5897
let
int_is_cst
(t: t) : option int
5898
ensures { denotes_cst ivalue t result }
5899
ensures { match result with
5900
| Some z -> forall env. is_value t env z
5901
| None -> exists nd. in_supports t nd
5902
end }
5903
raises { Unsupported -> t.size > 61 }
5904
= if t.size > 61 then raise Unsupported;
5905
let r = IBDDS.int_is_cst t in
5906
{proof…}
5907
match r with
5908
| Some z ->
5909
let lemma cv (env: Node.t -> int) : unit ensures { ivalue t env = z }
5910
= is_value_iff t env z in ()
5911
| None -> ()
5912
end;
5913
{qed}
5914
r

The bits that can be 1 (negative when the high bits can) and the bits that are always 1

  Valid (1.1s) (colibri2 6) (cvc4 2) (split_vc) (depth 1)
5918
let partial
int_to_knownbits
(t: t) : (int, int)
5919
ensures { denotes_in ivalue kb_mem t result }
5920
ensures { let (known0, _) = result in
5921
forall q. 0 <= q -> (bittest known0 q <-> exists sn. bit t q sn) }
5922
ensures { let (_, known1) = result in
5923
forall q. 0 <= q -> (bittest known1 q <-> forall sn. bit t q sn) }
5924
raises { Unsupported -> t.size > 61 }
5925
= if t.size > 61 then raise Unsupported;
5926
lsl_le_max_int (to_int t.size);
5927
let (k0, k1) = IBDDS.int_to_knownbits t in
5928
{proof…}
5929
let lemma kb (env: Node.t -> int) : unit
5930
ensures { kb_mem (ivalue t env) (k0, k1) }
5931
= assert { forall i. 0 <= i -> (bittest (ivalue t env) i <-> bit t i (sem env i)) } in
5932
{qed}
5933
(k0, k1)
5934
Valid (301ms) (colibri2)
5935
let
int_compute
(env: Node.t -> int) (t: t) : int
5936
ensures { denotes_at ivalue t env result }
5937
ensures { is_value t env result }
5938
raises { Unsupported -> t.size > 61 }
5939
= if t.size > 61 then raise Unsupported;
5940
IBDDS.compute_i env t

Any term: the dispatch of bddbitv.ml

The terms without tail go to the bounded functions above, the others to the integer ones. The specifications use the integer value: the integer value of a term without tail is its bounded value (value_untailed).

  Valid (57ms) (colibri2)
5950
let ghost
value_untailed
(t: t) (env: Node.t -> int) : unit
5951
requires { not (tailed t) }
5952
ensures { is_value t env (value t env) }
5953
ensures { ivalue t env = value t env }
5954
= let lemma b (p: int) : unit
5955
requires { 0 <= p }
5956
ensures { bittest (value t env) p <-> bit t p (sem env p) }
5957
= PBDD2.def_v t.bdd (to_int t.size) (sem env) p in
5958
is_value_iff t env (value t env)
5959
Valid (143ms) (colibri2)
5960
let partial
any_cst
(x: int) : t
5961
ensures { denotes0 ivalue (fun _ -> x) result }
5962
raises { Unsupported -> Zbit.numbits (iabs x) > Int63.max_int }
5963
= if x < 0 then int_cst x
5964
else begin
5965
let r = bv_cst x in
5966
let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = x } = value_untailed r env in
5967
r
5968
end
5969
Valid (714ms) (colibri2 10) (cvc5) (split_vc 4) (depth 2)
5970
let
any_is_cst
(t: t) : option int
5971
ensures { denotes_cst ivalue t result }
5972
ensures { match result with
5973
| Some z -> forall env. is_value t env z
5974
| None -> exists nd. in_supports t nd
5975
end }
5976
raises { Unsupported -> t.size > 61 }
5977
= if IBDD.has_tail t then int_is_cst t
5978
else begin
5979
let r = bv_is_cst t in
5980
match r with
5981
| Some z ->
5982
let lemma lv (env: Node.t -> int) : unit ensures { is_value t env z } = value_untailed t env in
5983
let lemma cv (env: Node.t -> int) : unit ensures { ivalue t env = z }
5984
= value_untailed t env in
5985
r
5986
| None -> r
5987
end
5988
end
5989
Valid (726ms) (cvc4)
5990
let partial
any_logand
(t1 t2: t) : t
5991
ensures { denotes2 ivalue Zbit.land t1 t2 result }
5992
= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_logand t1 t2
5993
else begin
5994
let r = try bv_logand t1 t2 with Unsupported -> absurd end in
5995
let lemma lv (env: Node.t -> int) : unit
5996
ensures { ivalue r env = Zbit.land (ivalue t1 env) (ivalue t2 env) }
5997
= value_untailed r env; value_untailed t1 env; value_untailed t2 env in
5998
r
5999
end
6000
Valid (1.2s) (colibri2)
6001
let partial
any_logor
(t1 t2: t) : t
6002
ensures { denotes2 ivalue Zbit.lor t1 t2 result }
6003
= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_logor t1 t2
6004
else begin
6005
let r = try bv_logor t1 t2 with Unsupported -> absurd end in
6006
let lemma lv (env: Node.t -> int) : unit
6007
ensures { ivalue r env = Zbit.lor (ivalue t1 env) (ivalue t2 env) }
6008
= value_untailed r env; value_untailed t1 env; value_untailed t2 env in
6009
r
6010
end
6011
Valid (725ms) (cvc4)
6012
let partial
any_xor
(t1 t2: t) : t
6013
ensures { denotes2 ivalue Zbit.lxor t1 t2 result }
6014
= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_xor t1 t2
6015
else begin
6016
let r = try bv_xor t1 t2 with Unsupported -> absurd end in
6017
let lemma lv (env: Node.t -> int) : unit
6018
ensures { ivalue r env = Zbit.lxor (ivalue t1 env) (ivalue t2 env) }
6019
= value_untailed r env; value_untailed t1 env; value_untailed t2 env in
6020
r
6021
end
6022
Valid (744ms) (colibri2 9) (split_vc) (depth 1)
6023
let partial
any_logand_cst
(z: int) (t: t) : t
6024
ensures { denotes1 ivalue (fun x -> Zbit.land z x) t result }
6025
raises { Unsupported -> Zbit.numbits (iabs z) > Int63.max_int }
6026
= if IBDD.has_tail t || z < 0 then begin
6027
let c = int_cst z in
6028
let r = int_logand c t in
6029
let lemma lv (env: Node.t -> int) : unit
6030
ensures { ivalue r env = Zbit.land z (ivalue t env) }
6031
= assert { ivalue c env = z } in
6032
r
6033
end else begin
6034
let r = bv_logand_cst z t in
6035
let lemma lv (env: Node.t -> int) : unit
6036
ensures { ivalue r env = Zbit.land z (ivalue t env) }
6037
= value_untailed r env; value_untailed t env in
6038
r
6039
end
6040
Valid (747ms) (colibri2 9) (split_vc) (depth 1)
6041
let partial
any_logor_cst
(z: int) (t: t) : t
6042
ensures { denotes1 ivalue (fun x -> Zbit.lor z x) t result }
6043
raises { Unsupported -> Zbit.numbits (iabs z) > Int63.max_int }
6044
= if IBDD.has_tail t || z < 0 then begin
6045
let c = int_cst z in
6046
let r = int_logor c t in
6047
let lemma lv (env: Node.t -> int) : unit
6048
ensures { ivalue r env = Zbit.lor z (ivalue t env) }
6049
= assert { ivalue c env = z } in
6050
r
6051
end else begin
6052
let r = bv_logor_cst z t in
6053
let lemma lv (env: Node.t -> int) : unit
6054
ensures { ivalue r env = Zbit.lor z (ivalue t env) }
6055
= value_untailed r env; value_untailed t env in
6056
r
6057
end
6058
Valid (46ms) (colibri2)
6059
let
any_compute
(env: Node.t -> int) (t: t) : int
6060
ensures { denotes_at ivalue t env result }
6061
ensures { is_value t env result }
6062
raises { Unsupported -> t.size > 61 }
6063
= if IBDD.has_tail t then int_compute env t
6064
else begin
6065
let r = bv_compute env t in
6066
value_untailed t env;
6067
r
6068
end

The bits that can be 1 and the bits that are always 1

  Valid (941ms) (colibri2 6) (cvc4 3) (split_vc) (depth 1)
6071
let partial
any_to_knownbits
(t: t) : (int, int)
6072
ensures { denotes_in ivalue kb_mem t result }
6073
raises { Unsupported -> t.size > 61 }
6074
= if IBDD.has_tail t then begin
6075
let (k0, k1) = int_to_knownbits t in
6076
let lemma lv (env: Node.t -> int) : unit
6077
ensures { Zbit.subset k1 (ivalue t env) /\ Zbit.subset (ivalue t env) k0 }
6078
= let lemma b (q: int) : unit
6079
ensures { (bittest k1 q -> bittest (ivalue t env) q) /\ (bittest (ivalue t env) q -> bittest k0 q) }
6080
= if q >= 0 then assert { bittest (ivalue t env) q <-> bit t q (sem env q) } in
6081
() in
6082
(k0, k1)
6083
end else begin
6084
let (k0, k1) = bv_to_knownbits t in
6085
let lemma lv (env: Node.t -> int) : unit
6086
ensures { Zbit.subset k1 (ivalue t env) /\ Zbit.subset (ivalue t env) k0 }
6087
= value_untailed t env in
6088
(k0, k1)
6089
end

bv_solve, where TryLater (no claim) raises Unsupported

  Valid (702ms) (cvc5)
6092
let partial
any_solve
[@spec:none "solver: Zero, Unsat, Subst n q r (t = 0 iff r = 0 and n = q); never TryLater"] (sizes: Node.t -> int63) (t: t) : IBDDS.solve
6093
ensures { match result with
6094
| Zero -> forall env. value t env = 0
6095
| Unsat -> forall env. value t env <> 0
6096
| Subst n q r ->
6097
(forall env x. value r (upd_env env n x) = value r env) /\
6098
(forall env. value r env = 0 -> value t (upd_env env n (value q env)) = 0) /\
6099
(forall env. value t env = 0 ->
6100
value r env = 0 /\ (0 <= env n < Zbit.lsl 1 (sizes n) -> value q env = env n))
6101
| TryLater -> false
6102
end }
6103
raises { Overflow -> (exists nd nd'. Set.mem nd (support t) /\
6104
Set.mem nd' (Set.add nd (dom_snodes t)) /\ not nd'.scal /\ not (in_bounds (to_int nd'.s - nd.s))) \/
6105
(exists nd. Set.mem nd (support t) /\ not (in_bounds (Zbit.lsl 1 t.size - 1 + nd.s))) }
6106
raises { Unsupported -> tailed t \/ IBDDS.solve_later sizes t }
6107
= match bv_solve sizes t with
6108
| TryLater -> raise Unsupported
6109
| r -> r
6110
end

The two terms have the same bits (the same size, window and tail)

  Valid (596ms) (cvc4)
6114
let
same_bits
(a b: t) : bool
6115
ensures { decides_sound (forall p sn. 0 <= p -> (bit a p sn <-> bit b p sn)) result }
6116
= if a.size <> b.size then false
6117
else begin
6118
let (r1, _, _) = PBDD.is_equal a.bdd b.bdd in
6119
let (r2, _, _) = PBDD.is_equal a.tail b.tail in
6120
r1 && r2
6121
end

A node read by the term, if any

  Valid (40ms) (colibri2)
6124
let rec
first_node
[@spec:none "heuristic: the first node read in the list; no claim"] (l: list Key.t) : option Node.t
6125
variant { l }
6126
= match l with
6127
| Nil -> None
6128
| Cons (Key.Var n _ _) _ -> Some n
6129
| Cons _ l' -> first_node l'
6130
end

The term is the node n on sz bits

6133
predicate
bounded_node
(t: t) (n: Node.t) (sz: int) =
6134
0 <= sz /\ forall env. ivalue t env = Zbit.land (Zbit.mask sz) (env n)

The term is the value of one node: the integer n (with a tail) or the bounded n on sz bits. No claim for None

  Valid (720ms) (colibri2 16) (split_vc) (depth 1)
6138
let partial
any_is_one_node
[@spec:none "hint: Some n when t is the node n, or n on some bits (bounded_node); None is no claim"] (t: t) : option Node.t
6139
ensures { match result with
6140
| Some n -> (forall env. ivalue t env = env n) \/ (exists sz. bounded_node t n sz)
6141
| None -> true
6142
end }
6143
= let same_ivalue (a b: t) : unit
6144
requires { forall p sn. 0 <= p -> (bit a p sn <-> bit b p sn) }
6145
ensures { forall env. ivalue a env = ivalue b env }
6146
= let lemma lv (env: Node.t -> int) : unit ensures { ivalue a env = ivalue b env }
6147
= is_value_iff a env (ivalue b env) in
6148
() in
6149
if IBDD.has_tail t then
6150
match first_node (PBDD.vars t.tail) with
6151
| None -> None
6152
| Some n ->
6153
let m = int_monome n in
6154
if same_bits t m then begin same_ivalue t m; Some n end else None
6155
end
6156
else
6157
match first_node (PBDD.vars t.bdd) with
6158
| None -> None
6159
| Some n ->
6160
(* the size of [n]: the bits of [t] when every node is [-1] *)
6161
match bv_compute (fun _ -> -1) t with
6162
| exception Unsupported -> None
6163
| v ->
6164
let s = Zbit.numbits v in
6165
if s > to_int Int63.max_int then None
6166
else begin
6167
let m = try bv_monome (Int63.of_int s) n with Unsupported -> absurd end in
6168
if same_bits t m then begin
6169
same_ivalue t m;
6170
let lemma lv (env: Node.t -> int) : unit
6171
ensures { ivalue t env = Zbit.land (Zbit.mask s) (env n) }
6172
= value_untailed m env in
6173
assert { bounded_node t n s };
6174
Some n
6175
end else None
6176
end
6177
end
6178
end

For the tests: c read as a bit–vector one bit larger, and back. The same integers.

  Valid (720ms) (colibri2)
6183
let partial
reget
(c:t) : t
6184
ensures { forall sn. v result sn = v c sn \/ c.size >= 0x3FFFFFFFFFFFFFFE }
6185
= if c.size >= 0x3FFFFFFFFFFFFFFE then c
6186
else begin
6187
let s = c.size + 1 in
6188
IBDD.mk (IBDD.get c s) s
6189
end
6190
end