library colibrilib.bv_sem — module SemThe code of RealValue.Check.compute_ground (realValue.ml) for the integer bitwise builtins of colibri2 and the SMT–LIB bit–vector operators: code is its specification, written with the same Zarith functions, and eval its implementation (extracted, called by realValue.ml). The values of the arguments and of the result are integers: a bit–vector of size n is 0 <= x < 2^n, a Boolean is -1 (true) or 0 (false).
module Sem10use int.Int11use list.List12use int.ComputerDivision as C13use int.EuclideanDivision as E14use mach.int.Int as MI15use mach.int.Int6316use colibrilib.zarith.Zbit17use colibrilib.zbit.ZbitInt18use colibrilib.safe_bits.BitsSpec19use colibrilib.safe_bits.SafeBits20use colibrilib.zarith.Z21
The builtins: colibri_and_int, colibri_ior_int, colibri_xor_int, colibri_not_int, colibri_rshift_int, colibri_extract_int, colibri_signed_extract_int, colibri_update_int, colibri_testbit_int; the conversions sbv_to_int, ubv_to_int (and bv2nat), int_to_bv of a bit–vector of size n; the SMT–LIB bit–vector operators of size n (concat of sizes n and m, extract of the bits lo..hi, repeat k times, zero_extend and sign_extend by k, rotate_left and rotate_right by i)
type builtin =31| And | Or | Xor | Not | Asr | Extract | SignedExtract | Update | Test32| Sbv2int int | Bv2nat int | Int2bv int33| BvConcat int int | BvExtract int int int | BvRepeat int int34| BvZeroExtend int int | BvSignExtend int int35| BvRotl int int | BvRotr int int36| BvNot int | BvAnd int | BvOr int | BvXor int37| BvNand int | BvNor int | BvXnor int | BvComp int38| BvNeg int | BvAdd int | BvSub int | BvMul int39| BvUdiv int | BvUrem int | BvSdiv int | BvSrem int | BvSmod int40| BvShl int | BvLshr int | BvAshr int41| BvUlt int | BvUle int | BvUgt int | BvUge int42| BvSlt int | BvSle int | BvSgt int | BvSge int43
Z.logand, Z.logor, Z.logxor, Z.lognot, Z.shift_left, Z.shift_right and Z.testbit are Zbit.land, Zbit.lor, Zbit.lxor, Zbit.lnot, Zbit.lsl, Zbit.asr and Zbit.bittest (as in zarith.drv); Z.div and Z.rem are C.div and C.mod (truncated), Z.fdiv is fdiv (rounded down).
Z.extract x off len: the bits off..off+len-1 of x. Zarith raises Invalid_argument for len <= 0; here it is 0
function z_extract (x off len:int) : int =55if len <= 0 then 0 else Zbit.land (Zbit.asr x off) (Zbit.mask len)56
Z.signed_extract x off len: the same bits, sign extended
function z_signed_extract (x off len:int) : int =59if len <= 0 then 060else if Zbit.bittest x (off + len - 1)61then Zbit.lor (z_extract x off len) (Zbit.lnot (Zbit.mask len))62else z_extract x off len63
Z.fdiv a b, b <> 0
function fdiv (a b:int) : int = if b > 0 then E.div a b else E.div (- a) (- b)66
RealValue.Check.compute_groundbitv n x: the value of a bit–vector argument of size n, which raises Wrong_arg when x is not 0 <= x < 2^n. It is used only on such values, where it is x itself (bitv below)
function bv (n x:int) : int = Zbit.land (Zbit.mask n) x73
extract n t
function ext (n t:int) : int = z_extract t 0 n76
signed_bitv n x
function signed (n x:int) : int = z_signed_extract (bv n x) 0 n79
A Boolean
function bool (b:bool) : int = if b then -1 else 082
The loop of repeat: k copies of the n bits a
Valid (23ms) (colibri2)let rec ghost function repeat (n k a:int) : int85variant { k }86= if k <= 0 then 0 else Zbit.lor (Zbit.lsl (repeat n (k - 1) a) n) a87
The value of the builtin b applied to the values l (0 for a wrong number of arguments, and for a rotation of a size n <= 0 or by i < 0: neither is a well–sorted SMT–LIB term)
function code (b:builtin) (l:list int) : int =92match b, l with93| And, Cons x (Cons y Nil) -> Zbit.land x y94| Or, Cons x (Cons y Nil) -> Zbit.lor x y95| Xor, Cons x (Cons y Nil) -> Zbit.lxor x y96| Not, Cons x Nil -> Zbit.lnot x97| Asr, Cons x (Cons o Nil) -> Zbit.asr x o98| Extract, Cons x (Cons o (Cons l Nil)) -> BitsSpec.extract o l x99| SignedExtract, Cons x (Cons o (Cons l Nil)) -> BitsSpec.signed_extract o l x100| Update, Cons dst (Cons o (Cons l (Cons src Nil))) -> BitsSpec.update o l src dst101| Test, Cons x (Cons k Nil) -> bool (Zbit.bittest x k)102| Sbv2int n, Cons x Nil -> signed n x103| Bv2nat n, Cons x Nil -> bv n x104| Int2bv n, Cons x Nil -> ext n x105| BvConcat n m, Cons x (Cons y Nil) -> Zbit.lor (Zbit.lsl (bv n x) m) (bv m y)106| BvExtract n lo hi, Cons x Nil -> z_extract (bv n x) lo (hi - lo + 1)107| BvRepeat n k, Cons x Nil -> repeat n k (bv n x)108| BvZeroExtend n _, Cons x Nil -> bv n x109| BvSignExtend n k, Cons x Nil ->110let a = bv n x in111if Zbit.bittest a (n - 1) then ext (n + k) (Zbit.lor (Zbit.lsl (-1) n) a) else a112| BvRotl n i, Cons x Nil ->113if n <= 0 || i < 0 then 0 else114let a = bv n x in115let k = C.mod i n in116if k = 0 then ext n a117else ext n (Zbit.lor (Zbit.lsl a k) (z_extract a (n - k) k))118| BvRotr n i, Cons x Nil ->119if n <= 0 || i < 0 then 0 else120let a = bv n x in121let k = C.mod i n in122ext n (Zbit.lor (Zbit.lsl a (n - k)) (Zbit.asr a k))123| BvNot n, Cons x Nil -> ext n (Zbit.lnot (bv n x))124| BvAnd n, Cons x (Cons y Nil) -> Zbit.land (bv n x) (bv n y)125| BvOr n, Cons x (Cons y Nil) -> Zbit.lor (bv n x) (bv n y)126| BvXor n, Cons x (Cons y Nil) -> ext n (Zbit.lxor (bv n x) (bv n y))127| BvNand n, Cons x (Cons y Nil) -> ext n (Zbit.lnot (Zbit.land (bv n x) (bv n y)))128| BvNor n, Cons x (Cons y Nil) -> ext n (Zbit.lnot (Zbit.lor (bv n x) (bv n y)))129| BvXnor n, Cons x (Cons y Nil) -> ext n (Zbit.lxor (bv n x) (Zbit.lnot (bv n y)))130| BvComp n, Cons x (Cons y Nil) -> if bv n x = bv n y then ext 1 (-1) else 0131| BvNeg n, Cons x Nil -> z_extract (Zbit.lsl 1 n - bv n x) 0 n132| BvAdd n, Cons x (Cons y Nil) -> ext n (bv n x + bv n y)133| BvSub n, Cons x (Cons y Nil) -> ext n (bv n x - bv n y)134| BvMul n, Cons x (Cons y Nil) -> ext n (bv n x * bv n y)135| BvUdiv n, Cons x (Cons y Nil) ->136let b = bv n y in137if b = 0 then ext n (-1) else ext n (C.div (bv n x) b)138| BvUrem n, Cons x (Cons y Nil) ->139let b = bv n y in140if b = 0 then bv n x else ext n (C.mod (bv n x) b)141| BvSdiv n, Cons x (Cons y Nil) ->142let b = signed n y in143let a = signed n x in144if b = 0 then (if a < 0 then ext n 1 else ext n (-1)) else ext n (C.div a b)145| BvSrem n, Cons x (Cons y Nil) ->146let b = signed n y in147if b = 0 then bv n x else ext n (C.mod (signed n x) b)148| BvSmod n, Cons x (Cons y Nil) ->149let b = signed n y in150let a = signed n x in151if b = 0 then bv n x else ext n (a - fdiv a b * b)152| BvShl n, Cons x (Cons o Nil) ->153let b = bv n o in154if n <= b then 0 else ext n (Zbit.lsl (bv n x) b)155| BvLshr n, Cons x (Cons o Nil) ->156let b = bv n o in157if n <= b then 0 else ext n (Zbit.asr (bv n x) b)158| BvAshr n, Cons x (Cons o Nil) ->159let b = bv n o in160let b = if n <= b then n else b in161ext n (Zbit.asr (signed n x) b)162| BvUlt n, Cons x (Cons y Nil) -> bool (bv n x < bv n y)163| BvUle n, Cons x (Cons y Nil) -> bool (bv n x <= bv n y)164| BvUgt n, Cons x (Cons y Nil) -> bool (bv n x > bv n y)165| BvUge n, Cons x (Cons y Nil) -> bool (bv n x >= bv n y)166| BvSlt n, Cons x (Cons y Nil) -> bool (signed n x < signed n y)167| BvSle n, Cons x (Cons y Nil) -> bool (signed n x <= signed n y)168| BvSgt n, Cons x (Cons y Nil) -> bool (signed n x > signed n y)169| BvSge n, Cons x (Cons y Nil) -> bool (signed n x >= signed n y)170| _ -> 0171end172
x is a bit–vector of size n
predicate in_range (n x:int) = 0 <= x < Zbit.lsl 1 n177
The bit–vector arguments are in range
predicate args_ok (b:builtin) (l:list int) =180match b, l with181| (Sbv2int n | Bv2nat n | BvExtract n _ _ | BvRepeat n _ | BvZeroExtend n _182| BvSignExtend n _ | BvRotl n _ | BvRotr n _ | BvNot n | BvNeg n), Cons x Nil ->183in_range n x184| BvConcat n m, Cons x (Cons y Nil) -> in_range n x /\ in_range m y185| (BvAnd n | BvOr n | BvXor n | BvNand n | BvNor n | BvXnor n | BvComp n186| BvAdd n | BvSub n | BvMul n | BvUdiv n | BvUrem n | BvSdiv n | BvSrem n187| BvSmod n | BvShl n | BvLshr n | BvAshr n | BvUlt n | BvUle n | BvUgt n188| BvUge n | BvSlt n | BvSle n | BvSgt n | BvSge n), Cons x (Cons y Nil) ->189in_range n x /\ in_range n y190| _ -> true191end192
The integer builtins whose result is not too big (SafeBits)
predicate small (b:builtin) (l:list int) =195match b, l with196| Asr, Cons x (Cons o Nil) -> shift_ok o x197| Extract, Cons x (Cons o (Cons l Nil)) -> extract_ok o l x198| SignedExtract, Cons _ (Cons o (Cons l Nil)) -> signed_extract_ok o l199| Update, Cons _ (Cons o (Cons l (Cons _ Nil))) -> update_ok o l200| _ -> true201end202
The bits of 0 <= x < 2^s from s are zero
Valid (52ms) (colibri2)let ghost high_zero (x s:int) : unit207requires { 0 <= s /\ 0 <= x < Zbit.lsl 1 s }208ensures { forall i. s <= i -> not (Zbit.bittest x i) }209= {proof…} Zbit.numbits_lt_lsl x s;210let lemma bit (i:int) : unit211requires { s <= i }212ensures { not (Zbit.bittest x i) }213= if x > 0 then Zbit.numbits_high_clear x i in214() {qed}215
A bit–vector argument is not in range (Wrong_arg)
exception WrongArg218
bitv n x
Valid (130ms) (colibri2 12) (cvc4) (split_vc) (depth 1)let bitv (n x:int) : int221ensures { in_range n x /\ 0 <= n }222ensures { result = x = bv n x }223raises { WrongArg -> not in_range n x }224= if 0 <= x && Zbit.numbits x <= n then begin225{proof…}226Zbit.numbits_ge_pos 0 x;227assert { 0 <= n };228assert { x < Zbit.lsl 1 n229by Zbit.lsl 1 n <= x -> n + 1 = Zbit.numbits (Zbit.lsl 1 n) <= Zbit.numbits x };230high_zero x n;231let lemma bit (i:int) : unit232requires { 0 <= i }233ensures { Zbit.bittest (bv n x) i <-> Zbit.bittest x i }234= () in235Zbit.ext_bittest (bv n x) x;236{qed}237x238end else begin239{proof…}240assert { not in_range n x by in_range n x -> Zbit.numbits x <= n };241{qed}242raise WrongArg243end244
Z.extract x off len (total)
Valid (50ms) (colibri2)let z_extract_p (x off len:int) : int247ensures { result = z_extract x off len }248= if len <= 0 then 0249else begin250let y = if off >= 0 then asr_int x off else lsl_int x (- off) in251Zbit.land y (mask_int len)252end253
extract n t
Valid (25ms) (colibri2)let ext_p (n t:int) : int256ensures { result = ext n t }257= z_extract_p t 0 n258
Z.signed_extract x 0 n
Valid (41ms) (colibri2)let z_signed_extract0 (x n:int) : int261ensures { result = z_signed_extract x 0 n }262= if n <= 0 then 0263else if test_bit_int x (n - 1) then Zbit.lor (z_extract_p x 0 n) (Zbit.lnot (mask_int n))264else z_extract_p x 0 n265
signed_bitv n x
Valid (43ms) (colibri2)let signed_p (n x:int) : int268ensures { in_range n x /\ 0 <= n }269ensures { result = signed n x }270raises { WrongArg -> not in_range n x }271= z_signed_extract0 (bitv n x) n272273let function bool_p (b:bool) : int = if b then -1 else 0274
The loop of repeat
Valid (40ms) (colibri2)let rec repeat_p (n k a:int) : int277requires { 0 <= n }278variant { k }279ensures { result = repeat n k a }280= if k <= 0 then 0 else Zbit.lor (lsl_int (repeat_p n (k - 1) a) n) a281
Z.fdiv a b
Valid (43ms) (colibri2)let fdiv_p (a b:int) : int284requires { b <> 0 }285ensures { result = fdiv a b }286= if b > 0 then Z.fdiv a b else Z.fdiv (- a) (- b)287
The value of the builtin b applied to the values l
Valid (393ms) (colibri2 203) (split_vc) (depth 1)let eval (b:builtin) (l:list int) : int290ensures { args_ok b l /\ small b l }291ensures { result = code b l }292raises { WrongArg -> not args_ok b l }293raises { TooBig -> args_ok b l /\ not small b l }294= match b, l with295| And, Cons x (Cons y Nil) -> Zbit.land x y296| Or, Cons x (Cons y Nil) -> Zbit.lor x y297| Xor, Cons x (Cons y Nil) -> Zbit.lxor x y298| Not, Cons x Nil -> Zbit.lnot x299| Asr, Cons x (Cons o Nil) ->300if shift_ok o x then SafeBits.shift_right o x else raise TooBig301| Extract, Cons x (Cons o (Cons l Nil)) ->302if extract_ok o l x then SafeBits.extract o l x else raise TooBig303| SignedExtract, Cons x (Cons o (Cons l Nil)) ->304if signed_extract_ok o l then SafeBits.signed_extract o l x else raise TooBig305| Update, Cons dst (Cons o (Cons l (Cons src Nil))) ->306if update_ok o l then SafeBits.update o l src dst else raise TooBig307| Test, Cons x (Cons k Nil) ->308if k < 0 then 0 else bool_p (test_bit_int x k)309| Sbv2int n, Cons x Nil -> signed_p n x310| Bv2nat n, Cons x Nil -> bitv n x311| Int2bv n, Cons x Nil -> ext_p n x312| BvConcat n m, Cons x (Cons y Nil) ->313let a = bitv n x in314let b = bitv m y in315Zbit.lor (lsl_int a m) b316| BvExtract n lo hi, Cons x Nil -> z_extract_p (bitv n x) lo (hi - lo + 1)317| BvRepeat n k, Cons x Nil ->318let a = bitv n x in319repeat_p n k a320| BvZeroExtend n _, Cons x Nil -> bitv n x321| BvSignExtend n k, Cons x Nil ->322let a = bitv n x in323if n <= 0 then a (* no bit-vector of size <= 0 but 0 *)324else if test_bit_int a (n - 1) then ext_p (n + k) (Zbit.lor (lsl_int (-1) n) a) else a325| BvRotl n i, Cons x Nil ->326let a = bitv n x in327if n <= 0 || i < 0 then 0 else328let k = MI.(%) i n in329if k = 0 then ext_p n a330else ext_p n (Zbit.lor (lsl_int a k) (z_extract_p a (n - k) k))331| BvRotr n i, Cons x Nil ->332let a = bitv n x in333if n <= 0 || i < 0 then 0 else334let k = MI.(%) i n in335ext_p n (Zbit.lor (lsl_int a (n - k)) (asr_int a k))336| BvNot n, Cons x Nil -> ext_p n (Zbit.lnot (bitv n x))337| BvAnd n, Cons x (Cons y Nil) -> let a = bitv n x in Zbit.land a (bitv n y)338| BvOr n, Cons x (Cons y Nil) -> let a = bitv n x in Zbit.lor a (bitv n y)339| BvXor n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (Zbit.lxor a (bitv n y))340| BvNand n, Cons x (Cons y Nil) ->341let a = bitv n x in ext_p n (Zbit.lnot (Zbit.land a (bitv n y)))342| BvNor n, Cons x (Cons y Nil) ->343let a = bitv n x in ext_p n (Zbit.lnot (Zbit.lor a (bitv n y)))344| BvXnor n, Cons x (Cons y Nil) ->345let a = bitv n x in ext_p n (Zbit.lxor a (Zbit.lnot (bitv n y)))346| BvComp n, Cons x (Cons y Nil) ->347let a = bitv n x in if a = bitv n y then ext_p 1 (-1) else 0348| BvNeg n, Cons x Nil ->349let a = bitv n x in350z_extract_p (lsl_int 1 n - a) 0 n351| BvAdd n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a + bitv n y)352| BvSub n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a - bitv n y)353| BvMul n, Cons x (Cons y Nil) -> let a = bitv n x in ext_p n (a * bitv n y)354| BvUdiv n, Cons x (Cons y Nil) ->355let a = bitv n x in356let b = bitv n y in357if b = 0 then ext_p n (-1) else ext_p n (MI.(/) a b)358| BvUrem n, Cons x (Cons y Nil) ->359let a = bitv n x in360let b = bitv n y in361if b = 0 then a else ext_p n (MI.(%) a b)362| BvSdiv n, Cons x (Cons y Nil) ->363let a = signed_p n x in364let b = signed_p n y in365if b = 0 then (if a < 0 then ext_p n 1 else ext_p n (-1)) else ext_p n (MI.(/) a b)366| BvSrem n, Cons x (Cons y Nil) ->367let a = signed_p n x in368let b = signed_p n y in369if b = 0 then bitv n x else ext_p n (MI.(%) a b)370| BvSmod n, Cons x (Cons y Nil) ->371let a = signed_p n x in372let b = signed_p n y in373if b = 0 then bitv n x else ext_p n (a - fdiv_p a b * b)374| BvShl n, Cons x (Cons o Nil) ->375let a = bitv n x in376let b = bitv n o in377if n <= b then 0 else ext_p n (lsl_int a b)378| BvLshr n, Cons x (Cons o Nil) ->379let a = bitv n x in380let b = bitv n o in381if n <= b then 0 else ext_p n (asr_int a b)382| BvAshr n, Cons x (Cons o Nil) ->383let a = signed_p n x in384let b = bitv n o in385let b = if n <= b then n else b in386ext_p n (asr_int a b)387| BvUlt n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a < bitv n y)388| BvUle n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a <= bitv n y)389| BvUgt n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a > bitv n y)390| BvUge n, Cons x (Cons y Nil) -> let a = bitv n x in bool_p (a >= bitv n y)391| BvSlt n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a < signed_p n y)392| BvSle n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a <= signed_p n y)393| BvSgt n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a > signed_p n y)394| BvSge n, Cons x (Cons y Nil) -> let a = signed_p n x in bool_p (a >= signed_p n y)395| _ -> 0396end397end398