Skip to content

Instantly share code, notes, and snippets.

@regularcoder
Created January 4, 2014 11:59
Show Gist options
  • Save regularcoder/8254723 to your computer and use it in GitHub Desktop.
Save regularcoder/8254723 to your computer and use it in GitHub Desktop.
Fletcher's checksum in C#
/*
* 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
Copy link

kzorin52 commented Nov 1, 2021

IEnumerable<ulong> Blockify(IReadOnlyList<byte> inputAsBytes, int blockSize)
{
    var i = 0;
    ulong block = 0;

    while (i < inputAsBytes.Count)
    {
        block = (block << 8) | inputAsBytes[i];
        i++;

        if (i % blockSize != 0 && i != inputAsBytes.Count) continue;

        yield return block;
        block = 0;
    }
}

byte[] GetFletcher(IReadOnlyList<byte> input, int n = 32) // Fletcher 32, 16, 64
{
    var bytesPerCycle = n / 16;
    var modValue = (ulong) (Math.Pow(2, 8 * bytesPerCycle) - 1);

    ulong sum1 = 0;
    ulong sum2 = 0;

    foreach (var block in Blockify(input, bytesPerCycle))
    {
        sum1 = (sum1 + block) % modValue;
        sum2 = (sum2 + sum1) % modValue;
    }

    return BitConverter.GetBytes(sum1 + sum2 * (modValue + 1));
}

@MarcusWichelmann
Copy link

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