library colibrilib.known_bits — module RangeThe 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).
module Range636use int.Int637use int.MinMax638use option.Option639use colibrilib.zarith.Zbit640use colibrilib.zbit.ZbitInt641use colibrilib.safe_bits.SafeBits642use colibrilib.lowbits.LowBits643use colibrilib.spec.Sound644use KnownBits645
No carry between two integers without common bits
Valid (103ms) (colibri2)let rec ghost no_carry_disj (a b i:int) : unit648requires { 0 <= i }649requires { forall j. not (Zbit.bittest a j /\ Zbit.bittest b j) }650variant { i }651ensures { not (Zbit.carry a b i) }652= {proof…} if i > 0 then begin653no_carry_disj a b (i - 1);654Zbit.carry_succ a b (i - 1)655end {qed}656
The sum of two integers without common bits is their union
Valid (98ms) (colibri2)let ghost add_disj (a b:int) : unit659requires { forall j. not (Zbit.bittest a j /\ Zbit.bittest b j) }660ensures { a + b = Zbit.lor a b }661= {proof…} let lemma bit (i:int) : unit662requires { 0 <= i }663ensures { Zbit.bittest (a + b) i <-> Zbit.bittest (Zbit.lor a b) i }664= no_carry_disj a b i; Zbit.bittest_add a b i in665Zbit.ext_bittest (a + b) (Zbit.lor a b) {qed}666
The bits above the nb bits are the sign
Valid (83ms) (colibri2)let ghost sign_bits (x:int) : int669ensures { 0 <= result }670ensures { forall i. result <= i -> (Zbit.bittest x i <-> x < 0) }671= {proof…} let i = max 0 (nb x) in672let lemma high (j:int) : unit673requires { i <= j }674ensures { Zbit.bittest x j <-> x < 0 }675= SafeBits.bittest_high x j in676i {qed}677
0 <= r < 2^(k+1): the bit k of r is 2^k <= r
Valid (111ms) (colibri2)let ghost top_bit (r k:int) : unit680requires { 0 <= k }681requires { 0 <= r < Zbit.lsl 1 (k + 1) }682ensures { Zbit.bittest r k <-> Zbit.lsl 1 k <= r }683= {proof…} Zbit.numbits_lsl k;684Zbit.numbits_lt_lsl r (k + 1);685if Zbit.lsl 1 k <= r then begin686Zbit.numbits_ge_pos (Zbit.lsl 1 k) r;687Zbit.numbits_top_bit r688end else begin689Zbit.numbits_lt_lsl r k;690if r > 0 then Zbit.numbits_high_clear r k691end {qed}692
The low part of n bits and the high part
Valid (174ms) (colibri2 22) (cvc5) (split_vc) (depth 1)let ghost split (x n:int) : unit695requires { 0 <= n }696ensures { x = Zbit.asr x n * Zbit.lsl 1 n + Zbit.land (Zbit.mask n) x }697ensures { 0 <= Zbit.land (Zbit.mask n) x < Zbit.lsl 1 n }698ensures { forall i. 0 <= i < n ->699(Zbit.bittest (Zbit.land (Zbit.mask n) x) i <-> Zbit.bittest x i) }700= {proof…} let r = Zbit.land (Zbit.mask n) x in701Zbit.mask_nonneg n;702Zbit.land_nonneg_l (Zbit.mask n) x;703let lemma r_high (i:int) : unit704requires { n <= i }705ensures { not (Zbit.bittest r i) }706= Zbit.mask_bits_high n i in707if r >= Zbit.lsl 1 n then begin708Zbit.numbits_lsl n;709Zbit.numbits_ge_pos (Zbit.lsl 1 n) r;710Zbit.numbits_top_bit r711end;712let h = Zbit.asr x n in713let lemma bits_r (i:int) : unit714requires { 0 <= i < n }715ensures { Zbit.bittest r i <-> Zbit.bittest x i }716= Zbit.mask_bits n i in717let lemma bits_h (i:int) : unit718ensures { Zbit.bittest (Zbit.lsl h n) i <-> (n <= i /\ Zbit.bittest x i) }719= if i - n < 0 then Zbit.bittest_neg h (i - n) in720add_disj (Zbit.lsl h n) r;721let lemma bit (i:int) : unit722requires { 0 <= i }723ensures { Zbit.bittest (Zbit.lor (Zbit.lsl h n) r) i <-> Zbit.bittest x i }724= if i < n then bits_r i in725Zbit.ext_bittest (Zbit.lor (Zbit.lsl h n) r) x;726LowBits.lsl_mul h n {qed}727
The high part grows with the integer
Valid (40ms) (colibri2 3) (cvc5) (split_vc) (depth 1)let ghost asr_mono (x y n:int) : unit730requires { 0 <= n }731requires { x <= y }732ensures { Zbit.asr x n <= Zbit.asr y n }733= {proof…} split x n;734split y n;735let p = Zbit.lsl 1 n in736let hx = Zbit.asr x n in737let hy = Zbit.asr y n in738if hx > hy then739assert { (hx - hy - 1) * p >= 0 by hx - hy - 1 >= 0 /\ p > 0 } {qed}740
A subset of the same sign is smaller
Valid (1.1s) (colibri2)let ghost subset_le (a b:int) : unit743requires { Zbit.subset a b }744requires { a < 0 <-> b < 0 }745ensures { a <= b }746= {proof…} let d = Zbit.land b (Zbit.lnot a) in747let lemma disj (j:int) : unit748ensures { not (Zbit.bittest a j /\ Zbit.bittest d j) }749= if j < 0 then Zbit.bittest_neg a j in750add_disj a d;751let lemma bit (i:int) : unit752requires { 0 <= i }753ensures { Zbit.bittest (Zbit.lor a d) i <-> Zbit.bittest b i }754= () in755Zbit.ext_bittest (Zbit.lor a d) b;756let i = max (sign_bits a) (max (sign_bits b) (sign_bits d)) in757assert { Zbit.bittest d i <-> Zbit.bittest b i /\ not Zbit.bittest a i };758assert { 0 <= d } {qed}759
A subset of a negative integer is negative
Valid (112ms) (colibri2)let ghost subset_sign (a b:int) : unit762requires { Zbit.subset a b }763ensures { a < 0 -> b < 0 }764= {proof…} let i = max (sign_bits a) (sign_bits b) in765assert { Zbit.bittest a i -> Zbit.bittest b i } {qed}766
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)let of_range (a b:int) : t771ensures { includes mem (fun x -> a <= x <= b) result }772= if a > b || (a < 0 && 0 <= b) then begin top_all a; top end773else begin774let c = Zbit.lxor a b in775let ghost i0 = max (sign_bits a) (max (sign_bits b) (sign_bits c)) in776assert { Zbit.bittest c i0 <-> not (Zbit.bittest a i0 <-> Zbit.bittest b i0) };777assert { 0 <= c };778let n = Zbit.numbits c in779if c > 0 then begin780Zbit.numbits_top_bit c;781assert { 0 <= n - 1 by Zbit.bittest c (n - 1) }782end;783assert { 0 <= n };784let lemma high (i:int) : unit785requires { n <= i }786ensures { Zbit.bittest a i <-> Zbit.bittest b i }787= if c > 0 then Zbit.numbits_high_clear c i788else assert { not (Zbit.bittest c i) } in789let lemma asr_bit (i:int) : unit790requires { 0 <= i }791ensures { Zbit.bittest (Zbit.asr a n) i <-> Zbit.bittest (Zbit.asr b n) i }792= high (i + n) in793Zbit.ext_bittest (Zbit.asr a n) (Zbit.asr b n);794let m = Zbit.lnot (ZbitInt.mask_int n) in795let lemma m_bit (i:int) : unit796requires { 0 <= i }797ensures { Zbit.bittest m i <-> n <= i }798= if i < n then Zbit.mask_bits n i else Zbit.mask_bits_high n i in799let lemma inside (x:int) : unit800requires { a <= x <= b }801ensures { forall i. 0 <= i -> Zbit.bittest m i ->802(Zbit.bittest x i <-> Zbit.bittest a i) }803= asr_mono a x n;804asr_mono x b n;805let lemma bit (i:int) : unit806requires { n <= i }807ensures { Zbit.bittest x i <-> Zbit.bittest a i }808= assert { Zbit.bittest (Zbit.asr x n) (i - n) <-> Zbit.bittest (Zbit.asr a n) (i - n) } in809() in810cst_mask a m811end812
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)let bounds (k:t) : option (int, int)816ensures { match result with817| None -> 0 <= k.u /\ k.l < 0818| Some (lo, hi) -> forall x. mem x k -> lo <= x <= hi819end }820= if 0 <= k.u && k.l < 0 then None821else begin822let lemma inside (x:int) : unit823requires { mem x k }824ensures { k.u <= x <= k.l }825= subset_sign k.u x;826subset_sign x k.l;827subset_sign k.u k.l;828subset_le k.u x;829subset_le x k.l in830Some (k.u, k.l)831end832
The bit k of z is given by the low part of k+1 bits
Valid (85ms) (colibri2)let ghost bit_k (z k:int) : unit835requires { 0 <= k }836ensures { Zbit.bittest z k <-> Zbit.lsl 1 k <= Zbit.land (Zbit.mask (k + 1)) z }837= {proof…} split z (k + 1);838top_bit (Zbit.land (Zbit.mask (k + 1)) z) k {qed}839
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)let next (k:int) (b:bool) (x:int) : int842ensures { forall z. x <= z -> (Zbit.bittest z k <-> b) -> result <= z }843= if k < 0 || k > SafeBits.bound then x844else if (if ZbitInt.test_bit_int x k then b else not b) then x845else begin846let p = ZbitInt.lsl_int 1 k in847let pp = ZbitInt.lsl_int 1 (k + 1) in848LowBits.lsl_dbl 1 k;849let blk = Zbit.land x (Zbit.lnot (ZbitInt.mask_int (k + 1))) in850split x (k + 1);851bit_k x k;852let ghost h = Zbit.asr x (k + 1) in853let ghost r = Zbit.land (Zbit.mask (k + 1)) x in854let lemma blk_eq (_:unit) : unit855ensures { blk = h * pp }856= let lemma disj (j:int) : unit857ensures { not (Zbit.bittest blk j /\ Zbit.bittest r j) }858= if j < 0 then Zbit.bittest_neg blk j in859add_disj blk r;860let lemma bit (i:int) : unit861requires { 0 <= i }862ensures { Zbit.bittest (Zbit.lor blk r) i <-> Zbit.bittest x i }863= () in864Zbit.ext_bittest (Zbit.lor blk r) x in865blk_eq ();866let res = if b then blk + p else blk + pp in867let lemma above (z:int) : unit868requires { x <= z }869requires { Zbit.bittest z k <-> b }870ensures { res <= z }871= split z (k + 1);872bit_k z k;873asr_mono x z (k + 1);874let hz = Zbit.asr z (k + 1) in875if hz > h then876assert { (hz - h - 1) * pp >= 0 by hz - h - 1 >= 0 /\ pp > 0 } in877res878end879
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)let prev (k:int) (b:bool) (x:int) : int882ensures { forall z. z <= x -> (Zbit.bittest z k <-> b) -> z <= result }883= if k < 0 || k > SafeBits.bound then x884else if (if ZbitInt.test_bit_int x k then b else not b) then x885else begin886let p = ZbitInt.lsl_int 1 k in887let ghost pp = Zbit.lsl 1 (k + 1) in888LowBits.lsl_dbl 1 k;889let blk = Zbit.land x (Zbit.lnot (ZbitInt.mask_int (k + 1))) in890split x (k + 1);891bit_k x k;892let ghost h = Zbit.asr x (k + 1) in893let ghost r = Zbit.land (Zbit.mask (k + 1)) x in894let lemma blk_eq (_:unit) : unit895ensures { blk = h * pp }896= let lemma disj (j:int) : unit897ensures { not (Zbit.bittest blk j /\ Zbit.bittest r j) }898= if j < 0 then Zbit.bittest_neg blk j in899add_disj blk r;900let lemma bit (i:int) : unit901requires { 0 <= i }902ensures { Zbit.bittest (Zbit.lor blk r) i <-> Zbit.bittest x i }903= () in904Zbit.ext_bittest (Zbit.lor blk r) x in905blk_eq ();906let res = if b then blk - 1 else blk + p - 1 in907let lemma below (z:int) : unit908requires { z <= x }909requires { Zbit.bittest z k <-> b }910ensures { z <= res }911= split z (k + 1);912bit_k z k;913asr_mono z x (k + 1);914let hz = Zbit.asr z (k + 1) in915if hz < h then916assert { (h - hz - 1) * pp >= 0 by h - hz - 1 >= 0 /\ pp > 0 } in917res918end919end920