From: Benjamin Kaduk <kaduk@mit.edu>
Date: Wed, 14 Jan 2015 20:05:35 +0000 (-0500)
Subject: opr: implement the BSD ffs() functions
X-Git-Tag: openafs-stable-1_8_0pre1~388
X-Git-Url: https://git.openafs.org/?p=openafs.git;a=commitdiff_plain;h=d4369917;hp=6419d241866af95942d285b2e07dd510a43086f6

opr: implement the BSD ffs() functions

Provide opr implementations of ffs(), fls(), ffsll(), and flsll().
There is no need to provide the 'long' form, since int is 32 bits
and long long is 64 bits.

These functions return the index of the first (or last) bit set
in a given (long long) word, or zero if no bits are set.

Change-Id: I126000f8b650f41d67567a9af659e0805478af2d
Reviewed-on: http://gerrit.openafs.org/11671
Tested-by: BuildBot <buildbot@rampaginggeek.com>
Reviewed-by: Jeffrey Altman <jaltman@your-file-system.com>
Reviewed-by: Daria Brashear <shadow@your-file-system.com>
---

diff --git a/src/opr/Makefile.in b/src/opr/Makefile.in
index af6a61b..647eaca 100644
--- a/src/opr/Makefile.in
+++ b/src/opr/Makefile.in
@@ -9,6 +9,7 @@ LT_libs = $(LIB_hcrypto) $(LIB_roken)
 HEADERS = $(TOP_INCDIR)/afs/opr.h \
 	  $(TOP_INCDIR)/afs/opr_assert.h \
 	  $(TOP_INCDIR)/opr/dict.h \
+	  $(TOP_INCDIR)/opr/ffs.h \
 	  $(TOP_INCDIR)/opr/fmt.h \
 	  $(TOP_INCDIR)/opr/jhash.h \
 	  $(TOP_INCDIR)/opr/lock.h \
@@ -45,6 +46,9 @@ $(TOP_INCDIR)/afs/opr_assert.h: ${srcdir}/opr_assert.h
 $(TOP_INCDIR)/opr/dict.h: ${srcdir}/dict.h
 	$(INSTALL_DATA) $? $@
 
+$(TOP_INCDIR)/opr/ffs.h: ${srcdir}/ffs.h
+	$(INSTALL_DATA) $? $@
+
 $(TOP_INCDIR)/opr/fmt.h: ${srcdir}/fmt.h
 	$(INSTALL_DATA) $? $@
 
diff --git a/src/opr/NTMakefile b/src/opr/NTMakefile
index 7f49d3b..127c407 100644
--- a/src/opr/NTMakefile
+++ b/src/opr/NTMakefile
@@ -14,6 +14,7 @@ INCFILES = \
 	$(INCFILEDIR)\opr.h \
 	$(INCFILEDIR)\opr_assert.h \
 	$(DESTDIR)\include\opr\dict.h \
+	$(DESTDIR)\include\opr\ffs.h \
 	$(DESTDIR)\include\opr\fmt.h \
 	$(DESTDIR)\include\opr\jhash.h \
 	$(DESTDIR)\include\opr\proc.h \
diff --git a/src/opr/ffs.h b/src/opr/ffs.h
new file mode 100644
index 0000000..9a9ff6e
--- /dev/null
+++ b/src/opr/ffs.h
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2014 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * This contains portable implementations of the BSD ffs() suite of functions,
+ * which locate the first or last bit set in a bit string.
+ */
+
+#ifndef OPENAFS_OPR_FFS_H
+#define OPENAFS_OPR_FFS_H
+
+static_inline int
+opr_ffs(int value)
+{
+    afs_int32 i;
+    afs_uint32 tmp = value;
+
+    if (tmp == 0)
+	return 0;
+    /* This loop must terminate because tmp is nonzero and thus has at least
+     * one bit set. */
+    for (i = 1;; ++i) {
+	if (tmp & 1u)
+	    return i;
+	else
+	    tmp >>= 1;
+    }
+    /* NOTREACHED */
+}
+
+static_inline int
+opr_ffsll(long long value)
+{
+    afs_int32 i;
+    afs_uint64 tmp = value;
+
+    if (tmp == 0)
+	return 0;
+    /* This loop must terminate because tmp is nonzero and thus has at least
+     * one bit set. */
+    for (i = 1;; ++i) {
+	if (tmp & 1ull)
+	    return i;
+	else
+	    tmp >>= 1;
+    }
+    /* NOTREACHED */
+}
+
+static_inline int
+opr_fls(int value)
+{
+    afs_int32 i;
+    /* tmp must be unsigned to avoid undefined behavior. */
+    afs_uint32 tmp = value;
+
+    if (tmp == 0)
+	return 0;
+    /* This loop must terminate because tmp is nonzero and thus has at least
+     * one bit set. */
+    for (i = 32;; --i) {
+	if (tmp & 0x80000000u)
+	    return i;
+	else
+	    tmp <<= 1;
+    }
+    /* NOTREACHED */
+}
+
+static_inline int
+opr_flsll(long long value)
+{
+    afs_int32 i;
+    /* tmp must be unsigned to avoid undefined behavior. */
+    afs_uint64 tmp = value;
+
+    if (tmp == 0)
+	return 0;
+    /* This loop must terminate because tmp is nonzero and thus has at least
+     * one bit set. */
+    for (i = 64;; --i) {
+	if (tmp & 0x8000000000000000ull)
+	    return i;
+	else
+	    tmp <<= 1;
+    }
+    /* NOTREACHED */
+}
+
+#endif /* OPENAFS_OPR_FFS_H */