Существует ли фрагмент кода C, который эффективно вычисляет безопасное переполнение без использования встроенных компиляторов?

11

Вот функция C, которая добавляет intк другому, терпя неудачу, если переполнение произойдет:

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

К сожалению, он не очень хорошо оптимизирован GCC или 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

Эта версия с __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;
        }
}

будет оптимизирован лучше :

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

но мне любопытно, есть ли способ без использования встроенных функций, которые будут сопоставлены с шаблоном GCC или Clang.

Тавиан Барнс
источник
1
Я вижу, что есть gcc.gnu.org/bugzilla/show_bug.cgi?id=48580 в контексте умножения. Но сложение должно быть намного проще для сопоставления с образцом. Я сообщу об этом.
Тавиан Барнс
Сообщено: gcc.gnu.org/bugzilla/show_bug.cgi?id=93742
Барнс

Ответы:

6

Лучшее, что я придумал, если у вас нет доступа к флагу переполнения архитектуры, - это что-то делать unsigned. Просто подумайте обо всей арифметике битов, поскольку нас интересует только старший бит, который является знаковым битом, когда интерпретируется как знаковые значения.

(Все эти ошибки по модулю, я не проверял это подробно, но я надеюсь, что идея ясна)

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

Если вы обнаружите версию дополнения, свободную от UB, например атомарную, ассемблер будет даже без ветвления (но с префиксом блокировки)

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

Так что если бы у нас была такая операция, но еще более «расслабленная», это могло бы еще больше улучшить ситуацию

Take3: если мы используем специальное «приведение» от неподписанного результата к подписанному, это теперь без веток:

#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;
}
Йенс Гастедт
источник
2
Не DV, но я считаю, что второй XOR не следует отрицать. Посмотрите, например, эту попытку проверить все предложения.
Bob__
Я попробовал что-то подобное, но не смог заставить его работать. Выглядит многообещающе, но я бы хотел, чтобы GCC оптимизировал идиоматический код.
R .. GitHub ОСТАНОВИТЬСЯ ПОМОЩЬ ЛЬДУ
1
@PSkocik, нет, это не зависит от представления знака, вычисление полностью выполняется как unsigned. Но это зависит от того факта, что беззнаковый тип имеет не только замаскированный бит знака. (Оба теперь гарантированы в C2x, то есть сохраняются для всех дуг, которые мы могли найти). Тогда вы не можете привести unsignedрезультат обратно, если он больше чем INT_MAX, это будет определено реализацией и может вызвать сигнал.
Йенс Гастедт
1
@PSkocik, к сожалению, нет, это казалось революционным для комитета. Но вот «Take3», который на самом деле выходит без веток на моей машине.
Йенс Гастедт
1
Извините, что беспокою вас снова, но я думаю, что вы должны изменить Take3 на что-то вроде этого, чтобы получить правильные результаты. Хотя это выглядит многообещающе .
Bob__
2

Ситуация с подписанными операциями намного хуже, чем с неподписанными, и я вижу только один шаблон для добавления со знаком, только для clang и только когда доступен более широкий тип:

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 выдает точно такой же asm, как и в __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

В противном случае самое простое решение, которое я могу придумать, - это (с интерфейсом, который использовал Дженс):

_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 и clang генерируют очень похожий ассм . GCC дает это:

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

Мы хотим вычислить сумму в unsigned, поэтому unsignedдолжны иметь возможность представлять все значения intбез слипания между ними. Чтобы легко преобразовать результат из unsignedв int, полезно и обратное. В целом, два дополнения предполагается.

Я думаю, что на всех популярных платформах мы можем unsignedвыполнить преобразование с intпомощью простого назначения, например, int sum = u;но, как упоминал Дженс, даже самый последний вариант стандарта C2x позволяет ему подавать сигнал. Следующий наиболее естественный способ - сделать что-то подобное: *(unsigned *)&sum = u;но варианты дополнения без ловушек, очевидно, могут отличаться для типов со знаком и без знака. Таким образом, приведенный выше пример проходит сложный путь. К счастью, и gcc, и clang оптимизируют это сложное преобразование.

PS Два приведенных выше варианта нельзя сравнивать напрямую, так как они ведут себя по-разному. Первый следует первоначальному вопросу и не забивает *valueв случае переполнения. Второй следует за ответом Йенса и всегда перебивает переменную, на которую указывает первый параметр, но он не имеет ответвлений.

Александр Черепанов
источник
Не могли бы вы показать сгенерированный asm?
R .. GitHub ОСТАНОВИТЬ ЛЬДА
Заменил равенство на xor в проверке переполнения, чтобы улучшить asm с помощью gcc. Добавлен асм.
Александр Черепанов
1

лучшая версия, которую я могу придумать:

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

который производит:

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
Илья Бурсов
источник
Я удивлен даже тем, что не использует флаг переполнения. Все еще намного лучше, чем явные проверки диапазона, но это не обобщает добавление длинных длинных.
Тавиан Барнс
@TavianBarnes вы правы, к сожалению, нет хорошего способа использовать флаги переполнения в c (кроме встроенных компиляторов)
Илья Бурсов
1
Этот код страдает от переполнения со знаком, что является неопределенным поведением.
Emacs сводит меня с ума
@emacsdrivesmenuts, вы правы, приведение в сравнении может быть переполнено.
Йенс Гастедт
@emacsdrivesmenuts Актерский состав не является неопределенным. Когда значение выходит за пределы диапазона int, приведение от более широкого типа либо выдаст значение, определенное реализацией, либо вызовет сигнал. Все реализации, которые мне нужны, определяют его, чтобы сохранить битовый шаблон, который делает правильные вещи.
Тавиан Барнс
0

Я мог бы заставить компилятор использовать флаг знака, предполагая (и утверждая) представление дополнения до двух без заполнения байтов. Такие реализации должны приводить к требуемому поведению в строке, аннотированной комментарием, хотя я не могу найти положительного формального подтверждения этого требования в стандарте (и, вероятно, его нет).

Обратите внимание, что следующий код обрабатывает только положительное целочисленное сложение, но может быть расширено.

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

Это дает и Clang и GCC:

safe_add:
        add     esi, DWORD PTR [rdi]
        js      .L3
        mov     DWORD PTR [rdi], esi
        xor     eax, eax
        ret
.L3:
        mov     eax, -1
        ret
Конрад Рудольф
источник
Я думаю, что актерский состав в сравнении не определен. Но вы можете сойти с рук, как я в моем ответе. Но с другой стороны, все самое интересное в том, что вы можете охватить все случаи. Ваш_Static_assert задача не слишком важна, потому что это тривиально верно для любой современной архитектуры и даже будет навязываться для C2x.
Йенс Гастт
2
@Jens На самом деле кажется, что приведение определено реализацией, а не неопределенно, если я правильно читаю (ISO / IEC 9899: 2011) 6.3.1.3/3. Можете ли вы проверить это еще раз? (Однако распространение этого на отрицательные аргументы делает все это довольно запутанным и в конечном итоге похожим на ваше решение.)
Конрад Рудольф
Вы правы, это определено, но может также подать сигнал :(
Jens Gustedt
@Jens Да, технически я предполагаю, что реализация дополнения до двух может все еще содержать байты заполнения. Может быть, код должен проверить это, сравнив теоретический диапазон сINT_MAX . Я буду редактировать пост. Но опять же, я не думаю, что этот код должен использоваться на практике в любом случае.
Конрад Рудольф