Tổng kiểm tra CRC sử dụng dài (64 bit)

Question

Tôi đã kiểm tra các triển khai CRC64 khác nhau. Ví dụ: this, this và this. Vấn đề với tất cả những điều này là chúng hoạt động với các byte. Tuy nhiên, trên hệ thống 64 bit, tôi muốn làm việc với long (8 byte). Bằng cách này, tôi sẽ cần phải lặp lại ít hơn. Ví dụ, đối với dữ liệu 128 byte, sử dụng byte, tôi cần lặp lại 128 lần, trong khi với long, tôi sẽ chỉ cần lặp lại 16 lần.

Có triển khai CRC64 nào sử dụng long hoặc thậm chí kích thước từ lớn hơn byte không? Các kế hoạch này có thể được sửa đổi để làm như vậy không?

Answer 1

Tính toán CRC sử dụng mẹo để tránh phải xử lý dữ liệu từng bit một: Nó sử dụng bảng tra cứu cho phép xử lý nhiều bit cùng một lúc.

Xử lý n bit cùng một lúc yêu cầu bảng tra cứu có kích thước 2^n. Việc triển khai bạn liên kết đọc 1 byte (8 bit) tại một thời điểm, và thực sự tất cả họ đều sử dụng bảng tra cứu có kích thước 256 == 2^8.

Xử lý 64 bit cùng một lúc sẽ yêu cầu bảng tra cứu có kích thước 2^64, điều này không thực tế. Đây là lý do tại sao việc triển khai phổ biến CRC thực hiện xử lý 1 byte tại một thời điểm.

Mặc dù có thể xử lý 2 byte cùng một lúc bằng mảng nhập 65536, điều này có thể có tác động tiêu cực về hiệu suất do sử dụng bộ nhớ cache CPU nhiều hơn.