Mercurial > libjeffpc
changeset 796:cf1cd2707dfb
int: add p2roundup to round an integer to the next multiple of power of 2
Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
author | Josef 'Jeff' Sipek <jeffpc@josefsipek.net> |
---|---|
date | Sat, 28 Mar 2020 10:39:35 -0400 |
parents | 952b4ab949eb |
children | 4c0939533a78 |
files | include/jeffpc/int.h tests/.hgignore tests/CMakeLists.txt tests/test_p2roundup.c |
diffstat | 4 files changed, 122 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/include/jeffpc/int.h Sat Mar 28 10:36:52 2020 -0400 +++ b/include/jeffpc/int.h Sat Mar 28 10:39:35 2020 -0400 @@ -117,6 +117,33 @@ return !(val & (val - 1)); } +/* round val to the next multiple of power of 2 */ +static inline uint64_t p2roundup(uint64_t val, uint64_t align) +{ + if (align <= 1) + return val; + + /* + * alignment must be a power of two - if it isn't, panic + * + * Note: We cannot include error.h since we don't want everyone that + * includes in types.h (and therefore int.h) to automatically pull + * in error.h. We work around it by making a local prototype and + * then calling it. This is still type safe, since many places + * include both error.h (and therefore get the real panic prototype) + * and this header. In those compilation units, the compiler makes + * sure that the two signatures match. No warnings/errors there, + * imply that the below prototype is 100% correct. + */ + if (!is_p2(align)) { + extern void panic(const char *, ...); + + panic("roundup - non-power of 2 align: %#"PRIx64, align); + } + + return (val + (align - 1)) & ~(align - 1); +} + /* * These prototypes exist to catch bugs in the code generating macros below. */
--- a/tests/.hgignore Sat Mar 28 10:36:52 2020 -0400 +++ b/tests/.hgignore Sat Mar 28 10:39:35 2020 -0400 @@ -37,6 +37,7 @@ test_mutex-unlock-unheld test_nvl test_nvl_pack +test_p2roundup test_padding test_qstring test_rwlock-destroy-memcpy
--- a/tests/CMakeLists.txt Sat Mar 28 10:36:52 2020 -0400 +++ b/tests/CMakeLists.txt Sat Mar 28 10:39:35 2020 -0400 @@ -66,6 +66,7 @@ build_test_bin_and_run(mutex-unlock-unheld) endif() build_test_bin_and_run(nvl) +build_test_bin_and_run(p2roundup) build_test_bin_and_run(padding) build_test_bin_and_run(rwlock-destroy-memcpy) build_test_bin_and_run(rwlock-destroy-null)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test_p2roundup.c Sat Mar 28 10:39:35 2020 -0400 @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2020 Josef 'Jeff' Sipek <jeffpc@josefsipek.net> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include <jeffpc/types.h> + +#include "test.c" + +#define CHECK(name, idx, _val, _align, _exp) \ + do { \ + const uint64_t v = (_val); \ + const uint64_t a = (_align); \ + const uint64_t exp = (_exp); \ + uint64_t got; \ + \ + fprintf(stderr, "%s: %2d: p2roundup(%#018"PRIx64", " \ + "%#018"PRIx64")...", (name), (idx), v, a); \ + \ + got = p2roundup(v, a); \ + if (got != exp) \ + fail("expected %#018"PRIx64", got %#018"PRIx64, \ + exp, got); \ + \ + fprintf(stderr, "ok.\n"); \ + } while (0) + +#define TEST(name, _in, out) \ + do { \ + const uint64_t val = (_in); \ + int shift; \ + \ + /* no alignment -> no change */ \ + CHECK((name), 0, val, 0ul, val); \ + CHECK((name), 1, val, 1ul, val); \ + \ + for (shift = 1; shift < 64; shift++) { \ + const uint64_t align = 1ull << shift; \ + CHECK((name), shift + 1, val, align, (out)); \ + } \ + } while (0) + +void test(void) +{ + /* aligning zero always yields zero */ + TEST("zero", 0ul, 0); + + /* aligning one always yields alignment */ + TEST("one", 1ul, align); + + /* aligning INT64_MAX yields INT64_MAX+1 */ + TEST("INT64_MAX", INT64_MAX, ((uint64_t) INT64_MAX) + 1); + + /* aligning UINT64_MAX yields zero because of overflow */ + TEST("UINT64_MAX", UINT64_MAX, 0); + + /* check against alternate implementations */ +#define TEST_BATCH(name) \ + do { \ + TEST(name " 0x111...", 0x1111111111111111, ALT_IMPL); \ + TEST(name " 0x555...", 0x5555555555555555, ALT_IMPL); \ + TEST(name " 0xaaa...", 0xaaaaaaaaaaaaaaaa, ALT_IMPL); \ + TEST(name " digits asc", 0x0123456789abcdef, ALT_IMPL); \ + TEST(name " digits desc", 0xfedcba9876543210, ALT_IMPL); \ + } while (0) + +#define ALT_IMPL (((val >> shift) + ((val << (64 - shift)) ? 1 : 0)) << shift) + TEST_BATCH("ALT1"); +#undef ALT_IMPL +#define ALT_IMPL (val + ((val % align) ? (align - (val % align)) : 0)) + TEST_BATCH("ALT2"); +#undef ALT_IMPL +#define ALT_IMPL (val + ((val & (align - 1)) ? (align - (val & (align - 1))) : 0)) + TEST_BATCH("ALT3"); +#undef ALT_IMPL +}