BSD checksum

The BSD checksum algorithm is a commonly used, legacy checksum algorithm. It has been implemented in BSD and is also available through the 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.

int bsdChecksumFromFile(FILE *fp) /* The file handle for input data */
{
    int checksum = 0;             /* The checksum mod 2^16. */

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

Below is some 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.

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;
}

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 (big-endian) 

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
gollark: Yes, you can only make something optimize effectively for good if you can define what that is rigorously, and people haven't yet and wouldn't agree on it.
gollark: Ignore them, they are clearly the government.
gollark: It might be fun to come up with a unified, consistent and of course completely disconnected from reality theory/system for how all the random free energy and crystal things work together.
gollark: Do a class action thing claiming to represent everyone who was scammed with them?
gollark: *Could* you try and make money by launching masses of lawsuits against all 5G blocking healing quantum frequency crystal sellers?
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.