Конкурс «Запутанный код C» 2006. Пожалуйста, объясните sykes2.c

975

Как работает эта C-программа?

main(_){_^448&&main(-~_);putchar(--_%64?32|-~7[__TIME__-_/8%8][">'txiZ^(~z?"-48]>>";;;====~$::199"[_*2&8|_/64]/(_&2?1:8)%8&1:10);}

Компилируется как есть (проверено gcc 4.6.3). Он печатает время при компиляции. В моей системе:

    !!  !!!!!!              !!  !!!!!!              !!  !!!!!! 
    !!  !!  !!              !!      !!              !!  !!  !! 
    !!  !!  !!              !!      !!              !!  !!  !! 
    !!  !!!!!!    !!        !!      !!    !!        !!  !!!!!! 
    !!      !!              !!      !!              !!  !!  !! 
    !!      !!              !!      !!              !!  !!  !! 
    !!  !!!!!!              !!      !!              !!  !!!!!!

Источник: sykes2 - часы в одну строку , намеки автора sykes2

Некоторые подсказки: нет предупреждений компиляции по умолчанию. Скомпилированы -Wallследующие предупреждения:

sykes2.c:1:1: warning: return type defaults to int [-Wreturn-type]
sykes2.c: In function main’:
sykes2.c:1:14: warning: value computed is not used [-Wunused-value]
sykes2.c:1:1: warning: implicit declaration of function putchar [-Wimplicit-function-declaration]
sykes2.c:1:1: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
sykes2.c:1:1: warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]
sykes2.c:1:1: warning: control reaches end of non-void function [-Wreturn-type]
шероховатый
источник
6
Отладка: добавление printf("%d", _);в начало mainраспечаток: pastebin.com/HHhXAYdJ
банально
Целое число, каждая нетипизированная переменная по умолчанию имеет значениеint
drahnr
18
Вы прочитали подсказку? ioccc.org/2006/sykes2/hint.text
nhahtdh
2
Также читайте stackoverflow.com/questions/10321196/…
Xofo
Если вы запустите его так, это приведет к сбою:./a.out $(seq 0 447)
SS Anne

Ответы:

1819

Давайте де-запутать это.

Отступ:

main(_) {
    _^448 && main(-~_);
    putchar(--_%64
        ? 32 | -~7[__TIME__-_/8%8][">'txiZ^(~z?"-48] >> ";;;====~$::199"[_*2&8|_/64]/(_&2?1:8)%8&1
        : 10);
}

Введение переменных, чтобы распутать этот беспорядок:

main(int i) {
    if(i^448)
        main(-~i);
    if(--i % 64) {
        char a = -~7[__TIME__-i/8%8][">'txiZ^(~z?"-48];
        char b = a >> ";;;====~$::199"[i*2&8|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    } else {
        putchar(10); // newline
    }
}

Обратите внимание, что -~i == i+1из-за двойного дополнения. Поэтому мы имеем

main(int i) {
    if(i != 448)
        main(i+1);
    i--;
    if(i % 64 == 0) {
        putchar('\n');
    } else {
        char a = -~7[__TIME__-i/8%8][">'txiZ^(~z?"-48];
        char b = a >> ";;;====~$::199"[i*2&8|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    }
}

Теперь обратите внимание, что a[b]это то же самоеb[a] , и примените -~ == 1+изменение снова:

main(int i) {
    if(i != 448)
        main(i+1);
    i--;
    if(i % 64 == 0) {
        putchar('\n');
    } else {
        char a = (">'txiZ^(~z?"-48)[(__TIME__-i/8%8)[7]] + 1;
        char b = a >> ";;;====~$::199"[(i*2&8)|i/64]/(i&2?1:8)%8;
        putchar(32 | (b & 1));
    }
}

Преобразование рекурсии в цикл и пробежка в немного упрощенном виде:

// please don't pass any command-line arguments
main() {
    int i;
    for(i=447; i>=0; i--) {
        if(i % 64 == 0) {
            putchar('\n');
        } else {
            char t = __TIME__[7 - i/8%8];
            char a = ">'txiZ^(~z?"[t - 48] + 1;
            int shift = ";;;====~$::199"[(i*2&8) | (i/64)];
            if((i & 2) == 0)
                shift /= 8;
            shift = shift % 8;
            char b = a >> shift;
            putchar(32 | (b & 1));
        }
    }
}

Это выводит один символ за итерацию. Каждый 64-й символ выводит новую строку. В противном случае он использует пару таблиц данных, чтобы выяснить, что выводить, и помещает либо символ 32 (пробел), либо символ 33 (а !). Первая таблица ( ">'txiZ^(~z?") представляет собой набор из 10 битовых карт, описывающих внешний вид каждого символа, а вторая таблица ( ";;;====~$::199") выбирает соответствующий бит для отображения из битовой карты.

Второй стол

Давайте начнем с изучения второй таблицы int shift = ";;;====~$::199"[(i*2&8) | (i/64)];. i/64это номер строки (от 6 до 0) и i*2&8равен 8, если i4, 5, 6 или 7 mod 8.

if((i & 2) == 0) shift /= 8; shift = shift % 8выбирает либо восьмеричную цифру (для i%8= 0,1,4,5), либо восьмеричную цифру (для i%8= 2,3,6,7) табличного значения. Таблица сдвига в итоге выглядит так:

row col val
6   6-7 0
6   4-5 0
6   2-3 5
6   0-1 7
5   6-7 1
5   4-5 7
5   2-3 5
5   0-1 7
4   6-7 1
4   4-5 7
4   2-3 5
4   0-1 7
3   6-7 1
3   4-5 6
3   2-3 5
3   0-1 7
2   6-7 2
2   4-5 7
2   2-3 3
2   0-1 7
1   6-7 2
1   4-5 7
1   2-3 3
1   0-1 7
0   6-7 4
0   4-5 4
0   2-3 3
0   0-1 7

или в табличной форме

00005577
11775577
11775577
11665577
22773377
22773377
44443377

Обратите внимание, что автор использовал нулевой терминатор для первых двух записей таблицы (подлый!).

Это разработано после семисегментного дисплея с 7s в качестве пробелов. Таким образом, записи в первой таблице должны определять сегменты, которые загораются.

Первый стол

__TIME__это специальный макрос, определенный препроцессором. Он расширяется до строковой константы, содержащей время запуска препроцессора в форме "HH:MM:SS". Обратите внимание, что он содержит ровно 8 символов. Обратите внимание, что 0-9 имеют значения ASCII от 48 до 57 и :имеют значение ASCII 58. Выходные данные составляют 64 символа в строке, так что остается 8 символов на символ __TIME__.

7 - i/8%8таким образом, индекс того, __TIME__что в данный момент выводится ( 7-необходим, потому что мы выполняем итерацию iвниз). Итак, tхарактер __TIME__выхода.

aв результате получается двоичное значение, в зависимости от входных данных t:

0 00111111
1 00101000
2 01110101
3 01111001
4 01101010
5 01011011
6 01011111
7 00101001
8 01111111
9 01111011
: 01000000

Каждое число представляет собой растровое изображение, описывающее сегменты, которые подсвечиваются на нашем семисегментном дисплее. Поскольку все символы являются 7-битными ASCII, старший бит всегда очищается. Таким образом, 7в таблице сегментов всегда печатается как пустой. Вторая таблица выглядит так с 7пробелами s:

000055  
11  55  
11  55  
116655  
22  33  
22  33  
444433  

Так, например, 4есть 01101010(биты 1, 3, 5 и 6 установлены), который печатает как

----!!--
!!--!!--
!!--!!--
!!!!!!--
----!!--
----!!--
----!!--

Чтобы показать, что мы действительно понимаем код, давайте немного скорректируем вывод с помощью этой таблицы:

  00  
11  55
11  55
  66  
22  33
22  33
  44

Это закодировано как "?;;?==? '::799\x07". В художественных целях мы добавим 64 к нескольким символам (поскольку используются только младшие 6 битов, это не повлияет на вывод); это дает "?{{?}}?gg::799G"(обратите внимание, что 8-й символ не используется, поэтому мы можем сделать его как угодно). Положим нашу новую таблицу в исходный код:

main(_){_^448&&main(-~_);putchar(--_%64?32|-~7[__TIME__-_/8%8][">'txiZ^(~z?"-48]>>"?{{?}}?gg::799G"[_*2&8|_/64]/(_&2?1:8)%8&1:10);}

мы получили

          !!              !!                              !!   
    !!  !!              !!  !!  !!  !!              !!  !!  !! 
    !!  !!              !!  !!  !!  !!              !!  !!  !! 
          !!      !!              !!      !!                   
    !!  !!  !!          !!  !!      !!              !!  !!  !! 
    !!  !!  !!          !!  !!      !!              !!  !!  !! 
          !!              !!                              !!   

как мы и ожидали. Это не так хорошо выглядит, как оригинал, что объясняет, почему автор решил использовать таблицу, которую он сделал.

nneonneo
источник
2
@drahnr - Технически это и *(разыменование) и a +: P
ловко
18
@ АртёмЦарионов: Около 30 минут, но я возвращаюсь и редактирую его довольно много. Я часто использую C, и я сделал несколько деобфускаций IOCCC для личного интереса прежде (последний, который я сделал, только для личного интереса, был этим красивым raytracer ). Если вы хотите спросить, как это работает, я был бы рад сделать это;)
nneonneo
5
@ АртёмЦарионов: около дня IIRC (также подсчитывает время, потраченное на понимание геометрии raytracer). Эта программа также очень умная, потому что она не использует ключевые слова .
nneonneo
178
C .. вся мощь языка ассемблера в сочетании с удобочитаемостью языка ассемблера
Вим
6
Чтобы узнать больше об этом, посмотрите «Запутанный С и другие тайны» Дона Либеса. Он обучает методам Си, анализируя записи C Obfuscated C Contest.
Крис N
102

Давайте отформатируем это для удобства чтения:

main(_){
  _^448&&main(-~_);
  putchar((--_%64) ? (32|-(~7[__TIME__-_/8%8])[">'txiZ^(~z?"-48]>>(";;;====~$::199")[_*2&8|_/64]/(_&2?1:8)%8&1):10);
}

Таким образом, запустив его без аргументов, _ (условно argc) есть 1. main()будет рекурсивно вызывать себя, передавая результат -(~_)(отрицательный побитовый НЕ _), так что на самом деле будет идти 448 рекурсий (только условие, где _^448 == 0).

Принимая это, он напечатает 7 64-символьных широких линий (внешнее троичное условие и 448/64 == 7). Итак, давайте перепишем это немного чище:

main(int argc) {
  if (argc^448) main(-(~argc));
  if (argc % 64) {
    putchar((32|-(~7[__TIME__-argc/8%8])[">'txiZ^(~z?"-48]>>(";;;====~$::199")[argc*2&8|argc/64]/(argc&2?1:8)%8&1));
  } else putchar('\n');
}

Теперь 32является десятичным для ASCII-пространства. Он либо печатает пробел, либо '!' (33 - это «!», Следовательно, « &1» в конце). Давайте сосредоточимся на пятне в середине:

-(~(7[__TIME__-argc/8%8][">'txiZ^(~z?"-48]) >>
     (";;;====~$::199"[argc*2&8|argc/64]) / (argc&2?1:8) % 8

Как сказал другой автор, __TIME__это время компиляции для программы и является строкой, так что происходит некоторая строковая арифметика, а также использование преимуществ двунаправленного нижнего индекса массива: a [b] совпадает с b [a] для массивов символов.

7[__TIME__ - (argc/8)%8]

Это выберет один из первых 8 символов в __TIME__. Затем он индексируется в [">'txiZ^(~z?"-48](0-9 символов, 48-57 десятичных). Символы в этой строке должны быть выбраны для их значений ASCII. Эта же символьная манипуляция кодом ASCII продолжается через выражение, что приводит к выводу либо '', либо '!' в зависимости от расположения в глифе персонажа.

chmeee
источник
49

Добавление к другим решениям -~xравно, x+1потому что ~xэквивалентно (0xffffffff-x). Это равно (-1-x)в дополнении 2s, так и -~xесть -(-1-x) = x+1.

Томас Сонг
источник
5
Интересно. Некоторое время я знал, что ~ x == -x - 1, но я не знал математических соображений, стоящих за этим.
Приближается к
3
Эй, Коул, (-1-x) - это то же самое, что (-x-1), вам не нужно «исправлять» это !!
Томас Сонг
7
По той же причине, почему, если кому-то -1338, то это НЕ 1337.
Эндрю Мао
4

Я как можно больше обфускировал арифметику по модулю и удалил рекурсию

int pixelX, line, digit ;
for(line=6; line >= 0; line--){
  for (digit =0; digit<8; digit++){
    for(pixelX=7;pixelX > 0; pixelX--){ 
        putchar(' '| 1 + ">'txiZ^(~z?"["12:34:56"[digit]-'0'] >> 
          (";;;====~$::199"[pixel*2 & 8  | line] / (pixelX&2 ? 1 : 8) ) % 8 & 1);               
    }
  }
  putchar('\n');
}

Расширяя это немного больше:

int pixelX, line, digit, shift;
char shiftChar;
for(line=6; line >= 0; line--){
    for (digit =0; digit<8; digit++){
        for(pixelX=7;pixelX >= 0; pixelX--){ 
            shiftChar = ";;;====~$::199"[pixelX*2 & 8 | line];
            if (pixelX & 2)
                shift = shiftChar & 7;
            else
                shift = shiftChar >> 3;     
            putchar(' '| (">'txiZ^(~z?"["12:34:56"[digit]-'0'] + 1) >> shift & 1 );
        }

    }
    putchar('\n');
}
Лефтерис Е
источник