Как безопасно сравнить два беззнаковых целых счетчика?

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

Если вы хотите, чтобы действие 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 операций может быть «сохранено».Вышеуказанное, однако, должно работать именно в тех случаях, когда операции остаются где-то близко к сбалансированным в соотношении 2: 1, даже если число операций превышает диапазон uint32_t.

Answer 2

Размещенный код на самом деле, кажется, не использует счетчики, которые могут обернуться.

В комментарии в коде говорится, что безопаснее сравнивать a/2 > b вместо a > 2*b, потому что последнее потенциально может переполниться, а первое - нет.Это особенно верно для типа a больше, чем тип b.

Answer 3

Я думаю, вы неправильно интерпретировали комментарий в коде:

Мы делим на два, чтобы не переполнить iter_c * 2.

Независимо от того, откуда поступают значениянаписать a/2 безопасно, но писать a*2 небезопасно.Какой бы тип без знака вы ни использовали, вы всегда можете разделить число на два, а умножение может привести к переполнению.

Если условие будет записано так:

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

, то примерно половина входных данных вызовет неправильное условие.При этом, если вы беспокоитесь о переполнении счетчиков, вы можете заключить их в класс:

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 4

Обратите внимание на переполнения по мере их возникновения.

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 5

Нормализуйте значения, как только они будут перенесены, вынуждая их одновременно переносить.Сохраняйте разницу между ними, когда они переносятся.

Попробуйте что-то вроде этого;

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 6

Если даже использования 64 бит недостаточно, то вам нужно кодировать свой собственный метод "var increment" вместо перегрузки оператора ++ (который может испортить ваш код, если вы не будете осторожны).
Метод просто сбрасывает var на '0' или другое какое-либо значащее значение.