什么是最好的C ++方式乘以无符号整数模块化安全？ [英] What's the best C++ way to multiply unsigned integers modularly safely?

问题描述

假设您使用< cstdint> ，并输入类似 std :: uint8_t 和 std :: uint16_t ，并且希望执行 + = 和 * = 。你希望这些数字的算术模块化，像C / C ++中的典型。这通常工作，你发现实验工作与 std :: uint8_t ， std :: uint32_t 和 std :: uint64_t ，但不是 std :: uint16_t 。

，与 std :: uint16_t 的乘法有时会失败壮观，优化的构建产生各种奇怪的结果。原因？由于有符号整数溢出导致的未定义行为。编译器基于未定义的行为不发生的假设进行优化，因此开始从程序中修剪大块代码。具体的未定义行为如下：

  std :: uint16_t x = UINT16_C（0xFFFF） 
 x * = x; 
  

原因是C ++的促销规则，以及你和几乎所有人一样，一个在其上 std :: numeric_limits< int> :: digits == 31 的平台。也就是说， int 是32位（ digits 计数位，但不是符号位）。 x 被提升为 signed int ，尽管未分配， 0xFFFF * 0xFFFF



演示一般问题：

  //编译最近版本的clang并运行：
 // clang ++ -std = c ++ 11 -O3 -Wall -fsanitize = undefined stdint16 .cpp -o stdint16 
 
 #include< cinttypes> 
 #include< cstdint> 
 #include< cstdio> 
 
 int main（）
 {
 std :: uint8_t a = UINT8_MAX; a * = a; // OK 
 std :: uint16_t b = UINT16_MAX; b * = b; // undefined！ 
 std :: uint32_t c = UINT32_MAX; c * = c; // OK 
 std :: uint64_t d = UINT64_MAX; d * = d; // OK 
 
 std :: printf（％02PRIX8％04PRIX16％08PRIX32％016PRIX64\\\
，
a，b，c ，d）; 
 
 return 0; 
} 
  

您会得到一个不错的错误：

  main.cpp：11：55：runtime error：signed integer overflow：65535 * 65535 
不能在类型'int'中表示
  

避免这种情况的方法当然是在乘法之前至少转换为 unsigned int 。只有无符号类型的位数精确等于 int 的位数的一半的确切情况是有问题的。任何较小的将导致乘法无法溢出，如 std :: uint8_t ;任何更大的将导致类型精确映射到一个促销等级，如 std :: uint64_t 匹配 unsigned long 或 unsigned long long （取决于平台）。

但这真的很烂：它需要知道哪种类型是有问题的根据当前平台上的 int 的大小。有没有更好的方法可以避免未定义的行为与无符号整数乘法没有 #if mazes？

这篇文章关于一个C解决方案的一个系统上的 uint32_t * uint32_t 乘法，其中 int 是64位有一个非常简单的解决方案，我没有想到：



解决方案，翻译成我的问题，很简单：

  static_cast< std :: uint16_t>（1U * x * x）
  

只需在算术运算链左侧插入 1U 将 unsigned int 和 std :: uint16_t 的第一个参数提升到更大的等级，然后依此类推。促销将确保答案是无符号的，并且所请求的位保持存在。

这是非常简单和优雅，我希望我一年前想过了。感谢以前回应的所有人。

Let's say that you are using <cstdint> and types like std::uint8_t and std::uint16_t, and want to do operations like += and *= on them. You'd like arithmetic on these numbers to wrap around modularly, like typical in C/C++. This ordinarily works, and you find experimentally works with std::uint8_t, std::uint32_t and std::uint64_t, but not std::uint16_t.

Specifically, multiplication with std::uint16_t sometimes fails spectacularly, with optimized builds producing all kinds of weird results. The reason? Undefined behavior due to signed integer overflow. The compiler is optimizing based upon the assumption that undefined behavior does not occur, and so starts pruning chunks of code from your program. The specific undefined behavior is the following:

std::uint16_t x = UINT16_C(0xFFFF);
x *= x;

The reason is C++'s promotion rules and the fact that you, like almost everyone else these days, are using a platform on which std::numeric_limits<int>::digits == 31. That is, int is 32-bit (digits counts bits but not the sign bit). x gets promoted to signed int, despite being unsigned, and 0xFFFF * 0xFFFF overflows for 32-bit signed arithmetic.

Demo of the general problem:

// Compile on a recent version of clang and run it:
// clang++ -std=c++11 -O3 -Wall -fsanitize=undefined stdint16.cpp -o stdint16

#include <cinttypes>
#include <cstdint>
#include <cstdio>

int main()
{
     std::uint8_t a =  UINT8_MAX; a *= a; // OK
    std::uint16_t b = UINT16_MAX; b *= b; // undefined!
    std::uint32_t c = UINT32_MAX; c *= c; // OK
    std::uint64_t d = UINT64_MAX; d *= d; // OK

    std::printf("%02" PRIX8 " %04" PRIX16 " %08" PRIX32 " %016" PRIX64 "\n",
        a, b, c, d);

    return 0;
}

You'll get a nice error:

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535
    cannot be represented in type 'int'

The way to avoid this, of course, is to cast to at least unsigned int before multiplying. Only the exact case where the number of bits of the unsigned type exactly equals half the number of bits of int is problematic. Any smaller would result in the multiplication being unable to overflow, as with std::uint8_t; any larger would result in the type exactly mapping to one of the promotion ranks, as with std::uint64_t matching unsigned long or unsigned long long depending on platform.

But this really sucks: it requires knowing which type is problematic based upon the size of int on the current platform. Is there some better way by which undefined behavior with unsigned integer multiplication can be avoided without #if mazes?

解决方案

This article regarding a C solution to the case of uint32_t * uint32_t multiplication on a system in which int is 64 bits has a really simple solution that I hadn't thought of: 32 bit unsigned multiply on 64 bit causing undefined behavior?

That solution, translated to my problem, is simple:

static_cast<std::uint16_t>(1U * x * x)

Simply involving 1U in the left side of the chain of arithmetic operations like that will promote the first parameter to the larger rank of unsigned int and std::uint16_t, then so on down the chain. The promotion will ensure that the answer is both unsigned and that the requested bits remain present. The final cast then reduces it back to the desired type.

This is really simple and elegant, and I wish I had thought of it a year ago. Thank you to everyone who responded before.

这篇关于什么是最好的C ++方式乘以无符号整数模块化安全？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！