Forum: Mikrocontroller und Digitale Elektronik 8x8 Bitmuster um 90° drehen


von Michael N. (garril)


Lesenswert?

Hallo,

ich habe ein kleines Logikproblem.

Und zwar habe ich eine Matrize, die beispielsweise wie folgt aussieht:
1
1: 00000000
2
2: 00000000
3
3: 00000000
4
4: 00011100
5
5: 00000000
6
6: 00000000
7
7: 00000000
8
8: 00000000
nun möchte ich dieses Muster um 90° nach rechts drehen damit es wie 
folgt aussieht:
1
1: 00000000
2
2: 00000000
3
3: 00000000
4
4: 00000100
5
5: 00000100
6
6: 00000100
7
7: 00000000
8
8: 00000000

Das ganze steht in einem Array und ich möchte dann mithilfe einer 
Schleife das ganz umbauen...Nur ich komme einfach nicht zu einer Lösung
1
int original_muster[8];
2
int gedrehtes_muster[8];
3
int i=0;
4
while (i<8) {
5
  original_muster[i]= //nnnnnnnn? und nun? n'tes (1-8) Bit ist i'tes Bit von original_muster[8-n]
6
  i++;
7
}

Meine Beschreibung im Kommentar stimmt, allerdings weiß ich nicht wie 
ich das nun programmieren soll...
Über Hilfe wäre ich sehr dankbar.

Gruß und schönen Abend,
Michael

von waaaaaaaaa (Gast)


Lesenswert?

original_muster[i]|=(original[8-n]>>i)<<n;

?? Kanns gerade nicht testen.

von Michael N. (garril)


Lesenswert?

und woher bekomme ich n?
Wie verpacke ich das wiederrum in ne schleife?

Programmiere zu selten auf Bitebene um das schnell zu verstehen...

von Frank (Gast)


Lesenswert?

Wenn's nicht gerade ein hochoptimierter Algorithmus sein muss, dann ist 
es der Logik nach mit dem Vertauschen der X- und Y-Koordinaten zwischen 
Lesen und Schreiben (in einen Zwischenpuffer) zu erledigen. In einem 
Basic-artigen Pseudocode sähe das etwa so aus:

for x=0 to xmax-1
 for y=0 to ymax-1
  buf[x,y]=orig[y,x]
 next y
next x

... oder?

von Simon K. (simon) Benutzerseite


Lesenswert?

1
int original_muster;
2
int gedrehtes_muster = {0}; /* Auf 0 Initialisieren! */
3
4
for (i=0; i<8; i++) {
5
  for (j=0; j<8; j++) {
6
    if (original_muster[i] & (1<<j))
7
      gedrehtes_muster[j] |= (1<<i);
8
  }
9
}

So würde ich anfangen. Ist aber nicht getestet. Kann man auch noch 
optimieren. z.B. nur ein/zwei Shift pro Zyklus, statt 1<<n.

von Mw E. (Firma: fritzler-avr.de) (fritzler)


Lesenswert?

Marixmultiplikation mit einer Drehmatrix?
Für Matrixmul sollts Bibliotheken geben.

von Wegstaben V. (wegstabenverbuchsler)


Lesenswert?

Michael N. schrieb:
> und woher bekomme ich n?
> Wie verpacke ich das wiederrum in ne schleife?
>
> Programmiere zu selten auf Bitebene um das schnell zu verstehen...

Ach, und in deiner gewohnten Hochsprache gibt es keine Schleifen und 
Schleifenindex-Variablen?

von Bronco (Gast)


Lesenswert?

Das hat nicht zufällig was mit einem Grafikdisplay zu tun?
Hatte in dem Zusammenhang mal die gleiche Anwendung...

Wie Simon richtig schreibt:
Du brauchst zwei Schleifen, eine für die Bytes und eine für die Bits.
Falls es ein µC ohne Barrelshifter ist (z.B. AVR): Versuche den Code so 
zu optimieren, daß Du immer nur um eine Bit-Stelle weiterscheiben mußt, 
da der AVR für jede Stelle einen Befehl braucht.

von Michael N. (garril) (Gast)


Lesenswert?

Habs gerafft :)
Muss mal sehen wann ich zum programmieren komme.

Danke soweit

Geht nicht direkt um ein display (kommt aber später in eine led matrix)

von Joachim D. (Firma: JDCC) (scheppertreiber)


Lesenswert?

Michael N. (garril) schrieb:
> kommt aber später in eine led matrix

Ist doch 8x8, drehe sie um 90°.

von xfr (Gast)


Lesenswert?

Simon K. schrieb:
> Kann man auch noch
> optimieren. z.B. nur ein/zwei Shift pro Zyklus, statt 1<<n.

Würde dann z.B. so aussehen:
1
uint8_t original_muster[8];
2
uint8_t gedrehtes_muster[8] = {0}; /* Auf 0 Initialisieren! */
3
4
uint8_t i, j, imask, jmask;
5
6
for (  i = 0, imask = 0x01; i < 8; i++, imask <<= 1) {
7
  for (j = 0, jmask = 0x01; j < 8; j++, jmask <<= 1) {
8
    if (original_muster[i] & jmask) {
9
      gedrehtes_muster[j] |= imask;
10
    }  
11
  }
12
}

von Peter S. (psavr)


Lesenswert?

1
uint8_t gedrehtes_muster[8] = {0,0,0,0,0,0,0,0}; //Auf 0 Initialisieren!

von Simon K. (simon) Benutzerseite


Lesenswert?

Peter S. schrieb:
>
1
> uint8_t gedrehtes_muster[8] = {0,0,0,0,0,0,0,0}; //Auf 0 Initialisieren!
2
>

Oder
1
uint8_t gedrehtes_muster[8] = {0}; /* Auf 0 Initialisieren! */

xfr schrieb:
> Würde dann z.B. so aussehen:
> ...

Genau! Für AVRs dürfte das so ziemlich das Effizienteste sein.

von Troll (Gast)


Lesenswert?

Ich würde dafür votieren, über das Carry-Bit zu rotieren.

von Falk B. (falk)


Lesenswert?

@  xfr (Gast)

Es reicht die Maske als Schleifenindikator, macht die Sache einen Tick 
schneller.
1
uint8_t i, j, imask, jmask;
2
3
for (  imask = 0x01; imask != 0; imask <<= 1) {
4
  for (jmask = 0x01; jmask != 0; jmask <<= 1) {
5
    if (original_muster[i] & jmask) {
6
      gedrehtes_muster[j] |= imask;
7
    }  
8
  }
9
}

von xfr (Gast)


Lesenswert?

Dann hat man aber i und j nicht mehr für den Array-Zugriff ... ;-)

von Falk B. (falk)


Lesenswert?

Ahhhr!

von Alexander V. (avogra)


Lesenswert?

Hier noch eine Alternative:
1
uint8_t orig[8], new[8] = {0,0,0,0,0,0,0,0};
2
3
for (uint8_t i = 0; i < 8; i++) {
4
  for (uint8_t j = 0; j < 8; j++) {
5
    new[i] = (new[i] << 1) | (orig[j] & 0x01);
6
    orig[j] >>= 1;
7
  }
8
}


Das selbe hab ich noch als Inline-Assembler rumliegen, mithilfe des 
Carry-Bits und intelligentem Stack-Mißbrauch :-P
In dem Projekt musste ich das regelmäßig auf 768 bytes anwenden. Die 
Assembler-Variante war glaub Faktor 3 schneller als in C.
Ich such heut Abend mal und stells hier ein.

von Alexander V. (avogra)


Angehängte Dateien:

Lesenswert?

So, hier mit etwas Verspätung die versprochene Routine, auf die Schnelle 
in ne undokumentierte C-Funktion verpackt :-P

Was mich gerade beim ausprobiern verwundert: Zum Einlesen des Arrays in 
die Register-Variablen benutzt der Compiler brav ldd (load with 
displacement). Beim Schreiben erzeugt er ein meiner Meinung nach 
unglaublich umständliches Konstrukt. Ich hab mich bei sowas schon oft 
getäuscht und musste dann zugegeben, dass der Compiler teilweise echt 
clever vorgeht. Hier kann ich mir aber nicht vorstellen, dass das nicht 
effizienter und mit weniger Code geht und er auch problemlos drauf 
kommen könnte.

Hier der entsprechende Ausschnitt des lss-files.
Einlesen des in-Arrays in die Register-Variablen:
1
  c0 = in[0];
2
     2cc:  70 81         ld  r23, Z
3
  c1 = in[1];
4
     2ce:  61 81         ldd  r22, Z+1  ; 0x01
5
  c2 = in[2];
6
     2d0:  52 81         ldd  r21, Z+2  ; 0x02
7
  c3 = in[3];
8
     2d2:  43 81         ldd  r20, Z+3  ; 0x03
9
  c4 = in[4];
10
     2d4:  34 81         ldd  r19, Z+4  ; 0x04
11
  c5 = in[5];
12
     2d6:  25 81         ldd  r18, Z+5  ; 0x05
13
  c6 = in[6];
14
     2d8:  96 81         ldd  r25, Z+6  ; 0x06
15
  c7 = in[7];
16
     2da:  87 81         ldd  r24, Z+7  ; 0x07
17
       .
18
       .
19
       .

Und später Zurückschreiben ins out-array:
1
  out[0] = c0;
2
     314:  7c 93         st  X, r23
3
  out[1] = c1;
4
     316:  11 96         adiw  r26, 0x01  ; 1
5
     318:  6c 93         st  X, r22
6
     31a:  11 97         sbiw  r26, 0x01  ; 1
7
  out[2] = c2;
8
     31c:  12 96         adiw  r26, 0x02  ; 2
9
     31e:  5c 93         st  X, r21
10
     320:  12 97         sbiw  r26, 0x02  ; 2
11
  out[3] = c3;
12
     322:  13 96         adiw  r26, 0x03  ; 3
13
     324:  4c 93         st  X, r20
14
     326:  13 97         sbiw  r26, 0x03  ; 3
15
  out[4] = c4;
16
     328:  14 96         adiw  r26, 0x04  ; 4
17
     32a:  3c 93         st  X, r19
18
     32c:  14 97         sbiw  r26, 0x04  ; 4
19
  out[5] = c5;
20
     32e:  15 96         adiw  r26, 0x05  ; 5
21
     330:  2c 93         st  X, r18
22
     332:  15 97         sbiw  r26, 0x05  ; 5
23
  out[6] = c6;
24
     334:  16 96         adiw  r26, 0x06  ; 6
25
     336:  9c 93         st  X, r25
26
     338:  16 97         sbiw  r26, 0x06  ; 6
27
  out[7] = c7;
28
     33a:  17 96         adiw  r26, 0x07  ; 7
29
     33c:  8c 93         st  X, r24
30
     33e:  17 97         sbiw  r26, 0x07  ; 7
31
     340:  08 95         ret

Ich versteh ja, dass er die Adresse des out-arrays im X-Registerpaar 
bekommt und das kein load with displacement anbietet. aber zumindest das 
sbiw und folgende adiw hätte er zusammenfassen können. Und wenn er noch 
etwas schlauer ist, sichert er Z, kopiert X nach Z und benutzt Z wieder 
mit displacement.

Achso, ich hab mit AvrStudio 6.0.1843, also AVR Toolchain 3.4.0.663 / 
GCC 4.6.2 und Optimierung -Os compiliert.

Gibts für das seltsame Verhalten nen Grund, der sich mir nur nicht 
erschließt?

Gruß, Alex

von Martin S. (der_nachbauer)


Lesenswert?

Warum alles so kompliziert ?

Viel einfacher und pragmatisch wäre es, sie einfach gedreht auszulesen, 
also etwa in der entsprechenden Routine Zeilen- und Spaltenindex zu 
vertauschen ...

von Lothar M. (Firma: Titel) (lkmiller) (Moderator) Benutzerseite


Lesenswert?

Ich würde gern mal einen Schritt zurück machen...

Michael N. schrieb:
> nun möchte ich dieses Muster um 90° nach rechts drehen
Warum?
Warum an dieser Programmstelle?
Wo wird das Muster erzeugt?
Wie wird es ausgegeben?

Evtl. reicht es, wenn du dein mentales Modell an irgendeiner Stelle um 
90° drehst...
(Dieser Satz ist ernst gemeint!)

von Alexander V. (avogra)


Lesenswert?

@Martin: kommt darauf an, was du damit noch machen möchtest. Wenn du nur 
einzelne Werte brauchst, geb ich dir recht. Wenn du tatsächlich das 
gesamte Array brauchst, ist das in einem Rutsch sicher schneller. Ob der 
OP das schneller braucht, ist dann wieder eine sehr berechtigte Frage.

@Lothar: da hast du absolut recht.

Nachdem der OP geschrieben hat, dass es für eine LED-Matrix ist vermute 
ich einfach mal, dass er z.B. für Bit-Angle-Modulation ein Ausgabe-Array 
erzeugen will. dann kommt er ums vollständig drehen wohl nicht rum.

von Peter D. (peda)


Lesenswert?

Hier noch ein Weg, wie ich es beim MAX7219 für Anzeigen mit gemeinsamer 
Anode mache. Es erfolgt die Drehung bei Eingabe der neuen Ziffer:
1
void write_digit( uint8_t digmask, uint8_t val )
2
{
3
  uint8_t i, j;
4
  
5
  val = numbers[val];        // convert to 7-segment
6
  for( i = 0; i < 8; i++ ){
7
    j = display_ram[i] | digmask;
8
    if( !(val & 0x01) )
9
      j ^= digmask;
10
    display_ram[i] = j;
11
    val >>= 1;
12
  }
13
}

Welche Methode nun am besten ist, kann man ohne genauere Angaben zur 
Anwendung nicht sagen.


Peter

von Troll (Gast)


Lesenswert?

1
#include <avr/io.h>
2
3
volatile unsigned char mi[8] =
4
{
5
  0x1c, // 00011100
6
  0x36, // 00110110
7
  0x63, // 01100011
8
  0x63, // 01100011
9
  0x7f, // 01111111
10
  0x63, // 01100011
11
  0x63, // 01100011
12
  0x00  // 00000000
13
};
14
15
volatile unsigned char mo[8];
16
// Nach dem Drehen sollte mo
17
// 3e, 7e, c8, 88, c8, 7e, 3e, 00
18
// sein.
19
20
void BitsDrehen8x8(volatile unsigned char* pi, volatile unsigned char* po)
21
{
22
  asm volatile(
23
    " clc  \n"
24
    " ld   r8,  X+  \n"
25
    " ld   r9,  X+  \n"
26
    " ld   r10, X+  \n"
27
    " ld   r11, X+  \n"
28
    " ld   r12, X+  \n"
29
    " ld   r13, X+  \n"
30
    " ld   r14, X+  \n"
31
    " ld   r15, X+  \n"
32
    " ldi  r16, 8  \n"
33
    " mov  r7,  __zero_reg__  \n"
34
    "BitsDrehenLoop_%=:  \n"
35
    " lsr  r8   \n"  
36
    " rol  r7   \n"
37
    " lsr  r9   \n"  
38
    " rol  r7   \n"
39
    " lsr  r10  \n"  
40
    " rol  r7   \n"
41
    " lsr  r11  \n"  
42
    " rol  r7   \n"
43
    " lsr  r12  \n"  
44
    " rol  r7   \n"
45
    " lsr  r13  \n"  
46
    " rol  r7   \n"
47
    " lsr  r14  \n"  
48
    " rol  r7   \n"
49
    " lsr  r15  \n"  
50
    " rol  r7   \n"
51
    " st   Z+, r7  \n"
52
    " dec  r16  \n"
53
    " brne BitsDrehenLoop_%=  \n"
54
    : 
55
    : "x" (pi), "z" (po)
56
    : "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", "r16", "r17"
57
  );
58
}
59
60
int main()
61
{
62
  BitsDrehen8x8(mi, mo);
63
  for(;;)
64
  return 0;
65
}

von teuerprotz (Gast)


Lesenswert?

Blödsinn!
Das "mov  r7,  __zero_reg__" ist ja wohl voll überflüssig.
Und wie oft willst Du am Ende return aufrufen? Was soll das bringen?

von teuerprotz (Gast)


Lesenswert?

Außerdem hast Du in der Clobber-List die falschen Register angegeben. r7 
fehlt und r17 taucht in Deinem Code nicht auf.

von Alexander V. (avogra)


Lesenswert?

Und außerdem glaube ich, dass du im asm nicht vorgeben kannst, wie 
deiner Funktion die Parameter zu übergeben sind :) (siehe Zuordnung x 
und z)
Aber grundsätzlich hast du recht, das Arrays ein- und auslesen lässt 
sich bestimmt noch vereinfachen. Wieso müssen die Arrays volatile sein?

Ich habe es aus einem bestehenden Programm übernommen, wo das 
Zurückschreiben des Ergebnisses nochmal anders funktioniert. Ist also 
nur auf die schnelle zusammengestrickt gewesen.

von Troll (Gast)


Lesenswert?

Jaja, und das "clc" ist auch für die Füße, und der Eingangsparameter 
hätte ein "const" verdient.

Alexander v. Grafenstein schrieb:
> Und außerdem glaube ich, dass du im asm nicht vorgeben kannst, wie
> deiner Funktion die Parameter zu übergeben sind :) (siehe Zuordnung x
> und z)

Im Inline-Assembler-Cookbook ( 
http://www.nongnu.org/avr-libc/user-manual/inline_asm.html ) wird es 
unter "Input and Output Operands" so beschrieben.
Ich habe es ausprobiert, und es hat funktioniert. Das List-File sieht 
auch gut aus.

> Aber grundsätzlich hast du recht, das Arrays ein- und auslesen lässt
> sich bestimmt noch vereinfachen. Wieso müssen die Arrays volatile sein?

Müssen sie in diesem Fall nicht, aber wenn andere Teile des Programms 
auf mo zugreifen, sollte der Compiler schon wissen, dass er die vor 
Verwendung nachladen muss. Das gilt zwar insbesondere für ISRs, aber 
soweit ich das verstehe, eben auch, wenn z.B.
1
mo[1] = blah;
2
BitsDrehen8x8(mi, mo);
3
hurz = mo[1]; // hurz != blah !!!
Suche mal nach
"In most situations, a much better solution would be to declare the 
pointer destination itself volatile"

> Ich habe es aus einem bestehenden Programm übernommen, wo das
> Zurückschreiben des Ergebnisses nochmal anders funktioniert. Ist also
> nur auf die schnelle zusammengestrickt gewesen.

In den 80ern habe ich mal ähnlich einen Nadeldrucker mit HGC-Grafikdaten 
gefüttert. Deinen Beitrag habe ich mir zum Anlass genommen, in das 
Inline Assembler Cookbock reinzuschauen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.