aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/int_math.c70
-rw-r--r--src/int_math.h59
-rw-r--r--tests/int_math_test.c64
-rw-r--r--wscript12
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'])