6502.org Forum Projects Code Documents Tools Forum
It is currently Fri Apr 19, 2024 10:12 am

View unanswered posts | View active topics


Board index » 6502.org Users Forum » Programming

All times are UTC




Post new topic Reply to topic  Page 1 of 1
  [ 14 posts ] 
  Previous topic | Next topic 
Author Message
BigEd
PostPosted: Sun Sep 22, 2019 11:32 am 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
It's well-known how to do multi-byte add and subtract, using carry. But how about multi-byte compare?

Here's the challenge: short and sweet code to compare two pairs of bytes (lets say in zero page) setting the Z, C and V flags appropriately. As it's a compare, rather than a subtract, you need not to modify the inputs - you might need a little zero page working space.

As a bonus challenge, the same for four-byte values.

(Inspired by a query over on anycpu)
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Sun Sep 22, 2019 3:43 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8138
Location: Midwestern USA
Code:
        rep #%00100000         ; 16 bit accummulator
        lda value1
        cmp value2

:D

P.S. You didn't say which processor. :D

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Sun Sep 22, 2019 4:34 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1922
Location: Sacramento, CA, USA
Since Ed requested the V flag, I'm assuming he wants a signed compare, not the unsigned one you just posted.

... which brings up a question for Ed. Z V and N are needed for a full-featured signed comparison (without pre-biasing the inputs), while an unsigned comparison only requires C and Z. Why are you asking for C Z and V?

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)


Last edited by barrym95838 on Sun Sep 22, 2019 4:53 pm, edited 4 times in total.

Top
 Profile  
Reply with quote  
BigEd
PostPosted: Sun Sep 22, 2019 4:37 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
Anyone with the luxury of a machine which can handle 16 bits in one go is welcome to tackle the extended four-byte challenge...

My gut feel is that C and V are fairly easy and Z needs just a little fiddling.

As a tangent, it seems interesting to me that subtraction is best handled LSB first, but comparison could - perhaps - be a little better handled MSB first.
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Sun Sep 22, 2019 4:43 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1922
Location: Sacramento, CA, USA
Oops! You posted while I was editing my previous post, Ed. Could you please re-read my edited post and help me understand you better?

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
BigEd
PostPosted: Sun Sep 22, 2019 4:55 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
Ah, yes. Good point: for signed or unsigned comparison routines we need only two of the three flags. For a single instruction that serves both purposes we'd have to produce all three. So I suppose I'm looking for a dual-purpose routine (or macro) which can be used for either case. Does that make sense? Or rather, do I now give the appearance of understanding my own challenge?

Edit: scratch that. There are four flags. Let me come in again...


Last edited by BigEd on Sun Sep 22, 2019 5:02 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
BigEd
PostPosted: Sun Sep 22, 2019 4:57 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
... so, there are four flags: C, N, V, and Z. And an eight-bit compare on an eight-bit micro will sensibly affect all of them, and so be useful for both signed and unsigned comparisons. Is that right?

So a reasonable challenge might be to write a multi-byte version, which also delivers four flags, and is therefore fit for all likely purposes.
Top
 Profile  
Reply with quote  
Chromatix
PostPosted: Sun Sep 22, 2019 8:33 pm 
Offline

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462
For unsigned compares, the following is sufficient:
Code:
UCMP2:
  LDA a+1
  CMP b+1
  BNE :+
  LDA a+0
  CMP b+0
: RTS
This is trivial to extend to any number of bytes, and indeed the extra parts of such routines could be prepended to this one, or a generalised version implemented by preloading X and looping.

However, when signed integers get involved, the MSB comparison can still be used directly if the two are unequal, but the lower bytes' comparisons may need fettling of the resulting flags to match expectations. Things get even more complicated if one integer is signed and the other unsigned, as there are then MSB cases where the value of either integer may force the comparison result; this is something that C punts on as "undefined behaviour", but we should want to do better.

As it happens, CMP doesn't affect V; that is only set by ADC, SBC and BIT. And in fact it doesn't perform a correct signed comparison even on single bytes. For that, you must use SBC:
Code:
SCMP2:
   SEC
   LDA a+0
   SBC b+0
   LDA a+1
   SBC b+1
   RTS
This clobbers A, but so does using CMP.


Last edited by Chromatix on Sun Sep 22, 2019 10:33 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
BigEd
PostPosted: Sun Sep 22, 2019 8:35 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
Chromatix wrote:
As it happens, CMP doesn't affect V ... in fact it doesn't perform a correct signed comparison even on single bytes.

Oh! I feel as if I should have known that.
Top
 Profile  
Reply with quote  
Chromatix
PostPosted: Sun Sep 22, 2019 10:32 pm 
Offline

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462
Extending the problem to 4-byte integers, covering the mixed-signedness case, and optimising the signed case slightly:
Code:
MCMP4: ; a is unsigned, b is signed
  LDA a+3
  ORA b+3
  BPL UCMP4 ; if both values are in compatible unsigned range, compare them accordingly
  LSR A  ; either a is above b's range, or b is below a's range
  SEC    ; so enforce an "a greater than b" flag result
  RTS

UCMP4:
  LDA a+3
  CMP b+3
  BNE :+
  LDA a+2
  CMP b+2
  BNE :+
  LDA a+1
  CMP b+1
  BNE :+
  LDA a+0
  CMP b+0
: RTS

SCMP4:
  LDA a+0
  CMP b+0
  LDA a+1
  SBC b+1
  LDA a+2
  SBC b+2
  LDA a+3
  SBC b+3
  RTS
Top
 Profile  
Reply with quote  
BitWise
PostPosted: Mon Sep 23, 2019 8:20 am 
Offline
User avatar

Joined: Tue Mar 02, 2004 8:55 am
Posts: 996
Location: Berkshire, UK
How about adding an ORA/STA so you can detect zero? Something like:
Code:
SEC
LDA A+0 ; Subtract bytes LS to MS
SBC B+0
STA TEMP ; Save difference
LDA A+1
SBC B+1
ORA TEMP
STA TEMP
LDA A+2
SBC A+2
ORA TEMP
STA TEMP
LDA A+3
SBC A+3
BVC *+6 ; Overflowed?
EOR #$80 ; Yes, correct sign of result
ORA #1 ; And result can not be zero
ORA TEMP ; Set Z for all bytes
RTS

If A and B are unsigned numbers then test the Z and C flags. For signed numbers use Z and N

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs
Top
 Profile  
Reply with quote  
Chromatix
PostPosted: Mon Sep 23, 2019 10:46 am 
Offline

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462
Hmm, thinking about it, I do need to extend the signed version a bit to ensure the result flags also reflect the less-significant bytes if the MSB of the difference turns out to be zero. In this case a must either be equal to or slightly larger than b. Revised code below:
Code:
MCMP4: ; a is unsigned, b is signed
  LDA a+3
  ORA b+3
  BPL UCMP4 ; if both values are in compatible unsigned range, compare them accordingly
  LSR A  ; either a is above b's range, or b is below a's range
  SEC    ; so enforce an "a greater than b" flag result
  RTS

MCMP2: ; a is unsigned, b is signed
  LDA a+1
  ORA b+1
  BPL UCMP2 ; if both values are in compatible unsigned range, compare them accordingly
  LSR A  ; either a is above b's range, or b is below a's range
  SEC    ; so enforce an "a greater than b" flag result
  RTS

UCMP4:
  LDA a+3
  CMP b+3
  BNE OUT    ; only need to check less significant bytes if MSBs are equal
  LDA a+2
  CMP b+2
  BNE OUT
UCMP2:
  LDA a+1
  CMP b+1
  BNE OUT
  LDA a+0
  CMP b+0
OUT:
  RTS

SCMP4:
  PHX
  TSX
  LDA a+0
  CMP b+0
  PHP
  LDA a+1
  SBC b+1
  PHP
  LDA a+2
  SBC b+2
  PHP
  LDA a+3
  SBC b+3
  BNE OUT2  ; if MSB of difference is zero, retrieve next most significant byte's flags
  PLP
  CLV  ; V flag only valid in MSB, clear it otherwise
  BNE OUT2
  PLP
  CLV
  BNE OUT2
  PLP
  CLV
OUT2:
  TXS
  PLX
  RTS
Perhaps not the fastest of code, but it should work accurately.
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Mon Sep 23, 2019 3:22 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1922
Location: Sacramento, CA, USA
Bruce has an excellent write-up which seems to cover the subject here, but I haven't had a chance to read it in detail.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
BigEd
PostPosted: Mon Sep 23, 2019 4:26 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10789
Location: England
Ah, so he has - and who better to do it! Well spotted. I should probably have searched.
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 14 posts ] 

Board index » 6502.org Users Forum » Programming

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
6502.org is an ongoing project by Mike Naberezny and contributors.