实施安全左移

问题描述 投票：1回答：5

我想实现一个shift-left函数，它会在溢出时触发失败。

这是我的代码：

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

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

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

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

非常感谢你！！！

c++ c bit-shift integer-overflow
5个回答
1
投票

步骤1.如果x == 0and任何移位量，结果在概念上仍为0并且不是问题。

步骤2.不要尝试过度换班。

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

步骤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.74

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;
}
4
投票

如果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为真。

1
投票

你是否要求断言转移是否会导致进位？

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

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

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

然后，结果必须是：x×2y，比结果类型中可表示的最大值减少一个模数

让我们在你提议的代码中调用它的值z。就像你使用无符号类型一样，z >> y的值必须是z / 2y的组成部分。

这意味着如果y <32，如果有溢出，z >> y的值将严格小于x，因为模数，如果有非溢出，则得到x

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

... 4 E1 << E2的结果是E1左移E2位位置;腾出的位用零填充。如果E1具有无符号类型，则结果的值为E1×2E2，比结果类型中可表示的最大值减少一个模数。如果E1具有有符号类型和非负值，并且在结果类型中可以表示E1×2E2，那么这就是结果值;否则，行为未定义。

5 E1 >> E2的结果是E1右移E2位的位置。如果E1具有无符号类型或者E1具有带符号类型和非负值，则结果的值是E1 / 2E2的商的整数部分。如果E1具有带符号类型和负值，则结果值是实现定义的。

在V ++中，从5.8移位运算符[expr.shift]中的C ++ 14的n4296草案中完全相同：

...如果右操作数为负数，或者大于或等于提升左操作数的位长度，则行为未定义。

2 E1 << E2的值是E1左移E2位的位置;空位是零填充的。如果E1具有无符号类型，则结果的值为E1×2E2，比结果类型中可表示的最大值减少一个模数。否则，如果E1具有有符号类型和非负值，并且E1×2E2可在结果类型的相应无符号类型中表示，则转换为结果类型的该值是结果值;否则，行为未定义。

3 E1 >> E2的值是E1右移E2位的位置。如果E1具有无符号类型或者E1具有有符号类型和非负值，则结果的值是E1 / 2E2的商的整数部分。如果E1具有带符号类型和负值，则结果值是实现定义的。

因此，在两种语言中，并假设断言函数在[您的]系统中注册错误，代码应为：

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

为了编写安全功能，您必须首先确定哪些不安全。如果你不这样做，那么任务就是废话。你提到的那种“溢出”实际上是明确定义的。但存在以下危险行为案例：

  • 左移大于变量的大小，包括将数据移入有符号变量的符号位。 （未定义的行为）
  • 右边的运算符是负数。 （未定义的行为）
  • 右移负数。 （Impl.-定义的行为）
  • 左操作数的隐式整数提升导致它以静默方式更改签名，从而调用上述错误之一。

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

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

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;
}

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.