这个问题的动机是我用C/C++实现加密算法(例如SHA-1),编写与平台无关的可移植代码,并且彻底避免了undefined behavior.
假设一个标准化的加密算法要求您实现:
b = (a << 31) & 0xFFFFFFFF
其中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;
我们结束了,对吗?这就是我多年来的 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
可以左移).
以下是我的问题:
我的推理正确吗,这在理论上是一个合法的问题吗?
因为在每个平台上,下一个整数类型都是宽度的两倍,所以忽略这个问题安全吗?
通过像这样预先掩蔽输入来正确防御这种病理情况是一个好主意吗
b = (a & 1) << 31;
.(这在每个平台上都是正确的.但这可能会使速度关键的加密算法比必要的速度慢.)
澄清/编辑:
我会接受C或C++的答案,或者两者兼而有之.我想知道至少一种语言的答案.
预掩蔽逻辑可能会影响位旋转.例如,GCC将把
b = (a << 31) | (a >> 1);
编译成汇编语言中的32位旋转指令.但如果我们预先屏蔽左移位,新逻辑可能不会转换为位旋转,这意味着现在执行4个操作,而不是1个.