From 4a56f2baabd6c4ef3f485e9a5f7f3d4168a2d60b Mon Sep 17 00:00:00 2001
From: Alejandro Colomar <alx@kernel.org>
Date: Fri, 30 Dec 2022 23:00:14 +0100
Subject: [PATCH] Add bit manipulation functions

These functions implement bit manipulation APIs, which will be added to
C23, so that in the far future, we will be able to replace our functions
by the standard ones, just by adding the stdc_ prefix, and including
<stdbit.h>.

However, we need to avoid UB for an input of 0, so slightly deviate from
C23, and use a different name (with _wrap) for distunguishing our API
from the standard one.

Cc: Joseph Myers <joseph@codesourcery.com>
Cc: Yann Droneaud <ydroneaud@opteya.com>
Signed-off-by: Alejandro Colomar <alx@kernel.org>
---
 lib/bit.h           | 41 +++++++++++++++++++++++++++++++++++++++++
 libmisc/Makefile.am |  1 +
 libmisc/bit.c       | 18 ++++++++++++++++++
 3 files changed, 60 insertions(+)
 create mode 100644 lib/bit.h
 create mode 100644 libmisc/bit.c

diff --git a/lib/bit.h b/lib/bit.h
new file mode 100644
index 000000000..246925571
--- /dev/null
+++ b/lib/bit.h
@@ -0,0 +1,41 @@
+/*
+ * SPDX-FileCopyrightText:  Alejandro Colomar <alx@kernel.org>
+ *
+ * SPDX-License-Identifier:  BSD-3-Clause
+ */
+
+
+#ifndef SHADOW_INCLUDE_LIB_BIT_H_
+#define SHADOW_INCLUDE_LIB_BIT_H_
+
+
+#include <config.h>
+
+#ident "$Id$"
+
+#include <limits.h>
+
+
+inline unsigned long bit_ceil_wrapul(unsigned long x);
+inline int leading_zerosul(unsigned long x);
+
+
+/* stdc_bit_ceilul(3), but wrap instead of having Undefined Behavior */
+inline unsigned long
+bit_ceil_wrapul(unsigned long x)
+{
+	if (x == 0)
+		return 0;
+
+	return 1 + (ULONG_MAX >> leading_zerosul(x));
+}
+
+/* stdc_leading_zerosul(3) */
+inline int
+leading_zerosul(unsigned long x)
+{
+	return (x == 0) ? ULONG_WIDTH : __builtin_clz(x);
+}
+
+
+#endif  // include guard
diff --git a/libmisc/Makefile.am b/libmisc/Makefile.am
index b4ca708d7..ab363f549 100644
--- a/libmisc/Makefile.am
+++ b/libmisc/Makefile.am
@@ -12,6 +12,7 @@ libmisc_la_SOURCES = \
 	agetpass.c \
 	audit_help.c \
 	basename.c \
+	bit.c \
 	chkname.c \
 	chkname.h \
 	chowndir.c \
diff --git a/libmisc/bit.c b/libmisc/bit.c
new file mode 100644
index 000000000..39efd5685
--- /dev/null
+++ b/libmisc/bit.c
@@ -0,0 +1,18 @@
+/*
+ * SPDX-FileCopyrightText:  Alejandro Colomar <alx@kernel.org>
+ *
+ * SPDX-License-Identifier:  BSD-3-Clause
+ */
+
+
+#include <config.h>
+
+#ident "$Id$"
+
+#include "bit.h"
+
+#include <limits.h>
+
+
+extern inline unsigned long bit_ceil_wrapul(unsigned long x);
+extern inline int leading_zerosul(unsigned long x);
-- 
2.47.2