# Algorithm to rotate data

Hi all,

I am trying to rotate font data by 90 degrees and I'm hitting a brick wall... it should be simple but I'm just not getting it.

Here's what I want to do (scaled to 4 bits by 4 bits for clarity):

original

A B C D
E F G H
I J K L
M N O P

after rotation

M I E A
N J F B
O K G C
P L H D

Of course, I want to do it with an 8 x 8 font pattern, but above shows the idea.

Any help will be appreciated. Thanks!

-- Roger

One approach would be the following:

1. Map each ring into a line starting at the top left and working clockwise. So:
A B C D
E F G H
I J K L
M N O P
Becomes:
outer ring: ABCDHLPONMIE. Ring size = 4
inner ring: FGKJ. Ring size = 2

2. move the last 'ring size - 1' characters to the beginning of a new array
ABCDHLPON MIE //extract the last 3 as ring size = 4
-> MIE //new array

FGK J //extract the last 1 as ring size = 2
-> J //new array

1. concatenate the rest:
MIE ABCDHLPON
J FGK

2. shift each line back into a ring (inverse of step 1)
M I E A
N J F B
O K G C
P L H D

As for realising it in code, the difficult bit is going to be extracting each ring. But it is doable. If you design a function to extract a ring of a specified size, then you could call that same function for each of the rings in turn, and it could be scaled up to 8x8 easily that way. It would be also sensible to have the function be able to do the inverse to put the lines back into the ring which would be the same code as extracting them only moving flipping destination and source.
I'll write a few lines of code as a possible hint.

Something like this should work:

``````for (uint8_t i = 0; i < 4; i++)
for (uint8_t j = 0; j < 4; j++)
array_rotated[i][j] = array[3-j][i];
``````

Or, for a single dimension array:

``````for (uint8_t i = 0; i < 4; i++)
for (uint8_t j = 0; j < 4; j++)
array_rotated[(i*4)+j] = array[((3-j)*4)+i];
``````

Here’s an approach I might take:

``````char d[4][4]= {
{'A','B','C','D'},
{'E','F','G','H'},
{'I','J','K','L'},
{'M','N','O','P'}
};

typedef char (*accessfn)(int x, int y);

char normal( int x, int y){ return d[x][y]; }
char rotated( int x, int y){ return d[3-y][x]; }   // <<<<<< This is the main thing

void printMatrix( accessfn afn ){
for (int x=0;x<4;x++)
Serial << afn(x,0) << " " << afn(x,1) << " " << afn(x,2) << " " << afn(x,3) << " " << endl;
Serial << endl;
}

void setup(){
Serial << "Hello World!!!" << endl;
printMatrix(normal);
printMatrix(rotated);

Serial << "Or..." << endl;
accessfn rotationmode;

rotationmode = normal;
printMatrix(rotationmode);
rotationmode = rotated;
printMatrix(rotationmode);
}
``````

After a little bit of playing around with how coordinates map, it is really rather simple:

``````void setup() {
// put your setup code here, to run once:
const char maxSize = 4; //must be a multiple of 2, e.g. 2,4,6,8
char array[maxSize][maxSize] = {{'A','B','C','D'},{'E','F','G','H'},{'I','J','K','L'},{'M','N','O','P'}};
char rotatedArray[maxSize][maxSize];
/*
//rotate 90* anti-clockwise
for (char i = 0; i < maxSize; i++){
for (char j = 0; j < maxSize; j++){
char newI = maxSize-1-j;
char newJ = i;
rotatedArray[newI][newJ] = array[i][j];
}
}
*/
//rotate 90* clockwise
for (char i = 0; i < maxSize; i++){
for (char j = 0; j < maxSize; j++){
char newI = j;
char newJ = maxSize-1-i;
rotatedArray[newI][newJ] = array[i][j];
}
}

//It should now be reversed.
Serial.begin(115200);
Serial.println("In");
for (char i = 0; i < maxSize; i++){
for (char j = 0; j < maxSize; j++){
Serial.print(array[i][j]);
Serial.print(' ');
}
Serial.println();
}
Serial.println();
Serial.println("Out");
for (char i = 0; i < maxSize; i++){
for (char j = 0; j < maxSize; j++){
Serial.print(rotatedArray[i][j]);
Serial.print(' ');
}
Serial.println();
}
}

void loop() {
// put your main code here, to run repeatedly:

}
``````

Result:

``````In
A B C D
E F G H
I J K L
M N O P

Out
M I E A
N J F B
O K G C
P L H D
``````

This rotates the bits of an 8x8 font:

``````unsigned char font[8] = {
0B10101010,
0B11001100,
0B11100111,
0B00111100,
0B01001001,
0B10110111,
0B11000101,
0B01011101
};
unsigned char font_r[8];

// print an 8x8 bit font
void print_font_bits(unsigned char *font)
{
unsigned char c;
for(int i=0;i<8;i++) {
c = *font++;
for(int j=0;j<8;j++) {
if(c & 0x80)
Serial.print("1");
else
Serial.print("0");
c <<= 1;
}
Serial.println("");
}
}

// rotate the 8x8 bit font at *f and store the result in *fr
// This will not do a rotate in place so the output font
// must not be the same array as the input font
void rotate_font(unsigned char *f,unsigned char *fr)
{
unsigned char *fi;
unsigned char bit = 0x80;
unsigned char rf;
for(int i = 0;i<8;i++) {
fi = f;
rf = 0;
for(int j = 0;j<8;j++) {
rf >>= 1;
if(*fi++ & bit)rf |= 0x80;
}
bit >>= 1;
*fr++ = rf;
}
}

void setup(void)
{
Serial.begin(9600);
print_font_bits(font);
Serial.println("");
rotate_font(font,font_r);
print_font_bits(font_r);
}

void loop(void)
{
}
``````

Pete

OK maybe I wasn't entirely clear as to what I need to do. I used the "A", "B", "C", "D" thing as an example to show where the bit positions would be.

Here is what I am trying to do: The first block of "code" is an 8 by 8 pixel letter "A":

0b00010000
0b00101000
0b01000100
0b11111110
0b10000010
0b10000010
0b10000010
0b00000000

I need to rotate the letter 90 degrees clockwise:

0b01111000
0b00001100
0b00001010
0b00001001
0b00001010
0b00001100
0b01111000
0b00000000

I'm reading data from a raw binary file and trying to write one back out. I'm trying to do it in Basic (don't laugh!).

Here's the code I'm TRYING to make work......

`````` 10 dim fin(8)
20 dim fout(8)
30 open "R",#1,"ibm",1 ' raw font file
40 open "O",#2,"ibm90" ' output file rotated 90 deg
50 field #1,1 as d\$
60 r=lof(1)
70 for c=1 to r step 8
80   for b=0 to 7
90     get #1,c+b
100     fin(b)=asc(d\$) ' fin(0..7) is the 8 bytes of a char unrotated
110   next b
120   gosub 160
130 next c
140 end
150 for x=0 to 7
160   fout(x)=0 ' initialize fout(x)
170   for y=0 to 7
180     if (fin(y) and (2^y))=(2^y) then fout(x)=fout(x)+(2^y) ' if bit is set then "or" it into fout(x)
190   next y
200 next x
210 for x=0 to 7
220   print #2,chr\$(fout(x));
230 next x
240 return
``````

I can also do it in C... I did it in BASIC because I have a little test program I wrote that displays the font data to check if I did it right.

This SHOULD be simple, but I'm just not getting it. I feel like an idiot.

Any help will be greatly appreciated!

-- Roger

It's been a while since I wrote any BASIC, so can you explain lines 70 and 80, please?

Same code again, but working bitwise rather than element wise.

``````void setup() {
// put your setup code here, to run once:
byte array[8] = { 0b00010000,
0b00101000,
0b01000100,
0b11111110,
0b10000010,
0b10000010,
0b10000010,
0b00000000 };
byte rotatedArray[8] = {0};
/*
//rotate 90* anti-clockwise
for (char i = 0; i < maxSize; i++){
for (char j = 0; j < maxSize; j++){
char newI = 7-j;
char newJ = i;
byte value = ((array[i] >> j) & 1); //extract the j-th bit of the i-th element
rotatedArray[newI] |= (value << newJ); //set the newJ-th bit of the newI-th element
}
}
*/
//rotate 90* clockwise
for (char i = 0; i < 8; i++){
for (char j = 0; j < 8; j++){
char newI = j;
char newJ = 7-i;
byte value = ((array[i] >> j) & 1); //extract the j-th bit of the i-th element
rotatedArray[newI] |= (value << newJ); //set the newJ-th bit of the newI-th element
}
}

//It should now be reversed. Quick log to check.
Serial.begin(115200);
Serial.println("In");
for (char i = 0; i < 8; i++){
for (char j = 0; j < 8; j++){
Serial.print(((array[i]>>j)&1)?'1':'0');
Serial.print(' ');
}
Serial.println();
}
Serial.println();
Serial.println("Out");
for (char i = 0; i < 8; i++){
for (char j = 0; j < 8; j++){
Serial.print(((rotatedArray[i]>>j)&1)?'1':'0');
Serial.print(' ');
}
Serial.println();
}
}

void loop() {
// put your main code here, to run repeatedly:

}
``````

Worked like a charm! I used your code in a small C program (along with getchar and putchar) to fill and write the arrays, then converted the rotated binary file to a font file which I load into a Noritake 128x64 VFD display.

The font data is the actual IBM-PC text mode bitmap in the PC bios! It’s a nice readable font, which is why I wanted to get it working with the VFD display.

Thanks for your help (and thanks also to everyone else who replied!)

– Roger

AWOL:
It’s been a while since I wrote any BASIC, so can you explain lines 70 and 80, please?

Sure.

## – CODE: --------------------------------------------------------------------------------------------------- 70 for c=1 to r step 8 // c is the first byte of 8 to read (index into one character worth of font data) 80 for b=0 to 7 // b is an index into the character data 90 get #1,c+b // read byte “offset + index” 100 fin(b)=asc(d\$) // store byte in fin(x) (asc() returns the numeric value of the string byte) 110 next b // get next byte of char data block 120 gosub 160 // rotate one character 130 next c // do next character

BTW, the variable “r” in line 70 is the file size - i.e. it does “for 1 to 2048”.

Oh and thanks for the reply. Thanks to all the replies, I’ve got it working. Thanks!

– Roger

I’m still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?

AWOL:
I'm still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?

Basic uses 1-based arrays. And he is simulating a 2d array so his lower-level index "b" is more sensibly zero-based...

John

Basic uses 1-based arrays.

I know that

``````90     get #1,c+b // read byte "offset + index"
``````

But that’s not an array - it’s file, isn’t it?

AWOL:
I'm still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?

In BASIC, the index of the first random record (i.e. byte) is 1, not 0. I know it looks strange, but that's how it works.

BTW, the BASIC I'm using is BAS 2.3 by Michael Haardt, compiled and running in 64 bit Linux. It's syntax identical to GWBASIC.

When I need to whip up a quick and dirty program, I usually use BASIC because it's interactive - I can write, run, debug, edit and re-run without doing the "editor / compiler / debugger / editor / complier ...." dance.

AWOL:

Basic uses 1-based arrays.

I know that

``````90     get #1,c+b // read byte "offset + index"
``````

But that's not an array - it's file, isn't it?

The "get" command gets one byte from the file pointer "1" at index "c+b" and stores it in the string variable "d\$". Then, using "asc(d\$)" gives me the value of the byte. For example, if the byte at file location 24 was the letter "A", I would get this:

• get #1, 24
• (now d\$ == "A")
• asc(d\$) == 65 (a.k.a. 0x41)

Let's say the first 8 bytes of the font file are 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07.

The result would be:

fin(0) == 0
fin(1) == 1
fin(2) == 2
......
fin(6) == 6
fin(7) == 7

See? fin() in BASIC is the same thing as fin in C. At the top of the program where I do "dim fin(8)" is the same thing as "char fin[8];" in C.

Make sense?

AWOL:

Basic uses 1-based arrays.

I know that

``````90     get #1,c+b // read byte "offset + index"
``````

But that's not an array - it's file, isn't it?

Ok, Basic uses 1-based random-access-files

Makes a bit of sense, but all this swapping between zero and unity origin indexing is crazy.
Why isn’t it consistent?

AWOL:
Makes a bit of sense, but all this swapping between zero and unity origin indexing is crazy.
Why isn't it consistent?

That is a rhetorical question, right?

http://c2.com/cgi/wiki?ZeroAndOneBasedIndexes

I think I'm beginning to understand Dijkstra's comments about BASIC and brain-damage ]