How do I efficiently do signed comparisons on the

问题:

I want to compare two 16-bit numbers and branch on the result: the equivalent of if (a<b) goto negative. I'm using an Intel 8080.

The Z80 has a signed arithmetic overflow flag which can be used for this with some degree of effort. The standard code is:

ld de, _left
ld hl, _right
ld a, e
sub a, l
ld a, d
sbc a, h
jp po, $+5  ; branch on overflow flag not set
xor a, 0x80 ; flip sign bit
jm negative ; actually do the test

But the 8080 isn't a strict subset of the Z80, and the code above won't work there --- on the 8080, arithmetic instructions set the P flag based on the parity of the result, with hilarious results.

So what's the idiomatic way to do signed comparisons on the 8080?

Actually calculating the overflow flag is possible but really painful as it requires doing bit operations on both the operands and the result, and I'm running out of registers. Also, it's not actually what I want here; I don't actually care about the overflow. I just want to do the comparison.

(I can't simply subtract and branch if the result is negative because that doesn't work in all cases. Consider INT_MIN < INT_MAX. That's 0x8000 - 0x7fff = 1, which is obviously positive.)

回答1:

Considering the accepted answer and its comments, I would reconsider Jester's advice (which seems to me only +4B when compared to proposed Z80 code, but with somewhat different code layout, i.e. where less/greater_equal branches reside, which may further complicate or simplify your code ... plus it should perform better than doing xor 0x80 every time to both D and H):

    mov     a,d
    xra     h
    jp      sameSigns   ; as "JNS" in 8086 / "jp p," in Z80
    ; sign bits are different, signed overflow may happen
    ; but if H positive, then DE is less than HL
    xra     d           ; make A=H and set sign flag
    jm      DeIsGreaterEqualThanHl
:DeIsLessThanHl
    ; DE < HL
    ...

:sameSigns
    ; sign bits are equal, it is safe to do ordinary sub
    mov     a,e
    sub     l
    mov     a,d
    sbb     h
    jc      DeIsLessThanHl
:DeIsGreaterEqualThanHl
    ; DE >= HL
    ...

You can also modify it as procedure which returns CF=1 when DE<HL by doing:

:SignedCmpDeHl
    mov     a,d
    xra     h
    jp      sameSigns   ; as "JNS" in 8086 / "jp p," in Z80
    ; sign bits are different, signed overflow may happen
    ; but if H positive, then DE is less than HL
    xra     d           ; make A=H and set sign flag (CF=0)
    rm                  ; return CF=0 when DE >= HL (H is negative)
    stc
    ret                 ; return CF=1 when DE < HL (H is positive/zero)
:sameSigns
    ; sign bits are equal, it is safe to do ordinary sub
    mov     a,e
    sub     l
    mov     a,d
    sbb     h
    ret                 ; return with CF=1 when DE < HL (CF=0 DE >= HL)

BTW you can turn CF=0/1 into A=0/~0 by sbb a - sometimes that 0/255 is handy for further calculations...

But as I commented under question, many time this is worth of revisit on architectural level, to see if the whole code logic can't be turned into unsigned 0..FFFF mode of operation, maybe it would lead to adjusting (by -32768) values like "_left" just at one/two specific spots (like final output to user), while many more other internal comparisons/usages would work in unsigned way.

EDIT:

Some variants for compares against constants (for one-time constant it's probably better (size-wise) to just load it into other RP and use the generic RP1 vs RP2 compare, especially if you have spare RP and the generic compare is already instantiated for other code ... but for multiple uses of the same constant this will probably win both size-wise and speed-wise ... inlining wins speed-wise? May get on par with subroutine, depends how the result is used).

reg-pair (actually also any 8b reg) against zero:

; signed compare 8b or 16b register vs 0, into SF, destroys A
    xra     a       ; A=0
    ora     R       ; 16b R=[HDB], or any 8b R: SF = (RP < 0 or R < 0)
    ...i.e. "jm hlIsLessThanZero"

; signed compare 8b or 16b register vs 0, into CF, destroys A
    mov     a,R     ; 16b R=[HDB], or any 8b R
    ral             ; CF = (RP < 0) or (R < 0)
    ...i.e. "jc hlIsLessThanZero" or "sbb a" to get 0/255

reg-pair against any 16b #XY constant:

; signed 16b compare RP (HL/DE/BC) vs nonzero constant #XY
; subroutine, returns CF=1 if RP < #XY, modifies A
    mov     a,R
    xri     0x80    ; convert 8000..7FFF into 0000..FFFF
    cpi     #X^0x80 ; "X" is xor-ed with 0x80 too to have it in 0000..FFFF range
    rnz             ; if ZF=0, then CF=1 is (RP < XY) and CF=0 is (RP > XY)
    ; R == X, the low 8b P vs Y will decide
    mov     a,P
    cpi     #Y      ; CF=1 if (RP < XY)
    ret             ; 10B for particular #XY constant and RP

; inlined form
    mov     a,R
    xri     0x80    ; convert 8000..7FFF into 0000..FFFF
    cpi     #X^0x80 ; "X" is xor-ed with 0x80 too to have it in 0000..FFFF range
    jnz     HiByteWasDecisive   ; if ZF=0, then CF is set correctly, done
    mov     a,P     ; R == #X, the low 8b P vs #Y will decide final CF
    cpi     #Y      ; CF=1 if (RP < #XY)
:HiByteWasDecisive
    ; CF=1 is (RP < #XY) and CF=0 is (RP >= #XY)
    ...

回答2:

On the 8085 there are two undocumented flags K and V for signed comparison and signed overflow, along with undocumented instructions JK/JNK for jumping on signed less than/larger than

• What undocumented 8085 instructions is Steven Morse referring to in "In The Beginning"?
• What is the purpose of the reserved/undefined bit in the flag register?

Not sure whether they're available on 8080 or not. But if they don't you can convert a signed comparison to an unsigned one and vice versa by toggling the top bit

bool signedCmp(int a, int b)
{
    return unsignedCmp(a ^ INT_MIN, b ^ INT_MIN);
}

I don't know 8080 assembly but maybe something like this can be used to compare DE and HL

mov a, e
sub a, l     ; e - l
mov a, h
xri a, 0x80
mov h, a     ; h ^= 0x80
mov a, d
xri a, 0x80  ; a = d ^ 0x80
sbb a, h     ; d - h
jc lessthan  ; branch on carry
    ; >= case
:lessthan
    ; < case