实施安全左移

Question

我想实现一个在溢出时触发失败的左移函数。

这是我的代码：

uint32_t safe_shl(uint32_t x, uint8_t y) {
    uint32_t z = x << y;
    assert((z >> y) == x);
    return z;
}

请假设我的 assert 函数在我的系统中记录了一个错误。

我想确保我的方法是防弹的（即，在每次错误输入时失败，并且只在错误输入时失败）。

而且我还想问问你是否知道一个更有效的方法来实现这个（假设它确实是防弹的）。

Answer 1

如果 x << y 未定义，则所有投注均无效。
唯一安全的方法是在尝试之前检查它是否有效。

uint32_t safe_shl(uint32_t x, uint8_t y) {
    assert (y < 32);
    if (y < 32)
    {
        uint32_t z = x << y;
        assert((z >> y) == x);
        return z;
    }
    return 0;
}

请注意，您需要条件 - 无条件移位让编译器假定 y < 32 为真。

Answer 2

您是要断言移位是否会导致进位？

在这种情况下，如果不求助于内在函数或汇编程序，在 c++ 中就有点麻烦了。

#include <cassert>
#include <cstdint>
#include <limits>

bool shl_would_carry(uint32_t x, uint8_t y)
{
    constexpr auto nof_bits = std::numeric_limits<decltype(x)>::digits;
    if (y >= nof_bits)
    {
        if (x != 0) return true;
    }
    else
    {
        auto limit = decltype(x)(1) << (nof_bits - y);
        if (x >= limit) return true;
    }
    return false;
}

uint32_t safe_shl(uint32_t x, uint8_t y) 
{
    assert(!shl_would_carry(x, y));
    return x << y;
}

我觉得是的。

这可能会更好：

std::tuple<uint32_t, uint32_t> shl(uint32_t x, uint8_t y)
{
    uint32_t overflow, result;
    constexpr auto nof_bits = std::numeric_limits<decltype(x)>::digits;
    overflow = x >> (nof_bits - y); 
    result = x << y;
    return std::make_tuple(overflow, result);
}

uint32_t safe_shl(uint32_t x, uint8_t y) 
{
    auto t = shl(x, y);
    assert(!std::get<0>(t));
    return std::get<1>(t);
}

Answer 3

在 C 中，x << y 如果为 uint32_t 定义则提供 y < 32。来自 6.5.7 位移运算符中 C11 的 n1570 草案：

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

则要求结果为：x×2^y,约模比结果类型中可表示的最大值多 1

让我们将该值称为 z，就像它在您建议的代码中一样。就像您使用无符号类型一样，z >> y 的值需要是 z/2^y 的组成部分。

也就是说假设y < 32如果有溢出，z >> y的值会因为取模的原因严格小于x，如果有是非溢出，你正好得到 x

来自 6.5.7 移位运算符的完整参考：

...
4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

它与 5.8 中 C++14 的 n4296 草案中的 C++ 完全相同移位运算符 [expr.shift]:

...The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

2 The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

3 The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

所以在两种语言中，假设 assert 函数在[你的]系统中注册了一个错误，代码应该是：

uint32_t safe_shl(uint32_t x, uint8_t y) {
    assert(y<32);
    uint32_t z = x << y;
    assert((z >> y) == x);
    return z;
}

Answer 4

为了编写安全的函数，您必须首先确定什么是不安全的。如果你不这样做，任务就是废话。你说的那种 "overflow" 实际上是定义明确的。但存在以下危险行为案例：

左移超过变量的大小，包括将数据移入有符号变量的符号位。（未定义的行为）
右边的运算符是负数。（未定义的行为）
右移一个负数。（隐含定义的行为）
左操作数的隐式整数提升导致它悄无声息地改变符号，从而引发上述错误之一。

为避免这种情况，您需要确保：

左操作数必须是无符号的。
右操作数必须有效且在左操作数的类型范围内。
左操作数不能是小整数类型。

1)和3)用uint32_t求解。不存在 uint32_t 小于 int 的系统。

2) 通过使用无符号类型并检查它不是太大来解决。

此外，您似乎有一个要求，即不允许移出左操作数的边界。这很奇怪，但是好吧，让我们也实现它。可以通过检查 MSB 位位置加上移位数是否大于 31 来完成。

uint8_t msb_pos32 (uint32_t data)
{
  uint8_t result = 0;
  while(data>>=1 > 0)
  {
    result++;
  }
  return result;
}

uint32_t safe_LSL32 (uint32_t x, uint8_t y) 
{
  if(y > 31 || y+msb_pos32(x) > 31)
  {
    __asm HCF;               // error handling here
  }
  return x << y;
}

请注意，此代码可以进一步优化。

Answer 5

第 1 步。如果 x == 0 和任何移位量，结果在概念上仍然为 0，这不是问题。

第 2 步。不要尝试过度移动。

If the value of the right operand is negative or greater than or equal to the width of the promoted left operand, the behavior is undefined. C11 §6.5.7 3

第 3 步。在移位时确保无符号数学。

如果 int/unsigned 比 uintN_t x 宽，则 x << y 用 int 数学运算完成。这在 N==32 中很少见，但仍有可能。有符号数学溢出是可能的并导致 UB。通过 1u*x 或 (0u+x)，代码可以确保移位使用 unsigned 和 uintN_t 数学中较宽的一个。好的编译器仍然会生成最佳代码。

第 4 步。检测是否发生了减少。

If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type §6.5.7 4

uint32_t safe_shl(uint32_t x, uint8_t y) {
  if (x == 0) {
    return 0;
  } 
  assert(y < 32);
  uint32_t z = (1u*x) << y;
  assert((z >> y) == x);
  return z;
}

实施安全左移

Implementing safe shift-left

c

c++

integer-overflow

bit-shift