Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in 
CSDb User Forums


Forums > C64 Coding > Fast way to rotate a char?
2017-01-04 09:32
Rudi

Registered: May 2010
Posts: 86
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):
11001101
01011000
10100111
11111111
00101000
01010101
11011010
00100110
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
 
... 99 posts hidden. Click here to view all posts....
 
2017-01-10 22:43
Copyfault

Registered: Dec 2001
Posts: 195
I have to admit that the approach with those "Amiga-style"-merges is really outstanding. Hardly possible to force oneself to think different approaches...

Ok, at least I tried ;) One idea I had is to use the CMP-instruction to read out the bits of every byte. E.g.
ldx #$7f
cpx byte0
rol
cpx byte1
rol
cpx byte2
rol
cpx byte3
rol
cpx byte4
rol
cpx byte5
rol
cpx byte6
rol
cpx byte7
rol
eor #$ff
sta dest0

but this already sums up to 47cycle (if sticking to zp lda/sta/cpx). Furthermore, this will only work for dest0 unless one masks out bit7-bit1 step by step -> every byte needed 8 times, too many table lookups -> most probably not feasible :/


Another idea would be to store the char bit patterns along the diagonal. Usually we have
byte0: b7 b6 b5 b4 b3 b2 b1 b0
byte1: b7 b6 b5 b4 b3 b2 b1 b0
byte2: b7 b6 b5 b4 b3 b2 b1 b0
byte3: b7 b6 b5 b4 b3 b2 b1 b0
byte4: b7 b6 b5 b4 b3 b2 b1 b0
byte5: b7 b6 b5 b4 b3 b2 b1 b0
byte6: b7 b6 b5 b4 b3 b2 b1 b0
byte7: b7 b6 b5 b4 b3 b2 b1 b0

Now we could store the same information as e.g.
data0: byte0.b0 X X X X X X X
data1: byte0.b1 byte1.b0 X X X X X X
...
data7: byte0.b7 byte1.b6 byte2.b5 byte3.b4 byte4.b3 byte5.b2 byte6.b1 byte7.b0
...
dataE: byte7.b7 X X X X X X X

The huge advantage of such a data structure is obvious: mirroring the bitpatterns is equivalent to reversing the order of the dataX-bytes. Drawback: in order to display the corresponding bitpattern a conversion routine is _always_ needed (no matter if the "original" bitpattern should be displayed or the "mirrored" pattern). I couldn't come up with a decent routine to compensate for this.

Maybe someone can take the good points out of these thoughts...
2017-01-11 11:39
Color Bar

Registered: Oct 2012
Posts: 100
I'm now at 326 cycli.
2017-01-11 14:52
Rudi

Registered: May 2010
Posts: 86
Looking at the 4x4 rotation an recipe that I have made look like this:
1. rol 4 times higher 4 bytes.
2. swap lower nybbles of byte0->byte4, byte1->byte5 etc.
3. rol 4 times lower 4 bytes.
Done.

1 and 3 can be done with lookuptables. 2 is a more tricky.
So, what no.2 need is a fast way to swap lo-nybbles of two bytes, but it seems to be difficult. One would have to do that in 14 cycles or so. Impossible.

Someone gave me this xor-swap algorithm which takes 27 cycles:
LDA byte1
AND #$0f
EOR byte2
STA byte2
AND #$0f
EOR byte1
STA byte1
AND #$0f
EOR byte2
STA byte2
I also made this, but it takes one cycle more than the former:
LDX byte1
LDY byte2
LDA lowCleared,x
ORA andTab,y
STA byte1
LDA lowCleared,y
ORA andTab,x
STA byte2
I guess this wont help at all. Because 27*4 = 108 cycles. Allready reached the limit from the 312 version where each rotator-section take 104 cycles.
2017-01-11 15:24
Color Bar

Registered: Oct 2012
Posts: 100
Quoting Rudi
Someone gave me this xor-swap algorithm which takes 27 cycles:
LDA byte1
AND #$0f
EOR byte2
STA byte2
AND #$0f
EOR byte1
STA byte1
AND #$0f
EOR byte2
STA byte2

26 cycles:
lax byte1
and #$f0
ldy byte2
ora grabLowNybble,y  ;This table performs AND #$0f
sta byte1  ;Now low nybble of byte2 is in byte1
tya
and #$f0
ora grabLowNybble,x  ;byte1 was kept in X
sta byte2
2017-01-11 15:43
Oswald

Registered: Apr 2002
Posts: 4010
you just need a 64k table

lda byte1byte2
sta result

:)
2017-01-11 15:52
Rudi

Registered: May 2010
Posts: 86
Colorbar: nice
Oswald: hah yeah, like thats gonna happen. :P
2017-01-11 17:52
Color Bar

Registered: Oct 2012
Posts: 100
Flip disk ...
Rotate monitor clockwise ...
2017-01-11 19:45
Oswald

Registered: Apr 2002
Posts: 4010
del.
2017-01-11 19:55
Color Bar

Registered: Oct 2012
Posts: 100
Quote: Flip disk ...
Rotate monitor clockwise ...


Girls They Want to Have Fun
2017-01-12 10:31
Color Bar

Registered: Oct 2012
Posts: 100
Quoting Rudi

2. swap lower nybbles of byte0->byte4, byte1->byte5 etc.

That helped. If all bits from block 'a' in my post above are put entirely in destination0, and the bits of the 4x2 block above that in destination1, nybbles have to be swapped at the end, but the code
sta selfmod:+1
and #$0f
sta destination0
selfmod:
lda moveHighNybbleToLowNybble,x
sta destination1

simplifies to just 'STA destination' and with this I can reduce the cycle count to 312, I think.
Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Urban Space Cowboy
GeoAnas
OEP
Guests online: 24
Top Demos
1 Uncensored  (9.7)
2 The Shores of Reflec..  (9.7)
3 Edge of Disgrace  (9.7)
4 Coma Light 13  (9.6)
5 Lunatico  (9.6)
6 Comaland 100%  (9.6)
7 Incoherent Nightmare  (9.5)
8 Wonderland XII  (9.5)
9 Comaland  (9.5)
10 Neon  (9.5)
Top onefile Demos
1 Dawnfall V1.1  (9.5)
2 Daah, Those Acid Pil..  (9.4)
3 Treu Love [reu]  (9.4)
4 Dawnfall  (9.3)
5 Tunnel Vision  (9.3)
6 One-Der  (9.2)
7 Goatbeard  (9.2)
8 Globe 2016 [reu]  (9.2)
9 Hardware Accelerated..  (9.2)
10 Safe VSP  (9.1)
Top Groups
1 Booze Design  (9.4)
2 Oxyron  (9.4)
3 Censor Design  (9.4)
4 Crest  (9.3)
5 SHAPE  (9.2)
Top Diskmag Editors
1 Jazzcat  (9.5)
2 Peter  (9.4)
3 Newscopy  (9.4)
4 Remix  (9.3)
5 Tadpole  (9.3)

Home - Disclaimer
Copyright © No Name 2001-2017
Page generated in: 0.205 sec.