From 36e2bf56109a6fdf2926dd4a47c5346d9bd5d085 Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Mon, 15 Jun 2015 15:55:07 +0200
Subject: [PATCH] define ffs in terms of _BitScanForward if _BitScanForward is
 available and not ffs

In particular, Visual Studio 2013 does not have an ffs, but it does
have a _BitScanForward that can be used to implement ffs.
Also check that at least some ffs implementation is available.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 Makefile.am       |  1 +
 configure.ac      |  6 ++++++
 isl_config_post.h |  5 +++++
 isl_ffs.c         | 24 ++++++++++++++++++++++++
 4 files changed, 36 insertions(+)
 create mode 100644 isl_ffs.c

diff --git a/Makefile.am b/Makefile.am
index a3afc08f..7c660525 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -102,6 +102,7 @@ libisl_la_SOURCES = \
 	isl_factorization.c \
 	isl_factorization.h \
 	isl_farkas.c \
+	isl_ffs.c \
 	isl_flow.c \
 	isl_fold.c \
 	isl_hash.c \
diff --git a/configure.ac b/configure.ac
index eaea5cc7..1a501e02 100644
--- a/configure.ac
+++ b/configure.ac
@@ -70,6 +70,12 @@ AS_IF([test "x$with_int" == "ximath-32"], [
 
 AC_CHECK_DECLS(ffs,[],[],[#include <strings.h>])
 AC_CHECK_DECLS(__builtin_ffs,[],[],[])
+AC_CHECK_DECLS([_BitScanForward],[],[],[#include <intrin.h>])
+if test "x$ac_cv_have_decl_ffs" = xno -a \
+		"x$ac_cv_have_decl___builtin_ffs" = xno -a \
+		"x$ac_cv_have_decl__BitScanForward" = xno; then
+	AC_MSG_ERROR([No ffs implementation found])
+fi
 
 AC_SUBST(CLANG_CXXFLAGS)
 AC_SUBST(CLANG_LDFLAGS)
diff --git a/isl_config_post.h b/isl_config_post.h
index 68e8e00f..8b609564 100644
--- a/isl_config_post.h
+++ b/isl_config_post.h
@@ -10,6 +10,11 @@
 #define ffs __builtin_ffs
 #endif
 
+#if !HAVE_DECL_FFS && !HAVE_DECL___BUILTIN_FFS && HAVE_DECL__BITSCANFORWARD
+int isl_ffs(int i);
+#define ffs isl_ffs
+#endif
+
 #ifdef GCC_WARN_UNUSED_RESULT
 #define WARN_UNUSED	GCC_WARN_UNUSED_RESULT
 #else
diff --git a/isl_ffs.c b/isl_ffs.c
new file mode 100644
index 00000000..c1ee928f
--- /dev/null
+++ b/isl_ffs.c
@@ -0,0 +1,24 @@
+#include <isl_config.h>
+
+#if !HAVE_DECL_FFS && !HAVE_DECL___BUILTIN_FFS && HAVE_DECL__BITSCANFORWARD
+#include <intrin.h>
+
+/* Implementation of ffs in terms of _BitScanForward.
+ *
+ * ffs returns the position of the least significant bit set in i,
+ * with the least significant bit is position 1, or 0 if not bits are set.
+ *
+ * _BitScanForward returns 1 if mask is non-zero and sets index
+ * to the position of the least significant bit set in i,
+ * with the least significant bit is position 0.
+ */
+int isl_ffs(int i)
+{
+	unsigned char non_zero;
+	unsigned long index, mask = i;
+
+	non_zero = _BitScanForward(&index, mask);
+
+	return non_zero ? 1 + index : 0;
+}
+#endif
-- 
2.11.4.GIT