From 625e870b4fb7ff4caf4d8a4614e9bda7c174b291 Mon Sep 17 00:00:00 2001
From: David Herrmann <dh.herrmann@gmail.com>
Date: Tue, 13 May 2014 19:47:58 +0200
Subject: [PATCH] shared: add ALIGN_POWER2 macro

Sounds easy, turns out to be horrible to implement: ALIGN_POWER2 returns
the next higher power of 2. clz(0) is undefined, same is true for
left-shift-overflows, yey, C rocks!
---
 src/shared/macro.h   | 13 +++++++++++++
 src/test/test-util.c | 31 +++++++++++++++++++++++++++++++
 2 files changed, 44 insertions(+)

diff --git a/src/shared/macro.h b/src/shared/macro.h
index d53b07fea..53bd578d7 100644
--- a/src/shared/macro.h
+++ b/src/shared/macro.h
@@ -100,6 +100,19 @@ static inline size_t ALIGN_TO(size_t l, size_t ali) {
 
 #define ALIGN_TO_PTR(p, ali) ((void*) ALIGN_TO((unsigned long) p, ali))
 
+/* align to next higher power-of-2 (except for: 0 => 0, overflow => 0) */
+static inline unsigned long ALIGN_POWER2(unsigned long u) {
+        /* clz(0) is undefined */
+        if (u == 1)
+                return 1;
+
+        /* left-shift overflow is undefined */
+        if (__builtin_clzl(u - 1UL) < 1)
+                return 0;
+
+        return 1UL << (sizeof(u) * 8 - __builtin_clzl(u - 1UL));
+}
+
 #define ELEMENTSOF(x) (sizeof(x)/sizeof((x)[0]))
 
 /*
diff --git a/src/test/test-util.c b/src/test/test-util.c
index 93929cd9f..caf8d2b12 100644
--- a/src/test/test-util.c
+++ b/src/test/test-util.c
@@ -37,6 +37,36 @@ static void test_streq_ptr(void) {
         assert_se(!streq_ptr("abc", "cdef"));
 }
 
+static void test_align_power2(void) {
+        unsigned long i, p2;
+
+        assert_se(ALIGN_POWER2(0) == 0);
+        assert_se(ALIGN_POWER2(1) == 1);
+        assert_se(ALIGN_POWER2(2) == 2);
+        assert_se(ALIGN_POWER2(3) == 4);
+        assert_se(ALIGN_POWER2(12) == 16);
+
+        assert_se(ALIGN_POWER2(ULONG_MAX) == 0);
+        assert_se(ALIGN_POWER2(ULONG_MAX - 1) == 0);
+        assert_se(ALIGN_POWER2(ULONG_MAX - 1024) == 0);
+        assert_se(ALIGN_POWER2(ULONG_MAX / 2) == ULONG_MAX / 2 + 1);
+        assert_se(ALIGN_POWER2(ULONG_MAX + 1) == 0);
+
+        for (i = 1; i < 131071; ++i) {
+                for (p2 = 1; p2 < i; p2 <<= 1)
+                        /* empty */ ;
+
+                assert_se(ALIGN_POWER2(i) == p2);
+        }
+
+        for (i = ULONG_MAX - 1024; i < ULONG_MAX; ++i) {
+                for (p2 = 1; p2 && p2 < i; p2 <<= 1)
+                        /* empty */ ;
+
+                assert_se(ALIGN_POWER2(i) == p2);
+        }
+}
+
 static void test_first_word(void) {
         assert_se(first_word("Hello", ""));
         assert_se(first_word("Hello", "Hello"));
@@ -680,6 +710,7 @@ int main(int argc, char *argv[]) {
         log_open();
 
         test_streq_ptr();
+        test_align_power2();
         test_first_word();
         test_close_many();
         test_parse_boolean();
-- 
2.30.2