[펌] CRC / 2007.07.11 뇌입어 포스팅

 

미야맑음 | 미야
http://blog.naver.com/will2power/120014193819

파일 체크섬을 만드는 방법에 대한 글입니다.

 

CRC32: Generating a checksum for a file

 

This article was contributed by Brian Friesen.

Environment: VC5, VC6

 

출처 http://www.codeguru.com/algorithms/crc32.html

 

---

 

Introduction

시작하며

 

Recently I wrote a program in which I wanted to generate a CRC for a given file. I did some checking on the web for sample CRC code, but found very few algorithms to help me. So I decided to learn more about CRCs and write my own code. This article describes what a CRC is, how to generate them, what they can be used for, and lastly source code showing how it's done.

 

최근 필자는 주어진 파일에 대한 CRC를 만들어야 하는 프로그램을 작성했다. 필자는 웹에서 CRC 예제 코드를 찾아봤지만, 필자를 도와줄 수 있는 알고리즘은 너무 부족했다. 그래서 필자는 CRC에 대해 좀더 많이 배워서 스스로 코드를 만들어 쓰기로 결정하게 되었다. 이 글은 CRC가 무엇이며, 어떻게 만드는지, 무엇 때문에 사용될 수 있는지, 그리고 마지막으로 CRC가 구현되는 방법을 보여주는 소스코드에 대해 설명할 것이다.

 

What is a CRC

CRC란 모냐.

 

CRC is an acronym for Cyclic Redundancy Checksum or Cyclic Redundancy Check (depending on who you ask). A CRC is a "digital signature" representing data. The most common CRC is CRC32, in which the "digital signature" is a 32-bit number. The "data" that is being CRC'ed can be any data of any length; from a file, to a string, or even a block of memory. As long as the data can be represented as a series of bytes, it can be CRC'ed. There is no single CRC algorithm, there can be as many algorithms as there are programmers. The ideal CRC algorithm has several characteristics about it. First, if you CRC the same data more than once, you must get the same CRC every time. Secondly, if you CRC two different pieces of data you should get two very different CRC values. If you CRC the same data twice, you get the same digital signature. But if you CRC data that differs (even by a single byte) then you should get two very different digital signatures. With a 32-bit CRC there are over 4 billion possible CRC values. To be exact that's 2³² or 4,294,967,296. With that many CRC values it's not difficult for every piece of data being CRC'ed to get a unique CRC value. However, it is possible for spurious hits to happen. In other words two completely different pieces of data can have the same CRC. This is rare, but not so rare that it won't happen.

 

CRC는 Cyclic Redundancy Checksum 또는 Cyclic Redundancy Check의 머릿글자를 따온 것이다. CRC는 데이터를 대표하는 “디지털 인증”이다. 대부분의 일반 CRC는 CRC32를 의미한다. CRC32에서 “디지털 인증”은 32비트 숫자이다. CRC를 사용할 수 있는 “데이터”는 어떤 길이의 어떤 데이터라도 될 수 있다. 파일에서부터, 문자열, 메모리 블록에 이르기까지 모두 가능하다. 데이터가 바이트의 연속으로 표현되기만 한다면, 그 데이터에는 CRC를 적용할 수 있다. 유일한 CRC 알고리즘이란 존재하지 않는다. 프로그래머 수만큼 많은 알고리즘이 존재할 수 있다. 이상적인 CRC 알고리즘은 몇가지 특징을 가지고 있다. 첫째는, 같은 데이터에 대해 한번 이상 CRC를 만들 경우, 매번 같은 CRC가 만들어져야 한다. 둘째로, 만약 여러분이 두개의 다른 데이터 조각으로부터 CRC를 만든다면, 두개의 서로 다른 CRC 값을 얻을 수 있어야 한다. 같은 데이터로부터 두번 CRC를 만드면, 같은 디지털 인증을 얻는다. 하지만 (한 바이트라도) 다른 데이터로부터 CRC를 만들면, 두개의 서로 다른 디지털 인증을 얻어야 한다. 하나의 32비트 CRC에는, 40억 개를 넘는 CRC 값이 가능하다. 정확히 말하면 2³² 혹은 4,294,967,296 개이다. 이렇게 많은 CRC 값이 가능하기 때문에, 모든 데이터 조각마다 고유한 CRC 값을 만들어내는 것은 어려운 일은 아니다. 하지만, 중복된 값이 발생할 수 있는 가능성이 존재한다. 다시 말해, 두개의 완전히 다른 데이터 조각이 같은 CRC 값을 가질수 있다는 것이다. 이것은 드문 일이기는 하지만 전혀 일어나지 않을 만큼 드물다고 할 수 는 없다.

 

Why use CRCs

왜 CRC를 사용하나

 

Most of the time CRCs are used to compare data as an integrity check. Suppose there are two files that need to be compared to determine if they are identical. The first file is on Machine A and the other file is on Machine B. Each file is a rather large file (say 500 MB), and there is no network connection between the two machines. How do you compare the two files? The answer is CRC. You CRC each of the two files, which gives you two 32-bit numbers. You then compare those 32-bit numbers to see if they are identical. If the CRC values are different, then you can be 100% guaranteed that the files are not the same. If the CRC values are the same, then you can be 99% sure that the files are the same. Remember, because spurious hits can happen you cannot be positive that the two files are identical. The only way to be positive they are the same is to break down and do a comparison one byte at a time. But CRCs offer a quick way to be reasonably certain that two files are identical.

 

대부분의 경우 CRC는 데이터를 비교하여 무결성을 체크하는데에 사용된다. 두 개의 파일이 존재하고, 이 둘이 같은지를 알아내기 위해 비교를 해보아야 한다고 가정해보자. 첫번째 파일은 머신 A에 있고 다른 파일은 머신 B에 있다. 각각의 파일은 엄청나게 크다. (500 메가라고 하자) 두 머신 사이엔 네트웍 연결도 없다. 여러분은 어떻게 이 두개의 파일을 비교할 것인가? 해결책은 CRC이다. 여러분은 두개의 파일 각자에서 CRC를 만들어 두개의 32비트 숫자를 얻어낸다. 다음에 이 32비트 숫자를 비교하여 동일한지를 알아낸다. CRC 값이 다르다면, 두 파일은 같지 않다고 100% 장담할 수 있게 되는 것이다. 만약 CRC 값이 같다면, 두 파일이 서로 같다고 99% 확신할 수 있다. 중복된 CRC가 만들어질 수 있기 때문에 여러분은 두 파일이 동일하다고 완전히 장담할 수 없다는 것을 기억해야 한다. 그들이 같다고 장담할 수 있는 유일한 방법은 파일을 뽀개서(열어서) 한번에 한 바이트씩 비교하는 것이다. 하지만 CRC는 두개의 파일이 같다고 무리없이 확신할수 있는 빠른 방법을 제공한다.

 

How to generate CRCs

CRC는 어떻게 생성하냐.

 

Generating CRCs is a lot like cryptography in that involves a lot of mathematical theories. Since I don't fully understand it myself, I won't go into a lot of those details here. Instead I'll focus on how to program a CRC algorithm. Once you know how the algorithm works you should be able to write a CRC algorithm in any language on any platform. The first part of generating CRCs is the CRC lookup table. In CRC32 this is a table of 256 specific CRC numbers. These numbers are generated by a polynomial (the computation of these numbers and what polynomial to use are part of that math stuff I'm avoiding). The next part is a CRC lookup function. This function takes two things, a single byte of data to be CRC'ed and the current CRC value. It does a lookup in the CRC table according to the byte provided, and then does some math to apply that lookup value to the given CRC value resulting in a new CRC value. The last piece needed is the actual data that is to be CRC'ed. The CRC algorithm reads the first byte of data and calls the CRC lookup function which returns the CRC value for that single byte. It then calls the CRC lookup function with the next byte of data and passes the previous CRC value. After the second call, the CRC value represents the CRC of the first two bytes. You continuously call the CRC lookup function until all the bytes of the data have been processed. The resulting value is the CRC for the whole data.

 

CRC를 생성하는 것은 많은 수학 이론들을 사용한다는 점에서 암호화와 매우 비슷하다. 필자는 이 과정을 완벽히 이해하지 못하기 때문에, 여기서 상세한 설명을 하지는 않을 것이다. 대신 필자는 CRC 알고리즘을 프로그래밍하는 방법에 대해 초점을 맞출 것이다. 일단 여러분이 알고리즘의 작동방식을 알게 된다면, 어떤 플랫폼의 어떤 언어에서도 CRC 알고리즘을 작성할 수 있을 것이다. CRC를 생성하는 첫번째 단계는 CRC lookup 테이블이다. CRC32에서는 256개의 CRC 숫자들이 지정된 테이블이다. 이 숫자들은 다항식에 의해 생성된다. (이 숫자들의 계산 과정과, 어떤 다항식이 사용되는지는 필자가 피해가고자 하는 수학에 속하는 부분이다.) 다음 단계는 CRC lookup 함수이다. 이 함수는 두개의 파라미터를 받는데, CRC를 만들어낼 1바이트 데이터와 현재 CRC 값이다. 이 함수는 제공된 바이트에 따라 CRC lookup 테이블을 검색한 후, 그 lookup 값을 주어진 CRC 값에 적용하는 수학 계산을 하여 새로운 CRC 값을 산출해낸다. 필요한 마지막 조각은 CRC 생성에 사용될 실제 데이터이다. CRC 알고리즘은 데이터의 첫번째 바이트를 읽고 CRC lookup 함수를 호출하여 1바이트에 대한 CRC 값을 돌려받는다. 두번째 호출 이후에 CRC 값은 처음 두개의 바이트에 대한 CRC가 되는 것이다. 여러분은 계속해서 CRC lookup 함수를 호출하여 데이터의 모든 바이트가 처리되도록 하면 된다. 결과 값은 전체 데이터의 CRC가 된다.

 

Code Details

코드 설명.

 

In this sample program I wanted to show that there are many different ways of generating CRCs. There are over 8 different CRC functions, all based on the above steps for generating CRCs. Each function differs slightly in it's intended use or optimization. There are four main CRC functions, each described below. There are also two separate CRC classes, but more on that later. And lastly there are a few helper functions that CRC strings.

 

이 샘플 프로그램에서 필자는 CRC를 생성하는 방법이 많다는 것을 보여주고 싶었다. 8개 이상의 다른 CRC 함수들이 있는데, 모두 위에서 설명한 CRC 생성 단계에 기초한 것이다. 각각의 함수들은 의도된 사용처와 최적화에 있어서 약간씩 다르다. 4개의 주요 CRC 함수가 있는데 아래에서 설명될 것이다. 또 두 개의 별도의 CRC 클래스가 있는데, 그에 대해서는 다음에 설명하기로 한다. 그리고 마지막으로 CRC 문자열에 대한 몇 개의 보조 함수들이 있다.

 

C++ Streams: The first function represents the simplest CRC function. The file is opened using the C++ stream classes (ifstream). This function uses nothing but standard C++ calls, so this function should compile and run using any C++ compiler on any OS.

 

C++ Streams: 첫번째 함수는 가장 간단한 CRC 함수를 표현한 것이다. 파일은 C++ 스크림 클래스를 사용하여 열리게 된다. 이 함수는 표준 C++ 호출 이외에는 아무것도 사용하지 않기 때문에 어떤 OS에서든지 C++ 컴파일러를 사용하여 컴파일하고 실행할 수 있다.

 

Win32 I/O: This function is more optimized in that it uses the Win32 API for file I/O; CreateFile, and ReadFile. This will speed up the processing, but by using the Win32 API the code is no longer platform independent.

 

Win32 I/O: 이 함수는 좀더 최적화되었으며, 파일 입출력을 위해 Win32 API를 사용한다; CreateFile 와 ReadFile. 이것은 처리 속도를 증가시켜 주지만, Win32 API를 사용하기 때문에 코드는 더 이상 플랫폼 독립적이지 않다.

 

Filemaps: This function uses memory mapped files to process the file. Filemaps can be used to greatly increase the speed with which files are accessed. They allow the contents of a file to be accessed as if it were in memory. No longer does the programmer need to call ReadFile and WriteFile.

 

Filemaps: 이 함수는 메모리 맵 파일을 사용하여 파일을 처리하낟. 파일맵은 액세스되는 파일의 속도를 비약적으로 증가시켜줄 수 있다. 파일맵은 파일의 내용이 메모리에 존재하는 것처럼 엑세스 되도록 해준다. 프로그래머는 더 이상 ReadFile과 WriteFile을 호출할 필요가 없어진다.

 

Assembly: The final CRC function is one that is optimized using Intel Assembly. By hand writing the assembly code the algorithm can be optimized for speed, although at the sacrifice of being easy to read and understand.

 

Assembly: 마지막 CRC 함수는 인텔 어셈블리를 사용하여 최적화된 것이다. 어셈블리 코드를 직접 작성함으로써 알고리즘은 속도에 대해 최적화될 수 있다. 하지만 소스 코드를 읽거나 이해하기 어려워진다는 희생이 따를 것이다.

 

Those are the four main CRC functions. But there are actually two versions of each function. There are two classes, CCrc32Dynamic and CCrc32Static, each of which have the above four functions for a total of eight. The only difference between the static and dynamic classes is the CRC table. With the static class the CRC table and all the functions in the class are static. The trade off is simple. The static class is simpler to use, but the dynamic class uses memory more efficiently because the CRC table (1K in size) is only allocated when needed.

 

이들이 4가지 주요 CRC 함수들이다. 하지만 실제로는 각각의 함수들에 대해 두개의 버전이 존재한다. CCrc32Dynamic 와 CCrc32Static 라는, 두개의 클래스가 있는데, 그 각각은 위의 4개의 함수를 가지고 있으며, 전체 합쳐서 8개가 된다. static과 dynamic 클래스의 유일한 차이점은 CRC 테이블이다. static 클래스에서는 CRC 테이블과 클래스의 모든 함수들이 정적(static)이다. 반면에 간단함이라는 장점을 가진다. static 클래스는 사용하기 더욱 간단하다. 하지만 dynamic 클래스는 메모리를 더 효과적으로 사용한다. 그것은 CRC 테이블(1K 크기)이 필요할 때에만 할당되기 때문이다.

 

// Using the static class is as easy as one

//  line of code

dwErrorCode =

     CCrc32Static::FileCrc32Assembly(m_strFilename,

                                     dwCrc32);

 

// Whereas there is more involved when using the

//   dynamic class

CCrc32Dynamic *pobCrc32Dynamic = new CCrc32Dynamic;

pobCrc32Dynamic->Init();

dwErrorCode =

     pobCrc32Dynamic->FileCrc32Assembly(m_strFilename,

                                        dwCrc32);

pobCrc32Dynamic->Free();

delete pobCrc32Dynamic;

 

Whenever you calculate a CRC you need to take into account the speed of the algorithm. Generating CRCs for files is both a CPU and a disk intensive task. Here is a table showing the time it took to CRC three different files. The columns are the different file sizes, the rows are the different CRC functions, and the table entries are in seconds. The system these numbers were captured on is a dual Pentium III at 1 GHz with a 10,000 RPM SCSI Ultra160 hard drive.

 

여러분이 CRC를 계산할 때마다 알고리즘의 속도를 측정해야 할 필요가 있다. 파일의 CRC를 생성하는 것은 CPU와 디스크 양쪽에 부하를 주는 작업이다. 여기 세개의 다른 파일로부터 CRC를 생성하는데 걸린 시간을 보여주는 표가 있다. 각 열은 각각 다른 파일 사이즈이고, 각 행은 가각 다른CRC 함수들이다. 테이블 내용은  초 단위이다. 이러한 숫자들이 계산된 시스템은 듀얼 펜티엄 III, 1GHz, 10,000 RPM SCSI Ultra160 하드 드라이브이다.

 

	44 KB	34 MB	5 GB
C++ Streams	0.0013	0.80	125
Win32 I/O	0.0009	0.60	85
Filemaps	0.0010	0.60	87
Assembly	0.0006	0.35	49

 

As expected the C++ streams is the slowest function followed by the Win32 I/O. However, I was very surprised to see the filemaps was not were not faster than the Win32 I/O, in fact they are slower. After I thought about it some, I realized memory mapped files are designed to provide fast random access to files. But when you CRC you access the file sequentially. Thus filemaps are not faster, and the extra overhead of creating the "views" of the file are why it's slower. Filemaps do have one advantage that none of the other functions have. Memory mapped files are guaranteed to be able to access files up to the maximum file size in NT which is 2⁶⁴ or 18 exabytes. Although the Win32 I/O may handle files of this size, none of the documentation confirms this. [Note: The largest file I have CRC'ed is 40 GB, which all eight functions successfully CRC'ed, but took over 10 minutes each.]

 

예상대로 C++ 스트림이 가장 느린 함수이다. 그 뒤를 Win32 I/O를 사용한 함수가 따르고 있다. 그러나, 필자는 파일맵이 Win32 I/O보다 빠르지 않았다는 것을 알고 매우 놀랐다. 사실 더 느렸다. 필자가 그것에 해 조금 생각해 본 후에, 메모리 맵 파일이 파일의 랜덤 액세스를 빠르게 하기 위해 구상된 것임을 깨달았다. 하지만 CRC를 만들 때는 파일을 순차적으로 엑세스한다. 따라서 파일맵은 더 빠르지 않고 파일의 “view”를 생성하는 추가적인 오버헤드를 갖게된다. 그것이 더 느려진 이유이다. 파일맵은 다른 함수들이 갖지 못한 하나의 장점을 가지고 있다. 메모리 맵 파일은 NT에서 최대 파일 크기 2⁶⁴ or 18 exabytes까지 엑세스할 수 있도록 보장된다. Win32 I/O가 이 크기의 파일을 다룰 수 있을지는 모르겠지만, 어떤 문서도 이에 대해 보장하지 않는다. [주: 필자가 CRC를 생성했던 가장 큰 파일은 40 GB였고, 모든 8개의 함수가 성공적으로 CRC를 만들어냈다. 하지만 모든 경우에 10분 이상이 걸렸다.]

 

If anyone who reads this article knows a way to improve the speed even more, please post the code or email me. Especially if you know of a speed improvement for the assembly code. I will bet there are further optimizations that can be made to the assembly code. After all I don't know Intel Assembly very well, therefore I'm sure there are optimizations I don't know about.

 

이 글을 읽은 분들 중 속도를 더 빠르게 향상시킬 수 있는 방법을 아는 분이 있다면, 코드를 부쳐주거나 메일로 보내주면 감사하겠다. 특히 어셈블리 코드 속도 향상에 대해 알고 있다면 말이다. 필자는 어셈블리 코드에 대해 좀더 최적화 할 수 있을 거라고 생각한다. 필자는 인텔 어셈블리를 아주 잘 알지는 못하기 때문에, 내가 알고 있지 못하는 최적화 방법이 있을 거라고 확신한다.