Реверс-инжиниринг одной строчки JavaScript
- суббота, 15 июля 2017 г. в 03:12:58
https://habrahabr.ru/post/333372/
Несколько месяцев назад я получил от друга такое письмо:
Тема: Можешь развернуть и объяснить мне эту одну строчку кода?
Текст:Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.
Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.
Вызов принят!
Первым делом я оставил HTML в HTML, код JavaScript перенёс в файл
index.html
Я заметил, что там переменная
code.js
Далее,
Ещё я заметил, что элемент
Затем я объявил переменные
Я разложил цикл
Здесь я развернул троичный оператор
Это значение (индекс) используется для сдвига строки P, так что назовём
Я разложил
Здесь хитрый способ проверки на чётность результата в круглых скобках, когда для чётного значения возвращается 0, а для нечётного — 1.
Следовательно,
Другими словами, пятёрка — нечётное число, а результатом 5 AND 1 (5 & 1) будет 1. В консоли JavaScript легко проверить соблюдение этой логики.
Обратите внимание, что я также переименовал остальную часть
Далее я развернул
Я разобрался с оператором
Я также переименовал
И последнее, но не менее важное, я поместил круглые скобки в
Уточнение: Мне указали, что я ошибочно поместил
Окончательный результат выполнения можно увидеть здесь.
Так что здесь происходит? Давайте разберёмся.
Изначально значение
Изображение состоит из 32 строк, со 128 символами в каждой. Очень удобно, что 64 × 64 = 32 ×128 = 4096. Значение
Но когда устанавливать
Ну, для начала нам точно известно, что следует установить
Но когда
Если убрать
Теперь посмотрим на
Обратите внимание, что получается в каждом цикле:
Другими словами, мы может выразить
В таком случае мы можем переписать
Используем онлайновый графический калькулятор для отрисовки графиков некоторых из этих функций.
Прежде всего, отрисуем
Выходит симпатичный график со значениями y от 0 до 2.
Если отрисовать
Если отрисовать всю левую сторону выражения, то получится график, который выглядит как сочетание двух предыдущих.
В конце концов, если мы отрисуем две функции рядом друг с другом, то увидим следующее.
Давайте припомним вопрос, на который мы пытаемся ответить, то есть каким образом получилась такая красивая статическая картинка:
Мы знаем, что если «магия»
Увеличим первые 16 строк нашего графика, где
Побитовый XOR в JavaScript отбросит все значения справа от запятой, так что это равнозначно применению метода
Он вернёт 0, если оба бита равны 1 или оба равны 0.
Наша
Другими словами, каждая зелёная диагональ представляет собой один ряд в нашем графике. Поскольку для первых 16 рядов значение j всегда больше 1, но меньше 2, то мы можем получить нечётное значение только в том случае, если левая сторона выражения
Вот некоторые результаты из консоли JavaScript, чтобы посмотреть результаты вычислений: 0 или −2 означают, что результат чётный, а 1 соответствует нечётному числу.
Если посмотреть на наш график, то там самая правая диагональная линия едва выходит выше 1 и ниже −1 (мало чётных чисел — мало символов
После 16-й строки значение
Если присмотреться к нескольким самым нижним линиям в анимированной картинке, то вы заметите, что они не следуют одному и тому же шаблону из-за большой флуктуации графика.
Теперь вернёмся к
После достижения значения 64 график изменяется следующим образом.
Обратите внимание, что
Рендеринг HTML для такого условия выглядит следующим образом (вы можете жёстко вбить значение
К этому моменту количество символов
Для примера, когда
Обратите внимание, что диагональ для первого ряда (около отметки 64) сдвинулась примерно на один маленький квадратик вверх. Поскольку четыре больших квадратов представляют собой 128 символов, в одном большом квадрате будет 32 символа, а в одном маленьком квадрате 32/5 = 6,4 сивола (примерно). Если посмотрим на рендеринг HTML, то там первый ряд действительно сдвинулся вправо на 7 символов.
И один последний пример. Вот что происходит, если вызвать setInterval ещё семь раз, а
Для первого ряда
Выглядеть это будет так.
График бесконечно зациклен.
Надеюсь, наша работа имеет какой-то смысл. Вряд ли я когда-нибудь смог бы самостоятельно придумать нечто подобное, но было интересно разобраться в этом коде.
- Реверс-инжиниринг
- Ненормальное программирование
- Занимательные задачки
- Визуализация данных
- JavaScript
Несколько месяцев назад я получил от друга такое письмо:
Тема: Можешь развернуть и объяснить мне эту одну строчку кода?
Текст:Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.
<pre id=p><script>n=setInterval("for(n+=7,i=k,P='p.\\n';i-=1/k;P+=P[i%2?(i%2*j-j+n/k^j)&1:2])j=k/i;p.innerHTML=P",k=64)</script>Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.
Вызов принят!
Часть I. Извлекаем читаемый код
Первым делом я оставил HTML в HTML, код JavaScript перенёс в файл
code.js, а p закавычил в id="p".index.html
<script src="code.js"></script>
<pre id="p"></pre>Я заметил, что там переменная
k — просто константа, так что убрал её из строчки и переименовал в delay.code.js
var delay = 64;
var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var n = setInterval(draw, delay);Далее,
var draw был просто строкой, которая исполнялась как функция eval с периодичностью setInterval, поскольку setInterval может принимать и функции, и строки. Я перенёс var draw в явную функцию, но сохранил изначальную строку для справки на всякий случай.Ещё я заметил, что элемент
p в действительности ссылался на элемент DOM с идентификатором p, объявленным в HTML, который я недавно закавычил. Оказывается, на элементы в JavaScript можно ссылаться по их идентификатору, если id состоит только из букв и цифр. Я добавил document.getElementById("p"), чтобы сделать код понятнее.var delay = 64;
var p = document.getElementById("p"); // < --------------
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
for (n += 7, i = delay, P = 'p.\n'; i -= 1 / delay; P += P[i % 2 ? (i % 2 * j - j + n / delay ^ j) & 1 : 2]) {
j = delay / i; p.innerHTML = P;
}
};
var n = setInterval(draw, delay);Затем я объявил переменные
i, p и j и перенёс их в начало функции.var delay = 64;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
var i = delay; // < ---------------
var P ='p.\n';
var j;
for (n += 7; i > 0 ;P += P[i % 2 ? (i % 2 * j - j + n / delay ^ j) & 1 : 2]) {
j = delay / i; p.innerHTML = P;
i -= 1 / delay;
}
};
var n = setInterval(draw, delay);Я разложил цикл
for и преобразовал его в цикл while. Из трёх частей прежнего for осталась только одна часть CHECK_EVERY_LOOP, а всё остальное (RUNS_ONCE_ON_INIT; DO_EVERY_LOOP) перенёс за пределы цикла.var delay = 64;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
var i = delay;
var P ='p.\n';
var j;
n += 7;
while (i > 0) { // <----------------------
//Update HTML
p.innerHTML = P;
j = delay / i;
i -= 1 / delay;
P += P[i % 2 ? (i % 2 * j - j + n / delay ^ j) & 1 : 2];
}
};
var n = setInterval(draw, delay);Здесь я развернул троичный оператор
( condition ? do if true : do if false) in P += P[i % 2 ? (i % 2 * j - j + n / delay ^ j) & 1 : 2];.i%2 проверяет, является переменная i чётной или нечётной. Если она четная, то просто возвращает 2. Если нечётная, то возвращает «магическое» значение magic (i % 2 * j - j + n / delay ^ j) & 1; (подробнее об этом чуть позже).Это значение (индекс) используется для сдвига строки P, так что назовём
index и превратим строку в P += P[index];.var delay = 64;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
var i = delay;
var P ='p.\n';
var j;
n += 7;
while (i > 0) {
//Update HTML
p.innerHTML = P;
j = delay / i;
i -= 1 / delay;
let index;
let iIsOdd = (i % 2 != 0); // <---------------
if (iIsOdd) { // <---------------
index = (i % 2 * j - j + n / delay ^ j) & 1;
} else {
index = 2;
}
P += P[index];
}
};
var n = setInterval(draw, delay);Я разложил
& 1 из значения index = (i % 2 * j - j + n / delay ^ j) & 1 в ещё один оператор if.Здесь хитрый способ проверки на чётность результата в круглых скобках, когда для чётного значения возвращается 0, а для нечётного — 1.
& — это побитовый оператор AND. Он работает так:- 1 & 1 = 1
- 0 & 1 = 0
Следовательно,
something & 1 преобразует "something" в двоичное представление, а также добивает перед единицей необходимое количество нулей, чтобы соответствовать размеру "something", и возвращает просто результат AND последнего бита. Например, 5 в двоичном формате равняется 101, так что если мы применим на ней логическую операцию AND с единицей, то получится следующее: 101
AND 001
001Другими словами, пятёрка — нечётное число, а результатом 5 AND 1 (5 & 1) будет 1. В консоли JavaScript легко проверить соблюдение этой логики.
0 & 1 // 0 - even return 0
1 & 1 // 1 - odd return 1
2 & 1 // 0 - even return 0
3 & 1 // 1 - odd return 1
4 & 1 // 0 - even return 0
5 & 1 // 1 - odd return 1Обратите внимание, что я также переименовал остальную часть
index в magic, так что код с развёрнутым &1 будет выглядеть следующим образом:var delay = 64;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
var i = delay;
var P ='p.\n';
var j;
n += 7;
while (i > 0) {
//Update HTML
p.innerHTML = P;
j = delay / i;
i -= 1 / delay;
let index;
let iIsOdd = (i % 2 != 0);
if (iIsOdd) {
let magic = (i % 2 * j - j + n / delay ^ j);
let magicIsOdd = (magic % 2 != 0); // &1 < --------------------------
if (magicIsOdd) { // &1 <--------------------------
index = 1;
} else {
index = 0;
}
} else {
index = 2;
}
P += P[index];
}
};
var n = setInterval(draw, delay);Далее я развернул
P += P[index]; в оператор switch. К этому моменту стало понятно, что index может принимать только одно из трёх значений — 0, 1 или 2. Также понятно, что переменная P всегда инициализируется со значениями var P ='p.\n';, где 0 указывает на p, 1 указывает на ., а 2 указывает на \n — символ новой строкиvar delay = 64;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
var draw = function() {
var i = delay;
var P ='p.\n';
var j;
n += 7;
while (i > 0) {
//Update HTML
p.innerHTML = P;
j = delay / i;
i -= 1 / delay;
let index;
let iIsOdd = (i % 2 != 0);
if (iIsOdd) {
let magic = (i % 2 * j - j + n / delay ^ j);
let magicIsOdd = (magic % 2 != 0); // &1
if (magicIsOdd) { // &1
index = 1;
} else {
index = 0;
}
} else {
index = 2;
}
switch (index) { // P += P[index]; <-----------------------
case 0:
P += "p"; // aka P[0]
break;
case 1:
P += "."; // aka P[1]
break;
case 2:
P += "\n"; // aka P[2]
}
}
};
var n = setInterval(draw, delay);Я разобрался с оператором
var n = setInterval(draw, delay);. Метод setInterval возвращает целые числа, начиная с единицы, увеличивая значение при каждом вызове. Это целое число может использоваться для clearInterval (то есть для отмены). В нашем случае setInterval вызывается всего один раз, а переменная n просто установилась в значение 1.Я также переименовал
delay в DELAY для напоминания, что это всего лишь константа.И последнее, но не менее важное, я поместил круглые скобки в
i % 2 * j - j + n / DELAY ^ j для указания, что у ^ (побитового XOR) меньший приоритет, чем у операторов %, *, −, + и /. Другими словами, сначала выполнятся все вышеупомянутые вычисления, а уже потом ^. То есть получается (i % 2 * j - j + n / DELAY) ^ j).Уточнение: Мне указали, что я ошибочно поместил
p.innerHTML = P; //Update HTML в цикл, так что я убрал его оттуда.const DELAY = 64; // approximately 15 frames per second 15 frames per second * 64 seconds = 960 frames
var n = 1;
var p = document.getElementById("p");
// var draw = "for(n+=7,i=delay,P='p.\\n';i-=1/delay;P+=P[i%2?(i%2*j-j+n/delay^j)&1:2])j=delay/i;p.innerHTML=P";
/**
* Draws a picture
* 128 chars by 32 chars = total 4096 chars
*/
var draw = function() {
var i = DELAY; // 64
var P ='p.\n'; // First line, reference for chars to use
var j;
n += 7;
while (i > 0) {
j = DELAY / i;
i -= 1 / DELAY;
let index;
let iIsOdd = (i % 2 != 0);
if (iIsOdd) {
let magic = ((i % 2 * j - j + n / DELAY) ^ j); // < ------------------
let magicIsOdd = (magic % 2 != 0); // &1
if (magicIsOdd) { // &1
index = 1;
} else {
index = 0;
}
} else {
index = 2;
}
switch (index) { // P += P[index];
case 0:
P += "p"; // aka P[0]
break;
case 1:
P += "."; // aka P[1]
break;
case 2:
P += "\n"; // aka P[2]
}
}
//Update HTML
p.innerHTML = P;
};
setInterval(draw, 64);Окончательный результат выполнения можно увидеть здесь.
Часть 2. Понимание кода
Так что здесь происходит? Давайте разберёмся.
Изначально значение
i установлено на 64 посредством var i = DELAY;, а затем каждый цикл оно уменьшается на 1/64 (0,015625) через i -= 1 / DELAY;. Цикл продолжается, пока i больше нуля (код while (i > 0) {). Поскольку за каждый проход i уменьшается на 1/64, то требуется 64 цикла, прежде чем оно уменьшится на единицу (64/64 = 1). В целом уменьшение i произойдёт 64×64 = 4096 раз, чтобы уменьшиться до нуля.Изображение состоит из 32 строк, со 128 символами в каждой. Очень удобно, что 64 × 64 = 32 ×128 = 4096. Значение
i может быть чётным (не нечётным let iIsOdd = (i % 2 != 0);), если i является строго чётным числом. Такое произойдёт 32 раза, когда оно равняется 64, 62, 60 и т. д. Эти 32 раза index примет значение 2 index = 2;, а к строке добавится символ новой строки: P += "\n"; // aka P[2]. Остальные 127 символов в строке примут значения p или ..Но когда устанавливать
p, а когда .?Ну, для начала нам точно известно, что следует установить
. при нечётном значении let magic = ((i % 2 * j - j + n / DELAY) ^ j);, или установить p, если «магия» чётная.var P ='p.\n';
...
if (magicIsOdd) { // &1
index = 1; // second char in P - .
} else {
index = 0; // first char in P - p
}Но когда
magic чётное, а когда нечётное? Это вопрос на миллион долларов. Перед тем как перейти к нему, давайте определим ещё кое-что.Если убрать
+ n/DELAY из let magic = ((i % 2 * j - j + n / DELAY) ^ j);, то получится статическая картинка, на которой вообще ничего не двигается:Теперь посмотрим на
magic без + n/DELAY. Как получилась эта красивая картинка?(i % 2 * j - j) ^ j Обратите внимание, что получается в каждом цикле:
j = DELAY / i;
i -= 1 / DELAY;Другими словами, мы может выразить
j через конечное i как j = DELAY/ (i + 1/DELAY). Но поскольку 1/DELAY слишком малое число, то для этого примера можно отбросить + 1/DELAY и упростить выражение до j = DELAY/i = 64/i.В таком случае мы можем переписать
(i % 2 * j - j) ^ j как i % 2 * 64/i - 64/i) ^ 64/i.Используем онлайновый графический калькулятор для отрисовки графиков некоторых из этих функций.
Прежде всего, отрисуем
i%2.Выходит симпатичный график со значениями y от 0 до 2.
Если отрисовать
64/i, то получим такой график:Если отрисовать всю левую сторону выражения, то получится график, который выглядит как сочетание двух предыдущих.
В конце концов, если мы отрисуем две функции рядом друг с другом, то увидим следующее.
О чём говорят эти графики?
Давайте припомним вопрос, на который мы пытаемся ответить, то есть каким образом получилась такая красивая статическая картинка:
Мы знаем, что если «магия»
(i % 2 * j - j) ^ j принимает чётное значение, то нужно добавить p, а для нечётного числа нужно добавить ..Увеличим первые 16 строк нашего графика, где
i имеет значения от 64 до 32.Побитовый XOR в JavaScript отбросит все значения справа от запятой, так что это равнозначно применению метода
Math.floor, который округляет число в меньшую сторону.Он вернёт 0, если оба бита равны 1 или оба равны 0.
Наша
j начинается с единицы и медленно продвигается к двойке, останавливаясь прямо около неё, так что можем считать её всегда единицей при округлении в меньшую сторону (Math.floor(1.9999) === 1), и нам нужна ещё одна единица с левой стороны, чтобы получить в результате ноль и дать нам p.Другими словами, каждая зелёная диагональ представляет собой один ряд в нашем графике. Поскольку для первых 16 рядов значение j всегда больше 1, но меньше 2, то мы можем получить нечётное значение только в том случае, если левая сторона выражения
(i % 2 * j - j) ^ j, она же i % 2 * i/64 — i/64, то есть зелёная диагональ, тоже будет выше 1 или ниже −1.Вот некоторые результаты из консоли JavaScript, чтобы посмотреть результаты вычислений: 0 или −2 означают, что результат чётный, а 1 соответствует нечётному числу.
1 ^ 1 // 0 - even p
1.1 ^ 1.1 // 0 - even p
0.9 ^ 1 // 1 - odd .
0 ^ 1 // 1 - odd .
-1 ^ 1 // -2 - even p
-1.1 ^ 1.1 // -2 - even pЕсли посмотреть на наш график, то там самая правая диагональная линия едва выходит выше 1 и ниже −1 (мало чётных чисел — мало символов
p). Следующая выходит чуть дальше за эти границы, третья — ещё чуть дальше и т. д. Линия номер 16 едва удерживается в границах между 2 и −2. После линии 16 мы видим, что наш статический график меняет свой характер.После 16-й строки значение
j пересекает лимит 2, так что меняется ожидаемый результат. Теперь мы получим чётное число, если зелёная диагональная линия выше 2 или ниже −2, или внутри рамок 1 и −1, но не соприкасается с ними. Вот почему мы видим на картинке две или больше групп символов p начиная с 17-й строки.Если присмотреться к нескольким самым нижним линиям в анимированной картинке, то вы заметите, что они не следуют одному и тому же шаблону из-за большой флуктуации графика.
Теперь вернёмся к
+ n/DELAY. В коде мы видим, что значение n начинается с 8 (1 от setInteval и плюс 7 на каждый вызов метода). Затем оно увеличивается на 7 при каждом срабатывании setInteval. После достижения значения 64 график изменяется следующим образом.
Обратите внимание, что
j по-прежнему находится около единицы, но теперь левая половина красной диагонали в пределах примерно 62-63 находится примерно около нуля, а правая половина в пределах примерно 63-64 — около единицы. Поскольку наши символы появляются в убывающем порядке от 64 к 62, то можно ожидать, что правая половина диагонали в районе 63-64 (1 ^ 1 = 0 // even) добавит кучку символов p, а левая половина диагонали в районе 62-63 (1 ^ 0 = 1 // odd) добавит кучку точек. Всё это будет нарастать слева направо, как обычный текст.Рендеринг HTML для такого условия выглядит следующим образом (вы можете жёстко вбить значение
n в редакторе CodePen и посмотреть). Это совпадает с нашими ожиданиями.К этому моменту количество символов
p выросло до постоянной величины. Например, в первом ряду половина всех значений всегда будут чётными. Теперь символы p и . будут только меняться местами.Для примера, когда
n увеличивается на 7 на следующем вызове setInterval, график немного изменится.Обратите внимание, что диагональ для первого ряда (около отметки 64) сдвинулась примерно на один маленький квадратик вверх. Поскольку четыре больших квадратов представляют собой 128 символов, в одном большом квадрате будет 32 символа, а в одном маленьком квадрате 32/5 = 6,4 сивола (примерно). Если посмотрим на рендеринг HTML, то там первый ряд действительно сдвинулся вправо на 7 символов.
И один последний пример. Вот что происходит, если вызвать setInterval ещё семь раз, а
n будет равняться 64+9×7.Для первого ряда
j по-прежнему равняется 1. Теперь верхняя половина красной диагонали около отметки 64 примерно упирается в два, а нижний конец около единицы. Это переворачивает картинку в другую сторону, поскольку теперь 1^2 = 3 // odd - . и 1 ^ 1 = 0 //even - p. Так что можно ожидать кучу точек, за которыми пойдут символы p.Выглядеть это будет так.
График бесконечно зациклен.
Надеюсь, наша работа имеет какой-то смысл. Вряд ли я когда-нибудь смог бы самостоятельно придумать нечто подобное, но было интересно разобраться в этом коде.