Codeoptimierung XOR auf Cortex-M3

[Random .. (thorstendb)]

Moin,

hat jemand eine Idee, wie man folgendes optimieren kann?

  while(packetSize) {
    *d = *s ^ cr[cryptoindex & CRYPT_KEY_MSK];
    ++d, ++s;
    ++cryptoindex;
    --packetSize;
  }

packetSize = 128..1024 Byte, immer 4*n Byte
d = Destination
s = Source (darf auch selbst überscheiben werden, ist aber nach Beenden 
der Funktion ungültig.
cr = 2^n Ringbuffer mit XOR Daten
Alle Variablen sind (uint32_t).
Die Daten werden später von einem Interrupt ausgegeben.
Das ganze läuft auf einem SAM3X.

LoopUnrolling auf 1/8 bzw. komplett hat schon ein wenig gebracht, aber 
es braucht noch immer "zu lange". Rausziehen der Increments mit pre-Inc 
hat dem Compiler auch ein klein wenig geholfen...


VG,
/th.

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

Wenn du den erzeugten bzw. real verwendeten Code weglässt, dann ist das 
schwer zu beantworten. Die Maschine führt ja C nicht direkt aus.

[Peter II (Gast)]

man müsste die Optimierung schon globaler machen.

Wenn d = s ist, kann man vieles sparen

  while(packetSize) {
    *s = *s ^ cr[cryptoindex & CRYPT_KEY_MSK];
    ++s;
    ++cryptoindex;
    --packetSize;
  }

warum braucht man cryptoindex und packetSize?

  for( i = 0; i < packetSize; ++i ) {
    *s = *s ^ cr[i & CRYPT_KEY_MSK];
    ++s;
  }

[Random .. (thorstendb)]

Hi,

Der cryptoindex startet an anderer Position als der index für die 
packetSize. Man könnte den als Offset dazuaddieren.

Wird auf s zurückgeschrieben, müsste nach der XOR Schleife ein memcpy() 
s->d gemacht werden.

[Exbärde (Gast)]

Wenn der 'cryptoindex' überläuft, wird deine "crypto" angreifbar. 
(Spätestens dann. Wer weiß, wie 'cr' erzeugt wird)

[Peter II (Gast)]

Random ... schrieb:
> Der cryptoindex startet an anderer Position als der index für die
> packetSize. Man könnte den als Offset dazuaddieren.

ist doch bei meinen Vorschlag egal.

> Wird auf s zurückgeschrieben, müsste nach der XOR Schleife ein memcpy()
> s->d gemacht werden.

warum muss es denn überhaupt umkopiert werden?

[Yalu X. (yalu) (Moderator)]

Überlege dir, wie der Code in Assembler optimalerweise aussehen müsste.

Wäre dieser optimale Code überhaupt ausreichend schnell? Wenn nicht,
dann musst du dein Gesamtkonzept überdenken oder einen schnelleren
Controller nehmen.

Wie weit ist der vom Compiler erzeugte Code davon entfernt? Welche Teile
der Schleife werden nicht erwartungsgemäß übersetzt?

Ansonsten fällt mir spontan auch nicht viel mehr ein als das, was Peter
II schon geschrieben hat. Hast du schon probiert, ob dieser Vorschlag
geschwindigkeitsmäßig hinkommen würde (auch wenn er sonst nicht ganz
deinen Vorstellungen entspricht)?

Random ... schrieb:
> Der cryptoindex startet an anderer Position als der index für die
> packetSize. Man könnte den als Offset dazuaddieren.

Oder den Inhalt von cr vorher passend umschichten. Das bringt natürlich
nur dann etwas, wenn die Größe von cr deutlich kleiner als die
Paketgröße ist.

> Wird auf s zurückgeschrieben, müsste nach der XOR Schleife ein memcpy()
> s->d gemacht werden.

Wieso? Wird der Inhalt von s hinterher noch gebraucht? Oder liegt es nur
daran:

Random ... schrieb:
> s = Source (darf auch selbst überscheiben werden, ist aber nach Beenden
> der Funktion ungültig.

Aber das lässt sich ja sicher ändern.

[Random .. (thorstendb)]

Peter II schrieb:
> Random ... schrieb:
>> Der cryptoindex startet an anderer Position als der index für die
>> packetSize. Man könnte den als Offset dazuaddieren.
> ist doch bei meinen Vorschlag egal.
?

>> Wird auf s zurückgeschrieben, müsste nach der XOR Schleife ein memcpy()
>> s->d gemacht werden.
> warum muss es denn überhaupt umkopiert werden?
Weil s Teil eines Eth frames ist. Ich müsste die Library umbauen 
(können), um diese Buffer selbst wieder zu releasen, weil sie an anderer 
Stelle noch verwendet werden.

Ich überlege gerade, ob es sinnvoll ist, diese Daten per DMA in den 
Zielbuffer zu kopieren und dann mit einer anderen Task zu decrypten - 
bevor es in den Ausgabetimer geht. Oder live im Timer Interrupt 
decrypten, dort werden immer nur 2-16 Byte auf einmal benötigt...

> Oder den Inhalt von cr vorher passend umschichten.
cr ist sehr wesentlich grösser als der buffer :-)

[Peter II (Gast)]

Auch wenn man sich eventuell die Kapselung kaputt macht, kann man auch 
direkt beim senden erst die Verschlüsselung machen. Wenn dort die Daten 
nicht per DMA gesendet werden.

So wie aktuelle netzwerkkarte die Checksumme vom TCP auch in der 
Hardware berechnen obwohl sie von TCP eigentlich nichts wissen sollten.

[Random .. (thorstendb)]

Peter II schrieb:
> Auch wenn man sich eventuell die Kapselung kaputt macht, kann man auch
> direkt beim senden erst die Verschlüsselung machen. Wenn dort die Daten
> nicht per DMA gesendet werden.
>
> So wie aktuelle netzwerkkarte die Checksumme vom TCP auch in der
> Hardware berechnen obwohl sie von TCP eigentlich nichts wissen sollten.

andersrum. Die Daten kommen verschlüsselt an, und werden im Timer 
blockweise 2..8 Bytes pro Interrupt weiterverarbeitet. Sie gehen nie 
wieder in den Eth.

[dummy (Gast)]

>Wäre dieser optimale Code überhaupt ausreichend schnell? Wenn nicht,
>dann musst du dein Gesamtkonzept überdenken oder einen schnelleren
>Controller nehmen.

Wenn man an dem bisschen Code schon feilen muss ist der Controller
definitiv zu schlapp. CM3 kann auch Code im RAM ausführen.

[Peter II (Gast)]

Random ... schrieb:
> andersrum. Die Daten kommen verschlüsselt an, und werden im Timer
> blockweise 2..8 Bytes pro Interrupt weiterverarbeitet. Sie gehen nie
> wieder in den Eth.

Da sieht du schön, das wir eigentlich gar nicht helfen können. Denn für 
eine Optimierung muss man nicht nur einen kleinen Teil vom Programm 
kennen. Lokale kleine Optimierungen bringen meist nicht viel.

[Kai S. (zigzeg)]

Random ... schrieb:
> LoopUnrolling auf 1/8 bzw. komplett hat schon ein wenig gebracht, aber
> es braucht noch immer "zu lange".

Loop Unrolling per compiler option ? Oder wie ?
Evtl. per hand unrollen ?

Sind s und cr als const pointer deklariert ? Koennte evtl. weitere 
Optimierungsmoeglichkeiten geben.

Vielleicht bist Du auch schon an der maximalen Bandbreite des Memory. 
Evtl. mal benchmarken ?

ZigZeg

[Daniel A. (daniel-a)]

Vileicht kann man das dekrementieren von packetSize wegoptimieren, falls 
der Compiler das nicht sowiso tut.
Bei cryptoindex und s würde ich ein register davorpacken. Ob es etwas 
nützt weiss ich nicht.

  const char* end = s+packetSize;
  while(s<end) {
    *s = *s ^ cr[cryptoindex & CRYPT_KEY_MSK];
    ++s;
    ++cryptoindex;
  }

[micha (Gast)]

Vielleicht Unrolling via Duff's device 
(http://de.wikipedia.org/wiki/Duff%E2%80%99s_Device)

int n = (packetSize+7)/8;
switch(packetSize % 8) {
  case 0: do { *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 7:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 6:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 5:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];  
  case 4:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 3:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 2:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
  case 1:      *d++ = *s++ ^ cr[cryptoindex++ & CRYPT_KEY_MSK];
          } while (--n);

[Random .. (thorstendb)]

const werde ich mal ausmessen.
Unrolling hab ich wie oben "manuell" gemacht :-)

[Hans W. (Firma: Wilhelm.Consulting) (hans-)]

intel macht's vor...

http://web.archive.org/web/20120722193753/http://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf

sollte sich einfach ummünzen lassen...

73

[Random .. (thorstendb)]

SB8 ...
Hmmm ...
Ich arbeite schon auf 32Bit. D.h. die 1024Byte laufen schon als 32Bit 
1024/4 durch die XOR Schleife :-)

[Marcus H. (mharnisch)]

Hallo Thorsten

Random ... schrieb:
> cr = 2^n Ringbuffer mit XOR Daten

Falls (cryptoindex & CRYPT_KEY_MSK) sehr viel kleiner als die Laenge der 
Daten sein sollte, koenntest Du die Schleife andersherum abrollen. D.h. 
erst cr laden und dann alle XORs berechnen, die dazu passen.

Statt 2*packetsize Speicherzugriffe, haettest Du dann nur noch 
packetsize+(cryptoindex & CRYPT_KEY_MSK).

> LoopUnrolling auf 1/8 bzw. komplett hat schon ein wenig gebracht, aber
> es braucht noch immer "zu lange". Rausziehen der Increments mit pre-Inc
> hat dem Compiler auch ein klein wenig geholfen...

Ich gehe mal davon aus, dass Du den armcc verwendest und damit branch 
target optimization aktiviert ist[1]. Aber da das ganze schon ohne 
schleife nicht gepasst hat, wuerde ich mir in der Richtung keine 
Hoffnung machen.

Mit Mikrooptimiering derartiger trivial algorithmen kommt man meist 
nicht so weit. Eventuell solltest Du die Berechnung blockweise an 
anderer Stelle vornehmen, wo die Daten eh ausgelesen werden.

Footnotes:
[1] M3 mag's lieber, wenn das Sprungziel an einer Wortadresse liegt.

[Yalu X. (yalu) (Moderator)]

Random ... schrieb:
>> Oder den Inhalt von cr vorher passend umschichten.
> cr ist sehr wesentlich grösser als der buffer :-)

Dann kannst du dir aber die Maskierung mit "& CRYPT_KEY_MSK" sparen. Du
musst dazu nur cr um eine Paketlänge vergößern (was ja dann prozentual
nicht viel ausmacht) und in diesen Bereich die Daten vom Anfang von cr
hineinkopieren.

Damit sparst du immerhin eine Rechenoperation ein.

[Marcus H. (mharnisch)]

Marcus Harnisch schrieb:
> Falls (cryptoindex & CRYPT_KEY_MSK) sehr viel kleiner als die Laenge der
> Daten sein sollte, koenntest Du die Schleife andersherum abrollen. D.h.
> erst cr laden und dann alle XORs berechnen, die dazu passen.
>
> Statt 2*packetsize Speicherzugriffe, haettest Du dann nur noch
> packetsize+(cryptoindex & CRYPT_KEY_MSK).

Gut gedacht, falsch formuliert. Ersetze alle (cryptoindex & 
CRYPT_KEY_MSK) mit (CRYPT_KEY_MSK + 1)

[Random .. (thorstendb)]

Marcus Harnisch schrieb:
> Gut gedacht, falsch formuliert. Ersetze alle (cryptoindex &
> CRYPT_KEY_MSK) mit (CRYPT_KEY_MSK + 1)
Hm? Wie soll das funktionieren, ohne Index? Ausserdem ist (MASK+1) ja 
ausserhalb des Arrays :-)

Weiterhin ist das cryptArray wesentlich grösser als die eintreffenden 
Daten.

[Marcus H. (mharnisch)]

Random ... schrieb:
> Marcus Harnisch schrieb:
>> Gut gedacht, falsch formuliert. Ersetze alle (cryptoindex &
>> CRYPT_KEY_MSK) mit (CRYPT_KEY_MSK + 1)
> Hm? Wie soll das funktionieren, ohne Index? Ausserdem ist (MASK+1) ja
> ausserhalb des Arrays :-)

Ersetze in meiner falsch formulierten Antwort... nicht in Deinem Code 
:)

> Weiterhin ist das cryptArray wesentlich grösser als die eintreffenden
> Daten.

Ja das hattest Du gesagt. Du hast aber nicht gesagt, wie gross 
CRYPT_KEY_MSK ist. Es waere immerhin moeglich, dass Du nur einen kleinen 
Teil aus einem sehr grossen Feld betrachtest.