Inline Assembler- Bits spiegeln

[Anton S. (analysis)]

Ich habe ein LCD mit spiegelbildlich angeschlossenen Datenleitungen zu 
einem Port und brauche deshalb eine Funktion, um die Bits wieder 
"umzudrehen". Dazu gibt es 2 Lösungen, eine mit Inline Assembler und 
eine in C, die schon hier Beitrag "Re: Problem mit dtostrf" 
diskutiert wurden.

Minimalbeispiel:

//Assembler Routine zum Umdrehen (Spiegeln) der Bits
#define reverse(a) ({ \
           unsigned char ch; \
           asm volatile ( \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1" "\n\t" \
           "rol %0" "\n\t" \
           "ror %1"  /* restore input register */ \
           : /* output */ "=r&" (ch) \
           : /* input */ "r" ((uint8_t)(a)) \
           ); \
           ch; \
   })

 
int main (void) {            
 
   DDRB  = 0xff;             
   PORTB = 0x05;      //Initialisierung         

   while(1) {                
   port=0x29;
   port=reverse(port);
   PORTB=port;

   //2. Routine zum Drehen, es sollte am Ende wieder 0x29 rauskommen
  port=((port&0xaa)>>1)|((port&0x55)<<1);
  port=((port&0xcc)>>2)|((port&0x33)<<2);
  port=((port&0xf0)>>4)|((port&0x0f)<<4);
  PORTB=port;
   } 
   return 0;           
}

Das ganze läuft beim ersten Schleifendurchlauf richtig, allerdings gibt 
es bei weiteren Schleifendurchläufen Probleme. Die Assemblerroutine 
benutzt R20 und R24 (AVR Studio mit WinAVR20070525, Simulator) wobei 
diese Register von den nachfolgenden 2. Routine verändert werden. Obwohl 
am Anfang explizit port=0x29; steht verwendet die Assemblerroutine dann 
Datenmüll.

Wie müssen die Inline Assembler Befehle verändert werden? (Ich kenne 
mich leider mit Assembler nicht gut aus). Es würde immerhin einen 
erheblichen Geschwindigkeitsvorteil bedeuten von 17 zu 53 cycles.

[Matthias L. (Gast)]

> spiegelbildlich angeschlossenen Datenleitungen

Beim Hardwareentwurf, geschlafen bedeutet Mehraufwand in der Software.

[Anton S. (analysis)]

Matthias Lipinsky wrote:
> Beim Hardwareentwurf, geschlafen bedeutet Mehraufwand in der Software.

Das kann man bei ebay Angeboten vorher leider schlecht prüfen. Back to 
topic!

[Jörg X. (Gast)]

Wenn ich mir das so im Simulator anschaue, funktioniert das aber 
wunderbar (AVR-Studio 4.13, SP2, WinAVR 20071221 ).
Aus 0x29 (-> 0b00101001) wird  0x94 (-> 0b10010100) und wieder 0x29.
Dieser Gcc verwendet aber r24 und r25 für die Asm-Routine.

Also evtl. ist da bei dir ein Update fällig.
hth. Jörg

[Günther Kreischer (Gast)]

Hallo,

dein Makro wird dir immer wieder Probleme bereiten da man nicht immer 
davon ausgehen kann in welchen Registern dein Wert abgelegt ist. Der 
Optimizer im GCC "würfelt" schon einmal die Register durcheinander.

Zweitens ist das Makro kein sauberes Design. Wenn Du das schon mit 
Assembelrcode machen willst schreib eine Funktion, übergib der die 
Variable. Das passt immer.

Ciao

[Peter D. (peda)]

Anton Streg. wrote:
> Ich habe ein LCD mit spiegelbildlich angeschlossenen Datenleitungen zu
> einem Port und brauche deshalb eine Funktion, um die Bits wieder
> "umzudrehen".

> Es würde immerhin einen
> erheblichen Geschwindigkeitsvorteil bedeuten von 17 zu 53 cycles.

Also, erheblich ist der Unterschied nicht, ich würde sogar sagen, er ist 
vollkommen unmerkbar.
Schließlich muß man dem Menschen ja auch Zeit geben, das LCD abzulesen.
Oftmals hat man daher in den Programmen noch zusätzliche Verzögerungen 
für die Displayausgabe, damit der Text mindestens einmal gelesen werden 
kann. Da spielen dann 53 Zyklen keinerlei Rolle.


Aber Dein C-Code krankt an der 16Bit-Lastigkeit des GCC. Der GCC 
verliert schnell mal den Durchblick und erweitert eine Rechnung auf 
16Bit, auch wenn das Ergebnis nur 8bittig ist.
Besser ist daher dieser Code:

unsigned char mirror( unsigned char n )
{
  n = ((n >> 1) & 0x55) | ((n << 1) & 0xaa);
  n = ((n >> 2) & 0x33) | ((n << 2) & 0xcc);
  n = ((n >> 4) & 0x0f) | ((n << 4) & 0xf0);
  return n;
}

Der wird vom GCC 8bittig durchgeführt und braucht daher nur 20 Zyklen.


Peter

[Anton S. (analysis)]

Jörg X. wrote:
> Wenn ich mir das so im Simulator anschaue, funktioniert das aber
> wunderbar (AVR-Studio 4.13, SP2, WinAVR 20071221 ).

Habe nun die neueste WinAVR Version installiert. Das Problem taucht hier 
wirklich nicht mehr auf. Ich habe noch die beiden Listings angehängt.

WinAVR20071221 verwendet andere Register. Das Problem bleibt ob es einen 
Fehler im Makro gibt (ich bin nicht der Autor) oder nur ein spezieller 
Bug mit dem Compiler der auch wieder auftauchen kann.

[Anton S. (analysis)]

Peter Dannegger wrote:

>

> 
> unsigned char mirror( unsigned char n )
> {
>   n = ((n >> 1) & 0x55) | ((n << 1) & 0xaa);
>   n = ((n >> 2) & 0x33) | ((n << 2) & 0xcc);
>   n = ((n >> 4) & 0x0f) | ((n << 4) & 0xf0);
>   return n;
> }
> 
>

> Der wird vom GCC 8bittig durchgeführt und braucht daher nur 20 Zyklen.

Danke für den Tipp! Ich verstehe nur nicht ganz, warum meine 3 fast 
identische Zeilen die 2,5 fache Laufzeit brauchen bzw. wie man solche 
möglichen Optimierungen erkennt ;-)

[c mit 7 Siegeln (Gast)]

Ich bin durch den momentan laufenden thread 
Beitrag "Erfahrungen eines Einsteigers" auf diesen aufmerksam 
geworden.
Lerne c und möchte weder den thread oben zernudeln, noch einen anderen 
aufmachen, aber ich raffe nicht so ganz was bei mirror passiert.

Ich werde das auf Papier mal durchgehen, aber die frage: nach der ersten 
Zeile wird n ein Wert zugewiesen.

>>>Wird dieses veränderte n dann für die Berechnung aus Zeile 2 benützt?<<<

Ich kann mir gar nicht vorstellen, daß da dann nachher noch was übrig 
bleibt.... Oder kann noch jemand den Erklärbär machen?

[Huch (Gast)]

>Ich kann mir gar nicht vorstellen, daß da dann nachher noch was übrig
bleibt....

Das wird Dir klar, wenn Du Dir die Schritte mal auf Papier skizzierst.

[c mit 7 Siegeln (Gast)]

Habe ich ja vor, nur um Frust zu vermeiden: in Schritt 2 das veränderte 
n und nciht das aus dem Funktionsaufruf?

[Karl H. (kbuchegg)]

c mit 7 Siegeln schrieb:
> Habe ich ja vor, nur um Frust zu vermeiden: in Schritt 2 das veränderte
> n und nciht das aus dem Funktionsaufruf?

so wie's dort steht.
In der Zeile davor hat das n einen neuen Wert bekommen. Und natürlich 
wird mit diesem neuen Wert weitergemacht. Wenn in der Abarbeitung ein ; 
erreicht wird, ist die Zuweisungen jeweils erledigt worden und dann hat 
n in der Sequenz jeweils einen neuen Wert bekommen.

[Huch (Gast)]

>Habe ich ja vor, nur um Frust zu vermeiden: in Schritt 2 das veränderte
>n und nciht das aus dem Funktionsaufruf?

Ich bin etwas irritiert von Deiner Frage: Du kannst sie Dir eigentlich 
selbst ganz einfach beantworten.

Wozu sollte man in einer Zeile n neu berechnen, wenn es in nachfolgenden 
Zeilen dann nicht beachtet, und stattdessen der ursprünglich übergebene 
Wert von n genommen wird? Wozu gäbe es dann eine dritte Zeile, in der 
das selbe passiert? Dann bräuchte man ja die ersten beiden Zeilen 
überhaupt nicht.

Logisch, oder?

[c mit 7 Siegeln (Gast)]

ok, danke euch für die Hilfe.
DASS das richtige rauskommt habe ich nachvollzogen, aber WARUM das so 
ist... ich habe keine Ahnung ;-)
Müssen Programmierer entsprechend Mathematiker sein oder sich einfach an 
das Rezept erinnern.... nein, bitte nicht antworten das zöge mich 
runter.
Danke noch mal war ja ein alter thread, aber er erschien mir am besten 
geeignet zu sein.

[Huch (Gast)]

>Müssen Programmierer entsprechend Mathematiker sein ...

Nun. Mit Mathematik hat das Problem von oben eigentlich garnichts zu 
tun.

Man könnte sogar sagen, das es Definitionssache, insofern war meine 
Antwort ein wenig überheblich. Sorry. Denn z.B. in VHDL muss man sich an 
eine andere Logik gewöhnen.

Aber ein Programmier sollte immer auch mathematische Kenntnisse haben, 
das ist schon richtig und die gängigen Ausbildungswege beinhalten auch 
einen Gutteil davon.

[lucifer1655 (Gast)]

Hallo zusammen


Ich habe das gleiche Problem, die Datenleitungen von PIC (16F886) zu LCD 
müssten hardware- oder eben softwaremässig gedreht werden. Bei der 
Recherche bin ich auf diesen Thread gestossen, habe dann aber noch eine 
eigene Lösung in Assembler gefunden. Das ganze funktioniert für PICs, 
aber ich nehme an den Rotate Befehl gibt es genau in dieser Form auch 
bei AVR. Der Witz an der Sache ist, dass man sich das Carry als 
Zwischenspeicher zunutze machen kann:

old     equ 0x20           ; Zu konvertierendes Wort
new     equ 0x21           ; Gespiegeltes Ergebnis
counter equ 0x22           ; Schleifenzähler


bcf     STATUS,RP0         ; Bank 0 wählen
bcf     STATUS,RP1
movlw   0x8                ; Schleifenzähler mit 8 laden
movwf   counter
bcf     STATUS,C           ; Carry löschen
loop:
rrf     old,1              ; Altes Wort nach rechts durchs Carry rotieren und wieder
                           ; im Register ablegen. >> C enthält jetzt letztes Bit
rlf     new,1              ; Neues Wort nach links durchs Carry rotieren und wieder...
                           ; Das "alte" LSB ist jetzt MSB und rutscht mit jedem rlf um
                           ; eine Stelle nach vorn;
decfsz  counter            ; Schleifenzähler--; das ganze nochmals falls nicht null
goto    loop
.
.
.

Das ganze funktioniert soweit (zumindest im Emulator von Waliul Mondal), 
ich werde das ganze dann via inline assembler in meinen C-Code 
einbinden.



(Der Thread ist zwar steinalt, aber vielleicht quälst isch ja wieder mal 
jemand an diesem Problem rum...)

[Stefan F. (Gast)]

Wenn du 256 Bytes RAM frei hast, geht das mit einer Übersetzungstabelle 
(byte array) deutlich schneller (sowohl in C als auch in Assembler):

static uint8_t swap[256] = {
   0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,
   0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,
   0x08,0x88,0x48,0xc8,0x28,0xa8,0x68,0xe8,
   0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8,
   0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4,
   0x14,0x94,0x54,0xd4,0x34,0xb4,0x74,0xf4,
   0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec,
   0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc,
   0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2,
   0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2,
   0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea,
   0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa,
   0x06,0x86,0x46,0xc6,0x26,0xa6,0x66,0xe6,
   0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6,
   0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee,
   0x1e,0x9e,0x5e,0xde,0x3e,0xbe,0x7e,0xfe,
   0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1,
   0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1,
   0x09,0x89,0x49,0xc9,0x29,0xa9,0x69,0xe9,
   0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9,
   0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5,
   0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5,
   0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed,
   0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd,
   0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3,
   0x13,0x93,0x53,0xd3,0x33,0xb3,0x73,0xf3,
   0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb,
   0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb,
   0x07,0x87,0x47,0xc7,0x27,0xa7,0x67,0xe7,
   0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7,
   0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef,
   0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,0x7f,0xff};

data=swap[data];

[(prx) A. K. (prx)]

Zur Erinnerung: Der Thread ist von 2008.

[lucifer1655 (Gast)]

Daran habe ich auch gedacht, diese Variante entfällt aber mangels RAM 
(total 368 Byte).
Ich probiere aber, das ganze noch mit einer Tabelle zu lösen, einfach 
nibbleweise. Mal schauen, was dann schneller ist. Da ich aber den gratis 
XC8 benutze, nehme ich an, dass meine ASM Lösung effizienter ist.

@prx
Warum einen neuen eröffnen, wenn es genau zu diesem Thema schon einen 
gibt? ;)

[fchk (Gast)]

Man kann die Tabelle als const deklarieren. Dann sollte sie im Flash 
landen.

[Johann L. (gjlayde)]

Anton Streg. schrieb:
> Ich verstehe nur nicht ganz, warum meine 3 fast
> identische Zeilen die 2,5 fache Laufzeit brauchen

Das wird dir auch keiner erklären können weil dein Code nicht 
übersetzbar ist.

Wahrscheinlich ist "port" signed oder volatile oder keine 8-Bit Variable 
oder was auch immer..



Jörg X. schrieb:
> Dieser Gcc verwendet aber r24 und r25 für die Asm-Routine.
>
> Also evtl. ist da bei dir ein Update fällig.

Und was hat das nun mit der Registerverwendung zu tun?

Die Registerverwendung ist weder an eine bestimmte Version von GCC 
gebunden noch an das jeweilige Inline Assembler.  Ebenso gut könnte GCC 
R20 und R26 verwendet haben.

Das Problem ist nicht die Compilerversion sondern dass der Code 
schlichtweg falsch ist — da hülft auch kein Update.

[Johann L. (gjlayde)]

A. K. schrieb:
> Zur Erinnerung: Der Thread ist von 2008.

Die Frage kommt ja immer wieder.

Es gibt dazu garantiert auch Threads aus 2004, 2005, 2006, 2007, 2009, 
2010, 2011, 2012, 2013 und 2014, immer so mindestend alle 3-4 Wochen. 
Je nach Geschmack kann man dann einen davon auswählen oder NOCH einen 
aufmachen :-)

[Erwin M. (nobodyy)]

Bits einzeln durch die Gegend zu schieben ist Unsinn, sofern man keinen 
1-Bit-Mikrocontroller verwendet.
Da ein Mikrocontroller aber mindestens 8 Bit in einem Schritt 
verarbeitet sind nur Lookup-Tabellen sinnvoll, auch weil das viel 
CPU-Zeit spart.
Hier ist die für 8 Bit:

     const char reversed[256] = {
       0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
       0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
       0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
       0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
       0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
       0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
       0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
       0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
       0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
       0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
       0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
       0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
       0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
       0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
       0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
       0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
       0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
       0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
       0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
       0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
       0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
       0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
       0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
       0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
       0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
       0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
       0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
       0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
       0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
       0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
       0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
       0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF,
     };

Wer die testen will kann ja ein Hellworld-Programm schreiben, in dem er 
die Werte mit den aufwendig geschobenen vergleicht.
Entsprechend kann man solche Tabellen auch erzeugen.

Bei 16, 32 usw. Bits muss man die Tabelle für 8 Bit mehrmals verwenden, 
also das like Byte gespielt nach rechts packen (d. h. MSB nach LSB) 
usw..

[c-hater (Gast)]

Erwin Meyer schrieb:

> Bits einzeln durch die Gegend zu schieben ist Unsinn, sofern man keinen
> 1-Bit-Mikrocontroller verwendet.
> Da ein Mikrocontroller aber mindestens 8 Bit in einem Schritt
> verarbeitet sind nur Lookup-Tabellen sinnvoll, auch weil das viel
> CPU-Zeit spart.

Das kann man so nicht stehen lassen. Erstens sparen Lookuptabellen 
längst nicht immer Rechenzeit (sondern oft nur, wenn bestimmte 
Randbedingungen erfüllt sind) und zweitens brauchen sie Platz im 
Speicher, der vielleicht nicht in ausreichendem Maße vorhanden ist.

Nehmen wir mal den Table-Lookup im suboptimalsten Fall, in dem keinerlei 
Optimierungen möglich sind (oder wegen Unfähigkeit keine angewendet 
wurden). Dann sieht die MirrorBits-Funktion mit Lookup-Table in AVR 
Assembler ungefähr so aus:

.DEF tmp=R17
.EQU LUTNEGOFFS=-(MirrorLUT<<1)

;->R16: zu spiegelndes Byte
;<-R16: gespiegeltes Byte
MirrorBits:
  push tmp                     ; 2
  push ZL                      ; 2
  push ZH                      ; 2
  in tmp,RAMPZ                 ; 1
  push tmp                     ; 2

  mov ZL,R16                   ; 1
  clr ZH                       ; 1
  clr tmp                      ; 1

  subi ZL,Byte1(LUTNEGOFFS)    ; 1
  sbci ZH,Byte2(LUTNEGOFFS)    ; 1
  sbci tmp,Byte3(LUTNEGOFFS)   ; 1
  out RAMPZ,tmp                ; 1

  elpm R16,Z                   ; 3

  pop tmp                      ; 2
  out RAMPZ,tmp                ; 1
  pop ZH                       ; 2
  pop ZL                       ; 2
  pop tmp                      ; 2
  ret                          ; 4
                               ;--
                               ;32

Wir haben hier also flockige 32 Takte und 294 Bytes Flash für Code und 
LUT verbraucht.

Dazu kommen natürlich weitere 3 oder 4 Takte und 2 oder 4 Byte Flash für 
jeden Aufruf dieser Routine, aber das hätten wir bei der Alternative ja 
genauso und soll deshalb hier erstmal nicht weiter interessieren.

Wenn man nun genau die gleiche Suboptimalität für die beste Umsetzung 
ohne LUT voraussetzt, dann kommt etwa das raus:

;->R16: zu spiegelndes Byte
;<-R16: gespiegeltes Byte
MirrorBits:
  push tmp    ; 2

  bst R16,0   ; 1
  bld tmp,7   ; 1
  bst R16,1   ; 1
  bld tmp,6   ; 1
  bst R16,2   ; 1
  bld tmp,5   ; 1
  bst R16,3   ; 1
  bld tmp,4   ; 1
  bst R16,4   ; 1
  bld tmp,3   ; 1
  bst R16,5   ; 1
  bld tmp,2   ; 1
  bst R16,6   ; 1
  bld tmp,1   ; 1
  bst R16,7   ; 1
  bld tmp,0   ; 1

  mov R16,tmp ; 1

  pop tmp     ; 2
  ret         ; 4
              ;--
              ;25

Das sieht in jeder Hinsicht erstmal deutlich freundlicher aus. 
Rechenzeitbedarf -31%, Speicherverbrauch -93%, bezogen auf die 
LUT-Lösung.

Man sieht also: LUT alleine ist nicht notwendigerweise effizienter, da 
gehört schon noch etwas mehr dazu, damit sowas wirklich effizienter 
wird.

Das fängt erstmal mit der übliche Abwägung an, was es eigentlich zu 
optimieren gilt, Codegröße oder Rechenzeit.

Wenn es die Codegröße ist, fällt LUT meistens leider aus. Da hier fast 
immer die LUT selber den Löwenanteil des Speichers schluckt, gibt's da 
wenig zu optimieren. Ausnahme sind sehr komplexe Berechnungen, die auf 
Daten mit geringer Wortbreite angewendet werden. Da könnte sich auch bei 
Optimierung auf Codegröße hin und wieder mal eine LUT lohnen.

Anders bei der Optimierung auf Rechenzeit. Da steckt in den LUTs 
erhebliches Potential, man muß allerdings auch die richtigen 
Randbedingungen schaffen, damit das auch geweckt wird und nicht so ein 
absoluter Reinfall wie in obigem Beispiel rauskommt.

Die optimalen Randbedingungen für das Beispiel wären:
-LUT liegt unterhalb 64k
-LUT ist auf eine 256-Bytegrenze aligned

Dann reduziert sich das Ganze schonmal sehr deutlich auf:

;->R16: zu spiegelndes Byte
;<-R16: gespiegeltes Byte
MirrorBits:
  push ZL                      ; 2
  push ZH                      ; 2

  mov ZL,R16                   ; 1
  ldi ZH,High(MirrorLUT<<1)    ; 1

  lpm R16,Z                    ; 3

  pop ZH                       ; 2
  pop ZL                       ; 2
  ret                          ; 4
                               ;--
                               ;17

Das ist rechenzeitmäßig ganz erheblich besser als die erste LUT-Variante 
und immerhin auch schon deutlich besser als die "gerechnete" Variante. 
Aber da geht noch erheblich mehr. Wenn man dafür sorgt, daß Z frei 
verfügbar ist, dann kommt man zu:

;->R16: zu spiegelndes Byte
;<-R16: gespiegeltes Byte
MirrorBits:
  mov ZL,R16                   ; 1
  ldi ZH,High(MirrorLUT<<1)    ; 1
  lpm R16,Z                    ; 3
  ret                          ; 4
                               ;--
                               ; 9

Und wenn man dann noch den Callframe einspart und gleich das ZL-Register 
zur Parameter- und Ergebnisübergabe benutzt, dann kommt man hier an:

;->ZL: zu spiegelndes Byte
;<-ZL: gespiegeltes Byte
.MACRO MirrorBits
  ldi ZH,High(MirrorLUT<<1)    ; 1
  lpm ZL,Z                     ; 3
.ENDMACRO                      ;--
                               ; 4


So, und nun möchte ich die C-Lösung sehen, die das in vier Takten 
schafft. Nur um zu zeigen, wie vergleichweise einfach massive 
Rechenzeitoptimierungen doch in Assembler zu erreichen sind...

Sehr gute C-Compiler würden allerdings tatsächlich auch ohne 
Inline-Assembler die vier Takte schaffen können, theoretisch könnten die 
nämlich natürlich ganz genau dieselben Optimierungen vornehmen. Die 
Sache ist nur: ich kenne keinen, der das packt...

Der GCC jedenfalls kann's definitiv nicht. Selbst mit genauso viel 
Nachhilfe durch den Programmierer wie in Assembler packt er's nicht. Ja 
er packt es nichtmal, wenn man den eigentliche Kern der Sache auch noch 
selber als Inline-Funktion in Inline-Assembler schreibt. Blöde starre 
Runtime...

Fazit: Portabilität heißt letztlich nix anderes als "suboptimal auf 
jeder Zielplattform".

[Johann L. (gjlayde)]

c-hater schrieb:
> So, und nun möchte ich die C-Lösung sehen, die das in vier Takten
> schafft. Nur um zu zeigen, wie vergleichweise einfach massive
> Rechenzeitoptimierungen doch in Assembler zu erreichen sind...
>
> Sehr gute C-Compiler würden allerdings tatsächlich auch ohne
> Inline-Assembler die vier Takte schaffen können, theoretisch könnten die
> nämlich natürlich ganz genau dieselben Optimierungen vornehmen. Die
> Sache ist nur: ich kenne keinen, der das packt...

Ist jetzt nicht dein Ernst, oder?

Du würdest erwarten, dass ein Compiler den Code nach Möglichkeiten 
abscannt, Algorithmen durch LUTs zu ersetzen?

Eine Division durch 10 — kein Problem: Speicher hat man ja bekanntlich 
wie Heu!  Also eine LUT her, damit man ein paar grottige Ticks spart. 
Noch ein LUT für den nächsten Shift oder das mod 10 gefällig?.  Ja klar! 
Nur her damit!

Und natürlcih werden alle LUTs auf 256 Bytes aligned!  Weil das die 
Anwender von dem "sehr guten Compiler" so erwarten.

Vorstellungen haben die Leut...

[(prx) A. K. (prx)]

Johann L. schrieb:
> Vorstellungen haben die Leut...

Zumal es für unverbrauchte Rechenzeit keine Kostenerstattung gibt und 
deshalb eine simple Schleife auch nicht unbedingt schlecht dastehen 
muss, zumal wenn die kürzer ist (11 Worte als C-Funktion, statt 19 in 
obiger Bittransportversion).

Und: Was erwartest du von jemandem, der sich "c-hater" nennt?

[Jörg W. (dl8dtl) (Moderator)]

Erwin Meyer schrieb:

> Da ein Mikrocontroller aber mindestens 8 Bit in einem Schritt
> verarbeitet sind nur Lookup-Tabellen sinnvoll, auch weil das viel
> CPU-Zeit spart.

Lookup-Tabellen sind nur dafür gut, schnell zu sein.  Mit der
Ressource „Speicher“ gehen sie nämlich alles andere als schonend um.

Ist also ein typischer Fall, bei dem man sich Geschwindigkeit durch
Speicher erkauft.

Der oft recht günstige Mittelweg wurde hier genannt:

Beitrag "Re: Inline Assembler- Bits spiegeln"

Ansonsten kann man den Thread jetzt wieder in der Versenkung
verschwinden lassen.

[c-hater (Gast)]

A. K. schrieb:

> Zumal es für unverbrauchte Rechenzeit keine Kostenerstattung gibt

Doch, die gibt es. Jedes verschissene nJ, was ein batteriebetriebenes 
Gerät weniger verbraucht, weil es bei gleichem Takt schneller mit seiner 
Aufgabe fertig ist, zahlt sich z.B. ganz direkt in geringeren Kosten für 
den Erwerb der Primärelemente aus, die den Betrieb erst möglich machen.

> und
> deshalb eine simple Schleife auch nicht unbedingt schlecht dastehen
> muss, zumal wenn die kürzer ist (11 Worte als C-Funktion, statt 19 in
> obiger Bittransportversion).

Ich hätte dich für deutlich kreativer gehalten. Wenigstens um in der 
Diskussion gut auszusehen, hättest du dir ja wohl mal ein wenig Mühe 
geben können, wenn du schon mit so abstrusen Argumenten wie der 
Codegröße kommst.

Aber auch die kann ich in Asm potentiell immer besser optimieren als der 
beste C-Compiler. Es ist nur nicht so oft nötig wie die Optimierung 
bezüglich der Rechenzeit, deswegen mußte ich hier auch erst ein wenig 
nachdenken, bevor mir folgendes eingefallen ist:

;->R16: zu spiegelndes Byte
;<-R16: gespiegeltes Byte
MirrorBits_MinCodesize:
  push tmp     ; 2
  ldi tmp,1    ; 1

loop:
  lsr R16      ; 1  1
  rol tmp      ; 1  1
  brcc loop    ; 1  2

  mov R16,tmp  ; 1
  pop tmp      ; 2
  ret          ; 4

Das sind ACHT Worte und eine Laufzeit von 7*4+1*13=41 Takten.

Halten wir also fest: Sowohl bezüglich der Codegröße als auch bezüglich 
der Rechenzeit ist die jeweils beste Asm-Implementierung für die 
jeweilige Optimierung der jeweils besten C-Implementierung um ca. 30% 
überlegen. Weiters ist sie auch in der jeweils nicht optimierten 
Richtung der der jeweiligen C-Lösung überlegen. Und zwar noch 
signifikanter.

Mehr wollte ich nicht zeigen. ASM rules. Forever.

[Jörg W. (dl8dtl) (Moderator)]

c-hater schrieb:
> ASM rules. Forever.

Klar.  Solange man genügend CPU-Zyklen verbrennen kann/darf, den
ganzen Salat zu warten …

Wenn alle so prima zufrieden gewesen wären damit, glaubst du, man hätte
jemals höhere Programmiersprachen erfinden müssen?

Aber ich weiß, Richtige Programmierer™ können in jeder Sprache ihre
Assemblerprogramme produzieren.  Hatte letztens erst wieder ein
Beispiel dafür.