bug in roundup(3) from <sys/param.h>
Hi!
I was trying to understand what roundup() is (defined in <sys/param,h>).
It seems to be kind of:
SYNOPSIS
#include <sys/param.h>
roundup(x, step);DESCRIPTION
This macro rounds x to the nearest multiple of step that is not less than x.
I found that it doesn't work for negative numbers; but that's expected, and it could be documented as such. However, it doesn't work nicely with unsigned integers either: for values close to zero, where wrap around happens, the result is also bogus. See my experiments below.
$ sed -n 92,98p /usr/include/x86_64-linux-gnu/sys/param.h
#ifdef __GNUC__
# define roundup(x, y) (__builtin_constant_p (y) && powerof2 (y) \
? (((x) + (y) - 1) & ~((y) - 1)) \
: ((((x) + ((y) - 1)) / (y)) * (y)))
#else
# define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
#endif$ cat roundup.c #include <stdint.h> #include <stdio.h> #include <sys/param.h>
int
main(void)
{
/* signed */
{
int32_t n, m;
m = 3;
n = 10;
puts("signed:");
for (int32_t x = -n; x < 0; x++)
printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));
puts("");
for (int32_t x = 0; x < n; x++)
printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));
puts("");
for (int32_t x = INT32_MIN; x < INT_MIN + n; x++)
printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));
puts("");
for (int32_t x = INT32_MAX; x > INT32_MAX - n; x--)
printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));
}
/* unsigned */
{
uint32_t n, m;
m = 3;
n = 10;
puts("\nunsigned:");
for (uint32_t x = 1; x < n; x++)
printf("roundup(%u, %u) == %u\n", -x, m, roundup(-x, m));
puts("");
for (uint32_t x = 0; x < n; x++)
printf("roundup(%u, %u) == %u\n", x, m, roundup(x, m));
}
}$ cc -Wall -Wextra -Werror roundup.c $ ./a.out signed: roundup(-10, 3) == -6 roundup(-9, 3) == -6 roundup(-8, 3) == -6 roundup(-7, 3) == -3 roundup(-6, 3) == -3 roundup(-5, 3) == -3 roundup(-4, 3) == 0 roundup(-3, 3) == 0 roundup(-2, 3) == 0 roundup(-1, 3) == 0 /* These values are nonsense, but OK, let's ignore the negative */
roundup(0, 3) == 0roundup(1, 3) == 3roundup(2, 3) == 3roundup(3, 3) == 3roundup(4, 3) == 6roundup(5, 3) == 6roundup(6, 3) == 6roundup(7, 3) == 9roundup(8, 3) == 9roundup(9, 3) == 9
/* These make sense */
roundup(-2147483648, 3) == -2147483646roundup(-2147483647, 3) == -2147483643roundup(-2147483646, 3) == -2147483643roundup(-2147483645, 3) == -2147483643roundup(-2147483644, 3) == -2147483640roundup(-2147483643, 3) == -2147483640roundup(-2147483642, 3) == -2147483640roundup(-2147483641, 3) == -2147483637roundup(-2147483640, 3) == -2147483637roundup(-2147483639, 3) == -2147483637
/* Nonsense; ignore the negative */
roundup(2147483647, 3) == -2147483646 // UB; ignore roundup(2147483646, 3) == -2147483646 // UB; ignore roundup(2147483645, 3) == 2147483646 roundup(2147483644, 3) == 2147483646 roundup(2147483643, 3) == 2147483643 roundup(2147483642, 3) == 2147483643 roundup(2147483641, 3) == 2147483643 roundup(2147483640, 3) == 2147483640 roundup(2147483639, 3) == 2147483640 roundup(2147483638, 3) == 2147483640
/* These make sense */
unsigned:roundup(4294967295, 3) == 0 // Wrong; should be: 4294967295 roundup(4294967294, 3) == 0 // Wrong; should be: 4294967295 roundup(4294967293, 3) == 4294967295 roundup(4294967292, 3) == 4294967292 roundup(4294967291, 3) == 4294967292 roundup(4294967290, 3) == 4294967292 roundup(4294967289, 3) == 4294967289 roundup(4294967288, 3) == 4294967289 roundup(4294967287, 3) == 4294967289
roundup(0, 3) == 0roundup(1, 3) == 3roundup(2, 3) == 3roundup(3, 3) == 3roundup(4, 3) == 6roundup(5, 3) == 6roundup(6, 3) == 6roundup(7, 3) == 9roundup(8, 3) == 9roundup(9, 3) == 9
Do you think this is something to be fixed without important performance penalties, or should we just document the bug and live with it?
Cheers,
Alex
Signature · 1 line
<http://www.alejandro-colomar.es/>
Quoted 19 lines · Alejandro Colomar
Hi!
I was trying to understand what
roundup()is (defined in <sys/param,h>).It seems to be kind of:
SYNOPSIS
#include <sys/param.h>
roundup(x, step);DESCRIPTION
This macro rounds x to the nearest multiple of step that is not less than x.I found that it doesn't work for negative numbers; but that's expected, and it could be documented as such. However, it doesn't work nicely with unsigned integers either: for values close to zero, where wrap around happens, the result is also bogus. See my experiments below.
Quoted 9 lines
$ sed -n 92,98p /usr/include/x86_64-linux-gnu/sys/param.h #ifdef __GNUC__ # define roundup(x, y) (__builtin_constant_p (y) && powerof2 (y) \ ? (((x) + (y) - 1) & ~((y) - 1)) \ : ((((x) + ((y) - 1)) / (y)) * (y))) #else # define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y)) #endif
I came up with this implementation, which increases complexity quite a lot (compared to the one liner), but makes the macro work correctly for all input (or that's what my tests showed). It only has UB for signed input when the output would overflow <TYPE>_MAX (but of course, there's no way to avoid that).
Apart from working will all input, signed or unsigned, until the end of the range, it also has no problems about double evaluation.
If using GCC extensions is a problem, this could be rewritten a bit less safely and more standardese.
#define alx_widthof(t) (sizeof(t) * CHAR_BIT)
#define alx_is_signed(x) (((typeof(x)) -1) < 0)
#define alx_stype_max(t) (((((t) 1 << (alx_widthof(t) - 2)) - 1) << 1) + 1)
#define alx_roundup(x, step) \
({ \
__auto_type x_ = (x); \
__auto_type step_ = (step); \
\
if (alx_is_signed(x_)) { \
if (x_ < 0) { \
x_ = x_ / step_ * step_; \
} else if (x_ - 1 > alx_stype_max(typeof(x_)) - step_) { \
x_ = ((x_ - 1) / step_ + 1) * step_; \
} else { \
x_ = ((x_ - 1 + step_) / step_) * step_; \
} \
} else { \
if (x_ + step_ < step_) { \
x_ = ((x_ - 1) / step_ + 1) * step_; \
} else { \
x_ = ((x_ - 1 + step_) / step_) * step_; \
} \
} \
\
x_; \
})Signature · 1 line
<http://www.alejandro-colomar.es/>
Quoted 4 lines · Alejandro Colomar via Libc-alpha
Hi!
Do you think this is something to be fixed without important performance penalties, or should we just document the bug and live with it?
That's the problem with ill-defined interfaces, each implementation might eventually differs. It seems that BSD, AIX, and Solaris follows glibc implementation by wrapping around (Solaris also provides it through sysmacros.h instead of param.h). The exception is macOS that saturates the value.
I really won't bother with this interface, since potentially changing it might generate more potentially breakage than improvements.