所需：可包装计数器，其中<和>可以“正确地”处理

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中有类似的东西（事务ID包装），但我找不到实际执行它的函数。我很确定Linux内核中有这样的东西，可能是一个宏。但是既不能通过Google codesearch，也不能通过grep /usr/include/linux来找到它。有什么想法吗？

澄清了cur和dut的作用。"无效"是为了保障。当cur和dut之间的差异变大时，函数最终会抱怨。

- edgar.holleis

---

需要注意的是...你只需要<进行比较，因为可以这样做：lhs < rhs，rhs < lhs。如果其中一个成功了，你就得到了小于或大于的结果；如果两个都失败了，那么这两个数相等（或者如果你使用的语言无法重载运算符，则为相等）。 - workmad3

Answer 1

我认为你在谈论如何正确处理数字环的循环。实际上，这很容易。

这并没有完全按照你说的做（不确定为什么要有那个“exception”间隔），但是：

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“更晚”。这定义了“更早”和“更晚”的含义，既是最简单的数学概念，也是因为环形计数器可以被解释为在模65536下具有多个解决方案，它选择了与数字圆相对接近的a和b的解决方案。

如果a和b相差32768，则它们之间的距离相等，使用最简单的数学方法来选择最容易的...这“违反了”“更早”和“更晚”的反对称性，因为isLater(5,32773)为真，而isLater(32773,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;
}

现在不再使用closest函数；例如，当K=12768，a=5时，对于b=6,7,8,9,... 20005，isEarlier(a,b)和isLater(b,a)将为true，并且对于b=20006，20007，... 65534，65535，0，1，2，3，4，5，isEarlier(a,b)和isLater(b,a)将为false。

您有一种特定的间隔选择方式，与我在环绕数字中使用的原理不同。这里定义的函数不能满足您所述的需求，但我认为那些间隔选择有点奇怪。也许您可以解释一下如何确定它们？

- Jason S

---

抱歉，那行不通。diff = a-b 溢出了！请考虑 isEarlier(10000,50000) ：它应该是正确的，但是你的代码返回了错误结果。当然，除非你的机器在整数表示方面使用的不是二进制补码。 - edgar.holleis

diff=a-b 产生的结果是 10000-50000 smod 65536 = -40000 smod 65536 = 25536，其中 a smod m = (a+m/2) mod m) - m/2。10000 是在下一个 50000 计数之前的 40000 单位，但仅在最后一个 50000 计数之后的 25536 单位。 - Jason S

我认为更接近。你可能不这样认为，但你有自己特殊的“早”和“晚”的定义。 - Jason S

是的，你的方法可行，溢出是有意为之的。我没有仔细审查你的代码。我可能会使用它。 - edgar.holleis

2. 最初的问题对参数的含义并不是非常清楚。我的意思是第一个参数是当前计数器的值，第二个参数是要检查的值。在您的代码中用a和b替换后，它就实现了我的意图。

- edgar.holleis

Answer 2

首先计算差异，然后检查它落在哪个窗口中。

由于这很简单且过去/未来/错误窗口的大小不同，因此您必须自己完成。

- starblue

Answer 3

好的，记录一下。这是我的解决方案，也就是我想表达的意思：

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

- edgar.holleis

---

使用以下代码的测试用例：{cur = 10000, dut = 30000} => LATER {cur = 16000, dut = 36000} => FORBIDDEN这对你有意义吗？ - Jason S

我非常希望能够使用被禁止范围的功能，现在在原问题中已经明确说明。我非常清楚，在我的代码中，cur和dut之间的可接受跨度不是恒定的。但是，它保证了对于cur的每个值：16384个或更多的值是LATER，16384个或更多的值是EARLIER，16384个值是FORBIDDEN。 - edgar.holleis

好的。你听起来肯定知道自己想要什么，如果我有所推动而让你不舒服，那我很抱歉。（只是这个问题让我想起了我们公司遇到的一个案例，当时我们请了一位顾问，他认为自己知道该怎么做，但实际上却把本应该非常简单的程序搞得非常复杂……） - Jason S

Answer 4

在我看来，你刚刚已经写了它 :). 为什么不把你的帖子翻译成一些C代码呢？

- shodanex

Answer 5

请记住，在 C 语言中你无法让 ">" 和 "<" 像你想的那样工作。它们只适用于数字，而且没有操作符重载。对于异常情况也是如此；C 语言没有异常处理机制。

你可以编写一些访问函数，以这种方式处理无符号整数类型，并且这并不难。（在 C 语言中，有符号整数类型溢出是未定义的，尽管在大多数现代系统中，它会循环回来。）这并不难。

- David Thornley

---

这就是为什么我不会让它溢出的任何方式。这可能会与分析工具产生不良的业力。 - edgar.holleis

如果分析工具在处理无符号整数值溢出时出现问题，那么它们就有问题了。这在 C 语言中是完全合法的。 - David Thornley