none
Язык С, арифметическое переполнение

    Вопрос

  • Здравствуйте, подскажите, как правильно в C обрабатывать арифметическое переполнение знаковых и беззнаковых целых?

    1) Контроль переполнения при сложении беззнаковых осуществляется довольно просто, потому что по Стандарту - переполнение  беззнаковых, в отличии от переполнения знаковых, не приводит к неопределенному поведению:

    uint8_t a, b, c;
    c = a + b;

    if (c < a) { /*Переполнение.*/ }

    Относительно данной ситуации у меня есть только один вопрос, действительно ли при переполнении c всегда будет меньше любого из слагаемых? В том смысле, достаточно ли вышеприведенного сравнения, или нужно использовать (c<a)||(c<b)?

    2) Контроль переполнения знаковых несколько "объемнее", учитывая, что проверку нужно выполнять до самой операции. Но в целом - вопросов нет.

    3) Как правильно контролировать переполнение при умножении обоих видов целых? Есть ли какие-то проверенные и обкатанные решения, чтобы не изобретать велосипедов и не писать вставки на ассемблере, которые еще и не факт, что будут работать на другом процессоре / компиляторе / ОС?

    Я перерыл много литературы и мнений, но к единому решению так и не пришел.

    Для беззнаковых целых, предположительно, справедливо следующее:

    uint8_t a, b, c;
    c = a * b;
    if ( (c == 0) || (c/a != b) ) { /*Переполнение.*/ }

    При условии, что a != 0, и b != 0.

    Это так?







    • Изменено MGNeo 13 марта 2018 г. 12:49
    13 марта 2018 г. 12:40

Ответы

  • Собственно, вы сами ответили: стандартного способа нет. Ваши проверки работают, но лучше бы использовать специальные функции компилятора для этих целей. Думаю, так быстрее будет (хотя, я не измерял), да и код получается более естественный.

    В Visual Studio - функции из Intsafe.h

    #include <stdlib.h> #include <stdio.h> #include <windows.h> #include <tchar.h> #include <Intsafe.h> int _tmain(int argc, _TCHAR* argv[]) { ULONGLONG a=100000000000, b=5000000000, c; HRESULT hr = ULongLongMult(a,b,&c);

    if(SUCCEEDED(hr)) printf("Result is %llu",c); else if(hr==INTSAFE_E_ARITHMETIC_OVERFLOW) printf("Overflow"); else printf("Error occured"); return 0; }

    (Для использования операций со знаковыми числами нужно определить ENABLE_INTSAFE_SIGNED_FUNCTIONS перед включением заголовочного файла.)

    Эти функции определены как inline, в зависимости от архитектуры процессора они используют либо intrinsic-функции компилятора, либо специальный алгоритм с разбиением операндов на 2 32-битных компонента, позволяющий отловить переполнение по значениям определенных битов. Можно открыть сам заголовочный файл и посмотреть.

    В GCC - builtin-функции



    • Помечено в качестве ответа MGNeo 14 марта 2018 г. 6:03
    • Изменено VadimTagil 14 марта 2018 г. 7:41
    14 марта 2018 г. 5:58

Все ответы

  • Поясните для чего вы это делайте?

    В любом случае типично вопрос решается недопущением переполнения. Например, c объявляется как int, ну а дальше все очевидно. То же и при умножении. 



    This posting is provided "AS IS" with no warranties, and confers no rights.

    13 марта 2018 г. 16:24
  • В основном проверки нужны при определении размеров пространства данных хэш-таблицы.

    data_size = ((sizeof(size_t) + record_size) * cluster_capacity + sizeof(size_t)) * capacity;

    record_size, cluster_capacity и capacity так же вычисляются на основе нескольких слагаемых/множителей.

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




    • Изменено MGNeo 14 марта 2018 г. 4:04
    14 марта 2018 г. 4:02
  • Собственно, вы сами ответили: стандартного способа нет. Ваши проверки работают, но лучше бы использовать специальные функции компилятора для этих целей. Думаю, так быстрее будет (хотя, я не измерял), да и код получается более естественный.

    В Visual Studio - функции из Intsafe.h

    #include <stdlib.h> #include <stdio.h> #include <windows.h> #include <tchar.h> #include <Intsafe.h> int _tmain(int argc, _TCHAR* argv[]) { ULONGLONG a=100000000000, b=5000000000, c; HRESULT hr = ULongLongMult(a,b,&c);

    if(SUCCEEDED(hr)) printf("Result is %llu",c); else if(hr==INTSAFE_E_ARITHMETIC_OVERFLOW) printf("Overflow"); else printf("Error occured"); return 0; }

    (Для использования операций со знаковыми числами нужно определить ENABLE_INTSAFE_SIGNED_FUNCTIONS перед включением заголовочного файла.)

    Эти функции определены как inline, в зависимости от архитектуры процессора они используют либо intrinsic-функции компилятора, либо специальный алгоритм с разбиением операндов на 2 32-битных компонента, позволяющий отловить переполнение по значениям определенных битов. Можно открыть сам заголовочный файл и посмотреть.

    В GCC - builtin-функции



    • Помечено в качестве ответа MGNeo 14 марта 2018 г. 6:03
    • Изменено VadimTagil 14 марта 2018 г. 7:41
    14 марта 2018 г. 5:58
  • Спасибо.

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

    • Изменено MGNeo 14 марта 2018 г. 6:31
    14 марта 2018 г. 6:03
  • В основном проверки нужны при определении размеров пространства данных хэш-таблицы.




    Мне кажется для данного применения это не проблема. На 32 битных ПК переполнение возможно, но легко отслеживается использованием 64 битной арифметики.

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

    Кстати, переполнения вполне отлавливаются statiyeskimi анализаторами кода. Можно так же перейти на более современные языки вроде C# где переполнения могут кидать исключения.


    This posting is provided "AS IS" with no warranties, and confers no rights.

    14 марта 2018 г. 16:05