Нас с детства учили, что хороший, качественный код должен хорошо читаться, быть семантически и алгоритмически понятным. Все ругают программистов, которые пишут непонятный или переусложенный код.
Но что, если провести конкурс, в котором критерий «хорошести» кода будет перевернут?
Читаемость и понятность со знаком «минус». Именно с такими мыслями 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 из-за которого всё пришлось делать с нуля повторно этому поспособствовал). Цикл статей состоит из двух частей (от простого к сложному):
Есть ли сожаления, что победа досталась кому-то другому? В общем нет. Я особо надеялся на свою вторую работу (из части 2) и на номинацию «Самая запутанная программа для X11», но в этом году этой номинации не было. Что ж, это повод попытаться в следующем году придумать что-то посложнее.
Несмотря на то, что «Крестики-нолики» была моей второй работой, она проще, а следовательно лучше начать цикл статей с нее. По сравнению с другими работами других авторов она достаточно слабая, но позволяет уловить часть «приемов» для облегчения рассмотрения второй части.
Для начала, сам код работы:
prog.c («Т» — от английского названия игры — («Tic-Tac-Toe»):
Makefile:
Сборка:
Для удобства исходный код можно взять из github репозитория.
На этом месте я бы хотел обратиться к тем, кто достаточно хорошо знает язык Си. Если у вас есть желание — отложите статью в сторону до вечера или выходных и постарайтесь в свободное время понять, как именно работает программа, поупражнявшись таким образом в чтении запутанного кода.
Тех же, кто хочет сразу рассмотреть решение прошу читать дальше.
Так как код всё же должен выполнять свою работу (и, желательно, каким-нибудь извращенным методом), то попробуем в него поиграть. Для этого нужно запустить программу под отладчиком и установить точку останова на нужную функцию:
Теперь запустим программу:
Нам нарисовали поле и попросили указать координаты, по которым мы хотим нарисовать крестик (противник сделал свой ход ноликами). Сделаем ход так, как нас просят на экране и продолжим выполнение программы:
Продолжим игру:
Что ж, это было не трудно (в конце концов никто не обещал сложные машинные алгоритмы).
В игре также присутствует проверка на нечестный поступок (ход игроком два раза подряд), ход в несуществующую ячейку и пропуск хода. В случае же запуска программы без отладчика она завершится с сообщением «gdb only».
Пришло время взять скальпель и препарировать пациента.
Для удобства читаемости прогоним программу через indent (мне нравятся опции -kr -brf):
В первую очередь обратим внимание на то, что программа не содержит подключения заголовочных файлов, но при этом выводит в консоль сообщения. Как же это было достигнуто?
Секрет прост, если внимательно посмотреть на Makefile и объявление функции syscall. Да, программа напрямую использует системные вызовы для того, чтобы выводить на экран сообщения (write), проверять себя на запуск под отладчиком (ptrace) и экстренно прерывать программу (exit).
Можно также заметить, что Makefile содержит два набора чисел, передаваемых в компилятор — это сделано для того, чтобы программа работала корректно и под x86 и под x86_64 архитектурами (так как они имеют разные таблицы системных вызовов).
Заменим системные вызовы на понятные нам действия (заодно просуммируем константные математические выражения и исправим огрехи indent):
Программа во время работы выводит нам некоторые сообщения, но в коде нет строк в открытом виде. Как же кодируется текст?
Секрет можно открыть, проследив цепочку событий например после функции ptrace:
Очевидно, что константа ААа содержит в себе строку, но представлена как double. Это было достигнуто следующим образом — были созданы строки, длиной не более 8 байт (размер double), затем через указатель/memcpy/union они были приведены к double. Пришлось покрутить точность представления, но в итоге удалось добиться того, что как минимум бОльшая часть байт не страдала от «урезания» при конвертации строка в исходном коде > double > строка в памяти.
Проведем обратную конвертацию и заменим комплект из f() и O() на printf:
Стало относительно понятно, какой блок что именно проверяет, но общая природа проверок пока еще не ясна.
После замен double-строк на printf стал заметен блок, заполняющий какую-то длинную строку используя математику а затем печатающий её. Ну разумеется, это поле, рисуемое на экране:
Соответственно, для наглядности, продолжим заменять на читаемый аналог:
Если мы внимательно проследим за workflow программы, то сразу станет понятно предназначение однобуквенных функций. i() устанавливает ход противника (да, весь ИИ — это 9 OR условий, которые компьютер перебирает по очереди пока не найдет свободную ячейку (иногда даже выигрывает)), c() — проверяет условия победы или поражения, p, очевидно, количество ходов, которые совершил игрок. Переименуем функции, заодно расставим комментарии там, где можно разобраться без труда:
Осталась одна функция, которая какой-то математической магией проверяет условия победы.
На самом деле она делает это не просто, а очень просто и в сишном стиле — каждая ячейка поля представляется как один бит. И есть две переменные длиной не менее 32 бит — для учета AI и игрока. Проходим по каждой ячейке/биту и ставим 1 в соответствующую переменную если стоит фигура одного из игроков. Затем сравниваем, соответствует ли получившееся число одной из констант-побед, вынесенных в отдельный массив. Если да, то победил игрок, получивший нужную комбинацию.
Перепишем функцию и опишем константы:
Вот и всё. Программа разобрана по винтикам, все функции стали понятны.
Во второй части разберем симулятор работы NOR-чипов в DIP-8 корпусе, работающий через X11 (и умещающийся в 3?755 байт).
Надеюсь опыт разбора подобных конкурсных задач поможет вам проверять код Junior-C разработчиков.
Но что, если провести конкурс, в котором критерий «хорошести» кода будет перевернут?
Читаемость и понятность со знаком «минус». Именно с такими мыслями 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) ;} 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:
#!/usr/bin/env make
PROJECT= prog
CC= gcc
SRC= prog.c
CWARN= -Wall -Wextra -Wno-misleading-indentation
CSTD= -std=c99
BITS := $(shell uname -p)
ifeq ($(BITS), x86_64)
ARCH= -m64
# write
# ptrace
# exit
CDEFINE= -DP=1 -DT=101 -DE=60
else
ARCH= -m32
# write
# ptrace
# exit
CDEFINE= -DP=4 -DT=26 -DE=1
endif
OPT= -g
CFLAGS= ${CWARN} ${CSTD} ${ARCH} ${CDEFINE} ${OPT}
LDFLAGS= -ldl
RM= rm
all: ${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 move
Breakpoint 1 at 0x64e: file prog.c, line 1.
Теперь запустим программу:
(gdb) r
Starting program: /home/alex/development/c/ioccc/tic/prog
| |
-+-+-
|O|
-+-+-
| |
Breakpoint 1, move () at prog.c:1
1 void move(void) {/* now make your move with 'p set(x, y)', then 'c' */};
(gdb)
Нам нарисовали поле и попросили указать координаты, по которым мы хотим нарисовать крестик (противник сделал свой ход ноликами). Сделаем ход так, как нас просят на экране и продолжим выполнение программы:
(gdb) p set(0, 0)
X| |
-+-+-
|O|
-+-+-
| |
$1 = void
(gdb) c
Continuing.
X| |
-+-+-
|O|
-+-+-
|O|
Breakpoint 1, move () at prog.c:1
1 void 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) c
Continuing.
X|X|
-+-+-
|O|O
-+-+-
|O|
Breakpoint 1, move () at prog.c:1
1 void 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) c
Continuing.
winner
[Inferior 1 (process 2785) exited normally]
Что ж, это было не трудно (в конце концов никто не обещал сложные машинные алгоритмы).
В игре также присутствует проверка на нечестный поступок (ход игроком два раза подряд), ход в несуществующую ячейку и пропуск хода. В случае же запуска программы без отладчика она завершится с сообщением «gdb only».
Как это работает
Пришло время взять скальпель и препарировать пациента.
Для удобства читаемости прогоним программу через indent (мне нравятся опции -kr -brf):
Исходный код после 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):
После замены syscall и форматирования
#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:
Код после замены double-строк на 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 check_and_set_AI(1, 1) || check_and_set_AI(0, 0) || check_and_set_AI(1, 2) ||
check_and_set_AI(2, 1) || check_and_set_AI(0, 2) || check_and_set_AI(2, 0) ||
check_and_set_AI(1, 0) || check_and_set_AI(2, 2) || check_and_set_AI(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 (и умещающийся в 3?755 байт).
Надеюсь опыт разбора подобных конкурсных задач поможет вам проверять код Junior-C разработчиков.