Add integer and bit math utilities

2 files changed, 129 insertions, 0 deletions

diff --git a/src/int_math.c b/src/int_math.c
new file mode 100644
index 00000000..b20b14a6
--- /dev/null
+++ b/src/int_math.c
@@ -0,0 +1,70 @@
+/*
+  Copyright 2019-2020 David Robillard <http://drobilla.net>
+
+  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.
+
+  THIS 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 "int_math.h"
+
+#include <assert.h>
+
+unsigned
+serd_clz32(const uint32_t i)
+{
+	assert(i != 0);
+
+#ifdef HAVE_BUILTIN_CLZ
+	return (unsigned)__builtin_clz(i);
+#else
+	unsigned n    = 32u;
+	uint32_t bits = i;
+	for (unsigned s = 16; s > 0; s >>= 1) {
+		const uint32_t left = bits >> s;
+		if (left) {
+			n -= s;
+			bits = left;
+		}
+	}
+	return n - bits;
+#endif
+}
+
+unsigned
+serd_clz64(const uint64_t i)
+{
+	assert(i != 0);
+
+#ifdef HAVE_BUILTIN_CLZLL
+	return (unsigned)__builtin_clzll(i);
+#else
+	return i & 0xFFFFFFFF00000000 ? serd_clz32(i >> 32)
+	                              : 32 + serd_clz32(i & 0xFFFFFFFF);
+#endif
+}
+
+uint64_t
+serd_ilog2(const uint64_t i)
+{
+	assert(i != 0);
+	return (64 - serd_clz64(i | 1)) - 1;
+}
+
+uint64_t
+serd_ilog10(const uint64_t i)
+{
+	// See https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+	const uint64_t log2 = serd_ilog2(i);
+	const uint64_t t    = (log2 + 1) * 1233 >> 12;
+
+	return t - (i < POW10[t]) + (i == 0);
+}
diff --git a/src/int_math.h b/src/int_math.h
new file mode 100644
index 00000000..34ceba64
--- /dev/null
+++ b/src/int_math.h
@@ -0,0 +1,59 @@
+/*
+  Copyright 2019-2020 David Robillard <http://drobilla.net>
+
+  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.
+
+  THIS 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.
+*/
+
+#ifndef SERD_INTMATH_H
+#define SERD_INTMATH_H
+
+#include <stdint.h>
+
+static const uint64_t POW10[] = {1ull,
+                                 10ull,
+                                 100ull,
+                                 1000ull,
+                                 10000ull,
+                                 100000ull,
+                                 1000000ull,
+                                 10000000ull,
+                                 100000000ull,
+                                 1000000000ull,
+                                 10000000000ull,
+                                 100000000000ull,
+                                 1000000000000ull,
+                                 10000000000000ull,
+                                 100000000000000ull,
+                                 1000000000000000ull,
+                                 10000000000000000ull,
+                                 100000000000000000ull,
+                                 1000000000000000000ull,
+                                 10000000000000000000ull};
+
+/// Return the number of leading zeros in `i`
+unsigned
+serd_clz32(uint32_t i);
+
+/// Return the number of leading zeros in `i`
+unsigned
+serd_clz64(uint64_t i);
+
+/// Return the log base 2 of `i`
+uint64_t
+serd_ilog2(uint64_t i);
+
+/// Return the log base 10 of `i`
+uint64_t
+serd_ilog10(uint64_t i);
+
+#endif // SERD_INTMATH_H