I've got some C# code (but the language is irrelevant) that generates a 32-bit Fletcher checksum on an array of 16-bit words. My issue is that I've implemented an optimized algorithm, and after an hour or more of searching the web, I can only find test vectors "abcde", "abcdef", and "abcdefgh" on wikipedia.
I'm hoping that someone has some vectors that they can provide to me to help me verify a correct implementation; OR someone can reproduce my test vectors with the following code and get the same answers that I got.
My checksum code seeds the summation values with 0xFFFF before the first summation, so if I need to change the seed value before testing against someone else's vectors, that's fine. Adding a seed value to the constructor is a trivial exercise.
I realize that there may be other applications or web pages that I can use to test as well, but I've not been able to find them.
My vector generation code:
byte[] d1 = new byte[1878];
byte[] d2 = new byte[60];
byte[] d3 = new byte[61];
byte[] d4 = new byte[900];
byte[] d5 = new byte[901];
for( int i = 0; i < d1.Length; ++i )
{
d1[i] = (byte)( 13 * i );
}
Array.Copy( d1, 0, d2, 0, 60 );
Array.Copy( d1, 0, d3, 0, 61 );
Array.Copy( d1, 100, d4, 0, 900 );
Array.Copy( d1, 100, d5, 0, 901 );
And the checksum calculated on my vectors:
Checksum of array data[0:60] = 0xE35DC23D
Checksum of array data[0:61] = 0xA5A7C249
Checksum of array data[100:1000] = 0xBDDF3B63
Checksum of array data[100:1001] = 0xFA0A3C2B
Checksum of array data[] = 0xCBD2B70C
Going with @Craig_Estey comment as answer. What I did is shown below, along with answers. I even compared optimized vs. non-optimized to ensure the answers here are correct before using in my unit test code. Thanks SO!
#include "stdint.h"
#include "stdio.h"
#include "stdlib.h"
// ===========================================================================
uint32_t fletcher32(const uint16_t *data, int len) {
uint32_t s0 = 0x0FFFF;
uint32_t s1 = 0x0FFFF;
for( int i = 0; i < len; ++i ) {
s0 = ( s0 + data[i] ) % 65535;
s1 = ( s1 + s0 ) % 65535;
}
return (s1 << 16 | s0);
}
// ===========================================================================
uint32_t fletcher32_opt(const uint16_t *data, size_t len) {
uint32_t c0, c1;
len = (len + 1) & ~1; /* Round up len to words */
c0 = 0x0FFFF;
c1 = 0x0FFFF;
/* We similarly solve for n > 0 and n * (n+1) / 2 * (2^16-1) < (2^32-1) here. */
/* On modern computers, using a 64-bit c0/c1 could allow a group size of 23726746. */
for (c0 = c1 = 0; len > 0; ) {
size_t blocklen = (len > 360*2) ? 360*2 : len;
len -= blocklen;
do {
c0 = c0 + *data++;
c1 = c1 + c0;
} while ((blocklen -= 2));
c0 = c0 % 65535;
c1 = c1 % 65535;
}
return (c1 << 16 | c0);
}
// ===========================================================================
void main() {
uint16_t * d1 = malloc(sizeof(uint16_t) * 1878/2);
uint16_t x[4] = { (uint16_t)( 'a' | ('b' << 8) ),
(uint16_t)( 'c' | ('d' << 8) ),
(uint16_t)( 'e' | ('f' << 8) ),
(uint16_t)( 'g' | ('h' << 8) ) };
uint16_t lsb, msb;
uint32_t actCkSum, expCkSum;
// generate pseudo-random array of bytes, assembling them into words
for( int i = 0, idx = 0; i < 1878; i += 2, ++idx ) {
lsb = 0x0FF & ( 13 * ( i + 0 ) );
msb = 0x0FF & ( 13 * ( i + 1 ) );
d1[idx] = ( msb << 8 ) | lsb;
}
expCkSum = fletcher32( d1, 1878/2 );
actCkSum = fletcher32_opt( d1, 1878 );
printf( "Actual Checksum of array data[] = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array data[] = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
expCkSum = fletcher32( &d1[50], 450 );
actCkSum = fletcher32_opt( &d1[50], 900 );
printf( "Actual Checksum of array data[100:1000] = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array data[100:1000] = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
d1[500] = d1[500] & 0x00FF;
expCkSum = fletcher32( &d1[50], 451 );
actCkSum = fletcher32_opt( &d1[50], 901 );
printf( "Actual Checksum of array data[100:1001] = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array data[100:1001] = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
expCkSum = fletcher32( d1, 30 );
actCkSum = fletcher32_opt( d1, 60 );
printf( "Actual Checksum of array data[0:60] = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array data[0:60] = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
d1[30] = d1[30] & 0x00FF;
expCkSum = fletcher32( d1, 31 );
actCkSum = fletcher32_opt( d1, 61 );
printf( "Actual Checksum of array data[0:61] = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array data[0:61] = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
printf("\n");
actCkSum = fletcher32_opt( x, 8 );
expCkSum = fletcher32( x, 4 );
printf( "Actual Checksum of array abcdefgh = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array abcdefgh = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
actCkSum = fletcher32_opt( x, 6 );
expCkSum = fletcher32( x, 3 );
printf( "Actual Checksum of array abcdef = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array abcdef = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
x[2] = x[2] & 0x00FF;
actCkSum = fletcher32_opt( &x[0], 5 );
expCkSum = fletcher32( &x[0], 3 );
printf( "Actual Checksum of array abcde = 0x%08X\n", actCkSum );
printf( "Expected Checksum of array abcde = 0x%08X\n", expCkSum );
printf( "Checksum %s match expected value\n\n", expCkSum == actCkSum ? "does" : "DOES NOT" );
printf("\n");
}
And the output:
Actual Checksum of array data[] = 0xCBD2B70C
Expected Checksum of array data[] = 0xCBD2B70C
Checksum does match expected value
Actual Checksum of array data[100:1000] = 0xBDDF3B63
Expected Checksum of array data[100:1000] = 0xBDDF3B63
Checksum does match expected value
Actual Checksum of array data[100:1001] = 0xFA0A3C2B
Expected Checksum of array data[100:1001] = 0xFA0A3C2B
Checksum does match expected value
Actual Checksum of array data[0:60] = 0xE35DC23D
Expected Checksum of array data[0:60] = 0xE35DC23D
Checksum does match expected value
Actual Checksum of array data[0:61] = 0xA5A7C249
Expected Checksum of array data[0:61] = 0xA5A7C249
Checksum does match expected value
Actual Checksum of array abcdefgh = 0xEBE19591
Expected Checksum of array abcdefgh = 0xEBE19591
Checksum does match expected value
Actual Checksum of array abcdef = 0x56502D2A
Expected Checksum of array abcdef = 0x56502D2A
Checksum does match expected value
Actual Checksum of array abcde = 0xF04FC729
Expected Checksum of array abcde = 0xF04FC729
Checksum does match expected value