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과 유사한 것들로 가득 차 있기 때문에 적절히 보이는 대로 정리를 하겠습니다. 일단 argc
와 argv
, 그리고 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))
은 lhs
에 main
번 비트가 설정되면 0이 아니고(정확히는 (1 << main)
) 설정되지 않으면 0이 됩니다. 앞의 !!
는 원래 값이 0이면 0을, 0이 아니면 1을 반환하는 역할을 합니다. 따라서 이 식은 lhs
의 main
번 비트가 설정되면 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)))
는 b
와 c
중 하나일 때만 참이 되므로 XOR이 됩니다. C에는 논리 XOR 연산자는 없지만 b
와 c
가 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);
}
마찬가지로 a
와 bxorc
도 논리 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
라 하면 논리식을 다음과 같이 쓸 수 있습니다.
y
를 직접 정리해 보면 다음과 같음을 알 수 있습니다. (정리를 할 수 없다면 진리표를 만들어서 같은지 확인해 봐도 되겠습니다.)
이것은 전가산기에 해당하는 논리식입니다! 현재 비트 a
와 b
, 그리고 이전 덧셈에서의 올림 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;
}
그야말로 "아는 길도 돌아 가는" 프로그램이라 할 수 밖에 없습니다.