Project 1.2: CRC32 in RISC-V (Individual Project)

Computer Architecture I ShanghaiTech University

IMPORTANT INFO - PLEASE READ

This project is part of your design project (2 credits). Please note that the project and homework deadlines may be close to each other. Start early and do not procrastinate.

Introduction

In this project, you will implement the CRC32 checksum algorithm using the RISC-V instruction set. This task will help you understand data integrity verification and improve your assembly programming skills.

Please accept the assignment via this link. A starter code repository will be generated for you. Clone it to your Ubuntu system to begin. After completion, push your code to GitHub and submit on Gradescope.

Academic integrity is strictly enforced. Any plagiarism will result in serious consequences.

CRC32 Background

CRC32 (Cyclic Redundancy Check, 32-bit) is a widely used algorithm for data integrity verification in network communication and storage systems. It can effectively detect accidental errors in data transmission or storage.

The CRC32 algorithm generates a 32-bit checksum for messages of arbitrary length. The basic steps are as follows:

Step 0 Generating the look-up table:

We need to generate a lookup table for each 8-bit number from 00000000 to 11111111. Each item in the lookup table can be generated by using the reference C code below. Assume the polynomial (0xEDB88320) is used.

for (int i = 0; i < 256; i++) {
    uint32_t item = i;
    for (int j = 0; j < 8; j++) {
        if (item & 1) {
            item = (item >> 1) ^ 0xEDB88320;  // the least significant bit is 1
        } else {
            item >>= 1;                      // the least significant bit is 0
        }
    }
    crc_table[i] = item;
}

Taking the byte value 0x01 as an example:item = 0x01 (binary: 00000001) Use the polynomial (0xEDB88320).

• 1st iteration: The least significant bit (LSB) is 1 → item = (0x01 >> 1) ^ 0xEDB88320 = 0x00 ^ 0xEDB88320 = 0xEDB88320

• 2nd iteration: item = 0xEDB88320 (binary: 11101101 10111000 10000011 00100000) The LSB is 0 → item = 0xEDB88320 >> 1 = 0x76DC4190 (only right shift needed) Continue processing the remaining 6 bits...

Final result: crc_table[1] = 0x77073096

Step 1 Preprocessing:

Initialize a 32-bit CRC register to the initial value (e.g., 0xFFFFFFFF).

Step 2 Bit-by-bit / Byte-by-byte Processing:

Assume there is a long bit stream, and the CRC checksum is to be calculated. It is processed byte by byte using the reference code below.

for (size_t i = 0; i < length; i++) {
  uint8_t current_byte = bytes[i];              // Fetch one byte of data
  uint8_t index = (crc_register & 0xFF) ^ current_byte;  // XOR with the low 8 bits of CRC register
  uint32_t crc_shifted = crc_register >> 8;              // Right shift CRC by 8 bits
  uint32_t table_value = crc_table[index];      // Look up new value from table
  crc_register = crc_shifted ^ table_value;              // XOR with the right-shifted CRC
}

Detailed Algorithm Explanation

Assume current_byte=0x36 and the CRC register value is 0xFFFFFFFF:

XOR with the low 8 bits of CRC:

• Current CRC register: 0xFFFFFFFF
• Low 8 bits of CRC: 0xFF (binary: 11111111)
• Calculation of index: 0x36 ^ 0xFF = 0xC9
• Temporary variable index = 0xC9

Right shift CRC register by 8 bits:

• 0xFFFFFFFF right shifted by 8 bits → 0x00FFFFFF

Look up new value from table:

• Temporary variable index = 0xC9 (decimal 201)
• Look up the value at index 201 from the precomputed look-up table
• table[201] = E2B87A14 fro example.

XOR with the right-shifted CRC:

• Right-shifted CRC: 0x00FFFFFF
• Table lookup value: E2B87A14
• Calculation: 0x00FFFFFF ^ 0xE2B87A14 = 0xE24785EB

Update CRC register:

• New CRC register = 0xE24785EB

Step 3 Repeat:

Repeat step 2 for every byte of the bit stream.

Step 4 Post-processing:

1. After processing all data, XOR the final CRC register value 0xE24785EB with a final XOR value (e.g., 0xFFFFFFFF).
2. The final resulting 32-bit value is the CRC32 checksum, 1DB87A14.

Implementation

Parameter

CRC-32 Standard Generator Polynomial (supplementary materials):

The standard generator polynomial of CRC-32 can be expressed mathematically as: G(x) = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1.

Arranging the polynomial coefficients in order from x³² to x⁰ yields 1 0000 0100 1100 0001 0001 1101 1011 0111. The coefficient 1 of the highest-order term x³² is usually implicit, giving the 32-bit representation 0x04C11DB7.

Reversing the coefficient order of the standard polynomial produces 1 1101 1011 1000 1000 0011 0010 0000, with the 32-bit representation 0xEDB88320.

Input

A reference input is provided in input.S. The test cases have the same format, only the message length and content differ.

.data
# Length of input message (in bytes)
.globl length_of_input_message
length_of_input_message:
    .word 6

# Input message content (ASCII string)
.globl message
message:
    .asciiz "CS110P"

Output

You need to output the CRC32 checksum as an 8-digit hexadecimal string. For example:

12345678
Exited with error code 0

Execution

Make sure venus-jvm-latest.jar, crc32.S, main.S, and input.S are in the same directory. Run and output to crc32.out with:

java -jar venus-jvm-latest.jar -cc main.S > crc32.out

You need java to run the venus in terminal. Try to run sudo apt install openjdk-17-jre to download java-17.

Test

You can use the instruction as follow to check the output.

diff crc32.out crc32.ref

Tips

• Ensure you follow the RISC-V calling convention to avoid errors.
• Don't modify any other function or file!
• You may use any RISC-V instructions supported by Venus.
• Pay attention to memory access and register saving/restoring.
• Maybe you need to pay attention to the little-endian or big-endian.
• Write comments for clarity and debugging.
• Use ecall 11 to print characters, and ecall 17 to exit the program with return code 0. But You don't need to consider this, because the print function is already done.

Submission

Submit your code via GitHub and complete submission on Gradescope.

In Project 1.2 are: Siting Liu liust@shanghaitech.edu.cn Yuan Xiao xiaoyuan@shanghaitech.edu.cn Maoxi Ma mamx2023@shanghaitech.edu.cn Luntian Zhang zhanglt2023@shanghaitech.edu.cn