Common — library colibrilib.zarith — module Zbit

The 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.

148
module Zbit
149
use int.Int
150
use int.Power
151
use int.EuclideanDivision as ED
152
use int.MinMax
153
use mach.int.Int63
154
155
predicate
bittest
(x i:int)
156
157
axiom
bittest_neg
: forall x i. i < 0 -> not (bittest x i)
158
axiom
ext_bittest
: forall x y. (forall i. i >= 0 -> bittest x i = bittest y i) -> x = y
159
axiom
even_bittest
: forall x i. 0 <= i -> (bittest (2*x) i) =
160
if i = 0 then False else bittest x (i-1)
161
axiom
bittest_0
: forall i. not (bittest 0 i)
162
axiom
bittest_1
: forall i. (bittest 1 i) = (i=0)
163
axiom
odd_bittest
: forall x i. 0 <= i -> (bittest (2*x+1) i) =
164
if i = 0 then True else bittest x (i-1)
165
166
predicate
subset
(a:int) (b:int) = forall i. bittest a i -> bittest b i
167
168
function
asr
(x offset:int) : int
169
axiom
def_asr
: forall x offset. forall i. i >= 0 ->
170
bittest (asr x offset) i = bittest x (i + offset)
171
axiom
asr_gt
: forall x offset. 0 < x /\ offset < 0 -> x < (asr x offset)
172
axiom
asr_eq
: forall x. (asr x 0) = x
173
174
function
lsl
(x offset:int) : int = asr x (-offset)
175
axiom
lsl_succ
: forall x i. x > 0 -> i >= 0 -> asr x (-(i+1)) = 2 * (asr x (-i))
176
axiom
bittest_sub_lsl
: forall x s j. 0 <= j < s -> bittest (x - lsl 1 s) j = bittest x j

The high bits of a negative number x - 2^s with 0 <= x < 2^s are set

178
axiom
bittest_sub_lsl_high
: forall x s j. 0 <= x -> 0 <= s <= j -> x < lsl 1 s ->
179
bittest (x - lsl 1 s) j
180
181
function
mask
(k:int) : int = lsl 1 k - 1
182
axiom
mask_bits
: forall k i. 0 <= k -> 0 <= i < k -> bittest (mask k) i
183
axiom
mask_bits_high
: forall k i. 0 <= k -> i >= k -> not (bittest (mask k) i)
184
axiom
mask_nonneg
: forall k:int. 0 <= k -> 0 <= asr 1 (-k) - 1
185
186
function
numbits
(x:int) : int
187
axiom
numbits_0
: numbits 0 = 0
188
axiom
numbits_1
: numbits 1 = 1
189
axiom
numbits_top_bit
: forall x. x > 0 -> bittest x (numbits x - 1)
190
axiom
numbits_high_clear
: forall x. x > 0 -> (forall i. i >= numbits x -> not (bittest x i))
191
axiom
numbits_gt_pos
: forall x y. 0 <= x -> 0 <= y -> numbits x < numbits y -> x < y
192
axiom
numbits_ge_pos
: forall x y. 0 <= x -> 0 <= y -> x <= y -> numbits x <= numbits y
193
axiom
numbits_lt_lsl
: forall x n. 0 <= x -> x < lsl 1 n -> numbits x <= n
194
axiom
numbits_lsl
: forall n. 0 <= n -> numbits (lsl 1 n) = n + 1
195
axiom
numbits_lsl_lt
: forall x. 0 <= x -> x < lsl 1 (numbits x)
196
axiom
numbits_lsl_le
: forall x. 0 < x -> lsl 1 (numbits x - 1) <= x
197
198
axiom
mask_numbits
: forall k. 0 <= k -> numbits (mask k) = k
199
200
axiom
asr_numbits
: forall x offset. 0 < x -> numbits (asr x offset) = max 0 (numbits x - offset)
201
axiom
asr_nonneg
: forall x offset. 0 <= x -> 0 <= asr x offset
202
203
204
function
land
(x y:int) : int
205
axiom
def_land
: forall x y. forall i. (bittest (land x y) i) = (bittest x i /\ bittest y i)
206
axiom
land_nonneg
: forall x y. 0 <= x -> 0 <= y -> 0 <= land x y
207
axiom
land_nonneg_l
: forall x y. 0 <= x -> 0 <= land x y
208
axiom
land_le
: forall x y. 0 <= x -> 0 <= y -> land x y <= y
209
axiom
land_numbits
: forall x y. 0 <= x -> 0 <= y -> (numbits (land x y)) <= min (numbits x) (numbits y)
210
211
function
lor
(x y:int) : int
212
axiom
def_lor
: forall x y. forall i. (bittest (lor x y) i) = (bittest x i \/ bittest y i)
213
axiom
lor_nonneg
: forall x y. 0 <= x -> 0 <= y -> 0 <= lor x y
214
axiom
lor_le
: forall x y. 0 <= x -> 0 <= y -> y <= lor x y
215
axiom
lor_numbits
: forall x y. 0 <= x -> 0 <= y -> (numbits (lor x y)) = max (numbits x) (numbits y)
216
217
function
lnot
(x:int) : int
218
axiom
def_lnot
: forall x. forall i. 0 <= i -> (bittest (lnot x) i) = not (bittest x i)
219
220
function
set
(x:int) (offset:int) : int (* = lor x (lsl 1 offset) *)
221
axiom
def_set
: forall x offset. forall i. 0 <= i -> bittest (set x offset) i = (i = offset \/ bittest x i)
222
axiom
set_nonneg
: forall x offset. 0 <= x -> 0 <= set x offset
223
axiom
numbits_set
: forall x offset. 0 <= x -> 0 <= offset ->
224
numbits (set x offset) = max (numbits x) (offset+1)
225
226
function
unset
(x:int) (offset:int) : int = land x (lnot (lsl 1 offset))
227
function
lxor
(x y:int) : int = lor (land x (lnot y)) (land (lnot x) y)
228
axiom
unset_nonneg
: forall x offset. 0 <= x -> 0 <= land x (lnot (asr 1 (-offset)))
229
axiom
numbits_unset_le
: forall x offset. 0 <= x -> 0 <= offset ->
230
numbits (unset x offset) <= numbits x
231
232
function
change
(x:int) (offset:int) (v:bool) : int (* = if v then lor x (lsl 1 offset) else land x (lnot (lsl 1 offset)) *)
234
axiom
def_change
: forall x offset v. forall i. 0 <= i -> bittest (change x offset v) i = if i= offset then v else bittest x i
235
axiom
change_nonneg
: forall x offset v. 0 <= x -> 0 <= change x offset v
236
axiom
numbits_change_true
: forall x offset. 0 <= x -> 0 <= offset ->
237
numbits (change x offset True) = max (numbits x) (offset+1)

Carry into the bit i of x + y

240
predicate
carry
(x y i: int)
241
axiom
carry_0
: forall x y. not (carry x y 0)
242
axiom
carry_succ
: forall x y i. 0 <= i ->
243
(carry x y (i+1) <-> ((bittest x i /\ bittest y i) \/ ((bittest x i \/ bittest y i) /\ carry x y i)))
244
axiom
bittest_add
: forall x y i. 0 <= i ->
245
(bittest (x + y) i <-> ((bittest x i <-> bittest y i) <-> carry x y i))

The integer whose bit i is f i, for 0 <= i < n

248
function
of_bits
(f: int -> bool) (n:int) : int
249
axiom
of_bits_nonneg
: forall f n. 0 <= of_bits f n
250
axiom
def_of_bits
: forall f n i. 0 <= i -> (bittest (of_bits f n) i <-> (i < n /\ f i))

The arithmetic meaning of the shifts, called explicitly

253
val ghost
asr_div
(x n:int) : unit
254
requires { 0 <= n }
255
ensures { asr x n = ED.div x (power 2 n) }
256
257
val ghost
lsl_mul
(x n:int) : unit
258
requires { 0 <= n }
259
ensures { lsl x n = x * power 2 n }
260
261
val
land
(x y:int) : int
262
ensures { result = land x y }
263
264
val
lor
(x y:int) : int
265
ensures { result = lor x y }
266
267
val
lnot
(x:int) : int
268
ensures { result = lnot x }
269
270
val
lxor
(x y:int) : int
271
ensures { result = lxor x y }
272
273
val
numbits
(x:int) : int
274
requires { 0 <= x }
275
ensures { result = numbits x }

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.

282
val
test_bit
(x:int) (i:int63) : bool
283
requires { 0 <= i }
284
ensures { result <-> bittest x i }
285
286
val
lsl63
(x:int) (offset:int63) : int
287
requires { 0 <= offset }
288
ensures { result = lsl x offset }
289
290
val
asr63
(x:int) (offset:int63) : int
291
requires { 0 <= offset }
292
ensures { result = asr x offset }
293
294
val
mask63
(k:int63) : int
295
requires { 0 <= k }
296
ensures { result = mask k }

The position of the lowest bit set, of a non zero integer

299
val
trailing_zeros
(x:int) : int
300
requires { x <> 0 }
301
ensures { 0 <= result }
302
ensures { bittest x result }
303
ensures { forall j. 0 <= j < result -> not (bittest x j) }
304
end