在C/C++中无符号左移之前掩盖是否过于偏执？

Question

这个问题的动机是我在C/C++中实现加密算法(例如SHA-1),编写可移植平台无关的代码,并彻底避免未定义的行为.

假设标准化的加密算法要求您实现此目的:

b = (a << 31) & 0xFFFFFFFF

where a和b是无符号的32位整数.请注意,在结果中,我们丢弃高于最低32位的任何位.

---

作为第一个天真的近似,我们可以假设int在大多数平台上都是32位宽,所以我们写:

unsigned int a = (...);
unsigned int b = a << 31;

我们知道这个代码无处不在,因为int在某些系统上是16位宽,在其他系统上是64位,甚至可能是36位.但是使用stdint.h,我们可以使用以下uint32_t类型改进此代码:

uint32_t a = (...);
uint32_t b = a << 31;

所以我们完成了,对吧？这就是我多年来的想法.... 不完全的.假设在某个平台上,我们有:

// stdint.h
typedef unsigned short uint32_t;

在C/C++中执行算术运算的规则是,如果类型(例如short)比类型更窄int,那么int如果所有值都适合,则它会变宽,unsigned int否则.

假设编译器定义short为32位(带符号)和int48位(带符号).然后这些代码行:

uint32_t a = (...);
uint32_t b = a << 31;

将有效地意味着:

unsigned short a = (...);
unsigned short b = (unsigned short)((int)a << 31);

请注意,这a是int因为所有ushort(即uint32)都适合int(即int48).

但是现在我们遇到了一个问题:将非零位移位到有符号整数类型的符号位是未定义的行为.出现这个问题的原因是我们uint32被提升为int48- 而不是晋升为uint48(左转移可以).

---

这是我的问题:

1. 我的推理是否正确,这在理论上是一个合理的问题吗？

2. 这个问题是否可以安全忽略,因为在每个平台上,下一个整数类型是宽度的两倍？

3. 是一个好主意,通过屏蔽预这样？:输入正确抵御这种病态情况b = (a & 1) << 31;.(这在每个平台上都必须是正确的.但这可能使速度关键的加密算法比必要的慢.)

澄清/编辑:

• 我会接受C或C++或两者的答案.我想知道至少一种语言的答案.

• 预掩码逻辑可能会损害位旋转.例如,GCC将b = (a << 31) | (a >> 1);使用汇编语言编译为32位位旋转指令.但是如果我们预先屏蔽左移,则新逻辑可能不会转换为位旋转,这意味着现在执行4次操作而不是1次.

Answer 1

说到C方面的问题,

1. 我的推理是否正确,这在理论上是一个合理的问题吗？

这是我以前没有考虑过的问题,但我同意你的分析.C <<根据提升的左操作数的类型定义运算符的行为,并且可以想象整数提升导致在int该操作数的原始类型为(签名)时uint32_t.我不希望在任何现代机器上实际看到这一点,但我完全按照实际标准编程,而不是我个人的期望.

2. 这个问题是否可以安全忽略,因为在每个平台上,下一个整数类型是宽度的两倍？

C不需要整数类型之间的这种关系,尽管它在实践中无处不在.但是,如果你决定只依赖于标准 - 也就是说,如果你正在努力编写严格符合规范的代码 - 那么你就不能依赖这种关系.

3. 通过预先掩盖这样的输入来正确防御这种病态是一个好主意吗？:b =(a&1)<< 31;.(这在每个平台上都必须是正确的.但这可能使速度关键的加密算法比必要的慢.)

该类型unsigned long保证至少有32个值位,并且在整数提升下不受任何其他类型的提升.在许多常见的平台上,它具有完全相同的表示形式uint32_t,甚至可能是相同的类型.因此,我倾向于写下这样的表达式:

uint32_t a = (...);
uint32_t b = (unsigned long) a << 31;

或者,如果您a只需要作为计算中的中间值b,则将其声明为unsigned long开头.

Answer 2

Q1:在转换之前屏蔽确实可以防止OP关注的未定义行为.

Q2:"......因为在每个平台上,下一个整数类型都是宽度的两倍？" - >不."下一个"整数类型可以小于2x甚至相同的大小.

以下是适用于所有兼容的C编译器的明确定义uint32_t.

uint32_t a; 
uint32_t b = (a & 1) << 31;

问题3:uint32_t a; uint32_t b = (a & 1) << 31;预计不会产生执行掩码的代码 - 可执行文件中不需要它 - 仅在源代码中.如果确实发生了掩码,那么在速度成为问题的情况下获得更好的编译器.

正如所建议的那样,更好地强调这些转变的无符号性.

uint32_t b = (a & 1U) << 31;

@John Bollinger很好地解答了如何处理OP的具体问题.

在一般的问题是如何形成一个数字,至少n位,有一定迹象的烦躁和 不受奇怪整数促销- OP困境的核心.下面通过调用unsigned不改变值的操作来实现这一点- 除了类型关注之外,有效的无操作.产品的宽度至少为unsigned或uint32_t.一般来说,铸造可能会缩小类型.除非确定不会发生缩小,否则需要避免铸造.优化编译器不会创建不必要的代码.

uint32_t a;
uint32_t b = (a + 0u) << 31;
uint32_t b = (a*1u) << 31;

Answer 3

从这个关于uint32 * uint32算术中可能的UB的问题中找出线索,以下简单的方法应该适用于C和C++:

uint32_t a = (...);
uint32_t b = (uint32_t)((a + 0u) << 31);

整数常量0u具有类型unsigned int.这促进了除a + 0u到uint32_t或unsigned int,取其宽.因为类型具有等级int或更高,所以不再进行促销,并且可以应用左操作数为uint32_t或的移位unsigned int.

最终的回归uint32_t只会抑制有关缩小转换的潜在警告(比如说int是64位).

一个体面的C编译器应该能够看到添加零是一个无操作,这比看到一个预掩码在无符号移位后没有效果更麻烦.

Answer 4

为了避免不必要的促销,您可以使用更大的类型和一些typedef,如

using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)),
                                              unsigned,
                                              std::uint32_t>;