代码之家 › 专栏 › 技术社区 › edgar.holleis

需要:wrappable counter where<and>do“the right thing”,language C

wrap overflow count c

4

edgar.holleis · 技术社区 · 17 年前

我需要一个允许溢出的计数器的代码,在这里,对于某些定义的时间间隔,lt;gt;继续将早期的值与后期的值区分开来。

为了澄清,一种可能的实施方式是:

考虑两个这样的柜台 cur 和 dut (正在测试的设备),考虑两个功能:

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

库尔 和 杜特 是16位, 库尔 刚刚溢出,它的当前值是,比方说 5 . 取决于 杜特 ,函数将返回

0到16384:i更早-> (cur < dut) IsHelp & Gt; (cur > dut)
16384到32768:IsEarlier->假,IsLater->真
32768到49152:无效,日志错误
49152到65536:isearlier->真,islater->假

更新 : 我可以自己写代码,没问题。我只是懒惰。我知道在PostgreSQL(TransactionIDsWrap)中有类似的东西,我只是找不到实际执行它的函数。我很确定Linux内核中有类似的东西,可能是宏。但是谷歌的代码搜索,或者grep over/usr/include/linux都可以打开它。你知道它在哪里吗?

更新 :阐明了CUR和DUT的作用。“无效”是作为一种保障。随着CUR和DUT之间的差异越来越大,该功能最终会产生抱怨。

5 回复 | 直到 17 年前

1

3

Jason S 17 年前

我想你说的是正确处理数字圈的包围圈。实际上,这很容易。

这并不完全符合你所说的(不确定为什么会有“异常”间隔),但是:

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(532773)是真的,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等早期(A、B)和更高级(B、A)将为假。

您有一个特定的间隔选择,这与我使用的环绕数的基本原理不同。这里定义的函数不能满足您的需求,但是我发现这些间隔的选择有点特别。也许你可以解释一下你是如何决定的?

2

1

starblue 17 年前

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

因为它非常简单,过去/未来/错误窗口的大小也各不相同,所以您必须自己做。

3

1

edgar.holleis 17 年前

好的,记录在案。这是我的解决方案,这就是我的意思:

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

4

0

shodanex 17 年前

在我看来,你刚刚写的是:)。为什么不把你的文章翻译成C代码呢?

5

0

David Thornley 17 年前

请记住,您不能让“>”和“<”在C中执行您想要的操作。它们仅适用于数字,并且不存在运算符重载。同样的事情也适用于您的异常;C没有异常。

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