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 将输入 data[] (1 - 8)

其实我不知道如何处理这条线: unsigned tlen = len > 360 ？ 360:长度；

也许-> int8_t tlen = len > 255 ？第255章

Answer 1

如何计算 tlen值(value)

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 个半字节求和，但在那之后，你需要对 sum1 = (sum1 & 0xf) + (sum1 >> 4) 形式进行多达 7 次归约。将其归结为 1 范围通过 0x1e ，您的原始算法执行此操作的方式。将其写为 (sum1 - 1)%0xf + 1 可能更有效.在这种情况下，您甚至可以将范围从 1 到 15 更改回 0 到 14，将总和初始化为 0 并将减少写为 sum1 %= 0xf .除非您需要与使用其他范围的实现兼容。