Common — library colibrilib.bv_sem — module Agree

Sem.code is the SMT–LIB semantics

557
module Agree
558
use int.Int
559
use int.Power
560
use int.EuclideanDivision as E
561
use int.ComputerDivision as C
562
use list.List
563
use colibrilib.zarith.Zbit
564
use colibrilib.safe_bits.SafeBits as SB
565
use colibrilib.known_bits.Range
566
use Sem
567
use Smtlib

Facts

2^n

  Valid (45ms) (colibri2)
572
let ghost
pow_lsl
(n:int) : unit
573
requires { 0 <= n }
574
ensures { power 2 n = Zbit.lsl 1 n }
575
= Zbit.lsl_mul 1 n
576
Valid (43ms) (colibri2)
577
let ghost
pow_pos
(n:int) : unit
578
requires { 0 <= n }
579
ensures { 0 < power 2 n }
580
= ()

The bits of ext n y

  Valid (55ms) (colibri2)
583
let ghost
ext_bits
(n y:int) : unit
584
ensures { forall i. 0 <= i -> (Zbit.bittest (ext n y) i <-> i < n /\ Zbit.bittest y i) }
585
= {proof…} Zbit.asr_eq y;
586
if n > 0 then begin
587
let lemma bit (i:int) : unit
588
requires { 0 <= i }
589
ensures { Zbit.bittest (ext n y) i <-> i < n /\ Zbit.bittest y i }
590
= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in ()
591
end {qed}

A non–negative integer without bits from m is below 2^m

  Valid (71ms) (colibri2)
594
let ghost
bits_lt
(m v:int) : unit
595
requires { 0 <= m /\ 0 <= v }
596
requires { forall i. m <= i -> not (Zbit.bittest v i) }
597
ensures { v < Zbit.lsl 1 m }
598
= {proof…} if v > 0 then begin
599
Zbit.numbits_top_bit v;
600
Zbit.numbits_lsl_lt v;
601
let k = Zbit.numbits v in
602
assert { k <= m };
603
pow_lsl k; pow_lsl m;
604
assert { power 2 k <= power 2 m by power 2 m = power 2 k * power 2 (m - k) }
605
end else begin
606
pow_lsl m
607
end {qed}

in_range from the bits

  Valid (56ms) (colibri2)
610
let ghost
in_range_bits
(m v:int) : unit
611
requires { 0 <= m /\ 0 <= v }
612
requires { forall i. m <= i -> not (Zbit.bittest v i) }
613
ensures { in_range m v }
614
= bits_lt m v

lam m f is a bit–vector of size m

  Valid (349ms) (colibri2)
617
let ghost
lam_range
(m:int) (f:int -> bool) : unit
618
requires { 0 <= m }
619
ensures { in_range m (lam m f) }
620
= in_range_bits m (lam m f)

ext n y is a bit–vector of size n

  Valid (134ms) (cvc4)
623
let ghost
ext_range
(n y:int) : unit
624
requires { 0 <= n }
625
ensures { in_range n (ext n y) }
626
= {proof…} ext_bits n y;
627
if n > 0 then begin
628
Zbit.mask_nonneg n; Zbit.land_nonneg_l (Zbit.mask n) (Zbit.asr y 0);
629
Zbit.ext_bittest (ext n y) (Zbit.land (Zbit.mask n) (Zbit.asr y 0))
630
end;
631
in_range_bits n (ext n y) {qed}

The bits from n of a bit–vector of size n are zero

  Valid (41ms) (colibri2)
634
let ghost
range_high
(n x:int) : unit
635
requires { in_range n x }
636
ensures { 0 <= n }
637
ensures { forall i. n <= i -> not (Zbit.bittest x i) }
638
= {proof…} Zbit.numbits_lt_lsl x n; Zbit.numbits_ge_pos 0 x; Sem.high_zero x n {qed}

Equal bits

  Valid (44ms) (colibri2)
641
let ghost
same_bits
(n x y:int) : unit
642
requires { in_range n x /\ in_range n y }
643
requires { forall i. 0 <= i < n -> (Zbit.bittest x i <-> Zbit.bittest y i) }
644
ensures { x = y }
645
= {proof…} range_high n x; range_high n y;
646
let lemma bit (i:int) : unit
647
requires { 0 <= i }
648
ensures { Zbit.bittest x i <-> Zbit.bittest y i }
649
= () in
650
Zbit.ext_bittest x y {qed}

bv n x of a bit–vector of size n

  Valid (64ms) (colibri2)
653
let ghost
bv_id
(n x:int) : unit
654
requires { in_range n x }
655
ensures { bv n x = x }
656
= {proof…} range_high n x;
657
let lemma bit (i:int) : unit
658
requires { 0 <= i }
659
ensures { Zbit.bittest (bv n x) i <-> Zbit.bittest x i }
660
= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in
661
Zbit.ext_bittest (bv n x) x {qed}

ext n y is y mod 2^n

  Valid (364ms) (colibri2 10) (split_vc) (depth 1)
664
let ghost
ext_mod
(n y:int) : unit
665
requires { 0 <= n }
666
ensures { ext n y = E.mod y (power 2 n) }
667
= {proof…} pow_lsl n;
668
split y n;
669
let r = Zbit.land (Zbit.mask n) y in
670
ext_bits n y;
671
let lemma bit (i:int) : unit
672
requires { 0 <= i }
673
ensures { Zbit.bittest (ext n y) i <-> Zbit.bittest r i }
674
= if i >= n then Zbit.mask_bits_high n i in
675
Zbit.ext_bittest (ext n y) r;
676
let q = Zbit.asr y n in
677
assert { y = q * power 2 n + r };
678
assert { E.div y (power 2 n) = q
679
by q * power 2 n <= y < q * power 2 n + power 2 n };
680
assert { E.mod y (power 2 n) = r } {qed}

nat2bv is ext

  Valid (48ms) (colibri2)
683
let ghost
nat2bv_ext
(m n:int) : unit
684
requires { 0 <= m }
685
ensures { nat2bv m n = ext m n }
686
= ext_mod m n

A bit–vector is its own ext

  Valid (58ms) (colibri2)
689
let ghost
ext_id
(n x:int) : unit
690
requires { in_range n x }
691
ensures { ext n x = x }
692
= {proof…} range_high n x; ext_range n x; ext_bits n x;
693
same_bits n (ext n x) x {qed}

lam 1 f

  Valid (51ms) (colibri2)
696
let ghost
lam1
(f:int -> bool) : unit
697
ensures { lam 1 f = if f 0 then 1 else 0 }
698
= {proof…} lam_range 1 f;
699
pow_lsl 1;
700
assert { Zbit.bittest 1 0 };
701
if f 0 then same_bits 1 (lam 1 f) 1
702
else same_bits 1 (lam 1 f) 0 {qed}

A bit of s as a bit–vector of size 1

  Valid (340ms) (colibri2 14) (split_vc 3) (depth 2)
705
let ghost
extract1
(j s:int) : unit
706
ensures { extract j j s = if Zbit.bittest s j then 1 else 0 }
707
= {proof…} let e = extract j j s in
708
assert { forall i. 0 <= i -> (Zbit.bittest e i <-> i < 1 /\ Zbit.bittest s (j + i)) };
709
assert { Zbit.bittest e 0 <-> Zbit.bittest s j };
710
in_range_bits 1 e;
711
pow_lsl 1;
712
assert { power 2 1 = 2 };
713
assert { Zbit.bittest 1 0 };
714
assert { forall i. 0 < i -> not (Zbit.bittest 1 i) };
715
if Zbit.bittest s j then same_bits 1 e 1 else same_bits 1 e 0 {qed}

The most significant bit

  Valid (40ms) (colibri2)
718
let ghost
msb_val
(m s:int) : unit
719
ensures { msb m s = if Zbit.bittest s (m - 1) then 1 else 0 }
720
= extract1 (m - 1) s

bv2int: a bit–vector of size n as a signed integer

  Valid (118ms) (cvc4)
723
let ghost
signed_val
(n x:int) : unit
724
requires { 1 <= n /\ in_range n x }
725
ensures { signed n x = bv2int n x }
726
= {proof…} bv_id n x;
727
range_high n x;
728
Zbit.asr_eq x;
729
ext_id n x;
730
assert { z_extract x 0 n = x };
731
pow_lsl n;
732
if Zbit.bittest x (n - 1) then begin
733
let w = Zbit.lor x (Zbit.lnot (Zbit.mask n)) in
734
let lemma bit (i:int) : unit
735
requires { 0 <= i }
736
ensures { Zbit.bittest w i <-> Zbit.bittest (x - Zbit.lsl 1 n) i }
737
= if i < n then (Zbit.mask_bits n i; Zbit.bittest_sub_lsl x n i)
738
else (Zbit.mask_bits_high n i; Zbit.bittest_sub_lsl_high x n i) in
739
Zbit.ext_bittest w (x - Zbit.lsl 1 n)
740
end {qed}

E.mod of a sum

  Valid (44ms) (colibri2 5) (split_vc) (depth 1)
743
let ghost
mod_add
(x y p:int) : unit
744
requires { 0 < p }
745
ensures { E.mod (x + E.mod y p) p = E.mod (x + y) p }
746
= {proof…} let q = E.div y p in
747
assert { y = p * q + E.mod y p };
748
assert { x + y = p * q + (x + E.mod y p) };
749
assert { E.mod (p * q + (x + E.mod y p)) p = E.mod (x + E.mod y p) p } {qed}

The non–negative divisions

  Valid (87ms) (colibri2)
752
let ghost
cdiv_pos
(a b:int) : unit
753
requires { 0 <= a /\ 0 < b }
754
ensures { C.div a b = E.div a b /\ C.mod a b = E.mod a b }
755
= {proof…} assert { 0 <= C.mod a b < b };
756
assert { a = C.div a b * b + C.mod a b };
757
assert { E.div a b = C.div a b by C.div a b * b <= a < C.div a b * b + b } {qed}

The operators for arguments of size n >= 1

  Valid (812ms) (cvc5)
761
let ghost
op_not
(n x:int) : unit
762
requires { 1 <= n /\ in_range n x }
763
ensures { code (BvNot n) (Cons x Nil) = bvnot n x }
764
= {proof…} bv_id n x; ext_bits n (Zbit.lnot x); ext_range n (Zbit.lnot x);
765
in_range_bits n (bvnot n x);
766
same_bits n (ext n (Zbit.lnot x)) (bvnot n x) {qed}
767
Valid (955ms) (cvc5)
768
let ghost
op_and
(n x y:int) : unit
769
requires { 1 <= n /\ in_range n x /\ in_range n y }
770
ensures { code (BvAnd n) (Cons x (Cons y Nil)) = bvand n x y }
771
= {proof…} bv_id n x; bv_id n y; range_high n x; range_high n y;
772
in_range_bits n (Zbit.land x y);
773
in_range_bits n (bvand n x y);
774
same_bits n (Zbit.land x y) (bvand n x y) {qed}
775
Valid (88ms) (colibri2 11) (split_vc) (depth 1)
776
let ghost
op_or
(n x y:int) : unit
777
requires { 1 <= n /\ in_range n x /\ in_range n y }
778
ensures { code (BvOr n) (Cons x (Cons y Nil)) = bvor n x y }
779
= {proof…} bv_id n x; bv_id n y; range_high n x; range_high n y;
780
in_range_bits n (Zbit.lor x y);
781
in_range_bits n (bvor n x y);
782
same_bits n (Zbit.lor x y) (bvor n x y) {qed}
783
Valid (530ms) (colibri2 11) (cvc4) (cvc5) (split_vc) (depth 1)
784
let ghost
op_xor
(n x y:int) : unit
785
requires { 1 <= n /\ in_range n x /\ in_range n y }
786
ensures { code (BvXor n) (Cons x (Cons y Nil)) = bvxor n x y }
787
= {proof…} bv_id n x; bv_id n y;
788
let c = ext n (Zbit.lxor x y) in
789
ext_bits n (Zbit.lxor x y); ext_range n (Zbit.lxor x y);
790
in_range_bits n (bvxor n x y);
791
let lemma bit (i:int) : unit
792
requires { 0 <= i < n }
793
ensures { Zbit.bittest c i <-> Zbit.bittest (bvxor n x y) i }
794
= assert { Zbit.bittest (bvnot n y) i <-> not (Zbit.bittest y i) };
795
assert { Zbit.bittest (bvnot n x) i <-> not (Zbit.bittest x i) };
796
assert { Zbit.bittest (bvand n x (bvnot n y)) i <-> Zbit.bittest x i /\ not (Zbit.bittest y i) };
797
assert { Zbit.bittest (bvand n (bvnot n x) y) i <-> not (Zbit.bittest x i) /\ Zbit.bittest y i } in
798
same_bits n c (bvxor n x y) {qed}
799
Valid (827ms) (colibri2 7) (cvc5) (split_vc) (depth 1)
800
let ghost
op_nand
(n x y:int) : unit
801
requires { 1 <= n /\ in_range n x /\ in_range n y }
802
ensures { code (BvNand n) (Cons x (Cons y Nil)) = bvnand n x y }
803
= {proof…} bv_id n x; bv_id n y;
804
let c = ext n (Zbit.lnot (Zbit.land x y)) in
805
ext_bits n (Zbit.lnot (Zbit.land x y)); ext_range n (Zbit.lnot (Zbit.land x y));
806
in_range_bits n (bvnand n x y);
807
same_bits n c (bvnand n x y) {qed}
808
Valid (1.1s) (colibri2 7) (cvc5) (split_vc) (depth 1)
809
let ghost
op_nor
(n x y:int) : unit
810
requires { 1 <= n /\ in_range n x /\ in_range n y }
811
ensures { code (BvNor n) (Cons x (Cons y Nil)) = bvnor n x y }
812
= {proof…} bv_id n x; bv_id n y;
813
let c = ext n (Zbit.lnot (Zbit.lor x y)) in
814
ext_bits n (Zbit.lnot (Zbit.lor x y)); ext_range n (Zbit.lnot (Zbit.lor x y));
815
in_range_bits n (bvnor n x y);
816
same_bits n c (bvnor n x y) {qed}
817
Valid (1.0s) (colibri2 11) (cvc4) (cvc5) (split_vc) (depth 1)
818
let ghost
op_xnor
(n x y:int) : unit
819
requires { 1 <= n /\ in_range n x /\ in_range n y }
820
ensures { code (BvXnor n) (Cons x (Cons y Nil)) = bvxnor n x y }
821
= {proof…} bv_id n x; bv_id n y;
822
let c = ext n (Zbit.lxor x (Zbit.lnot y)) in
823
ext_bits n (Zbit.lxor x (Zbit.lnot y)); ext_range n (Zbit.lxor x (Zbit.lnot y));
824
in_range_bits n (bvxnor n x y);
825
let lemma bit (i:int) : unit
826
requires { 0 <= i < n }
827
ensures { Zbit.bittest c i <-> Zbit.bittest (bvxnor n x y) i }
828
= assert { Zbit.bittest (bvnot n y) i <-> not (Zbit.bittest y i) };
829
assert { Zbit.bittest (bvnot n x) i <-> not (Zbit.bittest x i) };
830
assert { Zbit.bittest (bvand n x y) i <-> Zbit.bittest x i /\ Zbit.bittest y i };
831
assert { Zbit.bittest (bvand n (bvnot n x) (bvnot n y)) i <->
832
not (Zbit.bittest x i) /\ not (Zbit.bittest y i) } in
833
same_bits n c (bvxnor n x y) {qed}
834
Valid (389ms) (colibri2 15) (cvc4) (split_vc) (depth 1)
835
let ghost
op_concat
(n m x y:int) : unit
836
requires { 1 <= n /\ 1 <= m /\ in_range n x /\ in_range m y }
837
ensures { code (BvConcat n m) (Cons x (Cons y Nil)) = concat n m x y }
838
= {proof…} bv_id n x; bv_id m y; range_high n x; range_high m y;
839
let c = Zbit.lor (Zbit.lsl x m) y in
840
let lemma bit (i:int) : unit
841
requires { 0 <= i }
842
ensures { Zbit.bittest c i <-> (i < n + m /\ if i < m then Zbit.bittest y i else Zbit.bittest x (i - m)) }
843
= Zbit.def_asr x (- m) i;
844
if i - m < 0 then Zbit.bittest_neg x (i - m) in
845
Zbit.lsl_mul x m;
846
assert { 0 <= c };
847
in_range_bits (n + m) c;
848
in_range_bits (n + m) (concat n m x y);
849
same_bits (n + m) c (concat n m x y) {qed}
850
Valid (400ms) (colibri2 18) (split_vc) (depth 1)
851
let ghost
op_extract
(n lo hi x:int) : unit
852
requires { 0 <= lo <= hi < n /\ in_range n x }
853
ensures { code (BvExtract n lo hi) (Cons x Nil) = extract hi lo x }
854
= {proof…} bv_id n x;
855
let l = hi - lo + 1 in
856
let c = z_extract x lo l in
857
Zbit.mask_nonneg l;
858
Zbit.land_nonneg_l (Zbit.mask l) (Zbit.asr x lo);
859
assert { 0 <= c };
860
let lemma bit (i:int) : unit
861
requires { 0 <= i }
862
ensures { Zbit.bittest c i <-> (i < l /\ Zbit.bittest x (lo + i)) }
863
= Zbit.def_asr x lo i;
864
if i < l then Zbit.mask_bits l i else Zbit.mask_bits_high l i in
865
in_range_bits l c;
866
assert { forall i. 0 <= i -> (Zbit.bittest (extract hi lo x) i <-> i < l /\ Zbit.bittest x (lo + i)) };
867
in_range_bits l (extract hi lo x);
868
same_bits l c (extract hi lo x) {qed}
869
Valid (61ms) (colibri2)
870
let ghost
op_neg
(n x:int) : unit
871
requires { 1 <= n /\ in_range n x }
872
ensures { code (BvNeg n) (Cons x Nil) = bvneg n x }
873
= {proof…} bv_id n x; pow_lsl n; nat2bv_ext n (power 2 n - x) {qed}
874
Valid (66ms) (colibri2)
875
let ghost
op_add
(n x y:int) : unit
876
requires { 1 <= n /\ in_range n x /\ in_range n y }
877
ensures { code (BvAdd n) (Cons x (Cons y Nil)) = bvadd n x y }
878
= {proof…} bv_id n x; bv_id n y; nat2bv_ext n (x + y) {qed}
879
Valid (77ms) (colibri2)
880
let ghost
op_mul
(n x y:int) : unit
881
requires { 1 <= n /\ in_range n x /\ in_range n y }
882
ensures { code (BvMul n) (Cons x (Cons y Nil)) = bvmul n x y }
883
= {proof…} bv_id n x; bv_id n y; nat2bv_ext n (x * y) {qed}
884
Valid (79ms) (colibri2)
885
let ghost
op_sub
(n x y:int) : unit
886
requires { 1 <= n /\ in_range n x /\ in_range n y }
887
ensures { code (BvSub n) (Cons x (Cons y Nil)) = bvsub n x y }
888
= {proof…} bv_id n x; bv_id n y;
889
let p = power 2 n in
890
pow_pos n;
891
mod_add x (p - y) p;
892
assert { x + (p - y) = p * 1 + (x - y) };
893
assert { E.mod (p * 1 + (x - y)) p = E.mod (x - y) p };
894
ext_mod n (x - y) {qed}

All ones

  Valid (127ms) (cvc4)
897
let ghost
ones
(n:int) : unit
898
requires { 1 <= n }
899
ensures { ext n (-1) = lam n (fun _ -> true) }
900
= {proof…} ext_bits n (-1); ext_range n (-1);
901
let lemma bit (i:int) : unit
902
requires { 0 <= i }
903
ensures { Zbit.bittest (-1) i }
904
= SB.minus_one_bits i in
905
in_range_bits n (lam n (fun _ -> true));
906
same_bits n (ext n (-1)) (lam n (fun _ -> true)) {qed}
907
Valid (68ms) (colibri2)
908
let ghost
op_udiv
(n x y:int) : unit
909
requires { 1 <= n /\ in_range n x /\ in_range n y }
910
ensures { code (BvUdiv n) (Cons x (Cons y Nil)) = bvudiv n x y }
911
= {proof…} bv_id n x; bv_id n y;
912
if y = 0 then ones n
913
else begin cdiv_pos x y; nat2bv_ext n (E.div x y) end {qed}
914
Valid (70ms) (colibri2)
915
let ghost
op_urem
(n x y:int) : unit
916
requires { 1 <= n /\ in_range n x /\ in_range n y }
917
ensures { code (BvUrem n) (Cons x (Cons y Nil)) = bvurem n x y }
918
= {proof…} bv_id n x; bv_id n y;
919
if y <> 0 then begin cdiv_pos x y; nat2bv_ext n (E.mod x y) end {qed}
920
Valid (398ms) (colibri2 12) (split_vc) (depth 1)
921
let ghost
op_shl
(n x y:int) : unit
922
requires { 1 <= n /\ in_range n x /\ in_range n y }
923
ensures { code (BvShl n) (Cons x (Cons y Nil)) = bvshl n x y }
924
= {proof…} bv_id n x; bv_id n y; range_high n y;
925
Zbit.lsl_mul x y;
926
nat2bv_ext n (x * power 2 y);
927
if n <= y then begin
928
let p = power 2 n in
929
pow_pos n;
930
assert { power 2 y = p * power 2 (y - n) };
931
assert { x * power 2 y = p * (x * power 2 (y - n)) + 0 };
932
assert { E.mod (p * (x * power 2 (y - n)) + 0) p = E.mod 0 p };
933
ext_mod n (x * power 2 y)
934
end else ext_mod n (Zbit.lsl x y) {qed}

bvlshr is asr

  Valid (149ms) (colibri2)
937
let ghost
lshr_asr
(n x y:int) : unit
938
requires { 1 <= n /\ in_range n x /\ 0 <= y }
939
ensures { bvlshr n x y = Zbit.asr x y }
940
ensures { in_range n (Zbit.asr x y) }
941
= {proof…} Zbit.asr_div x y;
942
range_high n x;
943
nat2bv_ext n (E.div x (power 2 y));
944
Zbit.asr_nonneg x y;
945
in_range_bits n (Zbit.asr x y);
946
ext_id n (Zbit.asr x y) {qed}
947
Valid (791ms) (colibri2)
948
let ghost
op_lshr
(n x y:int) : unit
949
requires { 1 <= n /\ in_range n x /\ in_range n y }
950
ensures { code (BvLshr n) (Cons x (Cons y Nil)) = bvlshr n x y }
951
= {proof…} bv_id n x; bv_id n y; range_high n y;
952
lshr_asr n x y;
953
range_high n x;
954
if n <= y then begin
955
let lemma bit (i:int) : unit
956
requires { 0 <= i }
957
ensures { not (Zbit.bittest (Zbit.asr x y) i) }
958
= () in
959
Zbit.ext_bittest (Zbit.asr x y) 0
960
end else ext_id n (Zbit.asr x y) {qed}

The bits of bvnot

  Valid (123ms) (cvc4)
963
let ghost
not_bits
(n x:int) : unit
964
requires { 1 <= n }
965
ensures { in_range n (bvnot n x) }
966
ensures { forall i. 0 <= i -> (Zbit.bittest (bvnot n x) i <-> i < n /\ not (Zbit.bittest x i)) }
967
= in_range_bits n (bvnot n x)

The bits of signed

  Valid (151ms) (cvc5)
970
let ghost
signed_bits
(n x:int) : unit
971
requires { 1 <= n /\ in_range n x }
972
ensures { forall i. 0 <= i ->
973
(Zbit.bittest (signed n x) i <-> if i < n then Zbit.bittest x i else Zbit.bittest x (n - 1)) }
974
= {proof…} signed_val n x; range_high n x; pow_lsl n;
975
let lemma bit (i:int) : unit
976
requires { 0 <= i }
977
ensures { Zbit.bittest (signed n x) i <-> if i < n then Zbit.bittest x i else Zbit.bittest x (n - 1) }
978
= if Zbit.bittest x (n - 1) then begin
979
if i < n then Zbit.bittest_sub_lsl x n i else Zbit.bittest_sub_lsl_high x n i
980
end in () {qed}
981
Valid (1.6s) (colibri2 21) (cvc4) (split_vc 3) (depth 3)
982
let ghost
op_ashr
(n x y:int) : unit
983
requires { 1 <= n /\ in_range n x /\ in_range n y }
984
ensures { code (BvAshr n) (Cons x (Cons y Nil)) = bvashr n x y }
985
= {proof…} bv_id n y; range_high n y; range_high n x;
986
msb_val n x;
987
signed_bits n x;
988
let b = if n <= y then n else y in
989
let c = ext n (Zbit.asr (signed n x) b) in
990
ext_bits n (Zbit.asr (signed n x) b); ext_range n (Zbit.asr (signed n x) b);
991
if Zbit.bittest x (n - 1) then begin
992
not_bits n x;
993
lshr_asr n (bvnot n x) y;
994
not_bits n (bvlshr n (bvnot n x) y);
995
let lemma bit (i:int) : unit
996
requires { 0 <= i < n }
997
ensures { Zbit.bittest c i <-> Zbit.bittest (bvashr n x y) i }
998
= Zbit.def_asr (signed n x) b i; Zbit.def_asr (bvnot n x) y i in
999
same_bits n c (bvashr n x y)
1000
end else begin
1001
lshr_asr n x y;
1002
let lemma bit (i:int) : unit
1003
requires { 0 <= i < n }
1004
ensures { Zbit.bittest c i <-> Zbit.bittest (bvashr n x y) i }
1005
= Zbit.def_asr (signed n x) b i; Zbit.def_asr x y i in
1006
same_bits n c (bvashr n x y)
1007
end {qed}
1008
Valid (1.5s) (colibri2 3) (cvc4) (cvc5 6) (split_vc) (depth 1)
1009
let ghost
op_cmp
(op:builtin) (n x y:int) : unit
1010
requires { 1 <= n /\ in_range n x /\ in_range n y }
1011
requires { match op with
1012
| BvUlt m | BvUle m | BvUgt m | BvUge m | BvSlt m | BvSle m | BvSgt m | BvSge m -> m = n
1013
| _ -> false end }
1014
ensures { code op (Cons x (Cons y Nil)) = match op with
1015
| BvUlt _ -> bool (bvult x y)
1016
| BvUle _ -> bool (bvule x y)
1017
| BvUgt _ -> bool (bvugt x y)
1018
| BvUge _ -> bool (bvuge x y)
1019
| BvSlt _ -> bool (bvslt n x y)
1020
| BvSle _ -> bool (bvsle n x y)
1021
| BvSgt _ -> bool (bvsgt n x y)
1022
| _ -> bool (bvsge n x y) end }
1023
= {proof…} bv_id n x; bv_id n y;
1024
signed_val n x; signed_val n y; msb_val n x; msb_val n y;
1025
pow_lsl n;
1026
assert { signed n x < signed n y <-> bvslt n x y };
1027
assert { signed n y < signed n x <-> bvslt n y x };
1028
assert { signed n x <= signed n y <-> bvsle n x y };
1029
assert { signed n y <= signed n x <-> bvsle n y x } {qed}
1030
Valid (54ms) (colibri2)
1031
let ghost
op_bv2nat
(n x:int) : unit
1032
requires { 1 <= n /\ in_range n x }
1033
ensures { code (Bv2nat n) (Cons x Nil) = ubv_to_int x }
1034
= bv_id n x
1035
Valid (126ms) (cvc5)
1036
let ghost
op_sbv2int
(n x:int) : unit
1037
requires { 1 <= n /\ in_range n x }
1038
ensures { code (Sbv2int n) (Cons x Nil) = sbv_to_int n x }
1039
= signed_val n x
1040
Valid (80ms) (colibri2)
1041
let ghost
op_int2bv
(n x:int) : unit
1042
requires { 1 <= n }
1043
ensures { code (Int2bv n) (Cons x Nil) = int_to_bv n x }
1044
= {proof…} pow_pos n;
1045
ext_mod n x;
1046
nat2bv_ext n (E.mod x (power 2 n));
1047
ext_mod n (E.mod x (power 2 n)) {qed}

The signed division

The truncated division is unique

  Valid (352ms) (colibri2 10) (cvc5 3) (split_vc 3) (depth 3)
1052
let ghost
cdiv_unique
(a b q r:int) : unit
1053
requires { b <> 0 }
1054
requires { a = q * b + r }
1055
requires { 0 <= r < b \/ b < r <= 0 \/ 0 <= r < - b \/ - b < r <= 0 }
1056
requires { a >= 0 -> r >= 0 }
1057
requires { a <= 0 -> r <= 0 }
1058
ensures { C.div a b = q /\ C.mod a b = r }
1059
= {proof…} let q' = C.div a b in
1060
let r' = C.mod a b in
1061
assert { a = q' * b + r' };
1062
assert { (a >= 0 -> r' >= 0) /\ (a <= 0 -> r' <= 0) };
1063
assert { - (if b < 0 then - b else b) < r' < (if b < 0 then - b else b) };
1064
assert { (q - q') * b = r' - r };
1065
if q <> q' then begin
1066
if b > 0 then begin
1067
if q > q' then assert { (q - q') * b >= b } else assert { (q' - q) * b >= b }
1068
end else begin
1069
if q > q' then assert { (q - q') * (- b) >= - b } else assert { (q' - q) * (- b) >= - b }
1070
end
1071
end {qed}

The truncated division by the signs of the absolute values

  Valid (402ms) (colibri2 26) (cvc5) (split_vc) (depth 1)
1074
let ghost
cdiv_signs
(a b:int) : unit
1075
requires { 0 <= a /\ 0 < b }
1076
ensures { C.div a b = E.div a b /\ C.mod a b = E.mod a b }
1077
ensures { C.div (- a) b = - E.div a b /\ C.mod (- a) b = - E.mod a b }
1078
ensures { C.div a (- b) = - E.div a b /\ C.mod a (- b) = E.mod a b }
1079
ensures { C.div (- a) (- b) = E.div a b /\ C.mod (- a) (- b) = - E.mod a b }
1080
= {proof…} let q = E.div a b in
1081
let r = E.mod a b in
1082
assert { a = q * b + r /\ 0 <= r < b };
1083
cdiv_unique a b q r;
1084
cdiv_unique (- a) b (- q) (- r);
1085
cdiv_unique a (- b) (- q) r;
1086
cdiv_unique (- a) (- b) q (- r) {qed}

The Euclidean remainder of - a

  Valid (403ms) (colibri2 7) (cvc5) (split_vc) (depth 1)
1089
let ghost
emod_neg
(a b:int) : unit
1090
requires { 0 <= a /\ 0 < b }
1091
ensures { E.mod (- a) b = if E.mod a b = 0 then 0 else b - E.mod a b }
1092
= {proof…} let q = E.div a b in
1093
let r = E.mod a b in
1094
assert { a = q * b + r /\ 0 <= r < b };
1095
if r = 0 then begin
1096
assert { - a = (- q) * b + 0 };
1097
assert { E.div (- a) b = - q by (- q) * b <= - a < (- q) * b + b }
1098
end else begin
1099
assert { - a = (- q - 1) * b + (b - r) };
1100
assert { E.div (- a) b = - q - 1 by (- q - 1) * b <= - a < (- q - 1) * b + b }
1101
end {qed}

The floor remainder

  Valid (1.4s) (colibri2 3) (split_vc) (depth 1)
1104
let ghost
fmod_val
(a b:int) : unit
1105
requires { b <> 0 }
1106
ensures { a - fdiv a b * b = if b > 0 then E.mod a b else - E.mod (- a) (- b) }
1107
= {proof…} if b > 0 then assert { a = b * E.div a b + E.mod a b }
1108
else assert { - a = (- b) * E.div (- a) (- b) + E.mod (- a) (- b) } {qed}

E.mod of a small value

  Valid (37ms) (colibri2)
1111
let ghost
small_mod
(d p:int) : unit
1112
requires { 0 <= d < p }
1113
ensures { E.mod d p = d }
1114
= assert { E.div d p = 0 }

The absolute value of a signed bit–vector: abs_s of bvsmod

  Valid (372ms) (colibri2) (cvc5 12) (split_vc 2) (depth 2)
1117
let ghost
abs_val
(n x:int) : unit
1118
requires { 1 <= n /\ in_range n x }
1119
ensures { msb n x = 0 \/ msb n x = 1 }
1120
ensures { msb n x = 0 -> signed n x = x }
1121
ensures { msb n x = 1 -> bvneg n x = - signed n x /\ 0 < bvneg n x < power 2 n }
1122
ensures { 0 <= x < power 2 n }
1123
ensures { msb n x = 1 -> 0 < x }
1124
= {proof…} msb_val n x; signed_val n x; pow_lsl n; pow_pos n;
1125
if Zbit.bittest x (n - 1) then begin
1126
assert { x <> 0 by not (Zbit.bittest 0 (n - 1)) };
1127
assert { 0 < power 2 n - x < power 2 n };
1128
small_mod (power 2 n - x) (power 2 n);
1129
assert { E.mod (power 2 n - x) (power 2 n) = power 2 n - x }
1130
end {qed}

bvneg of a non–negative value below 2^n

  Valid (47ms) (colibri2)
1133
let ghost
neg_val
(n u:int) : unit
1134
requires { 1 <= n /\ 0 <= u < power 2 n }
1135
ensures { bvneg n u = E.mod (- u) (power 2 n) }
1136
= {proof…} pow_pos n;
1137
assert { power 2 n - u = power 2 n * 1 + (- u) };
1138
assert { E.mod (power 2 n * 1 + (- u)) (power 2 n) = E.mod (- u) (power 2 n) } {qed}

A value below 2^n is its own nat2bv

  Valid (41ms) (colibri2)
1141
let ghost
nat2bv_id
(n u:int) : unit
1142
requires { 1 <= n /\ 0 <= u < power 2 n }
1143
ensures { nat2bv n u = u }
1144
= ()
1145
Valid (1.7s) (colibri2 26) (cvc5) (split_vc 2) (depth 2)
1146
let ghost
op_sdiv
(n x y:int) : unit
1147
requires { 1 <= n /\ in_range n x /\ in_range n y }
1148
ensures { code (BvSdiv n) (Cons x (Cons y Nil)) = bvsdiv n x y }
1149
= {proof…} abs_val n x; abs_val n y;
1150
let p = power 2 n in
1151
pow_pos n; pow_lsl n;
1152
assert { p >= 2 by power 2 n = 2 * power 2 (n - 1) };
1153
let sa = signed n x in
1154
let sb = signed n y in
1155
ext_mod n 1; ext_mod n (-1);
1156
assert { E.mod 1 p = 1 /\ E.mod (-1) p = p - 1 };
1157
ones n;
1158
if y = 0 then begin
1159
msb_val n y;
1160
assert { msb n y = 0 };
1161
if msb n x = 1 then begin
1162
neg_val n (p - 1);
1163
assert { bvudiv n (bvneg n x) y = p - 1 };
1164
assert { sa < 0 }
1165
end
1166
end else begin
1167
let a = if msb n x = 0 then x else bvneg n x in
1168
let b = if msb n y = 0 then y else bvneg n y in
1169
assert { 0 <= a < p /\ 0 < b < p };
1170
assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };
1171
cdiv_signs a b;
1172
let q = E.div a b in
1173
assert { 0 <= q <= a by a = b * q + E.mod a b };
1174
nat2bv_ext n q; ext_mod n q;
1175
assert { bvudiv n a b = q };
1176
neg_val n q;
1177
ext_mod n (C.div sa sb);
1178
ext_mod n q
1179
end {qed}
1180
Valid (2.0s) (colibri2 22) (cvc4) (split_vc 4) (depth 3)
1181
let ghost
op_srem
(n x y:int) : unit
1182
requires { 1 <= n /\ in_range n x /\ in_range n y }
1183
ensures { code (BvSrem n) (Cons x (Cons y Nil)) = bvsrem n x y }
1184
= {proof…} abs_val n x; abs_val n y; bv_id n x;
1185
let p = power 2 n in
1186
pow_pos n;
1187
let sa = signed n x in
1188
let sb = signed n y in
1189
if y = 0 then begin
1190
msb_val n y;
1191
assert { msb n y = 0 };
1192
if msb n x = 1 then begin
1193
neg_val n (bvneg n x);
1194
assert { E.mod (- (p - x)) p = x by - (p - x) = p * (-1) + x }
1195
end
1196
end else begin
1197
let a = if msb n x = 0 then x else bvneg n x in
1198
let b = if msb n y = 0 then y else bvneg n y in
1199
assert { 0 <= a < p /\ 0 < b < p };
1200
assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };
1201
cdiv_signs a b;
1202
let r = E.mod a b in
1203
assert { 0 <= r < b };
1204
nat2bv_ext n r; ext_mod n r;
1205
assert { bvurem n a b = r };
1206
neg_val n r;
1207
ext_mod n (C.mod sa sb);
1208
ext_mod n r
1209
end {qed}
1210
Valid (2.3s) (colibri2 44) (cvc5 2) (split_vc 7) (depth 4)
1211
let ghost
op_smod
(n x y:int) : unit
1212
requires { 1 <= n /\ in_range n x /\ in_range n y }
1213
ensures { code (BvSmod n) (Cons x (Cons y Nil)) = bvsmod n x y }
1214
= {proof…} abs_val n x; abs_val n y; bv_id n x; bv_id n y;
1215
let p = power 2 n in
1216
pow_pos n;
1217
let sa = signed n x in
1218
let sb = signed n y in
1219
if y = 0 then begin
1220
msb_val n y;
1221
assert { msb n y = 0 };
1222
if msb n x = 1 then begin
1223
let a = bvneg n x in
1224
assert { bvurem n a y = a };
1225
neg_val n a;
1226
assert { E.mod (- (p - x)) p = x by - (p - x) = p * (-1) + x };
1227
nat2bv_id n x;
1228
assert { bvadd n (bvneg n a) y = x }
1229
end
1230
end else begin
1231
let a = if msb n x = 0 then x else bvneg n x in
1232
let b = if msb n y = 0 then y else bvneg n y in
1233
assert { 0 <= a < p /\ 0 < b < p };
1234
assert { sa = (if msb n x = 0 then a else - a) /\ sb = (if msb n y = 0 then b else - b) };
1235
assert { sb <> 0 };
1236
fmod_val sa sb;
1237
emod_neg a b;
1238
let r = E.mod a b in
1239
assert { 0 <= r < b };
1240
nat2bv_ext n r; ext_mod n r;
1241
assert { bvurem n a b = r };
1242
let f = sa - fdiv sa sb * sb in
1243
ext_mod n f;
1244
if r = 0 then begin
1245
assert { f = 0 };
1246
assert { E.mod 0 p = 0 }
1247
end else begin
1248
neg_val n r;
1249
if msb n x = 0 then begin
1250
if msb n y = 0 then begin
1251
assert { f = r }; nat2bv_id n r
1252
end else begin
1253
assert { f = r - b };
1254
assert { y = p - b by sb = y - p };
1255
assert { bvadd n r y = r - b + p by
1256
E.mod (r + y) p = r - b + p by r + y = p * 0 + (r - b + p) };
1257
assert { E.mod (r - b) p = r - b + p by r - b = p * (-1) + (r - b + p) }
1258
end
1259
end else begin
1260
if msb n y = 0 then begin
1261
assert { f = b - r };
1262
assert { bvneg n r = p - r by E.mod (- r) p = p - r by - r = p * (-1) + (p - r) };
1263
assert { bvadd n (bvneg n r) y = b - r by
1264
E.mod (p - r + b) p = b - r by p - r + b = p * 1 + (b - r) };
1265
nat2bv_id n (b - r)
1266
end else begin
1267
assert { f = - r };
1268
assert { bvneg n r = p - r by E.mod (- r) p = p - r by - r = p * (-1) + (p - r) };
1269
assert { E.mod (- r) p = p - r by - r = p * (-1) + (p - r) }
1270
end
1271
end
1272
end
1273
end {qed}

The recursive definitions

A bit–vector of size 1 is 0 or 1

  Valid (60ms) (colibri2)
1278
let ghost
range1
(a:int) : unit
1279
requires { in_range 1 a }
1280
ensures { a = 0 \/ a = 1 }
1281
ensures { Zbit.bittest a 0 <-> a = 1 }
1282
= {proof…} pow_lsl 1; assert { power 2 1 = 2 };
1283
assert { Zbit.bittest 1 0 };
1284
assert { not (Zbit.bittest 0 0) } {qed}
1285
Valid (694ms) (cvc4)
1286
let ghost
xnor1
(a b:int) : unit
1287
requires { in_range 1 a /\ in_range 1 b }
1288
ensures { bvxnor 1 a b = if a = b then 1 else 0 }
1289
= {proof…} range1 a; range1 b;
1290
let v = bvxnor 1 a b in
1291
assert { Zbit.bittest (bvnot 1 a) 0 <-> not (Zbit.bittest a 0) };
1292
assert { Zbit.bittest (bvnot 1 b) 0 <-> not (Zbit.bittest b 0) };
1293
assert { Zbit.bittest (bvand 1 a b) 0 <-> Zbit.bittest a 0 /\ Zbit.bittest b 0 };
1294
assert { Zbit.bittest (bvand 1 (bvnot 1 a) (bvnot 1 b)) 0 <->
1295
not (Zbit.bittest a 0) /\ not (Zbit.bittest b 0) };
1296
assert { Zbit.bittest v 0 <-> (Zbit.bittest a 0 <-> Zbit.bittest b 0) };
1297
in_range_bits 1 v;
1298
range1 v {qed}
1299
Valid (383ms) (colibri2)
1300
let ghost
and1
(a b:int) : unit
1301
requires { in_range 1 a /\ in_range 1 b }
1302
ensures { bvand 1 a b = if a = 1 /\ b = 1 then 1 else 0 }
1303
= {proof…} range1 a; range1 b;
1304
let v = bvand 1 a b in
1305
assert { Zbit.bittest v 0 <-> Zbit.bittest a 0 /\ Zbit.bittest b 0 };
1306
in_range_bits 1 v;
1307
range1 v {qed}

The low bits 0..i of s

  Valid (738ms) (cvc5)
1310
let ghost
low_bits
(i s:int) : unit
1311
requires { 0 <= i }
1312
ensures { in_range (i + 1) (extract i 0 s) }
1313
ensures { forall k. 0 <= k -> (Zbit.bittest (extract i 0 s) k <-> k <= i /\ Zbit.bittest s k) }
1314
= in_range_bits (i + 1) (extract i 0 s)
1315
Valid (364ms) (colibri2 22) (split_vc) (depth 1)
1316
let rec ghost
comp_val
(m s t:int) : unit
1317
requires { 1 <= m /\ in_range m s /\ in_range m t }
1318
variant { m }
1319
ensures { bvcomp m s t = if s = t then 1 else 0 }
1320
= {proof…} if m = 1 then begin
1321
range1 s; range1 t; xnor1 s t
1322
end else begin
1323
let hs = extract (m - 1) (m - 1) s in
1324
let ht = extract (m - 1) (m - 1) t in
1325
extract1 (m - 1) s; extract1 (m - 1) t;
1326
pow_lsl 1; assert { power 2 1 = 2 };
1327
assert { in_range 1 hs /\ in_range 1 ht };
1328
let ls = extract (m - 2) 0 s in
1329
let lt = extract (m - 2) 0 t in
1330
low_bits (m - 2) s; low_bits (m - 2) t;
1331
comp_val (m - 1) ls lt;
1332
xnor1 hs ht;
1333
let c = bvcomp (m - 1) ls lt in
1334
assert { in_range 1 c by c = 0 \/ c = 1 };
1335
and1 (bvxnor 1 hs ht) c;
1336
assert { bvcomp m s t = bvand 1 (bvxnor 1 hs ht) c };
1337
range_high m s; range_high m t;
1338
if hs = ht && ls = lt then begin
1339
let lemma bit (k:int) : unit
1340
requires { 0 <= k < m }
1341
ensures { Zbit.bittest s k <-> Zbit.bittest t k }
1342
= if k = m - 1 then () else
1343
assert { Zbit.bittest ls k <-> Zbit.bittest lt k } in
1344
same_bits m s t
1345
end else begin
1346
if s = t then absurd
1347
end
1348
end {qed}
1349
Valid (60ms) (colibri2)
1350
let ghost
op_comp
(n x y:int) : unit
1351
requires { 1 <= n /\ in_range n x /\ in_range n y }
1352
ensures { code (BvComp n) (Cons x (Cons y Nil)) = bvcomp n x y }
1353
= {proof…} bv_id n x; bv_id n y; comp_val n x y;
1354
ext_mod 1 (-1); assert { power 2 1 = 2 } {qed}

The bits of the loop of Sem.repeat

  Valid (163ms) (colibri2 10) (cvc5 2) (split_vc) (depth 1)
1357
let rec ghost
sem_repeat_bits
(n k a:int) : unit
1358
requires { 1 <= n /\ 0 <= k /\ in_range n a }
1359
variant { k }
1360
ensures { 0 <= Sem.repeat n k a }
1361
ensures { forall i. 0 <= i ->
1362
(Zbit.bittest (Sem.repeat n k a) i <-> i < n * k /\ Zbit.bittest a (E.mod i n)) }
1363
= {proof…} range_high n a;
1364
if k > 0 then begin
1365
sem_repeat_bits n (k - 1) a;
1366
let r = Sem.repeat n (k - 1) a in
1367
Zbit.lsl_mul r n;
1368
let lemma bit (i:int) : unit
1369
requires { 0 <= i }
1370
ensures { Zbit.bittest (Sem.repeat n k a) i <-> i < n * k /\ Zbit.bittest a (E.mod i n) }
1371
= Zbit.def_asr r (- n) i;
1372
if i < n then begin
1373
small_mod i n;
1374
Zbit.bittest_neg r (i - n)
1375
end else begin
1376
assert { i = n * 1 + (i - n) };
1377
assert { E.mod (n * 1 + (i - n)) n = E.mod (i - n) n }
1378
end in ()
1379
end {qed}

The bits of repeat

  Valid (702ms) (colibri2 15) (cvc5) (split_vc 3) (depth 3)
1382
let rec ghost
repeat_bits
(j m t:int) : unit
1383
requires { 1 <= m /\ 1 <= j /\ in_range m t }
1384
variant { j }
1385
ensures { in_range (m * j) (Smtlib.repeat j m t) }
1386
ensures { forall i. 0 <= i ->
1387
(Zbit.bittest (Smtlib.repeat j m t) i <-> i < m * j /\ Zbit.bittest t (E.mod i m)) }
1388
= {proof…} range_high m t;
1389
if j = 1 then begin
1390
let lemma bit (i:int) : unit
1391
requires { 0 <= i < m }
1392
ensures { E.mod i m = i }
1393
= small_mod i m in ()
1394
end else begin
1395
repeat_bits (j - 1) m t;
1396
let r = Smtlib.repeat (j - 1) m t in
1397
let c = concat m (m * (j - 1)) t r in
1398
let lemma bit (i:int) : unit
1399
requires { 0 <= i }
1400
ensures { Zbit.bittest c i <-> i < m * j /\ Zbit.bittest t (E.mod i m) }
1401
= if m * (j - 1) <= i < m * j then begin
1402
small_mod (i - m * (j - 1)) m;
1403
assert { i = m * (j - 1) + (i - m * (j - 1)) };
1404
assert { E.mod (m * (j - 1) + (i - m * (j - 1))) m = E.mod (i - m * (j - 1)) m }
1405
end in
1406
in_range_bits (m * j) c
1407
end {qed}
1408
Valid (685ms) (cvc5)
1409
let ghost
op_repeat
(n k x:int) : unit
1410
requires { 1 <= n /\ 1 <= k /\ in_range n x }
1411
ensures { code (BvRepeat n k) (Cons x Nil) = Smtlib.repeat k n x }
1412
= {proof…} bv_id n x;
1413
sem_repeat_bits n k x; repeat_bits k n x;
1414
in_range_bits (n * k) (Sem.repeat n k x);
1415
same_bits (n * k) (Sem.repeat n k x) (Smtlib.repeat k n x) {qed}

A bit–vector of size n is one of size n + k

  Valid (42ms) (colibri2)
1418
let ghost
range_up
(n k x:int) : unit
1419
requires { in_range n x /\ 0 <= k }
1420
ensures { in_range (n + k) x }
1421
= range_high n x; in_range_bits (n + k) x
1422
Valid (846ms) (colibri2 11) (cvc5) (split_vc) (depth 1)
1423
let ghost
op_zero_extend
(n k x:int) : unit
1424
requires { 1 <= n /\ 0 <= k /\ in_range n x }
1425
ensures { code (BvZeroExtend n k) (Cons x Nil) = zero_extend k n x }
1426
= {proof…} bv_id n x;
1427
if k > 0 then begin
1428
pow_lsl 1; assert { power 2 1 = 2 };
1429
repeat_bits k 1 0;
1430
let z = Smtlib.repeat k 1 0 in
1431
let c = concat k n z x in
1432
range_high n x;
1433
in_range_bits (k + n) c;
1434
range_up n k x;
1435
assert { not (Zbit.bittest 0 0) };
1436
same_bits (n + k) x c
1437
end {qed}
1438
Valid (1.2s) (colibri2 20) (cvc4) (cvc5 2) (split_vc) (depth 1)
1439
let ghost
op_sign_extend
(n k x:int) : unit
1440
requires { 1 <= n /\ 0 <= k /\ in_range n x }
1441
ensures { code (BvSignExtend n k) (Cons x Nil) = sign_extend k n x }
1442
= {proof…} bv_id n x; range_high n x;
1443
let e = extract (n - 1) (n - 1) x in
1444
extract1 (n - 1) x;
1445
let w = Zbit.lor (Zbit.lsl (-1) n) x in
1446
ext_bits (n + k) w; ext_range (n + k) w;
1447
let lemma wbit (i:int) : unit
1448
requires { 0 <= i }
1449
ensures { Zbit.bittest w i <-> if i < n then Zbit.bittest x i else true }
1450
= Zbit.def_asr (-1) (- n) i;
1451
if i >= n then SB.minus_one_bits (i - n) else Zbit.bittest_neg (-1) (i - n) in
1452
if k = 0 then begin
1453
if Zbit.bittest x (n - 1) then same_bits n (ext n w) x
1454
end else begin
1455
pow_lsl 1; assert { power 2 1 = 2 };
1456
assert { in_range 1 e };
1457
repeat_bits k 1 e;
1458
let c = concat k n (Smtlib.repeat k 1 e) x in
1459
in_range_bits (k + n) c;
1460
let lemma mod1 (i:int) : unit ensures { E.mod i 1 = 0 } = () in
1461
assert { Zbit.bittest e 0 <-> Zbit.bittest x (n - 1) };
1462
if Zbit.bittest x (n - 1) then same_bits (n + k) (ext (n + k) w) c
1463
else begin range_up n k x; same_bits (n + k) x c end
1464
end {qed}

The rotations, by the bits

  Valid (6.0s) (colibri2 20) (cvc4) (cvc5 2) (split_vc 4) (depth 3)
1467
let rec ghost
rotl_bits
(i m t:int) : unit
1468
requires { 1 <= m /\ 0 <= i /\ in_range m t }
1469
variant { i }
1470
ensures { in_range m (rotate_left i m t) }
1471
ensures { forall p. 0 <= p < m ->
1472
(Zbit.bittest (rotate_left i m t) p <-> Zbit.bittest t (E.mod (p - i) m)) }
1473
= {proof…} if i = 0 then begin
1474
let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p - i) m = p }
1475
= small_mod p m in ()
1476
end else if m = 1 then begin
1477
let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p - i) m = 0 = p }
1478
= () in ()
1479
end else begin
1480
let lo = extract (m - 2) 0 t in
1481
let hi = extract (m - 1) (m - 1) t in
1482
let u = concat (m - 1) 1 lo hi in
1483
low_bits (m - 2) t;
1484
in_range_bits m u;
1485
let lemma ubit (p:int) : unit
1486
requires { 0 <= p < m }
1487
ensures { Zbit.bittest u p <-> Zbit.bittest t (E.mod (p - 1) m) }
1488
= if p = 0 then begin
1489
assert { E.mod (-1) m = m - 1 by - 1 = m * (-1) + (m - 1) };
1490
small_mod (m - 1) m;
1491
assert { E.mod (m * (-1) + (m - 1)) m = E.mod (m - 1) m }
1492
end else small_mod (p - 1) m in
1493
rotl_bits (i - 1) m u;
1494
let lemma bit (p:int) : unit
1495
requires { 0 <= p < m }
1496
ensures { Zbit.bittest (rotate_left i m t) p <-> Zbit.bittest t (E.mod (p - i) m) }
1497
= let q = E.mod (p - (i - 1)) m in
1498
assert { 0 <= q < m };
1499
ubit q;
1500
mod_add (-1) (p - (i - 1)) m in ()
1501
end {qed}
1502
Valid (1.2s) (colibri2 18) (cvc5 4) (split_vc 4) (depth 3)
1503
let rec ghost
rotr_bits
(i m t:int) : unit
1504
requires { 1 <= m /\ 0 <= i /\ in_range m t }
1505
variant { i }
1506
ensures { in_range m (rotate_right i m t) }
1507
ensures { forall p. 0 <= p < m ->
1508
(Zbit.bittest (rotate_right i m t) p <-> Zbit.bittest t (E.mod (p + i) m)) }
1509
= {proof…} if i = 0 then begin
1510
let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p + i) m = p }
1511
= small_mod p m in ()
1512
end else if m = 1 then begin
1513
let lemma bit (p:int) : unit requires { 0 <= p < m } ensures { E.mod (p + i) m = 0 = p }
1514
= () in ()
1515
end else begin
1516
let lo = extract 0 0 t in
1517
let hi = extract (m - 1) 1 t in
1518
let u = concat 1 (m - 1) lo hi in
1519
assert { forall k. 0 <= k -> (Zbit.bittest hi k <-> k < m - 1 /\ Zbit.bittest t (1 + k)) };
1520
assert { forall k. 0 <= k -> (Zbit.bittest lo k <-> k < 1 /\ Zbit.bittest t k) };
1521
in_range_bits m u;
1522
let lemma ubit (p:int) : unit
1523
requires { 0 <= p < m }
1524
ensures { Zbit.bittest u p <-> Zbit.bittest t (E.mod (p + 1) m) }
1525
= if p = m - 1 then begin
1526
assert { E.mod m m = 0 by m = m * 1 + 0 }
1527
end else small_mod (p + 1) m in
1528
rotr_bits (i - 1) m u;
1529
let lemma bit (p:int) : unit
1530
requires { 0 <= p < m }
1531
ensures { Zbit.bittest (rotate_right i m t) p <-> Zbit.bittest t (E.mod (p + i) m) }
1532
= let q = E.mod (p + (i - 1)) m in
1533
assert { 0 <= q < m };
1534
ubit q;
1535
mod_add 1 (p + (i - 1)) m in ()
1536
end {qed}
1537
Valid (2.4s) (colibri2 34) (split_vc 3) (depth 3)
1538
let ghost
op_rotl
(n i x:int) : unit
1539
requires { 1 <= n /\ 0 <= i /\ in_range n x }
1540
ensures { code (BvRotl n i) (Cons x Nil) = rotate_left i n x }
1541
= {proof…} bv_id n x; range_high n x;
1542
rotl_bits i n x;
1543
let k = C.mod i n in
1544
cdiv_pos i n;
1545
assert { 0 <= k < n };
1546
let lemma md (p:int) : unit
1547
requires { 0 <= p < n }
1548
ensures { E.mod (p - i) n = E.mod (p - k) n }
1549
= assert { p - i = n * (- E.div i n) + (p - k) };
1550
assert { E.mod (n * (- E.div i n) + (p - k)) n = E.mod (p - k) n } in
1551
if k = 0 then begin
1552
ext_id n x;
1553
let lemma bit (p:int) : unit
1554
requires { 0 <= p < n }
1555
ensures { Zbit.bittest x p <-> Zbit.bittest (rotate_left i n x) p }
1556
= md p; small_mod p n in
1557
same_bits n x (rotate_left i n x)
1558
end else begin
1559
let w = Zbit.lor (Zbit.lsl x k) (z_extract x (n - k) k) in
1560
ext_bits n w; ext_range n w;
1561
let lemma bit (p:int) : unit
1562
requires { 0 <= p < n }
1563
ensures { Zbit.bittest (ext n w) p <-> Zbit.bittest (rotate_left i n x) p }
1564
= md p;
1565
Zbit.def_asr x (- k) p;
1566
Zbit.def_asr x (n - k) p;
1567
if p < k then begin
1568
Zbit.bittest_neg x (p - k);
1569
Zbit.mask_bits k p;
1570
assert { p - k = n * (-1) + (p - k + n) };
1571
assert { E.mod (n * (-1) + (p - k + n)) n = E.mod (p - k + n) n };
1572
small_mod (p - k + n) n
1573
end else begin
1574
Zbit.mask_bits_high k p;
1575
small_mod (p - k) n
1576
end in
1577
same_bits n (ext n w) (rotate_left i n x)
1578
end {qed}
1579
Valid (1.4s) (colibri2)
1580
let ghost
op_rotr
(n i x:int) : unit
1581
requires { 1 <= n /\ 0 <= i /\ in_range n x }
1582
ensures { code (BvRotr n i) (Cons x Nil) = rotate_right i n x }
1583
= {proof…} bv_id n x; range_high n x;
1584
rotr_bits i n x;
1585
let k = C.mod i n in
1586
cdiv_pos i n;
1587
assert { 0 <= k < n };
1588
let w = Zbit.lor (Zbit.lsl x (n - k)) (Zbit.asr x k) in
1589
ext_bits n w; ext_range n w;
1590
let lemma bit (p:int) : unit
1591
requires { 0 <= p < n }
1592
ensures { Zbit.bittest (ext n w) p <-> Zbit.bittest (rotate_right i n x) p }
1593
= assert { p + i = n * E.div i n + (p + k) };
1594
assert { E.mod (n * E.div i n + (p + k)) n = E.mod (p + k) n };
1595
Zbit.def_asr x (k - n) p;
1596
Zbit.def_asr x k p;
1597
if p + k < n then begin
1598
small_mod (p + k) n;
1599
Zbit.bittest_neg x (p + k - n)
1600
end else begin
1601
assert { p + k = n * 1 + (p + k - n) };
1602
assert { E.mod (n * 1 + (p + k - n)) n = E.mod (p + k - n) n };
1603
small_mod (p + k - n) n
1604
end in
1605
same_bits n (ext n w) (rotate_right i n x) {qed}

All the builtins

The SMT–LIB terms: sizes > 0, extract with 0 <= lo <= hi < n, repeat at least once, extensions and rotations by >= 0

1611
predicate
well_sorted
(b:builtin) =
1612
match b with
1613
| And | Or | Xor | Not | Asr | Extract | SignedExtract | Update | Test -> false
1614
| BvConcat n m -> 0 < n /\ 0 < m
1615
| BvExtract n lo hi -> 0 <= lo <= hi < n
1616
| BvRepeat n k -> 0 < n /\ 1 <= k
1617
| BvZeroExtend n k | BvSignExtend n k | BvRotl n k | BvRotr n k -> 0 < n /\ 0 <= k
1618
| Sbv2int n | Bv2nat n | Int2bv n
1619
| BvNot n | BvAnd n | BvOr n | BvXor n | BvNand n | BvNor n | BvXnor n | BvComp n
1620
| BvNeg n | BvAdd n | BvSub n | BvMul n | BvUdiv n | BvUrem n | BvSdiv n | BvSrem n
1621
| BvSmod n | BvShl n | BvLshr n | BvAshr n | BvUlt n | BvUle n | BvUgt n | BvUge n
1622
| BvSlt n | BvSle n | BvSgt n | BvSge n -> 0 < n
1623
end

The SMT–LIB semantics of a builtin applied to the values l (a Boolean is -1 or 0, as in code)

1627
function
smt
(b:builtin) (l:list int) : int =
1628
match b, l with
1629
| Sbv2int n, Cons x Nil -> sbv_to_int n x
1630
| Bv2nat _, Cons x Nil -> ubv_to_int x
1631
| Int2bv n, Cons x Nil -> int_to_bv n x
1632
| BvConcat n m, Cons x (Cons y Nil) -> concat n m x y
1633
| BvExtract _ lo hi, Cons x Nil -> extract hi lo x
1634
| BvRepeat n k, Cons x Nil -> Smtlib.repeat k n x
1635
| BvZeroExtend n k, Cons x Nil -> zero_extend k n x
1636
| BvSignExtend n k, Cons x Nil -> sign_extend k n x
1637
| BvRotl n i, Cons x Nil -> rotate_left i n x
1638
| BvRotr n i, Cons x Nil -> rotate_right i n x
1639
| BvNot n, Cons x Nil -> bvnot n x
1640
| BvAnd n, Cons x (Cons y Nil) -> bvand n x y
1641
| BvOr n, Cons x (Cons y Nil) -> bvor n x y
1642
| BvXor n, Cons x (Cons y Nil) -> bvxor n x y
1643
| BvNand n, Cons x (Cons y Nil) -> bvnand n x y
1644
| BvNor n, Cons x (Cons y Nil) -> bvnor n x y
1645
| BvXnor n, Cons x (Cons y Nil) -> bvxnor n x y
1646
| BvComp n, Cons x (Cons y Nil) -> bvcomp n x y
1647
| BvNeg n, Cons x Nil -> bvneg n x
1648
| BvAdd n, Cons x (Cons y Nil) -> bvadd n x y
1649
| BvSub n, Cons x (Cons y Nil) -> bvsub n x y
1650
| BvMul n, Cons x (Cons y Nil) -> bvmul n x y
1651
| BvUdiv n, Cons x (Cons y Nil) -> bvudiv n x y
1652
| BvUrem n, Cons x (Cons y Nil) -> bvurem n x y
1653
| BvSdiv n, Cons x (Cons y Nil) -> bvsdiv n x y
1654
| BvSrem n, Cons x (Cons y Nil) -> bvsrem n x y
1655
| BvSmod n, Cons x (Cons y Nil) -> bvsmod n x y
1656
| BvShl n, Cons x (Cons y Nil) -> bvshl n x y
1657
| BvLshr n, Cons x (Cons y Nil) -> bvlshr n x y
1658
| BvAshr n, Cons x (Cons y Nil) -> bvashr n x y
1659
| BvUlt _, Cons x (Cons y Nil) -> bool (bvult x y)
1660
| BvUle _, Cons x (Cons y Nil) -> bool (bvule x y)
1661
| BvUgt _, Cons x (Cons y Nil) -> bool (bvugt x y)
1662
| BvUge _, Cons x (Cons y Nil) -> bool (bvuge x y)
1663
| BvSlt n, Cons x (Cons y Nil) -> bool (bvslt n x y)
1664
| BvSle n, Cons x (Cons y Nil) -> bool (bvsle n x y)
1665
| BvSgt n, Cons x (Cons y Nil) -> bool (bvsgt n x y)
1666
| BvSge n, Cons x (Cons y Nil) -> bool (bvsge n x y)
1667
| _ -> code b l
1668
end

Sem.code, so the model check (Sem.eval), computes the SMT–LIB semantics of the well–sorted terms whose bit–vector arguments are in range

  Valid (1.7s) (cvc5)
1673
let ghost
code_is_smtlib
(b:builtin) (l:list int) : unit
1674
requires { well_sorted b /\ args_ok b l }
1675
ensures { code b l = smt b l }
1676
= {proof…} match b, l with
1677
| Sbv2int n, Cons x Nil -> op_sbv2int n x
1678
| Bv2nat n, Cons x Nil -> op_bv2nat n x
1679
| Int2bv n, Cons x Nil -> op_int2bv n x
1680
| BvConcat n m, Cons x (Cons y Nil) -> op_concat n m x y
1681
| BvExtract n lo hi, Cons x Nil -> op_extract n lo hi x
1682
| BvRepeat n k, Cons x Nil -> op_repeat n k x
1683
| BvZeroExtend n k, Cons x Nil -> op_zero_extend n k x
1684
| BvSignExtend n k, Cons x Nil -> op_sign_extend n k x
1685
| BvRotl n i, Cons x Nil -> op_rotl n i x
1686
| BvRotr n i, Cons x Nil -> op_rotr n i x
1687
| BvNot n, Cons x Nil -> op_not n x
1688
| BvAnd n, Cons x (Cons y Nil) -> op_and n x y
1689
| BvOr n, Cons x (Cons y Nil) -> op_or n x y
1690
| BvXor n, Cons x (Cons y Nil) -> op_xor n x y
1691
| BvNand n, Cons x (Cons y Nil) -> op_nand n x y
1692
| BvNor n, Cons x (Cons y Nil) -> op_nor n x y
1693
| BvXnor n, Cons x (Cons y Nil) -> op_xnor n x y
1694
| BvComp n, Cons x (Cons y Nil) -> op_comp n x y
1695
| BvNeg n, Cons x Nil -> op_neg n x
1696
| BvAdd n, Cons x (Cons y Nil) -> op_add n x y
1697
| BvSub n, Cons x (Cons y Nil) -> op_sub n x y
1698
| BvMul n, Cons x (Cons y Nil) -> op_mul n x y
1699
| BvUdiv n, Cons x (Cons y Nil) -> op_udiv n x y
1700
| BvUrem n, Cons x (Cons y Nil) -> op_urem n x y
1701
| BvSdiv n, Cons x (Cons y Nil) -> op_sdiv n x y
1702
| BvSrem n, Cons x (Cons y Nil) -> op_srem n x y
1703
| BvSmod n, Cons x (Cons y Nil) -> op_smod n x y
1704
| BvShl n, Cons x (Cons y Nil) -> op_shl n x y
1705
| BvLshr n, Cons x (Cons y Nil) -> op_lshr n x y
1706
| BvAshr n, Cons x (Cons y Nil) -> op_ashr n x y
1707
| (BvUlt n | BvUle n | BvUgt n | BvUge n | BvSlt n | BvSle n | BvSgt n | BvSge n),
1708
Cons x (Cons y Nil) -> op_cmp b n x y
1709
| _ -> ()
1710
end {qed}
1711
end