library colibrilib.safe_bits — module BitsSpecThe definitions. A negative offset shifts to the left
module BitsSpec7use int.Int8use int.MinMax9use colibrilib.zarith.Zbit10
The len bits of x from the position off, as a non negative integer
function extract (off len x:int) : int =13if len <= 0 then 0 else Zbit.land (Zbit.asr x off) (Zbit.mask len)14
The n lowest bits of y, sign extended from the highest one
function sext (y n:int) : int =17if Zbit.bittest y (n - 1) then Zbit.lor (Zbit.land y (Zbit.mask n)) (Zbit.lnot (Zbit.mask n))18else Zbit.land y (Zbit.mask n)19
The len bits of x from the position off (the bits at negative positions are 0, as for Zbit.bittest), sign extended from the highest one
function signed_extract (off len x:int) : int =24if len <= 0 then 025else if Zbit.bittest x (off + len - 1) then Zbit.lor (extract off len x) (Zbit.lnot (Zbit.mask len))26else extract off len x27
The algorithm of the implementation (equal to the specification by a lemma below).
function signed_extract_alg (off len x:int) : int =30let n = if off < 0 then len + off else len in31if n <= 0 then 0 else Zbit.lsl (sext (Zbit.asr x (max off 0)) n) (max (- off) 0)32
dst where the len bits from the position off are replaced by the len lowest bits of src
function update (off len src dst:int) : int =36if len <= 0 then dst37else Zbit.lor (Zbit.land dst (Zbit.lnot (Zbit.lsl (Zbit.mask len) off)))38(Zbit.lsl (Zbit.land src (Zbit.mask len)) off)39Valid (33ms) (colibri2)40let lemma mask_field (len i:int) : unit41requires { 0 <= len }42ensures { Zbit.bittest (Zbit.mask len) i <-> 0 <= i < len }43= if i < 0 then Zbit.bittest_neg (Zbit.mask len) i44else if i < len then Zbit.mask_bits len i45else Zbit.mask_bits_high len i46Valid (48ms) (colibri2)47let lemma bit_extract (off len x i:int) : unit48requires { 0 <= i }49ensures { Zbit.bittest (extract off len x) i <-> (i < len /\ Zbit.bittest x (i + off)) }50= if len > 0 then mask_field len i51Valid (148ms) (colibri2)52let lemma bit_sext (y n i:int) : unit53requires { 0 <= i /\ 0 < n }54ensures { Zbit.bittest (sext y n) i <-> Zbit.bittest y (min i (n - 1)) }55= mask_field n i56Valid (221ms) (colibri2)57let lemma bit_signed_extract (off len x i:int) : unit58requires { 0 <= i }59ensures { Zbit.bittest (signed_extract off len x) i <->60(len > 0 /\ Zbit.bittest x (off + min i (len - 1))) }61= if len > 0 then begin62mask_field len i;63bit_extract off len x i;64if i >= len then bit_extract off len x (len - 1)65end6667function sx_len (off len:int) : int = if off < 0 then len + off else len68function sx_pos (off len i:int) : int =69if off >= 0 then off + min i (len - 1) else min (i + off) (len + off - 1)70predicate sx_on (off len i:int) = sx_len off len > 0 /\ (off >= 0 \/ i >= - off)71Valid (166ms) (cvc5)72let lemma bit_signed_extract_alg (off len x i:int) : unit73requires { 0 <= i }74ensures { Zbit.bittest (signed_extract_alg off len x) i <->75(sx_on off len i /\ Zbit.bittest x (sx_pos off len i)) }76= let n = sx_len off len in77if n > 0 then begin78let y = Zbit.asr x (max off 0) in79let s = sext y n in80if i >= max (- off) 0 then bit_sext y n (i - max (- off) 0)81else Zbit.bittest_neg s (i - max (- off) 0)82end83
The algorithm of the implementation computes the specification
Valid (790ms) (colibri2)let lemma signed_extract_alg_eq (off len x:int) : unit86ensures { signed_extract_alg off len x = signed_extract off len x }87= let lemma bit (i:int) : unit88requires { 0 <= i }89ensures { Zbit.bittest (signed_extract_alg off len x) i <-> Zbit.bittest (signed_extract off len x) i }90= bit_signed_extract off len x i; bit_signed_extract_alg off len x i;91if off < 0 && len > 0 && len + off <= 0 then Zbit.bittest_neg x (off + min i (len - 1)) in92Zbit.ext_bittest (signed_extract_alg off len x) (signed_extract off len x)93Valid (1.6s) (cvc4)94let lemma bit_update (off len src dst i:int) : unit95requires { 0 <= i }96ensures { Zbit.bittest (update off len src dst) i <->97(if len > 0 /\ off <= i < off + len then Zbit.bittest src (i - off) else Zbit.bittest dst i) }98= if len > 0 then mask_field len (i - off)99end100