Common — library colibrilib.known_bits — module Range

The known bits of an interval of integers, and the intervals of the known bits (used by colibri2/theories/LRA/dom_genrelbitv.ml and converter.ml to go from the domain of intervals to the known bits and back).

636
module Range
637
use int.Int
638
use int.MinMax
639
use option.Option
640
use colibrilib.zarith.Zbit
641
use colibrilib.zbit.ZbitInt
642
use colibrilib.safe_bits.SafeBits
643
use colibrilib.lowbits.LowBits
644
use colibrilib.spec.Sound
645
use KnownBits

No carry between two integers without common bits

  Valid (103ms) (colibri2)
648
let rec ghost
no_carry_disj
(a b i:int) : unit
649
requires { 0 <= i }
650
requires { forall j. not (Zbit.bittest a j /\ Zbit.bittest b j) }
651
variant { i }
652
ensures { not (Zbit.carry a b i) }
653
= {proof…} if i > 0 then begin
654
no_carry_disj a b (i - 1);
655
Zbit.carry_succ a b (i - 1)
656
end {qed}

The sum of two integers without common bits is their union

  Valid (98ms) (colibri2)
659
let ghost
add_disj
(a b:int) : unit
660
requires { forall j. not (Zbit.bittest a j /\ Zbit.bittest b j) }
661
ensures { a + b = Zbit.lor a b }
662
= {proof…} let lemma bit (i:int) : unit
663
requires { 0 <= i }
664
ensures { Zbit.bittest (a + b) i <-> Zbit.bittest (Zbit.lor a b) i }
665
= no_carry_disj a b i; Zbit.bittest_add a b i in
666
Zbit.ext_bittest (a + b) (Zbit.lor a b) {qed}

The bits above the nb bits are the sign

  Valid (83ms) (colibri2)
669
let ghost
sign_bits
(x:int) : int
670
ensures { 0 <= result }
671
ensures { forall i. result <= i -> (Zbit.bittest x i <-> x < 0) }
672
= {proof…} let i = max 0 (nb x) in
673
let lemma high (j:int) : unit
674
requires { i <= j }
675
ensures { Zbit.bittest x j <-> x < 0 }
676
= SafeBits.bittest_high x j in
677
i {qed}

0 <= r < 2^(k+1): the bit k of r is 2^k <= r

  Valid (111ms) (colibri2)
680
let ghost
top_bit
(r k:int) : unit
681
requires { 0 <= k }
682
requires { 0 <= r < Zbit.lsl 1 (k + 1) }
683
ensures { Zbit.bittest r k <-> Zbit.lsl 1 k <= r }
684
= {proof…} Zbit.numbits_lsl k;
685
Zbit.numbits_lt_lsl r (k + 1);
686
if Zbit.lsl 1 k <= r then begin
687
Zbit.numbits_ge_pos (Zbit.lsl 1 k) r;
688
Zbit.numbits_top_bit r
689
end else begin
690
Zbit.numbits_lt_lsl r k;
691
if r > 0 then Zbit.numbits_high_clear r k
692
end {qed}

The low part of n bits and the high part

  Valid (174ms) (colibri2 22) (cvc5) (split_vc) (depth 1)
695
let ghost
split
(x n:int) : unit
696
requires { 0 <= n }
697
ensures { x = Zbit.asr x n * Zbit.lsl 1 n + Zbit.land (Zbit.mask n) x }
698
ensures { 0 <= Zbit.land (Zbit.mask n) x < Zbit.lsl 1 n }
699
ensures { forall i. 0 <= i < n ->
700
(Zbit.bittest (Zbit.land (Zbit.mask n) x) i <-> Zbit.bittest x i) }
701
= {proof…} let r = Zbit.land (Zbit.mask n) x in
702
Zbit.mask_nonneg n;
703
Zbit.land_nonneg_l (Zbit.mask n) x;
704
let lemma r_high (i:int) : unit
705
requires { n <= i }
706
ensures { not (Zbit.bittest r i) }
707
= Zbit.mask_bits_high n i in
708
if r >= Zbit.lsl 1 n then begin
709
Zbit.numbits_lsl n;
710
Zbit.numbits_ge_pos (Zbit.lsl 1 n) r;
711
Zbit.numbits_top_bit r
712
end;
713
let h = Zbit.asr x n in
714
let lemma bits_r (i:int) : unit
715
requires { 0 <= i < n }
716
ensures { Zbit.bittest r i <-> Zbit.bittest x i }
717
= Zbit.mask_bits n i in
718
let lemma bits_h (i:int) : unit
719
ensures { Zbit.bittest (Zbit.lsl h n) i <-> (n <= i /\ Zbit.bittest x i) }
720
= if i - n < 0 then Zbit.bittest_neg h (i - n) in
721
add_disj (Zbit.lsl h n) r;
722
let lemma bit (i:int) : unit
723
requires { 0 <= i }
724
ensures { Zbit.bittest (Zbit.lor (Zbit.lsl h n) r) i <-> Zbit.bittest x i }
725
= if i < n then bits_r i in
726
Zbit.ext_bittest (Zbit.lor (Zbit.lsl h n) r) x;
727
LowBits.lsl_mul h n {qed}

The high part grows with the integer

  Valid (40ms) (colibri2 3) (cvc5) (split_vc) (depth 1)
730
let ghost
asr_mono
(x y n:int) : unit
731
requires { 0 <= n }
732
requires { x <= y }
733
ensures { Zbit.asr x n <= Zbit.asr y n }
734
= {proof…} split x n;
735
split y n;
736
let p = Zbit.lsl 1 n in
737
let hx = Zbit.asr x n in
738
let hy = Zbit.asr y n in
739
if hx > hy then
740
assert { (hx - hy - 1) * p >= 0 by hx - hy - 1 >= 0 /\ p > 0 } {qed}

A subset of the same sign is smaller

  Valid (1.1s) (colibri2)
743
let ghost
subset_le
(a b:int) : unit
744
requires { Zbit.subset a b }
745
requires { a < 0 <-> b < 0 }
746
ensures { a <= b }
747
= {proof…} let d = Zbit.land b (Zbit.lnot a) in
748
let lemma disj (j:int) : unit
749
ensures { not (Zbit.bittest a j /\ Zbit.bittest d j) }
750
= if j < 0 then Zbit.bittest_neg a j in
751
add_disj a d;
752
let lemma bit (i:int) : unit
753
requires { 0 <= i }
754
ensures { Zbit.bittest (Zbit.lor a d) i <-> Zbit.bittest b i }
755
= () in
756
Zbit.ext_bittest (Zbit.lor a d) b;
757
let i = max (sign_bits a) (max (sign_bits b) (sign_bits d)) in
758
assert { Zbit.bittest d i <-> Zbit.bittest b i /\ not Zbit.bittest a i };
759
assert { 0 <= d } {qed}

A subset of a negative integer is negative

  Valid (112ms) (colibri2)
762
let ghost
subset_sign
(a b:int) : unit
763
requires { Zbit.subset a b }
764
ensures { a < 0 -> b < 0 }
765
= {proof…} let i = max (sign_bits a) (sign_bits b) in
766
assert { Zbit.bittest a i -> Zbit.bittest b i } {qed}

Known bits containing the integers of [a, b]: the bits above the highest bit where a and b differ, when a and b have the same sign

  Valid (479ms) (colibri2 29) (cvc5) (split_vc 4) (depth 2)
771
let
of_range
(a b:int) : t
772
ensures { includes mem (fun x -> a <= x <= b) result }
773
= if a > b || (a < 0 && 0 <= b) then begin top_all a; top end
774
else begin
775
let c = Zbit.lxor a b in
776
let ghost i0 = max (sign_bits a) (max (sign_bits b) (sign_bits c)) in
777
assert { Zbit.bittest c i0 <-> not (Zbit.bittest a i0 <-> Zbit.bittest b i0) };
778
assert { 0 <= c };
779
let n = Zbit.numbits c in
780
if c > 0 then begin
781
Zbit.numbits_top_bit c;
782
assert { 0 <= n - 1 by Zbit.bittest c (n - 1) }
783
end;
784
assert { 0 <= n };
785
let lemma high (i:int) : unit
786
requires { n <= i }
787
ensures { Zbit.bittest a i <-> Zbit.bittest b i }
788
= if c > 0 then Zbit.numbits_high_clear c i
789
else assert { not (Zbit.bittest c i) } in
790
let lemma asr_bit (i:int) : unit
791
requires { 0 <= i }
792
ensures { Zbit.bittest (Zbit.asr a n) i <-> Zbit.bittest (Zbit.asr b n) i }
793
= high (i + n) in
794
Zbit.ext_bittest (Zbit.asr a n) (Zbit.asr b n);
795
let m = Zbit.lnot (ZbitInt.mask_int n) in
796
let lemma m_bit (i:int) : unit
797
requires { 0 <= i }
798
ensures { Zbit.bittest m i <-> n <= i }
799
= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in
800
let lemma inside (x:int) : unit
801
requires { a <= x <= b }
802
ensures { forall i. 0 <= i -> Zbit.bittest m i ->
803
(Zbit.bittest x i <-> Zbit.bittest a i) }
804
= asr_mono a x n;
805
asr_mono x b n;
806
let lemma bit (i:int) : unit
807
requires { n <= i }
808
ensures { Zbit.bittest x i <-> Zbit.bittest a i }
809
= assert { Zbit.bittest (Zbit.asr x n) (i - n) <-> Zbit.bittest (Zbit.asr a n) (i - n) } in
810
() in
811
cst_mask a m
812
end

The bounds of the integers of k, unless k has a non negative lower bound of the bits and a negative upper bound (both signs)

  Valid (112ms) (colibri2)
816
let
bounds
(k:t) : option (int, int)
817
ensures { match result with
818
| None -> 0 <= k.u /\ k.l < 0
819
| Some (lo, hi) -> forall x. mem x k -> lo <= x <= hi
820
end }
821
= if 0 <= k.u && k.l < 0 then None
822
else begin
823
let lemma inside (x:int) : unit
824
requires { mem x k }
825
ensures { k.u <= x <= k.l }
826
= subset_sign k.u x;
827
subset_sign x k.l;
828
subset_sign k.u k.l;
829
subset_le k.u x;
830
subset_le x k.l in
831
Some (k.u, k.l)
832
end

The bit k of z is given by the low part of k+1 bits

  Valid (85ms) (colibri2)
835
let ghost
bit_k
(z k:int) : unit
836
requires { 0 <= k }
837
ensures { Zbit.bittest z k <-> Zbit.lsl 1 k <= Zbit.land (Zbit.mask (k + 1)) z }
838
= {proof…} split z (k + 1);
839
top_bit (Zbit.land (Zbit.mask (k + 1)) z) k {qed}

The smallest integer from x on whose bit k is b (a lower bound)

  Valid (121ms) (colibri2 19) (cvc5 4) (split_vc 4) (depth 2)
842
let next (k:int) (b:bool) (x:int) : int
843
ensures { forall z. x <= z -> (Zbit.bittest z k <-> b) -> result <= z }
844
= if k < 0 || k > SafeBits.bound then x
845
else if (if ZbitInt.test_bit_int x k then b else not b) then x
846
else begin
847
let p = ZbitInt.lsl_int 1 k in
848
let pp = ZbitInt.lsl_int 1 (k + 1) in
849
LowBits.lsl_dbl 1 k;
850
let blk = Zbit.land x (Zbit.lnot (ZbitInt.mask_int (k + 1))) in
851
split x (k + 1);
852
bit_k x k;
853
let ghost h = Zbit.asr x (k + 1) in
854
let ghost r = Zbit.land (Zbit.mask (k + 1)) x in
855
let lemma blk_eq (_:unit) : unit
856
ensures { blk = h * pp }
857
= let lemma disj (j:int) : unit
858
ensures { not (Zbit.bittest blk j /\ Zbit.bittest r j) }
859
= if j < 0 then Zbit.bittest_neg blk j in
860
add_disj blk r;
861
let lemma bit (i:int) : unit
862
requires { 0 <= i }
863
ensures { Zbit.bittest (Zbit.lor blk r) i <-> Zbit.bittest x i }
864
= () in
865
Zbit.ext_bittest (Zbit.lor blk r) x in
866
blk_eq ();
867
let res = if b then blk + p else blk + pp in
868
let lemma above (z:int) : unit
869
requires { x <= z }
870
requires { Zbit.bittest z k <-> b }
871
ensures { res <= z }
872
= split z (k + 1);
873
bit_k z k;
874
asr_mono x z (k + 1);
875
let hz = Zbit.asr z (k + 1) in
876
if hz > h then
877
assert { (hz - h - 1) * pp >= 0 by hz - h - 1 >= 0 /\ pp > 0 } in
878
res
879
end

The greatest integer up to x whose bit k is b (an upper bound)

  Valid (129ms) (colibri2 17) (cvc5 4) (split_vc 3) (depth 2)
882
let prev (k:int) (b:bool) (x:int) : int
883
ensures { forall z. z <= x -> (Zbit.bittest z k <-> b) -> z <= result }
884
= if k < 0 || k > SafeBits.bound then x
885
else if (if ZbitInt.test_bit_int x k then b else not b) then x
886
else begin
887
let p = ZbitInt.lsl_int 1 k in
888
let ghost pp = Zbit.lsl 1 (k + 1) in
889
LowBits.lsl_dbl 1 k;
890
let blk = Zbit.land x (Zbit.lnot (ZbitInt.mask_int (k + 1))) in
891
split x (k + 1);
892
bit_k x k;
893
let ghost h = Zbit.asr x (k + 1) in
894
let ghost r = Zbit.land (Zbit.mask (k + 1)) x in
895
let lemma blk_eq (_:unit) : unit
896
ensures { blk = h * pp }
897
= let lemma disj (j:int) : unit
898
ensures { not (Zbit.bittest blk j /\ Zbit.bittest r j) }
899
= if j < 0 then Zbit.bittest_neg blk j in
900
add_disj blk r;
901
let lemma bit (i:int) : unit
902
requires { 0 <= i }
903
ensures { Zbit.bittest (Zbit.lor blk r) i <-> Zbit.bittest x i }
904
= () in
905
Zbit.ext_bittest (Zbit.lor blk r) x in
906
blk_eq ();
907
let res = if b then blk - 1 else blk + p - 1 in
908
let lemma below (z:int) : unit
909
requires { z <= x }
910
requires { Zbit.bittest z k <-> b }
911
ensures { z <= res }
912
= split z (k + 1);
913
bit_k z k;
914
asr_mono z x (k + 1);
915
let hz = Zbit.asr z (k + 1) in
916
if hz < h then
917
assert { (h - hz - 1) * pp >= 0 by h - hz - 1 >= 0 /\ pp > 0 } in
918
res
919
end
920
end