[c] проверка на переполнение для разных типов - C/C++

Нужно уметь просто проверять на переполнение для ряда операций над примитивными типами. Пока не придумал ничего лучше кучи функций вида

bool ovc_ssize_plus_ssize(ssize_t x, ssize_t y) {
  if (x >= 0) {
    return SSIZE_MAX - x >= y;
  } else {
    return SSIZE_MIN - x <= y;
  }
}

для используемых сочетаний типов и операций.

Может быть есть вариант попроще? В идеале какой-нибудь флажок для компилятора понавтыкать проверок на overflow flag после каждой арифметической операции. Не в идеале уже написанные кем-нибудь такие проверки в виде мини-библиотеки.

Интересует именно C, для C++ есть SafeInt. Для C вроде есть IntSafe от микрософта, но там только unsigned типы, что меня сбивает с толку. А что если мне надо от unsigned отнять signed? конвертировать signed в unsigned смысла нет, т.к. это уже другая семантика переполнения.

Здравствуйте, vsb, Вы писали:

vsb>Может быть есть вариант попроще?

В идеале нет ничего проще JO to_overflow_hand

Здравствуйте, vsb, Вы писали:

vsb>Нужно уметь просто проверять на переполнение для ряда операций над примитивными типами. Пока не придумал ничего лучше

vsb>Интересует именно C


 int mull(int a, int b){
 int res;
__asm __volatile__  (

    "movl %1, %%eax \t\n"
    "imull %2 \t\n"
    "jno f \t\n"
    "movl $0xffffffff, %%eax \t\n"
    "f: movl %%eax, %0 \t\n"
    : "=m" (res)
    : "r" (a), "r" (b)
    :
      );
return res;
};

Здравствуйте, vsb, Вы писали:

vsb>Интересует именно C, для C++ есть SafeInt. Для C вроде есть IntSafe от микрософта, но там только unsigned типы, что меня сбивает с толку. А что если мне надо от unsigned отнять signed? конвертировать signed в unsigned смысла нет, т.к. это уже другая семантика переполнения.

Проблема в том, что тут уже неоднократно озвучивалось: сложение знаковых целых с переполнением это UB (undefined behavior).
Поэтому вариант складывать через unsigned, конвертировать снова в signed и смотреть на знак — вполне неплохой.
Хотя для контроля переполнения при умножении это не сработает, а контролировать делением — изуверски дорого, там уже только ассемблер (или, как в SafeInt3, умножение более широких, но это тоже дорого).

Здравствуйте, smeeld, Вы писали:

vsb>>Может быть есть вариант попроще?

S>В идеале нет ничего проще JO to_overflow_hand

x86 only? Завтра придётся запускаться на ARM или Risc-V

Здравствуйте, vsb, Вы писали:

vsb>Нужно уметь просто проверять на переполнение для ряда операций над примитивными типами. Пока не придумал ничего лучше кучи функций вида

А какое поведение нужно при переполнении?
— считать как попало и выдать диагностику
— с насыщением до максимального значения и выдать диагностику
— с насыщением до "условной бесконечности" и "неопределённости" (INF,NAN)
— прекратить вычисления и выдать диагностику
— прекратить вычисления и послать сигнал

Можно так: как попало, диагностика

bool overflown = false;

unsigned plus(unsigned x, unsigned y)
{
  overflown |= (x/2 + y/2 > UINT_MAX/2);
  return x+y;
}
unsigned minus(unsigned x, unsigned y)
{
  overflown |= (x < y);
  return x-y;
}
unsigned multiply(unsigned x, unsigned y)
{
  overflown |= (x>1 && y>1 && x > UINT_MAX/y);
  return x*y;
}
unsigned divide(unsigned x, unsigned y)
{
  overflown |= (y==0);
  return x/y;
}

int main()
{
  unsigned z = multiply(plus(1U<<30, 3U<<30), minus(1,2)); // да, формулу придётся в префиксном виде писать
  printf("%s %u\n", overflown ? "ok" : "overflown", z);
}

Насыщение до бесконечности

// придётся пожертвовать двумя точками из диапазона всех чисел...
unsigned const uint_nan = ~0U;
unsigned const uint_inf = ~0U-1;

unsigned const uint_max = ~0U-2;

unsigned plus(unsigned x, unsigned y)
{
  if(x == uint_nan || y == uint_nan) return uint_nan;
  if(x == uint_inf || y == uint_inf) return uint_inf;
  if(x/2 + y/2 > uint_max/2) return uint_inf; // насыщение - прижимаем к oo
  return x+y;
}
unsigned plus(unsigned x, unsigned y)
{
  if(x == uint_nan || y == uint_nan) return uint_nan;
  if(x == uint_inf && y == uint_inf) return uint_nan; oo-oo = xz
  if(x < y) return 0; // насыщение - прижимаем к 0
  return x+y;
}

И т.п.

Здравствуйте, netch80, Вы писали:

vsb>>Интересует именно C, для C++ есть SafeInt. Для C вроде есть IntSafe от микрософта, но там только unsigned типы, что меня сбивает с толку. А что если мне надо от unsigned отнять signed? конвертировать signed в unsigned смысла нет, т.к. это уже другая семантика переполнения.

N>Проблема в том, что тут уже неоднократно озвучивалось: сложение знаковых целых с переполнением это UB (undefined behavior).
N>Поэтому вариант складывать через unsigned, конвертировать снова в signed и смотреть на знак — вполне неплохой.

Есть простой способ проверять перед сложением — будет overflow или нет, и в проверке нет UB. Собственно в первом сообщении этот код и показан.

Если конвертировать, то, например, будет проблема в таком случае:

unsigned char x = 1;
signed char y = -1; // 255
unsigned char x = checked_char_plus(x, (unsigned char) y);

1 + 255 = 256 = 0. Будет поймано переполнение. Но x + y в данном случае семантически значит 1 + (-1) = 0 и никакого переполнения тут нет, абсолютно нормальный код, т.е. false positive, если можно так выразиться.

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

N>Хотя для контроля переполнения при умножении это не сработает, а контролировать делением — изуверски дорого, там уже только ассемблер (или, как в SafeInt3, умножение более широких, но это тоже дорого).

Мне пока надо для дебаг-сборки, чтобы тесты валились (ну или у тестеров валилось) в корку, если вдруг где пролезла такая ситуация. Поэтому на производительность в разумной мере пофиг.

Здравствуйте, Кодт, Вы писали:

vsb>>Нужно уметь просто проверять на переполнение для ряда операций над примитивными типами. Пока не придумал ничего лучше кучи функций вида

К>А какое поведение нужно при переполнении?
К>- считать как попало и выдать диагностику
К>- с насыщением до максимального значения и выдать диагностику
К>- с насыщением до "условной бесконечности" и "неопределённости" (INF,NAN)
К>- прекратить вычисления и выдать диагностику
К>- прекратить вычисления и послать сигнал

Хотелось бы функций того вида, которого я написал, чтобы можно было писать assert(check_plus(x, y)) в нужных местах ну или отдельные функции asserted_plus(x, y), которые в релизной сборке скорее всего заинлайнятся в виде x + y, а в дебаг сборке будет assert.

К>Можно так: как попало, диагностика

скрыто

К>

К>bool overflown = false;

К>unsigned plus(unsigned x, unsigned y)
К>{
К>  overflown |= (x/2 + y/2 > UINT_MAX/2);
К>  return x+y;
К>}
К>unsigned minus(unsigned x, unsigned y)
К>{
К>  overflown |= (x < y);
К>  return x-y;
К>}
К>unsigned multiply(unsigned x, unsigned y)
К>{
К>  overflown |= (x>1 && y>1 && x > UINT_MAX/y);
К>  return x*y;
К>}
К>unsigned divide(unsigned x, unsigned y)
К>{
К>  overflown |= (y==0);
К>  return x/y;
К>}

К>int main()
К>{
К>  unsigned z = multiply(plus(1U<<30, 3U<<30), minus(1,2)); // да, формулу придётся в префиксном виде писать
К>  printf("%s %u\n", overflown ? "ok" : "overflown", z);
К>}
К>

К>Насыщение до бесконечности
К>

К>// придётся пожертвовать двумя точками из диапазона всех чисел...
К>unsigned const uint_nan = ~0U;
К>unsigned const uint_inf = ~0U-1;

К>unsigned const uint_max = ~0U-2;

К>unsigned plus(unsigned x, unsigned y)
К>{
К>  if(x == uint_nan || y == uint_nan) return uint_nan;
К>  if(x == uint_inf || y == uint_inf) return uint_inf;
К>  if(x/2 + y/2 > uint_max/2) return uint_inf; // насыщение - прижимаем к oo
К>  return x+y;
К>}
К>unsigned plus(unsigned x, unsigned y)
К>{
К>  if(x == uint_nan || y == uint_nan) return uint_nan;
К>  if(x == uint_inf && y == uint_inf) return uint_nan; oo-oo = xz
К>  if(x < y) return 0; // насыщение - прижимаем к 0
К>  return x+y;
К>}
К>

К>И т.п.

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

Здравствуйте, vsb, Вы писали:

vsb>Хотелось бы функций того вида, которого я написал, чтобы можно было писать assert(check_plus(x, y)) в нужных местах ну или отдельные функции asserted_plus(x, y), которые в релизной сборке скорее всего заинлайнятся в виде x + y, а в дебаг сборке будет assert.

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

#define BIT_SIZE(x) (sizeof(x) * 8)

template <typename T>
bool check_plus(T x, T y)
{
    T res = x + y;
    bool overflow = (((x ^ res) & (y ^ res)) >> (BIT_SIZE(T) - 1)) & 1;
    return !overflow;
}

signed overflow -- не, не слышал!

Здравствуйте, watchyourinfo, Вы писали:

W>signed overflow -- не, не слышал!

Ну, если у него есть всегда возможность потребовать -fwrapv для конкретного участка кода, то почему бы и нет?

Здравствуйте, vsb, Вы писали:

vsb>Есть простой способ проверять перед сложением — будет overflow или нет, и в проверке нет UB. Собственно в первом сообщении этот код и показан.

Эээ, вот тут есть тонкость. Твой пример возвращает просто признак переполнения. А что вернёт собственно код такой checked_add()? Если он выглядит, например, так

int checked_add(int x, int y, int *ovf) {
  *ovf = check_add_ovf(x, y);
  return x + y;
}

то независимо от того, что ты проверил переполнение и на него дальше реагируешь, компилятор, видя безусловное сложение, может это интерпретировать как "тут всё чисто" (стандартное поведение gcc).

Только если ты сделаешь что-то вида

int checked_add(int x, int y, int *ovf) {
  *ovf = check_add_ovf(x, y);
  return *ovf ? 0 : x + y;
}

то есть проблемное сложение будет под условием — только тогда на его основании не соптимизируют чего не положено.

Позже ты написал, что хочешь делать, чтобы был assert в случае debug mode. С учётом того, что выпадение по такому assert обычно noreturn, это должно сработать. Но на момент моего предыдущего ответа это не было сказано.

vsb>Если конвертировать, то, например, будет проблема в таком случае:

vsb>

vsb>unsigned char x = 1;
vsb>signed char y = -1; // 255
vsb>unsigned char x = checked_char_plus(x, (unsigned char) y);
vsb>

vsb>1 + 255 = 256 = 0. Будет поймано переполнение. Но x + y в данном случае семантически значит 1 + (-1) = 0 и никакого переполнения тут нет, абсолютно нормальный код, т.е. false positive, если можно так выразиться.
vsb>Может быть ещё какие-нибудь случаи есть из той же оперы. Поэтому по-хорошему с каждым сочетанием типов должна быть прописана своя логика.

Верно. Именно поэтому в SafeInt3 пачка случаев, 10-15 на каждую базовую операцию, по комбинациям размерности.

N>>Хотя для контроля переполнения при умножении это не сработает, а контролировать делением — изуверски дорого, там уже только ассемблер (или, как в SafeInt3, умножение более широких, но это тоже дорого).
vsb>Мне пока надо для дебаг-сборки, чтобы тесты валились (ну или у тестеров валилось) в корку, если вдруг где пролезла такая ситуация. Поэтому на производительность в разумной мере пофиг.

Я всё-таки предлагаю подумать про ассемблерную поддержку. Особенно если это под gcc, где выход ассемблера встраиваемый в код без внешних функций.
Написать код для пары основных платформ для теста не будет сложным, а облегчение заметное (ещё раз напоминаю про умножение, где ловить факт переполнения без ассемблерной поддержки сложнее всего).

	От:	vsb
	Дата:	04.10.14 16:37
	Оценка:

	От:	smeeld
	Дата:	04.10.14 17:26
	Оценка:	-1

	От:	smeeld
	Дата:	04.10.14 19:27
	Оценка:	4 (1)

От:	netch80	http://netch80.dreamwidth.org/
Дата:	06.10.14 14:29
Оценка:

От:	netch80	http://netch80.dreamwidth.org/
Дата:	06.10.14 14:29
Оценка:

	От:	cserg
	Дата:	07.10.14 01:03
	Оценка:	-1

	От:	watchyourinfo
	Дата:	07.10.14 02:38
	Оценка: