A bit on modulo arithmetic.

Let's consider implementing the AMD64 adc add with carry instruction.

Add without carry is easy.

But how do we accomodate the extra carry_in?

How do we compute the flags? Unsigned carry and signed overflow?

Aka last carry and second to last carry.

Doing the operation bit-wise is easy. You can loop over the bits.

But what about using C++ unsigned::operator+ to do almost all the work in one operation?

intsafe.h LongLongAdd (I wrote it), teaches us, without carry_in:

 - Adding positive to negative never overflows.

 - If you add two positive numbers, you expect a positive result.

 - If you add two negative numbers, you expect a negative result.

 - Overflow if inputs have the same sign and output has the other sign.

The HPPA manual says similar I was pleased to later read.

But intsafe.h functions have no carry_in. What about it?

QEMU seems to ignore it for flag computation (and is correct).

So, the answer is, if you consider the edge cases, adding carry_in does not change their outcome. Or rather, the correctness of the rules. 

So these are the rules.

z = x + y + carry;

signed_overflow = (x < 0) == (y < 0) && (x < 0) != (z < 0);

Let's go through edge cases to confirm.

We will use 4bit numbers. The third term in any addition is carry_in.

Negative numbers are interchangable with large positive numbers.

If the output is shown as having two digits, the first is the unsigned carry_out.

Base 16 is implied. F==0xF==decimal15

8 == -8; F == -1

The sign is considered negative if the second digit is higher than 7.

check large positive:

  7+7+0=E overflowed

  7+7+1=F overflowed

check medium positive:

  3+4+0=7 no overflow

  3+4+1=8 overflowed

check negatives:

  8+8+0=10 overflowed

  8+8+1=11 overflowed

  F+F+0=1E=-2 no overflow

  F+F+1=1F=-1 no overflow

check mix of positive and negative:

 7+8+0=F=-1 no overflow

 7+8+1=10=0 no overflow

 7+F+0=16=6=no overflow

7+F+1=17=7=no overflow

How about carry?

intsafe.h's ULongLongAdd is less informative. Carry is if output is less than either input.

This does not work with carry_in. The output is equal to the inputs if adding max + max + carry.

Like adding 4bit numbers: F+F+1=1F

Again, QEMU does not seem to consider it (and is correct).

So, think again, more like LongLongAdd:

 - Adding two “negative" (unsigned!) numbers always carries. Edge case:8+8=10

 - Adding two positive numbers never carries. Edge case:7+7=E

 - Adding positive and “negative“ carried if result is positive. Edge cases:1+F=10; 8+7=F

And again, adding carry_in does not push any edge case over the edge.

8+8+1=11

7+7+1=F

1+F+1=11

8+7+1=10 this one seems like carry_in made a difference. It did push the result into having carry_out, but the same rules work and do not need to consider carry_in.

Why does carry_in not matter in this regard?

I think it has something to do with the asymmetric range. There is one

more negative number than positive numbers, and carry_in is always positive.

unsigned_carry = ((x < 0 && y < 0) || ((x < 0) != (y < 0) && (z >= 0));