Common — library colibrilib.bitwise_rules — module Intervals

The known bits of the interval of a node in its bit–level term

837
module Intervals
838
use int.Int
839
use real.FromInt
840
use option.Option
841
use colibrilib.q.Real as Real
842
use colibrilib.known_bits.KnownBits
843
use colibrilib.zarith.Zbit
844
use colibrilib.zbit.ZbitInt
845
use colibrilib.bdd.Node
846
use colibrilib.ibdd.IBDD
847
use colibrilib.bddbitv.Export
848
use colibrilib.env.Env
849
use colibrilib.safe_bits.BitsSpec
850
use colibrilib.safe_bits.SafeBits
851
use colibrilib.sbdd.SNode
852
use colibrilib.spec.Defines
853
use list.List
854
use mach.int.Int63
855
use colibrilib.bddbitv.IBDDS as S
856
use colibrilib.bv_sem.Sem
857
use colibrilib.kb_interval.KbInterval as KI
858
use Term
859
use TermInterval

The known bits of the interval of the node (Dom_genrelbitv.bitmask_of_interval)

  Valid (101ms) (colibri2)
863
let
known_bits
(d:env) (n:Node.t) : KnownBits.t
864
ensures { live d -> KnownBits.mem (ienv d n) result }
865
raises { Contradiction -> not live d }
866
= match interval d n with
867
| None -> KnownBits.top
868
| Some u ->
869
match KI.known_bits (use_domain d) u with
870
| Some k -> k
871
| None ->
872
{proof…}
873
assert { live d -> Real.is_integer (from_int (ienv d n)) };
874
{qed}
875
raise Contradiction
876
end
877
end

The known bits of the interval of n in its term: n = u lor (l land n), on the unbounded integer term of n. Not on the term of its size: the size can come from the interval itself (TermSize.size), and then the equation is the term and says nothing to the term of n in the domain, which keeps the size of its type (a 12–bit i in [0;1023]: its two high bits stay unknown, and bvlshr i 2 too)

  Valid (1.7s) (colibri2 10) (cvc4 3) (split_vc) (depth 1)
886
let partial
bits_of_interval
(d:env) (n:Node.t) : unit
887
raises { Contradiction -> not live d }
888
raises { Unsupported -> false }
889
raises { Overflow -> false }
890
= let kb = known_bits d n in
891
if not (KnownBits.is_top kb) then begin
892
let x = monome_sized d n None in
893
try
894
let cu = int_cst kb.u in
895
let cl = int_cst kb.l in
896
let low = int_logand cl x in
897
let t = int_logor cu low in
898
let lemma ok (_:unit) : unit
899
requires { live d }
900
ensures { ienv d n = ivalue t (ienv d) }
901
= let en = ienv d n in
902
assert { ivalue x (ienv d) = en };
903
assert { ivalue cu (ienv d) = kb.u };
904
assert { ivalue cl (ienv d) = kb.l };
905
assert { ivalue low (ienv d) = Zbit.land kb.l en };
906
let v = Zbit.lor kb.u (Zbit.land kb.l en) in
907
assert { ivalue t (ienv d) = v };
908
assert { KnownBits.mem en kb };
909
let lemma b (i:int) : unit
910
requires { 0 <= i }
911
ensures { Zbit.bittest v i <-> Zbit.bittest en i }
912
= () in
913
Zbit.ext_bittest v en in
914
if not (same t x) then assume_equality d n t
915
with Unsupported -> () | Overflow -> () end
916
end
917
end