如何安全地比较两个无符号整数计数器？

Question

我们有两个无符号计数器，我们需要比较它们以检查一些错误情况：

uint32_t a, b;
// a increased in some conditions
// b increased in some conditions
if (a/2 > b) {
   perror("Error happened!");
   return -1;
}

问题是 a 和 b 总有一天会溢出。如果a溢出了，还是可以的。但是如果b溢出了，那就是虚惊一场。如何让这张支票防弹？

我知道让 a 和 b uint64_t 会延迟这个误报。但还是不能完全解决这个问题。

===============

稍微说明一下：计数器是用来跟踪内存分配的，这个问题在dmalloc/chunk.c:

#if LOG_PNT_SEEN_COUNT
  /*
   * We divide by 2 here because realloc which returns the same
   * pointer will seen_c += 2.  However, it will never be more than
   * twice the iteration value.  We divide by two to not overflow
   * iter_c * 2.
   */
  if (slot_p->sa_seen_c / 2 > _dmalloc_iter_c) {
    dmalloc_errno = ERROR_SLOT_CORRUPT;
    return 0;
  }
#endif

Answer 1

如果即使使用 64 位也不够，那么您需要编写自己的 "var increase" 方法，而不是重载 ++ 运算符（如果不小心，可能会弄乱您的代码） .
该方法只会将 var 重置为“0”或其他一些有意义的值。

Answer 2

通过强制它们同时换行，在它们换行后立即对值进行标准化。保持两者换行时的差异。

尝试这样的事情；

uint32_t a, b;
// a increased in some conditions
// b increased in some conditions
if (a or b is at the maximum value) {
   if (a > b)
   {
     a = a-b; b = 0;
   }
   else
   {
     b = b-a; a = 0;
   }
}
if (a/2 > b) {
   perror("Error happened!");
   return -1;
}

Answer 3

注意溢出。

uint32_t a, b;
bool aof = false;
bool bof = false;

if (condition_to_increase_a()) {
  a++;
  aof = a == 0;
}

if (condition_to_increase_b()) {
  b++;
  bof = b == 0;
}

if (!bof && a/2 + aof*0x80000000 > b) {
   perror("Error happened!");
   return -1;
}

每个a, b相互依存有2³²+1个不同的状态反映价值和条件增量。不知何故，需要的信息不只 uint32_t。可以使用 uint64_t、变体代码路径或辅助变量，例如此处的 bool。

Answer 4

我认为您误解了代码中的注释：

We divide by two to not overflow iter_c * 2.

无论值来自哪里，写a/2是安全的，但写a*2就不安全了。无论您使用什么无符号类型，您始终可以将数字除以二，而乘法可能会导致溢出。

如果条件写成这样：

if (slot_p->sa_seen_c > _dmalloc_iter_c * 2) {

然后大约一半的输入会导致错误的情况。也就是说，如果您担心计数器溢出，您可以将它们包装在 class:

class check {
    unsigned a = 0;
    unsigned b = 0;
    bool odd = true;
    void normalize() {
        auto m = std::min(a,b);
        a -= m;
        b -= m;
    }
public:
    void incr_a(){ 
        if (odd) ++a;
        odd = !odd;
        normalize();
    }
    void incr_b(){ 
        ++b;
        normalize();
    }
    bool check() const { return a > b;}
}

请注意，要完全避免溢出，您必须采取额外措施，但如果 a 和 b 增加或多或少相同的数量，这可能已经很好了。

Answer 5

发布的代码实际上似乎没有使用可能环绕的计数器。

代码中的注释是说比较 a/2 > b 比 a > 2*b 更安全，因为后者可能会溢出而前者不会。 a 的类型大于 b 的类型尤其如此。

Answer 6

如果您的目的是确保操作 x 的发生频率不超过操作 y 的两倍，我建议您这样做：

uint32_t x_count = 0;
uint32_t scaled_y_count = 0;

void action_x(void)
{
  if ((uint32_t)(scaled_y_count - x_count) > 0xFFFF0000u)
    fault();
  x_count++;
}

void action_y(void)
{
  if ((uint32_t)(scaled_y_count - x_count) < 0xFFFF0000u)
    scaled_y_count+=2;
}

在许多情况下，可能需要减少递增 scaled_y_count 时使用的比较中的常量，以限制 action_y 操作的数量 "stored up"。但是，在操作以 2:1 比例保持接近平衡的情况下，即使操作数超过 uint32_t.

的范围，上述方法也应该准确地工作。

如何安全地比较两个无符号整数计数器？

How to safely compare two unsigned integer counters?

c

c++

integer-overflow

unsigned-integer