[Перевод] Крестики-нолики на printf14.01.2025 15:45

Представляем вам реализацию игры в крестики-нолики на С с помощью одного вызова printf. Написана для участия в IOCCC в 2020 году.

Полный код в конце статьи

Полный код в конце статьи

Как играть

gcc -o prog prog.c
./prog

Игроки 1 и 2 ходят по очереди. Нужно ввести цифру от 1 до 9, чтобы занять клетку: 

1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 9

Игра заканчивается, если:

  • Игрок ставит три значения в ряд — он побеждает

  • Все клетки заняты — ничья

  • Игрок выполняет запрещенный ход — его оппонент побеждает

Обфускация

Вся программа состоит из одного вызова функции printf: 

int main() {
    while(*d) printf(fmt, arg);
}

Здесь fmt — это строка, а arg — последовательность аргументов для printf.

Несмотря на то, что истинное предназначение printf — быть Единственным Настоящим Отладчиком, эта функция также обладает полнотой по Тюрингу.

Эту особенность мы представили в настоящей, опубликованной, научной статье под названием «Control-Flow Bending: On the Effectiveness of Control-Flow Integrity». Иногда удается провернуть даже такое.

Мы воспользовались этим фактом во зло, чтобы выполнить всю логику крестиков-ноликов внутри одного вызова printf (и одного вызова scanf, чтобы принять пользовательский ввод). Вот краткое описание того, как оно работает.

Подготовка

Эта программа использует три указателя формата:

  • %d принимает целое число и печатает его

  • %s принимает строку и печатает ее

  • %n принимает указатель и записывает (!) по нему количество выведенных на данный момент байт

Ну да ладно, это наверняка все знают. Теперь копнем поглубже.

Указатели формата могут принимать дополнительные «аргументы».

  • "%hhn": сохранить количество распечатанных байтов по модулю 256 по указателю типа char

  • "%2$d": напечатать аргумент номер 2, а не следующий по порядку

  • "%8d": добить число отступами до 8 символов

  • "%3$.*4$d": напечатать аргумент 3, используя столько нулей, сколько указано в аргументе 4

Например, следующее выражение: 

printf("%1$.*2$d%3$hhn", 5, 10, &x)

будет иметь тот же эффект, как если бы мы написали: 

x = 10;

поскольку оно напечатает 0000000005 (число 5, добитое нулями до 10 символов), а потом сохранит количество выведенных байт в x.

Printf-ориентированное программирование

Ну ладно, сейчас начинается самая жара.

Мы можем выполнить произвольное вычисление с помощью printf, обращаясь с памятью как с битовым массивом, где каждый бит представлен двумя байтами:

  • Нулевой бит представлен последовательностью 00 00

  • Единичный бит представлен последовательностью xx 00, где xx — любой не-нулевой байт

Теперь мы используем строки форматирования, чтобы производить над этими «битами» произвольные логические операции.

Начнем с самой простой операции, ИЛИ: 

printf("%1$s%2$s%3$hhn", a, b, c)

вычислит следующее: 

*c = strlen(a) + strlen(b)

Но поскольку strlen(x) для единичного бита равно 1, а для нулевого — 0, то мы получим: 

*c = a | b

Выполнить операцию НЕ тоже просто: 

printf("%1$255d%1$s%hhn", a, b)

вычислит следующее: 

*b = (strlen(a)+255)%256 = strlen(a)-1

Но опять, вспоминая как работает strlen(x), мы получаем: 

*c = !b

На этой базе можно выразить любую логическую схему. Однако сделать это эффективно по-прежнему непросто.

Крестики-нолики

Состояние игры включает в себя игровое поле из 18 бит, по 9 на каждого игрока, а также счетчик ходов, который переключается между 1 и 2 игроками.

Победитель определяется следующим образом. Допустим, A, B и C — указатели на три клетки в ряд, а D — место, куда нужно сохранить информацию о том, выиграли мы или нет.

"%A$s%B$s%C$s%1$253d%11$hhn" // r11 = !(*A & *B & *C)
ZERO
"%11$s%1$255d%11hhn" // r11 = !r11
ZERO
"%11$s%D$s%D$hhn" // *D = *D | r11

Таким образом мы записываем по адресу D единицу, если у нас есть три значения в ряд. Дальше мы повторяем это для всех строк, столбцов и диагоналей, для обоих игроков.

Макрос ZERO гарантирует, что количество записанных байт будет кратно 256, чтобы при в остатке от деления был 0, благодаря следующему выражению: 

"%1$hhn%1$s" (повторяется 256 раз)

где аргумент 1 — это указатель на временную переменную, за которой следует нулевой байт.

Это работает, поскольку если текущее значение кратно 256, то "%1$hhn" запишет по адресу из аргумента 1 число 0 и "%1$s" не выведет никакого текста. С другой стороны, если текущее значение не кратно 256, то в аргумент будет записана строка единичной длины, а "%1$s" увеличит счетчик на 1. Повторяя это 256 раз, мы рано или поздно достигнем числа, дающего 0 в остатке при делении на 256.

Проверка на недопустимый ход выполняется аналогичным образом.

Чтобы определить, что нужно печатать, мы должны сконвертировать массив «битов» в символы X и O. Это довольно несложно сделать. Если представить, что аргумент 1 — это указатель на клетку первого игрока, аргумент 2 — указатель на клетку второго, а аргумент 3 — указатель на строку доски, мы можем вычислить: 

"%1$s" (повторяется 47 раз) "%2$s" (повторяется 56 раз) %1$32d%3$hhn"

что будет эквивалентно

*r3 = (*r1) * 47 + (*r2) * 56 + 32

И выведет 'X' если r1 = 1, 'O' если r2 = 1, а иначе ' '.

Дальнейшая обфускация

Чтобы наконец-то отобразить доску, используя всего одно выражение printf, мы заканчиваем строку формата следующим образом: 

"\n\033[2J\n%26$s"

Это управляющая последовательность, очищающая экран, а потом распечатывающая содержимое аргумента 26. Этот аргумент указывает на строку в памяти, которая изначально не определена, но с помощью того же printf мы предварительно соберем в этой строке текстовое представление игрового поля.

Следом за полем нам нужно вывести одну из строк ниже: 

P1>_        // игрок 1 ходит
P2>_        // игрок 2 ходит
P1 WINS     // игрок 1 победил
P2 WINS     // игрок 2 победил
P1 TIES     // игрок 1 вызвал ничью
P2 TIES     // игрок 2 вызвал ничью

Это проще, чем кажется. Используя тот же самый прием, что и раньше, мы выполняем: 

*byte4 = is_win * 'W' + is_tie * 'T'

Дальше I и S одинаковые в обоих случаях, а для E или N мы делаем то же самое.

Аналогичным образом мы конструируем строку форматирования для scanf на лету, но по другой причине. Нам нужно сначала выполнить printf чтобы вывести доску, а потом по очереди выполнять scanf и printf, считывая и отображая ходы игрока. Важно то, что после завершения игры не должно быть еще одного финального вызова scanf: приложение просто должно закрыться.

Можно было бы реализовать логику следующим образом: 

printf()
while (*ok) {
    scanf();
    printf();
}

Но тогра у нас будет ВДВОЕ БОЛЬШЕ вызовов printf, чем нам необходимо. Поэтому мы реализуем логику следующим образом: 

while (*ok) {
    scanf();
    printf();
}

(На самом деле мы передаем указатель на scanf в качестве аргумента, но эффект тот же).

Обратите внимание на отсутствие printf в начале. Чтобы игра не требовала никакого ввода перед первым вызовом printf, мы изначально задаем строку форматирования для scanf в NULL, из-за чего она ничего не делает и сразу же выходит. При первом вызове printf по адресу строки форматирования для scanf записывается %hhd, и в следующий раз оно срабатывает.

Полный код программы

#include  

#define N(a)       "%"#a"$hhn"
#define O(a,b)     "%10$"#a"d"N(b)
#define U          "%10$.*37$d"
#define G(a)       "%"#a"$s"
#define H(a,b)     G(a)G(b)
#define T(a)       a a 
#define s(a)       T(a)T(a)
#define A(a)       s(a)T(a)a
#define n(a)       A(a)a
#define D(a)       n(a)A(a)
#define C(a)       D(a)a
#define R          C(C(N(12)G(12)))
#define o(a,b,c)   C(H(a,a))D(G(a))C(H(b,b)G(b))n(G(b))O(32,c)R
#define SS         O(78,55)R "\n\033[2J\n%26$s";
#define E(a,b,c,d) H(a,b)G(c)O(253,11)R G(11)O(255,11)R H(11,d)N(d)O(253,35)R
#define S(a,b)     O(254,11)H(a,b)N(68)R G(68)O(255,68)N(12)H(12,68)G(67)N(67)

char* fmt = O(10,39)N(40)N(41)N(42)N(43)N(66)N(69)N(24)O(22,65)O(5,70)O(8,44)N(
            45)N(46)N    (47)N(48)N(    49)N( 50)N(     51)N(52)N(53    )O( 28,
            54)O(5,        55) O(2,    56)O(3,57)O(      4,58 )O(13,    73)O(4,
            71 )N(   72)O   (20,59    )N(60)N(61)N(       62)N (63)N    (64)R R
            E(1,2,   3,13   )E(4,    5,6,13)E(7,8,9        ,13)E(1,4    ,7,13)E
            (2,5,8,        13)E(    3,6,9,13)E(1,5,         9,13)E(3    ,5,7,13
            )E(14,15,    16,23)    E(17,18,19,23)E(          20, 21,    22,23)E
            (14,17,20,23)E(15,    18,21,23)E(16,19,    22     ,23)E(    14, 18,
            22,23)E(16,18,20,    23)R U O(255 ,38)R    G (     38)O(    255,36)
            R H(13,23)O(255,    11)R H(11,36) O(254    ,36)     R G(    36 ) O(
            255,36)R S(1,14    )S(2,15)S(3, 16)S(4,    17 )S     (5,    18)S(6,
            19)S(7,20)S(8,    21)S(9    ,22)H(13,23    )H(36,     67    )N(11)R
            G(11)""O(255,    25 )R        s(C(G(11)    ))n (G(          11) )G(
            11)N(54)R C(    "aa")   s(A(   G(25)))T    (G(25))N         (69)R o
            (14,1,26)o(    15, 2,   27)o   (16,3,28    )o( 17,4,        29)o(18
            ,5,30)o(19    ,6,31)o(        20,7,32)o    (21,8,33)o       (22 ,9,
            34)n(C(U)    )N( 68)R H(    36,13)G(23)    N(11)R C(D(      G(11)))
            D(G(11))G(68)N(68)R G(68)O(49,35)R H(13,23)G(67)N(11)R C(H(11,11)G(
            11))A(G(11))C(H(36,36)G(36))s(G(36))O(32,58)R C(D(G(36)))A(G(36))SS

#define arg d+6,d+8,d+10,d+12,d+14,d+16,d+18,d+20,d+22,0,d+46,d+52,d+48,d+24,d\
            +26,d+28,d+30,d+32,d+34,d+36,d+38,d+40,d+50,(scanf(d+126,d+4),d+(6\
            -2)+18*(1-d[2]%2)+d[4]*2),d,d+66,d+68,d+70, d+78,d+80,d+82,d+90,d+\
            92,d+94,d+97,d+54,d[2],d+2,d+71,d+77,d+83,d+89,d+95,d+72,d+73,d+74\
            ,d+75,d+76,d+84,d+85,d+86,d+87,d+88,d+100,d+101,d+96,d+102,d+99,d+\
            67,d+69,d+79,d+81,d+91,d+93,d+98,d+103,d+58,d+60,d+98,d+126,d+127,\
            d+128,d+129

char d[538] = {1,0,10,0,10};

int main() {
    while(*d) printf(fmt, arg);
}

Примечание переводчика

Проект автора завоевал призовое место в номинации «злоупотребление стандартной библиотекой»:
https://www.ioccc.org/2020/carlini/index.html

Оригинальный исходник с подробными комментариями можно найти в репозитории автора:
https://github.com/carlini/printf-tac-toe/blob/master/printtt.orig.c

Habrahabr.ru прочитано 1671 раз