views:

190

answers:

7

I have a few questions about divide overflow errors on x86 or x86_64 architecture. Lately I've been reading about integer overflows. Usually, when an arithmetic operation results in an integer overflow, the carry bit or overflow bit in the FLAGS register is set. But apparently, according to this article, overflows resulting from division operations don't set the overflow bit, but rather trigger a hardware exception, similar to when you divide by zero.

Now, integer overflows resulting from division are a lot more rare than say, multiplication. There's only a few ways to even trigger a division overflow. One way would be to do something like:

int16_t a = -32768;
int16_t b = -1;
int16_t c = a / b;

In this case, due to the two's complement representation of signed integers, you can't represent positive 32768 in a signed 16-bit integer, so the division operation overflows, resulting in the erroneous value of -32768.

A few questions:

1) Contrary to what this article says, the above did NOT cause a hardware exception. I'm using an x86_64 machine running Linux, and when I divide by zero the program terminates with a Floating point exception. But when I cause a division overflow, the program continues as usual, silently ignoring the erroneous quotient. So why doesn't this cause a hardware exception?

2) Why are division errors treated so severely by the hardware, as opposed to other arithmetic overflows? Why should a multiplication overflow (which is much more likely to accidentally occur) be silently ignored by the hardware, but a division overflow is supposed to trigger a fatal interrupt?

=========== EDIT ==============

Okay, thanks everyone for the responses. I've gotten responses saying basically that the above 16-bit integer division shouldn't cause a hardware fault because the quotient is still less than the register size. I don't understand this. In this case, the register storing the quotient is 16-bit - which is too small to store signed positive 32768. So why isn't a hardware exception raised?

Okay, let's do this directly in GCC inline assembly and see what happens:

int16_t a = -32768;
int16_t b = -1;

__asm__
(
    "xorw %%dx, %%dx;"            // Clear the DX register (upper-bits of dividend)
    "movw %1, %%ax;"              // Load lower bits of dividend into AX
    "movw %2, %%bx;"              // Load the divisor into BX
    "idivw %%bx;"                 // Divide a / b (quotient is stored in AX)
    "movw %%ax, %0;"              // Copy the quotient into 'b'
    : "=rm"(b)                    // Output list
    :"ir"(a), "rm"(b)             // Input list
    :"%ax", "%dx", "%bx"          // Clobbered registers
);

printf("%d\n", b);

This simply outputs an erroneous value: -32768. Still no hardware exception, even though the register storing the quotient (AX) is too small to fit the quotient. So I don't understand why no hardware fault is raised here.

+2  A: 

When you get an integer overflow with integer 2's complement add/subtract/multiply you still have a valid result - it's just missing some high order bits. This behaviour is often useful, so it would not be appropriate to generate an exception for this.

With integer division however the result of a divide by zero is useless (since, unlike floating point, 2's complement integers have no INF representation).

Paul R
+1  A: 

Contrary to what this article says, the above did NOT cause a hardware exception

The article did not say that. Is says

... they generate a division error if the source operand (divisor) is zero or if the quotient is too large for the designated register

Register size is definitely greater than 16 bits (32 || 64)

a1ex07
But in this case, the register storing the quotient is only 16-bit, so why isn't a hardware exception raised? See my edited question for further clarification.
Channel72
@Channel72, the type storing the quotient is only 16-bits. The register itself is 32-bits.
MSN
@MSN: In x86, the register size is variable. `ax` is a 16-bit register even on 64-bit machines, and that is the only way to explain how the result gets truncated here.
Potatoswatter
@MSN, I'm confused. The AX register stores the quotient, and the AX register is 16-bits
Channel72
@Potatoswatter, Ah, well, the assembly in the edited post is wrong (see andreyT's comment) but I sincerely doubt gcc would use 16-bit opcodes to do an int16_t divide. And the standard does not dictate how the division operation is actually implemented, only its results. Anyways, you can still get the integer overflow for division, but you shouldn't try with types that are smaller than `int` (Since you can only do it with INT_MIN/-1 anyway).
MSN
I tried the C code and it actually generates `idiv eax,ecx` in Visual Studio...
a1ex07
+1  A: 

From the relevant section on integer overflow:

Unlike the add, mul, and imul instructions, the Intel division instructions div and idiv do not set the overflow flag; they generate a division error if the source operand (divisor) is zero or if the quotient is too large for the designated register.

The size of a register is on a modern platform either 32 or 64 bits; 32768 will fit into one of those registers. However, the following code will very likely throw an integer overflow execption (it does on my core Duo laptop on VC8):

int x= INT_MIN;
int y= -1;
int z= x/y;
MSN
+6  A: 

In C language arithmetic operations are never performed within the types smaller than int. Any time you attempt arithmetic on smaller operands, they are first subjected to integral promotions which convert them to int. If on your platform int is, say, 32-bit wide, then there's no way to force a C program to perform 16-bit division. The compiler will generate 32-bit division instead. This is probably why your C experiment does not produce the expected overflow on division. If your platform does indeed have 32-bit int, then your best bet would be to try the same thing with 32-bit operands (i.e. divide INT_MIN by -1). I'm pretty sure that way you'll be able to eventually reproduce the overflow exception even in C code.


In your assembly code you are using 16-bit division, since you specified BX as the operand for idiv. 16-bit division on x86 divides the 32-bit dividend stored in DX:AX pair by the idiv operand. This is what you are doing in your code. The DX:AX pair is interpreted as one composite 32-bit register, meaning that the sign bit in this pair is now actually the highest-order bit of DX. The highest-order bit of AX is not a sign bit anymore.

And what you did you do with DX? You simply cleared it. You set it to 0. But with DX set to 0, your dividend is interpreted as positive! From the machine point of view, such a DX:AX pair actually represents a positive value +32768. I.e. in your assembly-language experiment you are dividing +32768 by -1. And the result is -32768, as it should be. Nothing unusual here.

If you want to represent -32768 in the DX:AX pair, you have to sign-extend it, i.e. you have to fill DX with all-one bit pattern, instead of zeros. Instead of doing xor DX, DX you should have initialized AX with your -32768 and then done cwd. That would sign-extend AX into DX.

For example, in my experiment (not GCC) this code

__asm  {
  mov AX, -32768
  cwd
  mov BX, -1
  idiv BX
}

causes the expected exception, because it does indeed attempt to divide -32768 by -1.

AndreyT
Okay I see. Thanks. This triggered the expected hardware fault.
Channel72
Nice catch on the assembly language example!
Michael Burr
+1  A: 
  1. The reason your example did not generate a hardware exception is due to C's integer promotion rules. Operands smaller than int get automatically promoted to ints before the operation is performed.

  2. As to why different kinds of overflows are handled differently, consider that at the x86 machine level, there's really no such thing a multiplication overflow. When you multiply AX by some other register, the result goes in the DX:AX pair, so there is always room for the result, and thus no occasion to signal an overflow exception. However, in C and other languages, the product of two ints is supposed to fit in an int, so there is such a thing as overflow at the C level. The x86 does sometimes set OF (overflow flag) on MULs, but it just means that the high part of the result is non-zero.

I. J. Kennedy
A: 

On an implementation with 32-bit int, your example does not result in a divide overflow. It results in a perfectly representable int, 32768, which then gets converted to int16_t in an implementation-defined manner when you make the assignment. This is due to the default promotions specified by the C language, and as a result, an implementation which raised an exception here would be non-conformant.

If you want to try to cause an exception (which still may or may not actually happen, it's up to the implementation), try:

int a = INT_MIN, b = -1, c = a/b;

You might have to do some tricks to prevent the compiler from optimizing it out at compile-time.

R..
A: 

I would conjecture that on some old computers, attempting to divide by zero would cause some severe problems (e.g. put the hardware into an endless cycle of trying to subtract enough so the remainder would be less than the dividend until an operator came along to fix things), and this started a tradition of divide overflows being regarded as more severe faults than integer overflows.

From a programming standpoint, there's no reason that an unexpected divide overflow should be any more or less serious than an unexpected integer overflow (signed or unsigned). Given the cost of division, the marginal cost of checking an overflow flag afterward would be pretty slight. Tradition is the only reason I can see for having a hardware trap.

supercat