Apakah ada cuplikan C yang menghitung penambahan yang aman-overflow secara efisien tanpa menggunakan kompiler bawaan?

Berikut adalah fungsi C yang menambahkan sebuah intke yang lain, gagal jika terjadi overflow:

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

Sayangnya itu tidak dioptimalkan dengan baik oleh GCC atau Dentang:

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

Versi ini dengan __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;
        }
}

adalah dioptimalkan lebih baik :

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

tapi saya ingin tahu apakah ada cara tanpa menggunakan builtin yang akan mendapatkan kecocokan pola oleh GCC atau Dentang.

Yang terbaik yang saya buat, jika Anda tidak memiliki akses ke bendera arsitektur yang meluap, adalah melakukan sesuatu unsigned. Pikirkan semua aritmatika bit di sini karena kami hanya tertarik pada bit tertinggi, yang merupakan bit tanda ketika ditafsirkan sebagai nilai yang ditandatangani.

(Semua kesalahan tanda modulo, saya tidak memeriksa ini dengan baik, tapi saya harap idenya jelas)

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

Jika Anda menemukan versi tambahan yang bebas dari UB, seperti versi atom, assembler bahkan tanpa cabang (tetapi dengan awalan kunci)

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

Jadi jika kita melakukan operasi seperti itu, tetapi bahkan lebih "santai" ini dapat memperbaiki situasi lebih jauh.

Take3: Jika kami menggunakan "pemeran" khusus dari hasil yang tidak ditandatangani ke yang ditandatangani, sekarang ini bebas cabang:

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

Situasi dengan operasi yang ditandatangani jauh lebih buruk daripada yang tidak ditandatangani, dan saya hanya melihat satu pola untuk penambahan yang ditandatangani, hanya untuk dentang dan hanya ketika jenis yang lebih luas tersedia:

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

dentang memberikan asm persis sama dengan __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

Kalau tidak, solusi paling sederhana yang dapat saya pikirkan adalah ini (dengan antarmuka seperti yang digunakan 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 dan dentang menghasilkan asm sangat mirip . gcc memberikan ini:

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

Kami ingin menghitung jumlahnya unsigned , jadi unsignedharus dapat mewakili semua nilai inttanpa ada yang menyatu. Untuk dengan mudah mengkonversi hasil dari unsignedke int, yang sebaliknya juga berguna. Secara keseluruhan, komplemen dua diasumsikan.

Pada semua platform populer, saya pikir kita dapat mengkonversi dari unsigned ke intdengan penugasan sederhana seperti int sum = u;tetapi, seperti yang disebutkan Jens, bahkan varian terbaru dari standar C2x memungkinkannya untuk menaikkan sinyal. Cara paling alami berikutnya adalah melakukan sesuatu seperti itu: *(unsigned *)&sum = u;tetapi varian padding non-trap tampaknya dapat berbeda untuk tipe yang ditandatangani dan tidak ditandatangani. Jadi contoh di atas berjalan dengan susah payah. Untungnya, baik gcc dan dentang mengoptimalkan konversi rumit ini.

PS Dua varian di atas tidak dapat dibandingkan secara langsung karena mereka memiliki perilaku yang berbeda. Yang pertama mengikuti pertanyaan awal dan tidak mengalahkan *valuejika terjadi overflow. Yang kedua mengikuti jawaban dari Jens dan selalu clobbers variabel yang ditunjukkan oleh parameter pertama tetapi itu tidak memiliki cabang.

versi terbaik yang bisa saya dapatkan adalah:

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

yang menghasilkan:

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

Saya bisa mendapatkan kompiler untuk menggunakan tanda bendera dengan mengasumsikan (dan menyatakan) representasi komplemen dua tanpa padding byte. Implementasi seperti itu harus menghasilkan perilaku yang diperlukan dalam baris yang dijelaskan oleh komentar, walaupun saya tidak dapat menemukan konfirmasi formal positif dari persyaratan ini dalam standar (dan mungkin tidak ada).

Perhatikan bahwa kode berikut hanya menangani penambahan bilangan bulat positif, tetapi dapat diperpanjang.

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

Ini menghasilkan clang dan GCC:

safe_add:
        add     esi, DWORD PTR [rdi]
        js      .L3
        mov     DWORD PTR [rdi], esi
        xor     eax, eax
        ret
.L3:
        mov     eax, -1
        ret