实现安全换档-左移

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

步骤1.如果x == 0和任何移位量，结果在概念上仍然是0，而不是一个问题。

第二步:不要尝试过度的轮班。

如果右操作数的值为负值，或大于或等于提升的左操作数的宽度，则行为未定义。C11§6.5.7 3

第三步:在移动时确保未签名的数学。

如果int/unsigned比uintN_t x宽，那么x << y就完成了int的数学运算。这在N==32中是很少见的，但也是可能的。签名的数学溢出是可能的，并导致UB。通过1u*x或(0u+x)，代码可以确保转换使用unsigned和uintN_t数学的更大范围。优秀的编译器仍然会做出最优的代码。

步骤4.检测是否发生了缩减。

如果E1具有无符号类型，则结果的值为E1×2E2，减少的模值比结果类型§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;
}

Answer 2

如果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 3

你是在要求断言这种转移是否会导致携带？

在这种情况下，它在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);
}