value rollup detection at runtime
omkarenator
below, at runtime:
int main() {
unsigned short int i = 0;
unsigned int j;
for (j = 0; j < 65537; j++)
i++;
return 0;
}
i is getting rolled up due to wrong indexing. Is there any idiom we
could add to catch this and through an error (or handle it by other
means) at runtime?
Here for simplicity I am using j and adding 1 to i at a time, but in
practical situations i can be increased arbitrarily by any value which
might be getting in from some place else (that means you don't just
check j and say, yeah its rolling i up). Say for first iteration by 1
then by 23k and so on.
more precisely :
while (1) {
i += random_value;
}
One solution I could think of, is maintain another signed int k (4
bytes) which will contain max value of i (65535) and before changing
i, I could subtract random_value from k and see whether its less that
zero/negative.
Is there any better way/idioms/general solution ?
Thanks
--
comp.lang.c.moderated - moderation address: cl...@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Dag-Erling Smørgrav
> int main() {
>
> unsigned short int i = 0;
> unsigned int j;
>
> for (j = 0; j < 65537; j++)
> i++;
>
> return 0;
> }
>
> i is getting rolled up due to wrong indexing.
It's called overflow, or rolling over, not "getting rolled up", and it
has nothing to do with indexing. Indexing is what you do to select an
element from an array.
> Is there any idiom we could add to catch this and through an error (or
> handle it by other means) at runtime?
Setting aside the obvious solution (using a wider variable to hold the
sum) -
If a is a variable of an unsigned integer type T which has a maximum
value T_MAX, and b is a scalar variable or constant such that b < T_MAX,
you can detect overflow in advance:
if (a + (T)b < a)
printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
a += b;
Without the cast, you'll run into all sorts of trouble due to automatic
type promotion.
If b >= T_MAX, you may or may not be able to detect overflow. For
instance, on a two's-complement machine with 16-bit short ints where
USHRT_MAX = 65535:
unsigned short a = 0;
unsigned int b = 65536;
if (a + (unsigned short)b < a)
printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
a += b;
printf("%uh\n", a);
The overflow is not detected, because (0 + 65536) mod 65536 = 0.
DES
--
Dag-Erling Smørgrav - d...@des.no
Barry Schwarz
The preferred method is to design your code so the situation does not
occur but that may not be possible or worth the effort.
If ULONG_MAX > UINT_MAX, you could change your variables to unsigned
long and check against UINT_MAX.
Since unsigned arithmetic never overflows but just wraps back to 0
silently, another approach is:
Store the sum in a temporary variable.
Check the temporary against both addends.
If the sum is less than either addend, a wrap occurred.
If not, assign the sum to the "real" variable and continue.
--
Remove del for email
Jyoti Sharma
wrote:
> Whats the most simple/elegant way to detect value roll up bugs as show
> below, at runtime:
>
> int main() {
>
> unsigned short int i = 0;
> unsigned int j;
>
> for (j = 0; j < 65537; j++)
> i++;
>
> return 0;
> }
>
> i is getting rolled up due to wrong indexing. Is there any idiom we
> could add to catch this and through an error (or handle it by other
> means) at runtime?
>
> Here for simplicity I am using j and adding 1 to i at a time, but in
> practical situations i can be increased arbitrarily by any value which
> might be getting in from some place else (that means you don't just
> check j and say, yeah its rolling i up). Say for first iteration by 1
> then by 23k and so on.
>
> more precisely :
>
> while (1) {
> i += random_value;
> }
>
> One solution I could think of, is maintain another signed int k (4
> bytes) which will contain max value of i (65535) and before changing
> i, I could subtract random_value from k and see whether its less that
> zero/negative.
>
> Is there any better way/idioms/general solution ?
The way you have suggested is the simplest and surest way. You can get the
max value from limits.h instead of typing the number in your code like
65535.
Regards,
Jyoti
Hans-Bernhard Bröker
> Whats the most simple/elegant way to detect value roll up bugs as show
> below, at runtime:
Compare the result of the addition with the operands. If the sum is
smaller than the inputs, it rolled over.
But don't do that with signed integers if you want your code to be portable.
Francis Glassborow
> omkarenator <omkar...@gmail.com> writes:
>> int main() {
>>
>> unsigned short int i = 0;
>> unsigned int j;
>>
>> for (j = 0; j < 65537; j++)
>> i++;
>>
>> return 0;
>> }
>>
>> i is getting rolled up due to wrong indexing.
>
> It's called overflow, or rolling over, not "getting rolled up", and it
> has nothing to do with indexing. Indexing is what you do to select an
> element from an array.
>
>> Is there any idiom we could add to catch this and through an error (or
>> handle it by other means) at runtime?
>
> Setting aside the obvious solution (using a wider variable to hold the
> sum) -
>
> If a is a variable of an unsigned integer type T which has a maximum
> value T_MAX, and b is a scalar variable or constant such that b < T_MAX,
> you can detect overflow in advance:
>
> if (a + (T)b < a)
> printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
> a += b;
>
Keith Thompson
> Dag-Erling Smørgrav wrote:
[...]
>> Setting aside the obvious solution (using a wider variable to hold the
>> sum) -
>>
>> If a is a variable of an unsigned integer type T which has a maximum
>> value T_MAX, and b is a scalar variable or constant such that b < T_MAX,
>> you can detect overflow in advance:
>>
>> if (a + (T)b < a)
>> printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
>> a += b;
>>
> And for multiplication?
Pain.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Dag-Erling Smørgrav
> Dag-Erling Smørgrav <d...@des.no> writes:
> > If a is a variable of an unsigned integer type T which has a maximum
> > value T_MAX, and b is a scalar variable or constant such that b < T_MAX,
> > you can detect overflow in advance:
> >
> > if (a + (T)b < a)
> > printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
> > a += b;
> And for multiplication?
No silver bullet there... you'll have to use a larger type, most likely
uintmax_t:
T multiply(T a, T b)
{
if ((uintmax_t)a * (uintmax_t)b > T_MAX)
printf("overflow: %ju * %ju\n", (uintmax_t)a, (uintmax_t)b);
return (T)(a * b);
}
You can use a temporary variable, but the compiler will probably DTRT in
either case:
T multiply(T a, T b)
{
uintmax_t p = (uintmax_t)a * (uintmax_t)b;
if (p > T_MAX)
printf("overflow: %ju * %ju\n", (uintmax_t)a, (uintmax_t)b);
return (T)p;
}
If there is no larger type available, you can fall back on what you
learned in calculus class:
a * b = e ^ (log(a) + log(b))
or
a * b = 2 ^ (log2(a) + log2(b))
The integer part of the base-two logarithm of a number is the index of
the highest set bit in its binary representation.
As an example, let's see if the 364^2 can fit in 16 bits:
The binary representation of 364 is 1 0100 0001; the highest set bit is
bit 8, which means that 8 <= log2(364) < 9 (the actual value is 8.5078).
Thus 16 <= log2(364) + log2(364) < 18, so 364^2 requires 17 or 18 bits
to store; so even though 364 fits in a uint16_t, 364 * 364 doesn't.
DES
--
Dag-Erling Smørgrav - d...@des.no
Francis Glassborow
> Francis Glassborow <francis.g...@btinternet.com> writes:
>> Dag-Erling Smørgrav <d...@des.no> writes:
>>> If a is a variable of an unsigned integer type T which has a maximum
>>> value T_MAX, and b is a scalar variable or constant such that b < T_MAX,
>>> you can detect overflow in advance:
>>>
>>> if (a + (T)b < a)
>>> printf("overflow: %ju + %ju\n", (uintmax_t)a, (uintmax_t)b);
>>> a += b;
>> And for multiplication?
>
> No silver bullet there... you'll have to use a larger type, most likely
> uintmax_t:
Thanks, you just made my point, pre-detection of overflow for signed
integer multiplication is non trivial yet the hardware can tell you when
it happens but according to the C Standard that is too late because you
are already in UB territory.
>
> T multiply(T a, T b)
> {
> if ((uintmax_t)a * (uintmax_t)b > T_MAX)
> printf("overflow: %ju * %ju\n", (uintmax_t)a, (uintmax_t)b);
> return (T)(a * b);
> }
>
> You can use a temporary variable, but the compiler will probably DTRT in
> either case:
>
> T multiply(T a, T b)
> {
> uintmax_t p = (uintmax_t)a * (uintmax_t)b;
> if (p > T_MAX)
No, that is far from enough for the general case.
> printf("overflow: %ju * %ju\n", (uintmax_t)a, (uintmax_t)b);
> return (T)p;
> }
>
> If there is no larger type available, you can fall back on what you
> learned in calculus class:
>
> a * b = e ^ (log(a) + log(b))
> or
> a * b = 2 ^ (log2(a) + log2(b))
>
> The integer part of the base-two logarithm of a number is the index of
> the highest set bit in its binary representation.
>
> As an example, let's see if the 364^2 can fit in 16 bits:
>
> The binary representation of 364 is 1 0100 0001; the highest set bit is
> bit 8, which means that 8 <= log2(364) < 9 (the actual value is 8.5078).
> Thus 16 <= log2(364) + log2(364) < 18, so 364^2 requires 17 or 18 bits
> to store; so even though 364 fits in a uint16_t, 364 * 364 doesn't.
Yes but you will get false positives or miss some that should be trapped.
>
> DES
--
Note that robinton.demon.co.uk addresses are no longer valid.
Dag-Erling Smørgrav
> Dag-Erling Smørgrav <d...@des.no> writes:
> > If there is no larger type available, you can fall back on what you
> > learned in calculus class:
> > The binary representation of 364 is 1 0100 0001; the highest set bit is
> > bit 8, which means that 8 <= log2(364) < 9 (the actual value is 8.5078).
> > Thus 16 <= log2(364) + log2(364) < 18, so 364^2 requires 17 or 18 bits
> > to store; so even though 364 fits in a uint16_t, 364 * 364 doesn't.
> Yes but you will get false positives or miss some that should be trapped.
There are three cases: a) unambiguously non-overflowing, b)
unambiguously overflowing, c) ambiguous. Whether you get false
positives or negatives depends on how you handle the third case. One
possibility is divide-and-conquer: if (x * y) is ambiguous, perform (x *
(y >> 2)) and see if it's equal to or less than half of T_MAX; if it is,
double the result, and iff y is odd, check that there is room left over
for the last x.
DES
--
Dag-Erling Smørgrav - d...@des.no
Francis Glassborow
> Francis Glassborow <francis.g...@btinternet.com> writes:
>> Dag-Erling Smørgrav <d...@des.no> writes:
>>> If there is no larger type available, you can fall back on what you
>>> learned in calculus class:
>>> [...]
>>> The binary representation of 364 is 1 0100 0001; the highest set bit is
>>> bit 8, which means that 8 <= log2(364) < 9 (the actual value is 8.5078).
>>> Thus 16 <= log2(364) + log2(364) < 18, so 364^2 requires 17 or 18 bits
>>> to store; so even though 364 fits in a uint16_t, 364 * 364 doesn't.
>> Yes but you will get false positives or miss some that should be trapped.
>
> There are three cases: a) unambiguously non-overflowing, b)
> unambiguously overflowing, c) ambiguous. Whether you get false
> positives or negatives depends on how you handle the third case. One
> possibility is divide-and-conquer: if (x * y) is ambiguous, perform (x *
> (y >> 2)) and see if it's equal to or less than half of T_MAX; if it is,
> double the result, and iff y is odd, check that there is room left over
> for the last x.
>
> DES
On modern hardware an integer multiplication is very fast (usually
taking the same time as an integer add or subtract). However, to ensure
that I do not incur UB I have to go through elaborate pre-tests
beforehand. Would it not be much better if I could post test? Remember
that most hardware these days uses two's complement and in such cases
the normal result for overflow is obtained by wrapping.
An incorrect result of a computation that can be tested seems to me to
be greatly preferable to overflow resulting in UB.
Some of us try to teach the dangers of UB in code, yet C (and C++) make
all integer arithmetic that includes values that are not known at
compile time liable to UB.
It is hardly surprising that many programmers dismiss UB as unimportant
because whatever happens will be OK.
There is a world of difference between overflowing in an integer
computation and writing to an uninitialised pointer. On most hardware
the former just results in an incorrect value, but the latter can (and
in my experience) do damage outside the program. I once managed to
'randomly' reprogram a graphics card by writing to an invalid pointer.
Making integer overflow have implementation defined behaviour is, IMO,
greatly preferable. Being ably to test and reset a (sticky) overflow
flag would also assist.
Dag-Erling Smørgrav
> On modern hardware an integer multiplication is very fast (usually
> taking the same time as an integer add or subtract). However, to
> ensure that I do not incur UB I have to go through elaborate pre-tests
> beforehand. Would it not be much better if I could post test?
I never said it wouldn't - and comp.std.c is --> thataway.
DES
--
Dag-Erling Smørgrav - d...@des.no
Hans-Bernhard Bröker
> On modern hardware an integer multiplication is very fast (usually
> taking the same time as an integer add or subtract).
A misleading argument at best. You know quite well that C doesn't limit
itself to "modern hardware" --- no matter what that even means.
> However, to ensure that I do not incur UB I have to go through
> elaborate pre-tests beforehand. Would it not be much better if I
> could post test?
Only if post-tests were significantly faster than pre-tests. I rather
much doubt that.
> Remember that most hardware these days uses two's complement and in
> such cases the normal result for overflow is obtained by wrapping.
The C standard doesn't have the luxury of limiting itself to "most
hardware", be that modern or not.
> An incorrect result of a computation that can be tested seems to me to
> be greatly preferable to overflow resulting in UB.
Wishing doesn't make it so.
How much money are you willing to bet that there is _no_ hardware
platform for which an efficient C compiler would be highly desirable,
which actually does go haywire if a multiplication overflows, or at
least does something else than wrap around twos-complement? Saturating
arithmetic in DSPs anyone?
Francis Glassborow
> Francis Glassborow wrote:
> Wishing doesn't make it so.
>
> How much money are you willing to bet that there is _no_ hardware
> platform for which an efficient C compiler would be highly desirable,
> which actually does go haywire if a multiplication overflows, or at
> least does something else than wrap around twos-complement? Saturating
> arithmetic in DSPs anyone?
Sorry I am having difficulty parsing that. I think you mean that the
actual behaviour is either wrap around or saturating. The mak the
behaviour implementation defined. My big concern is the devaluing of UB
that happens because it is not possible to right simmply integer
arithmetic without risking UB.
Hans-Bernhard Bröker
> Hans-Bernhard Bröker wrote:
>> Francis Glassborow wrote:
>
>> Wishing doesn't make it so.
>>
>> How much money are you willing to bet that there is _no_ hardware
>> platform for which an efficient C compiler would be highly desirable,
>> which actually does go haywire if a multiplication overflows, or at
>> least does something else than wrap around twos-complement?
>> Saturating arithmetic in DSPs anyone?
> Sorry I am having difficulty parsing that. I think you mean that the
> actual behaviour is either wrap around or saturating.
No, that's not what I meant. I mentioned saturating as one real-world
example of "doing something else than wrap-around of twos-complement
arithmetic". I mentioned "going haywire" as a paraphrase of UB.
> The mak the behaviour implementation defined.
Sorry, but because at least one letter is missing in there, I'm having
trouble parsing that.
> My big concern is the devaluing of UB that happens because it is not
> possible to right simmply integer arithmetic without risking UB.
^^^^^ ^^
Either your keyboard needs spring cleaning, or you an innoculation
against Myspeling Vyrus? ;-)
Francis Glassborow
> Francis Glassborow wrote:
>> Hans-Bernhard Bröker wrote:
>>> Francis Glassborow wrote:
>>
>>> Wishing doesn't make it so.
>>>
>>> How much money are you willing to bet that there is _no_ hardware
>>> platform for which an efficient C compiler would be highly desirable,
>>> which actually does go haywire if a multiplication overflows, or at
>>> least does something else than wrap around twos-complement?
>>> Saturating arithmetic in DSPs anyone?
>
>> Sorry I am having difficulty parsing that. I think you mean that the
>> actual behaviour is either wrap around or saturating.
>
> No, that's not what I meant. I mentioned saturating as one real-world
> example of "doing something else than wrap-around of twos-complement
> arithmetic". I mentioned "going haywire" as a paraphrase of UB.
>
> > The mak the behaviour implementation defined.
>
> Sorry, but because at least one letter is missing in there, I'm having
> trouble parsing that.
finger lingers too long on a key and suppress the action from the next
key pressed)
>
>> My big concern is the devaluing of UB that happens because it is not
>> possible to right simmply integer arithmetic without risking UB.
> ^^^^^ ^^
> Either your keyboard needs spring cleaning, or you an innoculation
> against Myspeling Vyrus? ;-)
Sorry, I have no idea why my brain chooses the wrong spelling from
'write'. 'right' and 'rite' I know better. Perhaps I do not multitask
very well particularly late at night.
I once (when I was the Editor of C Vu) wrote 'time in loo' which a
number of readers found hilarious because it sort of fitted the context
even if it was the wrong loo.
Trouble with spelling checkers is that they miss correctly spelt wrong
words. One I find interesting is interchanging 'unite' and 'untie' They
are anagrams of each other with the difference being a common typing
error (reversing two letters that are on different hands) and being
close to being antonyms.
I wonder if there are any other such pairs in English. Sorry, I digress
from the subject of this newsgroup.
I could live with a feature test that called out the behaviour on
overflow. There are places such as some uses of timers where you may
want a signed integer type and wrap round is fine but saturation isn't
and doing something weird certainly isn't. At the moment I cannot easily
restrict the use of such code to systems which provide wrap round (and
note that at present an implementation is not required to tell you what
it does on integer overflow, and IME they don't.