Embedded System

CRC-32 Checksum

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu cách tính toán CRC-32 (Cyclic Redundancy Check) với ngôn ngữ C.


HIỂU VỀ CYCLIC REDUNDANCY CHECK

Cyclic Redundancy Check, viết tắt là CRC, là một phương pháp dùng để kiểm tra lỗi (tính toàn vẹn) của dữ liệu được gửi đi trên một kênh giao tiếp nào đó. Thiết bị gửi sẽ tính toán mã CRC (với một đa thức được xác định trước) cho toàn bộ dữ liệu cần gửi và chèn mã CRC này vào cuối gói dữ liệu. Sau khi nhận được dữ liệu, thiết bị nhận sẽ tính toán mã CRC (với cùng đa thức mà thiết bị gửi sử dụng) cho toàn bộ dữ liệu nhận được (ngoại trừ mã CRC được chèn cuối gói dữ liệu). Nếu mã CRC của thiết bị gửi và thiết bị nhận trùng nhau thì dữ liệu được xác nhận là toàn vẹn, ngược lại thì thiết bị gửi sẽ cần gửi lại gói dữ liệu một lần nữa.

Các mã CRC thường được sử dụng là CRC-8 (8-bit), CRC-16 (16-bit) và CRC-32 (32-bit).


MỘT SỐ ĐỊNH NGHĨA

Đầu tiên chúng ta cần biết về Đa thức sinh (Generator Polynomial). Đa thức sinh là một đa thức có bậc n đóng vai trò số chia (Divider) trong phép chia nhị phân modulo-2 (Modulo-2 Binary Division) khi cần tính CRC-n bit.

Một số đa thức sinh phổ biến:

CRC-8: x^8 + x^2 + x + 1;

CRC-16: x^16 + x^15 + x^2 + 1;

CRC-32: x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1.

Tiếp theo chúng ta cần tìm hiểu về Modulo-2 Binary Division. Trong phép toán này, dữ liệu cần tính CRC sau khi được chèn thêm n bits 0 vào bên phải (n = số bit của mã CRC) sẽ đóng vai trò số bị chia (Dividend), đa thức sinh sẽ là số chia (Divisor), xem Figure 1.

Capture

Figure 1 – Modulo-2 Binary Division

Ở Figure 1, khi cần tính CRC-3, chúng ta có đa thức sinh bậc 3 là x^3 + x + 1, tương ứng với 1011. Dữ liệu ban đầu là 1001 sẽ được chèn thêm 3 bits 0 vào bên phải và trở thành 1001000. Sau đó chúng ta thực hiện phép chia nhị phân giữa số bị chia (Dividend) 1001000 và số chia (Divisor) 1011 với các bước như sau:

  • Bước 1: Gán n+1 bits cao nhất của Dividend cho Remainder.
  • Bước 2:
    1. Nếu bit cao nhất của Remainder là 1 thì có nghĩa là nó có thể chia cho Divisor, vì vậy ta set bit tương ứng của Quotient (thương) là 1, đồng thời thực hiện  phép XOR (phép trừ không nhớ) giữa Remainder và Divisor rồi gán lại cho Remainder.
    2. Nếu bit cao nhất của Remainder là 0 thì có nghĩa là nó không thể chia cho Divisor, do đó ta set bit tương ứng của Quotient là 0 và giữ nguyên Remainder.
  • Bước 3: Dịch Remainder sang trái 1 bit (vì bit cao nhất của Remainder sau khi thực hiện bước 2 luôn luôn là 0 nên chúng ta sẽ không bị mất thông tin khi thực hiện phép dịch trái) và quay lại bước 2. Quá trình này kết thúc khi chúng ta dịch trái n lần tương ứng với số bậc của đa thức sinh.

Theo kết quả nhận được, ta có Remainder = 110, Quotient = 1010.


GIẢI THUẬT TÍNH CRC-32

Để tính toán mã CRC-32 cho một byte data, chúng ta cần thực hiện các bước sau:

  1. Đảo ngược vị trí các bit trong data byte, ví dụ: từ b10100011 đảo thành b11000101;
  2. Chèn thêm 32 bits 0 vào bên phải của data byte;
  3. Thực hiện phép gán Remainder = data XOR 0xFFFFFFFF00;
  4. Thực hiện phép chia nhị phân giữa data và đa thức sinh, đối với CRC-32, đa thức sinh là 0x104C11DB7;
  5. Nhận được Remainder và thực hiện phép gán Remainder = Remainder XOR 0xFFFFFFFF;
  6. Đảo ngược vị trí các bit của Remainder và nhận được mã CRC-32 của data.

crc

Table 1 – một số mã CRC phổ biến

Bây giờ chúng ta sẽ thực hiện tính toán CRC-32 cho một byte.

Example 1: Tính CRC-32 cho một byte
File: simpleCRC32.c

#include "stdio.h"
#include "stdint.h"
#include "math.h"

typedef uint32_t CRC32;

#define crc32poly	0x104C11DB7

uint8_t reflect(uint8_t);
CRC32 calcCRC32(char);

int main(int argc, char **argv) {
	if (argc > 1)
		printf("Result: %X\n", calcCRC32(argv[1][0]));		
	return 0;
}

uint8_t reflect(uint8_t number) {
	uint8_t result = 0;
	for (uint8_t i = 0; i < 8; i++) {
		result = (result << 1) + ((number >> i) & 1);
	}
	return result;
}

CRC32 calcCRC32(char msg) {
    uint64_t remainder = ((uint64_t)reflect(msg) << 32) ^ ((uint64_t)0xFFFFFFFF << 8);
    
    for (int i = 0; i < 8; i++) {
        if (remainder & 0x8000000000)
            remainder ^= crc32poly << 7;
        remainder <<= 1;
    }
    remainder >>= 8;
       
    remainder ^= 0xFFFFFFFF;

    remainder = (reflect(remainder & 0xFF) << 24) | (reflect((remainder >> 8) & 0xFF) << 16) | (reflect((remainder >> 16) & 0xFF) << 8) | (reflect((remainder >> 24) & 0xFF));
    return remainder;
}

Giải thích:
– Dòng 7: định nghĩa đa thức sinh của CRC-32;
– function reflect() dùng để đảo ngược vị trí các bit của input byte;
– function calcCRC32() nhận một byte msg làm tham số và tính toán mã CRC-32 cho byte đó. Đầu tiên msg sẽ được reflect, dịch trái 32 bits rồi XOR với 0xFFFFFFFF00 và gán cho biến remainder. Lúc này 8 bit cao nhất của remainder chính là các bit của msg, chúng ta lần lượt kiểm tra các bit này và XOR remainder với đa thức sinh. Kết quả remainder nhận được sau cùng sẽ được XOR với 0xFFFFFFFF và đảo ngược một lần nữa, đây chính là mã CRC-32 của msg.

Compile & Execution:
$ gcc simpleCRC32.c -o simpleCRC32
$ ./simpleCRC32 a
E8B7BE43
$ ./simpleCRC32 b
71BEEFF9

Chúng ta có thể kiểm tra kết quả bằng công cụ tính CRC online.

Nâng cấp 1:

  • Nếu chú ý, ta sẽ nhận ra rằng đa thức sinh của CRC-32 có chiều bài 33 bit, trong đó bit cao nhất (MSB = bit 32) luôn luôn là 1, ngoài ra kết quả của phép XOR giữa remainder và đa thức sinh luôn có bit cao nhất là 0 và sẽ bị loại bỏ sau đó. Như vậy việc giữ lại bit 32 của đa thức sinh cũng không có nhiều ý nghĩa;
  • Việc đảo ngược bit của dữ liệu cũng không hiệu quả, vì chúng ta buộc phải đảo ngược 2 lần trước khi nhận được mã CRC. Thay vào đó, việc đảo ngược bit của đa thức sinh sẽ hiệu quả hơn.

Example 2: nâng cấp cho simpleCRC32.c

#include "stdio.h"
#include "stdint.h"
#include "math.h"

typedef uint32_t CRC32;

#define crc32polyreverse	0xEDB88320

CRC32 calcCRC32(char);

int main(int argc, char **argv) {
	if (argc > 1)
		printf("Result: %X\n", calcCRC32(argv[1][0]));
	return 0;
}

CRC32 calcCRC32(char msg) {
    CRC32 remainder = msg ^ 0xFFFFFFFF;
    
    for (int i = 0; i < 8; i++) {
        if (remainder & 1)
            remainder = (remainder >> 1) ^ crc32polyreverse;
        else
            remainder >>= 1;
    }
    remainder ^= 0xFFFFFFFF;
    return remainder;
}

Compile & Execution:
$ gcc simpleCRC32.c -o simpleCRC32
$ ./simpleCRC32 a
E8B7BE43
$ ./simpleCRC32 b
71BEEFF9

Nâng cấp 2: trong thực tế, dữ liệu cần truyền tải có thể lên đến hàng nghìn byte một lúc, do đó nhiệm vụ của chúng ta là tính toán mã CRC cho toàn bộ gói dữ liệu thay vì từng byte riêng lẻ.

Example 3: tính mã CRC-32 cho một chuỗi
File: CRC32.c

#include "stdio.h"
#include "stdint.h"
#include "math.h"

typedef uint32_t CRC32;

#define crc32polyreverse	0xEDB88320

CRC32 calcCRC32(const char*);

int main(int argc, char **argv) {
	if (argc > 1)
		printf("Result: %X\n", calcCRC32(argv[1]));
	return 0;
}

CRC32 calcCRC32(const char *msg) {
    CRC32 remainder = 0xFFFFFFFF;
    for (uint8_t i = 0; msg[i] != '\0'; i++) {
        remainder ^= msg[i];
    
        for (uint8_t bit = 0; bit < 8; bit++) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ crc32polyreverse;
            else
                remainder >>= 1;
        }
    }
    remainder ^= 0xFFFFFFFF;
    return remainder;
}

Compile & Execution:
$ gcc CRC32.c -o simpleCRC32
$ ./CRC32 codelungtung.com
6D94F8DF

Nâng cấp 3: chúng ta đều biết rằng mỗi byte trong gói dữ liệu có giá trị trong khoảng [0, 255], sẽ lợi hơn rất nhiều nếu tính toán trước 256 giá trị này và lưu trữ lại để dùng thay vì phải tính lại từ đầu như ở các example trước.

Example 4: tính mã CRC-32 sử dụng bảng hash

#include "stdio.h"
#include "stdint.h"
#include "math.h"

typedef uint32_t CRC32;

#define crc32polyreverse	0xEDB88320

CRC32 calcCRC32(const char*);
void createCRC32Table();

CRC32 crc32Table[256];

int main(int argc, char **argv) {
    createCRC32Table();

    if (argc > 1)
        printf("Result: %X\n", calcCRC32(argv[1]));
    return 0;
}

void createCRC32Table() {
    CRC32 remainder;
    for (int data = 0; data < 256; data++) {
        remainder = data;
        for (uint8_t bit = 0; bit < 8; bit++) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ crc32polyreverse;
            else
                remainder >>= 1;
        }
        crc32Table[data] = remainder;
    }
}

CRC32 calcCRC32(const char *msg) {
    CRC32 remainder = 0xFFFFFFFF;

    for (uint8_t i = 0; msg[i] != '\0'; i++) {
        remainder = crc32Table[(remainder & 0xFF) ^ msg[i]] ^ (remainder >> 8);
    }
    remainder ^= 0xFFFFFFFF;
    return remainder;
}

Compile & Execution:
$ gcc CRC32.c -o simpleCRC32
$ ./CRC32 codelungtung.com
6D94F8DF

Giải thích:
– function createCRC32Table() sẽ tính toán giá trị hash của 256 giá trị rồi lưu vào mảng crc32Table[256] để sử dụng sau này.


SUMMARY

Như vậy chúng ta đã tìm hiểu về cách tính toán mã CRC-32 cho gói dữ liệu. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Reference:
[1] How to calculate CRC32 by hand?
[2] CRC Implementation Code in C/C++.
[3] Calculate a 32-bit CRC lookup table in C/C++.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s