public
Created

Fletcher's checksum in C#

  • Download Gist
FletcherChecksum.cs
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
/*
* 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));
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.