Byteweise mit Carry addieren?

[Sven P. (Gast)]

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

[Läubi .. (laeubi)]

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

[Tom M. (tomm)]

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

[Floh (Gast)]

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.

[Sven P. (Gast)]

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 :-/

[Hc Z. (mizch)]

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.

[Floh (Gast)]

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;
}

[Floh (Gast)]

ergebnis[10]=carry_flag;

Hab ich vergessen :-)

[Tom M. (tomm)]

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
}

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

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;
}

[Andreas F. (aferber)]

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

[Klaus (Gast)]

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

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

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

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

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.

[Andreas F. (aferber)]

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

[Andreas F. (aferber)]

Hier noch die beiden von mir zum Test verwendeten Sourcen und die 
Listings.

Andreas

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

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.

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

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.

[Sven P. (Gast)]

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.

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

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.

[Andreas F. (aferber)]

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