프로그래밍 언어 입문서가 아닌 프로그래밍 기초 개념 입문서
문과생, 비전공자를 위한 프로그래밍 입문책입니다.
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 신고  댓글주소  수정/삭제  댓글쓰기

    좋은 글 잘 보고 있습니다~