Byteweise mit Carry addieren?

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

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

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.

Statt

1

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

2

vector0[i] += vector1[i]; // Summieren, Ueberlauf ignorieren

3

if (carry) vector0[i]++; // Uebertrag aus letzter Additionsrunde

besser

1

ergebnis = vector0[i] + vector1[i] + carry;

2

vector0[i] = ergebnis;

oder insgesamt

1

uint8_t vector0[10];

2

uint8_t vector1[10];

3

uint_fast16_t ergebnis = 0;

4

5

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

6

{

7

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

8

  vector0[i] = ergebnis;

9

  ergebnis >>= 8;

10

}

Kompiliert mit -O2 oder -Os ca. 20% kleiner, und ohne 16bit-Operationen:

1

uint8_t vector0[10];

2

uint8_t vector1[10];

3

4

uint8_t a, b, r1, r2, carry;

5

uint8_t *p = &vector0[0];

6

const uint8_t *q = &vector1[0];

7

8

for (uint8_t i = 10; i > 0; i--) {

9

        a = *p;

10

        b = *q++;

11

        r1 = a+b;

12

        r2 = r1+carry;

13

        carry = (r1 < a) | (r2 < r1);

14

        *p++ = r2;

15

}

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

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

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.

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

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

Andreas

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.

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

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

1

for (uint8_t i = 10; i > 0; i--) {

2

        /* ... */

3

}

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

Andreas