检测uint64_t中的整数溢出乘用C [英] detecting multiplication of uint64_t integers overflow with C

问题描述

有没有检查任何有效和可移植的方法时，在C或的int64_t操作数uint64_t中溢出的乘法运算？

Is there any efficient and portable way to check when multiplication operations with int64_t or uint64_t operands overflow in C?

例如，对于另外uint64_t中的我可以做的：

For instance, for addition of uint64_t I can do:

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

但我不能得到一个类似的简单的前pression乘法。

But I can not get to a similar simple expression for multiplication.

所有这一切发生，我更是打破了操作数为高，低uint32_t的部件和执行这些部件的倍增，同时检查溢出，一些真正丑陋和低效的可能了。

All that occurs to me is breaking the operands into high and low uint32_t parts and performing the multiplication of those parts while checking for overflow, something really ugly and probably inefficient too.

更新1 ：有些基准code实施增加了几个方法

Update 1: Some benchmark code implementing several approaches added

更新2 ：延斯Gustedt方法添加

Update 2: Jens Gustedt method added

基准程序：

#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是当假设的溢出是非常不寻常的，至少在我的电脑上它比什么都不做的情况下慢了两次最快的。

So far, case 4 that uses floating point to filter most cases is the fastest when it is assumed that overflows are very unusual, at least on my computer where it is only two times slower than the do-nothing case.

案例5，比4慢了30％，但它总是执行相同的，没有需要处理速度较慢，与4发生任何特殊情况下的数字。

Case 5, is 30% slower than 4, but it always performs the same, there isn't any special case numbers that require slower processing as happens with 4.

推荐答案

如果你想避免分裂为Ambroz的回答：

If you want to avoid division as in Ambroz' answer:

首先，你必须看到这两个数字越小，表示 A ，不到2 ³² ，否则结果会溢出无论如何。让 B 被分解成两个32位字是 B = C 2 ³² + D 。

First you have to see that the smaller of the two numbers, say a, is less than 2³², otherwise the result will overflow anyhow. Let b be decomposed into the two 32 bit words that is b = c 2³² + d.

然后计算不是那么困难，我发现：

The computation then is not so difficult, I find:

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);
}

所以这是两个乘法，两班倒，一些补充和条件检查。这可能是因为比在例如两个乘法可以paralle是流水线分工更加高效。你不得不基准，看看什么对你更好。

so this are two multiplications, two shifts, some additions and condition checks. This could be more efficient than the division because e.g the two multiplications can be pipelined in paralle. You'd have to benchmark to see what works better for you.

这篇关于检测uint64_t中的整数溢出乘用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！