Add a Bits utility library.

This library captures use of __builtin_popcount and __builtin_ctz on
GCC/clang and hopefully handles the MSVC case.

Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>

1 files changed, 73 insertions, 0 deletions

diff --git a/common/bits.h b/common/bits.h
new file mode 100644
index 00000000..1abf6735
--- /dev/null
+++ b/common/bits.h
@@ -0,0 +1,73 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (c) 2013  Mike Pedersen
+ *  Copyright (C) 2021  Symbiflow Authors
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+// This is a small library for implementing common bit vector utilities,
+// namely:
+//
+//  - popcount : The number of bits set in an unsigned int
+//  - ctz : The number of trailing zero bits in an unsigned int.
+//          Must be called with a value that has at least 1 bit set.
+//
+// These methods will typically use instrinics when available, and have a
+// generic fallback in the event that the instrinic is not available.
+//
+// If clz (count leading zeros) is needed, it can be added when needed.
+#ifndef BITS_H
+#define BITS_H
+
+#if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86))
+#include <intrin.h>
+#pragma intrinsic(_BitScanForward,_BitScanReverse,__popcnt)
+#endif
+
+// Uses plain nextpnr namespace to avoid header inclusion nightmare that is
+// "nextpnr.h".
+namespace nextpnr {
+
+struct Bits {
+    static int generic_popcount(unsigned int x);
+    static int generic_ctz(unsigned int x);
+
+    static int popcount(unsigned int x) {
+#if defined(__GNUC__) || defined(__clang__)
+        return __builtin_popcount(x);
+#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86))
+        return __popcnt(v);
+#else
+        return generic_popcount(x);
+#endif
+    }
+
+    static int ctz(unsigned int x) {
+#if defined(__GNUC__) || defined(__clang__)
+        return __builtin_ctz(x);
+#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86))
+        unsigned long result;
+        _BitScanForward(&result, v);
+        return result;
+#else
+        return generic_ctz(x);
+#endif
+    }
+};
+
+};
+
+#endif /* BITS_H */