library colibrilib.bddbitv — module Exportmodule Export5195
Implemented
use colibrilib.spec.Eval5196use colibrilib.spec.Sound5197use colibrilib.spec.Value5198use colibrilib.spec.Test5199use int.Int5200use colibrilib.bdd.NodeSet5201use int.EuclideanDivision as E5202use int.ComputerDivision as C5203use colibrilib.int63.Int635204use option.Option5205use set.Set5206use colibrilib.bdd.Node5207use colibrilib.sbdd.SNode5208use colibrilib.pbdd.PBDD5209use colibrilib.pbdd.PBDD25210use colibrilib.zarith.Zbit5211use colibrilib.zbit.ZbitInt5212use colibrilib.ibdd.IBDD5213use IBDDS5214use Modulo5215use list.List5216use list.Mem52175218exception Unsupported5219
The aliases below are the definitions of colibrilib/ibdd.mlw and colibrilib/bddbitv.mlw: go to their definition to stay in this module. The integers are the infinite integers of Why3, with two's complement bits: the functions Zbit.land, Zbit.lor, Zbit.lxor, Zbit.lnot, Zbit.lsl, Zbit.asr, Zbit.mask and the predicate bittest are the bitwise operations of the (mathematical) integers, Zbit.numbits x is the number of bits of |x|.
A term (an ibdd): the bits of a window of 2^size positions and a tail giving the bits above. Its bit p is a function of the snodes read at p.
The snode {n; s} read at the position p is the bit p + s of the integer env n (false below 0): sem env p is the valuation of the snodes at p for the values env of the nodes.
function sem (env: Node.t -> int) : PBDD2.env = IBDD.sem env5238
The bit p >= 0 of a term for the snodes sn read at p
function bit (t: t) (p: int) (sn: snodes) : bool = IBDD.bit t p sn5241
The value of a term without tail (a bounded bit–vector, non–negative) for the values env of the nodes: its bit p is bit t p (sem env p)
function value (t: t) (env: Node.t -> int) : int = IBDD.value t env5245
z is the (possibly negative) integer whose bits are the bits of t, for the values env of the nodes
predicate is_value (t: t) (env: Node.t -> int) (z: int) = IBDD.is_value t env z5249
The value of a term for the values env of the nodes. It exists and is unique (is_value_iff): two integers with the same bits are equal
Valid (41ms) (colibri2) (split_vc) (depth 1)let ghost function ivalue (t: t) (env: Node.t -> int) : int5253ensures { is_value t env result } =5254IBDD.value_exists t env5255Valid (67ms) (colibri2 2) (split_vc) (depth 1)5256let lemma is_value_iff (t: t) (env: Node.t -> int) (z: int) : unit5257ensures { is_value t env z <-> z = ivalue t env }5258= if pure { is_value t env z } then Zbit.ext_bittest z (ivalue t env)5259
SMT–LIB extract and update on integers (total)
function iextract (x pos len: int) : int =5262if len <= 0 then 0 else Zbit.land (Zbit.asr x pos) (Zbit.mask len)5263function iupdate (dst pos len src: int) : int =5264if len <= 0 then dst5265else Zbit.lor (Zbit.land dst (Zbit.lnot (Zbit.lsl (Zbit.mask len) pos)))5266(Zbit.lsl (Zbit.land src (Zbit.mask len)) pos)5267Valid (888ms) (colibri2)5268let lemma bittest_iextract (x pos len i: int) : unit5269requires { 0 <= i }5270ensures { Zbit.bittest (iextract x pos len) i <-> (i < len /\ Zbit.bittest x (pos + i)) }5271= if len > 0 then begin5272if i < len then Zbit.mask_bits len i else Zbit.mask_bits_high len i5273end5274Valid (3.4s) (colibri2 12) (cvc5) (split_vc 7) (depth 5)5275let lemma bittest_iupdate (dst pos len src i: int) : unit5276requires { 0 <= i }5277ensures { Zbit.bittest (iupdate dst pos len src) i <->5278(if pos <= i < pos + len then Zbit.bittest src (i - pos) else Zbit.bittest dst i) }5279= if len > 0 then begin5280Zbit.mask_nonneg len;5281if i >= pos then begin5282if i - pos < len then Zbit.mask_bits len (i - pos) else Zbit.mask_bits_high len (i - pos)5283end5284end5285
The term has a tail that is not false (it is not a bounded bit–vector)
predicate tailed (t: t) = IBDD.tailed t5288
The snodes ({n; s}) in the window or in the tail of a term
function all_snodes (t: t) : snodes = IBDD.all_snodes t5291
The snodes in the domain of the window, and the snodes on which the window really depends
function dom_snodes (t: t) : snodes = t.bdd.PBDD.dom_snodes5295function support (t: t) : snodes = PBDD.support_snodes t.bdd5296
Stable name for the extracted type
type solve_result = IBDDS.solve5299type int_solve_result = IBDDS.isolve5300Valid (186ms) (colibri2)5301let partial bv_cst (x:int) : t5302ensures { dom_snodes result = Set.empty }5303ensures { denotes0 value (fun _ -> x) result }5304ensures { not (tailed result) }5305raises { Unsupported -> x < 0 \/ Zbit.numbits x > Int63.max_int }5306= if 0 <= x && Zbit.numbits x <= to_int Int63.max_int then IBDD.cst x5307else raise Unsupported5308Valid (110ms) (colibri2)5309let bv_is_cst (x: t) : option int5310ensures { denotes_cst value x result }5311ensures { match result with5312| Some z -> forall env. value x env = z5313| None -> not (Set.is_empty (support x))5314end }5315raises { Unsupported -> x.size > 61 \/ tailed x }5316= if IBDD.has_tail x then raise Unsupported5317else if x.size <= 61 then begin5318lsl_le_max_int (to_int x.size);5319IBDD.is_cst x5320end else raise Unsupported5321Valid (468ms) (colibri2 10) (split_vc) (depth 1)5322let partial bv_lognot (size: int63) (t: t) : t5323ensures { dom_snodes result = dom_snodes t \/ size = 0 }5324ensures { denotes1 value (fun x -> Zbit.land (Zbit.lnot x) (Zbit.mask size)) t result }5325ensures { not (tailed result) }5326raises { Unsupported -> size < 0 \/ tailed t }5327= if size < 0 || IBDD.has_tail t then raise Unsupported5328else if size = 0 then begin5329let r = IBDD.zero () in5330let lemma eq (env: Node.t -> int) : unit5331ensures { value r env = Zbit.land (Zbit.lnot (value t env)) (Zbit.mask size) }5332= ext_bittest (value r env) pure { land (lnot (value t env)) (mask size) }5333in5334r5335end else IBDD.lognot size t5336Valid (218ms) (colibri2)5337let partial bv_monome (sz: int63) (n: Node.t) : t5338ensures { dom_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }5339ensures { denotes0 value (fun env -> Zbit.land (Zbit.mask sz) (env n)) result }5340ensures { not (tailed result) }5341raises { Unsupported -> sz < 0 }5342= if sz < 0 then raise Unsupported else IBDD.monome sz n5343Valid (112ms) (colibri2 12) (split_vc) (depth 1)5344let partial bv_shift_left (off: int) (sz: int63) (t: t) : t5345ensures { denotes1 value (fun x -> Zbit.land (Zbit.lsl x off) (Zbit.mask sz)) t result }5346ensures { not (tailed result) }5347raises { Unsupported -> off < 0 \/ sz < 0 \/ tailed t }5348raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }5349= if off < 0 || sz < 0 || IBDD.has_tail t then raise Unsupported5350else if off >= to_int sz then begin5351let r = IBDD.zero () in5352let lemma eq (env: Node.t -> int) : unit5353ensures { value r env = Zbit.land (Zbit.lsl (value t env) off) (Zbit.mask sz) }5354=5355let lemma bit (p: int) : unit5356requires { 0 <= p }5357ensures { not (bittest (Zbit.land (Zbit.lsl (value t env) off) (Zbit.mask sz)) p) }5358= if p < to_int sz then def_asr (value t env) (- off) p5359in5360ext_bittest (value r env) pure { land (lsl (value t env) off) (mask sz) }5361in5362r5363end else IBDDS.shift_left (Int63.of_int off) sz t5364Valid (812ms) (colibri2 14) (split_vc) (depth 1)5365let partial bv_shift_right (off: int) (sz: int63) (t: t) : t5366ensures { denotes1 value (fun x -> Zbit.asr (Zbit.land x (Zbit.mask sz)) off) t result }5367ensures { not (tailed result) }5368raises { Unsupported -> off < 0 \/ sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }5369raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }5370= if off < 0 || sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported5371else if off >= to_int sz then begin5372let r = IBDD.zero () in5373let lemma eq (env: Node.t -> int) : unit5374ensures { value r env = Zbit.asr (Zbit.land (value t env) (Zbit.mask sz)) off }5375=5376let lemma bit (p: int) : unit5377requires { 0 <= p }5378ensures { not (bittest (Zbit.asr (Zbit.land (value t env) (Zbit.mask sz)) off) p) }5379= def_asr pure { land (value t env) (mask sz) } off p5380in5381ext_bittest (value r env) pure { asr (land (value t env) (mask sz)) off }5382in5383r5384end else IBDDS.shift_right (Int63.of_int off) sz t5385Valid (374ms) (colibri2 17) (cvc4) (cvc5) (split_vc) (depth 1)5386let partial bv_arith_shift_right (off: int) (sz: int63) (t: t) : t5387ensures { denotes1 value (fun x -> Zbit.land (Zbit.asr (sext sz x) off) (Zbit.mask sz)) t result }5388ensures { not (tailed result) }5389raises { Unsupported -> off < 0 \/ sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }5390raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ 0 <= k <= off /\5391not (in_bounds (to_int nd.s + k)) }5392= if off < 0 || sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported5393else if sz = 0 then begin5394let r = IBDD.zero () in5395let lemma eq (env: Node.t -> int) : unit5396ensures { value r env = Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz) }5397= ext_bittest (value r env) pure { land (asr (sext sz (value t env)) off) (mask sz) }5398in5399r5400end else begin5401let off' = if off >= to_int sz then sz else Int63.of_int off in5402let r = IBDDS.arith_shift_right off' sz t in5403let lemma eq (env: Node.t -> int) : unit5404ensures { value r env = Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz) }5405=5406let lemma bit (p: int) : unit5407requires { 0 <= p }5408ensures { bittest (Zbit.land (Zbit.asr (sext sz (value t env)) off') (Zbit.mask sz)) p <->5409bittest (Zbit.land (Zbit.asr (sext sz (value t env)) off) (Zbit.mask sz)) p }5410=5411def_asr pure { sext sz (value t env) } (to_int off') p;5412def_asr pure { sext sz (value t env) } off p;5413sext_bit (to_int sz) (value t env) (p + to_int off');5414sext_bit (to_int sz) (value t env) (p + off)5415in5416ext_bittest pure { land (asr (sext sz (value t env)) off') (mask sz) }5417pure { land (asr (sext sz (value t env)) off) (mask sz) }5418in5419r5420end5421Valid (729ms) (colibri2 11) (split_vc) (depth 1)5422let partial bv_sign_extend (from sz: int63) (t: t) : t5423ensures { denotes1 value (fun x -> Zbit.land (sext from x) (Zbit.mask sz)) t result }5424ensures { not (tailed result) }5425raises { Unsupported -> from < 0 \/ sz < from \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }5426raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ from - sz <= k < 0 /\5427not (in_bounds (to_int nd.s + k)) }5428= if from < 0 || sz < from || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported5429else if from = 0 then begin5430let r = IBDD.zero () in5431let lemma eq (env: Node.t -> int) : unit5432ensures { value r env = Zbit.land (sext from (value t env)) (Zbit.mask sz) }5433= ext_bittest (value r env) pure { land (sext from (value t env)) (mask sz) }5434in5435r5436end else IBDDS.sign_extend from sz t5437Valid (372ms) (colibri2 12) (split_vc) (depth 1)5438let partial bv_rotate_right (off sz: int63) (t: t) : t5439ensures { denotes1 value (fun x -> rotr sz (E.mod off sz) x) t result }5440ensures { not (tailed result) }5441raises { Unsupported -> sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }5442raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ - sz <= k <= sz /\5443not (in_bounds (to_int nd.s - k)) }5444= if sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported5445else if sz = 0 then begin5446let r = IBDD.zero () in5447let lemma eq (env: Node.t -> int) : unit5448ensures { value r env = rotr sz (E.mod off sz) (value t env) }5449= ext_bittest (value r env) pure { rotr sz (E.mod off sz) (value t env) }5450in5451r5452end else IBDDS.rotate_right (bv_modulo off sz) sz t5453Valid (709ms) (colibri2 18) (cvc5 3) (split_vc) (depth 1)5454let partial bv_rotate_left (off sz: int63) (t: t) : t5455ensures { denotes1 value (fun x -> rotr sz (E.mod (- to_int off) sz) x) t result }5456ensures { not (tailed result) }5457raises { Unsupported -> sz < 0 \/ to_int sz + to_int sz > Int63.max_int \/ tailed t }5458raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ - sz <= k <= sz /\5459not (in_bounds (to_int nd.s - k)) }5460= if sz < 0 || sz > Int63.max_int - sz || IBDD.has_tail t then raise Unsupported5461else if sz = 0 then begin5462let r = IBDD.zero () in5463let lemma eq (env: Node.t -> int) : unit5464ensures { value r env = rotr sz (E.mod (- to_int off) sz) (value t env) }5465= ext_bittest (value r env) pure { rotr sz (E.mod (- to_int off) sz) (value t env) }5466in5467r5468end else begin5469let o = bv_modulo off sz in5470let ghost o' = if o = 0 then 0 else to_int sz - to_int o in5471let ghost d = E.div (to_int off) (to_int sz) in5472assert { to_int off = d * sz + o };5473if o = 0 then begin5474assert { (- d) * sz <= - to_int off < (- d) * sz + sz };5475assert { E.div (- to_int off) sz = - d };5476assert { - to_int off = sz * (- d) + E.mod (- to_int off) sz }5477end else begin5478assert { (- d - 1) * sz <= - to_int off < (- d - 1) * sz + sz };5479assert { E.div (- to_int off) sz = - d - 1 };5480assert { - to_int off = sz * (- d - 1) + E.mod (- to_int off) sz }5481end;5482assert { E.mod (- to_int off) sz = o' };5483IBDDS.rotate_left o sz t5484end5485Valid (331ms) (cvc4)5486let partial bv_extract (i j: int63) (t: t) : t5487ensures { denotes1 value5488(fun x -> if j < i then 0 else Zbit.land (Zbit.asr x i) (Zbit.mask (j - i + 1)))5489t result }5490ensures { not (tailed result) }5491raises { Unsupported -> i < 0 \/ tailed t \/ (i <= j /\ (j = Int63.max_int \/ t.size > 61 \/5492Zbit.lsl 1 t.size + to_int i > Int63.max_int)) }5493raises { Overflow -> exists nd. Set.mem nd (dom_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + i)) }5494= if i < 0 || IBDD.has_tail t then raise Unsupported5495else if j < i then begin5496let r = IBDD.zero () in5497let lemma eq (env: Node.t -> int) : unit5498ensures { value r env = 0 }5499= ext_bittest (value r env) 05500in5501r5502end else if j = Int63.max_int || t.size > 61 then raise Unsupported5503else begin5504lsl_le_max_int (to_int t.size);5505if Int63.lsl 1 t.size > Int63.max_int - i then raise Unsupported;5506IBDDS.extract i j t5507end5508Valid (70ms) (cvc5)5509let lemma mul_le (x y z: int) : unit5510requires { x <= y /\ 0 <= z }5511ensures { x * z <= y * z }5512= ()5513Valid (839ms) (colibri2 14) (cvc4) (cvc5) (split_vc) (depth 1)5514let partial bv_repeat [@spec:none "bit level: the bit p is the bit p - k * from of t, k < n"] (from n: int63) (t: t) : t5515ensures { forall env p. bittest (value result env) p <->5516exists k. 0 <= k < n /\ k * from <= p < k * from + from /\5517bittest (value t env) (p - k * from) }5518raises { Unsupported -> from < 0 \/ n < 0 \/ tailed t \/5519to_int from * to_int n + to_int from * to_int n > Int63.max_int }5520raises { Overflow -> exists nd k. Set.mem nd (dom_snodes t) /\ 0 < k < from * n /\5521not (in_bounds (to_int nd.s - k)) }5522= if from < 0 || n < 0 || IBDD.has_tail t then raise Unsupported5523else if from = 0 || n = 0 then begin5524let r = IBDD.zero () in5525let lemma bit (env: Node.t -> int) (p: int) : unit5526ensures { not (bittest (value r env) p) }5527= ext_bittest (value r env) 05528in5529r5530end else begin5531let m = Int63.max_int / 2 in5532let q = m / n in5533assert { to_int m = to_int q * n + C.mod (to_int m) (to_int n) /\55340 <= C.mod (to_int m) (to_int n) < n };5535if from > q then begin5536assert { (to_int from - to_int q - 1) * n >= 0 };5537raise Unsupported5538end;5539mul_le (to_int from) (to_int q) (to_int n);5540IBDDS.repeat from n t5541end5542Valid (86ms) (colibri2)5543let bv_compute (env: Node.t -> int) (t: t) : int5544ensures { denotes_at value t env result }5545raises { Unsupported -> t.size > 61 \/ tailed t }5546= if t.size > 61 || IBDD.has_tail t then raise Unsupported;5547lsl_le_max_int (to_int t.size);5548IBDDS.compute env t5549
The known bits (known0, known1) hold v: the bits of known1 are set in v, the bits of v are in known0
predicate kb_mem (v: int) (k: (int, int)) =5553let (k0, k1) = k in Zbit.subset k1 v /\ Zbit.subset v k05554Valid (94ms) (colibri2)5555let partial bv_to_knownbits (t: t) : (int, int)5556ensures { denotes_in value kb_mem t result }5557raises { Unsupported -> t.size > 61 \/ tailed t }5558= if t.size > 61 || IBDD.has_tail t then raise Unsupported;5559lsl_le_max_int (to_int t.size);5560IBDDS.to_knownbits t5561
The functions without precondition
Valid (104ms) (colibri2)let bv_zero () : t5564ensures { denotes0 value (fun _ -> 0) result }5565= IBDD.zero ()5566Valid (71ms) (colibri2)5567let bv_is_zero (t: t) : bool5568ensures { decides (forall p sn. 0 <= p -> not (bit t p sn)) result }5569= IBDD.is_zero_t t55705571let function bv_size (t: t) : int63 = t.size5572Valid (80ms) (colibri2) (split_vc) (depth 1)5573let bv_nodes (t: t) : NodeSet.t5574ensures { exact (fun n (r: NodeSet.t) -> Set.mem n r.NodeSet.elts) (fun n -> exists s a. Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (support t) \/5575Set.mem { SNode.n = n; SNode.s = s; SNode.scal = a } (support_snodes t.tail)) result }5576= IBDD.nodes t5577Valid (964ms) (colibri2)5578let partial bv_logand (t1 t2: t) : t5579ensures { denotes2 value Zbit.land t1 t2 result }5580ensures { not (tailed result) }5581raises { Unsupported -> tailed t1 \/ tailed t2 }5582= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported5583else IBDD.logand t1 t25584Valid (983ms) (colibri2)5585let partial bv_logor (t1 t2: t) : t5586ensures { denotes2 value Zbit.lor t1 t2 result }5587ensures { not (tailed result) }5588raises { Unsupported -> tailed t1 \/ tailed t2 }5589= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported5590else IBDD.logor t1 t25591Valid (1.0s) (colibri2)5592let partial bv_xor (t1 t2: t) : t5593ensures { denotes2 value Zbit.lxor t1 t2 result }5594ensures { not (tailed result) }5595raises { Unsupported -> tailed t1 \/ tailed t2 }5596= if IBDD.has_tail t1 || IBDD.has_tail t2 then raise Unsupported5597else IBDD.xor t1 t25598Valid (68ms) (colibri2 3) (split_vc) (depth 1)5599let partial bv_solve [@spec:none "solver: Zero, Unsat, Subst n q r (t = 0 iff r = 0 and n = q) or TryLater"] (sizes: Node.t -> int63) (t: t) : IBDDS.solve5600ensures { match result with5601| Zero -> forall env. value t env = 05602| Unsat -> forall env. value t env <> 05603| Subst n q r ->5604(forall env x. value r (upd_env env n x) = value r env) /\5605(forall env. value r env = 0 -> value t (upd_env env n (value q env)) = 0) /\5606(forall env. value t env = 0 ->5607value r env = 0 /\ (0 <= env n < Zbit.lsl 1 (sizes n) -> value q env = env n))5608| TryLater -> IBDDS.solve_later sizes t5609end }5610raises { Overflow -> (exists nd nd'. Set.mem nd (support t) /\5611Set.mem nd' (Set.add nd (dom_snodes t)) /\ not nd'.scal /\ not (in_bounds (to_int nd'.s - nd.s))) \/5612(exists nd. Set.mem nd (support t) /\ not (in_bounds (Zbit.lsl 1 t.size - 1 + nd.s))) }5613raises { Unsupported -> tailed t }5614= (* [TryLater] (no claim: sizes outside of the bounds, overflow of a shift, term too big...) is returned: the caller treats it as unsolved *)5615if IBDD.has_tail t then raise Unsupported;5617IBDDS.solve sizes t5618Valid (283ms) (colibri2)5619let partial bv_logand_cst (z: int) (t: t) : t5620ensures { dom_snodes result = dom_snodes t }5621ensures { denotes1 value (fun x -> Zbit.land z x) t result }5622ensures { not (tailed result) }5623raises { Unsupported -> z < 0 \/ Zbit.numbits z > Int63.max_int }5624= if 0 <= z && Zbit.numbits z <= to_int Int63.max_int then IBDD.logand_cst z t5625else raise Unsupported5626Valid (938ms) (colibri2)5627let partial bv_logor_cst (z: int) (t: t) : t5628ensures { dom_snodes result = dom_snodes t }5629ensures { denotes1 value (fun x -> Zbit.lor z x) t result }5630ensures { not (tailed result) }5631raises { Unsupported -> z < 0 \/ Zbit.numbits z > Int63.max_int }5632= if 0 <= z && Zbit.numbits z <= to_int Int63.max_int then IBDD.logor_cst z t5633else raise Unsupported5634
Valid (79ms) (colibri2 8) (split_vc) (depth 1)let partial int_cst (x: int) : t5638ensures { all_snodes result = Set.empty }5639ensures { denotes0 ivalue (fun _ -> x) result }5640ensures { to_int result.size <= numbits (numbits (iabs x)) }5641ensures { forall p sn. 0 <= p -> (bit result p sn <-> bittest x p) }5642raises { Unsupported -> Zbit.numbits (iabs x) > Int63.max_int }5643= if Zbit.numbits (if x < 0 then - x else x) <= to_int Int63.max_int then begin5644let r = IBDD.cst_z x in5645let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = x } = is_value_iff r env x in5646r5647end else raise Unsupported5648Valid (893ms) (colibri2 4) (split_vc) (depth 1)5649let partial int_monome (n: Node.t) : t5650ensures { denotes0 ivalue (fun env -> env n) result }5651ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = False } }5652ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = False }) }5653= let r = IBDD.umonome n in5654let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = env n } = is_value_iff r env (env n) in5655r5656
The sign of the node n: -1 if n < 0, else 0
Valid (50ms) (colibri2 9) (split_vc 2) (depth 2)let partial int_scalar (n: Node.t) : t5659ensures { denotes0 ivalue (fun env -> if env n < 0 then -1 else 0) result }5660ensures { all_snodes result = Set.singleton { SNode.n = n; SNode.s = (0:int63); SNode.scal = True } }5661ensures { forall p sn. 0 <= p -> (bit result p sn <-> sn { SNode.n = n; SNode.s = (0:int63); SNode.scal = True }) }5662= let r = IBDD.uscalar n in5663let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = if env n < 0 then -1 else 0 }5664= let z = if env n < 0 then -1 else 0 in5665let lemma bp (p: int) : unit5666requires { 0 <= p }5667ensures { bittest z p <-> bit r p (sem env p) }5668= IBDD.sem_def env p { SNode.n = n; SNode.s = (0:int63); SNode.scal = True };5669assert { Zbit.lsl 1 0 = 1 };5670assert { bittest (0 - Zbit.lsl 1 0) p };5671assert { bittest (-1) p /\ not (bittest 0 p) } in5672is_value_iff r env z in5673r5674
The sign of the term when it does not depend on the nodes
Valid (1.6s) (colibri2 8) (split_vc 2) (depth 2)let partial int_sign (t: t) : option bool5677ensures { denotes_cst (fun t env -> ivalue t env < 0) t result }5678ensures { match result with5679| Some b -> forall env. ivalue t env < 0 <-> b5680| None -> exists sn1 sn2. not (t.tail.PBDD.v 0 (fun nd -> sn1 (IBDDS.scal_of nd.SNode.n)) <->5681t.tail.PBDD.v 0 (fun nd -> sn2 (IBDDS.scal_of nd.SNode.n)))5682end }5683= let g = IBDDS.sign_bdd t in5684let lemma sg (env: Node.t -> int) : unit5685ensures { ivalue t env < 0 <-> g.PBDD.v 0 (sem env 0) }5686= IBDD.value_sign t env (ivalue t env)5687in5688let (f, ghost _, ghost sf) = PBDD.is_equal g (PBDD.tfalse ()) in5689if f then Some false5690else begin5691let (tr, ghost _, ghost st) = PBDD.is_equal g (PBDD.ttrue ()) in5692if tr then Some true5693else begin5694tail_v g 0 sf; tail_v g 0 st;5695assert { g.PBDD.v 0 sf /\ not (g.PBDD.v 0 st) };5696None5697end5698end5699Valid (476ms) (colibri2 4) (split_vc) (depth 1)5700let partial int_lognot (t: t) : t5701ensures { denotes1 ivalue Zbit.lnot t result }5702ensures { all_snodes result = all_snodes t }5703ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t p sn)) }5704= let r = IBDD.lognot_i t in5705let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.lnot (ivalue t env) }5706= is_value_iff r env (Zbit.lnot (ivalue t env)) in5707r5708Valid (627ms) (colibri2 5) (split_vc) (depth 1)5709let partial int_logand (t1 t2: t) : t5710ensures { denotes2 ivalue Zbit.land t1 t2 result }5711ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }5712ensures { to_int result.size <= to_int t1.size \/ to_int result.size <= to_int t2.size }5713ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn /\ bit t2 p sn) }5714= let r = IBDD.logand_i t1 t2 in5715let lemma lv (env: Node.t -> int) : unit5716ensures { ivalue r env = Zbit.land (ivalue t1 env) (ivalue t2 env) }5717= is_value_iff r env (Zbit.land (ivalue t1 env) (ivalue t2 env)) in5718r5719Valid (582ms) (colibri2 4) (split_vc) (depth 1)5720let partial int_logor (t1 t2: t) : t5721ensures { denotes2 ivalue Zbit.lor t1 t2 result }5722ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }5723ensures { forall p sn. 0 <= p -> (bit result p sn <-> bit t1 p sn \/ bit t2 p sn) }5724= let r = IBDD.logor_i t1 t2 in5725let lemma lv (env: Node.t -> int) : unit5726ensures { ivalue r env = Zbit.lor (ivalue t1 env) (ivalue t2 env) }5727= is_value_iff r env (Zbit.lor (ivalue t1 env) (ivalue t2 env)) in5728r5729Valid (713ms) (colibri2 4) (split_vc) (depth 1)5730let partial int_xor (t1 t2: t) : t5731ensures { denotes2 ivalue Zbit.lxor t1 t2 result }5732ensures { Set.subset (all_snodes result) (Set.union (all_snodes t1) (all_snodes t2)) }5733ensures { forall p sn. 0 <= p -> (bit result p sn <-> not (bit t1 p sn <-> bit t2 p sn)) }5734= let r = IBDD.xor_i t1 t2 in5735let lemma lv (env: Node.t -> int) : unit5736ensures { ivalue r env = Zbit.lxor (ivalue t1 env) (ivalue t2 env) }5737= is_value_iff r env (Zbit.lxor (ivalue t1 env) (ivalue t2 env)) in5738r5739Valid (927ms) (colibri2 9) (cvc4) (split_vc 3) (depth 3)5740let partial int_shift_left (off: int) (t: t) : t5741ensures { denotes1 ivalue (fun x -> Zbit.lsl x off) t result }5742ensures { forall env p. 0 <= p ->5743(bit result p (sem env p) <-> (off <= p /\ bit t (p - off) (sem env (p - off)))) }5744raises { Unsupported -> off < 0 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }5745raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }5746= if off < 0 || off > 0x1000_0000_0000_0000 || t.size > 60 then raise Unsupported5747else begin5748let r = IBDDS.shift_i (Int63.of_int off) t in5749let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.lsl (ivalue t env) off }5750= is_value_iff r env (Zbit.lsl (ivalue t env) off) in5751r5752end5753Valid (1.1s) (colibri2 11) (split_vc 3) (depth 3)5754let partial int_shift_right (off: int) (t: t) : t5755ensures { denotes1 ivalue (fun x -> Zbit.asr x off) t result }5756ensures { forall env p. 0 <= p ->5757(bit result p (sem env p) <-> bit t (p + off) (sem env (p + off))) }5758raises { Unsupported -> off < 0 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }5759raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }5760= if off < 0 || off > 0x1000_0000_0000_0000 || t.size > 60 then raise Unsupported5761else begin5762let r = IBDDS.shift_i (- (Int63.of_int off)) t in5763let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = Zbit.asr (ivalue t env) off }5764= is_value_iff r env (Zbit.asr (ivalue t env) off) in5765r5766end5767
t << off, a right shift when off is negative
Valid (126ms) (colibri2 8) (split_vc) (depth 1)let partial int_shift (off: int) (t: t) : t5770ensures { denotes1 ivalue (fun x -> Zbit.lsl x off) t result }5771ensures { forall env p. 0 <= p ->5772(bit result p (sem env p) <-> (0 <= p - off /\ bit t (p - off) (sem env (p - off)))) }5773raises { Unsupported -> off < - 0x1000_0000_0000_0000 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }5774raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }5775= if off >= 0 then int_shift_left off t else int_shift_right (- off) t5776
SMT–LIB extract: the len bits of t from the position off (total: a negative off reads false below the position 0, a negative len gives 0), as a non–negative integer
Valid (1.6s) (colibri2 14) (cvc4 4) (split_vc 3) (depth 2)let partial int_extract (off len: int) (t: t) : t5781ensures { denotes1 ivalue (fun x -> iextract x off len) t result }5782ensures { forall env p. 0 <= p ->5783(bit result p (sem env p) <->5784(p < len /\ 0 <= p + off /\ bit t (p + off) (sem env (p + off)))) }5785raises { Unsupported -> len > 0x100000 \/ off < - 0x1000_0000_0000_0000 \/ off > 0x1000_0000_0000_0000 \/ t.size > 60 }5786raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ not nd.scal /\ not (in_bounds (to_int nd.s + off)) }5787= if len > 0x100000 then raise Unsupported;5788let len' = if len < 0 then 0 else len in5789let s = int_shift (- off) t in5790Zbit.mask_nonneg len';5791let m = int_cst (ZbitInt.mask_int len') in5792let r = int_logand s m in5793let lemma bits (env: Node.t -> int) (p: int) : unit5794requires { 0 <= p }5795ensures { bit r p (sem env p) <->5796(p < len /\ 0 <= p + off /\ bit t (p + off) (sem env (p + off))) }5797= if p < len' then Zbit.mask_bits len' p else Zbit.mask_bits_high len' p5798in5799let lemma lv (env: Node.t -> int) : unit5800ensures { ivalue r env = iextract (ivalue t env) off len }5801= is_value_iff r env (iextract (ivalue t env) off len) in5802r5803
SMT–LIB update: t where the len bits from the position off are replaced by the low bits of y (total)
Valid (4.0s) (colibri2 63) (cvc4 36) (cvc5 7) (split_vc 62) (depth 5)let partial int_update (off len: int) (t y: t) : t5807ensures { denotes2 ivalue (fun x z -> iupdate x off len z) t y result }5808ensures { forall env p. 0 <= p ->5809(bit result p (sem env p) <->5810(if off <= p /\ p < off + len then bit y (p - off) (sem env (p - off))5811else bit t p (sem env p))) }5812raises { Unsupported -> len > Zbit.lsl 1 20 \/ off > 0x100000 \/ off < - 0x100000 \/ y.size > 60 }5813raises { Overflow -> exists nd. Set.mem nd (all_snodes y) /\ not nd.scal /\ not (in_bounds (to_int nd.s - off)) }5814= if len > ZbitInt.lsl_int 1 20 || off > 0x100000 || off < - 0x100000 || y.size > 60 then raise Unsupported;5815let len' = if len < 0 then 0 else len in5816let o = if off < 0 then 0 else off in5817let e = if off + len' < 0 then 0 else off + len' in5818Zbit.mask_nonneg len'; Zbit.mask_nonneg o; Zbit.mask_nonneg e;5819Zbit.mask_numbits len';5820Zbit.mask_nonneg 21; assert { lsl 1 21 = 2 * lsl 1 20 };5821Zbit.numbits_lt_lsl len' 21;5822let m = int_cst (ZbitInt.mask_int len') in5823assert { iabs (Zbit.mask len') = Zbit.mask len' /\ to_int m.size <= 21 };5824let ym = int_logand y m in5825assert { to_int ym.size <= 60 };5826let ys = int_shift off ym in5827Zbit.mask_numbits o; Zbit.mask_numbits e;5828let ce = int_cst (ZbitInt.mask_int e) in5829let co = int_cst (ZbitInt.mask_int o) in5830let band = int_logand ce (int_lognot co) in5831let hole = int_lognot band in5832let tc = int_logand t hole in5833let r = int_logor tc ys in5834let lemma bits (env: Node.t -> int) (p: int) : unit5835requires { 0 <= p }5836ensures { bit r p (sem env p) <->5837(if off <= p /\ p < off + len then bit y (p - off) (sem env (p - off))5838else bit t p (sem env p)) }5839= assert { bit band p (sem env p) <-> Zbit.bittest (Zbit.mask e) p /\ not Zbit.bittest (Zbit.mask o) p };5840assert { bit hole p (sem env p) <-> not (bit band p (sem env p)) };5841assert { bit tc p (sem env p) <-> bit t p (sem env p) /\ bit hole p (sem env p) };5842assert { bit ys p (sem env p) <-> 0 <= p - off /\ bit ym (p - off) (sem env (p - off)) };5843if 0 <= p - off then assert { bit ym (p - off) (sem env (p - off)) <->5844bit y (p - off) (sem env (p - off)) /\ bit m (p - off) (sem env (p - off)) };5845if p < o then Zbit.mask_bits o p else Zbit.mask_bits_high o p;5846if p < e then Zbit.mask_bits e p else Zbit.mask_bits_high e p;5847if 0 <= p - off then (if p - off < len' then Zbit.mask_bits len' (p - off) else Zbit.mask_bits_high len' (p - off))5848in5849let lemma lv (env: Node.t -> int) : unit5850ensures { ivalue r env = iupdate (ivalue t env) off len (ivalue y env) }5851= is_value_iff r env (iupdate (ivalue t env) off len (ivalue y env)) in5852r5853
t = 0: ISubst n q r means t = 0 iff r = 0 and n = q (for every value of n); IUnsolved when the term is not solved yet (a node read at several shifts)
Valid (56ms) (colibri2)let partial int_solve [@spec:none "solver: isolve_ok"] (t: t) : IBDDS.isolve5858ensures { isolve_ok t result }5859raises { Overflow -> exists nd. Set.mem nd (all_snodes t) /\ exists sh: int. not (in_bounds (to_int nd.s - sh)) }5860= IBDDS.int_solve_t t5861
t where the node n1 has the value of the term t1
Valid (2.9s) (colibri2 6) (split_vc 2) (depth 2)let partial int_subst (t: t) (n1: Node.t) (t1: t) : t5864ensures { denotes_subst ivalue upd_env n1 t1 t result }5865ensures { forall env z. is_value t1 env z ->5866forall p. 0 <= p -> (bit result p (sem env p) <-> bit t p (sem (upd_env env n1 z) p)) }5867raises { Unsupported -> t.size > 60 \/ exists nd. in_supports t nd /\ nd.SNode.n = n1 /\ not nd.SNode.scal /\ IBDDS.bad_sub t1 (to_int nd.SNode.s) }5868= let sel = fun (n: Node.t) ->5869ensures { result = (if n = n1 then Some t1 else None) }5870if Node.equal n n1 then Some t1 else None in5871let r = try IBDDS.compose_i t sel with Overflow -> raise Unsupported end in5872{proof…}5873let lemma lv (env: Node.t -> int) : unit5874ensures { ivalue r env = ivalue t (upd_env env n1 (ivalue t1 env)) }5875= is_value_iff r env (ivalue t (upd_env env n1 (ivalue t1 env))) in5876{qed}5877r5878
t where each node n has the value of the term f n
Valid (2.6s) (colibri2 6) (split_vc 2) (depth 2)let partial int_normalize (t: t) (f: Node.t -> t) : t5881ensures { denotes_compose ivalue f t result }5882ensures { forall env env'. (forall m. is_value (f m) env (env' m)) ->5883forall p. 0 <= p -> (bit result p (sem env p) <-> bit t p (sem env' p)) }5884raises { Unsupported -> t.size > 60 \/ exists nd. in_supports t nd /\ not nd.SNode.scal /\ IBDDS.bad_sub (f nd.SNode.n) (to_int nd.SNode.s) }5885= let sel = fun (n: Node.t) -> ensures { result = Some (f n) } Some (f n) in5886let r = try IBDDS.compose_i t sel with Overflow -> raise Unsupported end in5887{proof…}5888let lemma lv (env env': Node.t -> int) : unit5889requires { forall m. env' m = ivalue (f m) env }5890ensures { ivalue r env = ivalue t env' }5891= is_value_iff r env (ivalue t env') in5892{qed}5893r5894
The value of a term without node
Valid (340ms) (colibri2 4) (split_vc) (depth 1)let int_is_cst (t: t) : option int5897ensures { denotes_cst ivalue t result }5898ensures { match result with5899| Some z -> forall env. is_value t env z5900| None -> exists nd. in_supports t nd5901end }5902raises { Unsupported -> t.size > 61 }5903= if t.size > 61 then raise Unsupported;5904let r = IBDDS.int_is_cst t in5905{proof…}5906match r with5907| Some z ->5908let lemma cv (env: Node.t -> int) : unit ensures { ivalue t env = z }5909= is_value_iff t env z in ()5910| None -> ()5911end;5912{qed}5913r5914
The bits that can be 1 (negative when the high bits can) and the bits that are always 1
Valid (1.1s) (colibri2 6) (cvc4 2) (split_vc) (depth 1)let partial int_to_knownbits (t: t) : (int, int)5918ensures { denotes_in ivalue kb_mem t result }5919ensures { let (known0, _) = result in5920forall q. 0 <= q -> (bittest known0 q <-> exists sn. bit t q sn) }5921ensures { let (_, known1) = result in5922forall q. 0 <= q -> (bittest known1 q <-> forall sn. bit t q sn) }5923raises { Unsupported -> t.size > 61 }5924= if t.size > 61 then raise Unsupported;5925lsl_le_max_int (to_int t.size);5926let (k0, k1) = IBDDS.int_to_knownbits t in5927{proof…}5928let lemma kb (env: Node.t -> int) : unit5929ensures { kb_mem (ivalue t env) (k0, k1) }5930= assert { forall i. 0 <= i -> (bittest (ivalue t env) i <-> bit t i (sem env i)) } in5931{qed}5932(k0, k1)5933Valid (301ms) (colibri2)5934let int_compute (env: Node.t -> int) (t: t) : int5935ensures { denotes_at ivalue t env result }5936ensures { is_value t env result }5937raises { Unsupported -> t.size > 61 }5938= if t.size > 61 then raise Unsupported;5939IBDDS.compute_i env t5940
bddbitv.mlThe terms without tail go to the bounded functions above, the others to the integer ones. The specifications use the integer value: the integer value of a term without tail is its bounded value (value_untailed).
Valid (57ms) (colibri2)let ghost value_untailed (t: t) (env: Node.t -> int) : unit5950requires { not (tailed t) }5951ensures { is_value t env (value t env) }5952ensures { ivalue t env = value t env }5953= let lemma b (p: int) : unit5954requires { 0 <= p }5955ensures { bittest (value t env) p <-> bit t p (sem env p) }5956= PBDD2.def_v t.bdd (to_int t.size) (sem env) p in5957is_value_iff t env (value t env)5958Valid (143ms) (colibri2)5959let partial any_cst (x: int) : t5960ensures { denotes0 ivalue (fun _ -> x) result }5961raises { Unsupported -> Zbit.numbits (iabs x) > Int63.max_int }5962= if x < 0 then int_cst x5963else begin5964let r = bv_cst x in5965let lemma lv (env: Node.t -> int) : unit ensures { ivalue r env = x } = value_untailed r env in5966r5967end5968Valid (714ms) (colibri2 10) (cvc5) (split_vc 4) (depth 2)5969let any_is_cst (t: t) : option int5970ensures { denotes_cst ivalue t result }5971ensures { match result with5972| Some z -> forall env. is_value t env z5973| None -> exists nd. in_supports t nd5974end }5975raises { Unsupported -> t.size > 61 }5976= if IBDD.has_tail t then int_is_cst t5977else begin5978let r = bv_is_cst t in5979match r with5980| Some z ->5981let lemma lv (env: Node.t -> int) : unit ensures { is_value t env z } = value_untailed t env in5982let lemma cv (env: Node.t -> int) : unit ensures { ivalue t env = z }5983= value_untailed t env in5984r5985| None -> r5986end5987end5988Valid (726ms) (cvc4)5989let partial any_logand (t1 t2: t) : t5990ensures { denotes2 ivalue Zbit.land t1 t2 result }5991= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_logand t1 t25992else begin5993let r = try bv_logand t1 t2 with Unsupported -> absurd end in5994let lemma lv (env: Node.t -> int) : unit5995ensures { ivalue r env = Zbit.land (ivalue t1 env) (ivalue t2 env) }5996= value_untailed r env; value_untailed t1 env; value_untailed t2 env in5997r5998end5999Valid (1.2s) (colibri2)6000let partial any_logor (t1 t2: t) : t6001ensures { denotes2 ivalue Zbit.lor t1 t2 result }6002= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_logor t1 t26003else begin6004let r = try bv_logor t1 t2 with Unsupported -> absurd end in6005let lemma lv (env: Node.t -> int) : unit6006ensures { ivalue r env = Zbit.lor (ivalue t1 env) (ivalue t2 env) }6007= value_untailed r env; value_untailed t1 env; value_untailed t2 env in6008r6009end6010Valid (725ms) (cvc4)6011let partial any_xor (t1 t2: t) : t6012ensures { denotes2 ivalue Zbit.lxor t1 t2 result }6013= if IBDD.has_tail t1 || IBDD.has_tail t2 then int_xor t1 t26014else begin6015let r = try bv_xor t1 t2 with Unsupported -> absurd end in6016let lemma lv (env: Node.t -> int) : unit6017ensures { ivalue r env = Zbit.lxor (ivalue t1 env) (ivalue t2 env) }6018= value_untailed r env; value_untailed t1 env; value_untailed t2 env in6019r6020end6021Valid (744ms) (colibri2 9) (split_vc) (depth 1)6022let partial any_logand_cst (z: int) (t: t) : t6023ensures { denotes1 ivalue (fun x -> Zbit.land z x) t result }6024raises { Unsupported -> Zbit.numbits (iabs z) > Int63.max_int }6025= if IBDD.has_tail t || z < 0 then begin6026let c = int_cst z in6027let r = int_logand c t in6028let lemma lv (env: Node.t -> int) : unit6029ensures { ivalue r env = Zbit.land z (ivalue t env) }6030= assert { ivalue c env = z } in6031r6032end else begin6033let r = bv_logand_cst z t in6034let lemma lv (env: Node.t -> int) : unit6035ensures { ivalue r env = Zbit.land z (ivalue t env) }6036= value_untailed r env; value_untailed t env in6037r6038end6039Valid (747ms) (colibri2 9) (split_vc) (depth 1)6040let partial any_logor_cst (z: int) (t: t) : t6041ensures { denotes1 ivalue (fun x -> Zbit.lor z x) t result }6042raises { Unsupported -> Zbit.numbits (iabs z) > Int63.max_int }6043= if IBDD.has_tail t || z < 0 then begin6044let c = int_cst z in6045let r = int_logor c t in6046let lemma lv (env: Node.t -> int) : unit6047ensures { ivalue r env = Zbit.lor z (ivalue t env) }6048= assert { ivalue c env = z } in6049r6050end else begin6051let r = bv_logor_cst z t in6052let lemma lv (env: Node.t -> int) : unit6053ensures { ivalue r env = Zbit.lor z (ivalue t env) }6054= value_untailed r env; value_untailed t env in6055r6056end6057Valid (46ms) (colibri2)6058let any_compute (env: Node.t -> int) (t: t) : int6059ensures { denotes_at ivalue t env result }6060ensures { is_value t env result }6061raises { Unsupported -> t.size > 61 }6062= if IBDD.has_tail t then int_compute env t6063else begin6064let r = bv_compute env t in6065value_untailed t env;6066r6067end6068
The bits that can be 1 and the bits that are always 1
Valid (941ms) (colibri2 6) (cvc4 3) (split_vc) (depth 1)let partial any_to_knownbits (t: t) : (int, int)6071ensures { denotes_in ivalue kb_mem t result }6072raises { Unsupported -> t.size > 61 }6073= if IBDD.has_tail t then begin6074let (k0, k1) = int_to_knownbits t in6075let lemma lv (env: Node.t -> int) : unit6076ensures { Zbit.subset k1 (ivalue t env) /\ Zbit.subset (ivalue t env) k0 }6077= let lemma b (q: int) : unit6078ensures { (bittest k1 q -> bittest (ivalue t env) q) /\ (bittest (ivalue t env) q -> bittest k0 q) }6079= if q >= 0 then assert { bittest (ivalue t env) q <-> bit t q (sem env q) } in6080() in6081(k0, k1)6082end else begin6083let (k0, k1) = bv_to_knownbits t in6084let lemma lv (env: Node.t -> int) : unit6085ensures { Zbit.subset k1 (ivalue t env) /\ Zbit.subset (ivalue t env) k0 }6086= value_untailed t env in6087(k0, k1)6088end6089
bv_solve, where TryLater (no claim) raises Unsupported
Valid (702ms) (cvc5)let partial any_solve [@spec:none "solver: Zero, Unsat, Subst n q r (t = 0 iff r = 0 and n = q); never TryLater"] (sizes: Node.t -> int63) (t: t) : IBDDS.solve6092ensures { match result with6093| Zero -> forall env. value t env = 06094| Unsat -> forall env. value t env <> 06095| Subst n q r ->6096(forall env x. value r (upd_env env n x) = value r env) /\6097(forall env. value r env = 0 -> value t (upd_env env n (value q env)) = 0) /\6098(forall env. value t env = 0 ->6099value r env = 0 /\ (0 <= env n < Zbit.lsl 1 (sizes n) -> value q env = env n))6100| TryLater -> false6101end }6102raises { Overflow -> (exists nd nd'. Set.mem nd (support t) /\6103Set.mem nd' (Set.add nd (dom_snodes t)) /\ not nd'.scal /\ not (in_bounds (to_int nd'.s - nd.s))) \/6104(exists nd. Set.mem nd (support t) /\ not (in_bounds (Zbit.lsl 1 t.size - 1 + nd.s))) }6105raises { Unsupported -> tailed t \/ IBDDS.solve_later sizes t }6106= match bv_solve sizes t with6107| TryLater -> raise Unsupported6108| r -> r6109end6110
The two terms have the same bits (the same size, window and tail)
Valid (596ms) (cvc4)let same_bits (a b: t) : bool6114ensures { decides_sound (forall p sn. 0 <= p -> (bit a p sn <-> bit b p sn)) result }6115= if a.size <> b.size then false6116else begin6117let (r1, _, _) = PBDD.is_equal a.bdd b.bdd in6118let (r2, _, _) = PBDD.is_equal a.tail b.tail in6119r1 && r26120end6121
A node read by the term, if any
Valid (40ms) (colibri2)let rec first_node [@spec:none "heuristic: the first node read in the list; no claim"] (l: list Key.t) : option Node.t6124variant { l }6125= match l with6126| Nil -> None6127| Cons (Key.Var n _ _) _ -> Some n6128| Cons _ l' -> first_node l'6129end6130
The term is the node n on sz bits
predicate bounded_node (t: t) (n: Node.t) (sz: int) =61330 <= sz /\ forall env. ivalue t env = Zbit.land (Zbit.mask sz) (env n)6134
The term is the value of one node: the integer n (with a tail) or the bounded n on sz bits. No claim for None
Valid (720ms) (colibri2 16) (split_vc) (depth 1)let partial any_is_one_node [@spec:none "hint: Some n when t is the node n, or n on some bits (bounded_node); None is no claim"] (t: t) : option Node.t6138ensures { match result with6139| Some n -> (forall env. ivalue t env = env n) \/ (exists sz. bounded_node t n sz)6140| None -> true6141end }6142= let same_ivalue (a b: t) : unit6143requires { forall p sn. 0 <= p -> (bit a p sn <-> bit b p sn) }6144ensures { forall env. ivalue a env = ivalue b env }6145= let lemma lv (env: Node.t -> int) : unit ensures { ivalue a env = ivalue b env }6146= is_value_iff a env (ivalue b env) in6147() in6148if IBDD.has_tail t then6149match first_node (PBDD.vars t.tail) with6150| None -> None6151| Some n ->6152let m = int_monome n in6153if same_bits t m then begin same_ivalue t m; Some n end else None6154end6155else6156match first_node (PBDD.vars t.bdd) with6157| None -> None6158| Some n ->6159(* the size of [n]: the bits of [t] when every node is [-1] *)6160match bv_compute (fun _ -> -1) t with6161| exception Unsupported -> None6162| v ->6163let s = Zbit.numbits v in6164if s > to_int Int63.max_int then None6165else begin6166let m = try bv_monome (Int63.of_int s) n with Unsupported -> absurd end in6167if same_bits t m then begin6168same_ivalue t m;6169let lemma lv (env: Node.t -> int) : unit6170ensures { ivalue t env = Zbit.land (Zbit.mask s) (env n) }6171= value_untailed m env in6172assert { bounded_node t n s };6173Some n6174end else None6175end6176end6177end6178
For the tests: c read as a bit–vector one bit larger, and back. The same integers.
Valid (720ms) (colibri2)let partial reget (c:t) : t6183ensures { forall sn. v result sn = v c sn \/ c.size >= 0x3FFFFFFFFFFFFFFE }6184= if c.size >= 0x3FFFFFFFFFFFFFFE then c6185else begin6186let s = c.size + 1 in6187IBDD.mk (IBDD.get c s) s6188end6189end6190