How to Calculate Checksum

Checksums of various kinds are commonly used in data communication protocols to allow the recipient of a message to determine, quickly and easily, whether the data is likely to have been corrupted in transit. If you add all the bytes of a message together and find (neglecting overflow) that the sum is 96, then you tack that number onto the message before sending it, the recipient can repeat your summation on the first N – 1 byte of the message, and compare the result to the final byte to see if it’s 96. If so, the recipient can infer that the message probably (arguably) wasn’t altered in transit.

You’ll find a wide array of checksum techniques in common use. Three of the most popular ones are the conventional checksum, LRC (longitudinal redundancy check), and CRC (cyclic redundancy check). The latter isn’t really a checksum in the usual sense but is an example of a one-way hash that falls in the “linear congruential generator” family.

Notice, earlier, I said these data-integrity techniques can tell you whether data is “likely to have been corrupted.” No checksum technique is 100% foolproof in the general case, for arbitrary-length data. But some techniques are definitely better than others.

Let’s take a look at how to calculate LRC, checksum, and CRC using JavaScript.

How to Calculate Checksum Traditionally

The conventional 8-bit checksum is just what it sounds like: a sum of all bytes values in the input, with any overflow (from carry operations) discarded. In JavaScript:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function CHECKSUM(hexstring) {

		var s = hexstring.match(/../g);
		var sum = 0;
		s.forEach(function (hexbyte) {
			var n = 1 * ('0x' + hexbyte); // convert hex to number
			sum += n;
		});
		sum = (sum & 255).toString(16);
		if (sum.length % 2)
			sum = '0' + sum;
		return sum;
}

The input to this function is expected to be a hexstring that looks something like “48656C6C6F20776F726C6421” (which, in this case, is the hex version of the ASCII string “Hello world!”). If we use “48656C6C6F20776F726C6421” as input to the above function, the output will be “5d,” which is the hex value of the final 8-bit sum.

The code is very simple. We start (in Line 3) by parsing the hex input into two-nibble chunks using the regular expression /../g — which means find substrings that match the pattern “anything followed by anything” (that’s what the two dots mean), and do it globally (that’s what the ‘g’ means).” The result is an array, s, of two-digit hex values.

At Line 5, we enter a loop (using the forEach iteration construct) in which we convert the string version of a two-nibble hex value to an actual number that we can operate on. In Line 7, we do the actual summation. Note that the number sum is essentially a 32-bit integer, behind the scenes, meaning our final value could be much larger than 255. When we’re finished looping, we need to be sure to constrain the sum to an 8-bit value. We do that in Line 9, with the logical-AND against 255. At the same time, we convert back to hex using the toString() method, with an argument of 16 (meaning we want to use radix-16 or “base 16” in our final representation of the number).

In Lines 10 and 11, we need to check that the final hex value is two nibbles long. JavaScript’s toString(16) operation returns a single-digit value for values less than 10. In that case, we need to prepend ‘0’ to the answer.

If you want to try the code out, copy and paste the above code into your JS console (in Chrome, use Shift-Cmd-J to get the console), then add a line, at the bottom (outside the function), of CHECKSUM(“48656C6C6F20776F726C6421”). When you hit Enter, the console should show ‘5d’ as the return value.

How to Calculate Checksum w/LRC

Longitudinal redundancy check (LRC) is a variation on the 8-bit checksum, differing only in that the “summation” is done using XOR, instead of numerical addition.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function LRC(hexstring) {
		var s = hexstring.match(/../g);
		var lrc = 0;
		s.forEach(function (hexbyte) {
			var n = 1 * ('0x' + hexbyte);
			lrc ^= n;
		});

		lrc = lrc.toString(16);
		if (lrc.length % 2)
			lrc = '0' + lrc;
		return lrc;
}

In Line 6, you can see the XOR-in-place operator (^=).

Since XOR never overflows, we don’t have to constrain the final result to 8 bits with an AND. We simply check for a two-nibble length, then return the final value.

If you try the code in the console using the string shown further above, you should get an answer of ’21’.

Critique OF Checksum And LRC

Neither checksum nor LRC can be considered robust against message corruption. For example, consider the original message (“48656C6C6F20776F726C6421”); suppose we change the last two bytes of the message from 6421 to 6520. Both the LRC and the checksum remain unchanged! (We simply turned one bit ON in an upstream byte, and turned the same-position bit OFF downstream, creating two changes that cancel each other out at checksum time.)

Likewise, consider what happens if you invert the message (that is, you reverse the message bytewise, so that it starts with 21 and ends with 48). Again, LRC and checksum remain the same as they were for the original message. That’s because XOR and addition are commutative. A + B will always equal B + A.

Also, consider the fact that since an 8-bit LRC or checksum can only have 256 different values, there’s a 1 in 256 chance that any message will give the exact same LRC (or checksum) another message chosen at random.

In general, it’s very easy to “fool” checksum and LRC algorithms, so they’re not really very reliable for message integrity-checking.

Fortunately, there are better algorithms than LRC or checksum for integrity-checking, but they come at a cost in terms of computational overhead.

How to Calculate Checksum w/CRC

When integrity-checking really matters, generally speaking you need to use a non-commutative hash of some kind. Often, this means a cryptographic hash, like SHA-1 or MD5, but these are computationally intensive and can be considered “overkill” in many situations.

A good tradeoff of computational overhead and reliability can be found in the Cyclic Redundancy Check, which comes in various versions, although the 16-bit CRC described below is adequate (and quite popular) for short messages (up to around 4 kilobytes).

CRC is an interesting subject, but space forbids any kind of comprehensive treatment of it here. (Consult Google.) Suffice it to say, from a practicality standpoint, a two-byte CRC provides very good sensitivity to random bitflips in the data and is unlikely to give false positives with data containing multiple bitflips. Because of this, and because it’s easy to implement in hardware or software, and runs very quickly in very little memory, you’ll find it used in a variety of data communication environments, including storage-disk drivers (where disk errors are often detected using CRC), modems, and small electronic devices (including all of ID TECH’s ViVOpay-series credit card readers).

The following JavaScript code shows how to calculate a 16-bit CRC value (returned as four nibbles of hex-ASCII).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 16-bit Cyclic Redundancy Check.
// The optional 2nd argument should 
// be set to true if you need little-endian
// output.
function CRC( hexstring, invert ) {

	var crcTable = [0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0];

	var s = hexstring.match(/../g);
	var crc = 0xFFFF;
	var j, i;
	for (i = 0; i < s.length; i++) {
		var c = 1 * ("0x" + s[i]);
		j = (c ^ (crc >> 8)) & 0xFF;
		crc = crcTable[j] ^ (crc << 8);
	}
	var answer = ((crc ^ 0) & 0xFFFF);
	var hex = numToHex(answer);
	if ( invert )
		return hex.slice(2) + hex.slice(0, 2);
	return hex;
}

CRC implements a hash algorithm that can be described in English as:

We use a small utility routine to convert the final number from an integer to a hex string:

1
2
3
4
5

	function numToHex(n) {
		var hex = (1 * n).toString(16).toUpperCase();
		if (hex.length % 2 == 0) return hex;
		return "0" + hex;
	}

If you load both of these functions (numToHex, and CRC) into your browser’s JS console, and execute CRC( "48656C6C6F20776F726C6421" ), you should get a CRC for our “Hello world!” input data of ‘BD22’.

As an exercise, you might want to try flipping a bit in the input, to see what happens to output. For example, if you use our “Hello world!” string as input, and change the data’s final byte from 21 to 20, the CRC changes to ‘AD03’, which bears no relationship to ‘BD22’. Changing the final two bytes to ‘6520’ gives a CRC of ‘9E32’. (Remember, this same change did not perturb LRC or checksum.)

Consider a string representing ten zero (null) bytes. The LRC value of such a string would be zero. The checksum would obviously be zero. But the CRC would be E139.

You should be able to convince yourself pretty easily that reversing the input would give an entirely different CRC than using the original-direction input. (Which was not true for LRC or checksum.) CRC is not commutative, because of the way the top 8 bits of the CRC are XORed with the input byte before shifting everything to the left (which is similar to how cipher block chaining works, except in this case the “cipher block” size is 8 bits).

Note that while CRC is a one-way hash, it’s not a cryptographic hash per se, because it’s actually quite easy to calculate a “correction value” that, if tacked onto the data, would make a given alteration of the data yield the desired final CRC. (This is not true for so-called cryptographic hashes, where it’s difficult to calculate a “correction factor” that will back-correct an altered data block to the desired hash.) The CRC is thus appropriate for detecting unintentional data corruption.

Conclusion

There’s no shortage of “integrity check” algorithms you can use to monitor data packets for corruption. In some cases, a simple checksum or LRC will do. But for situations involving non-trivial amounts of data and a strict requirement for data integrity, you almost have to look to a “linear congruential generator” type of hash. The CRC family of algorithms have been well-tuned and optimized to provide good integrity discrimination combined with ease of implementation, rapid execution, and low memory requirements, making CRC attractive for a wide variety of data-checking scenarios involving everything from hard drives to credit card readers.

Want to Learn More About Checksum? ID TECH Has You Covered!