Fix MSP430 SUB instruction carry bit logic

[hidde-jan]

When running angr alongside microcorruptions, I noticed the carry bit was not always set correctly on SUB, CMP and TST.

From wikipedia:

While the carry flag is well-defined for addition, there are two ways in common use to use the carry flag for subtraction operations.

The first uses the bit as a borrow flag, setting it if a<b when computing a−b, and a borrow must be performed. If a≥b, the bit is cleared. A subtract with borrow (SBB) instruction will compute a−b−C = a−(b+C), while a subtract without borrow (SUB) acts as if the borrow bit were clear. The 8080, Z80, 8051, x86[1] and 68k families (among others) use a borrow bit.

The second takes advantage of the identity that −x = not(x)+1 and computes a−b as a+not(b)+1. The carry flag is set according to this addition, and subtract with carry computes a+not(b)+C, while subtract without carry acts as if the carry bit were set. The result is that the carry bit is set if a≥b, and clear if a<b. The System/360,[2] 6502, MSP430, ARM and PowerPC processors use this convention.

It seems the current carry check is not correct.

[hidde-jan]

I'm not sure about SUBC. It might also have a wrong check. It might need to be changed to

dst >= (src + self.get_carry())

[hidde-jan]

I'm kinda confused. This is the behavior I saw in the microcorruptions emulator for SUBC:

sr = 0, r15 = 1
subc #0x1, r15
=> sr = 3 (C+Z), r15 = 0

And

sr = 1 (C), r15 = 1
subc #0x1, r15
=> sr = 1 (C), r15 = 1

And

sr = 1 (C), r15 = 0
subc #0x1, r15
=> sr = 2 (Z), r15 = 0

I'm not sure what the carry logic is here now.

[lockshaw]

I think that microcorruption's emulation of the subc instruction is wrong, so I'd stick to the docs. For example, take the following case:

r7 = 7
sr = 1

...
-> sub #0x2, r7
...

Microcorruption claims that the value of r7 afterward is 6.

However, if we look at the TI's documentation, subc is defined as (~src) + C + dst -> dst. This gives us (~2) + 1 + 7 = (-3) + 1 + 7 = 5.

[hidde-jan]

Yeah, I think you're right. I'm pretty sure about the change in this PR though, as it only touches SUB.

[lockshaw]

Though it does also appear that the two "equivalent" definitions in the docs don't match: (~src) + C + dst -> dst: (~2) + 1 + 7 = (-3) + 1 + 7 = 5 dst - (src - 1) + C -> dst: 7 - (2 - 1) + 1 = 7 - 1 + 1 = 7

[hidde-jan]

From http://www.ti.com/lit/ug/slau049f/slau049f.pdf:

dst + .NOT.src + C −> dst
or
(dst − src − 1 + C −> dst)

So it would be

7 - 2 - 1 + 1 = 7 - 3 + 1 = 5

[lockshaw]

Yeah, that difference only appears in the 5xx and 6xx family guide, so I think we can assume the second definition on that generation's docs is wrong

[lockshaw]

So we should be able to use the carry flag as dst >= src + 1 - c

[lockshaw]

If you agree, add that in to the PR and then I'll merge (and, if you feel up to it, fix the completely incorrect definition of subc's compute_results)

[hidde-jan]

I’ll do a quick check tomorrow. Off to bed now 😴

Op 3 mrt. 2019 om 21:45 heeft lockshaw notifications@github.com het volgende geschreven:

If you agree, add that in to the PR and then I'll merge

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

[hidde-jan]

I think I got it now. After getting 4 people confused over the language in the TI MSP430 guide, I've reimplemented SUB and SUBC as it actually works in the microcontroller (SUB is ADD with ~src+1 and SUBC is ADD with ~src+C).

The overflow is now relatively easy to check. For ADD(C) it's

pos + pos = neg
or 
neg + neg = pos

For SUB(C) it's

pos - neg = neg
or 
neg - pos = pos

This is consistent with the documentation. The carry bit is more difficult. In the docs, it consistently says it's implemented by performing the operation and then checking if there is a carry out from the Most Significant Bit.

Indeed, with the new implementation we have

r15 = 0xffff
sub #1, r15
=> r15 = 0xfffe, sr = 1 (C)
i.e.
    0xffff
+ ~0x0001
+  0x0001
----------
    0xffff
+  0xfffe
+  0x0001
----------
   0x1fffd
+  0x0001
----------
   0x1fffe
=> r15 = 0xfffe, sr = 1 (C)

You can also work this out for sub #0xffff, r15 and we still get a carry, which is consistent with the previous check dst >= src.

[hidde-jan]

Hold on, I think there's still a mistake somewhere.

[hidde-jan]

Another update. I saw that the IRSB got ~20% more steps/instruction due to all the casting and negating in the previous commit. I've now cleaned up ADD(C) and changed SUB(C). SUBC's carry logic needs a few casts to Type.int_17 since we can get an overflow. For instance:

r15 = 0, sr = 0
subc #0xffff, r15
----------------
  0x0000
- 0x0000
+ 0x0000
----------------
0x0000
=> r15 = 0, sr = 0

has no carry, but if we don't cast to int17, we get 0xffff + 0x1 - 0x0 = 0x0 =< 0x0 so the carry flag would have been set erroneously.

[hidde-jan]

Ok, I'm done. I'm sure the current behavior for the carry flag of SUBC is now correct. What I'm less sure about is if this behavior is equivalent to the previous behavior where we cast up to int17 and then do the >=.

I notice the new builds are failing due to flake warnings. Do you need me to clean some of those up before the merge?

[lockshaw]

Looks good! Just make those couple minor fixes and I'll merge it in.

[hidde-jan]

Ok, updated the PR