Existe um trecho de código C que calcula a adição segura contra transbordamento de forma eficiente sem o uso de componentes internos do compilador?

11

Aqui está uma função C que adiciona um inta outro, falhando se o estouro acontecer:

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

Infelizmente, ele não é otimizado bem pelo GCC ou pelo 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

Esta versão com __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;
        }
}

é otimizado melhor :

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

mas estou curioso para saber se existe uma maneira, sem usar os built-in, que correspondam aos padrões do GCC ou do Clang.

Tavian Barnes
fonte
11
Vejo que há gcc.gnu.org/bugzilla/show_bug.cgi?id=48580 no contexto da multiplicação. Mas a adição deve ser muito mais fácil de corresponder aos padrões. Vou denunciá-lo.
Tavian Barnes 14/02

Respostas:

6

A melhor que eu criei, se você não tiver acesso ao sinalizador de estouro da arquitetura, é fazer as coisas unsigned. Basta pensar em toda aritmética de bits aqui, pois estamos interessados ​​apenas no bit mais alto, que é o bit de sinal quando interpretado como valores assinados.

(Todos esses erros de sinal de módulo, eu não verifiquei isso completamente, mas espero que a idéia seja clara)

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

Se você encontrar uma versão da adição livre de UB, como uma atômica, o assembler fica sem ramificação (mas com um prefixo de bloqueio)

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

Portanto, se tivéssemos essa operação, mas ainda mais "relaxada", isso poderia melhorar ainda mais a situação.

Take3: se usarmos um "elenco" especial do resultado não assinado para o assinado, isso agora é gratuito:

#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
fonte
2
Não é o DV, mas acredito que o segundo XOR não deve ser negado. Veja, por exemplo, esta tentativa de testar todas as propostas.
Bob__ 14/02
Eu tentei algo assim, mas não consegui fazê-lo funcionar. Parece promissor, mas eu gostaria que o GCC otimizasse o código idiomático.
R .. GitHub Pare de ajudar o gelo
11
@PSkocik, não, isso não depende da representação do sinal, o cálculo é feito inteiramente como unsigned. Mas isso depende do fato de o tipo não assinado não ter apenas o bit de sinal mascarado. (Ambos agora estão garantidos no C2x, ou seja, valem para todos os arcos que pudemos encontrar). Então, você não pode converter o unsignedresultado de volta, se for maior que INT_MAX, isso seria definido pela implementação e pode gerar um sinal.
Jens Gustedt 14/02
11
@PSkocik, infelizmente não, isso pareceu revolucionário para o comitê. Mas aqui está um "Take3" que sai real sem ramificações na minha máquina.
Jens Gustedt 14/02
11
Desculpe incomodá-lo novamente, mas eu acho que você deveria mudar Take3 em algo parecido com isso para obter resultados correctos. Parece promissor , no entanto.
Bob__ 14/02
2

A situação com operações assinadas é muito pior do que com operações não assinadas, e vejo apenas um padrão para adição assinada, apenas para clang e somente quando um tipo mais amplo está disponível:

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

O clang fornece exatamente o mesmo asm de __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

Caso contrário, a solução mais simples que consigo pensar é esta (com a interface usada pelo 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 e clang geram asm muito semelhante . O gcc fornece isso:

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

Queremos calcular a soma em unsigned, portanto, unsignedprecisamos representar todos os valores intsem que nenhum deles fique junto. Para converter facilmente o resultado de unsignedpara int, o oposto também é útil. No geral, o complemento de dois é assumido.

Em todas as plataformas populares, acho que podemos converter de unsignedpara intatravés de uma atribuição simples como int sum = u;, mas, como Jens mencionou, até a mais recente variante do padrão C2x permite gerar um sinal. A próxima maneira mais natural é fazer algo assim: *(unsigned *)&sum = u;mas as variantes não preenchidas de preenchimento aparentemente podem diferir para tipos assinados e não assinados. Portanto, o exemplo acima segue o caminho mais difícil. Felizmente, o gcc e o clang otimizam essa conversão complicada.

PS As duas variantes acima não puderam ser comparadas diretamente, pois apresentam um comportamento diferente. O primeiro segue a pergunta original e não derruba o *valueem caso de estouro. O segundo segue a resposta de Jens e sempre reprova a variável apontada pelo primeiro parâmetro, mas é sem ramificação.

Alexander Cherepanov
fonte
Você poderia mostrar o asm gerado?
R .. GitHub Pare de ajudar o gelo
Igualdade substituída por xor na verificação de estouro para melhorar o asm com o gcc. Adicionado asm.
Alexander Cherepanov 18/02
1

a melhor versão que posso apresentar é:

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

que produz:

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
fonte
Estou surpreso, mesmo que não use o sinalizador de estouro. Ainda muito melhor do que as verificações explícitas de intervalo, mas não generaliza a adição de longos longos.
Tavian Barnes
@TavianBarnes você está certo, infelizmente não há uma boa maneira de usar sinalizadores de estouro em c (exceto compilações específicas do compilador)
Iłya Bursov
11
Esse código sofre de estouro assinado, que é comportamento indefinido.
emacs me deixa louco
@emacsdrivesmenuts, você está certo, o elenco da comparação pode transbordar.
Jens Gustedt 14/02
@emacsdrivesmenuts O elenco não é indefinido. Quando fora da faixa de int, uma conversão de um tipo mais amplo produzirá um valor definido pela implementação ou aumentará um sinal. Todas as implementações que me interessam definem para preservar o padrão de bits que faz a coisa certa.
Tavian Barnes 14/02
0

Eu poderia fazer com que o compilador usasse o sinalizador assumindo (e afirmando) uma representação de complemento de dois sem preencher bytes. Tais implementações devem produzir o comportamento exigido na linha anotada por um comentário, embora eu não consiga encontrar uma confirmação formal positiva desse requisito no padrão (e provavelmente não exista).

Observe que o código a seguir lida apenas com adição positiva de número inteiro, mas pode ser estendido.

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

Isso gera clang e 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
fonte
Eu acho que o elenco da comparação é indefinido. Mas você pode se safar disso, como eu faço na minha resposta. Mas também é divertido poder cobrir todos os casos. Seu _Static_assertobjetivo não é muito objetivo, porque isso é trivialmente verdadeiro em qualquer arquitetura atual e será imposto até para o C2x.
Jens Gustedt 14/02
2
@ Jens Na verdade, parece que o elenco é definido pela implementação, não indefinido, se estou lendo (ISO / IEC 9899: 2011) 6.3.1.3/3 corretamente. Você pode verificar isso? (No entanto, estendendo isso para argumentos negativos torna a coisa toda bastante complicadas e, finalmente, semelhante à sua solução.)
Konrad Rudolph
Você está certo, é a implementação definida, mas também pode gerar um sinal :(
Jens Gustedt 14/02
@ Jens Sim, tecnicamente eu acho que a implementação do complemento de dois ainda pode conter bytes de preenchimento. Talvez o código deva testar isso comparando o intervalo teórico a INT_MAX. Eu vou editar a postagem. Mas, novamente, não acho que esse código deva ser usado na prática de qualquer maneira.
Konrad Rudolph