Добавьте целые числа безопасно и докажите безопасность
Назначение курса программирования просит
- написать (безопасную) функцию, которая добавляет два целых числа, и
- покажите, что функция безопасна.
Следующий код представляет мое решение.
Я не эксперт по стандарту C (или по формальным методам проверки).
Поэтому я хотел бы спросить:
Есть ли лучшие (или разные) решения?
Спасибо
#include <limits.h>
/*
Try to add integers op1 and op2.
Return
0 (success) or
1 (overflow prevented).
In case of success, write the sum to res.
*/
int safe_int_add(int * res,
int op1,
int op2) {
if (op2 < 0) {
/** We have: **********************************************/
/* */
/* 0 > op2 */
/* 0 < - op2 */
/* INT_MIN < - op2 + INT_MIN */
/* INT_MIN < INT_MIN - op2 */
/* INT_MIN <= INT_MIN - op2 */
/* */
/** Also, we have: ****************************************/
/* */
/* op2 >= INT_MIN */
/* - op2 <= - INT_MIN */
/* INT_MIN - op2 <= - INT_MIN + INT_MIN */
/* INT_MIN - op2 <= 0 */
/* INT_MIN - op2 <= INT_MAX */
/* */
/** Hence, we have: ***************************************/
/* */
/* INT_MIN <= INT_MIN - op2 <= INT_MAX */
/* */
/* i.e. the following subtraction does not overflow. */
/* */
/***********************************************************/
if (op1 < INT_MIN - op2) {
return 1;
}
/** We have: *********************************/
/* */
/* INT_MIN - op2 <= op1 */
/* INT_MIN <= op1 + op2 */
/* */
/** Also, we have: ***************************/
/* */
/* op2 < 0 */
/* op1 + op2 < op1 */
/* op1 + op2 < INT_MAX */
/* op1 + op2 <= INT_MAX */
/* */
/** Hence, we have: **************************/
/* */
/* INT_MIN <= op1 + op2 <= INT_MAX */
/* */
/* i.e. the addition does not overflow. */
/* */
/**********************************************/
}
else {
/** We have: **********************************************/
/* */
/* op2 >= 0 */
/* - op2 <= 0 */
/* INT_MAX - op2 <= INT_MAX */
/* */
/** Also, we have: ****************************************/
/* */
/* INT_MAX >= op2 */
/* - INT_MAX <= - op2 */
/* INT_MAX - INT_MAX <= - op2 + INT_MAX */
/* 0 <= - op2 + INT_MAX */
/* 0 <= INT_MAX - op2 */
/* INT_MIN <= INT_MAX - op2 */
/* */
/** Hence, we have: ***************************************/
/* */
/* INT_MIN <= INT_MAX - op2 <= INT_MAX */
/* */
/* i.e. the following subtraction does not overflow. */
/* */
/***********************************************************/
if (op1 > INT_MAX - op2) {
return 1;
}
/** We have: *********************************/
/* */
/* op1 <= INT_MAX - op2 */
/* op1 + op2 <= INT_MAX */
/* */
/** Also, we have: ***************************/
/* */
/* 0 <= op2 */
/* op1 <= op2 + op1 */
/* INT_MIN <= op2 + op1 */
/* INT_MIN <= op1 + op2 */
/* */
/** Hence, we have: **************************/
/* */
/* INT_MIN <= op1 + op2 <= INT_MAX */
/* */
/* i.e. the addition does not overflow. */
/* */
/**********************************************/
}
*res = op1 + op2;
return 0;
}
Решение
Подход OP оптимально переносим, оставаясь внутри типа int а также безопасно — нет неопределенного поведения (UB) с любой комбинацией int, Это не зависит от конкретного int формат (дополнение 2, дополнение 2, величина знака).
В С, int переполнение / (underflow) — неопределенное поведение. Так что код, если вы остаетесь с int, должен заранее определить потенциал переполнения. С op1 положительны, INT_MAX - op1 не может переполниться. Кроме того, с op1 отрицательна, INT_MIN - op1 не может переполниться. Таким образом, с краями, правильно рассчитанными и проверенными, op1 + op2 не переполнится
// Minor re-write:
int safe_int_add(int * res, int op1, int op2) {
assert(res != NULL);
if (op1 >= 0) {
if (op2 > INT_MAX - op1) return 1;
} else {
if (op2 < INT_MIN - op1) return 1;
}
*res = op1 + op2;
return 0;
}
Если знать более широкий тип доступен, код может использовать
int safe_int_add_wide(int * res, int op1, int op2) {
int2x sum = (int2x) op1 + op2;
if (sum < INT_MIN || sum > INT_MAX) return 1;
*res = (int) sum;
return 0;
}
Подходы с использованием unsignedи т. д. сначала нужно это квалифицировать UINT_MAX > = INT_MAX - INT_MIN, Обычно это верно, но не гарантируется стандартом C.
Другие решения
Вот как я бы это сделал:
Если входные аргументы имеют разные знаки, то результат всегда вычисляется без риска переполнения.
Если оба входных аргумента отрицательны, то вычислить -safe_int_add(res, -op1, -op2);, (Вам нужно будет проверить это op1 или же op2 не самый большой негатив в комплименте 2s).
Нужно продумать функцию, которая добавляет два положительных числа: конвертируйте два входа в неподписанные типы. Добавьте эти. То есть гарантированный чтобы не переполнять тип unsigned, так как вы можете хранить (как минимум) вдвое большие значения в unsigned int, чем в int со знаком (ровно в два раза для комплимента 1s, на один больше, чем для комплимента 2s).
Затем попытайтесь преобразовать обратно в знаковое, только если значение без знака достаточно мало.
Вы можете посмотреть на реализацию JDK 8, которая имеет прекрасную ссылку на книгу Восторг Хакера от Генри С. Уоррена-младшего здесь:
http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/b971b51bec01
public static int addExact(int x, int y) {
int r = x + y;
// HD 2-12 Overflow iff both arguments have the opposite sign of the result
if (((x ^ r) & (y ^ r)) < 0) {
throw new ArithmeticException("integer overflow");
}
return r;
}
В моей версии книги это глава 2-13. Там вы можете найти длинное объяснение всей проблемы.