Common — library colibrilib.bv_sem — module Smtlib

The SMT–LIB semantics

The definitions of the theory FixedSizeBitVectors (SMT–LIB 2.7, Theories/FixedSizeBitVectors.smt2, last updated 2025–09–09) and the abbreviations of the logic QF_BV (Logics/QF_BV.smt2), as written there (trusted). A bit–vector b: [0, m) → {0, 1} is the integer 0 <= v < 2^m whose bit x is b(x) (b(x) = 1 is bittest v x): λx:[0, m). f(x) is Zbit.of_bits f m, bv2nat(b) is v.

408
module Smtlib
409
use int.Int
410
use int.Power
411
use int.EuclideanDivision as E
412
use colibrilib.zarith.Zbit

λx:[0, m). f(x)

415
function
lam
(m:int) (f:int -> bool) : int = Zbit.of_bits f m

b(x) = 1

418
predicate
bit
(b x:int) = Zbit.bittest b x
419
420
function
bv2nat
(b:int) : int = b
421
422
function
bv2int
(m b:int) : int = if not (bit b (m - 1)) then bv2nat b else bv2nat b - power 2 m
423
424
function
nat2bv
(m n:int) : int = E.mod n (power 2 m)

The theory

s of size n, t of size m

429
function
concat
(n m s t:int) : int =
430
lam (n + m) (fun x -> if x < m then bit t x else bit s (x - m))
431
432
function
extract
(i j s:int) : int = lam (i - j + 1) (fun x -> bit s (j + x))
433
434
function
bvnot
(m s:int) : int = lam m (fun x -> not (bit s x))
435
436
function
bvand
(m s t:int) : int = lam m (fun x -> if not (bit s x) then false else bit t x)
437
438
function
bvor
(m s t:int) : int = lam m (fun x -> if bit s x then true else bit t x)
439
440
function
bvneg
(m s:int) : int = nat2bv m (power 2 m - bv2nat s)
441
442
function
bvadd
(m s t:int) : int = nat2bv m (bv2nat s + bv2nat t)
443
444
function
bvmul
(m s t:int) : int = nat2bv m (bv2nat s * bv2nat t)
445
446
function
bvudiv
(m s t:int) : int =
447
if bv2nat t = 0 then lam m (fun _ -> true) else nat2bv m (E.div (bv2nat s) (bv2nat t))
448
449
function
bvurem
(m s t:int) : int =
450
if bv2nat t = 0 then s else nat2bv m (E.mod (bv2nat s) (bv2nat t))
451
452
function
bvshl
(m s t:int) : int = nat2bv m (bv2nat s * power 2 (bv2nat t))
453
454
function
bvlshr
(m s t:int) : int = nat2bv m (E.div (bv2nat s) (power 2 (bv2nat t)))
455
456
predicate
bvult
(s t:int) = bv2nat s < bv2nat t
457
458
function
ubv_to_int
(s:int) : int = bv2nat s
459
460
function
sbv_to_int
(m s:int) : int = bv2int m s
461
462
function
int_to_bv
(n x:int) : int = nat2bv n (E.mod x (power 2 n))

The abbreviations of QF_BV, for s, t of size m

466
function
bvnand
(m s t:int) : int = bvnot m (bvand m s t)
467
468
function
bvnor
(m s t:int) : int = bvnot m (bvor m s t)
469
470
function
bvxor
(m s t:int) : int = bvor m (bvand m s (bvnot m t)) (bvand m (bvnot m s) t)
471
472
function
bvxnor
(m s t:int) : int = bvor m (bvand m s t) (bvand m (bvnot m s) (bvnot m t))
473
Valid (27ms) (colibri2)
474
let rec ghost function
bvcomp
(m s t:int) : int
475
variant { m }
476
= if m <= 1 then bvxnor m s t
477
else bvand 1 (bvxnor 1 (extract (m - 1) (m - 1) s) (extract (m - 1) (m - 1) t))
478
(bvcomp (m - 1) (extract (m - 2) 0 s) (extract (m - 2) 0 t))
479
480
function
bvsub
(m s t:int) : int = bvadd m s (bvneg m t)

((_ extract |m-1| |m-1|) s)

483
function
msb
(m s:int) : int = extract (m - 1) (m - 1) s
484
485
function
bvsdiv
(m s t:int) : int =
486
let msb_s = msb m s in
487
let msb_t = msb m t in
488
if msb_s = 0 /\ msb_t = 0 then bvudiv m s t
489
else if msb_s = 1 /\ msb_t = 0 then bvneg m (bvudiv m (bvneg m s) t)
490
else if msb_s = 0 /\ msb_t = 1 then bvneg m (bvudiv m s (bvneg m t))
491
else bvudiv m (bvneg m s) (bvneg m t)
492
493
function
bvsrem
(m s t:int) : int =
494
let msb_s = msb m s in
495
let msb_t = msb m t in
496
if msb_s = 0 /\ msb_t = 0 then bvurem m s t
497
else if msb_s = 1 /\ msb_t = 0 then bvneg m (bvurem m (bvneg m s) t)
498
else if msb_s = 0 /\ msb_t = 1 then bvurem m s (bvneg m t)
499
else bvneg m (bvurem m (bvneg m s) (bvneg m t))
500
501
function
bvsmod
(m s t:int) : int =
502
let msb_s = msb m s in
503
let msb_t = msb m t in
504
let abs_s = if msb_s = 0 then s else bvneg m s in
505
let abs_t = if msb_t = 0 then t else bvneg m t in
506
let u = bvurem m abs_s abs_t in
507
if u = 0 then u
508
else if msb_s = 0 /\ msb_t = 0 then u
509
else if msb_s = 1 /\ msb_t = 0 then bvadd m (bvneg m u) t
510
else if msb_s = 0 /\ msb_t = 1 then bvadd m u t
511
else bvneg m u
512
513
predicate
bvule
(s t:int) = bvult s t \/ s = t
514
515
predicate
bvugt
(s t:int) = bvult t s
516
517
predicate
bvuge
(s t:int) = bvult t s \/ s = t
518
519
predicate
bvslt
(m s t:int) =
520
(msb m s = 1 /\ msb m t = 0) \/ (msb m s = msb m t /\ bvult s t)
521
522
predicate
bvsle
(m s t:int) =
523
(msb m s = 1 /\ msb m t = 0) \/ (msb m s = msb m t /\ bvule s t)
524
525
predicate
bvsgt
(m s t:int) = bvslt m t s
526
527
predicate
bvsge
(m s t:int) = bvsle m t s
528
529
function
bvashr
(m s t:int) : int =
530
if msb m s = 0 then bvlshr m s t else bvnot m (bvlshr m (bvnot m s) t)

((_ repeat j) t), t of size m

  Valid (30ms) (colibri2)
533
let rec ghost function
repeat
(j m t:int) : int
534
variant { j }
535
= if j <= 1 then t else concat m (m * (j - 1)) t (repeat (j - 1) m t)
536
537
function
zero_extend
(i m t:int) : int =
538
if i = 0 then t else concat i m (repeat i 1 0) t
539
540
function
sign_extend
(i m t:int) : int =
541
if i = 0 then t else concat i m (repeat i 1 (extract (m - 1) (m - 1) t)) t
542
Valid (32ms) (colibri2)
543
let rec ghost function
rotate_left
(i m t:int) : int
544
variant { i }
545
= if i <= 0 then t
546
else if m = 1 then t
547
else rotate_left (i - 1) m (concat (m - 1) 1 (extract (m - 2) 0 t) (extract (m - 1) (m - 1) t))
548
Valid (29ms) (colibri2)
549
let rec ghost function
rotate_right
(i m t:int) : int
550
variant { i }
551
= if i <= 0 then t
552
else if m = 1 then t
553
else rotate_right (i - 1) m (concat 1 (m - 1) (extract 0 0 t) (extract (m - 1) 1 t))
554
end