Требуется: Wrappable Counter, где <и> делают "правильные вещи"

Question

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

Чтобы уточнить, одна из возможных реализаций будет:

Рассмотрим два таких счетчика cur и dut (тестируемое устройство), рассмотрим две функции:

bool isEarlier(cur, dut)    // Is dut earlier than cur?
bool isLater(cur, dut)

cur и dut 16-битные, cur только что переполнился, его текущее значение, скажем, 5. В зависимости от значения dut функции будут возвращать

• 0 до 16384: isEarlier -> (cur < dut), isLater -> (cur > dut)
• 16384 - 32768: isEarlier -> false, isLater -> true
• 32768 - 49152: неверно, ошибка журнала
• 49152 - 65536: isEarlier -> true, isLater -> false

Я могу написать код сам, без проблем. Я просто ленивый. Я точно знаю, что в PostgreSQL есть что-то подобное (перенос идентификаторов транзакций), я просто не смог найти функцию, которая на самом деле это делает. Я уверен, что в ядре Linux есть что-то подобное, возможно, макрос. Но ни Google Codesearch, ни grep над / usr / include / linux не могли бы его включить. Есть идеи где это?

Уточнена роль cur и dut «Недействительный» существует в качестве гарантии. По мере того, как различия между cur и dut становятся больше, функция в конечном итоге жалуется.

Answer 1

Я думаю, вы говорите о правильной обработке переноса числа. Это довольно просто, на самом деле.

Это не совсем то, что вы сказали (не уверен, почему у вас такой интервал "исключения"), но:

typedef unsigned short uint16_t;
typedef signed short int16_t;
// abstract out 16-bit types in case "short" doesn't correspond to 16bits

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff < 0;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = a-b;
   return diff > 0;
}

edit : это имеет "точку ветвления" в diff = -32768, так что если a = 5 и b = 32772, diff = -32767, что меньше 0 и, следовательно, 5 "раньше" «чем 32772. Если a = 5 и b = 32774, diff = -32769 = 32767, что больше 0 и, следовательно, 5« позже », чем 32774. Это определяет« раньше »и« позже »в смысле (а) простейшая математика, и (b), поскольку счетчики циклического переноса могут интерпретироваться как имеющие несколько решений mod 65536, он выбирает решения a и b, которые являются «наиболее близкими» друг к другу относительно круга чисел.

Если a и b отличаются на 32768, то они одинаково далеки друг от друга, и простая математика используется для выбора наиболее простого ... это "нарушает" антисимметричное свойство "ранее" и "позже" в том смысле, что isLater (5 , 32773) верно и isLater (32773,5) также верно. Но как вы узнаете, представляет ли «5» счет 5 или «5» 65541? (так же, как abs (-32768) == -32768 дает странный бессмысленный ответ) Если вы хотите сохранить антисимметрию, например isLater (b, a) == isEarlier (a, b), тогда вы всегда можете сделать это:

bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a;
   return diff < 0;
}

Если вы хотите сместить точку ветвления в одном направлении, чтобы это произошло при -32768 + K, используйте вместо этого:

bool isEarlier(uint16_t a, uint16_t b)
{
   int16_t diff = a-b-K;
   return diff < -K;
}
bool isLater(uint16_t a, uint16_t b)
{
   int16_t diff = b-a-K;
   return diff < -K;
}

Это больше не использует ближайший; если, например, K = 12768 и a = 5, то для b = 6,7,8,9, ... 20005, isEarlier (a, b) и isLater (b, a) будут истинными, а для b = 20006, 20007, ... 65534, 65535, 0, 1, 2, 3, 4, 5 isEarlier (a, b) и isLater (b, a) будут ложными.

У вас есть определенный выбор интервалов, который отличается от обоснования, которое я использую с числами с циклом. Определенные здесь функции не будут соответствовать вашим потребностям, как указано, но я считаю, что выбор интервала немного необычен. Возможно, вы могли бы объяснить, как вы их определили?

Answer 2

Хорошо, для записи. Вот мое решение, это то, что я имел в виду:

#include <stdint.h>


void increase_cyclic_counter (uint16_t *cnt)
{
#ifdef CYCLIC_COUNTER_EXPLICIT_WRAP
    if (*cnt < 2^16-1)
        *cnt++;
    else
        *cnt = 0;
#else
    *cnt++;
#endif
}


#define SAME 1
#define LATER 0
#define EARLIER 2
#define FORBIDDEN -1

/* dut (device under test) is tested against cur
 * returns:
 *    EARLIER (LATER) if dut happened earlier (later) in the sequence than cur
 *    SAME            if dut == cur
 *    FORBIDDEN       if dut and cur are that far away in the cyclic sequence
 *                    that no unambigious jugement is possible
 *
 * The basic idea is the same as with two-character year codes, where 
 * '97' stands for 1997 and '11' stands for 2011. '50' is regarded as 
 * too ambigous and therefore rejected.
 *
 * The implementation splits the short integer range 0-65535 into 4 parts:
 *   0-16383, 16384-32767, 32768-49151, 49152-65536
 * With cur and dut in the same range, normal arithmetics apply, else the 
 * ranges are compared to each other.
 */

int test_cyclic_counter (uint16_t cur, uint16_t dut)
{
    switch (((int)(cur>>14)) - ((int)(dut>>14)))
    {
        case 0:  // same range
            if (dut < cur) 
                return EARLIER;
            else if (dut == cur)
                return SAME;
            else 
                return LATER;

        case 1:
        case -3:
            return EARLIER;

        case 3:
        case -1:        
            return LATER;

        default: 
            return FORBIDDEN;
    }
}

Answer 3

Сначала вычислите разницу, затем проверьте, в какое окно она падает.

Поскольку это так просто и размеры окон прошлого / будущего / ошибки различаются, вы должны сделать это сами.

Answer 4

Имейте в виду, что вы не можете заставить ">" и "<" делать то, что вы хотите в C. Они применяются только к числам, и оператор не перегружен. То же самое относится и к вашему исключению; C не имеет исключений. </p>

Вы можете написать некоторые функции доступа, которые будут обрабатывать целочисленные типы без знака таким образом, и это не составит труда. (В C переполнение не определено для целочисленных типов со знаком, хотя в большинстве современных систем это происходит.) Это не будет так сложно.

Answer 5

Мне кажется, вы только что написали это :). Почему бы не перевести ваш пост в какой-нибудь код на C?