[TUHS] C history question: why is signed integer overflow UB?

[TUHS] C history question: why is signed integer overflow UB?

[Dan Cross]

[Note: A few folks Cc'ed directly]

This is not exactly a Unix history question, but given the close
relationship between C's development and that of Unix, perhaps it is
both topical and someone may chime in with a definitive answer.

Starting with the 1990 ANSI/ISO C standard, and continuing on to the
present day, C has specified that signed integer overflow is
"undefined behavior"; unsigned integer arithmetic is defined to be
modular, and unsigned integer operations thus cannot meaningfully
overflow, since they're always taken mod 2^b, where b is the number of
bits in the datum (assuming unsigned int or larger, since type
promotion of smaller things gets weird).

But why is signed overflow UB? My belief has always been that signed
integer overflow across various machines has non-deterministic
behavior, in part because some machines would trap on overflow (e.g.,
Unisys 1100 series mainframes) while others used non-2's-complement
representations for signed integers (again, the Unisys 1100 series,
which used 1's complement), and so the results could not be precisely
defined: even if it did not trap, overflowing a 1's complement machine
yielded a different _value_ than on 2's complement. And around the
time of initial standardization, targeting those machines was still an
important use case.  So while 2's complement with silent wrap-around
was common, it could not be assumed, and once machines that generated
traps on overflow were brought into the mix, it was safer to simply
declare behavior on overflow undefined.

But is that actually the case?

Thanks in advance.

        - Dan C.

[TUHS] Re: C history question: why is signed integer overflow UB?

[Luther Johnson]

My belief is that this was done so compilers could employ optimizations 
that did not have to consider or maintain implementation-specific 
behavior when integers would wrap. I don't agree with this, I think 2's 
complement behavior on integers as an implementation-specific behavior 
can be well-specified, and well-understood, machine by machine, but I 
think this is one of the places where compilers and benchmarks conspire 
to subvert the obvious and change the language to "language-legally" 
allow optimizations that can break the used-to-be-expected 2's 
complement implementation-specific behavior.

I'm sure many people will disagree, but I think this is part of the 
slippery slope of modern C, and part of how it stopped being more 
usefully, directly, tied to the machine underneath.

On 08/15/2025 10:17 AM, Dan Cross wrote:
> [Note: A few folks Cc'ed directly]
>
> This is not exactly a Unix history question, but given the close
> relationship between C's development and that of Unix, perhaps it is
> both topical and someone may chime in with a definitive answer.
>
> Starting with the 1990 ANSI/ISO C standard, and continuing on to the
> present day, C has specified that signed integer overflow is
> "undefined behavior"; unsigned integer arithmetic is defined to be
> modular, and unsigned integer operations thus cannot meaningfully
> overflow, since they're always taken mod 2^b, where b is the number of
> bits in the datum (assuming unsigned int or larger, since type
> promotion of smaller things gets weird).
>
> But why is signed overflow UB? My belief has always been that signed
> integer overflow across various machines has non-deterministic
> behavior, in part because some machines would trap on overflow (e.g.,
> Unisys 1100 series mainframes) while others used non-2's-complement
> representations for signed integers (again, the Unisys 1100 series,
> which used 1's complement), and so the results could not be precisely
> defined: even if it did not trap, overflowing a 1's complement machine
> yielded a different _value_ than on 2's complement. And around the
> time of initial standardization, targeting those machines was still an
> important use case.  So while 2's complement with silent wrap-around
> was common, it could not be assumed, and once machines that generated
> traps on overflow were brought into the mix, it was safer to simply
> declare behavior on overflow undefined.
>
> But is that actually the case?
>
> Thanks in advance.
>
>          - Dan C.
>

[TUHS] Re: C history question: why is signed integer overflow UB?

[Luther Johnson]

Or one's complement on those machines, but the idea was that this case 
is out of bounds, so you don't have to worry if munging some computation 
by substituting or rearranging expressions would change it, whatever the 
machine-specific behavior was.

On 08/15/2025 10:31 AM, Luther Johnson wrote:
> My belief is that this was done so compilers could employ 
> optimizations that did not have to consider or maintain 
> implementation-specific behavior when integers would wrap. I don't 
> agree with this, I think 2's complement behavior on integers as an 
> implementation-specific behavior can be well-specified, and 
> well-understood, machine by machine, but I think this is one of the 
> places where compilers and benchmarks conspire to subvert the obvious 
> and change the language to "language-legally" allow optimizations that 
> can break the used-to-be-expected 2's complement 
> implementation-specific behavior.
>
> I'm sure many people will disagree, but I think this is part of the 
> slippery slope of modern C, and part of how it stopped being more 
> usefully, directly, tied to the machine underneath.
>
> On 08/15/2025 10:17 AM, Dan Cross wrote:
>> [Note: A few folks Cc'ed directly]
>>
>> This is not exactly a Unix history question, but given the close
>> relationship between C's development and that of Unix, perhaps it is
>> both topical and someone may chime in with a definitive answer.
>>
>> Starting with the 1990 ANSI/ISO C standard, and continuing on to the
>> present day, C has specified that signed integer overflow is
>> "undefined behavior"; unsigned integer arithmetic is defined to be
>> modular, and unsigned integer operations thus cannot meaningfully
>> overflow, since they're always taken mod 2^b, where b is the number of
>> bits in the datum (assuming unsigned int or larger, since type
>> promotion of smaller things gets weird).
>>
>> But why is signed overflow UB? My belief has always been that signed
>> integer overflow across various machines has non-deterministic
>> behavior, in part because some machines would trap on overflow (e.g.,
>> Unisys 1100 series mainframes) while others used non-2's-complement
>> representations for signed integers (again, the Unisys 1100 series,
>> which used 1's complement), and so the results could not be precisely
>> defined: even if it did not trap, overflowing a 1's complement machine
>> yielded a different _value_ than on 2's complement. And around the
>> time of initial standardization, targeting those machines was still an
>> important use case.  So while 2's complement with silent wrap-around
>> was common, it could not be assumed, and once machines that generated
>> traps on overflow were brought into the mix, it was safer to simply
>> declare behavior on overflow undefined.
>>
>> But is that actually the case?
>>
>> Thanks in advance.
>>
>>          - Dan C.
>>
>

[TUHS] Re: C history question: why is signed integer overflow UB?

[Nevin Liber]

[-- Attachment #1: Type: text/plain, Size: 2792 bytes --]

On Fri, Aug 15, 2025 at 12:32 PM Luther Johnson <
luther.johnson@makerlisp.com> wrote:

> My belief is that this was done so compilers could employ optimizations
> that did not have to consider or maintain implementation-specific
> behavior when integers would wrap. I don't agree with this, I think 2's
> complement behavior on integers as an implementation-specific behavior
> can be well-specified, and well-understood, machine by machine, but I
> think this is one of the places where compilers and benchmarks conspire
> to subvert the obvious and change the language to "language-legally"
> allow optimizations that can break the used-to-be-expected 2's
> complement implementation-specific behavior.
>

It isn't just about optimizations.

Unsigned math in C is well defined here.  The problem is that its wrapping
behavior is almost (but not) always a bug.  Because of that, for instance,
one cannot write a no-false-positive sanitizer to catch this because it
cannot tell the difference between an accidental bug and a deliberate use.
This is a well-defined case with a very reasonable definition which most of
the time leads to bugs.

There are times folks want the wrapping behavior.  There are times folks
want saturating behavior.  There are times folks want such code to error
out.  There are times folks want the optimizing behavior because their code
doesn't go anywhere near wrapping.

Ultimately, one needs different functions for the different behaviors, but
if you only have one spelling for that operation, you can only get one
behavior.  A given type has to pick one of the above behaviors for a given
spelling of an operation.

You can, of course, disagree with what C picked here (many do), but it is
unlikely to change in the future.

Not that it hasn't been tried.  In 2018 there was a proposal for C++ P0907R0
Signed Integers are Two's Complement <https://wg21.link/P0907R0>, and if
you look at the next revision of that paper P0907R1
<https://wg21.link/P0907R1>, there was no consensus for the wrapping
behavior.  Quoting the paper:

   - Performance concerns, whereby defining the behavior prevents
   optimizers from assuming that overflow never occurs;
   - Implementation leeway for tools such as sanitizers;
   - Data from Google suggesting that over 90% of all overflow is a bug,
   and defining wrapping behavior would not have solved the bug.

Fun fact:  in C++ std::atomic<int> does wrap, so you can actually get the
behavior you want.  I haven't looked to see if that is also true using C's
_Atomic type qualifier.

Full disclosure:  I am on the WG21 (C++) Committee and am starting to
participate on the WG14 (C) Committee.
-- 
 Nevin ":-)" Liber  <mailto:nevin@eviloverlord.com>  +1-847-691-1404

[-- Attachment #2: Type: text/html, Size: 3725 bytes --]

[TUHS] Re: C history question: why is signed integer overflow UB?

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 4652 bytes --]

I suspect that it was the absence of a signed right shift. In my
Decsystem-20 OS class, one of the differences between the compiler on the
VAX and the compiler on the '20 was that -1 >> 1 was -1 on the VAX and
2^35-1 on the '20. This was in 1985 or 1986 for a compiler that was written
in 1982 or 83 (that no longer exists today, I'm told, other '20 compilers
took over). Some signed overflows / underflow / traps were different as
well, which only mattered in the '20 simulator we were running since all
traps and interrupts reset the trap frame (whether you wanted to or not),
so if you did it in the kernel interrupt, you'd double trap the machine (I
think this was an intentional difference to teach about being careful in an
interrupt context, but still...). It's the lack of uniformity for signed
operations for machines generally available in the late 70s and early 80s
(often based on designs dating back to the 60s) that I always assumed drove
it...  These details took up bits of three different lectures in the OS
class, and was a big source of problems by everybody...

So while my specific case was super weird / edge. But if it came up in an
undergraduate OS class at an obscure technical school in the middle of the
desert in New Mexico, I can't imagine that the design committee didn't know
about it. Since the standardization started a few years before c89, I'm
guessing that we'd see that if we had early drafts of the standard (or
maybe it was inherited from K&R-era).

Warner

On Fri, Aug 15, 2025 at 11:37 AM Luther Johnson <
luther.johnson@makerlisp.com> wrote:

> Or one's complement on those machines, but the idea was that this case
> is out of bounds, so you don't have to worry if munging some computation
> by substituting or rearranging expressions would change it, whatever the
> machine-specific behavior was.
>
> On 08/15/2025 10:31 AM, Luther Johnson wrote:
> > My belief is that this was done so compilers could employ
> > optimizations that did not have to consider or maintain
> > implementation-specific behavior when integers would wrap. I don't
> > agree with this, I think 2's complement behavior on integers as an
> > implementation-specific behavior can be well-specified, and
> > well-understood, machine by machine, but I think this is one of the
> > places where compilers and benchmarks conspire to subvert the obvious
> > and change the language to "language-legally" allow optimizations that
> > can break the used-to-be-expected 2's complement
> > implementation-specific behavior.
> >
> > I'm sure many people will disagree, but I think this is part of the
> > slippery slope of modern C, and part of how it stopped being more
> > usefully, directly, tied to the machine underneath.
> >
> > On 08/15/2025 10:17 AM, Dan Cross wrote:
> >> [Note: A few folks Cc'ed directly]
> >>
> >> This is not exactly a Unix history question, but given the close
> >> relationship between C's development and that of Unix, perhaps it is
> >> both topical and someone may chime in with a definitive answer.
> >>
> >> Starting with the 1990 ANSI/ISO C standard, and continuing on to the
> >> present day, C has specified that signed integer overflow is
> >> "undefined behavior"; unsigned integer arithmetic is defined to be
> >> modular, and unsigned integer operations thus cannot meaningfully
> >> overflow, since they're always taken mod 2^b, where b is the number of
> >> bits in the datum (assuming unsigned int or larger, since type
> >> promotion of smaller things gets weird).
> >>
> >> But why is signed overflow UB? My belief has always been that signed
> >> integer overflow across various machines has non-deterministic
> >> behavior, in part because some machines would trap on overflow (e.g.,
> >> Unisys 1100 series mainframes) while others used non-2's-complement
> >> representations for signed integers (again, the Unisys 1100 series,
> >> which used 1's complement), and so the results could not be precisely
> >> defined: even if it did not trap, overflowing a 1's complement machine
> >> yielded a different _value_ than on 2's complement. And around the
> >> time of initial standardization, targeting those machines was still an
> >> important use case.  So while 2's complement with silent wrap-around
> >> was common, it could not be assumed, and once machines that generated
> >> traps on overflow were brought into the mix, it was safer to simply
> >> declare behavior on overflow undefined.
> >>
> >> But is that actually the case?
> >>
> >> Thanks in advance.
> >>
> >>          - Dan C.
> >>
> >
>
>

[-- Attachment #2: Type: text/html, Size: 5513 bytes --]

[TUHS] Re: C history question: why is signed integer overflow UB?

[Luther Johnson]

[-- Attachment #1: Type: text/plain, Size: 4310 bytes --]

I hear and understand what you're saying. I think what I'm trying to 
point out, is that in C, as it was originally implemented, in 
expressions "a + b", "a >> 1", "++a", C "does what the machine does". 
That's a very different thing from having rational, safe, predictable 
language semantics for operations on types - but it was also a strength, 
and a simple way to describe what C would do, deferring to machine 
semantics. I believe one place in C89/C90 where this is stated 
explicitly, as "do what the machine does", is "-1 >> 1", as opposed to 
"-1 / 2".  On most machines, this program:

#include <stdio.h>

int main()
{
     printf("%d\n", -1 >> 1);
     printf("%d\n", -1 / 2);

     return 0;
}

returns:

-1
0

directly reflecting the underlying machine shift and divide instructions 
- but if you made an appeal to rational integer type semantics, you 
might decide for it to do something else.

Old C was one way. Modern C has gone another way, good tools and 
rational semantics for safer and/or higher performance code, or some 
balance between those and other goals. Old C just did what the machine 
did, and was a high leverage tool - but you had to understand your machine.

On 08/15/2025 11:02 AM, Nevin Liber wrote:
> On Fri, Aug 15, 2025 at 12:32 PM Luther Johnson 
> <luther.johnson@makerlisp.com <mailto:luther.johnson@makerlisp.com>> 
> wrote:
>
>     My belief is that this was done so compilers could employ
>     optimizations
>     that did not have to consider or maintain implementation-specific
>     behavior when integers would wrap. I don't agree with this, I
>     think 2's
>     complement behavior on integers as an implementation-specific
>     behavior
>     can be well-specified, and well-understood, machine by machine, but I
>     think this is one of the places where compilers and benchmarks
>     conspire
>     to subvert the obvious and change the language to "language-legally"
>     allow optimizations that can break the used-to-be-expected 2's
>     complement implementation-specific behavior.
>
>
> It isn't just about optimizations.
>
> Unsigned math in C is well defined here.  The problem is that its 
> wrapping behavior is almost (but not) always a bug.  Because of that, 
> for instance, one cannot write a no-false-positive sanitizer to catch 
> this because it cannot tell the difference between an accidental bug 
> and a deliberate use.  This is a well-defined case with a very 
> reasonable definition which most of the time leads to bugs.
>
> There are times folks want the wrapping behavior.  There are times 
> folks want saturating behavior.  There are times folks want such code 
> to error out.  There are times folks want the optimizing behavior 
> because their code doesn't go anywhere near wrapping.
>
> Ultimately, one needs different functions for the different 
> behaviors, but if you only have one spelling for that operation, you 
> can only get one behavior.  A given type has to pick one of the above 
> behaviors for a given spelling of an operation.
>
> You can, of course, disagree with what C picked here (many do), but it 
> is unlikely to change in the future.
>
> Not that it hasn't been tried.  In 2018 there was a proposal for C++ 
> P0907R0 Signed Integers are Two's Complement 
> <https://wg21.link/P0907R0>, and if you look at the next revision of 
> that paper P0907R1 <https://wg21.link/P0907R1>, there was no consensus 
> for the wrapping behavior.  Quoting the paper:
>
>   * Performance concerns, whereby defining the behavior prevents
>     optimizers from assuming that overflow never occurs;
>   * Implementation leeway for tools such as sanitizers;
>   * Data from Google suggesting that over 90% of all overflow is a
>     bug, and defining wrapping behavior would not have solved the bug.
>
> Fun fact:  in C++ std::atomic<int> does wrap, so you can actually get 
> the behavior you want.  I haven't looked to see if that is also true 
> using C's _Atomic type qualifier.
>
> Full disclosure:  I am on the WG21 (C++) Committee and am starting to 
> participate on the WG14 (C) Committee.
> -- 
>  Nevin ":-)" Liber  <mailto:nevin@eviloverlord.com 
> <mailto:nevin@eviloverlord.com>>  +1-847-691-1404


[-- Attachment #2: Type: text/html, Size: 7107 bytes --]

[TUHS] Re: C history question: why is signed integer overflow UB?

[John Levine]

It appears that Luther Johnson <luther.johnson@makerlisp.com> said:
>-=-=-=-=-=-
>
>I hear and understand what you're saying. I think what I'm trying to 
>point out, is that in C, as it was originally implemented, in 
>expressions "a + b", "a >> 1", "++a", C "does what the machine does". 

We just had the same argument in comp.arch and came to largely the same
conclusion.  While overflow behavior on any particular machine may be
predictable, there's no consistency from one machine to another,
particularly back when there were still one's complement machines
where people compiled C code (some of the Univac mainframes.)

It isn't all that predictable even on a single machine.  I know several
where overflow might or might not trap depending on a program-settable
status bit.

R's,
John

[TUHS] Re: C history question: why is signed integer overflow UB?

[Douglas McIlroy]

Idle thought; There's been mention of 1's complement. If overflow is
UB because of that possibility, maybe ==0 should be, too!

Doug

On Fri, Aug 15, 2025 at 2:44 PM John Levine <johnl@taugh.com> wrote:
>
> It appears that Luther Johnson <luther.johnson@makerlisp.com> said:
> >-=-=-=-=-=-
> >
> >I hear and understand what you're saying. I think what I'm trying to
> >point out, is that in C, as it was originally implemented, in
> >expressions "a + b", "a >> 1", "++a", C "does what the machine does".
>
> We just had the same argument in comp.arch and came to largely the same
> conclusion.  While overflow behavior on any particular machine may be
> predictable, there's no consistency from one machine to another,
> particularly back when there were still one's complement machines
> where people compiled C code (some of the Univac mainframes.)
>
> It isn't all that predictable even on a single machine.  I know several
> where overflow might or might not trap depending on a program-settable
> status bit.
>
> R's,
> John

[TUHS] Re: C history question: why is signed integer overflow UB?

[Dave Horsfall]

On Fri, 15 Aug 2025, Douglas McIlroy wrote:

> Idle thought; There's been mention of 1's complement. If overflow is UB 
> because of that possibility, maybe ==0 should be, too!

I understand that with ones-complement machines (such as the CDC series), 
a computation resulting in -0 will be normalised to 0 (but a bit inversion 
won't).

-- Dave

[TUHS] Re: C history question: why is signed integer overflow UB?

[Luther Johnson]

Relating this all to a Godel-ish classification of axiomatic systems, 
language definitions with undefined behavior may be perfectly 
consistent, but there is useful behavior that cannot be expressed in 
those languages, while languages with no undefined behavior but with 
lots of implementation-specific behavior can express much more, but with 
less consistency.

On 08/15/2025 02:04 PM, Douglas McIlroy wrote:
> Idle thought; There's been mention of 1's complement. If overflow is
> UB because of that possibility, maybe ==0 should be, too!
>
> Doug
>
> On Fri, Aug 15, 2025 at 2:44 PM John Levine <johnl@taugh.com> wrote:
>> It appears that Luther Johnson <luther.johnson@makerlisp.com> said:
>>> -=-=-=-=-=-
>>>
>>> I hear and understand what you're saying. I think what I'm trying to
>>> point out, is that in C, as it was originally implemented, in
>>> expressions "a + b", "a >> 1", "++a", C "does what the machine does".
>> We just had the same argument in comp.arch and came to largely the same
>> conclusion.  While overflow behavior on any particular machine may be
>> predictable, there's no consistency from one machine to another,
>> particularly back when there were still one's complement machines
>> where people compiled C code (some of the Univac mainframes.)
>>
>> It isn't all that predictable even on a single machine.  I know several
>> where overflow might or might not trap depending on a program-settable
>> status bit.
>>
>> R's,
>> John

[TUHS] Re: C history question: why is signed integer overflow UB?

[Lars Brinkhoff]

Warner Losh writes:
> I suspect that it was the absence of a signed right shift. In my
> Decsystem-20 OS class, one of the differences between the compiler on
> the VAX and the compiler on the '20 was that -1 >> 1 was -1 on the VAX
> and 2^35-1 on the '20.

The DEC-20 (aka PDP-10) does have a signed right shift instruction.
Apparently the compiler didn't use it.

[TUHS] Re: C history question: why is signed integer overflow UB?

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 2964 bytes --]

below...

On Fri, Aug 15, 2025 at 10:18 AM Dan Cross <crossd@gmail.com> wrote:

> [Note: A few folks Cc'ed directly]
>
>
>
> Starting with the 1990 ANSI/ISO C standard, and continuing on to the
> present day, C has specified that signed integer overflow is
> "undefined behavior"; unsigned integer arithmetic is defined to be
> modular, and unsigned integer operations thus cannot meaningfully
> overflow, since they're always taken mod 2^b, where b is the number of
> bits in the datum (assuming unsigned int or larger, since type
> promotion of smaller things gets weird).
>
> But why is signed overflow UB? My belief has always been that signed
> integer overflow across various machines has non-deterministic
> behavior, in part because some machines would trap on overflow while
> others used non-2's-complement
> representations for signed integers and so the results could not be
> precisely
> defined: even if it did not trap, overflowing a 1's complement machine
> yielded a different _value_ than on 2's complement. And around the
> time of initial standardization, targeting those machines was still an
> important use case.  So while 2's complement with silent wrap-around
> was common, it could not be assumed, and once machines that generated
> traps on overflow were brought into the mix, it was safer to simply
> declare behavior on overflow undefined.
>
We need someone like Peter Darnell, Plauger, and some of the original ANSI
C weenies that had to argue this all through in those days, but I think you
caught the core issues.

This was just one of the many troublesome things that had to be worked
through.  Until C89, the only ``official'' C was what Dennis shipped at any
given time, and that was a bit ephemeral — particularly as the PCs and
microprocessors C compiler implemented started to play fast and lose with
the C syntax.

The core task of the C89 was to do as little harm as possible.  My memory
is that Dennis was pretty cool and rarely played his trump card (far
pointers is one case I am aware that he told the 8086 people to pound sand)
, but the compromise that the committee tended to use to kick the can down
the road and get the standard out the door was to make things UB with the
hopes that later versions could find a way to tighten things up.

Truth is, other language specs had used that (like Fortran) , so it was not
a bad idea.

So, back to your question, I can not say what the actual cause if why there
was a conflict WRT to  signed integer overflow, but I bet it was that,
since so many compilers handled it in different ways, the committee did not
have a way to make a formal standard that would work, and they never found
one later.

FWIW:   Remember, C89 tossed a lot of systems like the PDP-11 away with
floating point.  It says, we are going to use IEEE 754.  So just because an
old system used a format, did not guarantee it would be accepted.

[-- Attachment #2: Type: text/html, Size: 4830 bytes --]