Но что, если провести конкурс, в котором критерий хорошести кода будет перевернут? Читаемость и понятность со знаком минус. Именно с такими мыслями Leonid A. Broukhis, Simon Cooper и Landon Curt Noll провели первый конкурс IOCCC (International Obfuscated C Code Contest) в 1984м году. Цель конкурса создать самый запутанный и непонятный код, удивить судей нестандартными способами скрытия истинной работы кода или же просто показать способы программирования, которые, на первый взгляд, кажутся мешаниной из знаков, чисел и пробелов.
Более подробно про критерии, задачи и победителей можно прочитать на сайте конкурса: www.ioccc.org
Несмотря на то, что меня пугала перспектива сразиться с программистами, некоторые из которых могут писать четырехступенчатые квайны, вывод которых отформатирован в виде лица персонажа и иероглифов имени или вывести свой собственный sha-512 хэш, я всё же решил поучаствовать в 27м конкурсе IOCCC.
Что из этого вышло, я бы хотел рассказать в статье из двух частей. Так как каждый участник может отправить не более 8.000000 работ я решил ограничиться двумя (умерший HDD из-за которого всё пришлось делать с нуля повторно этому поспособствовал). Цикл статей состоит из двух частей (от простого к сложному):
- Как я участвовал в IOCCC-'19 (и проиграл). Часть 1: Крестики-нолики
- Как я участвовал в IOCCC-'19 (и проиграл). Часть 2: Симулятор NOR
От автора
Есть ли сожаления, что победа досталась кому-то другому? В общем нет. Я особо надеялся на свою вторую работу (из части 2) и на номинацию Самая запутанная программа для X11, но в этом году этой номинации не было. Что ж, это повод попытаться в следующем году придумать что-то посложнее.
Исходный код
Несмотря на то, что Крестики-нолики была моей второй работой, она проще, а следовательно лучше начать цикл статей с нее. По сравнению с другими работами других авторов она достаточно слабая, но позволяет уловить часть приемов для облегчения рассмотрения второй части.
Для начала, сам код работы:
prog.c (Т от английского названия игры (Tic-Tac-Toe):
void move(void) {/* now make your move with 'p set(x, y)', then 'c' */};const double aaa = 1.40812272124156708779e-308;const double aaA = 1.63732567860768633471e-306;const double aAa = 5.81846600316580299542e+180;const double aAA = 6.13331437392687289128e-154;const double Aaa = 6.01393815945279298101e-154;const double AaA = 6.01347195647080563440e-154;const double AAa = 7.87488138007920286678e+276;const double AAA = 1.28060532144786065112e-152; extern long int syscall(long int,...);unsigned w[]={1409286144,344064,84,588692+1073415340,268501008,67125252,1073807364,67174464,0}; char s[32]={0};int p=0, v;void O( char*s){while( syscall( P, 1, s++,1),v--); } char *f(double g){static double G;G=g;return(char* ) &G; }void o( double g){v=8;O(f(g));v=8;O(f(aaa )) ;syscall(E,0) ;} voidset(int x,int y){if(p)o(aaA);if(x<0||y<0||x>2||y>2||s[(y*2 )*6+x*2]!=32)o (aAa);s[(y*2 )*6+x*2]=88;p= 1; v= 31; O( s);}inta( char x , char y ) {return(s[(y*2 )*6+x*2]!=32 )?0:(s[(y*2)*6 +x*2] =79);} int i(){return a(1,1)||a(0, 0)||a(1,2)||a( 2,1)||a(0,2) ||a(2,0)||a(1, 0)||a(2,2)|| a(0,1);}void c (){ unsigned * W =w;char*_= s;unsigned l =0,I=0;while(* _){l|=*_==88 ;I|= *_==79; l <<=1;I <<=1; _++ ; }while(* W){if((l&*W) ==*W)o(aAA);if ((I&*W)==*W) o(Aaa);W++;}if ((l|I)==159+ 899685+899712+ 1407830736)o ( AaA ); } int main(void){v = 15+15;while( v--){s[v]=32;s [v]=(v%2)==1?124:s[v];s[v]=(v/6%2)==1?45:s[v];s[v]=((v%2)==1)&&((v/6%2)==1)?43:s[v];s[v]=(v%6)==5?10:s[v];}if(syscall(T,0,0,0,0)!=-1)o(AAa);while(1){i();v=31;O(s);c(); move ();if(!p)o(AAA ) ;p=0;c(); }return 0;}
Makefile:
#!/usr/bin/env makePROJECT= progCC= gccSRC= prog.cCWARN= -Wall -Wextra -Wno-misleading-indentationCSTD= -std=c99BITS := $(shell uname -p)ifeq ($(BITS), x86_64) ARCH= -m64 # write # ptrace # exit CDEFINE= -DP=1 -DT=101 -DE=60else ARCH= -m32 # write # ptrace # exit CDEFINE= -DP=4 -DT=26 -DE=1endifOPT= -gCFLAGS= ${CWARN} ${CSTD} ${ARCH} ${CDEFINE} ${OPT}LDFLAGS= -ldlRM= rmall: ${PROJECT}${PROJECT}:${CC} ${CFLAGS} ${SRC} -o $@ ${LDFLAGS}clean:${RM} -f ${PROJECT}
Сборка:
make
Для удобства исходный код можно взять из github репозитория.
Обращение к читателю
На этом месте я бы хотел обратиться к тем, кто достаточно хорошо знает язык Си. Если у вас есть желание отложите статью в сторону до вечера или выходных и постарайтесь в свободное время понять, как именно работает программа, поупражнявшись таким образом в чтении запутанного кода.
Тех же, кто хочет сразу рассмотреть решение прошу читать дальше.
Как играть
Так как код всё же должен выполнять свою работу (и, желательно, каким-нибудь извращенным методом), то попробуем в него поиграть. Для этого нужно запустить программу под отладчиком и установить точку останова на нужную функцию:
$ gdb ./prog GNU gdb (Ubuntu 8.1-0ubuntu3.2) 8.1.0.20180409-git<...>Reading symbols from ./prog...done.(gdb) b moveBreakpoint 1 at 0x64e: file prog.c, line 1.
Теперь запустим программу:
(gdb) rStarting program: /home/alex/development/c/ioccc/tic/prog | | -+-+- |O| -+-+- | | Breakpoint 1, move () at prog.c:11void move(void) {/* now make your move with 'p set(x, y)', then 'c' */};(gdb)
Нам нарисовали поле и попросили указать координаты, по которым мы хотим нарисовать крестик (противник сделал свой ход ноликами). Сделаем ход так, как нас просят на экране и продолжим выполнение программы:
(gdb) p set(0, 0)X| | -+-+- |O| -+-+- | | $1 = void(gdb) cContinuing.X| | -+-+- |O| -+-+- |O| Breakpoint 1, move () at prog.c:11void move(void) {/* now make your move with 'p set(x, y)', then 'c' */};
Продолжим игру:
(gdb) p set(1, 0)X|X| -+-+- |O| -+-+- |O| $2 = void(gdb) cContinuing.X|X| -+-+- |O|O-+-+- |O| Breakpoint 1, move () at prog.c:11void move(void) {/* now make your move with 'p set(x, y)', then 'c' */};(gdb) p set(2,0)X|X|X-+-+- |O|O-+-+- |O| $3 = void(gdb) cContinuing.winner [Inferior 1 (process 2785) exited normally]
Что ж, это было не трудно (в конце концов никто не обещал сложные машинные алгоритмы).
В игре также присутствует проверка на нечестный поступок (ход игроком два раза подряд), ход в несуществующую ячейку и пропуск хода. В случае же запуска программы без отладчика она завершится с сообщением gdb only.
Как это работает
Пришло время взять скальпель и препарировать пациента.
Для удобства читаемости прогоним программу через indent (мне нравятся опции -kr -brf):
void move(void) { /* now make your move with 'p set(x, y)', then 'c' */};const double aaa = 1.40812272124156708779e-308;const double aaA = 1.63732567860768633471e-306;const double aAa = 5.81846600316580299542e+180;const double aAA = 6.13331437392687289128e-154;const double Aaa = 6.01393815945279298101e-154;const double AaA = 6.01347195647080563440e-154;const double AAa = 7.87488138007920286678e+276;const double AAA = 1.28060532144786065112e-152;extern long int syscall(long int, ...);unsigned w[] = { 1409286144, 344064, 84, 588692 + 1073415340, 268501008, 67125252, 1073807364, 67174464, 0};char s[32] = { 0 };int p = 0, v;void O(char *s) { while (syscall(P, 1, s++, 1), v--);}char *f(double g) { static double G; G = g; return (char *) &G;}void o(double g) { v = 8; O(f(g)); v = 8; O(f(aaa)); syscall(E, 0);} void set(int x, int y) { if (p) o(aaA); if (x < 0 || y < 0 || x > 2 || y > 2 || s[(y * 2) * 6 + x * 2] != 32) o(aAa); s[(y * 2) * 6 + x * 2] = 88; p = 1; v = 31; O(s);}int a(char x, char y) { return (s[(y * 2) * 6 + x * 2] != 32) ? 0 : (s[(y * 2) * 6 + x * 2] = 79);}int i() { return a(1, 1) || a(0, 0) || a(1, 2) || a(2, 1) || a(0, 2) || a(2, 0) || a(1, 0) || a(2, 2) || a(0, 1);}void c() { unsigned *W = w; char *_ = s; unsigned l = 0, I = 0; while (*_) { l |= *_ == 88; I |= *_ == 79; l <<= 1; I <<= 1; _++; } while (*W) { if ((l & *W) == *W) o(aAA); if ((I & *W) == *W) o(Aaa); W++; } if ((l | I) == 159 + 899685 + 899712 + 1407830736) o(AaA);}int main(void) { v = 15 + 15; while (v--) { s[v] = 32; s[v] = (v % 2) == 1 ? 124 : s[v]; s[v] = (v / 6 % 2) == 1 ? 45 : s[v]; s[v] = ((v % 2) == 1) && ((v / 6 % 2) == 1) ? 43 : s[v]; s[v] = (v % 6) == 5 ? 10 : s[v]; } if (syscall(T, 0, 0, 0, 0) != -1) o(AAa); while (1) { i(); v = 31; O(s); c(); move(); if (!p) o(AAA); p = 0; c(); } return 0;}
Заголовочные файлы
В первую очередь обратим внимание на то, что программа не содержит подключения заголовочных файлов, но при этом выводит в консоль сообщения. Как же это было достигнуто?
Секрет прост, если внимательно посмотреть на Makefile и объявление функции syscall. Да, программа напрямую использует системные вызовы для того, чтобы выводить на экран сообщения (write), проверять себя на запуск под отладчиком (ptrace) и экстренно прерывать программу (exit).
Можно также заметить, что Makefile содержит два набора чисел, передаваемых в компилятор это сделано для того, чтобы программа работала корректно и под x86 и под x86_64 архитектурами (так как они имеют разные таблицы системных вызовов).
Заменим системные вызовы на понятные нам действия (заодно просуммируем константные математические выражения и исправим огрехи indent):
#include <stdio.h>#include <stdlib.h>#include <sys/ptrace.h>void move(void) { /* now make your move with 'p set(x, y)', then 'c' */};const double aaa = 1.40812272124156708779e-308;const double aaA = 1.63732567860768633471e-306;const double aAa = 5.81846600316580299542e+180;const double aAA = 6.13331437392687289128e-154;const double Aaa = 6.01393815945279298101e-154;const double AaA = 6.01347195647080563440e-154;const double AAa = 7.87488138007920286678e+276;const double AAA = 1.28060532144786065112e-152;extern long int syscall(long int, ...);unsigned w[] = { 1409286144, 344064, 84, 1074004032, 268501008, 67125252, 1073807364, 67174464, 0};char s[32] = { 0 };int p = 0, v;void O(char *s) { while (write(1, s++, 1), v--);}char *f(double g) { static double G; G = g; return (char *) &G;}void o(double g) { v = 8; O(f(g)); v = 8; O(f(aaa)); exit(0);} void set(int x, int y) { if (p) o(aaA); if (x < 0 || y < 0 || x > 2 || y > 2 || s[(y * 2) * 6 + x * 2] != 32) o(aAa); s[(y * 2) * 6 + x * 2] = 88; p = 1; v = 31; O(s);}int a(char x, char y) { return (s[(y * 2) * 6 + x * 2] != 32) ? 0 : (s[(y * 2) * 6 + x * 2] = 79);}int i() { return a(1, 1) || a(0, 0) || a(1, 2) || a(2, 1) || a(0, 2) || a(2, 0) || a(1, 0) || a(2, 2) || a(0, 1);}void c() { unsigned *W = w; char *_ = s; unsigned l = 0, I = 0; while (*_) { l |= *_ == 88; I |= *_ == 79; l <<= 1; I <<= 1; _++; } while (*W) { if ((l & *W) == *W) o(aAA); if ((I & *W) == *W) o(Aaa); W++; } if ((l | I) == 1409630292) o(AaA);}int main(void) { v = 15 + 15; while (v--) { s[v] = 32; s[v] = (v % 2) == 1 ? 124 : s[v]; s[v] = (v / 6 % 2) == 1 ? 45 : s[v]; s[v] = ((v % 2) == 1) && ((v / 6 % 2) == 1) ? 43 : s[v]; s[v] = (v % 6) == 5 ? 10 : s[v]; } if (ptrace(0, 0, 0, 0) != -1) o(AAa); while (1) { i(); v = 31; O(s); c(); move(); if (!p) o(AAA); p = 0; c(); } return 0;}
Строки и их хранение
Программа во время работы выводит нам некоторые сообщения, но в коде нет строк в открытом виде. Как же кодируется текст?
Секрет можно открыть, проследив цепочку событий например после функции ptrace:
if (ptrace(0, 0, 0, 0) != -1) o(AAa);
const double AAa = 7.87488138007920286678e+276;void O(char *s) { while (write(1, s++, 1), v--);}char *f(double g) { static double G; G = g; return (char *) &G;}void o(double g) { v = 8; O(f(g));
Очевидно, что константа ААа содержит в себе строку, но представлена как double. Это было достигнуто следующим образом были созданы строки, длиной не более 8 байт (размер double), затем через указатель/memcpy/union они были приведены к double. Пришлось покрутить точность представления, но в итоге удалось добиться того, что как минимум бОльшая часть байт не страдала от урезания при конвертации строка в исходном коде double строка в памяти.
Проведем обратную конвертацию и заменим комплект из f() и O() на printf:
#include <stdio.h>#include <stdlib.h>#include <sys/ptrace.h>void move(void) { /* now make your move with 'p set(x, y)', then 'c' */};extern long int syscall(long int, ...);unsigned w[] = { 1409286144, 344064, 84, 1074004032, 268501008, 67125252, 1073807364, 67174464, 0};char s[32] = { 0 };int p = 0, v;void set(int x, int y) { if (p) { printf("%s\n", "cheater"); exit(EXIT_SUCCESS); } if (x < 0 || y < 0 || x > 2 || y > 2 || s[(y * 2) * 6 + x * 2] != 32) { printf("%s\n", "bad move"); exit(EXIT_SUCCESS); } s[(y * 2) * 6 + x * 2] = 88; p = 1; printf("%s", s);}int a(char x, char y) { return (s[(y * 2) * 6 + x * 2] != 32) ? 0 : (s[(y * 2) * 6 + x * 2] = 79);}int i() { return a(1, 1) || a(0, 0) || a(1, 2) || a(2, 1) || a(0, 2) || a(2, 0) || a(1, 0) || a(2, 2) || a(0, 1);}void c() { unsigned *W = w; char *_ = s; unsigned l = 0, I = 0; while (*_) { l |= *_ == 88; I |= *_ == 79; l <<= 1; I <<= 1; _++; } while (*W) { if ((l & *W) == *W) { printf("%s\n", "winner"); exit(EXIT_SUCCESS); } if ((I & *W) == *W) { printf("%s\n", "loser"); exit(EXIT_SUCCESS); } W++; } if ((l | I) == 1409630292) { printf("%s\n", "draw"); exit(EXIT_SUCCESS); }}int main(void) { v = 15 + 15; while (v--) { s[v] = 32; s[v] = (v % 2) == 1 ? 124 : s[v]; s[v] = (v / 6 % 2) == 1 ? 45 : s[v]; s[v] = ((v % 2) == 1) && ((v / 6 % 2) == 1) ? 43 : s[v]; s[v] = (v % 6) == 5 ? 10 : s[v]; } if (ptrace(0, 0, 0, 0) != -1) { printf("%s\n", "gdb only"); exit(EXIT_SUCCESS); } while (1) { i(); printf("%s", s); c(); move(); if (!p) { printf("%s\n", "no move"); exit(EXIT_SUCCESS); } p = 0; c(); } return 0;}
Стало относительно понятно, какой блок что именно проверяет, но общая природа проверок пока еще не ясна.
Отрисовка поля
После замен double-строк на printf стал заметен блок, заполняющий какую-то длинную строку используя математику а затем печатающий её. Ну разумеется, это поле, рисуемое на экране:
while (v--) { s[v] = 32; // Заполняем все ячейки пробелами s[v] = (v % 2) == 1 ? 124 : s[v]; // Если ячейка нечетная, то ставим знак '|' s[v] = (v / 6 % 2) == 1 ? 45 : s[v]; // Если ряд нечетный, то ставим знак '-' s[v] = ((v % 2) == 1) && ((v / 6 % 2) == 1) ? 43 : s[v]; // Если пересечение, то '+' s[v] = (v % 6) == 5 ? 10 : s[v]; // Добавляем перенос строк } printf("%s", s);
Соответственно, для наглядности, продолжим заменять на читаемый аналог:
memcpy(s, " | | \n" "-+-+-\n" " | | \n" "-+-+-\n" " | | \n", 30);
Обтачивая main
Если мы внимательно проследим за workflow программы, то сразу станет понятно предназначение однобуквенных функций. i() устанавливает ход противника (да, весь ИИ это 9 OR условий, которые компьютер перебирает по очереди пока не найдет свободную ячейку (иногда даже выигрывает)), c() проверяет условия победы или поражения, p, очевидно, количество ходов, которые совершил игрок. Переименуем функции, заодно расставим комментарии там, где можно разобраться без труда:
#include <stdio.h>#include <stdlib.h>#include <sys/ptrace.h>#include <string.h>void move(void) { /* now make your move with 'p set(x, y)', then 'c' */};extern long int syscall(long int, ...);unsigned w[] = { 1409286144, 344064, 84, 1074004032, 268501008, 67125252, 1073807364, 67174464, 0};char s[32] = { 0 };int players_turns = 0;static void print_map(void) { printf("%s", s);}void set(int x, int y) { // Игрок походил более одного раза if (players_turns > 0) { printf("%s\n", "cheater"); exit(EXIT_SUCCESS); } // Игрок походил в занятую ячейку или за пределы поля if (x < 0 || y < 0 || x > 2 || y > 2 || s[(y * 2) * 6 + x * 2] != 32) { printf("%s\n", "bad move"); exit(EXIT_SUCCESS); } // Ставим маркер игрока s[(y * 2) * 6 + x * 2] = 'X'; // Ставим защиту от повторного хода players_turns = 1; print_map();}int check_and_set_AI(char x, char y) { return // Свободна ли ячейка? Если да, ставим 'O', если нет - вернем 0. (s[(y * 2) * 6 + x * 2] != 32) ? 0 : (s[(y * 2) * 6 + x * 2] = 'O');}int set_AI() { // Пробуем все ячейки по очереди return a(1, 1) || a(0, 0) || a(1, 2) || a(2, 1) || a(0, 2) || a(2, 0) || a(1, 0) || a(2, 2) || a(0, 1);}void check_victory() { unsigned *W = w; char *_ = s; unsigned l = 0, I = 0; while (*_) { l |= *_ == 88; I |= *_ == 79; l <<= 1; I <<= 1; _++; } while (*W) { if ((l & *W) == *W) { printf("%s\n", "winner"); exit(EXIT_SUCCESS); } if ((I & *W) == *W) { printf("%s\n", "loser"); exit(EXIT_SUCCESS); } W++; } if ((l | I) == 1409630292) { printf("%s\n", "draw"); exit(EXIT_SUCCESS); }}int main(void) { // Проверяем, что мы под GDB if (ptrace(0, 0, 0, 0) != -1) { printf("%s\n", "gdb only"); exit(EXIT_SUCCESS); } // Инициализируем карту memcpy(s, " | | \n" "-+-+-\n" " | | \n" "-+-+-\n" " | | \n", 30); // Цикл игры while (1) { set_AI(); print_map(); check_victory(); move(); if (!players_turns) { printf("%s\n", "no move"); exit(EXIT_SUCCESS); } players_turns = 0; check_victory(); } return 0;}
Проверка победы
Осталась одна функция, которая какой-то математической магией проверяет условия победы.
На самом деле она делает это не просто, а очень просто и в сишном стиле каждая ячейка поля представляется как один бит. И есть две переменные длиной не менее 32 бит для учета AI и игрока. Проходим по каждой ячейке/биту и ставим 1 в соответствующую переменную если стоит фигура одного из игроков. Затем сравниваем, соответствует ли получившееся число одной из констант-побед, вынесенных в отдельный массив. Если да, то победил игрок, получивший нужную комбинацию.
while (*_) { l |= *_ == 'X'; I |= *_ == 'O'; l <<= 1; I <<= 1; _++; }
Перепишем функцию и опишем константы:
#include <stdio.h>#include <stdlib.h>#include <sys/ptrace.h>#include <string.h>void move(void) { /* now make your move with 'p set(x, y)', then 'c' */};unsigned victory_positions[] = { 1409286144, // Первая строка 344064, // Вторая строка 84, // Третья строка 1074004032, // Первый столбец 268501008, // Второй столбец 67125252, // Третий столбец 1073807364, // Диагональ 00->22 67174464, // Диагональ 20->02 0 // Признак конца массива};char map[32] = { 0 };int players_turns = 0;static void print_map(void) { printf("%s", map);}void set(int x, int y) { // Игрок походил более одного раза if (players_turns > 0) { printf("%s\n", "cheater"); exit(EXIT_SUCCESS); } // Игрок походил в занятую ячейку или за пределы поля if (x < 0 || y < 0 || x > 2 || y > 2 || map[(y * 2) * 6 + x * 2] != 32) { printf("%s\n", "bad move"); exit(EXIT_SUCCESS); } // Ставим маркер игрока map[(y * 2) * 6 + x * 2] = 'X'; // Ставим защиту от повторного хода players_turns = 1; print_map();}int check_and_set_AI(char x, char y) { return // Свободна ли ячейка? Если да, ставим 'O', если нет - вернем 0. (map[(y * 2) * 6 + x * 2] != 32) ? 0 : (map[(y * 2) * 6 + x * 2] = 'O');}int set_AI() { // Пробуем все ячейки по очереди return a(1, 1) || a(0, 0) || a(1, 2) || a(2, 1) || a(0, 2) || a(2, 0) || a(1, 0) || a(2, 2) || a(0, 1);}void check_victory() { unsigned * victory_iterator = victory_positions; char * map_iterator = map; unsigned player_score = 0, enemy_score = 0; // Проход по полю - считаем score while (*map_iterator) { player_score |= *_ == 'X'; enemy_score |= *_ == 'O'; player_score <<= 1; enemy_score <<= 1; map_iterator++; } // Проход по выигрышным комбинациям while (*victory_iterator) { // Победил игрок if ((player_score & *victory_iterator) == *victory_iterator) { printf("%s\n", "winner"); exit(EXIT_SUCCESS); } // Победил противник if ((enemy_score & *victory_iterator) == *victory_iterator) { printf("%s\n", "loser"); exit(EXIT_SUCCESS); } victory_iterator++; } // Оба игрока в сумме заняли все ячейки if ((player_score | enemy_score) == 1409630292) { printf("%s\n", "draw"); exit(EXIT_SUCCESS); }}int main(void) { // Проверяем, что мы под GDB if (ptrace(0, 0, 0, 0) != -1) { printf("%s\n", "gdb only"); exit(EXIT_SUCCESS); } // Инициализируем карту memcpy(map, " | | \n" "-+-+-\n" " | | \n" "-+-+-\n" " | | \n", 30); // Цикл игры while (1) { set_AI(); print_map(); check_victory(); move(); if (!players_turns) { printf("%s\n", "no move"); exit(EXIT_SUCCESS); } players_turns = 0; check_victory(); } return 0;}
Вот и всё. Программа разобрана по винтикам, все функции стали понятны.
Во второй части разберем симулятор работы NOR-чипов в DIP-8 корпусе, работающий через X11 (и умещающийся в 3755 байт).
Надеюсь опыт разбора подобных конкурсных задач поможет вам проверять код Junior-C разработчиков.