[C, Отладка, Системное программирование] Как я участвовал в IOCCC-'19 (и проиграл). Часть 1: «Крестики-нолики»
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Нас с детства учили, что хороший, качественный код должен хорошо читаться, быть семантически и алгоритмически понятным. Все ругают программистов, которые пишут непонятный или переусложенный код.
Но что, если провести конкурс, в котором критерий «хорошести» кода будет перевернут? Читаемость и понятность со знаком «минус». Именно с такими мыслями 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
SPL
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 и форматирования
SPL
#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
SPL
#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, очевидно, количество ходов, которые совершил игрок. Переименуем функции, заодно расставим комментарии там, где можно разобраться без труда:
Убираем однобуквенность и ставим комментарии
SPL
#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;
_++;
}
Перепишем функцию и опишем константы:
Конец игры
SPL
#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 разработчиков.
===========
Источник:
habr.com
===========
Похожие новости:
- [DevOps, Карьера в IT-индустрии, Системное администрирование] Как увлеличить доход сисадмина в 4 раза за три года
- [Data Mining, Big Data, Natural Language Processing] Парсим Википедию, фильтруя, для задач NLP в 44 строки кода
- [Астрономия, Научно-популярное] Прощаемся с кометой NEOWISE
- [Производство и разработка электроники, Процессоры, Реверс-инжиниринг] Реверс-инжиниринг чипа компьютера Commodore (перевод)
- [Laravel, PHP, Symfony, Разработка веб-сайтов] PhpStorm 2020.2: объединенные типы PHP 8, новый движок потока управления, пул-реквесты GitHub, OpenAPI
- [Облачные вычисления, Компьютерное железо, Биотехнологии, Интернет вещей, Здоровье] Neocortix делает вклад в исследования COVID-19, открывая мир 64-битных Arm устройств для Folding@Home и Rosetta@Home (перевод)
- [DevOps, Kubernetes, Серверное администрирование, Системное администрирование] Docker и все, все, все
- [Microsoft Azure, SharePoint, Облачные сервисы, Разработка для Office 365] Common Data Service и Power Apps. Создание мобильного приложения
- [Node.JS, TypeScript] Пишем свой dependency free WebSocket сервер на Node.js
- [Go] Go: Как использовать nil-значения без использования ссылочных типов (перевод)
Теги для поиска: #_c, #_otladka (Отладка), #_sistemnoe_programmirovanie (Системное программирование), #_c, #_ioccc, #_konkurs (конкурс), #_c, #_otladka (
Отладка
), #_sistemnoe_programmirovanie (
Системное программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:54
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
Нас с детства учили, что хороший, качественный код должен хорошо читаться, быть семантически и алгоритмически понятным. Все ругают программистов, которые пишут непонятный или переусложенный код. Но что, если провести конкурс, в котором критерий «хорошести» кода будет перевернут? Читаемость и понятность со знаком «минус». Именно с такими мыслями 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»): 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 -brfSPLvoid 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 и форматированияSPL#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-строк на printfSPL#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, очевидно, количество ходов, которые совершил игрок. Переименуем функции, заодно расставим комментарии там, где можно разобраться без труда: Убираем однобуквенность и ставим комментарииSPL#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; _++; } Перепишем функцию и опишем константы: Конец игрыSPL#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 разработчиков. =========== Источник: habr.com =========== Похожие новости:
Отладка ), #_sistemnoe_programmirovanie ( Системное программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:54
Часовой пояс: UTC + 5