Created
January 4, 2014 11:59
-
-
Save regularcoder/8254723 to your computer and use it in GitHub Desktop.
Fletcher's checksum in C#
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Created by SharpDevelop. | |
* Date: 1/4/2014 | |
* Time: 5:15 PM | |
* | |
* | |
*/ | |
using System; | |
using System.Text; | |
using System.Collections.Generic; | |
namespace Checksums | |
{ | |
/// <summary> | |
/// Calculates Fletcher's checksums | |
/// Sample outputs: | |
/// Fletcher16: "abcde" -> 51440 | |
/// Fletcher32: "abcde" -> 3948201259 | |
/// Fletcher64: "abcde" -> 14034561336514601929 | |
/// </summary> | |
public class FletcherChecksum | |
{ | |
/// <summary> | |
/// Transforms byte array into an enumeration of blocks of 'blockSize' bytes | |
/// </summary> | |
/// <param name="inputAsBytes"></param> | |
/// <param name="blockSize"></param> | |
/// <returns></returns> | |
private IEnumerable<UInt64> Blockify(byte[] inputAsBytes, int blockSize) | |
{ | |
int i = 0; | |
//UInt64 used since that is the biggest possible value we can return. | |
//Using an unsigned type is important - otherwise an arithmetic overflow will result | |
UInt64 block = 0; | |
//Run through all the bytes | |
while(i < inputAsBytes.Length) | |
{ | |
//Keep stacking them side by side by shifting left and OR-ing | |
block = block << 8 | inputAsBytes[i]; | |
i++; | |
//Return a block whenever we meet a boundary | |
if(i % blockSize == 0 || i == inputAsBytes.Length) | |
{ | |
yield return block; | |
//Set to 0 for next iteration | |
block = 0; | |
} | |
} | |
} | |
/// <summary> | |
/// Get Fletcher's checksum, n can be either 16, 32 or 64 | |
/// </summary> | |
/// <param name="inputWord"></param> | |
/// <param name="n"></param> | |
/// <returns></returns> | |
public UInt64 GetChecksum(String inputWord, int n) | |
{ | |
//Fletcher 16: Read a single byte | |
//Fletcher 32: Read a 16 bit block (two bytes) | |
//Fletcher 64: Read a 32 bit block (four bytes) | |
int bytesPerCycle = n / 16; | |
//2^x gives max value that can be stored in x bits | |
//no of bits here is 8 * bytesPerCycle (8 bits to a byte) | |
UInt64 modValue = (UInt64) (Math.Pow(2, 8 * bytesPerCycle) - 1); | |
//ASCII encoding conveniently gives us 1 byte per character | |
byte[] inputAsBytes = Encoding.ASCII.GetBytes(inputWord); | |
UInt64 sum1 = 0; | |
UInt64 sum2 = 0; | |
foreach (UInt64 block in Blockify(inputAsBytes, bytesPerCycle)) | |
{ | |
sum1 = (sum1 + block) % modValue; | |
sum2 = (sum2 + sum1) % modValue; | |
} | |
return sum1 + (sum2 * (modValue+1)); | |
} | |
} | |
} |
kzorin52
commented
Nov 1, 2021
In case it helps someone, here is another, simplified implementation for fletcher-64:
public static class FletcherChecksum
{
public static ulong ComputeFletcher64(byte[] input)
{
// Convert the input data into an array of 32bit blocks.
int blockCount = Math.DivRem(input.Length, sizeof(uint), out int rem) + (rem > 0 ? 1 : 0);
var blocks = new uint[blockCount];
Buffer.BlockCopy(input, 0, blocks, 0, input.Length);
// Use 2^32 − 1 as the modulus.
const ulong mod = uint.MaxValue;
ulong sum1 = 0;
ulong sum2 = 0;
foreach (ulong block in blocks)
{
sum1 = (sum1 + block) % mod;
sum2 = (sum2 + sum1) % mod;
}
// Combine checksums.
return (sum2 << 32) | sum1;
}
}
public class FletcherChecksumTests
{
[Test]
// Test cases taken from https://en.wikipedia.org/wiki/Fletcher%27s_checksum#Test_vectors.
[TestCase("abcde", 0xC8C6C527646362C6UL)]
[TestCase("abcdef", 0xC8C72B276463C8C6UL)]
[TestCase("abcdefgh", 0x312E2B28CCCAC8C6UL)]
public void ComputeFletcher64_ComputesCorrectResult(string input, ulong checksum)
{
byte[] bytes = Encoding.ASCII.GetBytes(input);
ulong result = FletcherChecksum.ComputeFletcher64(bytes);
result.Should().Be(checksum);
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment