World Library  
Flag as Inappropriate
Email this Article

BSD checksum

Article Id: WHEBN0021350732
Reproduction Date:

Title: BSD checksum  
Author: World Heritage Encyclopedia
Language: English
Subject: SYSV checksum, List of hash functions, Checksum
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

b) Add seg and bitmask:

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

Loop 2:

 checksum: 1011        seg: 1000

a) Circular shift checksum:

 1011 -> 1101

b) Add seg and bitmask:

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

Loop 3:

 checksum: 0101        seg: 1110

a) Circular shift checksum:

 0101 -> 1010

b) Add seg and bitmask:

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

Checksum: 1000

Sources

  • official FreeBSD sum source code
  • official GNU sum manual page
  • coreutils download page --- find and unpack the newest version of the coreutils package, read src/sum.c
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.