4

我需要将代码发送到一个允许溢出的计数器，并且 < > 在某个定义的时间间隔内继续从后面的值中区分早期值。

为了澄清，一种可能的实现是：

考虑两个这样的计数器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 中有类似的东西（事务 ids wrap），我只是找不到实际执行它的函数。我很确定 Linux 内核中有类似的东西，可能是一个宏。但是无论是 Google 代码搜索还是 grep over /usr/include/linux 都无法打开它。任何想法它在哪里？

明确了 cur 和 dut 的作用。“无效”是有保障的。随着 cur 和 dut 之间的差异变大，函数最终会报错。

4

5 回答 5

3

我认为您正在谈论正确处理数字圈的环绕。实际上，这很容易。

这并没有完全按照您所说的进行（不确定为什么您有那个“异常”间隔），但是：

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“晚”。这定义了（a）最简单的数学意义上的“早”和“晚”，以及（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) 将为假。

您可以选择特定的间隔，这与我使用环绕数字的基本原理不同。这里定义的函数不能满足你所​​说的需求，但我发现这些间隔的选择有点奇怪。也许您可以解释一下您是如何确定它们的？

于 2009-01-19T17:41:06.437 回答
1

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

由于它是如此简单，并且过去/未来/错误窗口的大小各不相同，因此您必须自己做。

于 2009-01-19T16:14:55.487 回答
1

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

#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;
    }
}
于 2009-01-20T00:46:28.370 回答
0

在我看来你刚刚写了它:)。为什么不将您的帖子翻译成一些 C 代码？

于 2009-01-19T15:56:28.970 回答
0

请记住，您无法在 C 中使用“>”和“<”来执行您想要的操作。它们仅适用于数字，并且没有运算符重载。同样的事情也适用于你的例外；C 没有例外。

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

于 2009-01-19T16:04:23.243 回答