Gibt es ein C-Snippet, das eine überlaufsichere Addition effizient berechnet, ohne Compiler-Integrationen zu verwenden?

11

Hier ist eine C-Funktion, die eine intzu einer anderen hinzufügt und fehlschlägt, wenn ein Überlauf auftreten würde:

int safe_add(int *value, int delta) {
        if (*value >= 0) {
                if (delta > INT_MAX - *value) {
                        return -1;
                }
        } else {
                if (delta < INT_MIN - *value) {
                        return -1;
                }
        }

        *value += delta;
        return 0;
}

Leider ist es von GCC oder Clang nicht gut optimiert :

safe_add(int*, int):
        movl    (%rdi), %eax
        testl   %eax, %eax
        js      .L2
        movl    $2147483647, %edx
        subl    %eax, %edx
        cmpl    %esi, %edx
        jl      .L6
.L4:
        addl    %esi, %eax
        movl    %eax, (%rdi)
        xorl    %eax, %eax
        ret
.L2:
        movl    $-2147483648, %edx
        subl    %eax, %edx
        cmpl    %esi, %edx
        jle     .L4
.L6:
        movl    $-1, %eax
        ret

Diese Version mit __builtin_add_overflow()

int safe_add(int *value, int delta) {
        int result;
        if (__builtin_add_overflow(*value, delta, &result)) {
                return -1;
        } else {
                *value = result;
                return 0;
        }
}

ist besser optimiert :

safe_add(int*, int):
        xorl    %eax, %eax
        addl    (%rdi), %esi
        seto    %al
        jo      .L5
        movl    %esi, (%rdi)
        ret
.L5:
        movl    $-1, %eax
        ret

Aber ich bin gespannt, ob es einen Weg gibt, ohne eingebaute Elemente zu verwenden, die von GCC oder Clang musterangepasst werden.

Tavian Barnes
quelle
1
Ich sehe, dass es im Zusammenhang mit der Multiplikation gcc.gnu.org/bugzilla/show_bug.cgi?id=48580 gibt . Das Hinzufügen von Mustern sollte jedoch viel einfacher sein. Ich werde es melden.
Tavian Barnes

Antworten:

6

Das Beste, was ich mir ausgedacht habe, ist, Dinge zu erledigen, wenn Sie keinen Zugriff auf die Überlaufflagge der Architektur haben unsigned. Denken Sie hier nur an alle Bitarithmetik, da wir nur an dem höchsten Bit interessiert sind, das das Vorzeichenbit ist, wenn es als vorzeichenbehaftete Werte interpretiert wird.

(All diese Modulo-Vorzeichenfehler habe ich nicht gründlich überprüft, aber ich hoffe, die Idee ist klar)

#include <stdbool.h>

bool overadd(int a[static 1], int b) {
  unsigned A = a[0];
  unsigned B = b;
  // This computation will be done anyhow
  unsigned AB = A + B;
  // See if the sign bits are equal
  unsigned AeB = ~(A^B);
  unsigned AuAB = (A^AB);
  // The function result according to these should be:
  //
  // AeB \ AuAB | false | true
  //------------+-------+------
  // false      | false | false
  // true       | false | true
  //
  // So the expression to compute from the sign bits is (AeB & AuAB)

  // This is INT_MAX
  unsigned M = -1U/2;
  bool ret = (AeB & AuAB) > M;

  if (!ret) a[0] += b;
  return ret;
}

Wenn Sie eine Version des Zusatzes finden, die frei von UB ist, z. B. eine atomare, ist der Assembler sogar ohne Verzweigung (jedoch mit einem Sperrpräfix).

#include <stdbool.h>
#include <stdatomic.h>
bool overadd(_Atomic(int) a[static 1], int b) {
  unsigned A = a[0];
  atomic_fetch_add_explicit(a, b, memory_order_relaxed);
  unsigned B = b;
  // This computation will be done anyhow
  unsigned AB = A + B;
  // See if the sign bits are equal
  unsigned AeB = ~(A^B);
  unsigned AuAB = (A^AB);
  // The function result according to these should be:
  //
  // AeB \ AuAB | false | true
  //------------+-------+------
  // false      | false | false
  // true       | false | true
  //
  // So the expression to compute from the sign bits is (AeB & AuAB)

  // This is INT_MAX
  unsigned M = -1U/2;
  bool ret = (AeB & AuAB) > M;
  return ret;
}

Wenn wir also eine solche Operation hätten, aber noch "entspannter", könnte dies die Situation noch weiter verbessern.

Take3: Wenn wir eine spezielle "Besetzung" vom nicht signierten zum signierten Ergebnis verwenden, ist diese jetzt verzweigungsfrei:

#include <stdbool.h>
#include <stdatomic.h>

bool overadd(int a[static 1], int b) {
  unsigned A = a[0];
  //atomic_fetch_add_explicit(a, b, memory_order_relaxed);
  unsigned B = b;
  // This computation will be done anyhow
  unsigned AB = A + B;
  // See if the sign bits are equal
  unsigned AeB = ~(A^B);
  unsigned AuAB = (A^AB);
  // The function result according to these should be:
  //
  // AeB \ AuAB | false | true
  //------------+-------+------
  // false      | false | false
  // true       | false | true
  //
  // So the expression to compute from the sign bits is (AeB & AuAB)

  // This is INT_MAX
  unsigned M = -1U/2;
  unsigned res = (AeB & AuAB);
  signed N = M-1;
  N = -N - 1;
  a[0] =  ((AB > M) ? -(int)(-AB) : ((AB != M) ? (int)AB : N));
  return res > M;
}
Jens Gustedt
quelle
2
Nicht der DV, aber ich glaube, dass der zweite XOR nicht negiert werden sollte. Siehe zB diesen Versuch , alle Vorschläge zu testen.
Bob__
Ich habe so etwas versucht, konnte es aber nicht zum Laufen bringen. Sieht vielversprechend aus, aber ich wünschte, GCC hätte den idiomatischen Code optimiert.
R .. GitHub STOP HELPING ICE
1
@PSkocik, nein das hängt nicht von der Vorzeichendarstellung ab, die Berechnung erfolgt komplett als unsigned. Dies hängt jedoch davon ab, dass beim vorzeichenlosen Typ nicht nur das Vorzeichenbit ausgeblendet ist. (Beide sind jetzt in C2x garantiert, dh für alle Bögen, die wir finden konnten). Dann können Sie das unsignedErgebnis nicht zurückgeben, wenn es größer als INT_MAXist. Dies wäre eine definierte Implementierung und kann ein Signal auslösen.
Jens Gustedt
1
@PSkocik, nein leider nicht, das schien dem Ausschuss revolutionär zu sein. Aber hier ist ein "Take3", der tatsächlich ohne Verzweigungen auf meiner Maschine herauskommt.
Jens Gustedt
1
Es tut uns Leid , Sie wieder zu stören, aber ich denke , Sie sollten Take3 in wie etwas ändern diese korrekte Ergebnisse zu erhalten. Es scheint jedoch vielversprechend .
Bob__
2

Die Situation bei signierten Operationen ist viel schlimmer als bei nicht signierten, und ich sehe nur ein Muster für die signierte Addition, nur für das Klirren und nur, wenn ein breiterer Typ verfügbar ist:

int safe_add(int *value, int delta)
{
    long long result = (long long)*value + delta;

    if (result > INT_MAX || result < INT_MIN) {
        return -1;
    } else {
        *value = result;
        return 0;
    }
}

clang gibt genau das gleiche asm wie bei __builtin_add_overflow:

safe_add:                               # @safe_add
        addl    (%rdi), %esi
        movl    $-1, %eax
        jo      .LBB1_2
        movl    %esi, (%rdi)
        xorl    %eax, %eax
.LBB1_2:
        retq

Ansonsten ist die einfachste Lösung, die ich mir vorstellen kann, folgende (mit der Schnittstelle als Jens):

_Bool overadd(int a[static 1], int b)
{
    // compute the unsigned sum
    unsigned u = (unsigned)a[0] + b;

    // convert it to signed
    int sum = u <= -1u / 2 ? (int)u : -1 - (int)(-1 - u);

    // see if it overflowed or not
    _Bool overflowed = (b > 0) != (sum > a[0]);

    // return the results
    a[0] = sum;
    return overflowed;
}

gcc und clang erzeugen einen sehr ähnlichen asm . gcc gibt dies:

overadd:
        movl    (%rdi), %ecx
        testl   %esi, %esi
        setg    %al
        leal    (%rcx,%rsi), %edx
        cmpl    %edx, %ecx
        movl    %edx, (%rdi)
        setl    %dl
        xorl    %edx, %eax
        ret

Wir wollen die Summe in berechnen unsigned , unsignedmüssen also in der Lage sein, alle Werte von darzustellen, intohne dass einer von ihnen zusammenklebt. Um das Ergebnis einfach von unsignednach zu konvertieren int, ist auch das Gegenteil sinnvoll. Insgesamt wird das Zweierkomplement angenommen.

Ich denke, wir können auf allen gängigen Plattformen konvertieren unsignedint durch eine einfache Zuordnung zu , int sum = u;aber wie Jens erwähnte, ermöglicht es sogar die neueste Variante des C2x-Standards, ein Signal zu erzeugen. Der nächst natürlichste Weg ist, so etwas zu tun: *(unsigned *)&sum = u;Aber Nicht-Trap-Varianten der Polsterung können sich offenbar für signierte und nicht signierte Typen unterscheiden. Das obige Beispiel geht also den harten Weg. Glücklicherweise optimieren sowohl gcc als auch clang diese knifflige Konvertierung.

PS Die beiden oben genannten Varianten konnten nicht direkt verglichen werden, da sie sich unterschiedlich verhalten. Die erste folgt der ursprünglichen Frage und blockiert die *valuebei Überlauf nicht. Der zweite folgt der Antwort von Jens und blockiert immer die Variable, auf die der erste Parameter zeigt, aber sie ist verzweigungslos.

Alexander Cherepanov
quelle
Könnten Sie den generierten ASM anzeigen?
R .. GitHub STOP HELPING ICE
Ersetzt die Gleichheit durch xor in der Überlaufprüfung, um mit gcc einen besseren asm zu erzielen. Asm hinzugefügt.
Alexander Cherepanov
1

Die beste Version, die ich finden kann, ist:

int safe_add(int *value, int delta) {
    long long t = *value + (long long)delta;
    if (t != ((int)t))
        return -1;
    *value = (int) t;
    return 0;
}

welches produziert:

safe_add(int*, int):
    movslq  %esi, %rax
    movslq  (%rdi), %rsi
    addq    %rax, %rsi
    movslq  %esi, %rax
    cmpq    %rsi, %rax
    jne     .L3
    movl    %eax, (%rdi)
    xorl    %eax, %eax
    ret
.L3:
    movl    $-1, %eax
    ret
Iłya Bursov
quelle
Ich bin überrascht, dass das Überlauf-Flag nicht verwendet wird. Immer noch viel besser als die expliziten Bereichsprüfungen, aber es wird nicht verallgemeinert, lange Longs hinzuzufügen.
Tavian Barnes
@TavianBarnes Sie haben Recht, leider gibt es keine gute Möglichkeit, Überlauf-Flags in c zu verwenden (außer compilerspezifischen Buildins)
Iłya Bursov
1
Dieser Code leidet unter einem signierten Überlauf, bei dem es sich um undefiniertes Verhalten handelt.
Emacs macht mich verrückt
@emacsdrivesmenuts, Sie haben Recht, die Besetzung im Vergleich kann überlaufen.
Jens Gustedt
@emacsdrivesmenuts Die Besetzung ist nicht undefiniert. Wenn intein Cast von einem breiteren Typ außerhalb des Bereichs von liegt , wird entweder ein implementierungsdefinierter Wert erzeugt oder ein Signal ausgelöst. Alle Implementierungen, die mir wichtig sind, definieren es, um das Bitmuster beizubehalten, das das Richtige tut.
Tavian Barnes
0

Ich könnte den Compiler dazu bringen, das Vorzeichen-Flag zu verwenden, indem ich eine Zweierkomplementdarstellung annehme (und bestätige), ohne Bytes aufzufüllen. Solche Implementierungen sollten das erforderliche Verhalten in der durch einen Kommentar kommentierten Zeile ergeben, obwohl ich im Standard keine positive formale Bestätigung dieser Anforderung finden kann (und es wahrscheinlich keine gibt).

Beachten Sie, dass der folgende Code nur die positive Ganzzahladdition behandelt, aber erweitert werden kann.

int safe_add(int* lhs, int rhs) {
    _Static_assert(-1 == ~0, "integers are not two's complement");
    _Static_assert(
        1u << (sizeof(int) * CHAR_BIT - 1) == (unsigned) INT_MIN,
        "integers have padding bytes"
    );
    unsigned value = *lhs;
    value += rhs;
    if ((int) value < 0) return -1; // impl. def., 6.3.1.3/3
    *lhs = value;
    return 0;
}

Dies ergibt sowohl Clang als auch GCC:

safe_add:
        add     esi, DWORD PTR [rdi]
        js      .L3
        mov     DWORD PTR [rdi], esi
        xor     eax, eax
        ret
.L3:
        mov     eax, -1
        ret
Konrad Rudolph
quelle
Ich denke, dass die Besetzung im Vergleich undefiniert ist. Aber Sie könnten damit durchkommen, wie ich es in meiner Antwort tue. Aber der ganze Spaß besteht auch darin, alle Fälle abdecken zu können. Ihr _Static_assertdient nicht viel einem Zweck, da dies für jede aktuelle Architektur trivial gilt und sogar für C2x auferlegt wird.
Jens Gustedt
2
@Jens Eigentlich scheint es, dass die Besetzung implementierungsdefiniert und nicht undefiniert ist, wenn ich (ISO / IEC 9899: 2011) 6.3.1.3/3 richtig lese. Können Sie das noch einmal überprüfen? (
Konrad Rudolph
Sie haben Recht, es ist eine Implementierung definiert, kann aber auch ein Signal auslösen :(
Jens Gustedt
@Jens Ja, technisch gesehen enthält die Zweierkomplement-Implementierung möglicherweise noch Füllbytes. Vielleicht sollte der Code dies testen, indem er den theoretischen Bereich mit vergleicht INT_MAX. Ich werde den Beitrag bearbeiten. Andererseits denke ich nicht, dass dieser Code in der Praxis sowieso verwendet werden sollte.
Konrad Rudolph