Common — library colibrilib.bitwise_rules — module Rules

The rules. A rule requires the meaning of the term of r in the model (the interpretation of the builtin in realValue.ml); a term too big for the BDD (Unsupported, Overflow) gives no equation.

185
module Rules
186
use int.Int
187
use option.Option
188
use colibrilib.known_bits.KnownBits
189
use colibrilib.zarith.Zbit
190
use colibrilib.zbit.ZbitInt
191
use colibrilib.safe_bits.BitsSpec
192
use colibrilib.safe_bits.SafeBits
193
use colibrilib.bdd.Node
194
use colibrilib.sbdd.SNode
195
use colibrilib.ibdd.IBDD
196
use colibrilib.bddbitv.Export
197
use colibrilib.env.Env
198
use colibrilib.spec.Defines
199
use list.List
200
use mach.int.Int63
201
use int.EuclideanDivision as E
202
use int.ComputerDivision as C
203
use colibrilib.bddbitv.IBDDS as S
204
use colibrilib.bv_sem.Sem
205
use Term

The bits of a scalar

  Valid (138ms) (colibri2)
208
let ghost
scalar_bits
(s:int) (c:bool) : unit
209
requires { s = if c then -1 else 0 }
210
ensures { forall i. 0 <= i -> (Zbit.bittest s i <-> c) }
211
= {proof…} let lemma bit (i:int) : unit
212
requires { 0 <= i }
213
ensures { Zbit.bittest s i <-> c }
214
= if c then SafeBits.minus_one_bits i in
215
() {qed}

The bits of 2^k

  Valid (186ms) (colibri2)
218
let ghost
pow_bits
(k:int) : unit
219
requires { 0 <= k }
220
ensures { forall i. Zbit.bittest (Zbit.lsl 1 k) i <-> i = k }
221
= {proof…} let lemma bit (i:int) : unit
222
ensures { Zbit.bittest (Zbit.lsl 1 k) i <-> i = k }
223
= if i < 0 then Zbit.bittest_neg (Zbit.lsl 1 k) i in
224
() {qed}

Converter.testbit_node: the registered node colibri_testbit_int a k

  Valid (336ms) (colibri2)
227
let
testbit_node
(d:env) (a:Node.t) (k:int) : Node.t
228
ensures { live d -> is_testbit d result a k }
229
= apply d (testbit_cst ()) (Cons a (Cons (int_node d k) Nil))

r = a land b

  Valid (967ms) (colibri2) (cvc4) (split_vc) (depth 1)
232
let partial
logand
(d:env) (r a b:Node.t) : unit
233
requires { live d -> defines2 (ienv d) Zbit.land r a b }
234
raises { Contradiction -> not live d }
235
= assume_equality d r (int_logand (monome d a) (monome d b))

r = a lor b

  Valid (341ms) (colibri2)
238
let partial
logor
(d:env) (r a b:Node.t) : unit
239
requires { live d -> defines2 (ienv d) Zbit.lor r a b }
240
raises { Contradiction -> not live d }
241
= assume_equality d r (int_logor (monome d a) (monome d b))

r = a lxor b

  Valid (101ms) (colibri2)
244
let partial
logxor
(d:env) (r a b:Node.t) : unit
245
requires { live d -> defines2 (ienv d) Zbit.lxor r a b }
246
raises { Contradiction -> not live d }
247
= assume_equality d r (int_xor (monome d a) (monome d b))

r = lnot a

  Valid (74ms) (colibri2)
250
let partial
lognot
(d:env) (r a:Node.t) : unit
251
requires { live d -> defines1 (ienv d) Zbit.lnot r a }
252
raises { Contradiction -> not live d }
253
= assume_equality d r (int_lognot (monome d a))

r = asr a off (colibri_rshift_int)

  Valid (177ms) (colibri2 4) (split_vc) (depth 1)
256
let partial
shift_right
(d:env) (r a:Node.t) (off:int) : unit
257
requires { live d -> defines1 (ienv d) (fun x -> Zbit.asr x off) r a }
258
raises { Contradiction -> not live d }
259
raises { Unsupported -> false }
260
raises { Overflow -> false }
261
= try
262
let x = monome d a in
263
assume_equality d r
264
(if off >= 0 then int_shift_right off x else int_shift_left (- off) x)
265
with Unsupported -> () | Overflow -> () end

r = extract off len a (colibri_extract_int)

  Valid (270ms) (colibri2)
268
let partial
extract
(d:env) (r a:Node.t) (off len:int) : unit
269
requires { live d -> defines1 (ienv d) (fun x -> BitsSpec.extract off len x) r a }
270
raises { Contradiction -> not live d }
271
raises { Unsupported -> false }
272
raises { Overflow -> false }
273
= try assume_equality d r (int_extract off len (monome d a))
274
with Unsupported -> () | Overflow -> () end

r = update off len src dst: dst with the bits from off to off+len-1 replaced by the bits of src (colibri_update_int)

  Valid (1.1s) (colibri2)
278
let partial
update
(d:env) (r dst src:Node.t) (off len:int) : unit
279
requires { live d -> defines2 (ienv d) (fun xs xd -> BitsSpec.update off len xs xd) r src dst }
280
raises { Contradiction -> not live d }
281
raises { Unsupported -> false }
282
raises { Overflow -> false }
283
= try assume_equality d r (int_update off len (monome d dst) (monome d src))
284
with Unsupported -> () | Overflow -> () end

r = signed_extract off len a (colibri_signed_extract_int): the bits of a from off (m = 2^len - 1), and above them the bit off+len-1 of a, the testbit node b: r = ((asr a off) land m) lor (scalar b land lnot m)

  Valid (5.7s) (colibri2 49) (cvc4 17) (cvc5) (split_vc 39) (depth 5)
290
let partial
signed_extract
(d:env) (r a:Node.t) (off len:int) : unit
291
requires { live d -> defines1 (ienv d) (fun x -> BitsSpec.signed_extract off len x) r a }
292
raises { Contradiction -> not live d }
293
raises { Unsupported -> false }
294
raises { Overflow -> false }
295
= let k = off + len - 1 in
296
if 0 < len <= 0x100000 && 0 <= k then begin
297
let b = testbit_node d a k in
298
try
299
let m = ZbitInt.mask_int len in
300
let xa = monome d a in
301
let x = if off >= 0 then int_shift_right off xa else int_shift_left (- off) xa in
302
let cm = int_cst m in
303
let low = int_logand x cm in
304
let sb = int_scalar b in
305
let high = int_logand sb (int_lognot cm) in
306
let t = int_logor low high in
307
let lemma ok (_:unit) : unit
308
requires { live d }
309
ensures { ienv d r = ivalue t (ienv d) }
310
= let ea = ienv d a in
311
let s = if ienv d b < 0 then -1 else 0 in
312
assert { ivalue x (ienv d) = Zbit.asr ea off };
313
assert { ivalue cm (ienv d) = m };
314
assert { ivalue low (ienv d) = Zbit.land (Zbit.asr ea off) m };
315
assert { ivalue sb (ienv d) = s };
316
assert { ivalue high (ienv d) = Zbit.land s (Zbit.lnot m) };
317
let v = Zbit.lor (Zbit.land (Zbit.asr ea off) m) (Zbit.land s (Zbit.lnot m)) in
318
assert { ivalue t (ienv d) = v };
319
scalar_bits s (Zbit.bittest ea k);
320
let lemma bit (i:int) : unit
321
requires { 0 <= i }
322
ensures { Zbit.bittest v i <-> Zbit.bittest (BitsSpec.signed_extract off len ea) i }
323
= BitsSpec.bit_signed_extract off len ea i;
324
BitsSpec.mask_field len i in
325
Zbit.ext_bittest v (BitsSpec.signed_extract off len ea) in
326
assume_equality d r t
327
with Unsupported -> () | Overflow -> () end
328
end

The bit k of a is the scalar of r: a = (a land lnot 2^k) lor (scalar r land 2^k)

  Valid (2.5s) (colibri2 21) (cvc4 9) (cvc5) (split_vc 17) (depth 4)
332
let partial
testbit
(d:env) (r a:Node.t) (k:int) : unit
333
requires { live d -> is_testbit d r a k }
334
raises { Contradiction -> not live d }
335
raises { Unsupported -> false }
336
raises { Overflow -> false }
337
= if 0 <= k <= 0x100000 then begin
338
let bit = ZbitInt.lsl_int 1 k in
339
try
340
let x = monome d a in
341
let cnb = int_cst (Zbit.lnot bit) in
342
let cb = int_cst bit in
343
let sr = int_scalar r in
344
let low = int_logand x cnb in
345
let high = int_logand sr cb in
346
let t = int_logor low high in
347
let lemma ok (_:unit) : unit
348
requires { live d }
349
ensures { ienv d a = ivalue t (ienv d) }
350
= let ea = ienv d a in
351
let s = if ienv d r < 0 then -1 else 0 in
352
assert { ivalue x (ienv d) = ea };
353
assert { ivalue cnb (ienv d) = Zbit.lnot bit };
354
assert { ivalue cb (ienv d) = bit };
355
assert { ivalue sr (ienv d) = s };
356
assert { ivalue low (ienv d) = Zbit.land ea (Zbit.lnot bit) };
357
assert { ivalue high (ienv d) = Zbit.land s bit };
358
let v = Zbit.lor (Zbit.land ea (Zbit.lnot bit)) (Zbit.land s bit) in
359
assert { ivalue t (ienv d) = v };
360
scalar_bits s (Zbit.bittest ea k);
361
pow_bits k;
362
let lemma b (i:int) : unit
363
requires { 0 <= i }
364
ensures { Zbit.bittest v i <-> Zbit.bittest ea i }
365
= () in
366
Zbit.ext_bittest v ea in
367
assume_equality d a t
368
with Unsupported -> () | Overflow -> () end
369
end

When the value v of the Boolean node r is known: its scalar is its value, and the bit k of a is v

  Valid (1.3s) (colibri2 105) (cvc4 9) (split_vc 10) (depth 4)
373
let partial
testbit_value
(d:env) (r a:Node.t) (k:int) (v:bool) : unit
374
requires { live d -> is_testbit d r a k }
375
requires { has_bool d r v }
376
raises { Contradiction -> not live d }
377
= (* the scalar of [r] is its value *)
378
let x = int_monome r in
379
let sr = int_scalar r in
380
let s = int_lognot sr in
381
let t = if v then int_logor x s else int_logand x s in
382
let lemma ok_r (_:unit) : unit
383
requires { live d }
384
ensures { ienv d r = ivalue t (ienv d) }
385
= let er = ienv d r in
386
assert { er = if v then -1 else 0 };
387
assert { ivalue x (ienv d) = er };
388
assert { ivalue sr (ienv d) = er };
389
assert { ivalue s (ienv d) = Zbit.lnot er };
390
scalar_bits er v;
391
let lemma bit (i:int) : unit
392
requires { 0 <= i }
393
ensures { Zbit.bittest (Zbit.lnot er) i <-> not v }
394
= () in
395
let w = if v then Zbit.lor er (Zbit.lnot er) else Zbit.land er (Zbit.lnot er) in
396
assert { ivalue t (ienv d) = w };
397
let lemma b (i:int) : unit
398
requires { 0 <= i }
399
ensures { Zbit.bittest w i <-> Zbit.bittest er i }
400
= () in
401
Zbit.ext_bittest w er in
402
assume_equality d r t;
403
(* the bit [k] of [a] *)
404
if 0 <= k <= 0x100000 then begin
405
let bit = ZbitInt.lsl_int 1 k in
406
try
407
let xa = monome d a in
408
let c = if v then int_cst bit else int_cst (Zbit.lnot bit) in
409
let ta = if v then int_logor xa c else int_logand xa c in
410
let lemma ok_a (_:unit) : unit
411
requires { live d }
412
ensures { ienv d a = ivalue ta (ienv d) }
413
= let ea = ienv d a in
414
assert { ivalue xa (ienv d) = ea };
415
assert { ivalue c (ienv d) = if v then bit else Zbit.lnot bit };
416
pow_bits k;
417
let w = if v then Zbit.lor ea bit else Zbit.land ea (Zbit.lnot bit) in
418
assert { ivalue ta (ienv d) = w };
419
assert { Zbit.bittest ea k <-> v };
420
let lemma b (i:int) : unit
421
requires { 0 <= i }
422
ensures { Zbit.bittest w i <-> Zbit.bittest ea i }
423
= () in
424
Zbit.ext_bittest w ea in
425
assume_equality d a ta
426
with Unsupported -> () | Overflow -> () end
427
end

The SMT–LIB bit–vector operators

A bit–vector node of size n has the term bv_monome n a (its bits 0..n-1, without tail); the result is a term without tail, whose integer value is its bounded value (value_untailed). A size too big for the BDD gives no equation.

The bits of bv n x from n are zero

  Valid (825ms) (colibri2)
437
let ghost
bv_high
(n x:int) : unit
438
requires { 0 <= n }
439
ensures { forall i. n <= i -> not (Zbit.bittest (bv n x) i) }
440
ensures { forall i. 0 <= i < n -> (Zbit.bittest (bv n x) i <-> Zbit.bittest x i) }
441
= ()

z_extract y 0 n is y when the bits of y from n are zero

  Valid (174ms) (colibri2)
444
let ghost
extract0
(y n:int) : unit
445
requires { 0 <= n }
446
requires { forall i. n <= i -> not (Zbit.bittest y i) }
447
ensures { z_extract y 0 n = y }
448
= {proof…} let lemma bit (i:int) : unit
449
requires { 0 <= i }
450
ensures { Zbit.bittest (z_extract y 0 n) i <-> Zbit.bittest y i }
451
= Zbit.def_asr y 0 i in
452
Zbit.ext_bittest (z_extract y 0 n) y {qed}

sbv_to_int

  Valid (891ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
455
let ghost
sbv2int_spec
(s x:int) : unit
456
ensures { signed s x = BitsSpec.signed_extract 0 s x }
457
= {proof…} if s > 0 then begin
458
bv_high s x;
459
let lemma bit (i:int) : unit
460
requires { 0 <= i }
461
ensures { Zbit.bittest (z_extract (bv s x) 0 s) i <-> Zbit.bittest (BitsSpec.extract 0 s x) i }
462
= Zbit.def_asr (bv s x) 0 i; Zbit.def_asr x 0 i in
463
Zbit.ext_bittest (z_extract (bv s x) 0 s) (BitsSpec.extract 0 s x)
464
end {qed}

The values of the SMT–LIB bit–vector operators used by the rules: the results of the bv_* functions of colibrilib.bddbitv.Export

468
function
bv_spec
(b:builtin) (x o:int) : int =
469
match b with
470
| BvXor n -> Zbit.lxor (bv n x) (bv n o)
471
| BvNot n -> Zbit.land (Zbit.lnot (bv n x)) (Zbit.mask n)
472
| BvExtract n lo hi -> Zbit.land (Zbit.asr (bv n x) lo) (Zbit.mask (hi - lo + 1))
473
| BvSignExtend n k -> Zbit.land (S.sext n (bv n x)) (Zbit.mask (n + k))
474
| BvRotr n i -> S.rotr n (E.mod i n) (bv n x)
475
| BvRotl n i -> S.rotr n (E.mod (- i) n) (bv n x)
476
| BvShl n -> Zbit.land (Zbit.lsl (bv n x) o) (Zbit.mask n)
477
| BvLshr n -> Zbit.asr (Zbit.land (bv n x) (Zbit.mask n)) o
478
| BvAshr n -> Zbit.land (Zbit.asr (S.sext n (bv n x)) o) (Zbit.mask n)
479
| _ -> 0
480
end

bvxor

  Valid (240ms) (cvc5)
483
let ghost
xor_spec
(n x y:int) : unit
484
requires { 0 <= n }
485
ensures { z_extract (Zbit.lxor (bv n x) (bv n y)) 0 n = bv_spec (BvXor n) x y }
486
= bv_high n x; bv_high n y; extract0 (Zbit.lxor (bv n x) (bv n y)) n

bvnot

  Valid (66ms) (colibri2)
489
let ghost
not_spec
(n x:int) : unit
490
requires { 1 <= n }
491
ensures { z_extract (Zbit.lnot (bv n x)) 0 n = bv_spec (BvNot n) x 0 }
492
= ()

extract

  Valid (334ms) (colibri2)
495
let ghost
extract_spec
(n lo hi x:int) : unit
496
requires { lo <= hi }
497
ensures { z_extract (bv n x) lo (hi - lo + 1) = bv_spec (BvExtract n lo hi) x 0 }
498
= ()

sign_extend

  Valid (1.8s) (colibri2 8) (cvc5) (split_vc 3) (depth 3)
501
let ghost
sign_extend_spec
(n k x:int) : unit
502
requires { 1 <= n /\ 0 <= k }
503
ensures { (let a = bv n x in
504
if Zbit.bittest a (n - 1) then z_extract (Zbit.lor (Zbit.lsl (-1) n) a) 0 (n + k)
505
else a) = bv_spec (BvSignExtend n k) x 0 }
506
= {proof…} let a = bv n x in
507
bv_high n x;
508
let w = if Zbit.bittest a (n - 1) then z_extract (Zbit.lor (Zbit.lsl (-1) n) a) 0 (n + k)
509
else a in
510
let lemma bit (i:int) : unit
511
requires { 0 <= i }
512
ensures { Zbit.bittest w i <-> Zbit.bittest (bv_spec (BvSignExtend n k) x 0) i }
513
= Zbit.def_asr (Zbit.lor (Zbit.lsl (-1) n) a) 0 i;
514
Zbit.def_asr (-1) (- n) i;
515
if i >= n then SafeBits.minus_one_bits (i - n) in
516
Zbit.ext_bittest w (bv_spec (BvSignExtend n k) x 0) {qed}

rotate_right

  Valid (1.1s) (colibri2 10) (split_vc) (depth 1)
519
let ghost
rotr_spec
(n i x:int) : unit
520
requires { 1 <= n /\ 0 <= i }
521
ensures { (let a = bv n x in let k = C.mod i n in
522
z_extract (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 n)
523
= bv_spec (BvRotr n i) x 0 }
524
= {proof…} let a = bv n x in
525
let k = C.mod i n in
526
assert { k = E.mod i n /\ 0 <= k < n };
527
bv_high n x;
528
let w = z_extract (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 n in
529
let lemma bit (p:int) : unit
530
requires { 0 <= p }
531
ensures { Zbit.bittest w p <-> Zbit.bittest (S.rotr n k a) p }
532
= Zbit.def_asr (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k)) 0 p;
533
Zbit.def_asr a k p;
534
Zbit.def_asr a (k - n) p;
535
if p + k - n < 0 then Zbit.bittest_neg a (p + k - n) in
536
Zbit.ext_bittest w (S.rotr n k a) {qed}

rotate_left

  Valid (1.4s) (colibri2 21) (cvc5 5) (split_vc 3) (depth 2)
539
let ghost
rotl_spec
(n i x:int) : unit
540
requires { 1 <= n /\ 0 <= i }
541
ensures { C.mod i n = 0 -> z_extract (bv n x) 0 n = bv_spec (BvRotl n i) x 0 }
542
ensures { C.mod i n <> 0 ->
543
z_extract (Zbit.lor (Zbit.lsl (bv n x) (C.mod i n))
544
(z_extract (bv n x) (n - C.mod i n) (C.mod i n))) 0 n
545
= bv_spec (BvRotl n i) x 0 }
546
= {proof…} let a = bv n x in
547
let k = C.mod i n in
548
assert { k = E.mod i n /\ 0 <= k < n };
549
bv_high n x;
550
if k = 0 then begin
551
assert { E.mod (- i) n = 0 };
552
extract0 a n;
553
let lemma bit (p:int) : unit
554
requires { 0 <= p }
555
ensures { Zbit.bittest a p <-> Zbit.bittest (S.rotr n 0 a) p }
556
= () in
557
Zbit.ext_bittest a (S.rotr n 0 a);
558
assert { bv_spec (BvRotl n i) x 0 = S.rotr n 0 a }
559
end else begin
560
assert { i = E.div i n * n + k };
561
assert { E.div (- i) n = - E.div i n - 1
562
by (- E.div i n - 1) * n <= - i < (- E.div i n - 1) * n + n };
563
let ghost q = E.div i n in
564
assert { n * (- q - 1) = - (n * q) - n };
565
assert { n * E.div (- i) n = - (n * q) - n };
566
assert { E.mod (- i) n = n - k
567
by E.mod (- i) n = - i - n * E.div (- i) n
568
so n * E.div (- i) n = - (n * E.div i n) - n };
569
let w = z_extract (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k)) 0 n in
570
let lemma bit (p:int) : unit
571
requires { 0 <= p }
572
ensures { Zbit.bittest w p <-> Zbit.bittest (S.rotr n (n - k) a) p }
573
= Zbit.def_asr (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k)) 0 p;
574
Zbit.def_asr a (- k) p;
575
Zbit.def_asr a (n - k) p;
576
if p - k < 0 then Zbit.bittest_neg a (p - k) in
577
Zbit.ext_bittest w (S.rotr n (n - k) a);
578
assert { bv_spec (BvRotl n i) x 0 = S.rotr n (n - k) a }
579
end {qed}

signed_bitv is the sign extension of the BDD

  Valid (644ms) (colibri2)
582
let ghost
signed_sext
(n x:int) : unit
583
requires { 1 <= n }
584
ensures { signed n x = S.sext n (bv n x) }
585
= {proof…} let a = bv n x in
586
bv_high n x;
587
Zbit.asr_eq a;
588
let lemma bit (i:int) : unit
589
requires { 0 <= i }
590
ensures { Zbit.bittest (Zbit.land a (Zbit.mask n)) i <-> Zbit.bittest a i }
591
= () in
592
Zbit.ext_bittest (Zbit.land a (Zbit.mask n)) a {qed}

bvshl, bvlshr, bvashr, for a shift 0 <= o < 2^n

  Valid (2.7s) (colibri2 32) (cvc4 3) (cvc5 9) (split_vc 20) (depth 5)
595
let ghost
shift_spec
(op:builtin) (n x o:int) : unit
596
requires { op = BvShl n \/ op = BvLshr n \/ op = BvAshr n }
597
requires { 1 <= n /\ 0 <= o < Zbit.lsl 1 n }
598
ensures { bv n o = o }
599
ensures { match op with
600
| BvShl _ -> (if n <= o then 0 else z_extract (Zbit.lsl (bv n x) o) 0 n)
601
| BvLshr _ -> (if n <= o then 0 else z_extract (Zbit.asr (bv n x) o) 0 n)
602
| _ -> z_extract (Zbit.asr (z_signed_extract (bv n x) 0 n) (if n <= o then n else o)) 0 n
603
end = bv_spec op x o }
604
= {proof…} high_zero o n;
605
let lemma bo (i:int) : unit
606
requires { 0 <= i }
607
ensures { Zbit.bittest (bv n o) i <-> Zbit.bittest o i }
608
= () in
609
Zbit.ext_bittest (bv n o) o;
610
let a = bv n x in
611
bv_high n x;
612
signed_sext n x;
613
assert { z_signed_extract a 0 n = S.sext n a };
614
let w = match op with
615
| BvShl _ -> (if n <= o then 0 else z_extract (Zbit.lsl a o) 0 n)
616
| BvLshr _ -> (if n <= o then 0 else z_extract (Zbit.asr a o) 0 n)
617
| _ -> z_extract (Zbit.asr (z_signed_extract a 0 n) (if n <= o then n else o)) 0 n
618
end in
619
let lemma bit (p:int) : unit
620
requires { 0 <= p }
621
ensures { Zbit.bittest w p <-> Zbit.bittest (bv_spec op x o) p }
622
= Zbit.def_asr a (- o) p;
623
Zbit.def_asr a o p;
624
Zbit.def_asr (Zbit.land a (Zbit.mask n)) o p;
625
Zbit.def_asr (Zbit.lsl a o) 0 p;
626
Zbit.def_asr (Zbit.asr a o) 0 p;
627
Zbit.def_asr (S.sext n a) o p;
628
Zbit.def_asr (z_signed_extract a 0 n) (if n <= o then n else o) p;
629
Zbit.def_asr (Zbit.asr (z_signed_extract a 0 n) (if n <= o then n else o)) 0 p;
630
Zbit.def_asr a 0 (p + o);
631
Zbit.def_asr a 0 (p + n);
632
Zbit.def_asr a 0 (n - 1);
633
if p - o < 0 then Zbit.bittest_neg a (p - o) in
634
Zbit.ext_bittest w (bv_spec op x o) {qed}

r = a op b, op one of bvand, bvor, bvxor

  Valid (2.9s) (colibri2 26) (split_vc 8) (depth 3)
637
let partial
bv_binop
(d:env) (r a b:Node.t) (n:int) (op:builtin) : unit
638
requires { op = BvAnd n \/ op = BvOr n \/ op = BvXor n }
639
requires { live d -> ienv d r = meaning d op (Cons a (Cons b Nil)) }
640
raises { Contradiction -> not live d }
641
= if 0 <= n <= 0x100000 then
642
try
643
let sz = Int63.of_int n in
644
let ta = bv_monome sz a in
645
let tb = bv_monome sz b in
646
let t = match op with
647
| BvAnd _ -> bv_logand ta tb
648
| BvOr _ -> bv_logor ta tb
649
| _ -> bv_xor ta tb
650
end in
651
let lemma ok (_:unit) : unit
652
requires { live d }
653
ensures { ienv d r = ivalue t (ienv d) }
654
= assert { meaning d op (Cons a (Cons b Nil))
655
= code op (Cons (ienv d a) (Cons (ienv d b) Nil)) };
656
(match op with
657
| BvXor _ -> xor_spec n (pure { ienv d a }) (pure { ienv d b })
658
| _ -> () end);
659
value_untailed t (pure { ienv d }) in
660
assume_equality d r t
661
with Unsupported -> () | Overflow -> () end

r = op a, op one of bvnot, extract, sign_extend, rotate_left, rotate_right

  Valid (2.4s) (colibri2 120) (cvc4) (cvc5 9) (split_vc 20) (depth 5)
665
let partial
bv_unop
(d:env) (r a:Node.t) (op:builtin) : unit
666
requires { match op with
667
| BvNot _ | BvExtract _ _ _ | BvSignExtend _ _ | BvRotl _ _ | BvRotr _ _ -> true
668
| _ -> false end }
669
requires { live d -> ienv d r = meaning d op (Cons a Nil) }
670
raises { Contradiction -> not live d }
671
= let n = match op with
672
| BvNot n | BvExtract n _ _ | BvSignExtend n _ | BvRotl n _ | BvRotr n _ -> n
673
| _ -> absurd end in
674
if 0 < n <= 0x100000 then
675
try
676
let sz = Int63.of_int n in
677
let ta = bv_monome sz a in
678
let t = match op with
679
| BvNot _ -> bv_lognot sz ta
680
| BvExtract _ lo hi ->
681
if 0 <= lo <= hi <= 0x100000 then
682
bv_extract (Int63.of_int lo) (Int63.of_int hi) ta
683
else raise Unsupported
684
| BvSignExtend _ k ->
685
if 0 <= k <= 0x100000 then bv_sign_extend sz (Int63.of_int (n + k)) ta
686
else raise Unsupported
687
| BvRotr _ i ->
688
if 0 <= i <= 0x100000 then bv_rotate_right (Int63.of_int i) sz ta
689
else raise Unsupported
690
| BvRotl _ i ->
691
if 0 <= i <= 0x100000 then bv_rotate_left (Int63.of_int i) sz ta
692
else raise Unsupported
693
| _ -> absurd
694
end in
695
let lemma ok (_:unit) : unit
696
requires { live d }
697
ensures { ienv d r = ivalue t (ienv d) }
698
= let ghost x = pure { ienv d a } in
699
assert { meaning d op (Cons a Nil) = code op (Cons x Nil) };
700
value_untailed t (pure { ienv d });
701
(match op with
702
| BvNot _ -> not_spec n x
703
| BvExtract _ lo hi -> extract_spec n lo hi x
704
| BvSignExtend _ k -> sign_extend_spec n k x;
705
assert { code op (Cons x Nil) = bv_spec op x 0 };
706
assert { value ta (ienv d) = bv n x };
707
assert { value t (ienv d) = Zbit.land (S.sext n (bv n x)) (Zbit.mask (n + k)) };
708
assert { ivalue t (ienv d) = bv_spec op x 0 }
709
| BvRotr _ i -> rotr_spec n i x
710
| BvRotl _ i -> rotl_spec n i x;
711
assert { code op (Cons x Nil) = bv_spec op x 0 };
712
assert { value ta (ienv d) = bv n x };
713
assert { value t (ienv d) = S.rotr n (E.mod (- i) n) (bv n x) };
714
assert { ivalue t (ienv d) = bv_spec op x 0 }
715
| _ -> () end) in
716
assume_equality d r t
717
with Unsupported -> () | Overflow -> () end

r = op a off, op one of bvshl, bvlshr, bvashr, the shift o of value off; no equation unless 0 <= off < 2^n (true in a model)

  Valid (1.7s) (colibri2 33) (cvc5) (split_vc 9) (depth 4)
721
let partial
bv_shift
(d:env) (r a o:Node.t) (n off:int) (op:builtin) : unit
722
requires { op = BvShl n \/ op = BvLshr n \/ op = BvAshr n }
723
requires { live d -> ienv d o = off }
724
requires { live d -> ienv d r = meaning d op (Cons a (Cons o Nil)) }
725
raises { Contradiction -> not live d }
726
= if 0 < n <= 0x100000 && 0 <= off && Zbit.numbits off <= n then
727
try
728
let sz = Int63.of_int n in
729
let ta = bv_monome sz a in
730
let t = match op with
731
| BvShl _ -> bv_shift_left off sz ta
732
| BvLshr _ -> bv_shift_right off sz ta
733
| _ -> bv_arith_shift_right off sz ta
734
end in
735
let lemma ok (_:unit) : unit
736
requires { live d }
737
ensures { ienv d r = ivalue t (ienv d) }
738
= assert { off < Zbit.lsl 1 n
739
by Zbit.lsl 1 n <= off -> n + 1 = Zbit.numbits (Zbit.lsl 1 n) <= Zbit.numbits off };
740
assert { meaning d op (Cons a (Cons o Nil))
741
= code op (Cons (ienv d a) (Cons (ienv d o) Nil)) };
742
shift_spec op n (pure { ienv d a }) off;
743
value_untailed t (pure { ienv d }) in
744
assume_equality d r t
745
with Unsupported -> () | Overflow -> () end
746
end