mikrocontroller.net

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


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Michael N. (garril)


Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich habe ein kleines Logikproblem.

Und zwar habe ich eine Matrize, die beispielsweise wie folgt aussieht:
1: 00000000
2: 00000000
3: 00000000
4: 00011100
5: 00000000
6: 00000000
7: 00000000
8: 00000000
nun möchte ich dieses Muster um 90° nach rechts drehen damit es wie 
folgt aussieht:
1: 00000000
2: 00000000
3: 00000000
4: 00000100
5: 00000100
6: 00000100
7: 00000000
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
int original_muster[8];
int gedrehtes_muster[8];
int i=0;
while (i<8) {
  original_muster[i]= //nnnnnnnn? und nun? n'tes (1-8) Bit ist i'tes Bit von original_muster[8-n]
  i++;
}

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)


Bewertung
0 lesenswert
nicht lesenswert
original_muster[i]|=(original[8-n]>>i)<<n;

?? Kanns gerade nicht testen.

von Michael N. (garril)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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


Bewertung
0 lesenswert
nicht lesenswert
int original_muster;
int gedrehtes_muster = {0}; /* Auf 0 Initialisieren! */

for (i=0; i<8; i++) {
  for (j=0; j<8; j++) {
    if (original_muster[i] & (1<<j))
      gedrehtes_muster[j] |= (1<<i);
  }
}

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)


Bewertung
0 lesenswert
nicht lesenswert
Marixmultiplikation mit einer Drehmatrix?
Für Matrixmul sollts Bibliotheken geben.

von Wegstaben V. (wegstabenverbuchsler)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


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

Ist doch 8x8, drehe sie um 90°.

von xfr (Gast)


Bewertung
0 lesenswert
nicht 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:
uint8_t original_muster[8];
uint8_t gedrehtes_muster[8] = {0}; /* Auf 0 Initialisieren! */

uint8_t i, j, imask, jmask;

for (  i = 0, imask = 0x01; i < 8; i++, imask <<= 1) {
  for (j = 0, jmask = 0x01; j < 8; j++, jmask <<= 1) {
    if (original_muster[i] & jmask) {
      gedrehtes_muster[j] |= imask;
    }  
  }
}

von Peter S. (psavr)


Bewertung
0 lesenswert
nicht lesenswert
uint8_t gedrehtes_muster[8] = {0,0,0,0,0,0,0,0}; //Auf 0 Initialisieren!

von Simon K. (simon) Benutzerseite


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

Oder
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)


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

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@  xfr (Gast)

Es reicht die Maske als Schleifenindikator, macht die Sache einen Tick 
schneller.
uint8_t i, j, imask, jmask;

for (  imask = 0x01; imask != 0; imask <<= 1) {
  for (jmask = 0x01; jmask != 0; jmask <<= 1) {
    if (original_muster[i] & jmask) {
      gedrehtes_muster[j] |= imask;
    }  
  }
}

von xfr (Gast)


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

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
Ahhhr!

von Alexander v. G. (avogra)


Bewertung
0 lesenswert
nicht lesenswert
Hier noch eine Alternative:
uint8_t orig[8], new[8] = {0,0,0,0,0,0,0,0};

for (uint8_t i = 0; i < 8; i++) {
  for (uint8_t j = 0; j < 8; j++) {
    new[i] = (new[i] << 1) | (orig[j] & 0x01);
    orig[j] >>= 1;
  }
}


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. G. (avogra)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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:
  c0 = in[0];
     2cc:  70 81         ld  r23, Z
  c1 = in[1];
     2ce:  61 81         ldd  r22, Z+1  ; 0x01
  c2 = in[2];
     2d0:  52 81         ldd  r21, Z+2  ; 0x02
  c3 = in[3];
     2d2:  43 81         ldd  r20, Z+3  ; 0x03
  c4 = in[4];
     2d4:  34 81         ldd  r19, Z+4  ; 0x04
  c5 = in[5];
     2d6:  25 81         ldd  r18, Z+5  ; 0x05
  c6 = in[6];
     2d8:  96 81         ldd  r25, Z+6  ; 0x06
  c7 = in[7];
     2da:  87 81         ldd  r24, Z+7  ; 0x07
       .
       .
       .

Und später Zurückschreiben ins out-array:
  out[0] = c0;
     314:  7c 93         st  X, r23
  out[1] = c1;
     316:  11 96         adiw  r26, 0x01  ; 1
     318:  6c 93         st  X, r22
     31a:  11 97         sbiw  r26, 0x01  ; 1
  out[2] = c2;
     31c:  12 96         adiw  r26, 0x02  ; 2
     31e:  5c 93         st  X, r21
     320:  12 97         sbiw  r26, 0x02  ; 2
  out[3] = c3;
     322:  13 96         adiw  r26, 0x03  ; 3
     324:  4c 93         st  X, r20
     326:  13 97         sbiw  r26, 0x03  ; 3
  out[4] = c4;
     328:  14 96         adiw  r26, 0x04  ; 4
     32a:  3c 93         st  X, r19
     32c:  14 97         sbiw  r26, 0x04  ; 4
  out[5] = c5;
     32e:  15 96         adiw  r26, 0x05  ; 5
     330:  2c 93         st  X, r18
     332:  15 97         sbiw  r26, 0x05  ; 5
  out[6] = c6;
     334:  16 96         adiw  r26, 0x06  ; 6
     336:  9c 93         st  X, r25
     338:  16 97         sbiw  r26, 0x06  ; 6
  out[7] = c7;
     33a:  17 96         adiw  r26, 0x07  ; 7
     33c:  8c 93         st  X, r24
     33e:  17 97         sbiw  r26, 0x07  ; 7
     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)


Bewertung
0 lesenswert
nicht 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. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht 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. G. (avogra)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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:
void write_digit( uint8_t digmask, uint8_t val )
{
  uint8_t i, j;
  
  val = numbers[val];        // convert to 7-segment
  for( i = 0; i < 8; i++ ){
    j = display_ram[i] | digmask;
    if( !(val & 0x01) )
      j ^= digmask;
    display_ram[i] = j;
    val >>= 1;
  }
}

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


Peter

von Troll (Gast)


Bewertung
0 lesenswert
nicht lesenswert
#include <avr/io.h>

volatile unsigned char mi[8] =
{
  0x1c, // 00011100
  0x36, // 00110110
  0x63, // 01100011
  0x63, // 01100011
  0x7f, // 01111111
  0x63, // 01100011
  0x63, // 01100011
  0x00  // 00000000
};

volatile unsigned char mo[8];
// Nach dem Drehen sollte mo
// 3e, 7e, c8, 88, c8, 7e, 3e, 00
// sein.

void BitsDrehen8x8(volatile unsigned char* pi, volatile unsigned char* po)
{
  asm volatile(
    " clc  \n"
    " ld   r8,  X+  \n"
    " ld   r9,  X+  \n"
    " ld   r10, X+  \n"
    " ld   r11, X+  \n"
    " ld   r12, X+  \n"
    " ld   r13, X+  \n"
    " ld   r14, X+  \n"
    " ld   r15, X+  \n"
    " ldi  r16, 8  \n"
    " mov  r7,  __zero_reg__  \n"
    "BitsDrehenLoop_%=:  \n"
    " lsr  r8   \n"  
    " rol  r7   \n"
    " lsr  r9   \n"  
    " rol  r7   \n"
    " lsr  r10  \n"  
    " rol  r7   \n"
    " lsr  r11  \n"  
    " rol  r7   \n"
    " lsr  r12  \n"  
    " rol  r7   \n"
    " lsr  r13  \n"  
    " rol  r7   \n"
    " lsr  r14  \n"  
    " rol  r7   \n"
    " lsr  r15  \n"  
    " rol  r7   \n"
    " st   Z+, r7  \n"
    " dec  r16  \n"
    " brne BitsDrehenLoop_%=  \n"
    : 
    : "x" (pi), "z" (po)
    : "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", "r16", "r17"
  );
}

int main()
{
  BitsDrehen8x8(mi, mo);
  for(;;)
  return 0;
}



von teuerprotz (Gast)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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. G. (avogra)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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.
mo[1] = blah;
BitsDrehen8x8(mi, mo);
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.