Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Arithmetic overflow checking

Reply
Thread Tools

Arithmetic overflow checking

 
 
tm
Guest
Posts: n/a
 
      07-10-2011
On 8 Jul., 05:04, Patricia Shanahan <(E-Mail Removed)> wrote:
> On 7/7/2011 5:51 PM, Peter Duniho wrote:
> ...
>
> > I would not worry about the "simple" or "efficient" criteria. IMHO, if
> > one is deciding to apply overflow checking to every computation, one has
> > already abandoned the hope of efficiency.

>
> Not necessarily. I assumed a couple of decades ago that array index
> checking would be impossibly inefficient, but it seems to work fine in
> Java.


And in other languages, like Pascal, Ada and Seed7, as well.

> I suspect that having integer range types would be a major help.
> When I'm working out whether an int can overflow, I often think in terms
> of the ranges of inputs to calculations. A compiler would be able to
> tell that adding a digit to a digit always fits in the range [0,18].


I think there are two things:

1. range checks (like value fits in [0,18]).
2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
computation overflows.

In the 1. case a compiler could generate code that does
the computation and checks the range afterwards.
In the 2. case a computation could result in wrong data,
because the overflow was silently ignored. In this case
either some checks must be done before the computation or
the overfow condition is recognized during or after the
computation. In an ideal world the hardware would do this.

A CPU could (in theory) easily recognize the overflow
and generate an interrupt. This way normal computations
(without overflow) would have no extra cost. AFAIK
commonly used CPUs do not have this possibility. They
have some FLAG, which is set when an overflow occurred.
But there is no possibility to cause an interrupt, when
the overflow FLAG is set. So code, which checks for
overflow, must check this flag after every computation.
Needless to say: Normal computations (without overflow)
are slowed down by this checks.

Because of this slow down most compilers and virtual
machines (AFAIK inluding the JVM) have no overflow
checking.

In other words: A missing hardware feature:

Trigger interupt when overflow flag is set.

Causes compilers and JVMs to omit overflow checks.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 
Reply With Quote
 
 
 
 
tm
Guest
Posts: n/a
 
      07-10-2011
On 10 Jul., 11:47, China Blue Dolls <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed)>,
>
> *tm <(E-Mail Removed)> wrote:
> > On 8 Jul., 05:04, Patricia Shanahan <(E-Mail Removed)> wrote:
> > > On 7/7/2011 5:51 PM, Peter Duniho wrote:
> > > ...

>
> > > > I would not worry about the "simple" or "efficient" criteria. IMHO,if
> > > > one is deciding to apply overflow checking to every computation, one has
> > > > already abandoned the hope of efficiency.

>
> > > Not necessarily. I assumed a couple of decades ago that array index
> > > checking would be impossibly inefficient, but it seems to work fine in
> > > Java.

>
> > * 2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
> > * * *computation overflows.

>
> C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
> So the concept of overflow does not apply.
>
> > * Trigger interupt when overflow flag is set.

>
> Not all CPUs detect integer arithmetic overflow. Not all CPUs signal integer
> arithmetic problems.


And popular CPUs, which do detect integer overflow, do not
trigger an interupt. This makes zero overhead overflow
detection impossible.

So software suffers because hardware / CPU designers want
to save a transistor...


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-10-2011
On 7/10/2011 5:47 AM, China Blue Dolls wrote:
>
> In C the array size is not part of the type or value, so there is nothing to
> check.


No; the size (element count) is part of an array's type. Your
compiler will confirm this for you by issuing a diagnostic for

char matrix[5][7]; /* five char[7] arrays */
char (*nine)[9]; /* pointer to char[9] */
nine = matrix; /* point it at the first char[7] */

> C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
> So the concept of overflow does not apply.


This is true only for `unsigned' integer arithmetic. Signed
integer arithmetic is in fact vulnerable to overflow.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      07-10-2011
On Jul 10, 4:28*pm, Eric Sosman <(E-Mail Removed)> wrote:
>
> * * *This is true only for `unsigned' integer arithmetic. *Signed
> integer arithmetic is in fact vulnerable to overflow.
>

All arithmetic is vulnerable to overflow. The question is whether the
system reports and error or gives wrong results. Sometimes wrong
results are better than errors, for instance in video games, but only
rarely.
--
Learn all about MPI
Tutorial on my website: http://www.malcolmmclean.site11.com/www
 
Reply With Quote
 
David Lamb
Guest
Posts: n/a
 
      07-10-2011
On 08/07/2011 12:30 AM, Eric Sosman wrote:
> On 7/7/2011 8:51 PM, Peter Duniho wrote:
>> [...]
>> I would not worry about the "simple" or "efficient" criteria. IMHO, if
>> one is deciding to apply overflow checking to every computation, one has
>> already abandoned the hope of efficiency.

>
> I've used machines that raised overflow traps "for free,"

....
> (The machines I speak of were from forty-odd years ago


When microprocessors started to arrive on the scene, a lot of old-timey
hardware folks said they'd forgotten 30+ years of hardware design. When
operating systems for computers based on said processors came out, a lot
of old-timey software folks said they'd forgotten 30+ years of operating
system design. We seem to still be suffering the consequences.
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      07-10-2011
On 07/10/2011 05:47 AM, China Blue Dolls wrote:
> In article<(E-Mail Removed)>,
>> 2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
>> computation overflows.

>
> C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
> So the concept of overflow does not apply.


That is only true for unsigned integers; signed integer overflow is
undefined.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      07-10-2011
China Blue Dolls <(E-Mail Removed)> writes:
> In article <(E-Mail Removed)>, pete <(E-Mail Removed)> wrote:
> > China Blue Dolls wrote:
> >
> > > In C the array size is not part of the type or value,
> > > so there is nothing to check.

> >
> > In C,
> > the size of an array is part of the type of the array.


One might even say that array types are characterized by their
element type and by the number of elements in the array.

> extern char s[];


That's not an array, that's a promise that somewhere else there's
an array.

Phil
--
"At least you know where you are with Microsoft."
"True. I just wish I'd brought a paddle." -- Matthew Vernon
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      07-10-2011
On Sun, 10 Jul 2011 10:53:09 -0400, David Lamb wrote:

> On 08/07/2011 12:30 AM, Eric Sosman wrote:
>> On 7/7/2011 8:51 PM, Peter Duniho wrote:
>>> [...]
>>> I would not worry about the "simple" or "efficient" criteria. IMHO, if
>>> one is deciding to apply overflow checking to every computation, one
>>> has already abandoned the hope of efficiency.

>>
>> I've used machines that raised overflow traps "for free,"

> ...
>> (The machines I speak of were from forty-odd years ago

>
> When microprocessors started to arrive on the scene, a lot of old-timey
> hardware folks said they'd forgotten 30+ years of hardware design. When
> operating systems for computers based on said processors came out, a lot
> of old-timey software folks said they'd forgotten 30+ years of operating
> system design. We seem to still be suffering the consequences.


That happened not once, but twice.

The first great leap backward was the minicomputer era, when the likes of
the PDP-8 arrived with a single user, single tasking OS reminiscent of
early computers, except they generally had teletypes instead of banks of
switches and flashing lights. By then the better mainframes were multi-
user, multitasking beasts.

Then the first microcomputers arrived in the mid/late '70s. By this time
the better minis had multi-tasking operating systems, but micros had re-
implemented the earliest mini OSes - CP/M was near as dammit a copy of
the old PDP-8 OS (RSTS?) from the late 60s - and the earliest micros even
had switches and flashing lights (KIM-1, IMSAI 8080). By 1980 the minis
were running UNIX but the latest and greatest micros had - drumroll - MS-
DOS!


--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      07-10-2011
On Sun, 10 Jul 2011 11:29:39 -0700, Patricia Shanahan wrote:

> On 7/10/2011 11:07 AM, Martin Gregorie wrote:
>> On Sun, 10 Jul 2011 10:53:09 -0400, David Lamb wrote:
>>
>>> On 08/07/2011 12:30 AM, Eric Sosman wrote:
>>>> On 7/7/2011 8:51 PM, Peter Duniho wrote:
>>>>> [...]
>>>>> I would not worry about the "simple" or "efficient" criteria. IMHO,
>>>>> if one is deciding to apply overflow checking to every computation,
>>>>> one has already abandoned the hope of efficiency.
>>>>
>>>> I've used machines that raised overflow traps "for free,"
>>> ...
>>>> (The machines I speak of were from forty-odd years ago
>>>
>>> When microprocessors started to arrive on the scene, a lot of
>>> old-timey hardware folks said they'd forgotten 30+ years of hardware
>>> design. When operating systems for computers based on said processors
>>> came out, a lot of old-timey software folks said they'd forgotten 30+
>>> years of operating system design. We seem to still be suffering the
>>> consequences.

>>
>> That happened not once, but twice.
>>
>> The first great leap backward was the minicomputer era, when the likes
>> of the PDP-8 arrived with a single user, single tasking OS reminiscent
>> of early computers, except they generally had teletypes instead of
>> banks of switches and flashing lights. By then the better mainframes
>> were multi- user, multitasking beasts.
>>
>> Then the first microcomputers arrived in the mid/late '70s. By this
>> time the better minis had multi-tasking operating systems, but micros
>> had re- implemented the earliest mini OSes - CP/M was near as dammit a
>> copy of the old PDP-8 OS (RSTS?) from the late 60s - and the earliest
>> micros even had switches and flashing lights (KIM-1, IMSAI 8080). By
>> 1980 the minis were running UNIX but the latest and greatest micros had
>> - drumroll - MS- DOS!
>>
>>
>>

> Only twice? Aren't you forgetting "smart" phones. One of the great
> advances in Android is (Drum roll!) multitasking!!!
>

They don't count since, unlike minis and micros, their builders didn't
retreat to the techno-stone age, ignore progress made to date, and build
primitive OS by rubbing (metaphorical) sticks together.

AFAIK all smartphones started an a more advanced level because they
inherited better operating systems. IIRC these all originated on
electronic memo pads such as Psion, HP and Palm Pilot made, and were all
a lot more advanced than the likes of RSTS, CP/M, Flex09, etc. Leastwise,
I don't think you can consider Symbian and whatever MS was calling the
iPAQ OS at that stage any more primitive than the contemporary versions
of MacOS, OS/2 or even Windows, though admittedly they were rather behind
UNIX and its distant relations such as OS-9/68K.


--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      07-10-2011
Malcolm McLean <(E-Mail Removed)> writes:
> On Jul 10, 4:28*pm, Eric Sosman <(E-Mail Removed)> wrote:
>> * * *This is true only for `unsigned' integer arithmetic. *Signed
>> integer arithmetic is in fact vulnerable to overflow.
>>

> All arithmetic is vulnerable to overflow. The question is whether the
> system reports and error or gives wrong results. Sometimes wrong
> results are better than errors, for instance in video games, but only
> rarely.


All arithmetic that's intended to model (a subset of) the real
numbers with the usual mathematical operations is vulnerable to
overflow. (Even arbitrary-precision packages can run out of memory.)

But C unsigned arithmetic, for example *doesn't* model normal real
arithmetic; it models arithmetic modulo 2**N and is not vulnerable
to overflow. (Wraparound is not overflow; it yields the correct
wrapped result.)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <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"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Arithmetic overflow checking tm C Programming 88 09-08-2011 08:24 PM
Arithmetic overflow error converting numeric to data type numeric. darrel ASP .Net 4 07-19-2007 09:57 PM
detecting overflow in arithmetic left shifter dlamoris VHDL 0 10-26-2006 06:53 AM
arithmetic overflow with enum Fraser Ross C++ 5 10-10-2005 09:48 AM
Usual Arithmetic Conversions-arithmetic expressions joshc C Programming 5 03-31-2005 02:23 AM



Advertisments