library colibrilib.safe_bits — module SafeBitsTotal versions. Each operation has a core version that requires that the result is not too big (a predicate whose name ends with ok) and the exported version that raises TooBig exactly when this predicate is false.
module SafeBits105use int.Int106use int.MinMax107use colibrilib.zarith.Zbit108use colibrilib.zbit.ZbitInt109use BitsSpec110use colibrilib.spec.Value111112exception TooBig113
Largest left shift or field length we agree to build
let constant bound : int = 1073741824116
lnot x is non negative when x is negative
Valid (67ms) (colibri2)let lemma lnot_nonneg (x:int) : unit119requires { x < 0 }120ensures { 0 <= Zbit.lnot x }121= let s = Zbit.numbits (-x) in122Zbit.numbits_top_bit (-x);123if s < 1 then Zbit.bittest_neg (-x) (s-1);124assert { s >= 1 };125Zbit.numbits_lsl_lt (-x);126let z = x + Zbit.lsl 1 s in127assert { z - Zbit.lsl 1 s = x };128Zbit.mask_nonneg s;129let w = Zbit.land (Zbit.mask s) (Zbit.lnot x) in130Zbit.land_nonneg_l (Zbit.mask s) (Zbit.lnot x);131let lemma bit (i:int) : unit132requires { 0 <= i }133ensures { Zbit.bittest (Zbit.lnot x) i <-> Zbit.bittest w i }134= if i < s then Zbit.mask_bits s i135else begin136Zbit.mask_bits_high s i;137Zbit.bittest_sub_lsl_high z s i138end in139Zbit.ext_bittest (Zbit.lnot x) w140
Number of bits that are not the sign extension
Valid (28ms) (colibri2)let function nb (x:int) : int143= if x < 0 then (lnot_nonneg x; Zbit.numbits (Zbit.lnot x)) else Zbit.numbits x144
Above nb x all the bits are the sign
Valid (81ms) (colibri2)let lemma bittest_high (x i:int) : unit147requires { 0 <= i }148requires { nb x <= i }149ensures { Zbit.bittest x i <-> x < 0 }150= if x > 0 then Zbit.numbits_high_clear x i151else if x = 0 then ()152else begin153lnot_nonneg x;154let y = Zbit.lnot x in155if y > 0 then Zbit.numbits_high_clear y i156end157Valid (36ms) (colibri2)158let lemma minus_one_bits (j:int) : unit159requires { 0 <= j }160ensures { Zbit.bittest (-1) j }161= Zbit.asr_eq 1;162Zbit.bittest_sub_lsl_high 0 0 j163
Shifting does not change the sign
Valid (360ms) (cvc5)let lemma sign_shift (off a y:int) : unit166requires { forall i. 0 <= i -> Zbit.bittest y i <-> Zbit.bittest a (i + off) }167ensures { y < 0 <-> a < 0 }168= let n = max (nb y) (nb a) + (if off < 0 then - off else off) in169bittest_high y n;170bittest_high a (n + off)171
Shift right (Zbit.asr); to the left if off is negative
let predicate shift_ok (off a:int) = off >= - bound || a = 0175Valid (470ms) (colibri2)176let shift_right (off a:int) : int177requires { shift_ok off a }178ensures { value_is (Zbit.asr a off) result }179= let r =180if off >= 0 then begin181if off >= nb a then (if a < 0 then -1 else 0) else ZbitInt.asr_int a off182end183else if a = 0 then 0184else ZbitInt.lsl_int a (-off) in185let lemma bit (i:int) : unit186requires { 0 <= i }187ensures { Zbit.bittest r i <-> Zbit.bittest (Zbit.asr a off) i }188= if off >= 0 && off >= nb a then bittest_high a (i + off) in189Zbit.ext_bittest r (Zbit.asr a off);190r191
BitsSpec.extract
let predicate extract_ok (off len a:int) =195len <= 0 || off <= - len || (shift_ok off a && (len <= bound || a >= 0))196Valid (65ms) (colibri2 10) (split_vc) (depth 1)197let extract (off len a:int) : int198requires { extract_ok off len a }199ensures { value_is (BitsSpec.extract off len a) result }200= if len <= 0 then 0201else if off <= - len then begin202let lemma bit (i:int) : unit203requires { 0 <= i }204ensures { Zbit.bittest (BitsSpec.extract off len a) i <-> Zbit.bittest 0 i }205= () in206Zbit.ext_bittest 0 (BitsSpec.extract off len a);2070208end209else begin210let y = shift_right off a in211sign_shift off a y;212if y >= 0 && len >= nb y then begin213let lemma bit (i:int) : unit214requires { 0 <= i }215ensures { Zbit.bittest y i <-> Zbit.bittest (BitsSpec.extract off len a) i }216= if i >= len then bittest_high y i in217Zbit.ext_bittest y (BitsSpec.extract off len a);218y219end else Zbit.land y (ZbitInt.mask_int len)220end221
BitsSpec.sext
Valid (409ms) (colibri2)let sext (y n:int) : int225requires { n > 0 }226ensures { value_is (BitsSpec.sext y n) result }227= if n > nb y then begin228let lemma bit (i:int) : unit229requires { 0 <= i }230ensures { Zbit.bittest y i <-> Zbit.bittest (BitsSpec.sext y n) i }231= if i >= n - 1 then (bittest_high y i; bittest_high y (n - 1)) in232Zbit.ext_bittest y (BitsSpec.sext y n);233y234end else begin235let m = ZbitInt.mask_int n in236if ZbitInt.test_bit_int y (n - 1) then Zbit.lor (Zbit.land y m) (Zbit.lnot m)237else Zbit.land y m238end239
Signed extraction of the specification BitsSpec
let predicate signed_extract_ok (off len:int) =242(if off < 0 then len + off else len) <= 0 || off >= - bound243Valid (341ms) (colibri2)244let signed_extract (off len a:int) : int245requires { signed_extract_ok off len }246ensures { value_is (BitsSpec.signed_extract off len a) result }247= BitsSpec.signed_extract_alg_eq off len a;248let n = if off < 0 then len + off else len in249if n <= 0 then 0250else begin251let y = shift_right (if off < 0 then 0 else off) a in252let s = sext y n in253if off >= 0 then (Zbit.asr_eq s; s) else ZbitInt.lsl_int s (- off)254end255
BitsSpec.update
let predicate update_ok (off len:int) = len <= 0 || (len <= bound && off <= bound)259Valid (45ms) (colibri2)260let update (off len src dst:int) : int261requires { update_ok off len }262ensures { value_is (BitsSpec.update off len src dst) result }263= if len <= 0 then dst264else begin265let m = ZbitInt.mask_int len in266let hole = shift_right (- off) m in267let part = shift_right (- off) (Zbit.land src m) in268Zbit.lor (Zbit.land dst (Zbit.lnot hole)) part269end270271end272