c - 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[] (1 - 8)

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

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

Answer 1

如何计算 tlen值

Actually I don't know what to do with the line: unsigned tlen = len > 360 ? 360 : len;

该行似乎来自 an old version的this Wikipedia section 。现在已经改为359，理由在talk page上有解释。 。该数字仅适用于对 16 位实体求和，因为它是满足 n 的最大数字

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

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

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

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

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