Home > Back-end >  Fletcher 32-bit checksum test vectors
Fletcher 32-bit checksum test vectors

Time:02-26

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

CodePudding user response:

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[]         = 0xX\n", actCkSum );
  printf( "Expected Checksum of array data[]         = 0xX\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] = 0xX\n", actCkSum );
  printf( "Expected Checksum of array data[100:1000] = 0xX\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] = 0xX\n", actCkSum );
  printf( "Expected Checksum of array data[100:1001] = 0xX\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]     = 0xX\n", actCkSum );
  printf( "Expected Checksum of array data[0:60]     = 0xX\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]     = 0xX\n", actCkSum );
  printf( "Expected Checksum of array data[0:61]     = 0xX\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     = 0xX\n", actCkSum );
  printf( "Expected Checksum of array abcdefgh     = 0xX\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       = 0xX\n", actCkSum );
  printf( "Expected Checksum of array abcdef       = 0xX\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        = 0xX\n", actCkSum );
  printf( "Expected Checksum of array abcde        = 0xX\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
  • Related