www.mikrocontroller.net

Forum: Compiler & IDEs Byteweise mit Carry addieren?


Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

folgendes Problem:
Gegeben sind zwei Byte-Vektoren, beispielsweise zweimal je 10 Bytes 
(vorzeichenlos, also uint8_t). Nun soll die Summe der beiden gebildet 
werden.

In Assembler ginge das prima in einer Schleife auf folgende Art:
- Zeiger X zeigt auf den Anfang des ersten,
- Zeiger Y zeigt auf den des zweiten Vektors.
- Byte 1 von X lesen.
- Byte 2 von Y lesen mit Postinkrement (ld R, X+).
- Byte 2 zu Byte 1 addieren mit Übertrag.
- Byte 1 nach X schreiben mit Postinkrement.

(logischerweise sollte man den Übertrag zu Beginn der Schleife 
löschen...)

Wie aber verklicker ich das in C dem GCC möglichst effizient? Das 
Übertragsflag gibts in C ja nicht, es würde also auf hässliche 
Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.

Vielen Dank und Gruß,
Sven

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Summe zweier 8bit Vektoren ist doch wieder ein 8 bit Vektor wofür 
benötigst du den Übertrag?

Autor: Tom M. (tomm) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Wie aber verklicker ich das in C dem GCC möglichst effizient? Das
> Übertragsflag gibts in C ja nicht, es würde also auf hässliche
> Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.

Wenn es auf die Performance drauf ankommt, würde ich einfach die 
Function in Assembler belassen/schreiben und dann reinlinken (.global 
für die zu exportierenden Symbole, dazu ein passendes header file). Geht 
schmerzlos. Die Doku zur avr-libc enthält ein Kapitel dazu, wie die 
Parameterübergabe funktioniert.

Ansonsten für die Summe einen grösseren Datentyp deklarieren und 
regelmässig/am Schluss prüfen (meinuint16>>8).

Autor: Floh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Wie aber verklicker ich das in C dem GCC möglichst effizient? Das
> Übertragsflag gibts in C ja nicht, es würde also auf hässliche
> Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.

uint8_t vector0[10];
uint8_t vector1[10];

uint16_t ergebnis[10];

for(uint8_t i=0;i<10;i++)
{
  ergebnis[i] = vector0[i]+vector1[i];
}

Die Rechnung müsste eigentlich schon von selbst mit 16 bit ablaufen, 
ansosnten kann man es noch casten.

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi, Floh:

Die Rechnung ist so aber leider falsch.

Ich hab mich auch etwas dumm ausgedrückt: Gemeint ist, dass die zehn 
Bytes in den beiden Vektoren eine 80-Bit-Zahl darstellen sollen, daher 
auch das Problem mit dem Carry. Ich hoffe, so ists verständlicher.

(Inline-)ASM wollte ich nach Möglichkeit vermeiden :-/

Autor: Hc Zimmerer (mizch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn ich Dich richtig verstanden habe, hast Du 2 Arrays vom Typ uint8_t 
und der Größe 10.  Die möchtest Du als 80-Bit-Zahlen interpretieren und 
zueinander addieren mit 80-Bit-Ergebnis.  Das höchste Bit fällt wohl 
raus.

Wenn's denn besonders effizient und/oder klein sein muss, würde ich das 
in Assembler machen.  Entweder inline oder als externe Function (im 
letzteren Fall hast Du halt noch den Overhead für Subroutine-Aufruf und 
-Rücksprung, sieht für mich aber schöner aus).

Edit: Hat sich mit Deiner Antwort überschnitten.

Autor: Floh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann so mit selbstgeschriebenem Carry ?

uint8_t vector0[10];  //80bit
uint8_t vector1[10];  //80bit

uint8_t ergebnis[11]; //da ergebnis 81 bit haben kann
uint8_t carry_flag=0;

for(uint8_t i=0;i<10;i++)
{
  ergebnis[i] = vector0[i] + vector1[i]+carry_flag;
  if((int)(vector0[i]+vector1[i])> 255)           //cast auf 16 bit 
rechnung
    carry_flag = 1;
  else
    carry_flag = 0;
}

Autor: Floh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ergebnis[10]=carry_flag;

Hab ich vergessen :-)

Autor: Tom M. (tomm) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
uint8_t vector0[10];
uint8_t vector1[10];
uint8_t carry = 0;
uint16_t ergebnis;

for(uint8_t i=0;i<10;i++)
{

  ergebnis = vector0[i] + vector1[i]; // Summieren

  vector0[i] += vector1[i]; // Summieren, Ueberlauf ignorieren
  if (carry) vector0[i]++; // Uebertrag aus letzter Additionsrunde

  carry = (ergebnis>>8); // 0 oder 1
}

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Statt
ergebnis = vector0[i] + vector1[i]; // Summieren
vector0[i] += vector1[i]; // Summieren, Ueberlauf ignorieren
if (carry) vector0[i]++; // Uebertrag aus letzter Additionsrunde
besser
ergebnis = vector0[i] + vector1[i] + carry;
vector0[i] = ergebnis;
oder insgesamt
uint8_t vector0[10];
uint8_t vector1[10];
uint_fast16_t ergebnis = 0;

for(uint8_t i=0;i<10;i++)
{
  ergebnis += vector0[i] + vector1[i];
  vector0[i] = ergebnis;
  ergebnis >>= 8;
}

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kompiliert mit -O2 oder -Os ca. 20% kleiner, und ohne 16bit-Operationen:
uint8_t vector0[10];
uint8_t vector1[10];

uint8_t a, b, r1, r2, carry;
uint8_t *p = &vector0[0];
const uint8_t *q = &vector1[0];

for (uint8_t i = 10; i > 0; i--) {
        a = *p;
        b = *q++;
        r1 = a+b;
        r2 = r1+carry;
        carry = (r1 < a) | (r2 < r1);
        *p++ = r2;
}       

Inspiriert vom Generic-Code der GMP-Library, oftmals gut geeignet als 
Quelle von optimierten Algorithmen für High-Precision-Arithmetik 
(allerdings ggf. Vorsicht wegen GPL geboten!).

Die Schleife zählt absichtlich rückwärts, da das noch den Vergleich für 
den Schleifenabbruch im generierten Code einspart.

Andreas

Autor: Klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Ferber schrieb:
> Kompiliert mit -O2 oder -Os ca. 20% kleiner, und ohne 16bit-Operationen:

Super :)  Und wenn du jetzt noch vernünftige Variablennamen nehmen 
würdest, wärs sogar gut lesbar ;-)

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nur ist diese Version trotz kryptischer Namen und etwas krampfiger 
Versuche, dem Compiler das Leben möglichst einfach zu machen, deutlich 
langsamer als meine Version, die das Optimieren dem Compiler überlasst 
(22T vs 15T pro Iteration bei avr-gcc 4.3.4 -Os).

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
PS: Man sollte Leerzeilen nicht mitzählen ;-). Es sind 20T vs 15T.

Der Compiler ist letztlich nicht übel. Es liessen sich nur noch 2 Takte 
einsparen, wenn man diesen C Code manuell optimiert aber beim Verfahren 
bleibt. Einzig die Schleifenendbedingung lässt zu wünschen übrig, der 
Rest ist bereits optimal.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Nur ist diese Version trotz kryptischer Namen und etwas krampfiger
> Versuche, dem Compiler das Leben möglichst einfach zu machen, deutlich
> langsamer als meine Version, die das Optimieren dem Compiler überlasst
> (22T vs 15T pro Iteration bei avr-gcc 4.3.4 -Os).

Sicher? Bei meinem Compiler (ebenfalls avr-gcc 4.3.4 mit -Os oder -O2) 
sind es 22T (deine Version) vs. 21T (meine Version), jeweils verpackt in 
eine Funktion, die vector0/vector1 als Parameter übergeben bekommt.

Zusätzlich ist die Registerlast deutlich geringer, so dass keine 
Register auf den Stack gepusht werden müssen (bei dir: 2 Register). Der 
Code vor und nach der Schleife sind 16T (du) vs. 6T (ich), jeweils das 
RET am Ende der Funktion mitgerechnet.

Insgesamt werden also unterm Strich 20 Takte gespart, nicht 
überwältigend, aber immerhin ca. 8,5%.

Andreas

Autor: Andreas Ferber (aferber)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hier noch die beiden von mir zum Test verwendeten Sourcen und die 
Listings.

Andreas

Autor: A. K. (prx)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Kommt offenbar stark darauf an, wo die Vektoren liegen. Bei sind sie 
statisch. Zwar hatte ich bei obiger Rechnung die 2 Takte für LD+ und ST+ 
nicht auf der Rechnung, aber das verschiebt die Bilanz nur zu 22/17.

Autor: A. K. (prx)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Wie wär's damit als Synthese? Vektoren als Parameter, Übertrag implizit 
über 16-Bit Rechnung statt teurer Vergleiche und ein dekrementierender 
Zähler ergibt nun 15T.

Den Code davor/dahinter rechne ich bei dominanter Schleife nicht mit. 
Jeder Befehl davon geht nur mit 1/10 in die Rechnung ein. Zumal hier 
nichts auf dem Stack landet.

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wobei man, das zeigten meine Versuche, statt der hässlichen 
do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die 
ist irgendwie intuitiver und genauso schnell.

Mag sein, dass das aber nur in den zwei, drei Testfällen funktioniert 
hat, ich wahr, offen gestanden, auch überrascht und werde das weiter 
verfolgen.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:

> Wobei man, das zeigten meine Versuche, statt der hässlichen
> do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die
> ist irgendwie intuitiver und genauso schnell.

Sie braucht einen Takt länger, wenn man addv3.c entsprechend umbaut. Bei 
do/while ist kein Vergleich erforderlich.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Wie wär's damit als Synthese? Vektoren als Parameter, Übertrag implizit
> über 16-Bit Rechnung statt teurer Vergleiche und ein dekrementierender
> Zähler ergibt nun 15T.

Ack, sieht gut aus :-)

Der entscheidende Punkt scheint wirklich die Verwendung (bzw. 
Nichtverwendung ;-) der Schleifenvariablen als Arrayindex zu sein. Siehe 
auch mein Post dazu im anderen Thread: 
Beitrag "Re: Sind ALLE Rechenoperationen automatisch 16-bit breit?"

A. K. schrieb:
> Sven P. schrieb:
>> Wobei man, das zeigten meine Versuche, statt der hässlichen
>> do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die
>> ist irgendwie intuitiver und genauso schnell.
> Sie braucht einen Takt länger, wenn man addv3.c entsprechend umbaut. Bei
> do/while ist kein Vergleich erforderlich.

Bei
for (uint8_t i = 10; i > 0; i--) {
        /* ... */
}

optimiert der GCC bei mir auch den Vergleich weg. Entscheidend ist hier 
wohl, dass der Schleifenabbruch beim Erreichen von 0 erfolgt.

Andreas

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.