Сложить-умножить два числа

[vak]

Представьте, что вам в программе нужно сложить два целых числа. Получили некий ответ, скажем 42. Верный ли это результат? А вдруг произошло переполнение, и на самом деле вышло огромное число, но не поместилось в размер переменной? Большинство языков программирования помочь не могут.

Для многих применений оно может и некритично, но что если вы делает софт для тормозной системы автомобиля. Или для импланта стимулятора сердца. От такой мелочи как переполнение кое-кто может тут же отдать богу душу.

На некоторых архитектурах целочисленное переполнение вызывает прерывание выполнения программы. В надежде, что софт умеет восстанавливаться после сбоя. Но большинство современных процессоров такого не умеют.

Не так давно в компиляторы GCC и CLANG ввели встроенные функции, чтобы отлавливать переполнение. Посмотрим, как эта штука работает.

Сложение

int64_t a, b, c;
if (__builtin_add_overflow(a, b, &c)) {
    // переполнение
}

Компилируем для riscv64. Конструкция превращается в машинные команды:

add     a4, a2, a3          # a4 = a + b
slti    a1, a3, 0           # a1 = (b < 0)
slt     a5, a4, a2          # a5 = (a + b < a)
bne     a1, a5, overflow    # (b < 0) != (a + b < a) ? overflow

Это эквивалентно Си-шному коду:

int64_t a, b, c;
c = a + b;
if ((b < 0) != (c < a)) {
    // переполнение
}

Вполне эффективное решение.

Умножение

Интересно, как компилятор сделает проверку переполнения при умножении.

int64_t a, b, c;
if (__builtin_mul_overflow(a, b, &c)) {
    // переполнение
}

Смотрим машинный код для riscv64.

mul     a4, a2, a3          # a4 = (a * b) bits 63:0
mulh    a1, a2, a3          # a1 = (a * b) >> 64
srai    a5, a4, 63          # a5 = (int64_t) (a * b) >> 63
bne     a1, a5, overflow    # (a * b) >> 64 != (int64_t) (a * b) >> 63 ? overflow

На Си это выглядело бы:

int64_t a, b, c;
c = a * b;
if (((int128_t)a * b) >> 64 != c >> 63) {
    // переполнение
}

Неплохо придумано. К счастью, на RISC-V имеется хитрая команда MULH, которая умножает два 64-битных целых и выдаёт старшие 64 бита результата.

Comments

[vak]

Интересно, надо будет потестировать эти ckd_add, ckd_sub, ckd_mul на RISC-V.

А не работает в обратную сторону вероятно потому, что компилятор при сложении предполагает отсутствие переполнения, и поэтому оптимизатор выбрасывает весь код как несущественный.

[nz]

Скорее всего это будут тонкие обертки над теми же __builtin_*.

Именно так: переполнение знакового - UB, UB в корректных программах не бывает, значит функцию будут вызывать только с аргументами, не вызывающими переполнения, значит проверять не надо.

[vak]

Действительно, в файле stdckdint.h всё тривиально:

#define ckd_add(R, A, B) __builtin_add_overflow((A), (B), (R))
#define ckd_sub(R, A, B) __builtin_sub_overflow((A), (B), (R))
#define ckd_mul(R, A, B) __builtin_mul_overflow((A), (B), (R))