обнаружение умножения переполнения целых чисел uint64_t на C

Question

Есть ли эффективный и переносимый способ проверки, когда операции умножения с переполнением операндов int64_t или uint64_t в C?

Например, для добавления uint64_t я могу сделать:

if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;

Но я не могу найти аналогичное простое выражение для умножения.

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

Обновление 1 : добавлен некоторый эталонный код, реализующий несколько подходов

Обновление 2 : добавлен метод Jens Gustedt

программа бенчмаркинга:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N 100000000

int d = 2;

#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)

#define calc_b (a + c)
// #define calc_b (a + d)

int main(int argc, char *argv[]) {
    uint64_t a;
    uint64_t c = 0;
    int o = 0;
    int opt;

    if (argc != 2) exit(1);

    opt = atoi(argv[1]);

    switch (opt) {

    case 1: /* faked check, just for timing */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (c > a) o++;
            c += b * a;
        }
        break;

    case 2: /* using division */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (b && (a > UINT64_MAX / b)) o++;
            c += b * a;
        }
        break;

    case 3: /* using floating point, unreliable */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if ((double)UINT64_MAX < (double)a * (double)b) o++;
            c += b * a;
        }
        break;

    case 4: /* using floating point and division for difficult cases */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            double m = (double)a * (double)b;
            if ( ((double)(~(uint64_t)(0xffffffff)) < m ) &&
                 ( (POW_2_64 < m) ||
                   ( b &&
                     (a > UINT64_MAX / b) ) ) ) o++;
            c += b * a;
        }
        break;

    case 5: /* Jens Gustedt method */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            uint64_t a1, b1;
            if (a > b) { a1 = a; b1 = b; }
            else       { a1 = b; b1 = a; }
            if (b1 > 0xffffffff) o++;
            else {
                uint64_t a1l = (a1 & 0xffffffff) * b1;
                uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
                if (a1h >> 32) o++;
            }
            c += b1 * a1;
        }
        break;

    default:
        exit(2);
    }
    printf("c: %lu, o: %u\n", c, o);
}

Пока что случай 4, который использует плавающую точку для фильтрации большинства случаев, является самым быстрым, когда предполагается, что переполнения очень необычны, по крайней мере, на моем компьютере, где он только в два раза медленнее, чем случай бездействия.

Случай 5 на 30% медленнее, чем 4, но он всегда работает одинаково, нет никаких особых номеров дел, требующих более медленной обработки, как в случае с 4.

Answer 1

На самом деле, для умножения можно использовать тот же принцип:

uint64_t a;
uint64_t b;
...
if (b != 0 && a > UINT64_MAX / b) { // if you multiply by b, you get: a * b > UINT64_MAX
    < error >
}
uint64_t c = a * b;

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

Answer 2

Если вы хотите избежать деления, как в ответе Амброза:

Сначала вы должны увидеть, что меньшее из двух чисел, скажем a, меньше 2 ³² , в противном случае результат все равно будет переполнен. Пусть b будет разложено на два 32-битных слова: b = c 2 ³² + d.

Тогда вычисление не так сложно, я нахожу:

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) {
  if (a > b) return mult_with_overflow_check(b, a);
  if (a > UINT32_MAX) overflow();
  uint32_t c = b >> 32;
  uint32_t d = UINT32_MAX & b;
  uint64_t r = a * c;
  uint64_t s = a * d;
  if (r > UINT32_MAX) overflow();
  r <<= 32;
  return addition_with_overflow_check(s, r);
}

так что это два умножения, две смены, некоторые сложения и проверки условий. Это может быть более эффективным, чем деление, потому что, например, два умножения могут передаваться параллельно. Тебе нужно будет проверить, что лучше для тебя работает.

Answer 3

Он может не обнаруживать точные переполнения, но в целом вы можете проверить результат умножения в логарифмическом масштабе:

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double
else prod = a * b;

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

Answer 4

case 6:
    for (a = 0; a < N; a++) {
        uint64_t b = a + c;
        uint64_t a1, b1;
        if (a > b) { a1 = a; b1 = b; }
        else       { a1 = b; b1 = a; }
        uint64_t cc = b1 * a1;
        c += cc;
        if (b1 > 0xffffffff) o++;
        else {
            uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32);
            a1l = (a1 + (a1 >> 32)) & 0xffffffff;
            uint64_t ab1l = a1l * b1;
            ab1l = (ab1l & 0xffffffff) + (ab1l >> 32);
            ab1l += (ab1l >> 32);
            uint64_t ccl = (cc & 0xffffffff) + (cc >> 32);
            ccl += (ccl >> 32);
            uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0;
            uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0;
            if (ab32 != cc32) o++;
        }
    }
    break;

Этот метод сравнивает (возможно, переполнение) результат нормального умножения с результатом умножения, которое не может быть переполнено. Все расчеты по модулю (2 ^ 32 - 1).

Это сложнее и (скорее всего) не быстрее, чем метод Йенса Гастдта.

После некоторых небольших модификаций он может размножаться с точностью до 96 бит (но без контроля переполнения). Что может быть более интересно, идея этого метода может быть использована для проверки переполнения для ряда арифметических операций (умножения, сложения, вычитания).

На некоторые вопросы ответили

Прежде всего, о "your code is not portable". Да, код не переносимый, потому что он использует uint64_t, который запрашивается в исходном вопросе. Строго говоря, вы не можете получить переносимый ответ с помощью (u)int64_t, поскольку он не требуется по стандарту.

О "once some overflow happens, you can not assume the result value to be anything". Стандарт говорит, что неподписанные итераторы не могут переполниться. Глава 6.2.5, пункт 9:

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

Таким образом, 64-разрядное умножение без знака выполняется по модулю 2 ^ 64, без переполнения.

Теперь о "logic behind". «Хэш-функция» здесь не является правильным словом. Я использую только вычисления по модулю (2^32 - 1). Результат умножения может быть представлен как n*2^64 + m, где m - видимый результат, а n означает, насколько мы переполнены. Поскольку 2^64 = 1 (mod 2^32 - 1), мы можем вычислить [true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1). Если вычисленное значение n не равно нулю, возникает переполнение. Если оно равно нулю, переполнения нет. Любые столкновения возможны только после n >= 2^32 - 1. Этого никогда не произойдет, поскольку мы проверяем, что один из мультипликатов меньше 2^32.

Answer 5

Связанный вопрос с некоторыми (надеюсь) полезными ответами: Лучший способ обнаружить целочисленное переполнение в C / C ++ .Плюс это не распространяется только на uint64_t;)