Implement Hash String ID Index #2

지난글에서는  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 김영민

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