[코드보기] strtok

문자열을 parsing하는 ANSI C 함수중에 가장 많이 사용되는 것이 strtok 함수가 아닐까 한다.

strtok 함수는 문자열에서 token을 찾아 잘라내는 함수이다.
strtok 함수는 자세한 내용은 여러 검색 사이트나 Microsoft MSND Site에서 검색를 통해서

알 수 있다.

여기서는 strtok 함수의 구현된 code에서 2가지 흥미로운 내용을 이야기하고자 한다.
하나는 비트연산이며, 다른 하나는 Reentrancy 문제이다.

우선 가정을 하나한다. 모든 문자는 ASCII code라고 가정한다. 2bytes 문자는 제외하고 생각한다.

먼저 비트연산에 대해서 이야기하자. (Reentrancy 문제는 다음에 이야기 하겠습니다.)

strtok 함수는 내부적으로 비트연산을 사용한다.
비트연산을 사용하는 목적은 문자열내에 token을 빠른 속도로 찾아내기 위해서 사용한다.

일단 먼저 문자열에서 첫번째 'a' 라는 문자를 찾는 방법을 생각 해 보자.
문자열을 반복문으로 순환하면서 첫번째 'a' 문자를 찾아보자.

<code 1>

char string[] = "this is a string";
unsigned int string_length = strlen(string);

for( index=0; index<string_length; index)
for( index=0; index<string_length; index++)
{
  if(string[index] == 'a')
      break;
}

그럼, 첫번째 'a' 문자 또는 첫번째 's'라는 문자를 찾아야 한다면 if 문을 하나 더 사용해야할까?
첫번째 'a' 또는's' 또는 't'를 찾아야 한다면 if문을 모두 3개 사용해야할까?
case 문으로 하면 보다 효율적일까?

아니면, 아래와 같이 찾아야 할 문자를 배열로 선언하고 for과 if문을 사용할까?

<code 2>

char string[] = "this is a string";
char token[] = "abc";
unsigned int string_length = strlen(string);

for( index=0; index<string_length; index)
for( index=0; index<string_length; index++)
{
  for(i_index=0; i_index<3; i_index++)
 {
   if(token[i_index] == string[index])
       break;
  }
 
  if(i_index < 3)
    break;
}

이와 같은 코드는 확장성과 속도면에서 저하를 가져온다.
그럼, 어떻게 하는 것이 좋을까?

조금 과장해서 이야기 하면 여기서 비트연산으로 마법을 일으킬 수 있다.

ASCII code는 255자를 표현할 수 있으며 1byte로 표현이 가능하다.
또한 ASCII code는 NULL(0)을 포함해서 256개가 있다.
그럼, 256개의 bit를 표현하기 한다면 32bytes가 필요하다.
32bytes는 C/C++ Code에서 32개의 byte 변수(char)로 표현이 가능하다.

그럼, 아래의 코드를 보자.

<code 3>

char string[] = "this is a string";
unsigned char bitmap[32]={0}; // 256가 bit masking을 사용하기 위해서.
unsigned int string_length = strlen(string);

// 'a' 문자의 ascii index 위치에 masking을 한다.
bitmap['a'>> 3] |= (1 << ('a' & 7));

for( index=0; index<string_length; index)
for( index=0; index<string_length; index++)
{
  if( (bitmap[string[index] >> 3]) & (1 << (string[index] & 7)) )
    break;
}

<code 1>과 같은 기능이지만 코드가 복잡하게 보인다.
하지만 <code 3>는 bit masking 을 사용하여 <code 1>에 비해 빠르고,
좋은 확장성을 지원한다.

그럼, 아래 코드를 보자.

<code 4>

char string[] = "this is a string";
char token[] = "abc";
unsigned int string_length = strlen(string);
unsigned char bitmap[32]={0}; // 256가 bit masking을 사용하기 위해서.

// token 배열에 저장된 문자의 ascii index 위치에 masking을 한다.
for( i_index = 0; i_index<3; i_index++)
  bitmap[ token[i] >> 3] |= (1 << ( token[i] & 7));
  bitmap[ token[i_index] >> 3] |= (1 << ( token[i_index] & 7));


for( index=0; index<string_length; index)
for( index=0; index<string_length; index++)
{
  if( (bitmap[string[index] >> 3]) & (1 << (string[index] & 7)) )
    break;
}

<code 4> 는 <code 2>와 완전히 같은 기능을 한다.
그리고, <code 2>보다 더 빠르게 동작한다.
코드만 보더라도 알 수 있다. <code 2>는 최대 string_length X 3 만큼 반복될 수 있으며,
<code 2><code 4>는 최대 3 + string_length 만큼 반복된다.
위와 같이 비트연산을 사용하면 쉽게 빠르게 동작하는 코드를 작성할 수 있다.

<code 4>가 <code 2>보다 빠르게 동작할 수 있는 것은 비트연산에 있다.
bitmap 배열은 char 32개 배열로써 모두 256bits이다.
256bits로 256개의 ASCII code 검사여부를 masking한다.
즉, bitmap[0] 의 두번째 bit가 1이면 ASCII code 1에 해당하는 문자를 문자열에서 찾는다.
'A'를 찾기를 원한다면 ASCII code 0x41(=65) 이므로, bitmap[8]의 두번째 bit에 1을 masking한다.
bitmap[8]의 두번째 bit는 bitmap[0]부터 시작해서 65번째 bit이다.
(계산해 보면 금방 알 수 있다. (8*8)+2 = 66, 0을 포함하여 65번째, 따라서 66번째이다.)
따라서, bitmap 배열에는 아래와 같이 저장이 된다.

bitmap[0]에는 ASCII code 0 부터 ASCII code 7 까지 검사여부를 masking한다.
bitmap[1]에는 ASCII code 8 부터 ASCII code 15 까지 검사여부를 masking한다.
:
:
bitmap[30]에는 ASCII code 240 부터 ASCII code 247 까지 검사여부를 masking한다.
bitmap[31]에는 ASCII code 248 부터 ASCII code 255 까지 검사여부를 masking한다.

그리고, ASCII code 값으로 쉽게 bitmap 배열에서의 위치를 찾고 masking할 수 있다.
여기서 bit 연산자인 shift 연산자와 & 연산자, | 연산자를 사용한다.
ASCII code 값을 8로 나눈 몫은 bitmap의 index가 되고, 8로 나눈 나머지는 bit의 위치가 된다.(이해가 안되시면 위 내용을 천천히 다시 생각 해 보세요.)

그럼, 계산을 해야 하는데 8로 나눈 몫과 나머지를 어떻게 구할 것인가?
/ 연산자와 % 연산자를 사용해서 안된다. 이것은 속도를 떨어뜨린다.
그래서, >> 연산자와 & 연산자를 사용한다.
ASCII code 값을 >>3 을 하면 8로 나눈 몫이 나오고, ASCII code 값을 &0x7 을 하면 8로 나눈 나머지가 나온다.

bitmap[ token[i] >> 3] |= (1 << ( token[i] & 7));

위 코드는  token[i]의 ASCII code 값을 >> 3을 값을 bitmap 배열을 인덱스로 사용하고 token[i]의 ASCII code 값을 & 7 을 해서 위치를 구한 다음에 위치만큼 1을 << 시켜서 bitmap배열에 저장한다.

string에서 문자를 찾을 경우에는

if( (bitmap[string[index] >> 3]) & (1 << (string[index] & 7)) )

위 코드와 같이 bitmap 배열에서 string[index] 문자의 위치(bit의 순서)를 찾아서

bit 1로 masking 되어 있는지를 검사한다.