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

Как работает эта 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]

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

Отступ:

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);}

мы получили

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

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

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

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 продолжается через выражение, что приводит к выводу либо '', либо '!' в зависимости от расположения в глифе персонажа.

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

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

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');
}