summaryrefslogtreecommitdiffstats
path: root/libtommath/bn_mp_cnt_lsb.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtommath/bn_mp_cnt_lsb.c')
-rw-r--r--libtommath/bn_mp_cnt_lsb.c49
1 files changed, 49 insertions, 0 deletions
diff --git a/libtommath/bn_mp_cnt_lsb.c b/libtommath/bn_mp_cnt_lsb.c
new file mode 100644
index 0000000..6447a1f
--- /dev/null
+++ b/libtommath/bn_mp_cnt_lsb.c
@@ -0,0 +1,49 @@
+#include <tommath.h>
+#ifdef BN_MP_CNT_LSB_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
+ */
+
+static const int lnz[16] = {
+ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
+};
+
+/* Counts the number of lsbs which are zero before the first zero bit */
+int mp_cnt_lsb(mp_int *a)
+{
+ int x;
+ mp_digit q, qq;
+
+ /* easy out */
+ if (mp_iszero(a) == 1) {
+ return 0;
+ }
+
+ /* scan lower digits until non-zero */
+ for (x = 0; x < a->used && a->dp[x] == 0; x++);
+ q = a->dp[x];
+ x *= DIGIT_BIT;
+
+ /* now scan this digit until a 1 is found */
+ if ((q & 1) == 0) {
+ do {
+ qq = q & 15;
+ x += lnz[qq];
+ q >>= 4;
+ } while (qq == 0);
+ }
+ return x;
+}
+
+#endif