꽃미남 프로그래머 김포프가 창립한 탑 프로그래머 양성 교육 기관 POCU 아카데미 오픈!
절찬리에 수강생 모집 중!
프로그래밍 언어 입문서가 아닌 프로그래밍 기초 개념 입문서
문과생, 비전공자를 위한 프로그래밍 입문책입니다.
jobGuid 꽃미남 프로그래머 "Pope Kim"님의 이론이나 수학에 치우치지 않고 실무에 곧바로 쓸 수 있는 실용적인 셰이더 프로그래밍 입문서 #겁나친절 jobGuid "1판의내용"에 "새로바뀐북미게임업계분위기"와 "비자관련정보", "1판을 기반으로 북미취업에 성공하신 분들의 생생한 경험담"을 담았습니다.
Posted by myerin
지난글에서는  Hash String을 사용하는 장점에 대해서 설명하였습니다.
Hash String을 사용하는 가장 큰 이점은 속도라고 설명을 드렸었는데, 이에 대한 컴파일러 최적화가 
어떻게 이루어 지는가에 대한 내용이 포프님께서 작성하신 글 ( http://www.gamedevforever.com/50 )에
 잘 설명되어 있습니다. Hash String을 사용할 때 문제가 되는 해쉬의 중복에 대한 내용은 
 ( http://blog.naver.com/PostView.nhn?blogId=techshare&logNo=100148848453 )에서
  잘 설명 되어 있습니다.

이번 글에서는 문자열을 Hash로 치환하고 이를 관리하는 시스템에 대해서 설명하도록 하겠습니다. 
여기서는 위 블로그 주인장이신 techsharer님의 테스트 결과에 따라 CRC32를 가지고 가장 해쉬 분포도가 
높은 공인된 다항식인 0x04C11DB7을 사용하도록 하겠습니다.

CRC32를 사용하기 위해서는 선행되어야 할 작업은 CRC32 테이블을 초기화 하는 것입니다. 
이러한 작업들을 설명하기 위한 클래스를 작성해 보도록 하겠습니다.

class CRC32Hash
{
public:
// Constructor
CRC32Hash();
// Creates a CRC from a text string
INT GetCRC(char* InText);
        INT GetCRC(wchar_t* InText); 
 

protected:
// Builds lookup table array
void InitTable();
// Reflects CRC bits in the lookup table
ULONG Reflect( ULONG Ref, char ch);

protected:
// Lookup table array
ULONG Table[256];
};


클래스의 헤더는 위와 같습니다. Init() 함수가 CRC32 테이블을 초기화 하는 함수이며 이는 내부에서 한번만
호출 되도록 protected 영역에 놓았습니다. Reflect는 테이블을 초기화 할 때 내부적으로 사용되는 함수 입니다.
저는 이 테이블 초기화를 생성자에서 자동 호출하도록 사용하고 있습니다. 위의 선언에 따라 생성자 및
 테이블 초기화를 구현해 보도록 하겠습니다.

CRC32Hash::CRC32Hash()
{
InitTable();
}

void CRC32Hash::InitTable()
{
// 이 함수는 CRC 테이블을 초기화 할 때 한번만 호출되어야 합니다.

// 이 테이블 초기화 함수는 PKZip, WinZip과 이더넷의 CRC-32가 사용하는 공식적인 다항식을 사용합니다.
ULONG Polynomial = 0x04C11DB7;

// 256개의 값들이 ASCII 문자 코드들을 표현하게 됩니다.
for ( INT i = 0; i <= 0xFF; i++ )
{
Table[i] = Reflect( i, 8 ) << 24;
for ( INT j = 0; j < 8; j++ )
{
Table[i] = ( Table[i] << 1 ) ^ ( Table[i] & ( 1 << 31 ) ? Polynomial : 0 );
}

Table[i] = Reflect( Table[i], 32 );
}
}

ULONG CRC32Hash::Reflect( ULONG Ref, char Ch )
{
ULONG Value( 0 );

// 7번째 비트와 0번째 비트를 교환합니다.
// 6번째 비트와 1번째 비트를 교환합니다.
// 이 작업 계속 진행합니다.
for ( INT i = 0; i < ( Ch + 1 ); i++ )
{
if ( Ref & 1 )
{
Value |= 1 << ( Ch - i );
}

Ref >>= 1;
}

return Value;
}


CRC32 테이블 초기화가 위의 함수들을 통해 이루어 지게 됩니다. 다음은 문자열을 이 테이블을 사용하여 CRC를
구하는 것입니다.

INT CRC32Hash::GetCRC( char* Text )
{
// 문자열을 이 함수에 넘겨 CRC를 생성하게 합니다.

// 위 테이블 초기화 함수들로 검색 테이블이 초기화되면, 이 함수는 검색 테이블을 사용하여 CRC들을 생성합니다.

// unsigned 변수들을 사용하도록 해야하는데, 음의 값을 가질 수 있는 변수들은 0 비트들이 요구될 때
// 상위 비트들을 사용하기 때문입니다.

//모든 비트들을 모두 켜서 시작합니다.
ULONG CRC( 0xFFFFFFFF );
// 문자열의 길이를 구합니다.
INT Len = strlen( Text );

// 버퍼의 텍스트를 저장합니다.
unsigned char* Buffer = Text;

// 문자열내의 각 문자에 대해 검색 테이블 값들을 사용하여, 알고리즘을 실행합니다.
while ( Len-- )
{
CRC = ( CRC >> 8 ) ^ Table[ ( CRC & 0xFF ) ^ *Buffer++ ];
}

// 초기 값과 Exclusive OR로 결과를 산출 합니다.
return CRC ^ 0xFFFFFFFF;
}

// Ansi character
INT CRC32Hash::GetCRC( char* Text )
{
// 문자열을 이 함수에 넘겨 CRC를 생성하게 합니다.

// 위 테이블 초기화 함수들로 검색 테이블이 초기화되면, 이 함수는 검색 테이블을 사용하여 CRC들을 생성합니다.

// unsigned 변수들을 사용하도록 해야하는데, 음의 값을 가질 수 있는 변수들은 0 비트들이 요구될 때
// 상위 비트들을 사용하기 때문입니다.

//모든 비트들을 모두 켜서 시작합니다.
ULONG CRC( 0xFFFFFFFF );
// 문자열의 길이를 구합니다.
INT Len = strlen( Text );

// 버퍼의 텍스트를 저장합니다.
unsigned char* Buffer = Text;

// 문자열내의 각 문자에 대해 검색 테이블 값들을 사용하여, 알고리즘을 실행합니다.
while ( Len-- )
{
char Ch = *Buffer++;
unsigned char* B = unsigned char(Ch);
CRC = ( CRC >> 8 ) ^ Table[ ( CRC & 0xFF ) ^ B ];
}

// 초기 값과 Exclusive OR로 결과를 산출 합니다.
return CRC ^ 0xFFFFFFFF;
}

// wide character
INT CRC32Hash::GetCRC( wchar_t* Text )
{
// 문자열을 이 함수에 넘겨 CRC를 생성하게 합니다.

// 위 테이블 초기화 함수들로 검색 테이블이 초기화되면, 이 함수는 검색 테이블을 사용하여 CRC들을 생성합니다.

// unsigned 변수들을 사용하도록 해야하는데, 음의 값을 가질 수 있는 변수들은 0 비트들이 요구될 때
// 상위 비트들을 사용하기 때문입니다.

//모든 비트들을 모두 켜서 시작합니다.
ULONG CRC( 0xFFFFFFFF );
// 문자열의 길이를 구합니다.
INT Len = strlen( Text );

// 버퍼의 텍스트를 저장합니다.
unsigned char* Buffer = Text;

// 문자열내의 각 문자에 대해 검색 테이블 값들을 사용하여, 알고리즘을 실행합니다.
while ( Len-- )
{
wchar_t Ch = *Buffer++;
                unsigned char B = unsigned char(Ch); 
CRC = ( CRC >> 8 ) ^ Table[ ( CRC & 0xFF ) ^  B ]; 
// wide character이기 때문에 한번 더 알고리즘을 실행합니다. 16bit 이기 때문에...
B = Ch >> 8;
CRC = ( CRC >> 8 ) ^ Table[ ( CRC & 0xFF ) ^  B ];  
  }

// 초기 값과 Exclusive OR로 결과를 산출 합니다.
return CRC ^ 0xFFFFFFFF;
}


이제 위의 함수를 사용하여 문자열에 대한 Hash Key (CRC)를 얻어올 수 있습니다. 이로서 기본적인 Hash String ID를 사용하기 위한 준비가 완료 되었습니다. GetCRC(...) 함수를 사용하여 얻어온 INT형으로의 비교만으로 문자열에 대한 비교 속도가 최대화 될 수 있습니다.

하지만 이것을 실제로 사용하기에는 편의성이 떨어지게 됩니다. 여기에 추가될 가장 기본적인 기능은 Hash Key를 가지고 이에 대한 문자열을 다시 얻어올 수 있어야 합니다. 또한 중복에 대한 분포도가 높을지라도 게임에서 많이사용되는 문자열들에 대한 처리를  해주어 중복을 더 회피할 수 있는 방법이 존재합니다. 다음 2회의 글에 걸쳐서 이러한 기법들에 대한 설명을 해 보도록 해 보겠습니다.

- by 김영민

- 참고 문서: 위키페디아 순환 중복 검사

댓글을 달아 주세요

  1. Favicon of https://gamedevforever.com 랩.좀비 2012.02.22 16:12 신고  댓글주소  수정/삭제  댓글쓰기

    올 좋은 글 감사합니다. 기초가 부족하니 새로워 보이는군요.

  2. Favicon of https://gamedevforever.com 친절한티스 2012.02.23 09:56 신고  댓글주소  수정/삭제  댓글쓰기

    좋은 글 잘 보고 있습니다~