메아리

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 != 0Q != 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는 바뀌지 않고요.

따라서 이 부분의 코드는 다음과 같이 결론지을 수 있습니다. 여기서 Nint의 비트 크기로 보통 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과는 두 칸 어긋나 있습니다.)

처음 루프가 시작되었을 때 lineargc의 값으로 초기화되어 있습니다. argc는 항상 양수이므로 처음에 루프는 항상 시작되고, 나중에 line이 오로지 0 비트만으로 채워져 있을 때, 즉 line이 11000...0002일 때 I는 정확히 0이 되어 루프를 끝내게 됩니다. 굳이 Iline과 두 칸 어긋나 있는 것은 바로 이 경우를 처리하기 위함입니다.

여하튼 코드를 다시 고치겠습니다.

#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가 오버플로우되어 음수가 되었을 때로 이 경우 Qint로 표현 가능한 가장 작은 숫자가 됩니다. 그런데 이 경우 Q의 절대값은 int로 표현 가능한 숫자 중 가장 크니까, line/Q 같은 식은 lineQ와 같지 않으면 항상 0이 됩니다. 그리고 line은 항상 110XXX...XXX2 꼴이므로 Q(= 1000...0002)과 절대 같을 수 없고요. 한편 prev/-Q의 경우, Q == -Q이므로1 prev/Q와 같은 의미인데 prev가 가질 수 있는 최소값은 모든 비트가 설정되었을 때, 즉 100...01002로 역시 Q와 절대 같을 수 없습니다.


  1. 2의 보수 체계에서 -n~n+1과 같은데, n이 100...0002이면 ~n은 011...1112이고 ~n+1은 100...0002로 다시 원래 값으로 돌아와 버립니다. 따라서 n == -nn은 사실 두 개가 있는 것이지요.


Copyright © 1999–2009, Kang Seonghoon.