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

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.

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

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

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

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