Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #59259 > unrolled thread

Test for overflow

Back to article view | Back to comp.lang.c

Contents

  Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-30 13:17 +0200
    Re: Test for overflow Lőrinczy Zsigmond <zsiga@nospam.for.me> - 2015-03-30 13:34 +0200
    Re: Test for overflow Richard Damon <Richard@Damon-Family.org> - 2015-03-30 07:42 -0400
      Re: Test for overflow asetofsymbols@gmail.com - 2015-03-30 04:47 -0700
        Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-30 13:57 +0200
          Re: Test for overflow Richard Damon <Richard@Damon-Family.org> - 2015-03-30 08:24 -0400
    Re: Test for overflow Richard Heathfield <rjh@cpax.org.uk> - 2015-03-30 13:03 +0100
    Re: Test for overflow Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-30 06:54 -0700
    Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 13:20 -0400
      Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 13:32 -0400
      Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 19:43 -0400
        Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-31 07:11 +0200
          Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-31 13:41 -0400
            Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-31 19:48 +0200
              Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-31 13:58 -0400
    Re: Test for overflow Thomas Jahns <jahns@idontlikespam.dkrz.de> - 2015-04-01 10:12 +0200
      Re: Test for overflow Richard Heathfield <rjh@cpax.org.uk> - 2015-04-01 09:43 +0100
        Re: Test for overflow Thomas Jahns <jahns@idontlikespam.dkrz.de> - 2015-04-01 10:59 +0200
          Re: Test for overflow Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-01 04:07 -0700
            Re: Test for overflow raltbos@xs4all.nl (Richard Bos) - 2015-04-01 13:52 +0000

#59259 — Test for overflow

Hi the math experts!

When parsing a digit sequence I test for overflow not by calculating the 
maximum number of digits allowed but just with the test

tvalue = value * base;

if (tvalue < value) {
    // overflow detected
}

I am assuming then that

if value * base > 2^64 then
    value * base mod 2^64 < value

for base >= 2 and base <= 36.

Is this correct?

I do not have the proof of it. Maybe one of the math people can help me out?

[toc] | [next] | [standalone]

#59260

I cannot say it is doubtless. A less intelligent test would be:


tvalue = value * base;

if (tvalue/base != value) {
    // overflow detected
}

[toc] | [prev] | [next] | [standalone]

#59261

On 3/30/15 7:17 AM, jacob navia wrote:
> Hi the math experts!
>
> When parsing a digit sequence I test for overflow not by calculating the
> maximum number of digits allowed but just with the test
>
> tvalue = value * base;
>
> if (tvalue < value) {
>     // overflow detected
> }
>
> I am assuming then that
>
> if value * base > 2^64 then
>     value * base mod 2^64 < value
>
> for base >= 2 and base <= 36.
>
> Is this correct?
>
> I do not have the proof of it. Maybe one of the math people can help me
> out?

By the standard, you shouldn't test for overflow by letting it happen 
and then looking for a strange result, but by testing before doing the 
operation. If you wait till after the overflow, you have already invoked 
undefined behavior. (If value or base is unsigned then you don't get 
"overflow" just a wrap around, your relationship does not necessarily 
hold for unsigneds, for example with 16 bits for simplicity, 0x1234 * 
0x10 = 0x2340)

On some machines, if value * base exceed INT_MAX, the result will be 
INT_MAX, on some others it could abort your program.

You can test if the overflow will occur by seeing if value > 
INT_MAX/base before doing the arithmetic (it is a bit easier for you 
case than in general as base has a limited domain of values)

[toc] | [prev] | [next] | [standalone]

#59263

On overflow I use "jc" for unsigned

[toc] | [prev] | [next] | [standalone]

#59264

Le 30/03/2015 13:47, asetofsymbols@gmail.com a écrit :
> On overflow I use "jc" for unsigned
>
The lcc-win compiler offers _overflow() with the contents of the 
overflow flag. I did not use it since I wanted to stay compatible with C99.

[toc] | [prev] | [next] | [standalone]

#59266

On 3/30/15 7:57 AM, jacob navia wrote:
> Le 30/03/2015 13:47, asetofsymbols@gmail.com a écrit :
>> On overflow I use "jc" for unsigned
>>
> The lcc-win compiler offers _overflow() with the contents of the
> overflow flag. I did not use it since I wanted to stay compatible with C99.
>

Which may be set for addition and subtraction, but generally not for 
multiplication. Most machines have an n * n => 2n bits multiply, so 
overflow isn't a problem in hardware, just in C which defines multiply 
as n * n => n bits

[toc] | [prev] | [next] | [standalone]

#59265

On 30/03/15 12:17, jacob navia wrote:
> Hi the math experts!
>
> When parsing a digit sequence I test for overflow not by calculating the
> maximum number of digits allowed but just with the test
>
> tvalue = value * base;
>
> if (tvalue < value) {
>      // overflow detected
> }
>
> I am assuming then that
>
> if value * base > 2^64 then
>      value * base mod 2^64 < value
>
> for base >= 2 and base <= 36.
>
> Is this correct?

Consider simpler cases. For example, if we have a four-bit type, then 
for overflow we are concerned by the following cases (we start off by 
ignoring 0 * anything and 1 * anything and 2 * stuff that won't overflow):

2 * 8 = 16 = 0 mod 16 - fine
3 * 8 = 24 = 8 mod 16 - this would fail your test, but it's right on the 
edge
4 * 8 = 32 = 0 mod 16 - fine
5 * 8 = 40 = 8 mod 16 - fail, and we have a pattern for 8s

2 * 9 = 18 = 2 mod 16 - fine
3 * 9 = 27 = 11 mod 16 - fail, and not really a borderline fail either

and the theory seems to be running into problems, even with four-bit 
quantities.

Okay, I grant that 64 bits != 4 bits. But if it doesn't work for 4, I 
see no particular reason to be optimistic that it'll work for 64.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#59271

jacob navia <jacob@jacob.remcomp.fr> writes:

> Hi the math experts!
>
> When parsing a digit sequence I test for overflow not by
> calculating the maximum number of digits allowed but just
> with the test
>
> tvalue = value * base;
>
> if (tvalue < value) {
>    // overflow detected
> }
>
> I am assuming then that
>
> if value * base > 2^64 then
>    value * base mod 2^64 < value
>
> for base >= 2 and base <= 36.
>
> Is this correct?

No.

You can test for out-of-range as follows:

If the maximum allowed value is 'ceiling', and assuming the
current value is in 'n', and the next digit value is in 'd',
then before the loop calculate

    unsigned long long q = ceiling / base, r = ceiling % base;
    // q is for "quotient", r is for "remainder"

and in the body of the loop test

    if(  n >= q  &&  (n > q  ||  d > r)  ){
        // augmenting 'n' with digit 'd' would exceed 'ceiling'
        ...
    }

Done this way only this one test need be done, and which in
most cases will do only a single comparison.

[toc] | [prev] | [next] | [standalone]

#59292

On 03/30/2015 07:17 AM, jacob navia wrote:
> Hi the math experts!
> 
> When parsing a digit sequence I test for overflow not by calculating the 
> maximum number of digits allowed but just with the test
> 
> tvalue = value * base;
> 
> if (tvalue < value) {
>     // overflow detected
> }
> 
> I am assuming then that
> 
> if value * base > 2^64 then
>     value * base mod 2^64 < value
> 
> for base >= 2 and base <= 36.
> 
> Is this correct?

I hope you're also assuming that value*base is computed using an
unsigned type - if not:

"If an exceptional condition occurs during the evaluation of an
expression (that is, if the result is not mathematically defined or not
in the range of representable values for its type), the behavior is
undefined." (6.5p5)
This clause isn't there just for the pleasure of pedants like myself -
it's present because there have been (and probably still are)
implementations where the behavior of such code would probably surprise you.

> I do not have the proof of it. Maybe one of the math people can help me out?


Even for unsigned types, tvalue < value is not guaranteed for base > 2.

Consider a plot of y=x*base as a C expression in unsigned long long,
(which therefore obeys modular arithmetic) as a function of x. It
consists of parallel lines, each with a slope equal to the base. Each of
those lines starts near y==0, and ends near y==ULLONG_MAX, and can be
labelled with the value of x/base, which ranged from 0 to base-1. The
total number of such linesfor 0 <= x && x <= ULLONG_MAX equals 'base'.

Compare that plot with a plot of y=x. The line for x%base==0 starts at
x=0, y=0, but then stays entire above y=x. The line for x%base ==
(base-1) stays entirely below y=x unless ULLONG_MAX%base == 0, in which
case they meet at x=ULLONG_MAX, y=ULONG_MAX. So for base==2, your test
works perfectly.
However, for every line where 0 < x%base && x%base < base - 1 crosses
y=x. Therefore, your test will misclassify some of the values of tvalue
in that range. It will also mishandle ULLONG_MAX*base if ULLONG_MAX%base==0.

[toc] | [prev] | [next] | [standalone]

#59294

On 03/30/2015 01:20 PM, James Kuyper wrote:
...
> y=x. Therefore, your test will misclassify some of the values of tvalue
> in that range. It will also mishandle ULLONG_MAX*base if ULLONG_MAX%base==0.

For ULLONG_MAX == 0xFFFFFFFFFFFFFFFF, the minimum permitted value, that
applies to base==3, base==5, base==15, and base==17.

[toc] | [prev] | [next] | [standalone]

#59316

On 03/30/2015 01:20 PM, James Kuyper wrote:
...
> Consider a plot of y=x*base as a C expression in unsigned long long,
> (which therefore obeys modular arithmetic) as a function of x. It
> consists of parallel lines, each with a slope equal to the base. Each of
> those lines starts near y==0, and ends near y==ULLONG_MAX, and can be
> labelled with the value of x/base, which ranged from 0 to base-1. The
> total number of such linesfor 0 <= x && x <= ULLONG_MAX equals 'base'.
> 
> Compare that plot with a plot of y=x. The line for x%base==0 starts at
> x=0, y=0, but then stays entire above y=x. The line for x%base ==
> (base-1) stays entirely below y=x unless ULLONG_MAX%base == 0, in which
> case they meet at x=ULLONG_MAX, y=ULONG_MAX. So for base==2, your test
> works perfectly.
> However, for every line where 0 < x%base && x%base < base - 1 crosses
> y=x. Therefore, your test will misclassify some of the values of tvalue
> in that range. It will also mishandle ULLONG_MAX*base if ULLONG_MAX%base==0.

All occurrences of x%base above should have been
x*base/(ULLONG_MAX+1), where the left and right operands of '/' are
evaluated mathematically without overflow, but where the division
results in an integer value rounded towards zero, per C rules. My
description should make slightly more sense that way :-}. I can't quite
figure out the train of thought that led me to use the simpler
expression, but it had something to do with the fact that the range of
values is the same for both expressions.

The correct expression has precisely the behavior I intended - I just
gave the wrong expression.

[toc] | [prev] | [next] | [standalone]

#59325

I hope this doesn't go into your kill file... Anyway
Now I will do

maxvalNotOverflow = maxval/base;

and then, at each step:

     if (value > maxvalNotOverflow) {
         digit = OVERFLOW_FLAG;
         break;
     }
     else value = value * base;

Now, I DO believe that my test is OK when testing for an ADDITION overflow.

     if (value+digit < value) {
         digit = OVERFLOW_FLAG;
         break;
     }
     else value += digit;

OK?

Note: ALL values are unsigned.

[toc] | [prev] | [next] | [standalone]

#59348

On 03/31/2015 01:11 AM, jacob navia wrote:
> I hope this doesn't go into your kill file... Anyway

So far, you haven't used you new e-mail address to say anything that
made me want to to add it to my kill file.

> Now I will do
> 
> maxvalNotOverflow = maxval/base;
> 
> and then, at each step:
> 
>      if (value > maxvalNotOverflow) {
>          digit = OVERFLOW_FLAG;
>          break;
>      }
>      else value = value * base;
> 
> Now, I DO believe that my test is OK when testing for an ADDITION overflow.
> 
>      if (value+digit < value) {
>          digit = OVERFLOW_FLAG;
>          break;
>      }
>      else value += digit;
> 
> OK?

I think so, so long as 'digit' is no wider than 'value' - given the
context, if they were different sizes, I'd expect 'digit' to be smaller,
so that shouldn't be a problem. Of course, my judgement is more reliable
when I say there's a problem than when I say there's no problem.

> Note: ALL values are unsigned.

[toc] | [prev] | [next] | [standalone]

#59349

Le 31/03/2015 19:41, James Kuyper a écrit :
> I think so, so long as 'digit' is no wider than 'value'

"Value" is an unsigned long long. To be able to overflow by adding a 
number smaller than 37, "value" *must* be bigger than 2^64 - 37.

If an overflow occurs, at most the last 6 bits could be set, what is 
surely smaller than a number that is bigger thzn 2^64 - 37!!

[toc] | [prev] | [next] | [standalone]

#59351

On 03/31/2015 01:48 PM, jacob navia wrote:
> Le 31/03/2015 19:41, James Kuyper a écrit :
>> I think so, so long as 'digit' is no wider than 'value'
> 
> "Value" is an unsigned long long. To be able to overflow by adding a 
> number smaller than 37, "value" *must* be bigger than 2^64 - 37.
> 
> If an overflow occurs, at most the last 6 bits could be set, what is 
> surely smaller than a number that is bigger thzn 2^64 - 37!!

The issue isn't the value of 'digit', but it's type. In the extremely
unlikely event that it was wider than unsigned long long (say,
int128_t), then 'value' would be converted to that wider type in both
places in the expression "value + digit < value". As a result, that
expression would detect overflow based upon the maximum value of the
wider type, producing false negatives if what you're really looking for
is overflow of the narrower type.
That's all based upon the possibility that 'digit' was wider than
'value', which I explicitly acknowledged was extremely implausible in
context. The purpose for which it's used could be served by unsigned
char, though unsigned int or unsigned long long would probably generate
faster code on many platforms. I just mentioned that possibility only
for the sake of completeness, since I had not seen any actual declarations.

[toc] | [prev] | [next] | [standalone]

#59380

On 03/30/15 13:17, jacob navia wrote:
> I do not have the proof of it. Maybe one of the math people can help me out?

Testing for integer multiplication overflow can be surprisingly involved in the 
general case:

http://www.fefe.de/intof.html

Regards, Thomas

[toc] | [prev] | [next] | [standalone]

#59382

On 01/04/15 09:12, Thomas Jahns wrote:
> On 03/30/15 13:17, jacob navia wrote:
>> I do not have the proof of it. Maybe one of the math people can help me out?
>
> Testing for integer multiplication overflow can be surprisingly involved in the
> general case:
>
> http://www.fefe.de/intof.html

At least at first glance, that page looks like someone has actually 
taken the trouble to think about it. Do you know who wrote the page?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#59383

On 04/01/15 10:43, Richard Heathfield wrote:
> At least at first glance, that page looks like someone has actually taken the
> trouble to think about it. Do you know who wrote the page?

Fefe is a prominent member of Chaos Computer Club, just look at the about me 
part of http://www.fefe.de/ or his Wikipedia entry[1]

His perspective is mostly a security-centric one, where integer overflow 
directly leads to buffer overflow.

Regards, Thomas

[1] https://en.wikipedia.org/wiki/Felix_von_Leitner

[toc] | [prev] | [next] | [standalone]

#59389

On Wednesday, April 1, 2015 at 9:59:13 AM UTC+1, Thomas Jahns wrote:
> On 04/01/15 10:43, Richard Heathfield wrote:
> > At least at first glance, that page looks like someone has actually taken the
> > trouble to think about it. Do you know who wrote the page?
> 
> Fefe is a prominent member of Chaos Computer Club, just look at the about me 
> part of http://www.fefe.de/ or his Wikipedia entry[1]
> 
> His perspective is mostly a security-centric one, where integer overflow 
> directly leads to buffer overflow.
> 
The solution to the security concerns is pretty simple.
Firstly, you need to run the program in an environment where integer overflow leads
to program termination with an error message.
Secondly, you need to eliminate unsigned types from calculations on integers that
are used as index or size values. Unfortunately there are one or two special cases
where unsigned values are extremely useful, they're rare, but they tend to be in
processor intensive code like huge integer arithmetical operations or integer
frequency transforms.

[toc] | [prev] | [next] | [standalone]

#59398

Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:

> The solution to the security concerns is pretty simple.
> Firstly, you need to run the program in an environment where integer overflow leads
> to program termination with an error message.
> Secondly, you need to eliminate unsigned types from calculations on integers that
> are used as index or size values. Unfortunately there are one or two special cases
> where unsigned values are extremely useful, they're rare, but they tend to be in
> processor intensive code like huge integer arithmetical operations or integer
> frequency transforms.

You forgot third: all types need to be 64-bit large, including size_t.

Richard

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web