메아리

Tour de IOCCC: 1995/heathbar

#                                                              include <stdio.h>
#                                                define     MAin   printf("%d\n"
#                                                define     mAIN        return 0
#                                                define     MaiN         {static
#                                                define     mAlN          ) {if(
#                                                define     MA1N           char*
#                                                define     MAiN            (!!(
#                                                define     mAiN            atoi
#                                                define     mAln            &1<<
#                                                define     MAlN            !=3)
#                                                define     MAln             )&&
#                                                define     MAIN             int
#                                                define     maln             --,
#                                                define     Maln              <<
#                                                define     MaIn              ++
#                                                define     MalN              |=
#                                                define     MA1n              ||
#                                                define     malN              -1
#                                                define     maIN               *
#                                                define     MaIN               =
#                                                define     ma1N               )
#                                                define     Ma1N               (
#                                                define     Main               ;
#                                                define     mA1n               !
#                                                define     MAIn               }
#                                                define     mA1N               ,
                                                  MAIN      mAIn
                                                  Ma1N      MAIN
                                                  ma1N      mA1N
                                                  mAiN      Ma1N
                    MA1N ma1N mA1N maIn MaIN malN mA1N      ma1n
                    mA1N                          maiN      Main 
                    MAIN      main Ma1N MAIN Ma1n mA1N MA1N maIN
                    mAin      mAlN                Ma1n      MAlN
                    mAIN      Main                maIn      MaIn
               mA1N Ma1n maln mAin MaIn           Main      maIn
               MaIN                mAiN           Ma1N      Ma1N
               Ma1n                maln           maIN      mAin
               MaIn                ma1N           ma1N      Main
               ma1n                MaIN           mAiN      Ma1N
               Ma1N                Ma1n           maln      maIN
               mAin                MaIn           ma1N      ma1N
               Main                mAIn           Ma1N      mAIn
               Ma1N                mAIn           Ma1N      mAIn
               Ma1N                mAIn      Ma1N mAIn      Ma1N mAIn
                Ma1N              mAIn       Ma1N mAIn      Ma1N mAIn
                  Ma1N          mAIn         Ma1N   mAIn  Ma1N   mAIn
                    Ma1N mAIn Ma1N           mAIn      Ma1N      mAIn
                         Ma1N                Ma1n                ma1N
                         ma1N                ma1N                ma1N
          ma1N ma1N ma1N ma1N                ma1N                ma1N
          ma1N           ma1N                ma1N                ma1N
          ma1N           ma1N                Main                MAin
          mA1N maiN ma1N Main mAIN Main      MAIn                MAIN
          mAIn  Ma1N              MAIN       mAin                ma1N
          MaiN   MAIN            main          MaIN            malN
          Main    main          MaIn             Main        mAIN
          mA1N     maiN        MalN                Ma1N    MAiN
          maIn      mAln      main                     ma1N
          MA1n       Ma1N    MAiN                      ma1n
          mAln        main  ma1N                       MA1n
          mAin           MAln                          Ma1N
          mA1n        MAiN  ma1n                       mAln
          main        MAln  mAin                       ma1N
          ma1N           ma1N      MAln Ma1N mA1n MAiN maIn
          mAln           main      MAln
          Ma1N           MAiN      ma1n
          mAln      main ma1N MA1n mAin MAln
          Ma1N      mA1n                MAiN
          ma1n      mAln                main
          MAln      mAin                ma1N
          ma1N      ma1N                ma1N
          ma1N      ma1N                Maln
          main      mA1N                MAiN
          ma1n      mAln                main
          MAln      mAin                ma1N
          MA1n      MAiN                maIn
          mAln       main              MAln
          Ma1N         MAiN          ma1n
          mAln           main ma1N MA1n
          mAin                MAln
          Ma1N                mA1n
          MAiN                ma1n
          mAln                main
          MAln                mAin
          ma1N                ma1N
          ma1N                ma1N
          Main                MAIn

이 프로그램이 하는 일은 자명합니다. 두 숫자를 더하는 것이죠. 코드 모양이 자기 스스로 말하고 있지 않습니까! (코드 모양은 덧셈을 구현하는 데 쓰이는 반가산기의 회로입니다.)

뭘 하는 프로그램인가?

소스 코드가 자기 자신을 설명하는 코드는 굳이 컴파일을 안 해 봐도 결과가 뻔합니다만, 그래도 전통에 따라 컴파일을 해 보겠습니다.

$ gcc heathbar.c -o heathbar
$ ./heathbar 1 2
3

좀 더 큰 수를 넣어 볼까요?

$ ./heathbar 421 597
1018
$ ./heathbar 19518 43406
62924
$ ./heathbar 32768 32768
0
$ ./heathbar 65535 43
42

오호라, 내부적으로 16비트로 구현된 것 같군요. 음수를 넣어 보면 어떨까요?

$ ./heathbar -1 43
42
$ ./heathbar 11724 -1724
10000

잘 동작하는군요. 따라서 이 코드는 두 숫자를 부호 없는 16비트 정수로 변환한 뒤 더하는 프로그램임을 알 수 있습니다.

어떻게 동작하는가?

멋진 모양이 아깝긴 하지만 구조를 알아 보기 위해 전처리기를 돌려 보겠습니다. 다음은 전처리기를 돌린 뒤 정리한 코드입니다.

#include <stdio.h>

int mAIn(int), atoi(char *), maIn = -1, ma1n, maiN;

int main(int Ma1n, char **mAin) {
    if (Ma1n != 3)
        return 0;

    maIn++, Ma1n--, mAin++;
    maIn = atoi((Ma1n--, *mAin++));
    ma1n = atoi((Ma1n--, *mAin++));

    mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(
        mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(Ma1n))))))))))))))));

    printf("%d\n", maiN);
    return 0;
}

int mAIn(int mAin) {
    static int main = -1;
    main++;
    return 0,
        maiN |= (
             (!!(maIn & 1 << main) ||
              ((!!(ma1n & 1 << main) || mAin) &&
               (!(!!(ma1n & 1 << main) && mAin))
              )
             ) &&
             (!(!!(maIn & 1 << main) &&
                ((!!(ma1n & 1 << main) || mAin) &&
                 (!(!!(ma1n & 1 << main) && mAin))
                )
               )
             )
            ) << main,
        (!!(ma1n & 1 << main) && mAin) ||
        (!!(maIn & 1 << main) &&
         ((!!(ma1n & 1 << main) || mAin) &&
          (!(!!(ma1n & 1 << main) && mAin))));
}

변수 이름도 main과 유사한 것들로 가득 차 있기 때문에 적절히 보이는 대로 정리를 하겠습니다. 일단 argcargv, 그리고 atoi의 출력으로 나오는 값이 무엇인 지는 자명하죠.

#include <stdio.h>

int mAIn(int), atoi(char *), lhs = -1, rhs, maiN;

int main(int argc, char **argv) {
    if (argc != 3)
        return 0;

    lhs++, argc--, argv++;
    lhs = atoi((argc--, *argv++));
    rhs = atoi((argc--, *argv++));

    mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(
        mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(mAIn(argc))))))))))))))));

    printf("%d\n", maiN);
    return 0;
}

int mAIn(int mAin) {
    static int main = -1;
    main++;
    return 0,
        maiN |= (
             (!!(lhs & 1 << main) ||
              ((!!(rhs & 1 << main) || mAin) &&
               (!(!!(rhs & 1 << main) && mAin))
              )
             ) &&
             (!(!!(lhs & 1 << main) &&
                ((!!(rhs & 1 << main) || mAin) &&
                 (!(!!(rhs & 1 << main) && mAin))
                )
               )
             )
            ) << main,
        (!!(rhs & 1 << main) && mAin) ||
        (!!(lhs & 1 << main) &&
         ((!!(rhs & 1 << main) || mAin) &&
          (!(!!(rhs & 1 << main) && mAin))));
}

mAIn 함수에는 !!(lhs & 1 << main)와 같은 꼴의 코드가 매우 많이 등장합니다. 여기서 !!((lhs & 1) << main)이라고 생각하고 왜 main으로 왼쪽 시프트를 하는 건지 궁금해 하면 안 됩니다. &&& 바로 직전에 결합할 정도로 우선순위가 낮기 때문에 !!(lhs & (1 << main))으로 해석해야 합니다.

(lhs & (1 << main))lhsmain번 비트가 설정되면 0이 아니고(정확히는 (1 << main)) 설정되지 않으면 0이 됩니다. 앞의 !!는 원래 값이 0이면 0을, 0이 아니면 1을 반환하는 역할을 합니다. 따라서 이 식은 lhsmain번 비트가 설정되면 1, 설정되지 않으면 0을 반환하게 됩니다. 의미를 알았으니 매크로로 적절히 치환해 보도록 하겠습니다.

#define ISSET(x,n) !!(x & (1 << n))

int mAIn(int mAin) {
    static int main = -1;
    main++;
    return 0,
        maiN |= (
             (ISSET(lhs,main) ||
              ((ISSET(rhs,main) || mAin) &&
               (!(ISSET(rhs,main) && mAin))
              )
             ) &&
             (!(ISSET(lhs,main) &&
                ((ISSET(rhs,main) || mAin) &&
                 (!(ISSET(rhs,main) && mAin))
                )
               )
             )
            ) << main,
        (ISSET(rhs,main) && mAin) ||
        (ISSET(lhs,main) &&
         ((ISSET(rhs,main) || mAin) &&
          (!(ISSET(rhs,main) && mAin))));
}

ISSET(lhs,main)ISSET(rhs,main)은 많이 중복되므로 바깥으로 빼 내고, mAin 변수도 거기에 맞춰서 이름을 간단하게 바꾸도록 하겠습니다.

#define ISSET(x,n) !!(x & (1 << n))

int mAIn(int c) {
    static int main = -1;
    int a, b;

    main++;

    a = ISSET(lhs,main);
    b = ISSET(rhs,main);
    return 0,
        maiN |= ((a || ((b || c) && (!(b && c)))) &&
             (!(a && ((b || c) && (!(b && c)))))
            ) << main,
        (b && c) || (a && ((b || c) && (!(b && c))));
}

정리를 하고 나니 중복되는 게 바로 눈에 띄이네요. 일단 ((b || c) && (!(b && c)))bc 중 하나일 때만 참이 되므로 XOR이 됩니다. C에는 논리 XOR 연산자는 없지만 bc가 0 아니면 1인 게 확실하면 비트 연산자 ^로 대신할 수 있습니다. 어떤 식을 0 아니면 1로 변환할 때는 앞에서 설명했을 때 !!를 쓰면 되니, 이 식은 !!b ^ !!c라고 간단히 나타낼 수 있습니다. 편의상 이 식을 bxorc라는 변수로 분리하겠습니다.

#define ISSET(x,n) !!(x & (1 << n))

int mAIn(int c) {
    static int main = -1;
    int a, b, bxorc;

    main++;

    a = ISSET(lhs,main);
    b = ISSET(rhs,main);
    bxorc = !!b ^ !!c;
    return 0,
        maiN |= ((a || bxorc) && (!(a && bxorc))) << main,
        (b && c) || (a && bxorc);
}

마찬가지로 abxorc도 논리 XOR로 고칠 수 있는 부분이 있군요.

#define ISSET(x,n) !!(x & (1 << n))

int mAIn(int c) {
    static int main = -1;
    int a, b, bxorc;

    main++;

    a = ISSET(lhs,main);
    b = ISSET(rhs,main);
    bxorc = !!b ^ !!c;
    return 0,
        maiN |= (!!a ^ !!bxorc) << main,
        (b && c) || (a && bxorc);
}

이제 mAIn 함수가 하는 일을 정리해 봅시다. 한 가지는 maiN 함수의 main번 비트를 설정하는 것이고, 다른 하나는 적절한(?) 값을 반환하는 것이지요. 전자를 x, 후자를 y라 하면 논리식을 다음과 같이 쓸 수 있습니다.

x = a \oplus b \oplus c \\ y = b \cdot c + a \cdot (b \oplus c)

y를 직접 정리해 보면 다음과 같음을 알 수 있습니다. (정리를 할 수 없다면 진리표를 만들어서 같은지 확인해 봐도 되겠습니다.)

x = a \oplus b \oplus c \\ y = a \cdot b + b \cdot c + c \cdot a

이것은 전가산기에 해당하는 논리식입니다! 현재 비트 ab, 그리고 이전 덧셈에서의 올림 c(첫 비트에서는 0)이 주어질 때, 이 논리식은 세 비트를 더해서 새 올림 y와 새 비트 x를 만들어 냅니다. 과연 자기 자신을 설명하는 코드군요.

mAIn 함수는 main 함수에서 16번 호출됩니다. 그 동안 정적 변수인 main(함수와는 다릅니다!)는 0, 1, 2, ..., 15로 증가하고, 반환된 올림 값은 그 다음 호출의 인자로 연결되어 전달됩니다. 따라서 이 코드는 결과적으로 다음과 같이 정리할 수 있겠습니다.

#define ISSET(x,n) !!(x & (1 << n))

int mAIn(int carry) {
    static int count = 0;
    int a = ISSET(lhs, count), b = ISSET(rhs, count);

    maiN |= (!!a ^ !!b ^ !!carry) << count; /* count번 비트를 설정 */
    carry = (a & b) | (b & c) | (c & a); /* 다음 올림 */
    ++count;

    return carry;
}

이 함수를 원래 코드에 합치고 이름을 바꾸면,

#include <stdio.h>

int adder(int), atoi(char *), lhs = -1, rhs, result;

int main(int argc, char **argv) {
    if (argc != 3)
        return 0;

    lhs--, argc--, argv++;
    lhs = atoi((argc--, *argv++));
    rhs = atoi((argc--, *argv++));

    adder(adder(adder(adder(
        adder(adder(adder(adder(
            adder(adder(adder(adder(
                adder(adder(adder(adder(argc))))))))))))))));

    printf("%d\n", result);
    return 0;
}

#define ISSET(x,n) !!(x & (1 << n))

int adder(int carry) {
    static int count = 0;
    int a = ISSET(lhs, count), b = ISSET(rhs, count);

    result |= (!!a ^ !!b ^ !!carry) << count; /* count번 비트를 설정 */
    carry = (a & b) | (b & c) | (c & a); /* 다음 올림 */
    ++count;

    return carry;
}

main의 코드는 어렵지 않습니다만 이것도 정리하면 다음과 같습니다.

#include <stdio.h>

int adder(int), atoi(char *), lhs = -1, rhs, result;

int main(int argc, char **argv) {
    if (argc != 3)
        return 0;

    lhs = atoi(argv[1]);
    rhs = atoi(argv[2]);
    argc -= 3; /* 결과적으로 0이 됨 */
    argv += 3; /* 실제로 쓰이지는 않음 */

    adder(adder(adder(adder(
        adder(adder(adder(adder(
            adder(adder(adder(adder(
                adder(adder(adder(adder(argc))))))))))))))));

    printf("%d\n", result);
    return 0;
}

#define ISSET(x,n) !!(x & (1 << n))

int adder(int carry) {
    static int count = 0;
    int a = ISSET(lhs, count), b = ISSET(rhs, count);

    result |= (!!a ^ !!b ^ !!carry) << count; /* count번 비트를 설정 */
    carry = (a & b) | (b & c) | (c & a); /* 다음 올림 */
    ++count;

    return carry;
}

따라서 최초의 올림값은 0임을 확신할 수 있습니다. adder가 하는 일도 다 알고 있으니 모두 정리하면 다음과 같이 되겠지요.

#include <stdio.h>

int lhs, rhs, result;

int main(int argc, char **argv) {
    if (argc != 3) return 0;

    lhs = atoi(argv[1]);
    rhs = atoi(argv[2]);
    result = (lhs + rhs) & 0xffff;
    printf("%d\n", result);

    return 0;
}

그야말로 "아는 길도 돌아 가는" 프로그램이라 할 수 밖에 없습니다.


Copyright © 1999–2009, Kang Seonghoon.