Exercise

Enhance your understanding of checksums by getting hands-on practice ​with the exercise provided in this lesson!

We'll cover the following

Simulator

In this exercise, you’ll use checksum.py to investigate various aspects of checksums.

#! /usr/bin/env python

import random
from optparse import OptionParser

def print_hex(v):
    if v < 16:
        return '0x0%x' % v
    else:
        return '0x%x' % v
    
def print_bin(word):
    v = bin(word)
    o = '0b'
    o += ('0' * (10 - len(str(v))))
    o += str(v)[2:]
    return o
    

parser = OptionParser()
parser.add_option('-s', '--seed', default='0', help='Random seed',
                  action='store', type='int', dest='seed')
parser.add_option('-d', '--data_size', default='4',
                  help='Number of bytes in data word',
                  action='store', type='int', dest='data_size')
parser.add_option('-D', '--data', default='',
                  help='Data in comma separated form',
                  action='store', type='string', dest='data')
parser.add_option('-c', '--compute', help='compute answers for me',
                  action='store_true', default=False, dest='solve')
(options, args) = parser.parse_args()

print ''
print 'OPTIONS seed', options.seed
print 'OPTIONS data_size', options.data_size
print 'OPTIONS data', options.data
print ''

random.seed(options.seed)

values = []
if options.data != '':
    tmp = options.data.split(',')
    for t in tmp:
        values.append(int(t))
else:
    for t in range(int(options.data_size)):
        values.append(int(random.random() * 256))



add = 0
xor = 0
fletcher_a, fletcher_b = 0, 0

for value in values:
    add = (add + value) % 256
    xor = xor ^ value
    fletcher_a = (fletcher_a + value) % 255
    fletcher_b = (fletcher_b + fletcher_a) % 255

print 'Decimal:  ', 
for word in values:
    print '%10s' % str(word),
print ''

print 'Hex:      ', 
for word in values:
    print '     ', print_hex(word),
print ''

print 'Bin:      ', 
for word in values:
    print print_bin(word),
print ''

print ''
if options.solve:
    print 'Add:           ', '%3d      ' % add, '(%s)' % print_bin(add)
    print 'Xor:           ', '%3d      ' % xor, '(%s)' % print_bin(xor)
    print 'Fletcher(a,b): ', '%3d,%3d  ' % (fletcher_a, fletcher_b), '(%s,%s)' % (print_bin(fletcher_a), print_bin(fletcher_b))
else:
    print 'Add:      ?'
    print 'Xor:      ?'
    print 'Fletcher: ?'
print ''
Simulator

Questions

  1. First just run checksum.py with no arguments. Compute the additive, XOR-based, and Fletcher checksums. Use -c to check your answers.

  2. Now do the same, but vary the seed (-s) to different values.

  3. Sometimes the additive and XOR-based checksums produce the same checksum (e.g., if the data value is all zeroes). Can you pass in a 4-byte data value (using the -D flag, e.g., -D a,b,c,d) that does not contain only zeroes and leads the additive and XOR-based checksum having the same value? In general, when does this occur? Check that you are correct with the -c flag.

  4. Now pass in a 4-byte value that you know will produce different checksum values for additive and XOR. In general, when does this occur?

  5. Usethesimulatortocomputechecksumstwice(once each for a different set of numbers). The two number strings should be different (e.g., -D a1,b1,c1,d1 the first time and -D a2,b2,c2,d2 the second) but should produce the same additive checksum. In general, when will the additive checksum be the same, even though the data values are different? Check your specific answer with the -c flag.

  6. Now do the same for the XOR checksum.

  7. Now let’s look at a specific set of data values. The first is: -D 1,2,3,4. What will the different checksums (additive, XOR, Fletcher) be for this data? Now compare it to computing these checksums over -D 4,3,2,1. What do you notice about these three checksums? How does Fletcher compare to the other two? How is Fletcher generally “better” than something like the simple additive checksum?

  8. No checksum is perfect. Given a particular input of your choosing, can you find other data values that lead to the same Fletcher checksum? When, in general, does this occur? Start with a simple data string (e.g., -D 0,1,2,3) and see if you can replace one of those numbers but end up with the same Fletcher checksum. As always, use -c to check your answers.

Writing your own code

In this part of the exercise, you’ll write some of your own code to implement various checksums.

  1. Write a short C program (called check-xor.c) that computes an XOR-based checksum over an input file, and prints the checksum as output. Use an 8-bit unsigned char to store the (one byte) checksum. Make some test files to see if it works as expected.

  2. Now write a short C program (called check-fletcher.c) that computes the Fletcher checksum over an input file. Once again, test your program to see if it works.

  3. Now compare the performance of both: is one faster than the other? How does performance change as the size of the input file changes? Use internal calls to gettimeofday to time the programs. Which should you use if you care about performance? About checking ability?

  4. Read about the 16-bit CRC and then implement it. Test it on a number of different inputs to ensure that it works. How is its performance as compared to the simple XOR and Fletcher? How about its checking ability?

  5. Now build a tool (create-csum.c) that computes a single-byte checksum for every 4KB block of a file, and records the results in an output file (specified on the command line). Build a related tool (check-csum.c) that reads a file, computes the checksums over each block, and compares the results to the stored checksums stored in another file. If there is a problem, the program should print that the file has been corrupted. Test the program by manually corrupting the file.

Get hands-on with 1400+ tech skills courses.