Existe-t-il un extrait de code C qui calcule efficacement l'addition sans débordement sans utiliser les compilations internes du compilateur?

11

Voici une fonction C qui ajoute un intà un autre, échouant en cas de débordement:

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

Malheureusement, il n'est pas bien optimisé par GCC ou 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

Cette version avec __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;
        }
}

est mieux optimisé :

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

mais je suis curieux de savoir s'il existe un moyen sans utiliser de modules intégrés qui seront mis en correspondance par GCC ou Clang.

Tavian Barnes
la source
1
Je vois qu'il y a gcc.gnu.org/bugzilla/show_bug.cgi?id=48580 dans le contexte de la multiplication. Mais l'addition devrait être beaucoup plus facile à faire correspondre. Je vais le signaler.
Tavian Barnes

Réponses:

6

Le meilleur que j'ai trouvé, si vous n'avez pas accès au drapeau de débordement de l'architecture, c'est de faire les choses dans unsigned . Pensez simplement à toute l'arithmétique des bits ici en ce que nous ne sommes intéressés que par le bit le plus élevé, qui est le bit de signe lorsqu'il est interprété comme des valeurs signées.

(Toutes ces erreurs de signature modulo, je n'ai pas vérifié cela à fond, mais j'espère que l'idée est claire)

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

Si vous trouvez une version de l'addition qui est exempte d'UB, comme une version atomique, l'assembleur est même sans branche (mais avec un préfixe de verrouillage)

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

Donc, si nous avions une telle opération, mais encore plus "détendue", cela pourrait encore améliorer la situation.

Take3: Si nous utilisons un "cast" spécial du résultat non signé au résultat signé, celui-ci est maintenant sans branche:

#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
la source
2
Pas le DV, mais je pense que le deuxième XOR ne doit pas être annulé. Voir par exemple cette tentative de tester toutes les propositions.
Bob__
J'ai essayé quelque chose comme ça, mais je n'ai pas réussi à le faire fonctionner. Semble prometteur mais je souhaite que GCC optimise le code idiomatique.
R .. GitHub STOP HELPING ICE
1
@PSkocik, non cela ne dépend pas de la représentation des signes, le calcul se fait entièrement comme unsigned. Mais cela dépend du fait que le type non signé n'a pas seulement le bit de signe masqué. (Les deux sont maintenant garantis dans C2x, c'est-à-dire, valables pour toutes les arches que nous pourrions trouver). Ensuite, vous ne pouvez pas unsignedrestituer le résultat s'il est supérieur à INT_MAX, cela serait défini par l'implémentation et pourrait déclencher un signal.
Jens Gustedt
1
@PSkocik, non malheureusement non, cela semblait revolutianary au comité. Mais voici un "Take3" qui sort sans branches sur ma machine.
Jens Gustedt
1
Désolé de vous déranger encore, mais je pense que vous devriez changer Take3 en quelque chose comme ça pour obtenir des résultats corrects. Cela semble cependant prometteur .
Bob__
2

La situation avec les opérations signées est bien pire qu'avec les opérations non signées, et je ne vois qu'un seul modèle pour l'addition signée, uniquement pour clang et uniquement lorsqu'un type plus large est disponible:

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 donne exactement le même asm qu'avec __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

Sinon, la solution la plus simple à laquelle je peux penser est la suivante (avec l'interface utilisée par 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 et clang génèrent un asm très similaire . gcc donne ceci:

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

Nous voulons calculer la somme unsigned, donc unsignednous devons être en mesure de représenter toutes les valeurs de intsans qu'aucune d'entre elles ne collent ensemble. Pour convertir facilement le résultat de unsignedenint , l'inverse est également utile. Dans l'ensemble, le complément à deux est supposé.

Sur toutes les plates-formes populaires, je pense que nous pouvons convertir de unsignedà intpar une simple affectation comme int sum = u;mais, comme Jens l'a mentionné, même la dernière variante de la norme C2x lui permet d'augmenter le signal. La prochaine façon la plus naturelle est de faire quelque chose comme ça: *(unsigned *)&sum = u;mais les variantes de remplissage non-trap pourraient apparemment différer pour les types signés et non signés. L'exemple ci-dessus va donc très mal. Heureusement, gcc et clang optimisent cette conversion délicate.

PS Les deux variantes ci-dessus n'ont pas pu être comparées directement car elles ont un comportement différent. La première fait suite à la question d'origine et n'encombre pas *valueen cas de débordement. Le second suit la réponse de Jens et frappe toujours la variable pointée par le premier paramètre mais elle est sans branche.

Alexander Cherepanov
la source
Pourriez-vous montrer le asm généré?
R .. GitHub STOP STOPINGING ICE
Egalité remplacée par xor dans la vérification de débordement pour obtenir un meilleur asm avec gcc. Ajouté asm.
Alexander Cherepanov
1

la meilleure version que je puisse proposer est:

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

qui produit:

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
la source
Je suis même surpris de ne pas utiliser l'indicateur de débordement. Encore beaucoup mieux que les vérifications de plage explicites, mais cela ne se généralise pas à l'ajout de longs longs.
Tavian Barnes
@TavianBarnes vous avez raison, malheureusement il n'y a pas de bon moyen d'utiliser les drapeaux de débordement en c (à l'exception des fonctionnalités spécifiques au compilateur)
Iłya Bursov
1
Ce code souffre d'un débordement signé, qui est un comportement indéfini.
emacs me rend
@emacsdrivesmenuts, vous avez raison, le casting du comparisson peut déborder.
Jens Gustedt
@emacsdrivesmenuts La distribution n'est pas indéfinie. Une fois hors de la plage de int, une distribution d'un type plus large produira une valeur définie par l'implémentation ou augmentera un signal. Toutes les implémentations qui m'intéressent le définissent pour préserver le modèle de bits qui fait la bonne chose.
Tavian Barnes
0

Je pourrais amener le compilateur à utiliser l'indicateur de signe en supposant (et en affirmant) une représentation du complément à deux sans remplissage d'octets. Ces mises en œuvre devraient produire le comportement requis dans la ligne annotée par un commentaire, bien que je ne puisse pas trouver de confirmation formelle positive de cette exigence dans la norme (et il n'y en a probablement pas).

Notez que le code suivant ne gère que l'addition d'entiers positifs, mais peut être étendu.

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

Cela donne à la fois clang et 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
la source
Je pense que le casting dans la comparaison n'est pas défini. Mais vous pourriez vous en tirer comme je le fais dans ma réponse. Mais aussi, tout le plaisir est de pouvoir couvrir tous les cas. Votre _Static_assertne sert pas à grand - chose, parce que cela est trivialement vrai sur toute architecture actuelle, et sera même imposée pour C2x.
Jens Gustedt
2
@Jens En fait, il semble que la distribution soit définie par l'implémentation, et non indéfinie, si je lis correctement (ISO / IEC 9899: 2011) 6.3.1.3/3. Pouvez-vous vérifier cela? (Cependant, étendre cela à des arguments négatifs rend le tout plutôt compliqué et finalement similaire à votre solution.)
Konrad Rudolph
Vous avez raison, c'est une implémentation définie, mais cela peut aussi
donner
@Jens Oui, techniquement, je suppose que l'implémentation d'un complément à deux peut toujours contenir des octets de remplissage. Peut-être que le code devrait tester cela en comparant la plage théorique à INT_MAX. Je vais éditer le post. Mais là encore, je ne pense pas que ce code devrait être utilisé dans la pratique de toute façon.
Konrad Rudolph