6502.org • View topic - Identity table, yay or nay?

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Identity table, yay or nay?

Page 1 of 3

[ 31 posts ]

Go to page 1, 2, 3 Next

Previous topic | Next topic

Author

Message

BillG

Post subject: Identity table, yay or nay?

Posted: Sun Aug 16, 2020 8:11 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

Many of you have written more 6502 code than me.

Do you use an identity table much or at all?

http://wiki.nesdev.com/w/index.php/Identity_table

An identity table is a page of memory initialized with values from 0 to FF. It is useful for synthesizing instructions such as:

* transfer from X to Y: ldy Indentity,X

* compare A with X: cmp Identity,X

I recently thought I was going to get to use it for the very first time in code to add two signed single-byte variables sign extended to a 16-bit result, but I ran out of registers.

Code:

    ldx     A_
    txa
    ora     #$7F
    bmi     2f
    lda #0
2:  tay

    lda     B_
    ora     #$7F
    bmi     3f
    lda     #0
3:  sta     Temp

    txa
    clc
    adc     B_
    tax

    tya
    adc     Temp

Now I think I can do something like this:

Code:

    lda     A_
    clc
    adc     B_
    tax

    ldy     #0
    bit     A_
    bpl     2f

    dey

2:
    lda     #0
    bit     B_
    bpl     3f

    lda     #$FF

3:
    adc     Indentity,Y

So is an identity table really worth having to avoid using a temporary variable?

Top

BigEd

Post subject: Re: Identity table, yay or nay?

Posted: Sun Aug 16, 2020 8:16 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10938
Location: England

(Never used one, personally. Looks like a classic tradeoff of space against time, and I've never needed those synthesised actions. It's certainly clever, and lookup tables, especially page-sized ones, are an idea I find very attractive.)

Top

GARTHWILSON

Post subject: Re: Identity table, yay or nay?

Posted: Sun Aug 16, 2020 9:42 pm

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8510
Location: Southern California

I haven't used it myself, but I put it in the article on self-modifying code at http://wilsonminesco.com/SelfModCode/, even though it's not really SMC, just another trick to synthesize instructions that are not natively on the '02.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Sun Aug 16, 2020 9:44 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

I decided to run this code through the assembler to see what it looked like:

Code:

 0000                     00001 Temp     rmb    1
 0001                     00002 A_       rmb    1
 0002                     00003 B_       rmb    1
                          00004
 0200                     00005          org    $200
 0200                     00006 Identity
                          00007
 0300                     00008          org    $300
                          00009
 0300 A6 01           [3] 00010          ldx    A_
 0302 8A              [2] 00011          txa
 0303 09 7F           [2] 00012          ora    #$7F
 0305 30 02 (0309)  [2/3] 00013          bmi    2f
 0307 A9 00           [2] 00014          lda    #0
 0309                     00015 2:
 0309 A8              [2] 00016          tay
 030A A5 02           [3] 00017          lda    B_
 030C 09 7F           [2] 00018          ora    #$7F
 030E 30 02 (0312)  [2/3] 00019          bmi    3f
 0310 A9 00           [2] 00020          lda    #0
 0312                     00021 3:
 0312 85 00           [3] 00022          sta    Temp
 0314 8A              [2] 00023          txa
 0315 18              [2] 00024          clc
 0316 65 02           [3] 00025          adc    B_
 0318 AA              [2] 00026          tax
 0319 98              [2] 00027          tya
 031A 65 00           [3] 00028          adc    Temp
                          00029
                          00030
 031C A5 01           [3] 00031          lda    A_
 031E 18              [2] 00032          clc
 031F 65 02           [3] 00033          adc    B_
 0321 AA              [2] 00034          tax
                          00035
 0322 A0 00           [2] 00036          ldy    #0
 0324 24 01           [3] 00037          bit    A_
 0326 10 01 (0329)  [2/3] 00038          bpl    2f
 0328 88              [2] 00039          dey
 0329                     00040 2:
 0329 A9 00           [2] 00041          lda    #0
 032B 24 02           [3] 00042          bit    B_
 032D 10 02 (0331)  [2/3] 00043          bpl    3f
 032F A9 FF           [2] 00044          lda    #$FF
 0331                     00045 3:
 0331 79 0200       [4/5] 00046          adc    Identity,Y

After a bit more guru meditation (nap), I came up with this:

Code:

 0334 A5 01           [3] 00049          lda    A_
 0336 18              [2] 00050          clc
 0337 65 02           [3] 00051          adc    B_
 0339 AA              [2] 00052          tax
                          00053
 033A A0 00           [2] 00054          ldy    #0
 033C 24 01           [3] 00055          bit    A_
 033E 10 01 (0341)  [2/3] 00056          bpl    2f
 0340 88              [2] 00057          dey
 0341                     00058 2:
 0341 24 02           [3] 00059          bit    B_
 0343 10 01 (0346)  [2/3] 00060          bpl    3f
 0345 88              [2] 00061          dey
 0346                     00062 3:
 0346 98              [2] 00063          tya
 0347 69 00           [2] 00064          adc    #0

Top

commodorejohn

Post subject: Re: Identity table, yay or nay?

Posted: Sun Aug 16, 2020 10:15 pm

Joined: Thu Jan 21, 2016 7:33 pm
Posts: 275
Location: Placerville, CA

Yeah, I've never had occasion to need it, but it's a useful trick to have in the toolbox.

Top

barrym95838

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 3:22 pm

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1948
Location: Sacramento, CA, USA

That was a productive nap! :-)

_________________
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

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:00 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

Surprisingly, some of my best work has been while napping, showering, eating, driving, etc.

If any of you ever have the misfortune to hire me and catch me napping at the computer, please be assured that I am still working, just conserving CPU cycles while doing a complex analysis as a background task...

I may still need that identity table as subtraction is not totally commutative.

There are two popular ways to negate a number:

* subtract it from zero
* invert and increment

Did you know that you can also

* decrement then invert?

You can subtract the contents of Y from A by

Code:

    sec
    lda     Value
    sbc     Indentity,Y

or you can do this:

Code:

    dey
    tya
    eor     #$FF
    clc
    adc     Value

One more byte and two cycles, but you save the 256 bytes of the table.

Top

BigEd

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:03 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10938
Location: England

Is it the case that you can omit the DEY if you change the CLC to SEC?

Top

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:08 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

BigEd wrote:

Is it the case that you can omit the DEY if you change the CLC to SEC?

Yes you can. I need another nap...

Top

floobydust

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:15 pm

Joined: Tue Mar 05, 2013 4:31 am
Posts: 1382

I also don't use an identity table... when your entire addressable range is 64KB, it seems like a lot to dedicate to what might be quite limited in usage. I'm sure there's always some exceptions for some purely embedded applications that are very specific.

I do use some lookup tables for certain things... like the disassembler that's in my Monitor code. But I generally prefer to have efficient routines to handle most calculations. I even have a 39-byte routine that calculates CRC-16 for a 128-byte Xmodem block. This certainly saves a huge amount of space versus using a couple 256-byte tables plus more code to access the tables, etc.

I do wake up with some better ideas once in a while... :wink:

_________________
Regards, KM
https://github.com/floobydust

Top

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:19 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

floobydust wrote:

If you cannot tell, I am still trying to justify making an identity table an included feature in FLEX. Every time I think I need it, I find a way around it.

Top

floobydust

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:23 pm

Joined: Tue Mar 05, 2013 4:31 am
Posts: 1382

BillG wrote:

floobydust wrote:

If you cannot tell, I am still trying to justify making an identity table an included feature in FLEX. Every time I think I need it, I find a way around it.

I thought so... I've spent years optimizing the BIOS and Monitor for my C02 Pocket SBC... still, Mike B manages to come up with a smaller and sometimes faster routine for what I have. Needless to say, I use his and add a comment in the source thanking him for another clever piece of code!

_________________
Regards, KM
https://github.com/floobydust

Top

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Mon Aug 17, 2020 8:36 pm

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

Actual code from my BASIC compiler...

Code:

 0C36 A9 00           [2] 00346          lda    #>1
 0C38 6D 1C25         [4] 00347          adc    I_+1
 0C3B 70 12 (0C4F)  [2/3] 00348          bvs    T00007
 0C3D A8              [2] 00349          tay
                          00350
 0C3E E0 FF           [2] 00351          cpx    #<32767   ; Thanks Mark B!
 0C40 D0 05 (0C47)  [2/3] 00352          bne    3f
 0C42 49 7F           [2] 00353          eor    #>32767
 0C44 F0 0C (0C52)  [2/3] 00354          beq    T00008
 0C46 98              [2] 00355          tya
                          00356
 0C47                     00357 3:
 0C47 E9 7F           [2] 00358          sbc    #>32767
 0C49 50 02 (0C4D)  [2/3] 00359          bvc    2f
 0C4B 49 80           [2] 00360          eor    #$80

Edit: Oops! I need to change that to Mike...

Top

GARTHWILSON

Post subject: Re: Identity table, yay or nay?

Posted: Tue Aug 18, 2020 2:01 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8510
Location: Southern California

floobydust wrote:

You might have a page or more available in ROM though, so you might as well use it for that rather than letting that space go unused.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BillG

Post subject: Re: Identity table, yay or nay?

Posted: Tue Aug 18, 2020 3:50 am

Joined: Thu Mar 12, 2020 10:04 pm
Posts: 702
Location: North Tejas

The identity table is back in play and I do not see an alternative except for storing a value in a temporary variable. The time spent is the same and the code is one byte larger.

Code:

                          00178 ; 00020     W := S + (W + W);
 0BB5 18              [2] 00179          clc
 0BB6 AD 11E9         [4] 00180          lda    W_
 0BB9 6D 11E9         [4] 00181          adc    W_
 0BBC AA              [2] 00182          tax
 0BBD AD 11EA         [4] 00183          lda    W_+1
 0BC0 6D 11EA         [4] 00184          adc    W_+1
 0BC3 18              [2] 00185          clc
 0BC4 A8              [2] 00186          tay
 0BC5 8A              [2] 00187          txa
 0BC6 6D 11E8         [4] 00188          adc    S_
 0BC9 AA              [2] 00189          tax
 0BCA AD 11E8         [4] 00190          lda    S_
 0BCD 09 7F           [2] 00191          ora    #$7F
 0BCF 30 02 (0BD3)  [2/3] 00192          bmi    2f
 0BD1 A9 00           [2] 00193          lda    #0
 0BD3                     00194 2:
 0BD3 79 D000       [4/5] 00195          adc    Identity,Y
 0BD6 8E 11E9         [4] 00196          stx    W_
 0BD9 8D 11EA         [4] 00197          sta    W_+1

Top

Page 1 of 3

[ 31 posts ]

Go to page 1, 2, 3 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 23 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