Tour de IOCCC: 2004/kopczynski
main(O){int I,Q,l=O;if(I=l*4){l=6;if(l>5)l+=Q-8?l-(Q=getchar()-2)%2:l;if(Q*=2)O+="has dirtiest IF"[(I/-Q&12)-l/Q%4];}printf("%d\n",8+O%4);}
이 프로그램은 (코드에서 주장하는 대로) if 문의 사용이 더럽습니다. 더 당황스러운 것은 이 프로그램이 전혀 상상도 못 했던 일을 수행한다는 것입니다.
뭘 하는 프로그램인가?
더러운 if 문에 걸맞게, 이 프로그램은 컴파일할 때도 좀 신경을 써야 합니다. 위의 코드에 나오는 모든 if 문은 사실 전처리기로 치환된 while 문입니다.
$ gcc -Dif=while kopczynski.c -o kopczynski
이제 컴파일된 프로그램을 테스트해 봅시다. 이 프로그램의 예제 입력으로 kopczynski-8a 같은 파일이 나와 있는데 이걸 한 번 넣어 보겠습니다.
$ ./kopczynski < kopczynski-8a
8
오? 다른 것도 넣어 봅시다. 이번에는 kopczynski-10을 넣어 보죠.
$ ./kopczynski < kopczynski-10
10
왠지 무슨 일을 하는지 감이 잡히죠? 확실히 하기 위해 우리가 직접 데이터를 만들어 넣어 보겠습니다.
$ ./kopczynski
### ##
#### ######
##### ### ####
## ## ## ###
## ## ## ###
## ### ## ##
## ## ##
## ## ##
# #######
## ####
#######
#######
^D
10
(^D
는 한 글자, Ctrl-D로 입력해야 합니다. 마지막 10은 프로그램의 출력입니다.) 예측한 대로 이 프로그램은 8, 9, 10, 11이 그려진 그림을 읽어서 해당하는 숫자를 알려 줍니다. 일종의 OCR인 셈이지요.
입력될 그림에는 약간의 제한이 있는데, 그려진 숫자가 서로 연결이 되어 있지 않아야 하며 #
가 없는 줄이 있어서는 안 되고, 한 줄이 23글자를 넘을 수 없습니다. (제가 그린 그림은 한 줄에 22글자가 최고입니다.) 이 조건만 지키면 이 프로그램은 매우 안정적으로 8, 9, 10, 11을 구별해 냅니다. 8, 9, 10, 11이 아닌 그림이 들어 오면 아무 값이나 출력하는 것 같아 보이지만, 사실 여기에는 좀 더 복잡한 얘기가 숨어 있습니다...
어떻게 동작하는가?
지금까지 수많은 한 줄짜리 프로그램을 분석해 왔기 때문에 굳이 길게 설명하지 않고 빠르게 진행하겠습니다. (이 프로그램은 코드보다 알고리즘을 설명하는 게 더 어렵습니다.) 먼저 모든 if 문은 사실 while 문이라고 했으니까 모두 치환하고, 적절히 들여쓰기를 넣습니다.
main(O) {
int I, Q, l = O;
while (I = l*4) {
l = 6;
while (l > 5)
l += Q-8 ? l - (Q=getchar()-2) % 2 : l;
while (Q *= 2)
O += "has dirtiest IF"[(I/-Q & 12) - l/Q % 4];
}
printf("%d\n", 8 + O%4);
}
main 함수의 인자 O
는 원래 argc
입니다. 또한 if 문을 피하기 위해서 사용한 삼항 연산자로 다시 if 문으로 돌려 놓겠습니다.
int main(int argc, char **argv) {
int I, Q, l = argc;
while (I = l*4) {
l = 6;
while (l > 5) {
if (Q-8) {
l += l - (Q=getchar()-2) % 2;
} else {
l += l;
}
}
while (Q *= 2)
argc += "has dirtiest IF"[(I/-Q & 12) - l/Q % 4];
}
printf("%d\n", 8 + argc%4);
return 0;
}
모든 while/if 조건문에 비교 연산자가 들어 가도록 고치고, l += l - ...;
과 같은 문장을 풀어 씁니다.
int main(int argc, char **argv) {
int I, Q, l = argc;
while ((I = l*4) != 0) {
l = 6;
while (l > 5) {
if (Q-8 != 0) {
l = l * 2 - (Q=getchar()-2) % 2;
} else {
l = l * 2;
}
}
while ((Q *= 2) != 0)
argc += "has dirtiest IF"[(I/-Q & 12) - l/Q % 4];
}
printf("%d\n", 8 + argc%4);
return 0;
}
공통된 코드(l = l * 2
보이시죠?)를 정리하고, 조건의 Q-8 != 0
은 Q != 8
과 같으므로 고칩니다.
int main(int argc, char **argv) {
int I, Q, l = argc;
while ((I = l*4) != 0) {
l = 6;
while (l > 5) {
int b = 0;
if (Q != 8) b = (Q=getchar()-2) % 2;
l = l * 2 - b;
}
while ((Q *= 2) != 0)
argc += "has dirtiest IF"[(I/-Q & 12) - l/Q % 4];
}
printf("%d\n", 8 + argc%4);
return 0;
}
while (l > 5)
부분만 떼어서 살펴 봅시다. l
은 처음에 6으로 설정되고, 안의 조건문에 따라 l = l*2 - 1;
또는 l = l*2;
둘 중 하나가 실행됩니다. 그런데 while 문의 조건은 l
이 6보다 작을 때 끝난다고 되어 있습니다. 분명 l
은 6부터 시작해서 계속 증가하는데? 그럼 이 while 문이 종료되는 방법은 l
이 오버플로우되어서 음수가 되는 방법 밖에 없습니다.
설명을 편하게 하기 위해서 int
가 8비트라고 하겠습니다. l
은 처음에 000001102이고, b
가 순서대로 1, 0, 1, 1이 입력되었다고 하면 000010112, 000101102, 001010112, 010101012로 변합니다. 여기까지는 l
이 양수니까 while 문이 끝날 수 없죠. 이제 그 다음에 0이 입력되면 l
은 101010102가 되는데, 최상위 비트가 설정되어 있으므로 이 값은 음수고 루프는 종료됩니다. (자세한 것은 2의 보수를 참고하세요.)
들어 오는 비트는 (Q=getchar()-2) % 2
로 결정되는데, 만약 #
(ASCII 35)이 입력되었다면 Q
는 35-2 = 33이 되고 b
는 1이 됩니다. 한편 공백(ASCII 32)이 입력되었다면 Q
는 32-2 = 30이 되고 b
는 0이 되죠. 개행 문자(ASCII 10)면 어떨까요? Q
는 10-2 = 8이 되고 b
는 0이 되는데, 흥미롭게도 Q
값은 바로 조건문에서 체크하는 그 값과 같습니다. 즉, 루프를 돌다가 개행 문자를 만나면 더 이상 getchar는 실행되지 않고 b
는 0으로 고정된다는 뜻이지요. 물론 Q
는 바뀌지 않고요.
따라서 이 부분의 코드는 다음과 같이 결론지을 수 있습니다. 여기서 N
은 int
의 비트 크기로 보통 32거나 64입니다.
이 코드는 다음 개행 문자가 나올 때까지 문자를 읽어 들인다.
#
와 같이 ASCII 코드가 홀수인 문자는 1로 처리되고, 아닌 문자(공백 등)는 0으로 처리된다. 루프가 끝난 뒤l
은 110XXX...XXX2가 되고, 개행문자 뒷쪽은 공백으로 처리한다.Q
는 8로 설정된다.
물론 위의 문장은 한 줄에 개행문자 포함 N-3
개를 넘는 문자가 있으면 성립하지 않지만, 애초에 저자가 한 줄에 N-9
개 넘는 문자가 있으면 동작하지 않는다고 했으니 신경쓰지 않도록 합시다. (예를 들어 이런 경우 Q
가 8이 아니게 되는데, 그러면 뒤의 루프는 의도한 대로 동작하지 않게 됩니다.)
해석된 코드를 좀 더 알아 보기 쉽게 풀어 써 놓겠습니다. Q
는 두 루프에서 다른 역할을 하니까 변수를 서로 독립시키도록 하죠.
#include <limits.h>
#include <assert.h>
#define N (sizeof(int) * CHAR_BIT) /* int의 비트 크기 */
int main(int argc, char **argv) {
int I, Q;
int ch; /* 원래 Q였음. */
int line = argc; /* 원래 l이었음 */
while ((I = line*4) != 0) {
int i;
line = 6;
/* 최대 N-3개의 문자를 읽는다. 개행 문자가 나오면 일찍 끝난다. */
for (i = 0; i < N - 3; ++i) {
ch = getchar() - 2;
if (ch == '\n' - 2) break;
line = line * 2 - ch % 2;
}
/* 일찍 끝났다면 나머지 문자는 공백으로 가정한다. */
for (; i < N - 3; ++i) {
line = line * 2;
}
assert(ch == '\n' - 2);
Q = 8;
while ((Q *= 2) != 0)
argc += "has dirtiest IF"[(I/-Q & 12) - line/Q % 4];
}
printf("%d\n", 8 + argc%4);
return 0;
}
이제 그 다음 while 문을 봅시다. Q
가 원래 8이었으므로, 정확히 N-4
번 루프를 실행하면 이 코드는 종료되겠죠.
#include <limits.h>
#include <assert.h>
#define N (sizeof(int) * CHAR_BIT)
int main(int argc, char **argv) {
int I, Q;
int ch;
int line = argc;
while ((I = line*4) != 0) {
int i;
line = 6;
for (i = 0; i < N - 3; ++i) {
ch = getchar() - 2;
if (ch == '\n' - 2) break;
line = line * 2 - ch % 2;
}
for (; i < N - 3; ++i) {
line = line * 2;
}
assert(ch == '\n' - 2);
Q = 8;
for (i = 0; i < N - 4; ++i) {
Q *= 2;
argc += "has dirtiest IF"[(I/-Q & 12) - line/Q % 4];
}
}
printf("%d\n", 8 + argc%4);
return 0;
}
그 다음으로 보이는 변수는 I
인데, 이 변수는 첫 while 문의 시작에서 I = line * 4
라고 선언되어 있습니다. 바깥 루프가 매 줄마다 반복되는 걸 생각하면 I
는 이전 줄의 정보를 담고 있는 셈이겠네요. (다만, 4로 곱했으므로 나중에 읽을 line
과는 두 칸 어긋나 있습니다.)
처음 루프가 시작되었을 때 line
은 argc
의 값으로 초기화되어 있습니다. argc
는 항상 양수이므로 처음에 루프는 항상 시작되고, 나중에 line
이 오로지 0 비트만으로 채워져 있을 때, 즉 line
이 11000...0002일 때 I
는 정확히 0이 되어 루프를 끝내게 됩니다. 굳이 I
가 line
과 두 칸 어긋나 있는 것은 바로 이 경우를 처리하기 위함입니다.
여하튼 코드를 다시 고치겠습니다.
#include <limits.h>
#include <assert.h>
#define N (sizeof(int) * CHAR_BIT)
int main(int argc, char **argv) {
int Q;
int ch;
int line = argc;
int prev; /* 원래 I였음 */
while (1) {
int i;
/* 이전 줄이 공백으로만 채워져 있으면 종료한다. */
prev = line * 4;
if (prev == 0) break;
line = 6;
for (i = 0; i < N - 3; ++i) {
ch = getchar() - 2;
if (ch == '\n' - 2) break;
line = line * 2 - ch % 2;
}
for (; i < N - 3; ++i) {
line = line * 2;
}
assert(ch == '\n' - 2);
Q = 8;
for (i = 0; i < N - 4; ++i) {
Q *= 2;
argc += "has dirtiest IF"[(prev/-Q & 12) - line/Q % 4];
}
}
printf("%d\n", 8 + argc%4);
return 0;
}
이제 가장 골때리는 코드가 남았습니다. 아래 코드에서 /
와 &
의 미묘한 우선순위에 속아 넘어 가면 안 됩니다. (C/C++에서는 비트 연산자가 산술 연산자보다 늦게 결합합니다. 사실 비트 연산자는 대략 논리 연산자와 비슷한 시점, 즉 매우 한참 뒤에 결합합니다.)
Q = 8;
for (i = 0; i < N - 4; ++i) {
Q *= 2;
argc += "has dirtiest IF"[(prev/-Q & 12) - line/Q % 4];
}
나눗셈과 비트 연산자들이 섞여 있으니 헷갈리군요. 일단 Q
는 거의 항상 2의 거듭제곱이므로 시프트 연산으로 고칠 수 있습니다. (prev/-Q
같은 건 -prev/Q
와 같겠고요.) 시프트 연산과 나눗셈이 다르게 동작할 때는 음수일 경우인데, 나눗셈은 항상 절대값을 기준으로 동작하기 때문에 시프트 연산의 피연산자가 음수라면 a>>b
대신에 -((-a)>>b)
식으로 써 줄 필요가 있긴 합니다.
여기까진 좋은데 Q
가 2의 거듭제곱이 아닌 경우가 단 하나 있으니, 맨 마지막에 Q
가 오버플로우되어 음수가 되었을 때로 이 경우 Q
는 int
로 표현 가능한 가장 작은 숫자가 됩니다. 그런데 이 경우 Q
의 절대값은 int
로 표현 가능한 숫자 중 가장 크니까, line/Q
같은 식은 line
이 Q
와 같지 않으면 항상 0이 됩니다. 그리고 line
은 항상 110XXX...XXX2 꼴이므로 Q
(= 1000...0002)과 절대 같을 수 없고요. 한편 prev/-Q
의 경우, Q == -Q
이므로1 prev/Q
와 같은 의미인데 prev
가 가질 수 있는 최소값은 모든 비트가 설정되었을 때, 즉 100...01002로 역시 Q
와 절대 같을 수 없습니다.
2의 보수 체계에서
-n
은~n+1
과 같은데,n
이 100...0002이면~n
은 011...1112이고~n+1
은 100...0002로 다시 원래 값으로 돌아와 버립니다. 따라서n == -n
인n
은 사실 두 개가 있는 것이지요. ↩