CRC32 체크섬은 어떻게 계산됩니까?
제가 못 보고 있는 것일 수도 있지만, CRC32는 불필요하게 복잡하거나 웹에서 찾을 수 있는 모든 곳에 설명이 불충분한 것 같습니다.
메시지 값을 (제너레이터) 다항식으로 나눈 비캐리 기반 산술적 나눗셈의 나머지는 이해하지만, 실제 실장은 알 수 없습니다.
'CRC 오류 검출 알고리즘에 대한 무통 가이드'를 읽었는데, 전혀 고통스럽지 않았습니다.그것은 이론을 꽤 잘 다루지만, 저자는 결코 단순한 "이거다"에 이르지 못한다.그는 표준 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의 다항식은 다음과 같습니다.
x3226 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x54 + x2 + x + 1
또는 16진수 및 2진수:
B70x01 04 C1 1D B7
0000 0000 0100 1100 0001 1101 1011 011
가장 높은 항(x32)은 일반적으로 명시적으로 쓰여지지 않으므로 대신 다음과 같이 16진수로 나타낼 수 있습니다.
0x04 C1 1D B7
즉 다항식, 즉 다항식과 1 0 첫 비트)및 '0'(''')입니다.x1번입니다.
왜 이 다항식일까요?왜냐하면 주어진 다항식이 있어야 하고 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!!!!
나눗셈은 우리가 버린 몫과 계산된 체크섬인 나머지를 산출합니다.이것으로 계산이 종료됩니다.보통 체크섬은 메시지에 추가되어 결과가 전송됩니다.이 경우는, 110101101110 이 됩니다.
32비트 숫자만 제수로 사용하고 스트림 전체를 배당금으로 사용합니다.몫은 버리고 나머지는 가지세요.나머지 부분은 메시지 끝에 붙이면 CRC32가 됩니다.
평균적인 남성 리뷰:
QUOTIENT
----------
DIVISOR ) DIVIDEND
= REMAINDER
- 처음 32비트를 취합니다.
- 시프트 비트
- 32비트가 DIVISOR보다 작으면 스텝2로 넘어갑니다
- XOR 32비트 by DIVISOR. 2단계로 이동합니다.
(스트림을 32비트로 분할하거나 패딩해야 합니다.예를 들어 8비트 ANSI 스트림을 패딩해야 합니다.또, 스트림의 마지막에 분할이 정지됩니다).
CRC-32 해시 튜토리얼을 게재했습니다.CRC-32 해시 튜토리얼 - AutoHotkey Community
이 예에서는 ANSI(문자당 1바이트) 문자열 'abc'의 CRC-32 해시를 계산하는 방법을 보여 줍니다.
calculate the CRC-32 hash for the 'ANSI' string 'abc':
inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7
start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)
reverse the bits in each byte:
10000110 01000110 11000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)
01111001101110010011100111111111000000000000000000000000
next we will perform 'CRC division':
a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'
note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit
'CRC division':
'divide' by the polynomial 0x104C11DB7:
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
we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53
note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bit
XOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2
thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2
IEEE 802.3의 경우 CRC-32.메시지 전체를 시리얼 비트스트림으로 간주하고 메시지 끝에 32개의 0을 추가합니다.그런 다음 메시지의 모든 바이트의 비트를 반전시키고 첫 번째 32비트를 1로 보완해야 합니다.CRC-32 다항식 0x104C11DB7로 나눕니다.마지막으로 1은 이 나눗셈의 나머지 32비트를 보완해야 합니다.나머지 4바이트 각각은 비트 반전입니다.이는 메시지 끝에 부가되는 32비트 CRC가 됩니다.
이 이상한 순서의 이유는 첫 번째 이더넷 실장에서는 메시지를 한 번에1 바이트씩 시리얼화하여 각 바이트의 최하위 비트를 먼저 전송하기 때문입니다.시리얼 비트스트림은 시리얼 CRC-32 시프트 레지스터 계산을 거쳤습니다.이 계산은 메시지가 완료된 후에 간단히 보완되어 회선으로 송신됩니다.메시지의 처음 32비트를 보완하는 이유는 메시지가 모두0인 경우에도 모두0의 CRC를 얻지 않기 위해서입니다.
Wikipedia Cyclic redundancy check 및 계산 CRC artices와 더불어 Reversing CRC - Theory and* Practice라는 제목의 논문이 좋은 참고 자료라는 것을 발견했습니다.
CRC 계산에는 기본적으로 대수적 접근법, 비트 지향 접근법 및 테이블 기반 접근법의 세 가지 접근법이 있습니다.Reversing CRC - Theory and* Practice에서 이 세 가지 알고리즘/접근법 각각은 부록에 포함된 이론으로 CRC32를 C 프로그래밍 언어로 구현하여 설명합니다.
* PDF 링크
CRC – CRC
리포트 HU ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★」
SAR-PR-2006-05
~2006년 5일
스티게,
CRC는 매우 간단합니다. 비트와 데이터로 표현된 다항식을 데이터로 나눕니다(또는 데이터를 다항식으로 표현하고 동일한 작업을 수행합니다).0과 다항식 사이의 나머지가 CRC입니다.코드가 약간 이해하기 어려운 것은 불완전한 탓도 있습니다.temp와 testcrc는 선언되어 있지 않기 때문에 무엇을 인덱스하고 있는지, 알고리즘에서 얼마나 많은 데이터가 실행되고 있는지 불명확하기 때문입니다.
CRC를 이해하는 방법은 짧은 다항식과 함께 짧은 데이터 조각(16비트 정도)을 사용하여 소수를 계산하는 것입니다. 아마도 4비트 정도일 것입니다.이렇게 연습하면 코딩하는 방법을 정말 이해할 수 있을 거예요.
CRC를 자주 사용하는 경우 소프트웨어에서 CRC를 계산하는 데 시간이 걸립니다.하드웨어 계산은 훨씬 더 효율적이며 몇 개의 게이트만 있으면 됩니다.
그리고 Rosetta Code는 수십 개의 컴퓨터 언어로 구현된 crc32를 보여줍니다.https://rosettacode.org/wiki/CRC-32 및 많은 설명과 구현에 대한 링크가 있습니다.
crc32를 리마인더로 줄이려면 다음 작업을 수행해야 합니다.
- 각 바이트의 비트 반전
- x 또는 0xFF의 첫 번째 4바이트(선행0 의 에러를 회피하기 위해서)
- 마지막에 패딩을 추가합니다(마지막 4바이트를 해시에 포함시킵니다).
- 미리 알림 계산
- 비트를 다시 반전시킵니다.
- x 또는 결과를 다시 표시합니다.
코드에서는 다음과 같습니다.
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
}
여기서 리마인더IEEE는 GF(2)[x]에 대한 완전한 리마인더입니다.
언급URL : https://stackoverflow.com/questions/2587766/how-is-a-crc32-checksum-calculated
'programing' 카테고리의 다른 글
| Vue nexttick을 사용하기 위해 지연된 jquery를 변경하는 방법 (0) | 2022.07.19 |
|---|---|
| vue findIndex가 함수가 아닙니다. (0) | 2022.07.19 |
| C의 스택에 구조를 작성하려면 어떻게 해야 합니까? (0) | 2022.07.19 |
| 필요에 따라 필드를 표시하는 방법 확인 (0) | 2022.07.19 |
| Java SE 6 vs. JRE 1.6 vs. JDK 1.6 - 이는 무엇을 의미합니까? (0) | 2022.07.19 |