Необходимый:Упаковываемый счетчик, где < и > поступать “правильно”
Вопрос
Мне нужен код для куттера, которому разрешено переполняться и где < > продолжайте отличать более ранние значения от более поздних значений в течение некоторого определенного интервала.
Чтобы уточнить, одной из возможных реализаций было бы:
Рассмотрим два таких счетчика cur
и dut
(тестируемое устройство), рассмотрим две функции:
bool isEarlier(cur, dut) // Is dut earlier than cur?
bool isLater(cur, dut)
cur
и dut
являются 16 битными, cur
только что переполнился, его текущее значение, скажем так 5
.В зависимости от значения dut
, функции возвращали бы
- от 0 до 16384:Раньше ->
(cur < dut)
, Островище ->(cur > dut)
- с 16384 по 32768:Более ранний -> ложный, более поздний -> истинный
- с 32768 по 49152:недопустимый, ошибка журнала
- с 49152 по 65536:Более ранний -> true, более поздний -> false
Я могу написать код сам, без проблем.Я просто ленивый.Я точно знаю, что в PostgreSQL есть что-то подобное (перенос идентификаторов транзакций), я просто не смог найти функцию, которая на самом деле это делает.Я почти уверен, что в ядре Linux есть что-то подобное, возможно, макрос.Но ни Google codesearch, ни grep через / usr / include / linux не смогли бы это сделать.Есть какие-нибудь идеи, где это находится?
Уточнена роль cur и dut."Недействительный" существует в качестве гарантии.Поскольку различия между cur и dut становятся больше, функция в конечном итоге жалуется.
Решение
Я думаю, вы говорите о правильном обращении с окружностью числового круга.На самом деле это довольно просто.
Это не совсем то, что вы сказали (не уверен, почему у вас есть этот интервал "исключения"), но:
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;
}
Редактировать:это имеет "точку разветвления" при diff =-32768, так что, если a = 5 и b = 32772, diff =-32767, что меньше 0 и, следовательно, 5 "раньше", чем 32772.Если a = 5 и b = 32774, diff =-32769 = 32767, что больше 0 и, следовательно, 5 "позже", чем 32774.Это определяет "раньше" и "позже" в смысле (а) простейшей математики, и (б) поскольку счетчики обхода могут интерпретироваться как имеющие несколько решений mod 65536, он выбирает решение a и b, которые "ближе" друг к другу по отношению к числовому кругу.
Если a и b отличаются на 32768, то они находятся на одинаковом расстоянии друг от друга, и для выбора используется простая математика...это "нарушает" антисимметричное свойство "раньше" и "позже" в том смысле, что isLater(5,32773) истинно и isLater (32773,5) также истинно.Но как вы узнаете, представляет ли "5" количество 5, или "5" представляет количество 65541?(точно так же, как abs(-32768) == -32768 дает нечетный бессмысленный ответ) Если вы хотите сохранить антисимметрию, напримерБолее поздний(b, a) == Более ранний(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, более ранние (a,b) и более поздние (b, a) будут истинными, и для b = 20006, 20007, ...65534, 65535, 0, 1, 2, 3, 4, 5 Значения isEarlier(a,b) и isLater(b,a) будут равны false.
У вас есть определенный выбор интервалов, который отличается от обоснования, которое я использую с обернутыми числами.Функции, определенные здесь, не будут соответствовать вашим потребностям, как указано, но я нахожу этот выбор интервала немного странным.Возможно, вы могли бы объяснить, как вы их определили?
Другие советы
Сначала вычислите разницу, затем проверьте, в какое окно она попадает.
Поскольку это так просто, а размеры окон прошлого / будущего / ошибок различаются, вы должны сделать это сами.
Хорошо, для протокола.Вот мое решение, это то, что я имел в виду:
#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;
}
}
Мне кажется, вы только что это написали :).Почему бы не перевести ваш пост на какой - нибудь C - код ?
Имейте в виду, что вы не можете получить ">" и "<" делать то , что ты хочешь в C.Они применяются только к номерам, и никакой перегрузки оператора не происходит.То же самое относится и к вашему исключению;C не имеет исключений.
Вы могли бы написать некоторые функции доступа, которые таким образом обрабатывали бы целочисленные типы без знака, и это было бы несложно.(В C переполнение не определено для целочисленных типов со знаком, хотя в большинстве современных систем оно обтекается.) Это было бы не так сложно.