arrays miteinander addieren - verbesserungsvorschläge

[Felicitas (Gast)]

guten abend,
ich wollte als übung für mich rechenarten (+-*/) für arrays 
implementieren.
das einfachste (die Addition) habe ich jetzt mal gemacht und wollte 
fragen was man besser machen kann

result ist noch static vorhanden (array mit 1024 elementen)
size ist die länge des arrays, welcher zur berechnung verwendet wurde
add1 ist array 1;
size1 ist länge von array 1;
add2 ist array 2;
size2 ist länge von array 2;

static uint8_t calcAdd(uint8_t* result, uint8_t* size, uint8_t* add1, uint8_t size1, uint8_t* add2, uint8_t size2)
{
    uint8_t temp1, temp2;
    uint8_t max = size1 > size2 ? (size1+1) : (size2+1);
    uint16_t temp;
    uint8_t overflow = 0;
    
    for(int8_t x=0; x<=max-2; x++)
    {
        temp1 = x < size1 ? add1[(size1-1) - x] : 0x00;
        temp2 = x < size2 ? add2[(size2-1) - x] : 0x00;
        temp = (uint16_t)temp1 + (uint16_t)temp2;
        result[(max-1) - x] = (uint8_t)(temp & 0xFF) + overflow;
        overflow = (uint8_t)(temp >> 8);
        printf(" 0x%02X, 0x%02X, 0x%02X\n", temp1, temp2, result[(max-1) - x]);
    }

    if(result[0] == 0x00)
    {
        memcpy(&result[0], &result[1], max);
        max--;
    }

    *size = max;

    printf("\n");
    return 1;
}

gebe ich z.B.

static uint8_t arr1[] = {0x22, 0x33, 0x44, 0xFF};
static uint8_t arr2[] = {0x22, 0x33, 0xFF};

in die Funktion ein, bekomme ich
{0x22, 0x55, 0x78, 0xFE} heraus.
Das passt.

[foobar (Gast)]

- Der Overflow ist verkehrt, probier mal { 255, 255 } und { 0,1 }.
- Der letzte Overflow geht verloren.
- Der Schleifenindex ist zu klein.
- Du mischt signed/unsigned bei den Indizes mit falschem Ergebnis.
- Der memcpy ist undefiniert (darf nicht überlappen).
- "<" statt "<=" in for-Schleifen spart meistens +/-1-Korrekturen.
- Big-Endian ist kacke ;-)

[PittyJ (Gast)]

Diese ganze + oder -1 Sache verwirrt nur. Da blickt keiner durch.

 max = size1 > size2 ? (size1+1) : (size2+1);
 result[(max-1) - x]

besser
max = .. size2 ..

und dann
for(int8_t x=0; x < max; x++)


Ansonsten hätte ich einen std::vector<uint8_t> benutzt.

[Achim M. (minifloat)]

Felicitas schrieb:
> was man besser machen kann

Wenn man ("the user knows") die Größe der Eingangs-und Ausgangs-BigInt 
kennt und alle gleich macht, geht's einfacher.

foobar schrieb:
> Big-Endian ist kacke ;-)
Nein, mixed-Endian ist richtig kacke. Dass man BigInt in selber 
endianness wie die ausführende Maschine sortiert, dürfte einleuchten.

Man könnte allerdings versuchen, die Rechnungen in 16- oder 32-bit 
chunks vorzunehmen, sofern 16- oder 32-bit-Maschin'. Dann braucht es 
weniger Rechenschritte.

mfg mf

[Felicitas (Gast)]

foobar schrieb:
> - Der Overflow ist verkehrt, probier mal { 255, 255 } und { 0,1 }.
> - Der letzte Overflow geht verloren.
> - Der Schleifenindex ist zu klein.
> - Du mischt signed/unsigned bei den Indizes mit falschem Ergebnis.
> - Der memcpy ist undefiniert (darf nicht überlappen).
> - "<" statt "<=" in for-Schleifen spart meistens +/-1-Korrekturen.

Joa, da war doch noch der ein oder andere Fehler drinne.
Das result array wurde komplett falschrum beschrieben

PittyJ schrieb:
> max = size1 > size2 ? (size1+1) : (size2+1);
>  result[(max-1) - x]
>
> besser
> max = .. size2 ..
>
> und dann
> for(int8_t x=0; x < max; x++)

Joa, dass passt besser

Achim M. schrieb:
> Man könnte allerdings versuchen, die Rechnungen in 16- oder 32-bit
> chunks vorzunehmen, sofern 16- oder 32-bit-Maschin'. Dann braucht es
> weniger Rechenschritte.

Das wollte ich zum schluss noch abändern. aber mit uint8_t kann ich es 
schneller mit Hand nachrechnen

momentan darf das Ergebnis halt nicht größer 1024 elemente haben. Aber 
das wollte ich auch zum schluss mit malloc versuchen zu umgehen. daher 
auch schonmal das size als rückgabewert um zu wissen wie groß das array 
letztendlich ist

static uint8_t calcAdd(uint8_t* result, uint16_t* size, uint8_t* add1, uint8_t size1, uint8_t* add2, uint8_t size2)
{
    uint8_t temp1, temp2;
    uint8_t max = size1 > size2 ? size1 : size2;
    uint16_t temp;
    uint8_t overflow = 0;
    
    for(uint8_t x=1; x<=max; x++)
    {
        temp1 = x <= size1 ? add1[size1 - x] : 0x00;
        temp2 = x <= size2 ? add2[size2 - x] : 0x00;
        temp = (uint16_t)temp1 + (uint16_t)temp2;
        result[1024 - x] = (uint8_t)(temp & 0xFF) + overflow;
        overflow = (uint8_t)(temp >> 8);
        printf(" 0x%02X, 0x%02X, 0x%02X\n", temp1, temp2, result[1024 - x]);
    }
    if(overflow)
    {
        result[1024 - max -1] = overflow;
    }

    *size = 1024;

    printf("\n");
    return 1;
}

[Jonas B. (jibi)]

>Achim M. schrieb:
>> Man könnte allerdings versuchen, die Rechnungen in 16- oder 32-bit
>> chunks vorzunehmen, sofern 16- oder 32-bit-Maschin'. Dann braucht es
>> weniger Rechenschritte.

Ja und wenn der Prozessor halbwegs modern ist hat er ganz andere 
Erweiterungen (z.B. AVX-512), die noch viel mehr parallele Operationen 
ermöglichen. Die auszuschöpfen wäre mein Ziel... zur Übung kann man das 
schon so machen, ich würde mir allerdings erstmal eine Testbench bauen.

>aber mit uint8_t kann ich es schneller mit Hand nachrechnen

Du kannst 137 mal 229 im Kopf rechnen? Respekt. Ich denke doch du musst 
auch einen Taschenrechner benutzen, von daher ist doch vollkommen egal 
wie groß die Zahlen sind. Mit einer Testbench allerdings könntest du 
einen kompletten Test für 8 bit Wortbreite schnell schreiben und 
komplett testen lassen.