Tính CRC 8 bit với bộ tiền xử lý C?

Question

Tôi đang viết mã cho một vi điều khiển 8 bit nhỏ xíu chỉ với một vài byte RAM. Nó có một công việc đơn giản là truyền 7 từ 16 bit, sau đó là CRC của những từ đó. Các giá trị của các từ được chọn tại thời gian biên dịch. CRC cụ thể là "phần còn lại của phân chia từ 0 đến từ 6 là số không dấu chia cho đa thức x^8 + x² + x + 1 (giá trị ban đầu 0xFF)."

Có thể tính CRC của các byte đó tại thời gian biên dịch bằng cách sử dụng bộ xử lý trước C không?

#define CALC_CRC(a,b,c,d,e,f,g) /* what goes here? */ 

#define W0 0x6301 
#define W1 0x12AF 
#define W2 0x7753 
#define W3 0x0007 
#define W4 0x0007 
#define W5 0x5621 
#define W6 0x5422 
#define CRC CALC_CRC(W0, W1, W2, W3, W4, W5, W6) 

Answer 1

Thuật toán checksum đơn giản nhất là cái gọi là kiểm tra chẵn lẻ theo chiều dọc, mà phá vỡ các dữ liệu vào "chữ" với n số cố định của các bit, và sau đó tính độc quyền hoặc của tất cả những từ đó. Kết quả được thêm vào tin nhắn dưới dạng một từ bổ sung.

Để kiểm tra tính toàn vẹn của tin nhắn, người nhận tính toán độc quyền hoặc tất cả các từ của nó, bao gồm cả tổng kiểm tra; nếu kết quả không phải là một từ có số không, người nhận biết rằng lỗi truyền đã xảy ra.

(souce: wiki)

Trong ví dụ của bạn:

#define CALC_CRC(a,b,c,d,e,f) ((a)^(b)^(c)^(d)^(e)^(f)) 

Answer 2

Disclaimer: đây không phải là thực sự là một câu trả lời trực tiếp, mà là một loạt các câu hỏi và ý kiến ​​cho rằng là quá dài cho một nhận xét.

Câu hỏi đầu tiên: Bạn có quyền kiểm soát cả hai đầu của giao thức, ví dụ: bạn có thể chọn thuật toán kiểm tra bằng chính bản thân hoặc đồng nghiệp kiểm soát mã ở đầu bên kia không?

Nếu CÓ đặt câu hỏi # 1:

Bạn cần phải đánh giá tại sao bạn cần checksum, những gì checksum là thích hợp, và hậu quả điểm nhận thông điệp tham nhũng với một kiểm tra hợp lệ (các yếu tố vào cả hai những gì & lý do tại sao).

Phương tiện truyền, giao thức, bitrate của bạn là gì? Bạn đang mong đợi/quan sát các lỗi bit? Vì vậy, ví dụ, với SPI hoặc I2C từ một chip khác trên cùng một bảng, nếu bạn có lỗi bit, nó có thể là lỗi kỹ sư HW hoặc bạn cần phải làm chậm tốc độ đồng hồ, hoặc cả hai. Một kiểm tra không thể làm tổn thương, nhưng không thực sự cần thiết. Mặt khác, với tín hiệu hồng ngoại trong môi trường ồn ào, và bạn sẽ có xác suất lỗi cao hơn nhiều.

Hậu quả của thư xấu luôn là câu hỏi quan trọng nhất ở đây. Vì vậy, nếu bạn đang viết bộ điều khiển cho nhiệt kế phòng kỹ thuật số và gửi một tin nhắn để cập nhật màn hình hiển thị 10x một giây, một giá trị xấu bao giờ 1000 tin nhắn có rất ít nếu có hại thực sự. Không có tổng kiểm tra hoặc kiểm tra yếu nên được tốt.

Nếu 6 byte này bắn tên lửa, hãy đặt vị trí của dao mổ robot hoặc gây chuyển tiền, bạn nên chắc chắn rằng mình có quyền kiểm tra chính xác và thậm chí có thể muốn xem băm mật mã có thể cần nhiều RAM hơn bạn có).

Đối với nội dung ở giữa, với tổn hại đáng chú ý đến hiệu suất/sự hài lòng với sản phẩm, nhưng không gây hại thực sự, đó là cuộc gọi của bạn.Ví dụ, một TV thỉnh thoảng thay đổi âm lượng thay vì kênh có thể gây khó chịu cho khách hàng - nhiều hơn là chỉ đơn giản bỏ lệnh nếu CRC tốt phát hiện lỗi, nhưng nếu bạn đang kinh doanh kiếm tiền/các TV knock-off có thể được chấp nhận nếu nó đưa sản phẩm ra thị trường nhanh hơn.

Vậy bạn cần kiểm tra những gì?

Nếu một hoặc cả hai đầu có HW hỗ trợ cho tổng kiểm tra được tích hợp vào thiết bị ngoại vi (khá phổ biến trong SPI chẳng hạn), đó có thể là lựa chọn khôn ngoan. Sau đó, nó trở nên nhiều hơn hoặc ít hơn miễn phí để tính toán.

Một LRC, theo đề xuất của câu trả lời của vulkanino, là thuật toán đơn giản nhất.

Wikipedia có một số thông tin khá về cách/tại sao để lựa chọn một đa thức nếu bạn thực sự cần một CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Nếu KHÔNG cho câu hỏi # 1:

CRC gì thuật toán/đa thức hiện đầu kia yêu cầu? Đó là những gì bạn đang mắc kẹt, nhưng nói với chúng tôi có thể giúp bạn có được một câu trả lời tốt hơn/đầy đủ hơn.

Suy nghĩ về việc thực hiện:

Hầu hết các thuật toán là khá nhẹ về RAM/đăng ký, chỉ cần một vài byte thêm. Nói chung, một hàm sẽ dẫn đến mã tốt hơn, sạch hơn, dễ đọc hơn, thân thiện với trình gỡ lỗi.

Bạn nên nghĩ về giải pháp macro như một mẹo tối ưu hóa, và giống như tất cả các thủ thuật tối ưu hóa, nhảy tới đầu có thể lãng phí thời gian phát triển và nguyên nhân gây ra nhiều vấn đề hơn giá trị.

Sử dụng macro cũng có một số hàm ý lạ bạn có thể chưa cân nhắc:
Bạn biết rằng bộ tiền xử lý chỉ có thể thực hiện phép tính nếu tất cả các byte trong thư được cố định tại thời gian biên dịch, phải không? Nếu bạn có một biến trong đó, trình biên dịch phải tạo mã. Nếu không có một hàm, mã đó sẽ được inlined mỗi khi nó được sử dụng (có, điều đó có thể có nghĩa là rất nhiều việc sử dụng ROM). Nếu tất cả các byte là biến, mã đó có thể tồi tệ hơn là chỉ viết hàm trong C. Hoặc với trình biên dịch tốt, nó có thể tốt hơn. Khó khăn để nói chắc chắn. Mặt khác, nếu một số lượng byte khác nhau thay đổi tùy thuộc vào thư được gửi, bạn có thể kết thúc với một số phiên bản của mã, mỗi phiên bản được tối ưu hóa cho việc sử dụng cụ thể đó.

Answer 3

Có thể thiết kế macro để thực hiện phép tính CRC tại thời gian biên dịch. Một cái gì đó như

 
// Choosing names to be short and hopefully unique. 
#define cZX((n),b,v) (((n) & (1 << b)) ? v : 0) 
#define cZY((n),b, w,x,y,z) (cZX((n),b,w)^CzX((n),b+1,x)^CzX((n),b+2,y)^cZX((n),b+3,z)) 
#define CRC(n) (cZY((n),0,cZ0,cZ1,cZ2,cZ3)^cZY((n),4,cZ4,cZ5,cZ6,cZ7)) 

có lẽ nên hoạt động và sẽ rất hiệu quả nếu (n) có thể được đánh giá dưới dạng hằng số biên dịch; nó sẽ chỉ đơn giản là đánh giá một hằng số. Mặt khác, nếu n là một biểu thức, biểu thức đó sẽ kết thúc nhận được tám lần được tính toán lại. Ngay cả khi n là một biến đơn giản, mã kết quả sẽ có khả năng lớn hơn đáng kể so với cách viết không dựa trên bảng không nhanh nhất và có thể chậm hơn cách viết nhỏ gọn nhất. BT2, một điều tôi thực sự muốn thấy trong tiêu chuẩn C và C++ sẽ là phương tiện chỉ định các quá tải sẽ được sử dụng cho các hàm được khai báo nội dòng nếu các tham số cụ thể có thể được đánh giá dưới dạng hằng số biên dịch.Các ngữ nghĩa sẽ là như vậy mà sẽ không có 'bảo đảm' rằng bất kỳ quá tải nào như vậy sẽ được sử dụng trong mọi trường hợp trình biên dịch có thể xác định giá trị, nhưng sẽ có một đảm bảo rằng (1) không sử dụng quá tải như vậy trong mọi trường hợp, tham số "biên dịch-thời gian-const" phải được đánh giá trong thời gian chạy và (2) bất kỳ tham số nào được coi là hằng số trong một quá tải như vậy sẽ được coi là hằng số trong bất kỳ hàm nào được gọi từ nó. Có rất nhiều trường hợp mà một hàm có thể được viết để đánh giá một hằng số biên dịch-thời gian nếu tham số của nó là hằng số, nhưng khi việc đánh giá thời gian chạy sẽ là hoàn toàn khủng khiếp. Ví dụ:

 
#define bit_reverse_byte(n) ((((n) & 128)>>7)|(((n) & 64)>>5)|(((n) & 32)>>3)|(((n) & 16)>>1)| 
    (((n) & 8)<<1)|(((n) & 4)<<3)|(((n) & 2)<<5)|(((n) & 1)<<7)) 
#define bit_reverse_word(n) (bit_reverse_byte((n) >> 8) | (bit_reverse_byte(n) << 8)) 

Hiển thị đơn giản chức năng đảo ngược bit một byte không lặp trong C trên PIC sẽ là khoảng 17-19 hướng dẫn đơn chu kỳ; một từ bit đảo ngược sẽ là 34, hoặc khoảng 10 cộng với một hàm byte-ngược (mà sẽ thực hiện hai lần). Mã lắp ráp tối ưu sẽ có khoảng 15 hướng dẫn một chu kỳ cho byte ngược hoặc 17 cho đảo ngược từ. Máy tính bit_reverse_byte(b) đối với một số biến số byte b sẽ mất hàng chục lệnh tổng cộng hàng chục chu kỳ. Máy tính bit_reverse_word( w ) for some 16-bit word w` có lẽ sẽ mất hàng trăm hướng dẫn lấy hàng trăm hoặc hàng nghìn chu kỳ để thực thi. Nó sẽ thực sự tốt đẹp nếu người ta có thể đánh dấu một hàm được mở rộng nội tuyến bằng cách sử dụng một cái gì đó như công thức trên trong kịch bản mà nó sẽ mở rộng đến tổng cộng bốn lệnh (về cơ bản chỉ tải kết quả). mở rộng sẽ là ghê tởm.