어쩌면 나는 그것을 보지 못하고 있지만 CRC32는 불필요하게 복잡해 보이거나 웹에서 찾을 수있는 곳에서 충분히 설명하지 못하는 것 같습니다.
나는 그것이 (생성자) 다항식으로 나눈 메시지 값의 비 캐리 기반 산술 분할의 나머지라는 것을 이해하지만 실제 구현은 나를 피합니다.
A Painless Guide To CRC Error Detection Algorithms를 읽었 으며 고통스럽지 않았다고 말해야합니다. 그것은 이론을 다소 잘 다루지 만 저자는 결코 단순한 “이것이다”에 도달하지 않습니다. 그는 표준 CRC32 알고리즘에 대한 매개 변수가 무엇인지 말하지만 어떻게 도달하는지 명확하게 배치하는 것을 무시합니다.
저를 얻는 부분은 그가 “이것입니다”라고 말하고 “그런데, 다른 초기 조건으로 되돌 리거나 시작할 수 있습니다.”라고 덧붙이며 최종 방법에 대한 명확한 대답을 제공하지 않습니다. 방금 추가 한 모든 변경 사항을 고려하여 CRC32 체크섬을 계산합니다.
- CRC32 계산 방법에 대한 더 간단한 설명이 있습니까?
나는 테이블이 어떻게 형성되는지 C로 코딩하려고 시도했다.
for (i = 0; i < 256; i++)
{
temp = i;
for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}
그러나 이것은 인터넷의 다른 곳에서 찾은 가치와 일치하지 않는 가치를 생성하는 것 같습니다. 내가 할 수 내가 온라인으로 발견 된 값을 사용하지만, 나는 그들이 만든 방법을 이해하고 싶다.
이 엄청나게 혼란스러운 숫자를 정리하는 데 도움을 주시면 대단히 감사하겠습니다.
답변
CRC32의 다항식은 다음과 같습니다.
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
또는 16 진수 및 2 진수 :
0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111
최고 용어 (x 32 )는 일반적으로 명시 적으로 작성되지 않으므로 대신 16 진수로 표현할 수 있습니다.
0x 04 C1 1D B7
1과 0을 자유롭게 셀 수 있지만 다항식과 일치하는 것을 알 수 있습니다. 여기서는 1비트 0 (또는 첫 번째 비트)이고 x비트 1 (또는 두 번째 비트)입니다.
왜이 다항식입니까? 주어진 다항식 표준이 필요하고 표준은 IEEE 802.3에 의해 설정 되었기 때문입니다. 또한 서로 다른 비트 오류를 효과적으로 감지하는 다항식을 찾는 것은 매우 어렵습니다.
CRC-32는 일련의 “캐리가없는 이진 산술”또는 기본적으로 “XOR 및 시프트 연산”으로 생각할 수 있습니다. 이를 기술적으로 다항식 산술이라고합니다.
더 잘 이해하려면 다음 곱셈을 생각하십시오.
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
x가 2 진법이라고 가정하면 다음을 얻습니다.
x^7 + x^3 + x^2 + x^1 + x^0왜? 3x ^ 3은 11x ^ 11이기 때문에 (하지만 1 또는 0의 사전 숫자 만 필요함) 다음과 같이 이어집니다.
=1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111 + 1x^11 + 1x^10 + 1x^1 + x^0
그러나 수학자들은 규칙을 변경하여 mod 2가되도록했습니다. 따라서 기본적으로 모든 이진 다항식 mod 2는 캐리 나 XOR없이 덧셈에 불과합니다. 따라서 원래 방정식은 다음과 같습니다.
=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)
나는 이것이 믿음의 도약이라는 것을 알고 있지만 이것은 라인 프로그래머로서의 능력을 넘어서는 것입니다. 당신이 하드 코어 CS 학생 또는 엔지니어라면 나는 이것을 분해하기 위해 도전합니다. 모든 사람이이 분석을 통해 이익을 얻을 수 있습니다.
따라서 전체 예제를 해결하려면 :
Original message : 1101011011
Polynomial of (W)idth 4 : 10011
Message after appending W zeros : 11010110110000
이제 CRC 산술을 사용하여 증강 메시지를 Poly로 나눕니다. 이것은 이전과 동일한 부문입니다.
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!
나눗셈은 우리가 버리는 몫과 계산 된 체크섬 인 나머지를 산출합니다. 이것으로 계산이 끝납니다. 일반적으로 체크섬이 메시지에 추가되고 결과가 전송됩니다. 이 경우 전송은 11010110111110입니다.
32 비트 숫자 만 제수로 사용하고 전체 스트림을 배당금으로 사용하십시오. 몫을 버리고 나머지를 유지하십시오. 메시지 끝에 나머지 부분을 붙이면 CRC32가 있습니다.
평균 남자 리뷰 :
QUOTIENT
----------
DIVISOR ) DIVIDEND
= REMAINDER
- 처음 32 비트를 가져옵니다.
- 시프트 비트
- 32 비트가 DIVISOR보다 작 으면 2 단계로 이동합니다.
- DIVISOR에 의한 XOR 32 비트. 2 단계로 이동합니다.
(스트림은 32 비트로 나눌 수 있어야합니다. 그렇지 않으면 패딩되어야합니다. 예를 들어, 8 비트 ANSI 스트림은 패딩되어야합니다. 또한 스트림의 끝에서 나누기가 중지됩니다.)
답변
IEEE802.3, CRC-32의 경우. 전체 메시지를 직렬 비트 스트림으로 생각하고 메시지 끝에 32 개의 0을 추가합니다. 다음으로, 메시지의 모든 바이트의 비트를 반전하고 처음 32 비트를 1로 보완해야합니다. 이제 CRC-32 다항식 0x104C11DB7로 나눕니다. 마지막으로,이 분할의 32 비트 나머지를 1로 보완해야합니다. 나머지 4 바이트를 각각 역으로 바꿉니다. 이것은 메시지 끝에 추가되는 32 비트 CRC가됩니다.
이 이상한 절차의 이유는 첫 번째 이더넷 구현이 메시지를 한 번에 한 바이트 씩 직렬화하고 모든 바이트의 최하위 비트를 먼저 전송하기 때문입니다. 그런 다음 직렬 비트 스트림은 직렬 CRC-32 시프트 레지스터 계산을 거쳤으며, 이는 메시지가 완료된 후 간단히 보완되어 유선으로 전송되었습니다. 메시지의 처음 32 비트를 보완하는 이유는 메시지가 모두 0이더라도 모두 0 CRC를 얻지 못하기 때문입니다.
답변
CRC는 매우 간단합니다. 비트와 데이터로 표현 된 다항식을 취하고 다항식을 데이터로 나눕니다 (또는 데이터를 다항식으로 표현하고 동일한 작업을 수행합니다). 0과 다항식 사이에있는 나머지는 CRC입니다. 부분적으로 불완전하기 때문에 코드를 이해하기가 약간 어렵습니다. temp 및 testcrc가 선언되지 않았기 때문에 인덱싱되는 항목과 알고리즘을 통해 실행되는 데이터의 양이 명확하지 않습니다.
CRC를 이해하는 방법은 짧은 다항식 (아마도 4 비트)이있는 짧은 데이터 (16 비트 정도)를 사용하여 몇 가지를 계산하는 것입니다. 이런 식으로 연습하면 코딩 방법을 이해하게 될 것입니다.
자주 수행하는 경우 CRC는 소프트웨어에서 계산하는 데 상당히 느립니다. 하드웨어 계산은 훨씬 더 효율적이며 몇 개의 게이트 만 필요합니다.
답변
Wikipedia Cyclic redundancy check 및 Computation of CRC 기사 외에도 Reversing CRC-Theory and Practice * 라는 제목의 논문 이 좋은 참고 자료가되었습니다.
CRC를 계산하는 데는 기본적으로 대수적 접근 방식, 비트 지향 접근 방식 및 테이블 기반 접근 방식의 세 가지 접근 방식이 있습니다. 에서 CRC 반전 – 이론 및 실습 * ,이 세 가지 각각의 알고리즘을 / C 프로그래밍 언어의 CRC32의 구현하여 부록에 동반 이론적으로 설명 접근한다.
* PDF 링크
반전 CRC – 이론 및 실습.
HU 베를린 공개 보고서
SAR-PR-2006-05
2006 년 5 월
저자 :
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich
답변
이 질문에 대한 답을 찾기 위해 잠시 시간을 보냈고 마침내 오늘 CRC-32에 대한 자습서를 게시했습니다.
CRC-32 해시 자습서-AutoHotkey Community
이 예제에서는 ASCII 문자열 ‘abc’에 대한 CRC-32 해시를 계산하는 방법을 보여줍니다.
calculate the CRC-32 hash for the ASCII string 'abc':
inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7
011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000
'CRC division':
01111001101110010011100111111111000000000000000000000000
100000100110000010001110110110111
---------------------------------
111000100010010111111010010010110
100000100110000010001110110110111
---------------------------------
110000001000101011101001001000010
100000100110000010001110110110111
---------------------------------
100001011101010011001111111101010
100000100110000010001110110110111
---------------------------------
111101101000100000100101110100000
100000100110000010001110110110111
---------------------------------
111010011101000101010110000101110
100000100110000010001110110110111
---------------------------------
110101110110001110110001100110010
100000100110000010001110110110111
---------------------------------
101010100000011001111110100001010
100000100110000010001110110110111
---------------------------------
101000011001101111000001011110100
100000100110000010001110110110111
---------------------------------
100011111110110100111110100001100
100000100110000010001110110110111
---------------------------------
110110001101101100000101110110000
100000100110000010001110110110111
---------------------------------
101101010111011100010110000001110
100000100110000010001110110110111
---------------------------------
110111000101111001100011011100100
100000100110000010001110110110111
---------------------------------
10111100011111011101101101010011
remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2
thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2
답변
그런 다음 항상 수십 개의 컴퓨터 언어로 구현 된 crc32를 보여주는 Rosetta 코드가 있습니다. https://rosettacode.org/wiki/CRC-32 및 많은 설명 및 구현에 대한 링크가 있습니다.
답변
crc32를 미리 알림으로 줄이려면 다음을 수행해야합니다.
- 각 바이트에서 비트 반전
- xor 0xFF를 사용하는 처음 4 바이트 (이는 선행 0에서 오류를 방지하기위한 것입니다)
- 끝에 패딩 추가 (마지막 4 바이트가 해시에 포함되도록 함)
- 알림 계산
- 비트를 다시 반전
- xor 결과를 다시.
코드에서 이것은 다음과 같습니다.
func CRC32 (file []byte) uint32 {
for i , v := range(file) {
file[i] = bits.Reverse8(v)
}
for i := 0; i < 4; i++ {
file[i] ^= 0xFF
}
// Add padding
file = append(file, []byte{0, 0, 0, 0}...)
newReminder := bits.Reverse32(reminderIEEE(file))
return newReminder ^ 0xFFFFFFFF
}여기서 alertIEEE는 GF (2) [x]에 대한 순수한 알림입니다.
