Why does integer division by -1 (negative one) res

Question

I have an assignment of expaining some seemingly strange behaviors of C code (running on x86). I can easily complete everything else but this one has really confused me.

Code snippet 1 outputs -2147483648

int a = 0x80000000;
int b = a / -1;
printf("%d\n", b);

Code snippet 2 outputs nothing, and gives a Floating point exception

int a = 0x80000000;
int b = -1;
int c = a / b;
printf("%d\n", c);

I well know the reason for the result of Code Snippet 1 (1 + ~INT_MIN == INT_MIN), but I can't quite understand how can integer division by -1 generate FPE, nor can I reproduce it on my Android phone (AArch64, GCC 7.2.0). Code 2 just output the same as Code 1 without any exceptions. Is it a hidden bug feature of x86 processor?

The assignment didn't tell anything else (including CPU architecture), but since the whole course is based on a desktop Linux distro, you can safely assume it's a modern x86.

---

Edit: I contacted my friend and he tested the code on Ubuntu 16.04 (Intel Kaby Lake, GCC 6.3.0). The result was consistent with whatever the assignment stated (Code 1 output the said thing and Code 2 crashed with FPE).

Answer 1

Both cases are weird, as the first consists in dividing -2147483648 by -1 and should give 2147483648, and not the result you are receiving.

0x80000000 is not a valid int number in a 32 bit architecture that represents numbers in two's complement. If you calculate its negative value, you'll get again to it, as it has no opposite number around zero. When you do arithmetic with signed integers, it works well for integer addition and substraction (always with care, as you are quite easy to overflow, when you add the largest value to some int) but you cannot safely use it to multiply or divide. So in this case, you are invoking Undefined Behaviour. You always invoke undefined behaviour (or implementation defined behaviour, which is similar, but not the same) on overflow with signed integers, as implementations vary widely in implementing that.

I'll try to explain what can be happening (with no trustness), as the compiler is free to do anything, or nothing at all.

Concretely, 0x80000000 as represented in two's complement is

1000_0000_0000_0000_0000_0000_0000

if we complement this number, we get (first complement all bits, then add one)

0111_1111_1111_1111_1111_1111_1111 + 1 =>
1000_0000_0000_0000_0000_0000_0000  !!!  the same original number.

suprisingly the same number.... You had an overflow (there's no counterpart positive value to this number, as we overflown when changing sign) then you take out the sign bit, masking with

1000_0000_0000_0000_0000_0000_0000 &
0111_1111_1111_1111_1111_1111_1111 =>
0000_0000_0000_0000_0000_0000_0000

which is the number you use as divisor, leading to a division by zero exception.

But as I said before, this is what can be happening on your system, but not sure, as the standard says this is Undefined behaviour and, as so, you can get whatever different behaviour from your computer/compiler.

NOTE 1

As the compiler is concerned, and the standard doesn't say anything about the valid ranges of int that must be implemented (the standard doesn't include normally 0x8000...000 in two's complement architectures) the correct behaviour of 0x800...000 in two's complement architectures should be, as it has the largest absolute value for an integer of that type, to give a result of 0 when dividing a number by it. But hardware implementations normally don't allow to divide by such a number (as many of them doesn't even implement signed integer division, but simulate it from unsigned division, so many simply extract the signs and do an unsigned division) That requires a check before division, and as the standard says Undefined behaviour, implementations are allowed to freely avoid such a check, and disallow dividing by that number. They simply select the integer range to go from 0x8000...001 to 0xffff...fff, and then from 0x000..0000 to 0x7fff...ffff, disallowing the value 0x8000...0000 as invalid.

Answer 2

On x86 if you divide by actually using the idiv operation (which is not really necessary for constant arguments, not even for variables-known-to-be-constant, but it happened anyway), INT_MIN / -1 is one of the cases that results in #DE (divide error). It's really a special case of the quotient being out of range, in general that is possible because idiv divides an extra-wide dividend by the divisor, so many combinations cause overflow - but INT_MIN / -1 is the only case that isn't a div-by-0 that you can normally access from higher level languages since they typically do not expose the extra-wide-dividend capabilities.

Linux annoyingly maps the #DE to SIGFPE, which has probably confused everyone who dealt with it the first time.

Answer 3

With undefined behavior very bad things could happen, and sometimes they do happen.

Your question has no sense in C (read Lattner on UB). But you could get the assembler code (e.g. produced by gcc -O -fverbose-asm -S) and care about machine code behavior.

On x86-64 with Linux integer overflow (and also integer division by zero, IIRC) gives a SIGFPE signal. See signal(7)

BTW, on PowerPC integer division by zero is rumored to give -1 at the machine level (but some C compilers generate extra code to test that case).

The code in your question is undefined behavior in C. The generated assembler code has some defined behavior (depends upon the ISA and processor).

^{(the assignment is done to make you read more about UB, notably Lattner 's blog, which you should absolutely read)}

Answer 4

Signed int division in two's complement is undefined if:

1. the divisor is zero, OR
2. the dividend is INT_MIN (==0x80000000 if int is int32_t) and the divisor is -1 (in two's complement, -INT_MIN > INT_MAX, which causes integer overflow, which is undefined behavior in C)

(https://www.securecoding.cert.org recommends wrapping integer operations in functions that check for such edge cases)

Since you're invoking undefined behavior by breaking rule 2, anything can happen, and as it happens, this particular anything on your platform happens to be an FPE signal being generated by your processor.

Answer 5

There are four things going on here:

• gcc -O0 behaviour explains the difference between your two versions. (While clang -O0 happens to compile them both with idiv). And why you get this even with compile-time-constant operands.
• x86 idiv faulting behaviour vs. behaviour of the division instruction on ARM

• If integer math results in a signal being delivered, POSIX require it to be SIGFPE: On which platforms does integer divide by zero trigger a floating point exception? But POSIX doesn't require trapping for any particular integer operation. (This is why it's allowed for x86 and ARM to be different).

  The Single Unix Specification defines SIGFPE as "Erroneous arithmetic operation". It's confusingly named after floating point, but in a normal system with the FPU in its default state, only integer math will raise it. On x86, only integer division. On MIPS, a compiler could use add instead of addu for signed math, so you could get traps on signed add overflow. (gcc uses addu even for signed, but an undefined-behaviour detector might use add.)

• C Undefined Behaviour rules (signed overflow, and division specifically) which let gcc emit code which can trap in that case.

---

gcc with no options is the same as gcc -O0.

-O0 Reduce compilation time and make debugging produce the expected results. This is the default.

This explains the difference between your two versions:

Not only does gcc -O0 not try to optimize, it actively de-optimizes to make asm that independently implements each C statement within a function. This allows gdb's jump command to work safely, letting you jump to a different line within the function and act like you're really jumping around in the C source.

It also can't assume anything about variable values between statements, because you can change variables with set b = 4. This is obviously catastrophically bad for performance, which is why -O0 code runs several times slower than normal code, and why optimizing for -O0 specifically is total nonsense. It also makes -O0 asm output really noisy and hard for a human to read, because of all the storing/reloading, and lack of even the most obvious optimizations.

int a = 0x80000000;
int b = -1;
  // debugger can stop here on a breakpoint and modify b.
int c = a / b;        // a and b have to be treated as runtime variables, not constants.
printf("%d\n", c);

I put your code inside functions on the Godbolt compiler explorer to get the asm for those statements.

To evaluate a/b, gcc -O0 has to emit code to reload a and b from memory, and not make any assumptions about their value.

But with int c = a / -1;, you can't change the -1 with a debugger, so gcc can and does implement that statement the same way it would implement int c = -a;, with an x86 neg eax or AArch64 neg w0, w0 instruction, surrounded by a load(a)/store(c). On ARM32, it's a rsb r3, r3, #0 (reverse-subtract: r3 = 0 - r3).

However, clang5.0 -O0 doesn't do that optimization. It still uses idiv for a / -1, so both versions will fault on x86 with clang. Why does gcc "optimize" at all? See Disable all optimization options in GCC. gcc always transforms through an internal representation, and -O0 is just the minimum amount of work needed to produce a binary. It doesn't have a "dumb and literal" mode that tries to make the asm as much like the source as possible.

---

x86 idiv vs. AArch64 sdiv:

x86-64:

    # int c = a / b  from x86_fault()
    mov     eax, DWORD PTR [rbp-4]
    cdq                                 # dividend sign-extended into edx:eax
    idiv    DWORD PTR [rbp-8]           # divisor from memory
    mov     DWORD PTR [rbp-12], eax     # store quotient

Unlike imul r32,r32, there's no 2-operand idiv that doesn't have a dividend upper-half input. Anyway, not that it matters; gcc is only using it with edx = copies of the sign bit in eax, so it's really doing a 32b / 32b => 32b quotient + remainder. As documented in Intel's manual, idiv raises #DE on:

• divisor = 0
• The signed result (quotient) is too large for the destination.

Overflow can easily happen if you use the full range of divisors, e.g. for int result = long long / int with a single 64b / 32b => 32b division. But gcc can't do that optimization because it's not allowed to make code that would fault instead of following the C integer promotion rules and doing a 64-bit division and then truncating to int. It also doesn't optimize even in cases where the divisor is known to be large enough that it couldn't #DE

When doing 32b / 32b division (with cdq), the only input that can overflow is INT_MIN / -1. The "correct" quotient is a 33-bit signed integer, i.e. positive 0x80000000 with a leading-zero sign bit to make it a positive 2's complement signed integer. Since this doesn't fit in eax, idiv raises a #DE exception. The kernel then delivers SIGFPE.

AArch64:

    # int c = a / b  from x86_fault()  (which doesn't fault on AArch64)
    ldr     w1, [sp, 12]
    ldr     w0, [sp, 8]          # 32-bit loads into 32-bit registers
    sdiv    w0, w1, w0           # 32 / 32 => 32 bit signed division
    str     w0, [sp, 4]

AFAICT, ARM hardware division instructions don't raise exceptions for divide by zero or for INT_MIN/-1. Or at least, some ARM CPUs don't. divide by zero exception in ARM OMAP3515 processor

AArch64 sdiv documentation doesn't mention any exceptions.

However, software implementations of integer division may raise: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka4061.html. (gcc uses a library call for division on ARM32 by default, unless you set a -mcpu that has HW division.)

---

C Undefined Behaviour.

As PSkocik explains, INT_MIN / -1 is undefined behaviour in C, like all signed integer overflow. This allows compilers to use hardware division instructions on machines like x86 without checking for that special case. If it had to not fault, unknown inputs would require run-time compare-and branch checks, and nobody wants C to require that.

---

More about the consequences of UB:

With optimization enabled, the compiler can assume that a and b still have their set values when a/b runs. It can then see the program has undefined behaviour, and thus can do whatever it wants. gcc chooses to produce INT_MIN like it would from -INT_MIN.

On a 2's complement system, the most-negative number is its own negative. This is a nasty corner-case for 2's complement, because it means abs(x) can still be negative. https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number

int x86_fault() {
    int a = 0x80000000;
    int b = -1;
    int c = a / b;
    return c;
}

compile to this with gcc6.3 -O3 for x86-64

x86_fault:
    mov     eax, -2147483648
    ret

but clang5.0 -O3 compiles to (with no warning even with -Wall -Wextra`):

x86_fault:
    ret

Undefined Behaviour really is totally undefined. Compilers can do whatever they feel like, including returning whatever garbage was in eax on function entry, or loading a NULL pointer and an illegal instruction. e.g. with gcc6.3 -O3 for x86-64:

int *local_address(int a) {
    return &a;
}

local_address:
    xor     eax, eax     # return 0
    ret

void foo() {
    int *p = local_address(4);
    *p = 2;
}

 foo:
   mov     DWORD PTR ds:0, 0     # store immediate 0 into absolute address 0
   ud2                           # illegal instruction

Your case with -O0 didn't let the compilers see the UB at compile time, so you got the "expected" asm output.

See also What Every C Programmer Should Know About Undefined Behavior (the same LLVM blog post that Basile linked).