 
Rudi
Registered: May 2010 Posts: 100 
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.... 
 
Skate
Registered: Jul 2003 Posts: 470 
Table lookup doesn't necessarily be faster than bit shifting. What i was saying is even using large tables to get rid of bit shifting doesn't save cycles unless you start thinking out of the box. 
 
Skate
Registered: Jul 2003 Posts: 470 
here is an algo which looks similar to c2p method without 8 bit restrictions.
void transpose8(unsigned char A[8], int m, int n,
unsigned char B[8]) {
unsigned x, y, t;
// Load the array and pack it into x and y.
x = (A[0]<<24)  (A[m]<<16)  (A[2*m]<<8)  A[3*m];
y = (A[4*m]<<24)  (A[5*m]<<16)  (A[6*m]<<8)  A[7*m];
t = (x ^ (x >> 7)) & 0x00AA00AA; x = x ^ t ^ (t << 7);
t = (y ^ (y >> 7)) & 0x00AA00AA; y = y ^ t ^ (t << 7);
t = (x ^ (x >>14)) & 0x0000CCCC; x = x ^ t ^ (t <<14);
t = (y ^ (y >>14)) & 0x0000CCCC; y = y ^ t ^ (t <<14);
t = (x & 0xF0F0F0F0)  ((y >> 4) & 0x0F0F0F0F);
y = ((x << 4) & 0xF0F0F0F0)  (y & 0x0F0F0F0F);
x = t;
B[0]=x>>24; B[n]=x>>16; B[2*n]=x>>8; B[3*n]=x;
B[4*n]=y>>24; B[5*n]=y>>16; B[6*n]=y>>8; B[7*n]=y;
}

 
HCL
Registered: Feb 2003 Posts: 668 
Ah, that's just beautiful Axis!!
..as usual, i'm the last one to read the thread.. but if anyone still wonders what that code does, it is mirroring the 8x8matrix by starting with 2x2bitblocks, then 4x4blocks, then finally the whole 8x8block. Mirroring and rotation is of course just a matter of configuring the macros :).
..and of course Graham did this 15+ years ago, hope that makes you all feel as retard as i do ;). 
 
Pex Mahoney Tufvesson
Registered: Sep 2003 Posts: 34 
I used Rudi's 472cycle approach "This takes ~472 cycles, and is basically similar to Oswalds approach" in Storebror
There was no need to make it any faster, since it was a onetime calculation just before the android starts rotating. My routine included not only rotation, but mirroring across horizontal, vertical and diagonals as well.
And HCL... I'm even later than you are. So don't worry, you're ok! ;)

Have a noise night!
http://mahoney.c64.org 
 
CreaMD
Registered: Dec 2001 Posts: 2496 
I wonder if this would significantly speed up my proportional routine and help me "posthumously" win the internal compo I had with Wotnau ;)
So which one is the fastest? I need to rotate full line of bitmap 320 bytes char by char, +90 degrees each 
 
dano
Registered: Jul 2004 Posts: 130 
Haha, did my a proportial Routine for NewsPress back then the same way as CreaMD did. Switched to a standard one some time later as this was even faster. Guess i did the rotation the Oswaldway too back then. 
 
Oswald
Registered: Apr 2002 Posts: 4196 
don think you can beat a bitshifter with this c2p, couple hundred cycles even with axis method, while bitshifter worst case is about 170 (lsr a ror zp * 8 lines * 3 times) 
 
Rudi
Registered: May 2010 Posts: 100 
Im trying to figure my head around this:
Since the rotation is just a bunch of bitswaps. For example swapping bit 0 and 7, bit 1 and 15, 2 and 23 etc.00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
etc..
56 57 58 59 60 61 62 63. How would a swapbittable look for this? The number of swaps are only 32. only 32 lda's and sta's? lets say ~8 cycles in total per swap: 8*32 = 256 cycles for all the swaps. but still I dont know if its possible to have a table for this..
Edit: hm, woops. i think perhaps 32 is wrong, since both locations need to be written to, so maybe two sta's instead of just one. 
 
Cruzer
Registered: Dec 2001 Posts: 947 
Oswald: Why 3 times and not 8? 
 
Oswald
Registered: Apr 2002 Posts: 4196 
Quote: Oswald: Why 3 times and not 8?
coz you rotate in 2 buffers a,b:
a b
a b
a b
but if shifting is bigger than 3 you can just shift bits to opposite dir and then swap a,b (on screen). 3 is just a wild guess maybe 4 is the max, it was a long time ago. 
Previous  1  2  3  4  5  6  7  8  9  10  11  12  Next 