Add integer and bit math utilities

4 files changed, 205 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
diff --git a/tests/int_math_test.c b/tests/int_math_test.c
new file mode 100644
index 00000000..188559eb
--- /dev/null
+++ b/tests/int_math_test.c
@@ -0,0 +1,64 @@
+/*
+  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.
+*/
+
+#undef NDEBUG
+
+#include "../src/int_math.h"
+
+#include <assert.h>
+
+static void
+test_clz32(void)
+{
+	for (unsigned i = 0; i < 32; ++i) {
+		assert(serd_clz32(1u << i) == 32u - i - 1u);
+	}
+}
+
+static void
+test_clz64(void)
+{
+	for (unsigned i = 0; i < 64; ++i) {
+		assert(serd_clz64(1ull << i) == 64u - i - 1u);
+	}
+}
+
+static void
+test_ilog2(void)
+{
+	for (unsigned i = 0; i < 64; ++i) {
+		assert(serd_ilog2(1ull << i) == i);
+	}
+}
+
+static void
+test_ilog10(void)
+{
+	uint64_t power = 1;
+	for (unsigned i = 0; i < 20; ++i, power *= 10) {
+		assert(serd_ilog10(power) == i);
+	}
+}
+
+int
+main(void)
+{
+	test_clz32();
+	test_clz64();
+	test_ilog2();
+	test_ilog10();
+	return 0;
+}
diff --git a/wscript b/wscript
index 9a81651a..933dc467 100644
--- a/wscript
+++ b/wscript
@@ -125,6 +125,15 @@ def configure(conf):
                                 defines     = ['_POSIX_C_SOURCE=200809L'],
                                 mandatory   = False)
 
+    conf.check_cc(msg         = 'Checking for __builtin_clz',
+                  define_name = 'HAVE_BUILTIN_CLZ',
+                  fragment    = 'int main(void) {return __builtin_clz(0);}',
+                  mandatory   = False)
+    conf.check_cc(msg         = 'Checking for __builtin_clzll',
+                  define_name = 'HAVE_BUILTIN_CLZLL',
+                  fragment    = 'int main(void) {return __builtin_clzll(0);}',
+                  mandatory   = False)
+
     if not Options.options.no_pcre:
         autowaf.check_pkg(conf, 'libpcre',
                           uselib_store='PCRE',
@@ -161,6 +170,7 @@ lib_source = ['src/base64.c',
               'src/cursor.c',
               'src/env.c',
               'src/inserter.c',
+              'src/int_math.c',
               'src/iter.c',
               'src/model.c',
               'src/n3.c',
@@ -247,6 +257,7 @@ def build(bld):
                      ('cursor_test', 'tests/cursor_test.c'),
                      ('env_test', 'tests/env_test.c'),
                      ('free_null_test', 'tests/free_null_test.c'),
+                     ('int_math_test', 'tests/int_math_test.c'),
                      ('model_test', 'tests/model_test.c'),
                      ('nodes_test', 'tests/nodes_test.c'),
                      ('overflow_test', 'tests/overflow_test.c'),
@@ -676,6 +687,7 @@ def test(tst):
         check(['./cursor_test'])
         check(['./env_test'])
         check(['./free_null_test'])
+        check(['./int_math_test'])
         check(['./model_test'])
         check(['./nodes_test'])
         check(['./overflow_test'])