[CSDb] - User Forums - Fast way to rotate a char?

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Fast way to rotate a char?

2017-01-04 08:32

Rudi
Account closed

Registered: May 2010
Posts: 125

Fast way to rotate a char?

Im not talking about rol or ror, but swap bits so that they are rotated 90 degrees:

Example:

a char (and the bits can be random):

10110010 byte 1..
11010110 byte 2.. etc..
00111001
01010110
11011010
10110101
00110011
10110100

after "rotation" (rows and columns are swapped):

is it possible to use lookup tables for this or would that lookup table be too big?
or other lookuptable for getting and setting bits?

-Rudi

2017-01-04 08:59

Oswald

Registered: Apr 2002
Posts: 5094

my first idea:

lsr row7
ror a
lsr row6
ror a
...
ror row0
ror a
sta result_row7

then again:

lsr row7
ror a
...
lsr row0
ror a
sta result_row6

etc.

2017-01-04 09:06

Axis/Oxyron
Account closed

Registered: Apr 2007
Posts: 91

Depends on resolution. In multicolor/2x2 you can do it with 4 bit-tables, just like you would do a 2xn chunky-FX. In hires things get complicated. The shift/rol method is a good starting point. Perhaps the Amiga C2P techniques based on merges would be faster. Not sure, yet.

2017-01-04 09:07

ChristopherJam

Registered: Aug 2004
Posts: 1409

Sounds like a coding challenge!

Should be doable with 64 tables and 464 cycles, with neither source nor destination in zero page. But that's a lot of RAM.. Oswald's concept's a lot saner. Maybe fastest routine in under 4k code+tables would be interesting to hunt for?

    ldx byte0
    ldy byte1
    for j in range(8)
        lda t{j}0,x
        ora t{j}1,y
        sta $xxxx


    ldx byte2
    ldy byte3
    for j in range(8)
        lda#$xx
        ora t{j}2,x
        ora t{j}3,y
        sta $xxxx


    ldx byte4
    ldy byte5
    for j in range(8)
        lda#$xx
        ora t{j}4,x
        ora t{j}5,y
        sta $xxxx


    ldx byte6
    ldy byte7
    for j in range(8)
        lda#$xx
        ora t{j}6,x
        ora t{j}7,y
        sta $xxxx

(table ij copies a bit from location i to location j, clearing the rest)

2017-01-04 09:26

Rudi
Account closed

Registered: May 2010
Posts: 125

Interesting ideas. I think I understand Oswalds code.
Quoting ChristopherJam

Sounds like a coding challenge!

Feel free to make it a coding challenge.

2017-01-04 09:51

ChristopherJam

Registered: Aug 2004
Posts: 1409

Haha, googling C2P leads back to csdb (Identify this doughnut).

Looks like Michiel's swapping-two-address-bits-at-a-time technique at http://stackoverflow.com/questions/1667591/rotating-a-bitmap-90.. ?

Going to have to think about efficient ways to swap low nybble of one byte with high nybble of another now..

2017-01-04 09:51

Axis/Oxyron
Account closed

Registered: Apr 2007
Posts: 91

Challenge accepted. ;o)

2017-01-04 10:13

Shadow
Account closed

Registered: Apr 2002
Posts: 355

Is it just my spatial thinking that is a bit off now, or is your original example wrong? To me it doesn't seem like a correct 90 degree rotation is done, it looks like it's mirrored as well?

2017-01-04 11:12

Axis/Oxyron
Account closed

Registered: Apr 2007
Posts: 91

Got a first version running using Amiga style merges (328 cycles). Code still looks ugly and unoptimized.

The used tables are 256 bytes each and filled as follows:

lsrtab1: and #$aa, lsr
lsrtab2: and #$cc, lsr, lsr
lsrtab4: lsr, lsr, lsr, lsr
asltab1: and #$55, asl
asltab2: and #$33, asl, asl
asltab4: asl, asl, asl, asl

Code is using Dreamass-style macros.
src & dst are memory locations of the source and dest char.
tmp1 & tmp2 are 8 byte zp-arrays each.

;28 cycles mem->zp
;26 cycles zp->zp
;28 cycles zp->mem
#macro MERGE(src1, src2, mask1, mask2, bittab1, bittab2, dst1, dst2)
{
lax {src1}
ldy {src2}
and #{mask1}
ora {bittab1},y
sta {dst1}
tya
and #{mask2}
ora {bittab2},x
sta {dst2}
}

.MERGE(src+0, src+1, $aa, $55, lsrtab1, asltab1, tmp1+0, tmp1+1)
.MERGE(src+2, src+3, $aa, $55, lsrtab1, asltab1, tmp1+2, tmp1+3)
.MERGE(src+4, src+5, $aa, $55, lsrtab1, asltab1, tmp1+4, tmp1+5)
.MERGE(src+6, src+7, $aa, $55, lsrtab1, asltab1, tmp1+6, tmp1+7)
.MERGE(tmp1+0, tmp1+2, $cc, $33, lsrtab2, asltab2, tmp2+0, tmp2+2)
.MERGE(tmp1+1, tmp1+3, $cc, $33, lsrtab2, asltab2, tmp2+1, tmp2+3)
.MERGE(tmp1+4, tmp1+6, $cc, $33, lsrtab2, asltab2, tmp2+4, tmp2+6)
.MERGE(tmp1+5, tmp1+7, $cc, $33, lsrtab2, asltab2, tmp2+5, tmp2+7)
.MERGE(tmp2+0, tmp2+4, $f0, $0f, lsrtab4, asltab4, dst+0, dst+4)
.MERGE(tmp2+1, tmp2+5, $f0, $0f, lsrtab4, asltab4, dst+1, dst+5)
.MERGE(tmp2+2, tmp2+6, $f0, $0f, lsrtab4, asltab4, dst+2, dst+6)
.MERGE(tmp2+3, tmp2+7, $f0, $0f, lsrtab4, asltab4, dst+3, dst+7)

The code still looks pretty unoptimized. I think reordering merges can save some loads/stores to the tmp-arrays. Also SAX or AXS could come handy here.

If you are interested in the basic concept of this kind of C2p read here: http://www.lysator.liu.se/~mikaelk/doc/c2ptut/

2017-01-04 12:24

Axis/Oxyron
Account closed

Registered: Apr 2007
Posts: 91

Damn, should have asked Graham. He used nearly exactly my C2P code in the hidden-part of Deus Ex Machina.

2017-01-04 12:27

ChristopherJam

Registered: Aug 2004
Posts: 1409

Sweet. I thought I had an approach that would take ~360 cycles, but it appears I've made a mistake somewhere, so it's both slower than yours *and* broken..

(was going to do a three skews rotation, with ROL tables for the first and third passes, and swap macros for shuffling bits down in the middle pass)

I'll ponder more after dinner.

... 105 posts hidden. Click here to view all posts....