Kiến thức

CRC-32 Checksum – ntppro's notes

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.


Bạn đang xem: CRC-32 Checksum – ntppro’s notes

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 thuật toán được quy đị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 thuật toán mà thiết bị gửi đã sử dụng) cho toàn bộ dữ liệu nhận được (kể cả mã CRC được chèn cuối gói dữ liệu). Nếu mã CRC mà thiết bị nhận tính toán ra bằng ZERO thì dữ liệu được xác nhận là toàn vẹn, ngược lại thì dữ liệu đã bị mất mát, thay đổi trong quá trình truyền gửi.

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


Xem thêm: Các trường đào tạo kế toán ở TPHCM uy tín nhất 2021

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:

f = x^8 + x^2 + x + 1

  • CRC-16:

f = x^{16} + x^{15} + x^2 + 1

  • CRC-32

f = 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 (với N là bậc cao nhất của đa thức sinh) 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à chèn bit tiếp theo của Devidend vào vị trí bit 0 của Remainder rồi quay lại bước 2. Quá trình này kết thúc khi chúng ta sử dụng hết tất cả các bit của Devidend.

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 nghịch đảo: 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_t; #define CRC32POLY 0x104C11DB7 uint8_t reflect(uint8_t); crc32_t crc32_compute(char); int main(int argc, char **argv) { if (argc > 1) printf("Result: %Xn", crc32_compute(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_t crc32_compute(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_t; #define CRC32POLY_REVERSE 0xEDB88320 crc32_t crc32_compute(char); int main(int argc, char **argv) { if (argc > 1) printf("Result: %Xn", crc32_compute(argv[1][0])); return 0; } crc32_t crc32_compute(char msg) { crc32_t remainder = msg ^ 0xFFFFFFFF; for (int i = 0; i < 8; i++) { if (remainder & 1) remainder = (remainder >> 1) ^ CRC32POLY_REVERSE; 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_t; #define CRC32POLY_REVERSE 0xEDB88320 crc32_t crc32_compute(const char*); int main(int argc, char **argv) { if (argc > 1) printf("Result: %Xn", crc32_compute(argv[1])); return 0; } crc32_t crc32_compute(const char *msg) { crc32_t remainder = 0xFFFFFFFF; for (uint8_t i = 0; msg[i] != ''; i++) { remainder ^= msg[i]; for (uint8_t bit = 0; bit < 8; bit++) { if (remainder & 1) remainder = (remainder >> 1) ^ CRC32POLY_REVERSE; 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_t; #define CRC32POLY_REVERSE 0xEDB88320 crc32_t crc32_compute(const char*); void crc32_init(); crc32_t crc32Table[256]; int main(int argc, char **argv) { createCRC32Table(); if (argc > 1) printf("Result: %Xn", crc32_compute(argv[1])); return 0; } void crc32_init() { crc32_t remainder; for (int data = 0; data < 256; data++) { remainder = data; for (uint8_t bit = 0; bit < 8; bit++) { if (remainder & 1) remainder = (remainder >> 1) ^ CRC32POLY_REVERSE; else remainder >>= 1; } crc32Table[data] = remainder; } } crc32_t crc32_compute(const char *msg) { crc32_t remainder = 0xFFFFFFFF; for (uint8_t i = 0; msg[i] != ''; 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.


Xem thêm: Lực G-điều hấp dẫn bên trong một chiếc ôtô-VnExpress

KIỂM TRA TÍNH ĐÚNG ĐẮN CỦA MÃ CRC-32

Đoạn code dưới đây dùng để kiểm tra xem mã CRC-32 mà chúng ta đã tính toán cho đoạn dữ liệu “data” với kích thước “len” bytes là chính xác hay không.

Thuật toán: nghịch đảo 4 bytes CRC-32 đã tính toán được và chèn vào cuối đoạn dữ liệu. Thực hiện tính CRC-32 cho đoạn dữ liệu mới này (với cùng thuật toán đã sử dụng trước đó) và thực hiện phép nghịch đảo mã CRC-32 nhận đuợc. Kết quả nhận được là ZERO chứng minh rằng mã CRC-32 đã tính toán được là đúng đắn.

Example 5: kiểm tra tính đúng đắn của mã CRC-32

 int crc32_selfcheck(const void *data, uint32_t len, crc32_t crc) { uint8_t *msg = (uint8_t*)calloc(len + 4, 1); crc = ~crc; memcpy(msg, data, len); memcpy(msg+len, &crc, 4); crc32_t ret = ~crc32_compute(msg, len+4); free(msg); if (ret == 0) return 0; return -1; } 

Xem thêm: Eesti ja Soome-Ugri Keeleteaduse Ajakiri

KIỂM TRA TÍNH TOÀN VẸN CỦA DỮ LIỆU VỚI CRC-32

Nguyên lý cũng tương tự với

kiểm tra tính đúng đắn của mã CRC-32

, nhưng được thực hiện ở 2 thiết bị khác nhau.

  • Thiết bị gửi: cần nghịch đảo 4 bytes CRC-32 đã tính toán được và chèn vào cuối đoạn dữ liệu rồi gửi đi.
  • Thiết bị nhận: nhận được một đoạn dữ liệu bao gồm cả 4 bytes CRC-32 ở cuối. Thực hiện tính CRC-32 cho đoạn dữ liệu này (với cùng thuật toán mà thiết bị gửi đã sử dụng) và thực hiện phép nghịch đảo mã CRC-32 nhận đuợc. Kết quả nhận được là ZERO chứng minh rằng dữ liệu toàn vẹn.

Example 6: kiểm tra tính toàn vẹn của dữ liệu

 int crc32_check(const void *data, uint32_t len) { crc32_t ret = ~crc32_compute(msg, len); if (ret == 0) return 0; return -1; } 

KẾT THÚC

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. Source code có thể được clone tại

Github của mình

. 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++.

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button