[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

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

2017-01-09 15:11

Rastah Bar
Account closed

Registered: Oct 2012
Posts: 336

Quote: Are you using the masking method?

These diagrams illustrate what I am thinking of

xxxxxxxx source0
xxxxxxxx source1
xxxxxxxx
xxxxxxxx
aabbccdd
aabbccdd
aabbccdd
aabbccdd source7

xxxxaaaa destination0
xxxxaaaa destination1
xxxxbbbb
xxxxbbbb
xxxxcccc
xxxxcccc
xxxxdddd
xxxxdddd destination7

The source bits in the block indicated by the a's should end up in the proper locations in destination bytes. Using look up tables the 8 a's are put into one byte such that the high nybble is the desired nybble of destination0 and then the low nybble that of destination1. The same procedure can be followed for all 4x2 source blocks 'b','c','d', etcetera.

Code for doing that can look like

ldy source4
lda mergingTable1,y  ;This table takes two bits and puts them in a byte, such that they are in the right positions to use as nybble for the destination.
ldx source5
ora mergingTable2,x
ldx source6
ora mergingTable3,x
ldx source7
ora mergingTable4,x  ;Now the byte is filled with all bits from block 'a'.

tax
and #$0f
sta destination0
lda moveHighNybbleToLowNybble,x
sta destination1
-------------------+
42 cycles.

This has to be repeated for blocks 'b', 'c', 'd' (using the right lookup tables), but since source4 was saved in Y, that code can start with TAY instead of 'LDY source4' to save 1 cycle.

The lower half of the source matrix is therefore moved in 42+3*41 = 165 cycles.

The other half of the matrix goes very similar, but since the destination bytes are no longer empty, we have to add 'ORA destination0' and 'ORA destination1' before the 'STA destination0' and 'STA destination1', respectively. So that will take 4*6 cycles extra, totalling 2*165+24=354 cycles. But the method is very memory inefficient.

2017-01-09 15:18

White Flame

Registered: Sep 2002
Posts: 136

Here's another idea which I think fails, but might be salvageable.

So the basic LSR, ROR accumulation grabs a bit and stores a bit, taking 2 instructions per bit. However, if done in-place just like many basic shift-add multiplication routines, ROR both sets a final bit as well as reads the next bit to place. This means that in dream land, the flip can be done in about 64 RORs. If fully in zp, that would be 320 cycles, but only 128 bytes of code with no tables.

However, the tactic I took doesn't seem to have a nice clean loop of RORs linking source bit locations to final bit locations. Various CMP #80s and other byte-masking & merging seems to be required, which would likely bloat it back up to 400+ cycles. But maybe by shuffling it around differently, an arrangement could be made that's both fast and short.

2017-01-09 15:26

Rudi
Account closed

Registered: May 2010
Posts: 125

ok, ok. another idea is to use TXS and TSX (takes only 2 cycles each) for having X as temporary variable in optimizing. might require the lookup to switch from ,x and ,y to ,y and ,x however. I don't mind having a 4k+ big table for making it really fast. 32k+ table however thats overkill!

2017-01-09 15:44

Rastah Bar
Account closed

Registered: Oct 2012
Posts: 336

Quote: ok, ok. another idea is to use TXS and TSX (takes only 2 cycles each) for having X as temporary variable in optimizing. might require the lookup to switch from ,x and ,y to ,y and ,x however. I don't mind having a 4k+ big table for making it really fast. 32k+ table however thats overkill!

I think my method needs 18 tables of 1 page = 4.5k. Using TXS/TSX will shave off 2 cycles in total.

2017-01-10 11:11

Rastah Bar
Account closed

Registered: Oct 2012
Posts: 336

Quoting Color Bar

This has to be repeated for blocks 'b', 'c', 'd' (using the right lookup tables), but since source4 was saved in Y, that code can start with TAY instead of 'LDY source4' to save 1 cycle.

I meant that the 'LDY source4' can be omitted. The TAY doesn't make sense and should be omitted, so the code takes 342 cycli.

I can gain another 6 cycli by saving X. If the code

tax
lda moveHighNybbleToLowNybble,x

is replaced by

sta selfmod:+1
selfmod:
lda moveHighNybbleToLowNybble

then source7 is kept in X and the code for block 'b' can start with fetching the bits of source7 from a table and omit the 'LDX source7'. One cycle is gained that way. In that block source6 must then be saved in X as shown above, and in the following block source5. The code for the last block can stay as it was in the original post. That saves 3 cycles for half the matrix and 6 in total, and the algorithm takes 336 cycles.

2017-01-10 12:04

Oswald

Registered: Apr 2002
Posts: 5094

still awful lot of cycles. it seems, whatever the goal is, it is faster to construct the bits into final orientation right away.

2017-01-10 13:38

enthusi

Registered: May 2004
Posts: 677

I could still image some top-view char based game where rotating in 'realtime' might actually make sense.
But you would certainly need some very special case when this is favorable over replacing chars from a lookup.

2017-01-10 18:17

Rudi
Account closed

Registered: May 2010
Posts: 125

Still got 299 cycles after merging the 4x4 and 2x2 (195 cycles) plus 1x1 (104 cycles). Can't get it any lower than that at the moment. Im trying to look at a different method.

Anyway; Im wondering if the checkerboard pattern (AND-masking) approach with the shifts can be minimized.. Or changed to a more effective method. If it turns out that the checkerboard pattern is the most optimal then there's no other way than trying to optimize the actual assembly code.

2017-01-10 18:59

Rastah Bar
Account closed

Registered: Oct 2012
Posts: 336

Pretty good. Below the magic 300 cycles barrier. :-)

2017-01-10 21:12

Copyfault

Registered: Dec 2001
Posts: 478

@Rudi: what do you mean with "merge 4x4 and 2x2"? I understand the 312-cycles version, though this is only valid if you stick to zp load/store. If you access absolute adresses (which will be necessary to read/write to charset data or bitmap resp.), this very same version ends up with 328 cycles -> identical to Axis' first routine.

By reordering the merges just like Axis pointed out this can be lowered to 328 - 12 = 316 (300 if you stick to zp load/store).

So how do you come down to 299 cycles???