Tính toán CRC32 Ethernet - phần mềm so với kết quả thuật toán

Question

Tôi đang cố gắng tính chuỗi khung kiểm tra (FCS) của byte gói Ethernet theo byte. Đa thức là 0x104C11DB7. Tôi đã làm theo thuật toán XOR-SHIFT được thấy ở đây http://en.wikipedia.org/wiki/Cyclic_redundancy_check hoặc tại đây http://www.woodmann.com/fravia/crctut1.htm

Giả sử thông tin được cho là có CRC chỉ là một byte. Giả sử nó là 0x03.

1. bước: pad với 32 bit bên phải

   0x0300000000

2. align đa thức và các dữ liệu ở phía bên tay trái với bit đầu tiên của họ mà không phải là zero và xor họ

   0x300000000 xor 0x209823B6E = 0x109823b6e

3. lấy lại phần còn lại và xor lần nữa

   0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

Vì không có chút rời CRC32 của 0x03 nên 0x0d4326d9

Đáng tiếc là tất cả việc triển khai phần mềm cho tôi biết tôi sai, nhưng tôi đã làm gì sai hay gì họ có đang làm khác không?

Python nói với tôi:

"0x%08x" % binascii.crc32(chr(0x03)) 
0x4b0bbe37 

Các công cụ trực tuyến ở đây http://www.lammertbies.nl/comm/info/crc-calculation.html#intr được kết quả tương tự. Sự khác biệt giữa tính toán tay của tôi và thuật toán mà phần mềm được đề cập sử dụng là gì?

UPDATE:

Hóa ra có một câu hỏi tương tự đã có trên stack overflow:

Bạn tìm thấy một câu trả lời ở đây Python CRC-32 woes

Mặc dù đây không phải là rất trực quan. Nếu bạn muốn có một mô tả chính thức thêm về cách nó được thực hiện cho Ethernet khung bạn có thể nhìn vào Ethernet Standard document 802.3 Phần 3 - Chương 3.2.9 Khung Kiểm tra trình tự Dòng

Cho phép tiếp tục ví dụ với phần trên:

1. Đảo ngược thứ tự bit của tin nhắn của bạn. Điều đó đại diện cho cách họ sẽ đi vào máy thu từng chút một.

   0x03 do đó là 0xC0

2. Bổ sung 32 bit đầu tiên của thông điệp của bạn. Lưu ý rằng chúng ta sẽ nén byte đơn với 32 bit một lần nữa.

   0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

3. Hoàn thành XOR và phương pháp thay đổi từ trên một lần nữa. Sau khoảng 6 bước bạn nhận được: sau đó

   0x13822f2d

4. Bit sequense trên được bổ sung.

   0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

5. Hãy nhớ rằng chúng ta đảo ngược thứ tự chút để có được đại diện trên dây Ethernet trong bước một. Bây giờ chúng ta phải đảo ngược bước này và cuối cùng chúng ta hoàn thành nhiệm vụ của mình.

   0x4b0bbe37

Ai đã đưa ra cách này để làm việc đó nên ...

Rất nhiều lần bạn thực sự muốn biết nó là thông điệp mà bạn nhận được là chính xác. Để đạt được điều này, bạn nhận được tin nhắn đã nhận của bạn bao gồm FCS và thực hiện các bước tương tự từ 1 đến 5 như trên. Kết quả phải là những gì họ gọi là dư lượng. Đó là một hằng số cho một đa thức nhất định. Trong trường hợp này, nó là 0xC704DD7B.

Là mcdowella đề cập đến bạn phải chơi xung quanh với các bit của bạn cho đến khi bạn làm đúng, tùy thuộc vào Ứng dụng bạn đang sử dụng.

Answer 1

Có một chút thử nghiệm và lỗi cần thiết để tính toán CRC phù hợp, vì bạn không bao giờ đọc chính xác những gì phải làm. Đôi khi bạn phải đảo ngược bit đầu vào hoặc đa thức, đôi khi bạn phải bắt đầu với giá trị khác 0, v.v.

Một cách để bỏ qua điều này là xem xét mã nguồn của một chương trình nhận được đúng, chẳng hạn như http://sourceforge.net/projects/crcmod/files/ (ít nhất nó yêu cầu khớp, và đi kèm với một bài kiểm tra đơn vị cho điều này).

Một cách khác là phát xung quanh với triển khai. Ví dụ, nếu tôi sử dụng máy tính tại http://www.lammertbies.nl/comm/info/crc-calculation.html#intr Tôi có thể thấy rằng cho nó 00000000 tạo ra một CRC 0x2144DF1C, nhưng cho nó FFFFFFFF tạo FFFFFFFF - vì vậy nó không chính xác bộ phận đa thức mà bạn mô tả, mà 0 sẽ có tổng kiểm tra 0

Nhìn lướt qua mã nguồn và những kết quả này tôi nghĩ bạn cần bắt đầu với CRC của 0xFFFFFFFF - nhưng tôi có thể sai và bạn có thể kết thúc gỡ lỗi mã bên cạnh việc triển khai, sử dụng printfs tương ứng để tìm hiểu nơi khác nhau đầu tiên, và sửa chữa sự khác biệt từng cái một.

Answer 2

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

có tất cả các dữ liệu cho ethernet và sự giàu có của chi tiết quan trọng, ví dụ có (ít nhất) 2 công ước để mã hóa đa thức thành một giá trị 32-bit, hạn lớn nhất đầu tiên hoặc hạn nhỏ nhất đầu tiên.

Answer 3

Có một số địa điểm trên Internet nơi bạn sẽ đọc rằng thứ tự bit phải được đảo ngược trước khi tính toán FCS, nhưng thông số 802.3 không phải là một trong số chúng.Trích dẫn từ phiên bản năm 2008 của spec:

3.2.9 Frame Check Sequence (FCS) field 

A cyclic redundancy check (CRC) is used by the transmit and receive algorithms to 
generate a CRC value for the FCS field. The FCS field contains a 4-octet (32-bit) 
CRC value. This value is computed as a function of the contents of the protected 
fields of the MAC frame: the Destination Address, Source Address, Length/ Type 
field, MAC Client Data, and Pad (that is, all fields except FCS). The encoding is 
defined by the following generating polynomial. 

    G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 
      + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 

Mathematically, the CRC value corresponding to a given MAC frame is defined by 
the following procedure: 

a) The first 32 bits of the frame are complemented. 
b) The n bits of the protected fields are then considered to be the coefficients 
    of a polynomial M(x) of degree n – 1. (The first bit of the Destination Address 
    field corresponds to the x(n–1) term and the last bit of the MAC Client Data 
    field (or Pad field if present) corresponds to the x0 term.) 
c) M(x) is multiplied by x32 and divided by G(x), producing a remainder R(x) of 
    degree ≤ 31. 
d) The coefficients of R(x) are considered to be a 32-bit sequence. 
e) The bit sequence is complemented and the result is the CRC. 

The 32 bits of the CRC value are placed in the FCS field so that the x31 term is 
the left-most bit of the first octet, and the x0 term is the right most bit of the 
last octet. (The bits of the CRC are thus transmitted in the order x31, x30,..., 
x1, x0.) See Hammond, et al. [B37]. 

Chắc chắn phần còn lại của các bit trong khung là truyền theo thứ tự ngược, nhưng điều đó không bao gồm các FCS. Một lần nữa, từ spec:

3.3 Order of bit transmission 

Each octet of the MAC frame, with the exception of the FCS, is transmitted least 
significant bit first. 

Answer 4

đoạn Python này viết CRC chính xác cho Ethernet:

# write payload 
for byte in data: 
    f.write('%02X\n' % ord(byte)) 
# write FCS 
crc = zlib.crc32(data)&0xFFFFFFFF 
for i in range(4): 
    b = (crc >> (8*i)) & 0xFF 
    f.write('%02X\n' % b) 

Sẽ có lưu tôi một thời gian nếu tôi tìm thấy ở đây.