From 180a60bc879ab0554297bc08a7a0b9274b119b55 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Mon, 29 Dec 2014 17:51:36 +0100 Subject: [PATCH] macro: add DIV_ROUND_UP() This macro calculates A / B but rounds up instead of down. We explicitly do *NOT* use: (A + B - 1) / A as it suffers from an integer overflow, even though the passed values are properly tested against overflow. Our test-cases show this behavior. Instead, we use: A / B + !!(A % B) Note that on "Real CPUs" this does *NOT* result in two divisions. Instead, instructions like idivl@x86 provide both, the quotient and the remainder. Therefore, both algorithms should perform equally well (I didn't verify this, though). --- src/shared/macro.h | 11 +++++++++++ src/test/test-util.c | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+) diff --git a/src/shared/macro.h b/src/shared/macro.h index 548294e47..6a5742824 100644 --- a/src/shared/macro.h +++ b/src/shared/macro.h @@ -197,6 +197,17 @@ static inline unsigned long ALIGN_POWER2(unsigned long u) { UNIQ_T(X,xq); \ }) +/* [(x + y - 1) / y] suffers from an integer overflow, even though the + * computation should be possible in the given type. Therefore, we use + * [x / y + !!(x % y)]. Note that on "Real CPUs" a division returns both the + * quotient and the remainder, so both should be equally fast. */ +#define DIV_ROUND_UP(_x, _y) \ + __extension__ ({ \ + const typeof(_x) __x = (_x); \ + const typeof(_y) __y = (_y); \ + (__x / __y + !!(__x % __y)); \ + }) + #define assert_se(expr) \ do { \ if (_unlikely_(!(expr))) \ diff --git a/src/test/test-util.c b/src/test/test-util.c index 93f11eb6e..3f1b5487f 100644 --- a/src/test/test-util.c +++ b/src/test/test-util.c @@ -145,6 +145,39 @@ static void test_alloca(void) { assert_se(!memcmp(t, zero, 997)); } +static void test_div_round_up(void) { + int div; + + /* basic tests */ + assert_se(DIV_ROUND_UP(0, 8) == 0); + assert_se(DIV_ROUND_UP(1, 8) == 1); + assert_se(DIV_ROUND_UP(8, 8) == 1); + assert_se(DIV_ROUND_UP(12, 8) == 2); + assert_se(DIV_ROUND_UP(16, 8) == 2); + + /* test multiple evaluation */ + div = 0; + assert_se(DIV_ROUND_UP(div++, 8) == 0 && div == 1); + assert_se(DIV_ROUND_UP(++div, 8) == 1 && div == 2); + assert_se(DIV_ROUND_UP(8, div++) == 4 && div == 3); + assert_se(DIV_ROUND_UP(8, ++div) == 2 && div == 4); + + /* overflow test with exact division */ + assert_se(sizeof(0U) == 4); + assert_se(0xfffffffaU % 10U == 0U); + assert_se(0xfffffffaU / 10U == 429496729U); + assert_se(DIV_ROUND_UP(0xfffffffaU, 10U) == 429496729U); + assert_se((0xfffffffaU + 10U - 1U) / 10U == 0U); + assert_se(0xfffffffaU / 10U + !!(0xfffffffaU % 10U) == 429496729U); + + /* overflow test with rounded division */ + assert_se(0xfffffffdU % 10U == 3U); + assert_se(0xfffffffdU / 10U == 429496729U); + assert_se(DIV_ROUND_UP(0xfffffffdU, 10U) == 429496730U); + assert_se((0xfffffffdU + 10U - 1U) / 10U == 0U); + assert_se(0xfffffffdU / 10U + !!(0xfffffffdU % 10U) == 429496730U); +} + static void test_first_word(void) { assert_se(first_word("Hello", "")); assert_se(first_word("Hello", "Hello")); @@ -1357,6 +1390,7 @@ int main(int argc, char *argv[]) { test_max(); test_container_of(); test_alloca(); + test_div_round_up(); test_first_word(); test_close_many(); test_parse_boolean(); -- 2.30.2