Fletcher 32 位校验和测试向量

Question

我有一些 C# 代码（但与语言无关）可在 16 位字数组上生成 32 位 Fletcher 校验和。我的问题是我已经实现了优化算法，在网上搜索了一个多小时后，我只能在维基百科上找到测试向量“abcde”、“abcdef”和“abcdefgh”。

我希望有人可以提供一些向量给我，以帮助我验证正确的实现；或者有人可以使用以下代码重现我的测试向量并得到与我得到的相同的答案。

我的校验和代码在第一次求和之前使用 0xFFFF 为求和值设置种子，因此如果我需要在针对其他人的向量进行测试之前更改种子值，那很好。向构造函数添加种子值是一个微不足道的练习。

我知道可能还有其他应用程序或网页也可以用来测试，但我找不到它们。

我的矢量生成代码：

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

以及根据我的向量计算的校验和：

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

Answer 1

使用@Craig_Estey 评论作为答案。下面显示了我所做的以及答案。我什至比较了优化与 non-optimized 以确保在我的单元测试代码中使用之前这里的答案是正确的。非常感谢！

#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");
}

并且输出：

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

Fletcher 32 位校验和测试向量

Fletcher 32-bit checksum test vectors

language-agnostic

testing

algorithm