Introduction to Computer

Introduction to Computer, Fall 2013

Jump to...

assignment #1
assignment #2
assignment #3
final project
assignments

Assignment #4: CRC32 checksum

Cancelled!!

Assigned: TBD
Due: TBD

Description

CRC (cyclic redundancy check) is a type of hash function used to produce a checksum value from a large block of data. A checksum value is usually generated when we transfer data over the internet, or compressing data into an archive. So we can check the validity after the data is received or uncompressed. You can learn more information in the Wikipedia's CRC page.

In this project, you need to implement CRC32 algorithm used in Ethernet, FDDI, WinZip and PNG, by assembly. Here is a C implementation:

    unsigned int crc32(const char* data, size_t length){
        const unsigned int POLY = 0xEDB88320; // standard polynomial in CRC32
        unsigned int reminder = 0xFFFFFFFF; // standard initial value in CRC32
			    	
        for(size_t i = 0; i < length; i++){
   	    reminder ^= (unsigned char)data[i]; // must be zero extended
	    for(size_t bit = 0; bit < 8; bit++)
	        if(reminder & 0x01)
  		    reminder = (reminder >> 1) ^ POLY;
	        else
  		    reminder >>= 1;
        }
        return reminder ^ 0xFFFFFFFF;
    }

Although this function can produce the correct CRC32 checksum from a string, the naive method is very slow. You can find a faster method for it in the painless guide to CRC.

Specification

You have to implement a procedure called "crc32" by assembly. This function should accept a pointer pointing to the string data and the length of data. The calculated checksum should be stored in EAX when this function returns. A skeleton looks like:

    .386
    .model flat
    option casemap :none
    .data
        sum DWORD 0
    .code
    _crc32 PROC PUBLIC
        push ebp
        mov ebp, esp ; build stack frame
	
        ; begin CRC32 calculation
        ; WRITE YOUR OWN CODE HERE

        ; end CRC32 calculation
 
        mov eax, sum
        leave
        ret
    _crc32 ENDP
    END ; file ends here

To shift a number, you will need the instruction SHL or SHR. The first shifts a register or a memory location specified by the first operand to the left a number of bits specified in the second operand and fill the newly created bit position with 0. The second instruction shifts right. For example, assume that AX holds 11001111 initially. The instruction "SHL AX, 2" shifts the content of AX 2 bits to the left and AX becomes 00111100 after executing this instruction. Similarly, "SHR AX, 1" shifts AX one bit to the right and AX becomes 01100111 after this instruction. In addition, you can use [EBP+8] and [EBP+12] to access the parameters, data and length.

In hw4.zip, you can also find main.cpp where other functions are implemented. (The main program was written in C++. If it incurs warnings and errors when using MSVC 2005, please use this main.c instead.) They are used to open a file and do timings, and you don't need to modify them. When your work is done in crc32.asm, execute "nmake" and the executable file "crc32.exe" will be built. Then execute "crc32.exe FILE" and you can see the calculated CRC32 checksum and CPU cycles you've used.

You can refer to this document for writing MASM programs using Microsoft Visual C++ 2005 Express.

Grading

You will get 80 points if you implement this procedure correctly. Another 0~25 points will be added to your grade depending on the speed of your program.

Submission

Submit through online submission system.