diff options
| -rw-r--r-- | src/int_math.c | 70 | ||||
| -rw-r--r-- | src/int_math.h | 59 | ||||
| -rw-r--r-- | tests/int_math_test.c | 64 | ||||
| -rw-r--r-- | wscript | 12 |
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; +} @@ -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']) |