这个问题的动机是我用C/C++实现加密算法(例如SHA-1),编写与平台无关的可移植代码,并且彻底避免了undefined behavior.

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

b = (a << 31) & 0xFFFFFFFF

其中ab是无符号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;

我们结束了,对吗?这就是我多年来的 idea ...不完全是.假设在某个平台上,我们有:

// stdint.h
typedef unsigned short uint32_t;

在C/C++中执行算术运算的规则是,如果类型(如short)小于int,则如果所有值都可以容纳,则将其扩大到int,否则将扩大到unsigned int.

假设编译器将short定义为32位(带符号),将int定义为48位(带符号).然后是这些代码行:

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).

但现在我们有一个问题:shifting non-zero bits left into the sign bit of a signed integer type is undefined behavior.出现这个问题是因为我们的uint32升到了int48,而不是升到了uint48(在uint48可以左移).


以下是我的问题:

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

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

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

澄清/编辑:

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

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

推荐答案

this question中提取uint32 * uint32算术中可能出现的UB的线索,下面的简单方法应该在C和C++中有效:

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

整数常量0u的类型为unsigned int.这会促进将a + 0u添加到uint32_tunsigned int,以较宽者为准.由于该类型的秩为int或更高,因此不会再进行升级,并且可以在左操作数为uint32_tunsigned int时应用移位.

最终强制转换回uint32_t将仅 suppress 有关缩小转换的潜在警告(例如,如果int是64位).

一个好的C编译器应该能够看到加零是一个不可操作的操作,这比看到预掩码在无符号移位后没有效果要简单.

C++相关问答推荐

整值的最后一个字节如何影响C转换中的char强制转换?

Linux/C:复制修剪了最后一个填零孔的文件

如何在Scilab API中求解方程

在严格的C89模式下,收件箱不会在' uint64_t '上发出警告

为什么在传输 Big Data 时共享内存段的运行时间比管道更长?

由Go调用E.C.引起的内存快速增长

在struct中调用函数,但struct在void中 *

当多个线程在C中写入相同的文件描述符时,如何防止争用情况?

我可以在C中声明不同长度数组的数组而不带变量名吗?

正确的TCP/IP数据包 struct

为什么memcpy进入缓冲区和指向缓冲区的指针工作相同?

防止C++中递归函数使用堆栈内存

S和查尔有什么不同[1]?

C整型和_泛型.哪些类型是兼容的?

我在C中运行和调试时得到了不同的输出

错误:字符串在C中获得意外输出

为什么我的旧式&q;函数在传递浮点数时会打印2?

变量值不正确的问题

我错误地修复了一个错误,想了解原因

Makefile - 将 .o 文件放入子文件夹中