| |
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):
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 |
|
... 105 posts hidden. Click here to view all posts....
|
| |
Rastah Bar
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. |
| |
Rastah Bar
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5025 |
still awful lot of cycles. it seems, whatever the goal is, it is faster to construct the bits into final orientation right away. |
| |
enthusi
Registered: May 2004
Posts: 675 |
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. |
| |
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. |
| |
Rastah Bar
Registered: Oct 2012
Posts: 336 |
Pretty good. Below the magic 300 cycles barrier. :-) |
| |
Copyfault
Registered: Dec 2001
Posts: 466 |
@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??? |
| |
Rudi
Account closed
Registered: May 2010
Posts: 125 |
What I really meant was reordering merges, which I think Axis pointed on in one of his posts. Here I only managed to reorder the 2x2 rotation into 4x4 by removing some sta's and reusing the accumulator iirc. But unfortunately the code is so messy that I myself easily get tired after trying to optimize this. So, here comes a long list of code if you dont mind. I used tables for the shifts, and dot mind the eor-tag its the same as or. the next tag is the and value. Also used specific addresses in zp since this is just a test.
;-------------------------------
;4x4 & 2x2 rotation (195 cycles)
;-------------------------------
ldy $61
lax $65
and #$0f
eor shl4, y
sta $81
tya
and #$f0
eor shr4, x
sta $85
ldy $63
lda $67
and #$0f
eor shl4, y
ldy $81
tax
and #$33
eor shl2_eor_cc, y
sta $91
tya
and #$cc
eor shr2_eor_33, x
sta $93
lda $63
ldx $67
and #$f0
eor shr4, x
ldy $85
tax
and #$33
eor shl2_eor_cc, y
sta $95
tya
and #$cc
eor shr2_eor_33, x
sta $97
ldy $60
lax $64
and #$0f
eor shl4, y
sta $80
tya
and #$f0
eor shr4, x
sta $84
ldy $62
lax $66
and #$0f
eor shl4, y
ldy $80
and #$33
eor shl2_eor_cc, y
sta $90
tya
and #$cc
eor shr2_eor_33, x
sta $92
lda #$62
and #$f0
eor shr4, x
ldy $84
tax
and #$33
eor shl2_eor_cc, y
sta $94
tya
and #$cc
eor shr2_eor_33, x
sta $96
;-------------------------
;1x1 rotation (104 cycles)
;-------------------------
ldy $90
lax $91
and #$55
eor shl1_eor_aa, y
sta $70
tya
and #$aa
eor shr1_eor_55, x
sta $71
ldy $92
lax $93
and #$55
eor shl1_eor_aa, y
sta $72
tya
and #$aa
eor shr1_eor_55, x
sta $73
ldy $94
lax $95
and #$55
eor shl1_eor_aa, y
sta $74
tya
and #$aa
eor shr1_eor_55, x
sta $75
ldy $96
lax $97
and #$55
eor shl1_eor_aa, y
sta $76
tya
and #$aa
eor shr1_eor_55, x
sta $77 I wanted to make the 4x4vs2x2 rotator shorter by using other method, but havent found a solution for this yet (the 1x1 rotator also, for that matter, by optimizing those two distinct sections).
The character is at $60-$67 and the result is at $70-$77. |
| |
Copyfault
Registered: Dec 2001
Posts: 466 |
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... |
| |
Rastah Bar
Registered: Oct 2012
Posts: 336 |
I'm now at 326 cycli. |
| Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 - Next |
