summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@linux.intel.com>2012-03-20 02:51:11 (GMT)
committerH. Peter Anvin <hpa@linux.intel.com>2012-03-20 02:51:11 (GMT)
commit11bb3f9bfe081ae28f175a50cf848dd82c13023c (patch)
treecb32015e9e11ef5a318e51e45b3d0fa101811422
parente9675457d605686fb76e34539d14e1a8893269f0 (diff)
downloadpbn-11bb3f9bfe081ae28f175a50cf848dd82c13023c.zip
pbn-11bb3f9bfe081ae28f175a50cf848dd82c13023c.tar.gz
pbn-11bb3f9bfe081ae28f175a50cf848dd82c13023c.tar.bz2
pbn-11bb3f9bfe081ae28f175a50cf848dd82c13023c.tar.xz
pbn_ctz: Add function to count trailing zeroes
Add pbn_ctz() to count the number of trailing zeroes in a nonzero number. This is a useful operation in decimal-to-binary floating point conversion, and probably all other kinds of things.
-rw-r--r--Makefile2
-rw-r--r--pbn_ctz.c85
2 files changed, 86 insertions, 1 deletions
diff --git a/Makefile b/Makefile
index b2724f1..7b3cbfb 100644
--- a/Makefile
+++ b/Makefile
@@ -5,7 +5,7 @@ AR = ar
RANLIB = ranlib
LIBOBJ = pbn_add.o pbn_cmp.o pbn_dump.o pbn_init.o pbn_mul.o pbn_muls.o \
- pbn_shift.o pbn_and.o pbn_or.o pbn_xor.o pbn_bit.o \
+ pbn_shift.o pbn_and.o pbn_or.o pbn_xor.o pbn_bit.o pbn_ctz.o \
pbn_abs.o pbn_div.o pbn_divs.o
LIB = pbn.a
diff --git a/pbn_ctz.c b/pbn_ctz.c
new file mode 100644
index 0000000..07767ef
--- /dev/null
+++ b/pbn_ctz.c
@@ -0,0 +1,85 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * pbn_ctz.c
+ */
+
+#include <string.h>
+#include <limits.h>
+#include "pbnint.h"
+
+static int pbn_limb_ctz(pbn_limb_t v)
+{
+ int p = PBN_LIMB_BITS;
+
+#if defined(__GNUC__) && __GNUC__ >= 4
+ if (sizeof(pbn_limb_t) == sizeof(int))
+ return __builtin_ctz(v);
+ if (sizeof(pbn_limb_t) == sizeof(long))
+ return __builtin_ctzl(v);
+ if (sizeof(pbn_limb_t) == sizeof(long long))
+ return __builtin_ctzll(v);
+ /* else fall through, wtf... */
+#endif
+
+#if PBN_LIMB_BITS > 32
+ if (v & 0xffffffff)
+ p -= 32;
+ else
+ v >>= 32;
+#endif
+
+ if (v & 0xffff)
+ p -= 16;
+ else
+ v >>= 16;
+
+ if (v & 0xff)
+ p -= 8;
+ else
+ v >>= 8;
+
+ if (v & 0xf)
+ p -= 4;
+ else
+ v >>= 4;
+
+ if (v & 0x3)
+ p -= 2;
+ else
+ v >>= 2;
+
+ if (v & 0x1)
+ p -= 1;
+ else
+ v >>= 1;
+
+ return p;
+}
+
+int pbn_ctz(const struct pbn *pbn)
+{
+ int n = 0;
+ const pbn_limb_t *p = pbn->num;
+
+ if (pbn->bits == 0)
+ return -1; /* Zero value */
+
+ while (*p == 0) {
+ p++;
+ n += PBN_LIMB_BITS;
+ }
+
+ n += pbn_limb_ctz(*p);
+ return n;
+}