From 0776012d0942537b1ddfef13cd37f8bfb125f501 Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Tue, 1 Apr 2025 00:39:24 +0200
Subject: Add bit library
---
asl/base/bit.hpp | 174 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 174 insertions(+)
create mode 100644 asl/base/bit.hpp
(limited to 'asl/base/bit.hpp')
diff --git a/asl/base/bit.hpp b/asl/base/bit.hpp
new file mode 100644
index 0000000..f2e3f61
--- /dev/null
+++ b/asl/base/bit.hpp
@@ -0,0 +1,174 @@
+// Copyright 2025 Steven Le Rouzic
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+#pragma once
+
+#include "asl/base/integers.hpp"
+#include "asl/base/meta.hpp"
+
+namespace asl
+{
+
+constexpr bool has_single_bit(is_unsigned_integer auto x)
+{
+ return x != 0 && ((x - 1) & x) == 0;
+}
+
+// @Todo Move this to numeric library
+template<is_integer T>
+constexpr bool is_pow2(T x)
+{
+ using unsigned_type = select_t<is_unsigned_integer<T>, T, as_unsigned_integer<T>>;
+ return x > 0 && has_single_bit(static_cast<unsigned_type>(x));
+}
+
+constexpr int popcount(uint8_t v)
+{
+ v = v - ((v >> 1) & 0x55);
+ v = (v & 0x33) + ((v >> 2) & 0x33);
+ return (v + (v >> 4)) & 0x0F;
+}
+
+constexpr int popcount(uint16_t v)
+{
+ v = v - ((v >> 1) & 0x5555);
+ v = (v & 0x3333) + ((v >> 2) & 0x3333);
+ return static_cast<uint16_t>((v + (v >> 4) & 0x0F0F) * uint16_t{0x0101}) >> 8;
+}
+
+constexpr int popcount(uint32_t v)
+{
+ v = v - ((v >> 1) & 0x5555'5555);
+ v = (v & 0x3333'3333) + ((v >> 2) & 0x3333'3333);
+ return static_cast<int>(((v + (v >> 4) & 0x0F0F'0F0F) * 0x0101'0101) >> 24);
+}
+
+constexpr int popcount(uint64_t v)
+{
+ v = v - ((v >> 1) & 0x5555'5555'5555'5555);
+ v = (v & 0x3333'3333'3333'3333) + ((v >> 2) & 0x3333'3333'3333'3333);
+ return static_cast<int>(((v + (v >> 4) & 0x0F0F'0F0F'0F0F'0F0F) * 0x0101'0101'0101'0101) >> 56);
+}
+
+constexpr uint8_t propagate_right_one(uint8_t v)
+{
+ v = v | (v >> 1);
+ v = v | (v >> 2);
+ v = v | (v >> 4);
+ return v;
+}
+
+constexpr uint16_t propagate_right_one(uint16_t v)
+{
+ v = v | (v >> 1);
+ v = v | (v >> 2);
+ v = v | (v >> 4);
+ v = v | (v >> 8);
+ return v;
+}
+
+constexpr uint32_t propagate_right_one(uint32_t v)
+{
+ v = v | (v >> 1);
+ v = v | (v >> 2);
+ v = v | (v >> 4);
+ v = v | (v >> 8);
+ v = v | (v >> 16);
+ return v;
+}
+
+constexpr uint64_t propagate_right_one(uint64_t v)
+{
+ v = v | (v >> 1);
+ v = v | (v >> 2);
+ v = v | (v >> 4);
+ v = v | (v >> 8);
+ v = v | (v >> 16);
+ v = v | (v >> 32);
+ return v;
+}
+
+constexpr int countr_zero(is_unsigned_integer auto v)
+{
+ v = ~v & (v - 1);
+ return popcount(v);
+}
+
+constexpr int countr_one(is_unsigned_integer auto v)
+{
+ v = v & (~v - 1);
+ return popcount(v);
+}
+
+constexpr int countl_zero(is_unsigned_integer auto v)
+{
+ v = ~propagate_right_one(v);
+ return popcount(v);
+}
+
+constexpr int countl_one(is_unsigned_integer auto v)
+{
+ v = ~v;
+ v = ~propagate_right_one(v);
+ return popcount(v);
+}
+
+template<is_unsigned_integer T>
+constexpr T rotr(T v, int s);
+
+template<is_unsigned_integer T>
+constexpr T rotl(T v, int s) // NOLINT(*-no-recursion)
+{
+ static constexpr int N = sizeof(decltype(v)) * 8;
+ s = s % N;
+ return (s >= 0) ? (v << s) | (v >> (N - s)) : rotr(v, -s);
+}
+
+template<is_unsigned_integer T>
+constexpr T rotr(T v, int s) // NOLINT(*-no-recursion)
+{
+ static constexpr int N = sizeof(decltype(v)) * 8;
+ s = s % N;
+ return (s >= 0) ? (v >> s) | (v << (N - s)) : rotl(v, -s);
+}
+
+constexpr uint16_t byteswap(uint16_t v)
+{
+ return static_cast<uint16_t>((v << 8U) | (v >> 8U));
+}
+
+constexpr uint32_t byteswap(uint32_t v)
+{
+ return rotr(v & 0x00ff'00ff, 8) | rotl(v & 0xff00'ff00, 8);
+}
+
+constexpr uint64_t byteswap(uint64_t v)
+{
+ return (uint64_t{byteswap(static_cast<uint32_t>(v))} << 32)
+ | uint64_t{byteswap(static_cast<uint32_t>(v >> 32))};
+}
+
+constexpr auto bit_ceil(is_unsigned_integer auto v)
+{
+ v -= 1;
+ v = propagate_right_one(v);
+ v += 1;
+ return v;
+}
+
+constexpr auto bit_floor(is_unsigned_integer auto v)
+{
+ v = propagate_right_one(v);
+ v = v - (v >> 1);
+ return v;
+}
+
+constexpr int bit_width(is_unsigned_integer auto v)
+{
+ static constexpr int N = sizeof(decltype(v)) * 8;
+ return N - countl_zero(v);
+}
+
+} // namespace asl
+
--
cgit