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

[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

[madef]

Лет тридцать прошло с тех пор, как я играл в программиста, но память подсказывает, что в ассемблере х86 для переполнения были специальные флаги OF и CF.

[vak]

Верно, поэтому на архитектурах i686 и amd64 вышеуказанные интринсики сводятся к машинной команде JNO. Которая просто проверяет флаг переполнения.

[ircicq]

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

[vak]

А на MIPS к примеру знаковое сложение или умножение всегда даёт прерывание при переполнении. Глюкавый софт не пройдёт. Именно поэтому MIPS любят для управляющих микропроцессоров в космосе.

[spamsink]

И во сколько команд тогда встаёт знаковое __builtin_mul_overflow?

[archaicos]

Сколько нужно для обработчика прерываний.

[spamsink]

Это будет жутко неэффективно.

[archaicos]

Если задача – обнаружить и сдохнуть, то может проканать.

[spamsink]

Если обнаружить и сдохнуть, то достаточно просто SIGOVFL поймать, и никакие бюилтины не нужны.

А если как-то разумно обрабатывать, то однажды по какой-то причине начавшись, переполнения могут происходить с такой частотой, что восстановление путем перехвата прерываний приведёт к ungraceful degradation, а от этого может сдохнуть не девайс, а пользователь.

[archaicos]

Если сдохнуть мало, тогда пусть вычисляет условие.

[vak]

Соврал я про прерывание при умножении на MIPS. На самом деле умножение всегда выдаёт результат двойной ширины, в регистрах HI и LO. Без всякого переполнения.

[dmarck]

... "в целочисленных"

вот в FPU -- всё "гораздо развесистей, и менее предсказуемо"

[vak]

Как раз с FPU проще: можно заказать прерывание по переполнению и другим флагам. В классических языках типа Фортрана это даже стандартная фича, работает на всех архитектурах.

https://docs.oracle.com/cd/E19957-01/805-4940/z40009062fdd/index.html

[lxe]

Так сдвиг на 64 или на 63? Или mulh выдает не старшее 64-битное слово, а 64-битное окошко на один разряд его младше?

[vak]

С одной стороны неравенства сдвиг 128-битного числа на 64, с другой стороны сдвиг 64-битного числа на 63.

[nz]

в компиляторы GCC и CLANG ввели встроенные функции

В C23 ckd_add, ckd_sub, ckd_mul будут изкоробки.

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

Стоит помнить, что в обратную сторону это не работает.

[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))