Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

давайте разберемся

Если скомпилировать и запустить вот эту программу из Obfuscated C Contest, 2006:


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


то она покажет время в таком формате:

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



Как она это делает? Я сознательно не читаю объяснения на stackoverflow и разбираюсь сам; если вы хотите, можете попробовать тоже сами разобраться или проследить мой анализ.

Будем потихоньку приводить программу к читабельному виду. Вместо _ переименуем аргумент main в привычный argc, отделим первую строку и вставим в нее пробелы:


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


Мы помним, что argc при запуске программы без аргументов равен 1 (потому что argv, который тут игнорируется, включает в себя первым элементом имя программы).
Если argc XOR 448 равно нулю, тогда часть после && не будет выполняться, и после длинного вызова putchar() функция завершится. Если же не равно нулю, то выполнится рекурсивный вызов со значением "- ~ argc"; что это такое? ~ это побитовая инверсия, т.е. все единицы в нули и наоборот; и к этому мы применяем арифметический минус.
Вспомним, что в стандартном представлении "дополнение до 2" применить минус это "инверсия всех битов, а потом плюс 1". Значит, "- ~ argc" означает "инверсия, потом еще инверсия, потом плюс 1", или просто +1.

Поскольку argc начинается с 1, условие argc^448 не станет равно нулю, пока argc не вырастет до 448, а дальше он расти уже не будет, потому что не будет рекурсивных вызовов. Значит, это условие можно заменить просто на сравнение.

Неконец, в огромном вызове putchar пока что обратим внимание, что тернарный оператор argc%64? простирается до самого конца.

Следующая версия кода:


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


Мы видим теперь, что общая структура кода такая: сделать 448 вызовов функции main с аргументом argc от 1 до 448, и в каждом таком вызове сделать putchar,
причем благодаря устройству рекурсии первым будет выполнен putchar для argc==448, потом 447 и так далее вниз. Для тех значений argc, которые делятся на 64,
а таких ровно 7 (64*7=448), печатается код переноса строки 10, он же \n. Так мы получаем семь строк на выходе.

На самом деле цикл по сути дела работает от 447 до 0 включительно, а не от 448 до 1, если учесть --argc в самом начале putchar(); так было удобнее написать кратко,
чтобы воспользоваться тем, что argc начнется с 1. Мы можем теперь избавиться от рекурсии и написать нормальный цикл:


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



Ну что ж, после всех этих относительно простых вещей надо разобраться в этом очень странном вызове putchar(). Обратим внимание сначала на то, откуда собственно берется время - очевидно, это __TIME__, которое препроцессор во время компиляции меняет на строку типа "16:16:08" - ровно 8 символов, обратим внимание. Мы знаем, что наш цикл марширует от 447 к 0, и на каждом итерации цикла мы печатаем один символ: либо пробел, либо восклицательный знак, либо перевод строки. В каждой строке вывода у нас есть 64 символа (пробелы или !),
по 8 на каждый из 8 символов, составляющих "16:16:08". Значит, когда переменная цикла двигается от 447 вниз первые 64 раза, то первые восемь раз мы печатаем верхнюю строку символа "1", вторые восемь раз верхнюю строку символа "6", и так далее. Очевидно, странное использование __TIME__ рядом с i/8%8 должно позволить коду выделить тот символ, который сейчас печатается.

Тут мы вспоминаем старый трюк, который в этом коде используется несколько раз, и который не нужен ни для чего, кроме как написания запутанного кода на C/C++: тот факт, что array[index] и index[array] означает одно и то же: первая форма эквивалентна *(array+index), а вторая *(index+array), и это одно и то же. То есть можно написать как a[4], так и 4[a], или, вспомнив, что строка это массив символов, как "abcde"[3], так и 3["abcde"] и это будет значить одно и то же, хоть вторая форма и выглядит очень странно - потому что в выражении *(3+"abcde") сложение передвинет указатель на нужное место, а * возьмет из этого нужного места символ. Мы знаем, что __TIME__ это константная строка, т.е. указатель на char, и -i/8%8 двигает указатель, но оставляет его указателем, поэтому 7[все это] - пример нашего трюка, и мы можем выражение 7[__TIME__-i/8%8] переписать как
(*(__TIME__-(i/8 % 8) + 7)).

Каким образом это выражение вытаскивает из __TIME__ нужный нам символ? Давайте притворимся на секунду, что i движется не от 447 к 0, а по модулю 64, от 63 к 0 в каждой строке. Тогда первые восемь значений, 63...56, должны соответствать __TIME__[0], следующие восемь __TIME__[1] и так далее. Деление i/8 превращает 63...56 в 7, следующие восемь значений в 6 и так до нуля. А потом остаток % 8 убирает все, что осталось от той части i, которая меняется от строки к строке, кратной 64, про которую мы притворились на секунду, что ее нет. Таким образом, (i / 8 % 8) действительно движется от 7 к 0 там, где мы хотим получить __TIME__[0]... __TIME__[7], и поэтому выражение __TIME__ + 7 - (i / 8 % 8) дает ровно то, что надо.

Внесем эти знания в новую версию кода:


main() {
  int i;
  for (i = 447; i >= 0; i--) {
    int row = i/64;   // from 7 to 0
    int col = i % 64; // from 63 to 0
    if (col == 0) 
      putchar('\n');
    else {
      char ch = *(__TIME__ + 7 - col/8);
      putchar(32|-~ch[">'txiZ^(~z?"-48]>>";;;====~$::199"[i*2&8|i/64]/(i&2?1:8)%8&1);
    }
  }
}



Дальше мы смотрим на выражение ch[">'txiZ^(~z?"-48] и видим в нем тот же трюк, что и раньше. ch здесь используется в его числовом значении, ASCII-код символа, и мы знаем, что это либо цифра 0..9 (ASCII-коды 48..57), либо двоеточие ':', ASCII-код 58 (надо же, совсем рядом, как удобно!). То, что коды начинаются с 48, объясняет странное -48 внутри выражения (строго говоря, нарушающее стандарт C, потому что выходит далеко за пределы строки ">'txiZ^(~z?"), и все это выражение, как видно, можно заменить на
">'txiZ^(~z?" [ch-'0'], хотя что именно нам дают эти выглядящие случайно 10 символов, на которые мы заменяем наши исходные 0123456789:, пока непонятно.

Этот символ теперь мы сдвигаем вправо оператором >>, но вначале отметим, что операторы -~ слева от него оба имеют более высокий приоритет, поэтому на самом деле мы сначала увеличиваем код символа на 1 (как мы уже разобрались выше, это то, что делает ~-), а потом сдвигаем. Разделим оставшийся код на несколько строк, чтобы показать лучше, что происходит:


 else {
      char ch = *(__TIME__ + 7 - col/8);
      char code = ">'txiZ^(~z?" [ch-'0'];
      char shift = ";;;====~$::199"[i*2&8|i/64]/(i&2?1:8) % 8;
      putchar(32| (code+1) >> shift & 1);
    }



Итак, мы начинаем понимать, как код печатает представление символа в ASCII. Последнее & 1 гарантирует, что после всех наших вычислений осталось либо 0, либо 1,
и этому мы делаем OR с 32, получая таким образом либо 32 (код пробела), либо 33 (код восклицательного знака), и putchar печатает это. Значит, переменная code,
или точнее code+1, содержит закодированный битмап того, как выглядит каждый из символов 0..9 и двоеточие. В переменной shift вычисляется, на основании текущей
строки и колонки, в каком из битов code+1 содержится указание на то, в этом месте стоит единичка (воскл. знак) или нолик (пробел). С помощью сдвига на shift и
& 1 мы получаем нужный бит.

Но что-то тут не сходится, потому что для каждой цифры битмап должен быть размером 8x7: на выходе для нее выделяется восемь столбцов и семь строк. Т.е. нужно 56
битов, чтобы очевидным образом закодировать такой битмап, а у нас в code+1 никак больше 8 не может быть. Значит, эта информация каким-то образом сжата, и для того,
чтобы разобраться, как, нужно понять вычисление shift.

Магическая строка ";;;====~$::199", и в ней мы берем символ по индексу [i*2&8|i/64]. Что это за индекс? Это OR двух частей, одна из которых - просто номер строки
от 6 до 0 (i/64), а вторая является результатом &8, т.е. она равна либо 0, либо 8, и последнее только в случае, если i*2 содержит единицу в третьем бите, т.е. i
содержит во втором. Весь индекс можно заменить на следующий эквивалентный код: [ (col & 4 ? 8 : 0) + row], и он находится в границах от 0 до 14, как раз чтобы
уместиться в границах магической строки (в ней 14 символов, но адресация по индексу 14 все еще сработает и вернет число 0, т.е. замыкающий '\0'). Чему равно значение col&4? Для столбцов 4,5,6,7 (если брать col по модулю 8, т.е. смотреть внутри данной цифры) оно выполняется, для других нет.

Далее, число, которое мы получаем из магической строки, мы делим либо на 1, либо на 8, т.е. сдвигаем на три бита вправо, и это последнее только если неверно, что i&2.
И наконец, мы берем последние три бита с помощью % 8. Значит, в каждом символе магической строки закодированы два разных значения сдвига - в первых трех битах и следующих трех битах - и мы выбираем между ними с помощью условия i&2, или, что то же самое, col & 2. Номер столбца движется от 63 до 0, но для этого условия можно смотреть на него, как движущийся от 7 до 0 в границах вырисовки данной цифры, и условие соблюдается для значений 2,3,6,7. Для этих четырех столбцов мы будем использовать одно значение сдвига
из магического числа, для остальных другое.

Упрощенный код:


    else {
      char ch = *(__TIME__ + 7 - col/8);
      char code = ">'txiZ^(~z?" [ch-'0'] + 1;
      char shift;
      if (col & 4)
        shift = "$::199"[row];
      else
        shift = ";;;===="[row];
      if (!(col & 2)) shift >>= 3;
      shift = shift % 8;
      putchar(32| code >> shift & 1);
    }



Итак, у нас есть магическое число code, в котором закодированы нолики и единички, представляющие каким-то образом битмап нужной нам цифры. Используя только данные о строке 0..6 и столбце 0..7, но не о самой цифре, мы решаем, на какой из восьми битов code мы хотим сейчас смотреть. Для этого мы используем данные только о втором бите столбца (col & 2)
и третьем бите столбца (col & 4), но не первом. Значит, в нашем выводе восклицательные знаки всегда будут идти парами, что мы и наблюдаем на практике; по сути дела у нас только четыре столбца на цифру, каждый из которых мы повторяем дважды, потому что два раза получаем одно и то же значение shift. Однако остается совсем непонятным, как мы используем эти сдвиги - которые не зависят от цифры - для того, чтобы только восемью битами закодировать битмап цифры, пусть мы теперь и понимаем, что нам нужно не 7*8, а 7*4 = 28 битов для этого. Чтобы это понять получше, давайте вытащим из магических строк сдвигов сами значения; например у ";" ASCII-код 59, в двоичном значении 0x111011, значит она кодирует либо сдвиг 111=7, либо сдвиг 011=3, в зависимости от колонки. Посмотрим, не станет ли понятнее, если мы все эти сдвиги будем адресовать напрямую, а не вытаскивать из символов. Массив shifts[6][4] будет содержать сдвиг в зависимости от строки и битов 2-3 столбца. Чтобы его инициализировать, надо положить в shifts[i][j] либо первые три бита (когда j четное), либо вторые три бита ASCII-кода i-того символа либо в строке "$::199" (когда j>=2), либо в строке ";;;====". Кроме того, надо не забывать, что строки и столбцы все еще идут в нисходящем порядке, обратном тому, что мы видим на экране (напр. когда row==6, мы печатаем первую строку); чтобы вышло нагляднее, построим наш массив в "правильном" порядке, и обратим индексы при обращении к нему:


    else {
      char ch = *(__TIME__ + 7 - col/8);
      char code = ">'txiZ^(~z?" [ch-'0'] + 1;

      char shifts[7][4] = { {0,0,5,7},
                            {1,7,5,7},
                            {1,7,5,7},
                            {1,6,5,7},
                            {2,7,3,7},
                            {2,7,3,7},
                            {4,4,3,7} };
      char shift = shifts[6-row][(7-col%8) >> 1];
      putchar(32| code >> shift & 1);
    }



Теперь мы понимаем, как закодированы битмапы цифр и двоеточия. В массиве shifts во всех местах, где стоит одно и то же значения сдвига, у нас в битмапах ВСЕХ цифр обязано стоять ОДИНАКОВОЕ значение (но у разных цифр разное). Например, в самом правом столбце массива shifts стоят одни семерки; это значит, что на выводе там везде будет стоять седьмой бит числа code данной цифры. У одной цифры этот бит может быть 1, у другой 0, но у любой цифры самый правый столбец из четырех (а если точнее, самые правые два из восьми) будут одинаковыми. На самом деле именно тут все цифры кодируют 0, потому что это используется как пустое место для разграничения цифр. Битмапы цифр и двоеточия кодируются в остальных трех столбцах, а четвертый (и еще два места, которые пустые у всех цифр и где стоит 7 в массив сдвигов) всегда пустой.

Шестерка стоит только в одном месте, и именно там двоеточие кодирует 1, а во всех остальных разрядах 0.

Все остальные цифры вырисованы с помощью того, что какие-то числа из массива сдвигов объявляются 1, а какие-то 0, и массив сдвигов подобран так, чтобы худо-бедно можно было все цифры так нарисовать. Например, единичка "выбирает" сдвиги 5 и 3, и ставит в них 1, и 0 во все остальные; посмотрите в массив выше, и представьте, что вместо 5 и 3 стоит !, а все остальные места пустые - выйдет образ единички. Двойка "выбирает" сдвиги 0,5,6,2,4. Тройка - 0,5,6,3,4 и так далее.

Для того, чтобы все это сделать, нужно было подобрать правильный массив shifts, позволяющий таким путем найти хороший образ для каждой цифры и двоеточия; как это было сделано? Я подозреваю, что вручную. Это не так тяжело, как кажется, особенно если заметить, что строки 1-2 и 4-5 идентичны, они просто удлиняют в высоту все цифры, так что дизайн можно было делать без них. Кроме того, правый столбец из четырех заранее отводится под пустое место. Так что надо было начать с квадрата 3x5 и нарисовать на нем все цифры примерно так:

***      *    ***
  *      *    * *
 **      *    ***
  *      *    * *
***      *    ***


а потом разобраться с тем, какие у них есть общие участки, и как можно выделить только 6 общих участков, чтобы все цифры можно было построить, сочетая именно
эти шесть (шесть, потому что одно значение из восьми зарезервировано под правую пустую колонку, и одно нужно для двоеточия). Это, наверное, было сделано вручную.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 24 comments