From e189666a2d96d1faeb483324561f340ecbea3a73 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 10:53:03 -0800 Subject: 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> --- common/bits.cc | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 common/bits.cc (limited to 'common/bits.cc') 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 +#include + +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::digits; ++i) { + if((x & (1 << i)) != 0) { + return i; + } + } + + // Unreachable! + throw std::runtime_error("Unreachable!"); +} + +}; -- cgit v1.2.3