 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

BSD checksum

Article Id: WHEBN0021350732
Reproduction Date:

 Title: BSD checksum Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

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.

```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. */
}
```

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.

```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: 4-bit checksum using 4-bit sized segments (big-endian:Endianness)

```Input: 101110001110
```

Loop 1:

``` checksum: 0000        seg: 1011
```

a) Circular shift checksum:

``` 0000 -> 0000
```

``` 0000 + 1011 = 1011 -> 1011 & 1111 = 1011
```

Loop 2:

``` checksum: 1011        seg: 1000
```

a) Circular shift checksum:

``` 1011 -> 1101
```

``` 1101 + 1000 = 10101 -> 10101 & 1111 = 0101
```

Loop 3:

``` checksum: 0101        seg: 1110
```

a) Circular shift checksum:

``` 0101 -> 1010
```

``` 1010 + 1110 = 11000 -> 11000 & 1111 = 1000
```

Checksum: 1000

Sources

• official FreeBSD sum source code
• official GNU sum manual page