Admin: Created page with "The '''BSD checksum algorithm''' is a commonly used, legacy checksum algorithm. It has been implemented in BSD and is also available thr..."

2019-04-09T05:27:39Z

Created page with "The '''BSD checksum algorithm''' is a commonly used, legacy checksum algorithm. It has been implemented in BSD and is also available thr..."

New page

The '''BSD checksum algorithm''' is a commonly used, legacy [[checksum]] algorithm. It has been implemented in [[Berkeley Software Distribution|BSD]] and is also available through the [[sum (Unix)|GNU sum]] command line utility.

==Computation of the BSD checksum==
Below is the relevant part of the [[GNU]] sum source code ([[GPL]] licensed). It computes a 16-bit checksum by adding up all bytes (8-bit words) of the input data stream. In order to avoid many of the weaknesses of simply adding the data, the checksum accumulator is circular rotated to the right by one bit at each step before the new char is added.
<syntaxhighlight lang="cpp">
int bsdChecksumFromFile(FILE *fp) /* The file handle for input data */
{
int ch; /* Each character read. */
int checksum = 0; /* The checksum mod 2^16. */

while ((ch = getc(fp)) != EOF) {
checksum = (checksum >> 1) + ((checksum & 1) << 15);
checksum += ch;
checksum &= 0xffff; /* Keep it within bounds. */
}
return checksum;
}
</syntaxhighlight>

Below is a sample java code that calculates an 8-bit checksum. It adds each byte from the input byte array after a circular rotation of the checksum.
<syntaxhighlight lang="java">
byte checksum(byte[] input) {
byte checksum = 0;
for (byte cur_byte: input) {
checksum = (byte) (((checksum & 0xFF) >>> 1) + ((checksum & 0x1) << 7)); // Rotate the accumulator
checksum = (byte) ((checksum + cur_byte) & 0xFF); // Add the next chunk
}
return checksum;
}
</syntaxhighlight>

==Description of the algorithm==
As mentioned above, this algorithm computes a checksum by segmenting the data and adding it to an accumulator that is circular right shifted between each summation. To keep the accumulator within return value bounds, bit-masking with 1's is done.

'''Example:''' Calculating a 4-bit checksum using 4-bit sized segments ([[Endianness|big-endian]])
<br />
Input: 101110001110 -> three segments: 1011, 1000, 1110.
'''''Iteration 1:'''''
segment: 1011 checksum: 0000 bitmask: 1111
a) Apply circular shift to the checksum:
0000 -> 0000
b) Add checksum and segment together, apply bitmask onto the obtained result:
0000 + 1011 = 1011 -> 1011 & 1111 = 1011
'''''Iteration 2:'''''
segment: 1000 checksum: 1011 bitmask: 1111
a) Apply circular shift to the checksum:
1011 -> 1101
b) Add checksum and segment together, apply bitmask onto the obtained result:
1101 + 1000 = 10101 -> 10101 & 1111 = 0101
'''''Iteration 3:'''''
segment: 1110 checksum: 0101 bitmask: 1111
a) Apply circular shift to the checksum:
0101 -> 1010
b) Add checksum and segment together, apply bitmask onto the obtained result:
1010 + 1110 = 11000 -> 11000 & 1111 = 1000
'''''Final checksum:''''' 1000

==Sources==
* [http://svnweb.freebsd.org/base/stable/9/usr.bin/cksum/sum1.c?revision=225736&view=markup official FreeBSD sum source code]
* [https://www.gnu.org/software/coreutils/manual/html_node/sum-invocation.html official GNU sum manual page]
* [https://www.gnu.org/software/coreutils/ coreutils download page] --- find and unpack the newest version of the coreutils package, read src/sum.c

==Source==

[http://wikipedia.org/ http://wikipedia.org/]
==See Also on BitcoinWiki==
* [[Proof-of-Research Genesis Block]]
* [[BIP 0109]]
* [[BIP 0142]]
* [[Shaping codes]]
* [[BIP 0140]]

BSD checksum - Revision history

Admin: Created page with "The '''BSD checksum algorithm''' is a commonly used, legacy checksum algorithm. It has been implemented in BSD and is also available thr..."