Fletcher 校验和从 32 位重制为 8 位

Question

这个转换是从原始版本开始的吗？

uint8_t fletcher8( uint8_t *data, uint8_t len )
{
    uint8_t sum1 = 0xff, sum2 = 0xff;

    while (len) {
            unsigned tlen = len > 360 ? 360 : len;
            len -= tlen;
            do {
                    sum1 += *data++;
                    sum2 += sum1;
                    tlen -= sizeof( uint8_t );
            } while (tlen);
            sum1 = (sum1 & 0xff) + (sum1 >> 4);
            sum2 = (sum2 & 0xff) + (sum2 >> 4);
    }
    /* Second reduction step to reduce sums to 4 bits */
    sum1 = (sum1 & 0xff) + (sum1 >> 4);
    sum2 = (sum2 & 0xff) + (sum2 >> 4);
    return sum2 << 4 | sum1;
    }

原文：

uint32_t fletcher32( uint16_t *data, size_t len )
{
    uint32_t sum1 = 0xffff, sum2 = 0xffff;

    while (len) {
            unsigned tlen = len > 360 ? 360 : len;
            len -= tlen;
            do {
                    sum1 += *data++;
                    sum2 += sum1;
                    tlen -= sizeof( uint16_t );
            } while (tlen);
            sum1 = (sum1 & 0xffff) + (sum1 >> 16);
            sum2 = (sum2 & 0xffff) + (sum2 >> 16);
    }
    /* Second reduction step to reduce sums to 16 bits */
    sum1 = (sum1 & 0xffff) + (sum1 >> 16);
    sum2 = (sum2 & 0xffff) + (sum2 >> 16);
    return sum2 << 16 | sum1;
    }

len 将是 8.

data 将有一个 data[] (1 - 8) 输入

实际上我不知道如何处理该行： unsigned tlen = len > 360？ 360：长度；

也许-> int8_t tlen = len > 255？ 255： 长度；

Answer 1

如何计算此 tlen 值

实际上我不知道如何处理这一行：unsigned tlen = len > 360？ 360：长度；

该行似乎来自旧版本此维基百科的 a>部分。现在已更改为 359，其基本原理在讨论页面上进行了解释。该数字仅适用于对 16 位实体求和，因为它是满足以下条件的最大数字n

n(n+5)/2 × (2¹⁶−1) < 2³²

换句话说，这是您可以在不执行模数归约的情况下添加块的最大次数，并且仍然避免溢出 uint32_t。对于 4 位数据字和 8 位累加器，相应的值为 4，计算公式为

n(n+5)/2 × (2⁴−1) < 2⁸

因此，如果您更改数据大小，则必须修改该行。您还可以更改代码以使用更大的数据类型来保存其总和，从而在减少之前对更多块求和。但在这种情况下，您可能需要在循环内执行多个缩减步骤。

例如，如果您要对 sum1 和 sum2 使用 uint32_t，那么您可以在溢出危险之前对 23927 个半字节求和，但之后您最多需要进行 7 次 sum1 = (sum1 & 0xf) + (sum1 >> 4) 形式的缩减才能将其归结为该范围1 到 0x1e，就像你原来的算法那样。将其写为 (sum1 - 1)%0xf + 1 可能会更有效。在这种情况下，您甚至可以将范围从 1 到 15 更改回 0 到 14，将总和初始化为 0 并将缩减结果写为 sum1 %= 0xf。除非您需要与使用其他范围的实现兼容。

Answer 2

我认为你需要 0xF 掩码而不是 0xFF。 32 位使用 16 位掩码，32 的一半，8 位使用 8 位掩码，它不是 8 的一半，4 位是 8 的一半。

uint8_t fletcher8( uint8_t *data, uint8_t len )
{
    uint8_t sum1 = 0xf, sum2 = 0xf;

    while (len) {
        unsigned tlen = len > 360 ? 360 : len;
        len -= tlen;
        do {
                sum1 += *data++;
                sum2 += sum1;
                tlen -= sizeof( uint8_t );
        } while (tlen);
        sum1 = (sum1 & 0xf) + (sum1 >> 4);
        sum2 = (sum2 & 0xf) + (sum2 >> 4);
    }
    /* Second reduction step to reduce sums to 4 bits */
    sum1 = (sum1 & 0xf) + (sum1 >> 4);
    sum2 = (sum2 & 0xf) + (sum2 >> 4);
    return sum2 << 4 | sum1;
}

否则，您将创建不同的校验和，而不是 Fletcher。例如 sum1 正在执行我认为所谓的补码校验和。基本上它是一个 16 位在前面和 4 位在你的情况下，校验和其中进位位被添加回来。在互联网协议中使用使得修改数据包变得非常容易，而不必计算整个数据包的校验和，你可以仅添加和减去现有校验和的更改。

额外的减少步骤是针对极端情况，如果使用四位方案 sum1 += *data = 0x1F 的结果，则添加进位位为 0x01 + 0x0F = 0x10，您需要将该进位位添加回循环外也是如此 0x01 + 0x00 = 0x01。否则循环外的总和将加零。根据您的架构，您可能会使用 if(sum1&0x10) sum1=0x01; 之类的命令执行得更快。而不是狡猾地添加可能需要更多指令的东西。

当两者组合时，它不仅仅是一个带有进位位的校验和，而是最后一步。例如，如果您仅使用 32 位 fletcher 作为 16 位校验和，那么您就浪费了时间，结果的低 16 位只是一个库存校验和，并添加了进位位，没有什么特别的。 sum2 是一个有趣的数字，因为它是 sum1 校验和的累加（sum1 是数据的累加，sum2 是校验和的累加）。

Answer 3

原始版本中 sum1,sum2 是 32 位的。这就是为什么后来发生位移的原因。在您的情况下，您声明 sum1,sum2 为 8 位，因此位移没有意义。