Remake of Fletcher checksum from 32bit to 8

问题:

Is this conversion right from the original?

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

Original:

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 will be 8.

data will have an input of data[] (1 - 8)

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

Maybe -> int8_t tlen = len > 255 ? 255 : len;

回答1:

I think you need 0xF masks throughout not 0xFF. The 32 bit uses a 16 bit mask, half of 32, your 8 bit uses an 8 bit mask which is not half of 8, 4 bits is half of 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;
}

Otherwise you are creating a different checksum, not Fletcher. sum1 for example is performing what I think is called a ones complement checksum. Basically it is a 16 bit in prior and 4 bit in your case, checksum where the carry bits are added back in. used in internet protocols makes it very easy to modify a packet without having to compute the checksum on the whole packet, you can add and subtract only the changes against the existing checksum.

The additional reduction step is for a corner case, if the result of sum1 += *data = 0x1F using a four bit scheme, then the adding of the carry bit is 0x01 + 0x0F = 0x10, you need to add that carry bit back in as well so outside the loop 0x01 + 0x00 = 0x01. Otherwise that outside the loop sum is adding in zero. Depending on your architecture you might execute faster with something like if(sum1&0x10) sum1=0x01; than the shifty adding thing that may take more instructions.

Where it becomes something more than just a checksum with the carry bits added in is that last step when the two are combined. And if you for example only use the 32 bit fletcher as a 16 bit checksum, you have wasted your time, the lower 16 bits of the result are just a stock checksum with the carry bit added back in, nothing special. sum2 is the interesting number as it is an accumulation of sum1 checksums (sum1 is an accumulation of the data, sum2 is an accumulation of checksums).

回答2:

How to compute this tlen value

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

That line appears to come from an old version of this Wikipedia section. It has been changed to 359 by now, with the rationale explained on the talk page. The number only applies to summing 16 bit entities, as it is the largest number n satisfying

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

In other words, this is the larges number of times you can add blocks without performing a modulo reduction, and still avoid overflowing the uint32_t. For 4 bit data words and a 8 bit accumulator, the corresponding value will be 4, computed using

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

So you have to modify that line if you change your data size. You could also change the code to use a larger data type to keep its sums, thus summing more blocks before the reduction. But in that case, you might require more than one reduction step inside the loop.

For example, if you were to use uint32_t for sum1 and sum2, then you could sum 23927 nibbles before danger of overflow, but after that you would require up to 7 reductions of the form sum1 = (sum1 & 0xf) + (sum1 >> 4) to boil this down to the range 1 through 0x1e, the way your original agorithm does it. It might be more efficient to write this as (sum1 - 1)%0xf + 1. In which case you might even change the range back from 1 through 15 to 0 through 14, initialize the sums to 0 and write the reduction as sum1 %= 0xf. Unless you require compatibility with an implementation that uses the other range.

回答3:

in the original version sum1,sum2 are 32-bit. that is why the bit shifting afterwards. In your case you declare sum1,sum2 to be 8 bit so bit shifting makes no sense.