Czy istnieje fragment kodu C, który skutecznie oblicza bezpieczny dodatek przed przepełnieniem bez użycia wbudowanych kompilatorów?

11

Oto funkcja C, która dodaje intdo drugiej funkcję, która zawiedzie , jeśli nastąpi przepełnienie:

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

Niestety nie jest dobrze zoptymalizowany przez GCC lub Clang:

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

Ta wersja z __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;
        }
}

jest lepiej zoptymalizowany :

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

ale jestem ciekawy, czy istnieje sposób bez użycia wbudowanych, które zostaną dopasowane do wzorca przez GCC lub Clanga.

Tavian Barnes
źródło
1
Widzę, że istnieje gcc.gnu.org/bugzilla/show_bug.cgi?id=48580 w kontekście mnożenia. Ale dodawanie powinno być znacznie łatwiejsze do dopasowania do wzorca. Zgłosię to.
Tavian Barnes

Odpowiedzi:

6

Najlepszym, jaki wymyśliłem, jeśli nie masz dostępu do flagi przepełnienia architektury, jest robienie rzeczy unsigned. Pomyśl o całej arytmetyce bitów, ponieważ interesuje nas tylko najwyższy bit, który jest bitem znaku interpretowanym jako wartości podpisane.

(Wszystkie te błędy podpisywania modulo, nie sprawdziłem tego dokładnie, ale mam nadzieję, że pomysł jest jasny)

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

Jeśli znajdziesz wersję dodatku wolną od UB, taką jak atomowa, asembler jest nawet bez rozgałęzienia (ale z prefiksem blokady)

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

Gdybyśmy mieli taką operację, ale jeszcze bardziej „zrelaksowaną”, mogłoby to jeszcze bardziej poprawić sytuację.

Take3: Jeśli użyjemy specjalnego „rzutowania” z niepodpisanego wyniku na podpisany, teraz jest on wolny od gałęzi:

#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
źródło
2
Nie DV, ale uważam, że drugiego XOR nie należy negować. Zobacz np. Próbę przetestowania wszystkich propozycji.
Bob__
Próbowałem czegoś takiego, ale nie mogłem tego uruchomić. Wygląda obiecująco, ale chciałbym, aby GCC zoptymalizował kod idiomatyczny.
R .. GitHub ZATRZYMAJ LÓD
1
@PSkocik, nie, to nie zależy od reprezentacji znaku, obliczenia są całkowicie wykonane jak unsigned. Zależy to jednak od tego, że w typie niepodpisanym maskowany jest nie tylko bit znaku. (Obie są teraz gwarantowane w C2x, to znaczy, trzymaj wszystkie łuki, które mogliśmy znaleźć). Następnie nie można rzutować unsignedwyniku z powrotem, jeśli jest on większy niż INT_MAX, byłoby to zdefiniowane w implementacji i może podnieść sygnał.
Jens Gustedt
1
@PSkocik, niestety nie, to wydawało się komunistyczne. Ale oto „Take3”, który faktycznie wychodzi bez rozgałęzień na moim komputerze.
Jens Gustedt
1
Przepraszam, że przeszkadzam ponownie, ale myślę, że należy zmienić Take3 w coś takiego jak ten w celu uzyskania poprawnych wyników. Wydaje się jednak obiecujące .
Bob__
2

Sytuacja z podpisanymi operacjami jest znacznie gorsza niż z niepodpisanymi i widzę tylko jeden wzorzec dla podpisanego dodawania, tylko dla clang i tylko wtedy, gdy dostępny jest szerszy typ:

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 daje dokładnie taki sam asm jak w przypadku __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

W przeciwnym razie najprostszym rozwiązaniem, jakie mogę wymyślić, jest to (z interfejsem używanym przez Jensa):

_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 i clang generują bardzo podobny asm . gcc daje to:

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

Chcemy obliczyć sumę unsigned, więc unsignedmusimy być w stanie przedstawić wszystkie wartości intbez trzymania się jednej z nich. Aby łatwo przekonwertować wynik z unsignednaint , przydatne jest również przeciwieństwo. Ogólnie zakłada się uzupełnienie dwóch.

Na wszystkich popularnych platformach myślę, że możemy przekonwertować z unsignedna intzwykłe zadanie, int sum = u;ale, jak wspomniał Jens, nawet najnowszy wariant standardu C2x pozwala na podniesienie sygnału. Kolejnym najbardziej naturalnym sposobem jest zrobienie czegoś takiego: *(unsigned *)&sum = u;ale warianty wypełnienia bez pułapki najwyraźniej mogą się różnić dla typów podpisanych i niepodpisanych. Powyższy przykład jest trudny. Na szczęście zarówno gcc, jak i clang optymalizują tę trudną konwersję.

PS Dwa powyższe warianty nie mogły być bezpośrednio porównane, ponieważ mają różne zachowanie. Pierwszy podąża za pierwotnym pytaniem i nie blokuje się *valuew przypadku przepełnienia. Drugi podąża za odpowiedzią Jensa i zawsze blokuje zmienną wskazywaną przez pierwszy parametr, ale nie rozgałęzia się.

Aleksander Czerepanow
źródło
Czy możesz pokazać wygenerowany asm?
R .. GitHub ZATRZYMAJ LÓD
Zastąpiono równość xor w kontroli przepełnienia, aby uzyskać lepszy asm z gcc. Dodano asm.
Alexander Cherepanov
1

najlepsza wersja, jaką mogę wymyślić, to:

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

który produkuje:

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
źródło
Jestem zaskoczony, że nawet nie używa flagi przepełnienia. Nadal znacznie lepsze niż jawne sprawdzanie zasięgu, ale nie uogólnia się na dodawanie długich długich.
Tavian Barnes
@TavianBarnes masz rację, niestety nie ma dobrego sposobu na użycie flag przepełnienia w c (oprócz wbudowanych specyficznych dla kompilatora)
Iłya Bursov
1
Ten kod cierpi na przepełnienie ze znakiem, które jest niezdefiniowanym zachowaniem.
emacs doprowadza mnie do szału
@emacsdrivesmenuts, masz rację, obsada w porównaniu może się przepełnić.
Jens Gustedt
@emacsdrivesmenuts Obsada nie jest niezdefiniowana. Gdy jest poza zakresem int, rzutowanie z szerszego typu spowoduje albo wygenerowanie wartości zdefiniowanej przez implementację, albo podniesienie sygnału. Wszystkie implementacje, które dbam o to, aby to zdefiniować, aby zachować wzór bitów, który działa prawidłowo.
Tavian Barnes
0

Mógłbym zmusić kompilator do używania flagi znaku, zakładając (i potwierdzając) reprezentację dopełniacza dwóch bez wypełniania bajtów. Takie wdrożenia powinny dać wymagane zachowanie w wierszu opatrzonym komentarzem, chociaż nie mogę znaleźć pozytywnego formalnego potwierdzenia tego wymogu w standardzie (i prawdopodobnie nie ma takiego).

Zauważ, że poniższy kod obsługuje tylko dodatnie dodawanie liczb całkowitych, ale można je rozszerzyć.

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

Daje to zarówno clang, jak i 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
źródło
Myślę, że obsada w porównaniu jest niezdefiniowana. Ale możesz uciec od tego, tak jak ja w mojej odpowiedzi. Ale wtedy cała zabawa polega na tym, że mogę objąć wszystkie sprawy. Twój _Static_assertcel nie ma większego sensu, ponieważ jest to trywialnie prawdziwe w każdej obecnej architekturze, a nawet zostanie narzucone dla C2x.
Jens Gustedt
2
@Jens Właściwie wydaje się, że obsada jest zdefiniowana w implementacji, a nie niezdefiniowana, jeśli czytam (ISO / IEC 9899: 2011) 6.3.1.3/3 poprawnie. Czy możesz to dwukrotnie sprawdzić? (Jednak rozszerzenie tego na argumenty negatywne sprawia, że ​​cała sprawa jest raczej skomplikowana i ostatecznie podobna do twojego rozwiązania.)
Konrad Rudolph
Masz rację, to jest zdefiniowane uzupełnienie, ale może również podnieść sygnał :(
Jens Gustedt
@Jes Tak, technicznie wydaje mi się, że implementacja uzupełnienia dwóch może nadal zawierać bajty dopełniania. Może kod powinien to sprawdzić, porównując zakres teoretyczny z INT_MAX. Zmienię post. Ale z drugiej strony nie sądzę, aby ten kod i tak był wykorzystywany w praktyce.
Konrad Rudolph