From 7510ed6f684041db643c051cb17b13abf663b3b2 Mon Sep 17 00:00:00 2001
From: wm4 <wm4@nowhere>
Date: Thu, 31 Oct 2019 13:16:58 +0100
Subject: common: add mp_log2()

To be used in the next commit.

According to compiler explorer, __builtin_clz is very widely available,
and it barely makes sense to provide a fallback. clang also eats this
(and identifies at least as GCC 4). Actually, there's doubt that a fast
log2 implementation is needed at all (I guess UTF-8 parsing needs it,
but something UTF-8-specific would probably make it faster than using
log2). So the fallback is just something naive.
---
 common/common.c | 18 ++++++++++++++++++
 common/common.h |  2 ++
 2 files changed, 20 insertions(+)

diff --git a/common/common.c b/common/common.c
index d0b2382b78..967ab961c0 100644
--- a/common/common.c
+++ b/common/common.c
@@ -318,3 +318,21 @@ char **mp_dup_str_array(void *tctx, char **s)
         MP_TARRAY_APPEND(tctx, r, num_r, NULL);
     return r;
 }
+
+// Return rounded down integer log 2 of v, i.e. position of highest set bit.
+//  mp_log2(0)  == 0
+//  mp_log2(1)  == 0
+//  mp_log2(31) == 4
+//  mp_log2(32) == 5
+unsigned int mp_log2(uint32_t v)
+{
+#if defined(__GNUC__) && __GNUC__ >= 4
+    return v ? 31 - __builtin_clz(v) : 0;
+#else
+    for (int x = 31; x >= 0; x--) {
+        if (v & (((uint32_t)1) << x))
+            return x;
+    }
+    return 0;
+#endif
+}
diff --git a/common/common.h b/common/common.h
index 16e1ec4cfd..5e6950c931 100644
--- a/common/common.h
+++ b/common/common.h
@@ -88,6 +88,8 @@ bool mp_rect_intersection(struct mp_rect *rc, const struct mp_rect *rc2);
 bool mp_rect_contains(struct mp_rect *rc, int x, int y);
 bool mp_rect_equals(struct mp_rect *rc1, struct mp_rect *rc2);
 
+unsigned int mp_log2(uint32_t v);
+
 int mp_snprintf_cat(char *str, size_t size, const char *format, ...)
     PRINTF_ATTRIBUTE(3, 4);
 
-- 
cgit v1.2.3