library colibrilib.zarith — module ZbitThe bit operations of Zarith on the integers (two's complement, with an infinite sign extension). The logic functions are defined by their bits (bittest); the program functions are the functions of Zarith of the same meaning (zarith.drv). The interface is consistent: the module zbit_model.ZbitModel implements it.
module Zbit148use int.Int149use int.Power150use int.EuclideanDivision as ED151use int.MinMax152use mach.int.Int63153154predicate bittest (x i:int)155156axiom bittest_neg : forall x i. i < 0 -> not (bittest x i)157axiom ext_bittest : forall x y. (forall i. i >= 0 -> bittest x i = bittest y i) -> x = y158axiom even_bittest : forall x i. 0 <= i -> (bittest (2*x) i) =159if i = 0 then False else bittest x (i-1)160axiom bittest_0: forall i. not (bittest 0 i)161axiom bittest_1: forall i. (bittest 1 i) = (i=0)162axiom odd_bittest : forall x i. 0 <= i -> (bittest (2*x+1) i) =163if i = 0 then True else bittest x (i-1)164165predicate subset (a:int) (b:int) = forall i. bittest a i -> bittest b i166167function asr (x offset:int) : int168axiom def_asr: forall x offset. forall i. i >= 0 ->169bittest (asr x offset) i = bittest x (i + offset)170axiom asr_gt: forall x offset. 0 < x /\ offset < 0 -> x < (asr x offset)171axiom asr_eq: forall x. (asr x 0) = x172173function lsl (x offset:int) : int = asr x (-offset)174axiom lsl_succ: forall x i. x > 0 -> i >= 0 -> asr x (-(i+1)) = 2 * (asr x (-i))175axiom bittest_sub_lsl: forall x s j. 0 <= j < s -> bittest (x - lsl 1 s) j = bittest x j176
The high bits of a negative number x - 2^s with 0 <= x < 2^s are set
axiom bittest_sub_lsl_high: forall x s j. 0 <= x -> 0 <= s <= j -> x < lsl 1 s ->178bittest (x - lsl 1 s) j179180function mask (k:int) : int = lsl 1 k - 1181axiom mask_bits: forall k i. 0 <= k -> 0 <= i < k -> bittest (mask k) i182axiom mask_bits_high: forall k i. 0 <= k -> i >= k -> not (bittest (mask k) i)183axiom mask_nonneg : forall k:int. 0 <= k -> 0 <= asr 1 (-k) - 1184185function numbits (x:int) : int186axiom numbits_0: numbits 0 = 0187axiom numbits_1: numbits 1 = 1188axiom numbits_top_bit: forall x. x > 0 -> bittest x (numbits x - 1)189axiom numbits_high_clear: forall x. x > 0 -> (forall i. i >= numbits x -> not (bittest x i))190axiom numbits_gt_pos: forall x y. 0 <= x -> 0 <= y -> numbits x < numbits y -> x < y191axiom numbits_ge_pos: forall x y. 0 <= x -> 0 <= y -> x <= y -> numbits x <= numbits y192axiom numbits_lt_lsl: forall x n. 0 <= x -> x < lsl 1 n -> numbits x <= n193axiom numbits_lsl: forall n. 0 <= n -> numbits (lsl 1 n) = n + 1194axiom numbits_lsl_lt: forall x. 0 <= x -> x < lsl 1 (numbits x)195axiom numbits_lsl_le: forall x. 0 < x -> lsl 1 (numbits x - 1) <= x196197axiom mask_numbits: forall k. 0 <= k -> numbits (mask k) = k198199axiom asr_numbits: forall x offset. 0 < x -> numbits (asr x offset) = max 0 (numbits x - offset)200axiom asr_nonneg: forall x offset. 0 <= x -> 0 <= asr x offset201202203function land (x y:int) : int204axiom def_land: forall x y. forall i. (bittest (land x y) i) = (bittest x i /\ bittest y i)205axiom land_nonneg: forall x y. 0 <= x -> 0 <= y -> 0 <= land x y206axiom land_nonneg_l: forall x y. 0 <= x -> 0 <= land x y207axiom land_le: forall x y. 0 <= x -> 0 <= y -> land x y <= y208axiom land_numbits: forall x y. 0 <= x -> 0 <= y -> (numbits (land x y)) <= min (numbits x) (numbits y)209210function lor (x y:int) : int211axiom def_lor: forall x y. forall i. (bittest (lor x y) i) = (bittest x i \/ bittest y i)212axiom lor_nonneg: forall x y. 0 <= x -> 0 <= y -> 0 <= lor x y213axiom lor_le: forall x y. 0 <= x -> 0 <= y -> y <= lor x y214axiom lor_numbits: forall x y. 0 <= x -> 0 <= y -> (numbits (lor x y)) = max (numbits x) (numbits y)215216function lnot (x:int) : int217axiom def_lnot: forall x. forall i. 0 <= i -> (bittest (lnot x) i) = not (bittest x i)218219function set (x:int) (offset:int) : int (* = lor x (lsl 1 offset) *)220axiom def_set: forall x offset. forall i. 0 <= i -> bittest (set x offset) i = (i = offset \/ bittest x i)221axiom set_nonneg: forall x offset. 0 <= x -> 0 <= set x offset222axiom numbits_set: forall x offset. 0 <= x -> 0 <= offset ->223numbits (set x offset) = max (numbits x) (offset+1)224225function unset (x:int) (offset:int) : int = land x (lnot (lsl 1 offset))226function lxor (x y:int) : int = lor (land x (lnot y)) (land (lnot x) y)227axiom unset_nonneg: forall x offset. 0 <= x -> 0 <= land x (lnot (asr 1 (-offset)))228axiom numbits_unset_le: forall x offset. 0 <= x -> 0 <= offset ->229numbits (unset x offset) <= numbits x230231function change (x:int) (offset:int) (v:bool) : int (* = if v then lor x (lsl 1 offset) else land x (lnot (lsl 1 offset)) *)232axiom def_change: forall x offset v. forall i. 0 <= i -> bittest (change x offset v) i = if i= offset then v else bittest x i234axiom change_nonneg: forall x offset v. 0 <= x -> 0 <= change x offset v235axiom numbits_change_true: forall x offset. 0 <= x -> 0 <= offset ->236numbits (change x offset True) = max (numbits x) (offset+1)237
Carry into the bit i of x + y
predicate carry (x y i: int)240axiom carry_0: forall x y. not (carry x y 0)241axiom carry_succ: forall x y i. 0 <= i ->242(carry x y (i+1) <-> ((bittest x i /\ bittest y i) \/ ((bittest x i \/ bittest y i) /\ carry x y i)))243axiom bittest_add: forall x y i. 0 <= i ->244(bittest (x + y) i <-> ((bittest x i <-> bittest y i) <-> carry x y i))245
The integer whose bit i is f i, for 0 <= i < n
function of_bits (f: int -> bool) (n:int) : int248axiom of_bits_nonneg: forall f n. 0 <= of_bits f n249axiom def_of_bits: forall f n i. 0 <= i -> (bittest (of_bits f n) i <-> (i < n /\ f i))250
The arithmetic meaning of the shifts, called explicitly
val ghost asr_div (x n:int) : unit253requires { 0 <= n }254ensures { asr x n = ED.div x (power 2 n) }255256val ghost lsl_mul (x n:int) : unit257requires { 0 <= n }258ensures { lsl x n = x * power 2 n }259260val land (x y:int) : int261ensures { result = land x y }262263val lor (x y:int) : int264ensures { result = lor x y }265266val lnot (x:int) : int267ensures { result = lnot x }268269val lxor (x y:int) : int270ensures { result = lxor x y }271272val numbits (x:int) : int273requires { 0 <= x }274ensures { result = numbits x }275
The executable bit tests and shifts. Zarith takes the index or the offset as an OCaml int and rejects a negative one (zarith.drv): hence the type int63 and the precondition. Ghost code uses the logic functions bittest, lsl, asr and mask, unbounded.
val test_bit (x:int) (i:int63) : bool282requires { 0 <= i }283ensures { result <-> bittest x i }284285val lsl63 (x:int) (offset:int63) : int286requires { 0 <= offset }287ensures { result = lsl x offset }288289val asr63 (x:int) (offset:int63) : int290requires { 0 <= offset }291ensures { result = asr x offset }292293val mask63 (k:int63) : int294requires { 0 <= k }295ensures { result = mask k }296
The position of the lowest bit set, of a non zero integer
val trailing_zeros (x:int) : int299requires { x <> 0 }300ensures { 0 <= result }301ensures { bittest x result }302ensures { forall j. 0 <= j < result -> not (bittest x j) }303end304