在C / C ++的无符号左移之前掩盖了是否偏执?
这个问题是由我在C / C ++中实现encryptionalgorithm(例如SHA-1),编写可移植的平台不可知的代码,并彻底避免未定义的行为 。
假设一个标准化的encryptionalgorithm要求你实现这个:
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
types来改进这个代码:
uint32_t a = (...); uint32_t b = a << 31;
所以我们完成了,对吧? 这就是我多年来的想法。 … 不完全的。 假设在某个平台上,我们有:
// stdint.h typedef unsigned short uint32_t;
在C / C ++中执行算术运算的规则是,如果types(比如short
)比int
,那么如果所有值都适合,则将其扩展为int
否则,将其变为int
。
我们假设编译器将short
定义为32位(带符号), int
为48位(带符号)。 然后这些代码行:
uint32_t a = (...); uint32_t b = a << 31;
将有效地意味着:
unsigned short a = (...); unsigned short b = (unsigned short)((int)a << 31);
请注意,因为所有ushort
(即uint32
)都适合int
(即int48
),所以将a
提升为int
。
但是现在我们遇到了一个问题: 将非零位移位到有符号整数types的符号位是未定义的行为 。 发生这个问题是因为我们的uint32
升级到了int48
– 而不是升级到uint48
(在这种情况下,左移将会没问题)。
这是我的问题:
-
我的推理是否正确,这在理论上是一个合法的问题吗?
-
这个问题是否可以安全地忽略,因为在每个平台上,下一个整数types是宽度的两倍?
-
通过像这样预先屏蔽input,正确地防御这种病态情况是一个好主意:
b = (a & 1) << 31;
。 (这在每个平台上都是正确的,但是这可能会使速度要求较高的encryptionalgorithm慢于必要的)。
澄清/编辑:
-
我会接受C或C ++或两者的答案。 我想知道至less有一种语言的答案。
-
预掩蔽逻辑可能会损害位的旋转。 例如,GCC将编译
b = (a << 31) | (a >> 1);
b = (a << 31) | (a >> 1);
到汇编语言的32位位循环指令。 但是如果我们预先屏蔽左移,那么新逻辑可能不会被转换成位旋转,这意味着现在执行4个操作而不是1。
说到问题的C方面,
- 我的推理是否正确,这在理论上是一个合法的问题吗?
这是我之前没有考虑过的问题,但我同意你的分析。 C根据所提升的左操作数的types来定义<<
运算符的行为,并且可以想象的是,当该操作数的原始types是uint32_t
时,整数促销导致(signed) int
。 我不希望在任何现代机器上看到这一点,但我完全是为了实际的标准而不是个人的期望。
- 这个问题是否可以安全地忽略,因为在每个平台上,下一个整数types是宽度的两倍?
C不需要整数types之间的这种关系,尽pipe它在实践中无处不在。 如果你决定只依赖标准,那么就是说,如果你努力写严格符合的代码 – 那么你就不能依赖这样的关系。
- b =(a&1)<< 31;通过预先屏蔽input正确地防御这种病态情况是一个好主意。 (这在每个平台上都是正确的,但是这可能会使速度要求严格的密码algorithm变慢)。
unsigned long
types保证至less有32位值,在整数提升下不会升级到任何其他types。 在许多常见的平台上,它与uint32_t
具有完全相同的表示forms,甚至可能是相同的types。 因此,我倾向于写这样的expression:
uint32_t a = (...); uint32_t b = (unsigned long) a << 31;
或者如果你只需要在b
的计算中作为一个中间值,那么就把它声明为一个unsigned long
来开始。
Q1: 在换class之前进行掩蔽,可以防止OP所关心的未定义行为。
Q2:“…因为在每个平台上,下一个整数types是宽度的两倍?” – >不。 “下一个”整数types可能小于2倍甚至相同的大小。
对于所有具有uint32_t
兼容C编译器,以下内容都是明确定义的。
uint32_t a; uint32_t b = (a & 1) << 31;
Q3: uint32_t a; uint32_t b = (a & 1) << 31;
uint32_t a; uint32_t b = (a & 1) << 31;
预计不会产生执行掩码的代码 – 在可执行文件中不需要 – 只是在源代码中。 如果一个面具确实发生,那么得到一个更好的编译器应该是一个问题。
如所暗示的那样 ,更好地强调与这些转变无关性。
uint32_t b = (a & 1U) << 31;
@John Bollinger很好地回答了好细节如何处理OP的具体问题。
一般的问题是如何形成一个至less有n
位,一定的符号,不受令人惊讶的整数升级的数字 – OP的核心困境。 下面通过调用一个不改变值的unsigned
操作来实现这一点 – 除了types问题之外,还有一个没有操作的操作。 该产品将至less是unsigned
或uint32_t
的宽度。 一般而言,铸造可能会缩小types。 必须避免铸造,除非确定不会发生缩小。 优化编译器不会创build不必要的代码。
uint32_t a; uint32_t b = (a + 0u) << 31; uint32_t b = (a*1u) << 31;
从这个关于uint32 * uint32
algorithm可能的UB的问题中得到线索,下面的简单方法应该在C和C ++中工作:
uint32_t a = (...); uint32_t b = (uint32_t)((a + 0u) << 31);
整数常量0u
types是unsigned int
。 这促进了uint32_t
或unsigned int
的加法a + 0u
,以较宽的为准。 因为该types具有等级int
或更高级别,所以不再发生升级,并且可以应用左移操作数为uint32_t
或unsigned int
的移位。
最后回到uint32_t
将只是抑制关于缩小转换的潜在警告(如果int
是64位)。
一个体面的C编译器应该能够看到,加零是一个空操作,这比看到一个无符号移位后的预掩码没有效果要麻烦。
为了避免不必要的促销,你可以使用更大的types和一些typedef
using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)), unsigned, std::uint32_t>;
对于这段代码:
uint32_t a = (...); uint32_t b = a << 31;
要将一个无符号types提升为无符号types,请使用:
uint32_t b = a << 31u;
当<<
运算符的两边都是无符号types时,则6.3.1.8(C标准草案n1570)中的这一行适用:
否则,如果两个操作数都具有带符号的整数types或两者都具有无符号的整数types,则将具有较小整数转换等级的操作数转换为具有较高等级的操作数的types。
你所描述的问题是你使用了31
这是有signed int type
所以在6.3.1.8中的另一行
否则,如果具有有符号整数types的操作数的types可以表示具有无符号整数types的操作数types的所有值,则将具有无符号整数types的操作数转换为具有有符号整数types的操作数的types。
迫使a
提升为签名types
更新:
这个答案是不正确的,因为6.3.1.1(2)(强调我的):
…
如果int可以表示原始types的所有值(由宽度限制,对于位域),则该值被转换为int ; 否则,它被转换为一个无符号的整数 。 这些被称为整数促销.58)所有其他types都是整数 促销不变。
和脚注58(重点是我的):
58)整数提升仅适用于:作为通常的算术转换的一部分,对于某些参数expression式,一元运算符, – 和〜运算符的操作数以及两个运算符的操作数小节。
由于只有整数提升发生,而不是普通的算术转换,所以使用31u
并不保证如上所述将其转换为unsigned int
。