2-byte signed comparision

Question

I'm working on comparing 2-byte signed integers and I feel like I'm on the right track, but I must be missing something. I've rewritten the same algorithm from scratch a few different times and all of them get close but don't work for all the cases I'm testing. Here's my latest version:

MATH_lt_int: ; a < b, a: MATH_INT_INPUT_1, b: MATH_INT_INPUT_2
  jsr MATH_clear_int_output ; I use too many subroutines, sorry.
  lda MATH_INT_INPUT_1 + 1
  eor MATH_INT_INPUT_2 + 1
  bmi @different_sign ; eor our high bytes and check
                      ; the neg flag to see if they differ
  lda MATH_INT_INPUT_1 + 1 ; if one is positive here, they both must be
  bpl @both_positive
@both_negative: ; we have to do an inverted comparison here
                ; because if a < b then -b < -a
  sec
  lda MATH_INT_INPUT_1 + 1 ; check high byte first
  cmp MATH_INT_INPUT_2 + 1
  bcc @not_less_than ; inverted because negative
  sec
  lda MATH_INT_INPUT_1 ; low byte next
  cmp MATH_INT_INPUT_2
  ; the problem seems to be somewhere around here
  bcc @not_less_than ; inverted because negative
  beq @not_less_than
  jmp @less_than ; inverted because negative
@both_positive: ; we get to do a straight-up comparison here
  sec
  lda MATH_INT_INPUT_1 + 1 ; check high byte first
  cmp MATH_INT_INPUT_2 + 1
  bcc @less_than
  sec
  lda MATH_INT_INPUT_1 ; low byte next
  cmp MATH_INT_INPUT_2
  bcc @less_than
  jmp @not_less_than
@different_sign: ; if they have different signs, the negative one is smaller
  lda MATH_INT_INPUT_1 + 1
  bmi @less_than ; are we the negative one? Than we're @less_than
  jmp @not_less_than
@less_than:
  lda #1
  jmp @return
@not_less_than:
  lda #0
@return:
  sta MATH_INT_OUTPUT
  ; return
  rts

Test results:

50<50==0   => 0
50<60==1   => 1
60<50==0   => 0
-50<-60==0 => 1
-60<-50==1 => 1

So I'm currently missing it in the case where a>b and a and b are negative. That should be a 0 but it is a 1. So specifically, something must be wrong about what I'm doing in and around the second line containing bcc @not_less_than within the @both_negative section, but I can't see what's wrong with it.

Update Thanks to @penguin359 I was able to shorten the code to this with the same level of functionality, but unfortunately it still doesn't correctly handle negative numbers:

MATH_lt_int: ; a < b, a: MATH_INT_INPUT_1, b: MATH_INT_INPUT_2
  jsr MATH_clear_int_output ; I use too many subroutines, sorry.
  sec
  lda MATH_INT_INPUT_1 + 1 ; check high byte first
  cmp MATH_INT_INPUT_2 + 1
  bmi @less_than
  sec
  lda MATH_INT_INPUT_1 ; low byte next
  cmp MATH_INT_INPUT_2
  bmi @less_than
  jmp @not_less_than
@less_than:
  lda #1
  jmp @return
@not_less_than:
  lda #0
@return:
  sta MATH_INT_OUTPUT
  ; return
  rts

Test results:

50<50==0   => 0
50<60==1   => 1
60<50==0   => 0
-50<-60==0 => 0
-60<-50==1 => 0

Answer 1

You need to use the compare instructions for signed integers for the high-byte. bcc and friends is for branched compares on unsigned integers. bmi is the signed version of it.

http://6502.org/tutorials/compare_instructions.html

For the high-byte, you just stick to the bpl, bmi, and beq branch instructions, then it will compare signed integers as expected. There's no need to worry about handling negative numbers differently. If the high-byte proves equal, then you need to compare the low-byte, but in this case, you want the unsigned version of the instructions as there's no sign bit to deal with.

Think about some simple, easy example. Let's compare 1 and 2 stored in 16-bit words. The high bytes will both be 0x00 and equal, but the low bytes will be 0x01 and 0x02. An unsigned compare says that the latter is greater. Let's push it to the extreme case of this and compare 0 with 255. The high-byte is still 0x00 in both cases, but the low bytes are now 0x00 and 0xff. Obviously, a signed compare here would consider the latter lower and representing -1, but an unsigned compare will say it's greater. If we push it to 256, well, the high bytes are no longer equal and the signed compare there works as before.

Now, let's look at negatives and compare -1 (0xffff) and -2 (0xfffe). Well, the high bytes are equal, but the low bytes are 0xff and 0xfe with -1 being greater as it should be in unsigned world. Comparing it with -256 (0xff00) and -255 (0xff01), 0x00 is less than 0x01, as well as less than 0xfe and 0xff for the -2 and -1 case. Only the high byte needs a signed comparison.

Answer 2

In the same sign case, just do a 16 bit subtraction and check the result sign.

MATH_lt_int: ; a < b, a: MATH_INT_INPUT_1, b: MATH_INT_INPUT_2
  jsr MATH_clear_int_output ; I use too many subroutines, sorry.
  lda MATH_INT_INPUT_1 + 1
  eor MATH_INT_INPUT_2 + 1
  bmi @different_sign ; eor our high bytes and check
                  ; the neg flag to see if they differ
  sec
  lda MATH_INT_INPUT_1 ; check low byte first
  sbc MATH_INT_INPUT_2
  lda MATH_INT_INPUT_1 + 1 ; check high byte next
  sbc MATH_INT_INPUT_2 + 1
  bpl @not_less_than
  jmp @less_than
@different_sign: ; if they have different signs, the negative one is smaller
  lda MATH_INT_INPUT_1 + 1
  bpl @not_less_than
@less_than:
  lda #1
  jmp @return
@not_less_than:
  lda #0
@return:
  sta MATH_INT_OUTPUT
  ; return
  rts

A branchless version that basically emulates 17 bit sign extension could look like:

MATH_lt_int: ; a < b, a: MATH_INT_INPUT_1, b: MATH_INT_INPUT_2
  jsr MATH_clear_int_output ; I use too many subroutines, sorry.
  sec
  lda MATH_INT_INPUT_1 ; check low byte first
  sbc MATH_INT_INPUT_2
  lda MATH_INT_INPUT_1 + 1 ; check high byte next
  sbc MATH_INT_INPUT_2 + 1
  ror ; bring carry back into MSB as 17th bit
  eor #$80 ; carry reversed during subtraction
  eor MATH_INT_INPUT_1 + 1 ; reuse MSB emulating sign extension
  eor MATH_INT_INPUT_2 + 1 ; and perform the 1 bit subtraction
  rol ; bring sign bit into carry
  rol ; then LSB
  and #1
  sta MATH_INT_OUTPUT
  rts

Answer 3

Comparing signed numbers by looking only at the resulting sign is completely incorrect. Just look at the attempt to subtract +127 from -128, where the result should be -255 but since it does not fit in 8 bit, you get only +1 and a wrong sign.

More advanced CPUs like 68000 have special branch instructions, that is bgt/bge/blt/ble that correctly report whether the result of addition or subtraction, reflected in flags, was actually positive or negative. This is done in hardware by looking at "overflow XOR sign" combination of flags, so you can implement the similar strategy purely in software.

However, there is a simpler way: just invert higher (sign) bits of your numbers and compare them afterwards as unsigned quantities. You'll get the correct result for the former signed values. This works because such higher bit inversion moves signed -128..+127 interval to unsigned 0..+255 one.

Answer 4

Look this article:

Beyond 8-bit Unsigned Comparisons by Bruce Clark

http://6502.org/tutorials/compare_beyond.html

"The 6502 has several options available for comparing numbers. Each option, naturally, has its pros and cons in terms of speed and size. There are also some infrequently used options that occasionally come in handy. Finally, and unfortunately, some misconceptions abound about signed (twos complement) numbers and the correct way to compare them. All of these topics will be covered below."

Look on section 5 "SIGNED COMPARISONS"