By: Michael S (already5chosen.delete@this.yahoo.com), February 28, 2013 4:58 am

Room: Moderated Discussions

EduardoS (no.delete@this.spam.com) on February 27, 2013 11:07 pm wrote:

> Michael S (already5chosen.delete@this.yahoo.com) on February 27, 2013 4:24 pm wrote:

> > I say 12 rather than 14, because I don't think that negative/non-negative

> > conditions are really fundamental.

>

> The sign flag helps some times and is essentially free.

>

> > Now, do we really need 4 flag bits in order to implement 12 (or even all 14) fundamental

> > conditions? No, we don't. Up to 64 conditions, including all 14 defined in x86/ARM?SPARC,

> > can be easyly derived from just 7 distinct states = 3 bits.

> > For example, like those:

> > 0 - unsigned_less && signed_less. Implied non-overflow && negative

> > 1 - unsigned_less && signed_greater && non-overflow. Implied non-negative

> > 2 - unsigned_less && signed_greater && overflow. Implied negative

> > 3 - unsigned_greater && signed_less && non-overflow. Implied negative

> > 4 - unsigned_greater && signed_less && overflow. Implied non-negative

> > 5 - unsigned_greater && signed_greater. Implied non-overflow && non-negative

> > 6 - equal. Implied non-overflow && non-negative

>

> Encoding in three bits have the same "advantage" of killing the sign flag

I don't get what you're saying. Sign-of-result information is fully preserved in 3-bit encoding. Using encoding from my table above, SF = (0 || 2 || 3).

> at the expense

> of more complex (and time consuming) flag calculation, but the sign flag is free, so no

> real gain, also... 3 bitsT allow up to 8 resulting states, but there are 9, no?

>

You are right.

I was concerned only with sub/cmp and didn't pay attention to all combinations that can be generated by two-complement addition.

Specifically, my 7 states can not represent two additional zeros - ZF=1,CF=1,OF=0 and ZF=1,CF=1,OF=1. And there is only one 3-bit combination left so, without special measure, it's impossible to distinguish between the two states with just 3 bits.

One possible solution is definition of two separate addition instruction that behave identically except when faced with pair of 0x8000_0000 inputs in which case:

signed_add variant correctly detects carry and overflow, but leaves equivalent of ZF set;

unsigned_add variant correctly detects carry and ZF, but leaves equivalent of OF clear.

Then all 'C' compilers will happily ignore signed_add. All compiler for integer-overflow-paranoid languages will use signed_add when appropriated, being fully aware of the fact that ZF is not reliable after that. Anyway, ZF is most useful after sub/cmp, HLL compilers (unlike human coders) almost never exploit it after addition.

So, lets revisit my table:

0 - Z=0,S=1,C=0,B=1,O=0: unsigned_less && signed_less. Implied non-overflow && negative

1 - Z=0,S=0,C=0,B=1,O=0: unsigned_less && signed_greater && non-overflow. Implied non-negative

2 - Z=0,S=1,C=0,B=1,O=1: unsigned_less && signed_greater && overflow. Implied negative

3 - Z=0,S=1,C=1,B=0,O=0: unsigned_greater && signed_less && non-overflow. Implied negative

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

5 - Z=0,S=0,C=1,B=0,O=0: unsigned_greater && signed_greater. Implied non-overflow && non-negative

6 - Z=1,S=0,C=0,B=0,O=0: equal. Implied non-overflow && non-negative

7 - Z=1,S=0,C=1,B=0,O=0: equal with carry && non-overflow. Implied non-negative

Plus:

As result of signed_add:

4 - Z=x,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

As result of unsigned_add:

7 - Z=x,S=0,C=1,B=0,O=x: unsigned_greater && signed_less && overflow. Implied non-negative

So, let's look at your addition cases:

# 1

> mov eax, 1

> add eax, 1

>

> Non-Zero, Non-Negative, Non-Carry, Non-Overflow

1 - Z=0,S=0,C=0,B=1,O=0: unsigned_less && signed_greater && non-overflow. Implied non-negative

# 2

>

> mov eax, 0

> add eax, 0

>

> Zero, Non-Negative, Non-Carry, Non-Overflow

6 - Z=1,S=0,C=0,B=0,O=0: equal. Implied non-overflow && non-negative

# 3

> mov eax, -1

> add eax, 2

>

> Non-Zero, Non-Negative, Carry, Non-Overflow

5 - Z=0,S=0,C=1,B=0,O=0: unsigned_greater && signed_greater. Implied non-overflow && non-negative

# 4

>

> mov eax, -1

> add eax, 1

>

> Zero, Non-Negative, Carry, Non-Overflow

7 - Z=1,S=0,C=1,B=x,O=0: equal with carry. Implied overflow && non-negative

# 5

>

> mov eax, 80000000h

> add eax, 80000000h

>

> Zero, Non-Negative, Carry, Overflow

After unsigned_add:

7 - Z=1,S=0,C=1,B=x,O=0: equal with carry. Implied overflow && non-negative

After signed_add:

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

# 6

>

> mov eax, 80000001h

> add eax, 80000000h

>

> Non-Zero, Non-Negative, Carry, Overflow

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

#7

> mov eax, -2

> add eax, 1

>

> Non-Zero, Negative, Non-Carry, Non-Overflow

>

0 - Z=0,S=1,C=0,B=1,O=0: unsigned_less && signed_less. Implied non-overflow && negative

#8

> mov eax, 70000000h

> add eax, 70000000h

>

> Non-Zero, Negative, Non-Carry, Overflow

>

2 - Z=0,S=1,C=0,B=1,O=1: unsigned_less && signed_greater && overflow. Implied negative

#9

> mov eax, -1

> add eax, -1

>

> Non-Zero, Negative, Carry, Non-Overflow

>

3 - Z=0,S=1,C=1,B=0,O=0: unsigned_greater && signed_less && non-overflow. Implied negative

> Michael S (already5chosen.delete@this.yahoo.com) on February 27, 2013 4:24 pm wrote:

> > I say 12 rather than 14, because I don't think that negative/non-negative

> > conditions are really fundamental.

>

> The sign flag helps some times and is essentially free.

>

> > Now, do we really need 4 flag bits in order to implement 12 (or even all 14) fundamental

> > conditions? No, we don't. Up to 64 conditions, including all 14 defined in x86/ARM?SPARC,

> > can be easyly derived from just 7 distinct states = 3 bits.

> > For example, like those:

> > 0 - unsigned_less && signed_less. Implied non-overflow && negative

> > 1 - unsigned_less && signed_greater && non-overflow. Implied non-negative

> > 2 - unsigned_less && signed_greater && overflow. Implied negative

> > 3 - unsigned_greater && signed_less && non-overflow. Implied negative

> > 4 - unsigned_greater && signed_less && overflow. Implied non-negative

> > 5 - unsigned_greater && signed_greater. Implied non-overflow && non-negative

> > 6 - equal. Implied non-overflow && non-negative

>

> Encoding in three bits have the same "advantage" of killing the sign flag

I don't get what you're saying. Sign-of-result information is fully preserved in 3-bit encoding. Using encoding from my table above, SF = (0 || 2 || 3).

> at the expense

> of more complex (and time consuming) flag calculation, but the sign flag is free, so no

> real gain, also... 3 bitsT allow up to 8 resulting states, but there are 9, no?

>

You are right.

I was concerned only with sub/cmp and didn't pay attention to all combinations that can be generated by two-complement addition.

Specifically, my 7 states can not represent two additional zeros - ZF=1,CF=1,OF=0 and ZF=1,CF=1,OF=1. And there is only one 3-bit combination left so, without special measure, it's impossible to distinguish between the two states with just 3 bits.

One possible solution is definition of two separate addition instruction that behave identically except when faced with pair of 0x8000_0000 inputs in which case:

signed_add variant correctly detects carry and overflow, but leaves equivalent of ZF set;

unsigned_add variant correctly detects carry and ZF, but leaves equivalent of OF clear.

Then all 'C' compilers will happily ignore signed_add. All compiler for integer-overflow-paranoid languages will use signed_add when appropriated, being fully aware of the fact that ZF is not reliable after that. Anyway, ZF is most useful after sub/cmp, HLL compilers (unlike human coders) almost never exploit it after addition.

So, lets revisit my table:

0 - Z=0,S=1,C=0,B=1,O=0: unsigned_less && signed_less. Implied non-overflow && negative

1 - Z=0,S=0,C=0,B=1,O=0: unsigned_less && signed_greater && non-overflow. Implied non-negative

2 - Z=0,S=1,C=0,B=1,O=1: unsigned_less && signed_greater && overflow. Implied negative

3 - Z=0,S=1,C=1,B=0,O=0: unsigned_greater && signed_less && non-overflow. Implied negative

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

5 - Z=0,S=0,C=1,B=0,O=0: unsigned_greater && signed_greater. Implied non-overflow && non-negative

6 - Z=1,S=0,C=0,B=0,O=0: equal. Implied non-overflow && non-negative

7 - Z=1,S=0,C=1,B=0,O=0: equal with carry && non-overflow. Implied non-negative

Plus:

As result of signed_add:

4 - Z=x,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

As result of unsigned_add:

7 - Z=x,S=0,C=1,B=0,O=x: unsigned_greater && signed_less && overflow. Implied non-negative

So, let's look at your addition cases:

# 1

> mov eax, 1

> add eax, 1

>

> Non-Zero, Non-Negative, Non-Carry, Non-Overflow

1 - Z=0,S=0,C=0,B=1,O=0: unsigned_less && signed_greater && non-overflow. Implied non-negative

# 2

>

> mov eax, 0

> add eax, 0

>

> Zero, Non-Negative, Non-Carry, Non-Overflow

6 - Z=1,S=0,C=0,B=0,O=0: equal. Implied non-overflow && non-negative

# 3

> mov eax, -1

> add eax, 2

>

> Non-Zero, Non-Negative, Carry, Non-Overflow

5 - Z=0,S=0,C=1,B=0,O=0: unsigned_greater && signed_greater. Implied non-overflow && non-negative

# 4

>

> mov eax, -1

> add eax, 1

>

> Zero, Non-Negative, Carry, Non-Overflow

7 - Z=1,S=0,C=1,B=x,O=0: equal with carry. Implied overflow && non-negative

# 5

>

> mov eax, 80000000h

> add eax, 80000000h

>

> Zero, Non-Negative, Carry, Overflow

After unsigned_add:

7 - Z=1,S=0,C=1,B=x,O=0: equal with carry. Implied overflow && non-negative

After signed_add:

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

# 6

>

> mov eax, 80000001h

> add eax, 80000000h

>

> Non-Zero, Non-Negative, Carry, Overflow

4 - Z=0,S=0,C=1,B=0,O=1: unsigned_greater && signed_less && overflow. Implied non-negative

#7

> mov eax, -2

> add eax, 1

>

> Non-Zero, Negative, Non-Carry, Non-Overflow

>

0 - Z=0,S=1,C=0,B=1,O=0: unsigned_less && signed_less. Implied non-overflow && negative

#8

> mov eax, 70000000h

> add eax, 70000000h

>

> Non-Zero, Negative, Non-Carry, Overflow

>

2 - Z=0,S=1,C=0,B=1,O=1: unsigned_less && signed_greater && overflow. Implied negative

#9

> mov eax, -1

> add eax, -1

>

> Non-Zero, Negative, Carry, Non-Overflow

>

3 - Z=0,S=1,C=1,B=0,O=0: unsigned_greater && signed_less && non-overflow. Implied negative