Implement a count_leading_zeros builtin for ocaml and c. This may be a slight performance improvement and keeps compatibility with smt backend that already had a builtin for this because it can't handle the loop in the sail version. Will need implementations for prover backends.

3 files changed, 13 insertions, 0 deletions

diff --git a/lib/sail.c b/lib/sail.c
index e9c6ca37..7fc45714 100644
--- a/lib/sail.c
+++ b/lib/sail.c
@@ -767,6 +767,16 @@ void length_lbits(sail_int *rop, const lbits op)
   mpz_set_ui(*rop, op.len);
 }
 
+void count_leading_zeros(sail_int *rop, const lbits op)
+{
+  if (mpz_cmp_ui(*op.bits, 0) == 0) {
+    mpz_set_ui(*rop, op.len);
+  } else {
+    size_t bits = mpz_sizeinbase(*op.bits, 2);
+    mpz_set_ui(*rop, op.len - bits);
+  }
+}
+
 bool eq_bits(const lbits op1, const lbits op2)
 {
   assert(op1.len == op2.len);
diff --git a/lib/sail.h b/lib/sail.h
index 1a123cf4..eddf6e41 100644
--- a/lib/sail.h
+++ b/lib/sail.h
@@ -262,6 +262,7 @@ fbits fast_sign_extend(const fbits op, const uint64_t n, const uint64_t m);
 fbits fast_sign_extend2(const sbits op, const uint64_t m);
 
 void length_lbits(sail_int *rop, const lbits op);
+void count_leading_zeros(sail_int *rop, const lbits op);
 
 bool eq_bits(const lbits op1, const lbits op2);
 bool EQUAL(lbits)(const lbits op1, const lbits op2);
diff --git a/lib/vector_dec.sail b/lib/vector_dec.sail
index de63c1a1..909f3898 100644
--- a/lib/vector_dec.sail
+++ b/lib/vector_dec.sail
@@ -37,6 +37,8 @@ val vector_length = {
 
 overload length = {bitvector_length, vector_length}
 
+val count_leading_zeros = "count_leading_zeros" : forall 'N , 'N >= 1. bits('N) -> {'n, 0 <= 'n <= 'N . atom('n)}
+
 val "print_bits" : forall 'n. (string, bits('n)) -> unit
 
 val "prerr_bits" : forall 'n. (string, bits('n)) -> unit