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>

2 files changed, 124 insertions, 0 deletions

diff --git a/common/bits.cc b/common/bits.cc
new file mode 100644
index 00000000..1fe65544
--- /dev/null
+++ b/common/bits.cc
@@ -0,0 +1,51 @@
+/*
+ *  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.
+ *
+ */
+
+#include "bits.h"
+#include <limits>
+#include <stdexcept>
+
+namespace nextpnr {
+
+int Bits::generic_popcount(unsigned int v) {
+    unsigned int c; // c accumulates the total bits set in v
+    for (c = 0; v; c++) {
+        v &= v - 1; // clear the least significant bit set
+    }
+
+    return c;
+}
+
+int Bits::generic_ctz(unsigned int x) {
+    if(x == 0) {
+        throw std::runtime_error("Cannot call ctz with arg = 0");
+    }
+
+    for(size_t i = 0; i < std::numeric_limits<unsigned int>::digits; ++i) {
+        if((x & (1 << i)) != 0) {
+            return i;
+        }
+    }
+
+    // Unreachable!
+    throw std::runtime_error("Unreachable!");
+}
+
+};
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 */