Calculate a 16-bit Carry Flag?

[luser.droog]

I'm debugging my 8086 emulator
http://codegolf.stackexchange.com/questions/4732/emulate-an-intel-8086-cpu/9065#9065

And I'm hung up on the arithmetic. How do you tell if a 16bit addition yield
a Carry using postscript's 32-bit (PLRM stnd) integers. Since it's all 2's
complement, I figured I could just sign-extend all the inputs, call the ps
math op (`add`, `sub`), and then check the bits.

But no. Not working.

here's my code. This takes the 32bit result of the op (before it's chopped
to 8- or 16-bit to be stored in the destination) and attempts to set /CF to
one or zero depending on the Carry. /W has been set to 0 for a byte-op or 1
for a word-op.

setCF { dup
{7 15}W get shiftmask pop
dup 1 and exch -1 bitshift 1 and % _8|16 _9|17
%dup /CF exch def
2 copy ne {1}{0} ifelse /CF exch def
xor /OF exch def
} def

Does anybody know how to do this? I've read the wikipedia a zillion times
and it's just not clicking.

[Robert Bonomi]

In article <k9a31h$ngc$1...@dont-email.me>,

luser.droog <luser...@gmail.com> wrote:
>I'm debugging my 8086 emulator
>http://codegolf.stackexchange.com/questions/4732/emulate-an-intel-8086-cpu/9065#9065
>
>And I'm hung up on the arithmetic. How do you tell if a 16bit addition yield
>a Carry using postscript's 32-bit (PLRM stnd) integers. Since it's all 2's
>complement, I figured I could just sign-extend all the inputs, call the ps
>math op (`add`, `sub`), and then check the bits.

First, implement 'subtract' as 'complement and add'

Then:
*IF* bit {7 15} of the two operands are different you can't have a Carry.
If they're the same, do the addition, and if bit {7 15} of the result is
different from operands, overflow occurred

[luser.droog]

Awesome, thanks. So, I shouldn't be sign-extending everything willy-nilly,
right? Just treat them as unsigned values since they're all in the positive
range of a 32bit signed int? And by implementing subtract as you say, I
only have to do the carry nonsense once.

When you say 'overflow', you mean what I mean by 'carry', right? Cause I've
got a Carry Flag and an Overflow Flag, and for unsigned overflow, I've got
to XOR({7 15},{8 16}). unless I'm mistaken.

[Robert Bonomi]

In article <k9bbcb$l24$1...@dont-email.me>,

define what *you* mean by 'carry' and 'overflow' :)

from my _distant_ memories, overflow is set on mul/div -- you can't get
meaningful (even partial) results there.
'carry' is set for add/sub -- only one excess/'lost' bit is possible,
and you do multiple-precision is done by adding the 'carry' bit as a LSB
to the 'next more significant' chunk of th operand.

*dim* recollection of implementation details:
a) 'carry' set on =signed= result that carries into sign bit (only).
Or unsigned carry into next higher bit.
b) 'overflow' set if anything propagates -past- the carry position
c) 'overflow' set implies 'carry' set.

Aside -- beware of gotcha on 'complement and add'. can't complement a
'maximum negative' operand. If 1st operand not 'maximum negative', then
complement it, else if 2nd operand not 'maximum negative', then complement it,
else (both are 'maximum negative'), SHORTCUT: result is =zero=.

Trivia, For a number of years I used a (then supercomputer-class) machine
that "couldn't add" -- literal truth, it did addition by 'complement and
subtract'. at a high level, it was a wonderfully simple (read 'elegant')
design; the closer to the hardware you got, the _weirder_ it was. Weird,
but in a wonderful way. :)

[luser.droog]

Touché.

> from my _distant_ memories, overflow is set on mul/div -- you can't get
> meaningful (even partial) results there.
> 'carry' is set for add/sub -- only one excess/'lost' bit is possible,
> and you do multiple-precision is done by adding the 'carry' bit as a LSB
> to the 'next more significant' chunk of th operand.
>
> *dim* recollection of implementation details:
> a) 'carry' set on =signed= result that carries into sign bit (only).
> Or unsigned carry into next higher bit.
> b) 'overflow' set if anything propagates -past- the carry position
> c) 'overflow' set implies 'carry' set.
>
> Aside -- beware of gotcha on 'complement and add'. can't complement a
> 'maximum negative' operand. If 1st operand not 'maximum negative', then
> complement it, else if 2nd operand not 'maximum negative', then complement
> it, else (both are 'maximum negative'), SHORTCUT: result is =zero=.
>
> Trivia, For a number of years I used a (then supercomputer-class) machine
> that "couldn't add" -- literal truth, it did addition by 'complement and
> subtract'. at a high level, it was a wonderfully simple (read 'elegant')
> design; the closer to the hardware you got, the _weirder_ it was. Weird,
> but in a wonderful way. :)

Alright, following this led me to write

/SUB{D{exch}repeat {{negb ADDB}{negw ADDW}}W get exec}def

/ADDB{ 2 copy signb exch signb ne {
add /CF 0 def /OF 0 def
}{
dup signb 3 1 roll % signy x y
add
dup signb 3 2 roll % sum signsum signy
eq {
/CF 0 def
}{
/CF 1 def
} ifelse
dup 16#100 and 0 ne {
/OF 1 def
}{
/OF 0 def
} ifelse
} def

/ADDW { 2 copy 2{ -15 bitshift 1 and exch}repeat ne {
add /CF 0 def /OF 0 def
}{
dup -15 bitshift 1 and 3 1 roll
add dup -15 bitshift 3 2 roll eq {
/CF 0 def }{ /CF 1 def } ifelse
dup -16 bitshift 1 and /OF exch def
} def

And that just seems ugly and unmanageable.
So I went back to basics with

/adder { {c y x}{exch def}forall
x c and y c and x y and or or % Carry
dup 1 xor x y c and and or % Carry 1-Carry
x y c or or and % Carry Sum
} def

/addb { {b a}{exch def}forall
a 1 shiftmask b 1 shiftmask % a' a0 b' b0
exch 3 1 roll % a' b' a0 b0
0
8 { % a' b' a0 b0 c
adder % a' b' c s
4 1 roll % s0 a' b' c0
} repeat % s0 s1 s2 .. s7 c7
/CF exch def
7 { 1 bitshift or } repeat
} def

But that's just crazy, right?

So I peeked at the C solution and found:

33 void set_flag_add_byte( cpu_state_ptr cpu, uint8_t v1, uint8_t v2 )
34 {
35 uint16_t dst = (uint16_t)v1 + (uint16_t)v2;
36
37 set_psz_flags_byte( cpu, v1 + v2 );
38
39 cpu->flags.bit.CF = ( ( dst & 0xff00) != 0 );
40 cpu->flags.bit.OF = ( ( dst ^ v1 ) & ( dst ^ v2 ) & 0x80 ) != 0;
41 cpu->flags.bit.AF = ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0;
42 }
43
44 void set_flag_add_word( cpu_state_ptr cpu, uint16_t v1, uint16_t v2 )
45 {
46 uint32_t dst = (uint32_t)v1 + (uint32_t)v2;
47
48 set_psz_flags_word( cpu, v1 + v2 );
49
50 cpu->flags.bit.CF = ( ( dst & 0xffff0000 ) != 0 );
51 cpu->flags.bit.OF = ( ( ( dst ^ v1 ) & ( dst ^ v2 ) &
0x8000 ) != 0 );
52 cpu->flags.bit.AF = ( ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0 );
53 }
54
55 void set_flag_sub_byte( cpu_state_ptr cpu, uint8_t v1, uint8_t v2 )
56 {
57 uint16_t dst = (uint16_t)v1 - (uint16_t)v2;
58
59 set_psz_flags_byte(cpu, v1 - v2 );
60
61 cpu->flags.bit.CF = ( ( dst & 0xff00) != 0 );
62 cpu->flags.bit.OF = ( ( ( v1 ^ dst ) & ( v1 ^ v2 ) & 0x80 ) !=
0 );
63 cpu->flags.bit.AF = ( ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0 );
64 }
65
http://codegolf.stackexchange.com/a/6514/2381

Now that's something I can steal!

[Paul Vojta]

In article <JcCdnf5qr67SbCfN...@posted.nuvoxcommunications>,

Robert Bonomi <bon...@host122.r-bonomi.com> wrote:
>define what *you* mean by 'carry' and 'overflow' :)
>
>from my _distant_ memories, overflow is set on mul/div -- you can't get
>meaningful (even partial) results there.
>'carry' is set for add/sub -- only one excess/'lost' bit is possible,
>and you do multiple-precision is done by adding the 'carry' bit as a LSB
>to the 'next more significant' chunk of th operand.
>
>*dim* recollection of implementation details:
> a) 'carry' set on =signed= result that carries into sign bit (only).
> Or unsigned carry into next higher bit.
> b) 'overflow' set if anything propagates -past- the carry position
> c) 'overflow' set implies 'carry' set.

Dim, indeed.

On the 8086 family, arithmetic is two's complement, and there are no
separate "signed" or "unsigned" addition instructions.

Carry is set if the operation carries past the most significant bit.
(In other words, interpreting the bits as unsigned integers, carry for
16-bit addition is set if and only if the sum is >= 2^{16}. For 16-bit
subtraction a-b, carry is set if and only if b>a as unsigned quantities.)
This way, you can do addition of (say) 32-bit integers on a 16-bit machine
by doing a 16-bit add on the lowest significant word, and then a 16-bit ADC
(add with carry) on the corresponding higher-significant words.

Overflow is set if the operation leads to an overflow when considering the
operands as signed quantities. So, for addition, if you add two words with
the same sign bit and the sum has a different sign bit, then you get overflow;
otherwise you don't. For subtraction, it's a bit more complicated:
for a-b, if a>0, b<0, and the sign bit of the result is set, then you get
overflow; if a<0, b>0, and the sign bit of the result is not set, then you
get overflow; otherwise you don't.

Overflow does not imply carry set. For example, 0x4000+0x4000 gives 0x8000
with the overflow bit set but no carry bit.

>Aside -- beware of gotcha on 'complement and add'. can't complement a
>'maximum negative' operand. If 1st operand not 'maximum negative', then
>complement it, else if 2nd operand not 'maximum negative', then complement it,
>else (both are 'maximum negative'), SHORTCUT: result is =zero=.

Complement and add only works in one's complement arithmetic. For two's
complement (as in most modern processors, including the 8086), you need
to complement and increment to turn a (signed) word w into -w. That will
not simplify things if you are emulating a processor.

--Paul

[luser.droog]

Now that's a very nice explanation, thank you. Examples, reasoning.

>>Aside -- beware of gotcha on 'complement and add'. can't complement a
>>'maximum negative' operand. If 1st operand not 'maximum negative', then
>>complement it, else if 2nd operand not 'maximum negative', then complement
>>it, else (both are 'maximum negative'), SHORTCUT: result is =zero=.
>
> Complement and add only works in one's complement arithmetic. For two's
> complement (as in most modern processors, including the 8086), you need
> to complement and increment to turn a (signed) word w into -w. That will
> not simplify things if you are emulating a processor.
>
> --Paul

Actually this part seems irrelevant for me. I had already
interpreted "complement" as 2's-complement. And since ps integers are
32-bits, I can go ahead and negate the "maximum negative" 16-bit quantity.
Cause it still fits in 32bits!

Stealing from the C code led me to this set of procs for setting the flags.
And that part appears to run the test program. (But it's stuck in a loop
somewhere. So flags could still ba at issue. )

/setZF { dup 0 eq {/ZF 1 def}{/ZF 0 def} ifelse } def
/setSF { dup {-7 -15}W get bitshift 1 and /SF exch def } def
/setF { setZF setSF } def
/logF { setF /CF 0 def /OF 0 def } def %logical operators clear OF+CF

/nz1 { 0 ne{1}{0}ifelse } def %nonzero to 1
/arithF {
/CF c {16#ff00 16#ffff0000}W get and nz1 def
/OF c a xor c b xor and {16#80 16#8000}W get and nz1 def
/AF a b xor c xor 16#10 and nz1 def
} def
/ADD {
debug {()= pstack} if

{b a}{exch def}forall

/c a b add def
c arithF setF
} def
/SUB {
D 1 xor {exch}repeat

{b a}{exch def}forall

/c a b sub def
c arithF setF
} def
/SBB {
D 1 xor {exch}repeat

{b a}{exch def}forall

/c a b CF add sub def
c arithF setF
} def

[Steve]

Hi,

Here is a set of examples. Hope this makes some kind of sense.
It is in the form of an 8086 assembly program in DEBUG.

Regards,

Steve N.

PAGE ,132
TITLE Carry and Overflow Question.

CODE SEGMENT
ASSUME CS:CODE,DS:CODE
ORG 100H ; COM file opening
START:

COMMENT |

For the X86 architecture a carry is set when an unsigned number
operation exceeds the allowed size of the number. Unsigned 16-bit
numbers range from zero to 65,535. For a 16-bit number a carry will
be generated when two numbers added exceed 65,535. Or when subtracting
a larger number from a smaller number to generate a result that would
be smaller than zero. In school terms, adding 6 to 5 would generate a
1 and a carry into the tens column. Subtracting 6 from 5 would make a
9 and a borrow from the next larger column. Example; add 40,000 and
30,000. |

MOV AX,40000
MOV BX,30000
ADD AX,BX ; Add 30,000 to 40,000 and place result into AX.

NOP

COMMENT |

Show result in DEBUG.EXE.

D:\MASM\TEMP>debug carry.com
-u
1AF9:0100 B8409C MOV AX,9C40 ; 09C40H = 40,000
1AF9:0103 BB3075 MOV BX,7530 ; 07530H = 30,000
1AF9:0106 03C3 ADD AX,BX
-g 106 ; Go to ADD instruction.

AX=9C40 BX=7530 CX=0008 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=0106 NV UP EI PL NZ NA PO NC
1AF9:0106 03C3 ADD AX,BX
-t ; Execute ADD instruction.

AX=1170 BX=7530 CX=0008 DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=0108 NV UP EI PL NZ NA PO CY

Note that the result is 01170H (= 4,464), which is 70,000 MOD 65,536.
And the carry bit is set, indicating the result should be 011170H
(= 70,000), which does not fit into 16 bits.

On the 8086, an overflow is generated when a signed number operation
exceeds the allowed values of the register. Signed 16-bit numbers
range from -32,768, though zero, to +32,767. So if adding two positive
numbers exceed 32,767, an overflow happens. And if adding two negative
numbers makes a result less than -32,768, an overflow (underflow?) is
generated. Example; add 10,000 and 30,000.
|

MOV AX,10000
MOV BX,30000
ADD AX,BX ; Add 30,000 to 10,000 and place result into AX.

COMMENT |

1AF9:0109 B81027 MOV AX,2710 ; 02710H = 10,000
1AF9:010C BB3075 MOV BX,7530 ; 07530H = 30,000
1AF9:010F 03C3 ADD AX,BX
-g10f ; Go to ADD instruction.

AX=2710 BX=7530 CX=001A DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=010F NV UP EI PL NZ NA PO CY
1AF9:010F 03C3 ADD AX,BX
-t ; Execute ADD instruction.

AX=9C40 BX=7530 CX=001A DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=0111 OV UP EI NG NZ NA PO NC

The result is 09C40H which is -25,535, so an overflow occured.
No carry though as 40,000 is still a valid unsigned number.
|
MOV AX,10000
MOV BX,-30000
ADD AX,BX ; Add -30,000 to 10,000 and place result into AX.

COMMENT |

-g117 ; Go to ADD instruction.

AX=2710 BX=8AD0 CX=001A DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=0117 OV UP EI NG NZ NA PO NC
1AF9:0117 03C3 ADD AX,BX
-t ; Execute ADD instruction.

AX=B1E0 BX=8AD0 CX=001A DX=0000 SP=FFFE BP=0000 SI=0000 DI=0000
DS=1AF9 ES=1AF9 SS=1AF9 CS=1AF9 IP=0119 NV UP EI NG NZ NA PO NC

COMMENT |

Adding -30,000 to 10,000 (Signed) to get -20,000, or adding 35,536
to 10,000 (unsigned) to get 45,536 is valid so no carry or overflow
occurs.
|
NOP

CODE ENDS
END START