▍ Введение

Наш первый «компилятор WebAssembly в твите» имел длину 269 байт; с тех пор мы смогли снизить её всего до 192 байтов.

В результате мы получили компилятор, получающий арифметическое выражение, записанное в обратной польской нотации, и компилирующий его в валидный модуль WebAssembly. Этот модуль экспортирует одну функцию, которая возвращает результат исходного арифметического выражения. Компилятор выглядит так:

let c=(b,l)=>WebAssembly.instantiate(new Int8Array(
[,97,115,109,1,,,,1,5,1,96,,1,127,3,2,1,,7,4,1,,,,10,
l=(b=b.split` `.flatMap(t=>t>-1?[65,t]:107+'-*/'.indexOf(t)))
.length+4,1,l-2,,...b,11]))

А вот пример его использования:

(await c('11 11 1 - + 4 * 2 /')).instance.exports['']()

Но это не просто хитрый трюк — если вы начнёте разбираться, как работает этот код, то на удивление много узнаете о WebAssembly! В этом посте мы объясним, как это всё работает, пошагово деобфусцируя код.

С кодом из поста можно поэкспериментировать здесь: stackblitz.com/edit/rpn-to-wasm-js-compiler.

▍ Форматирование

Первым делом для повышения читаемости мы можем отформатировать код:

let c1 = (b, l) =>
  WebAssembly.instantiate(
    new Int8Array([
      , 97, 115, 109, 1, , , , 1, 5, 1, 96, , 1, 127, 3, 2, 1, , 7, 4, 1, , , , 10,
      (l = (b = b.split` `.flatMap(
            (t) => t > -1 ? [65, t] : 107 + "-*/".indexOf(t)
           )).length + 4),
      1, l - 2, , ...b, 11
    ])
  );

Он по-прежнему непонятен, но мы хотя бы можем определить отдельные части кода.

Если вкратце, мы выполняем очень простой «парсинг» выражения, превращая его в байт-код Wasm, а затем вручную превращаем байты в модуль из одной функции.

В более сложном компиляторе мы бы, вероятно, использовали библиотеку для генерации модуля WebAssembly и компиляции выражений, но наша главная метрика — это размер кода, поэтому мы записываем байты непосредственно в массив.

▍ Убираем выражение присваивания

Первый трюк, от которого нужно избавиться — это выражение присваивания.

Оператор присваивания в JavaScript — это выражение. То есть он генерирует результат после вычислений. Это видно из примеров:

let a, b;
console.log('a', a = 42);
a = b = 43;
console.log('b', b);

Этот код вернёт следующее:

a 42
b 43

Причина этого в том, что a = 42 присваивает значение 42 переменной a, а результатом всего выражения присваивания становится присваиваемое значение.

В a = b = 43 мы присваиваем результат вычисления b = 43 переменной a. Проще будет понять эквивалентное этому выражение: a = (b = 43).

В нашем коде мы используем этот трюк для многократного использования переменных и обновления их значений в местах, где мы также можем использовать присваиваемое значение. Кроме того, это также позволяет нам реализовать компилятор в одном выражении, избежав необходимости в фигурных скобках, точках с запятой и операторах возврата.

Чтобы откатить этот трюк, мы превратим тело нашей функции в блок и выполним каждое присваивание в отдельной строке:

let c2 = (b, l) => {
  b = b.split` `.flatMap(
    (t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))
  );
  l = b.length + 4;
  return WebAssembly.instantiate(
    new Int8Array([
      , 97, 115, 109, 1, , , , 1, 5, 1, 96, , 1, 127, 3, 2, 1, , 7, 4, 1, , , ,
      10, l, 1, l - 2, , ...b, 11
    ]),
  );
};

▍ Откатываем трюки с переменными

Теперь нам проще идентифицировать присваивания, но смысл переменных и аргументов функции понять по-прежнему сложно. Давайте это исправим, отказавшись от пары трюков с переменными.

Первым делом мы перестанем использовать однобуквенные переменные, заменив их имена на более понятные. На следующем шаге мы перестанем использовать переменные многократно: например, изначально в b хранится код для компиляции, но когда он становится не нужен, мы используем переменную повторно для хранения команд байт-кода.

Чтобы откатить это, добавим новую переменную instrs и переименуем b в code. Также изменим имя l на len. Эта переменная содержит значение, близкое к количеству байт-кодов.

Объявив l в теле, мы можем убрать её из списка аргументов функции. Изначально это нужно было для того, чтобы не пришлось объявлять её при помощи let или const, сэкономить несколько байтов и избавиться от необходимости тела функции.

Трюк работает так: мы добавляем неиспользованные аргументы к концу списка аргументов функции и используем их в качестве локальных переменных. Функция компилятора ожидает с кодом один аргумент; l мы используем, потому что не ожидаем, что вызывающая сторона задаст этой переменной значение.

Вот как будет выглядеть код без этого трюка:

let c3 = (code) => {
  const instrs = code.split` `.flatMap(
    (t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))
  );
  const len = instrs.length + 4;
  return WebAssembly.instantiate(
    new Int8Array([
      , 97, 115, 109, 1, , , , 1, 5, 1, 96, , 1, 127, 3, 2, 1, , 7, 4, 1, , , ,
      10, len, 1, len - 2, , ...instrs, 11
    ]),
  );
};

▍ Добавляем недостающие нули

Если посмотреть на массив в нашем коде, то можно заметить, что в нём есть много запятых, за которыми идёт другая запятая, а не значение. Такой синтаксис определяет разреженные массивы. Вот пример:

const a1 = [,,];
console.log(a1.length); // Вывод: 2
console.log(a1); // Вывод: [ <2 пустых элемента> ]

Это эквивалентно следующему:

const a2 = new Array(2);
console.log(a2.length); // Вывод: 2
console.log(a2); // Вывод: [ <2 пустых элемента> ]

Мы используем этот синтаксический трюк, чтобы экономить один байт каждый раз, когда нам нужно, чтобы в массиве встречался 0. Это работает, потому что Typed Array автоматически преобразуют элементы массивов в числа, а «пустой элемент» преобразуется в 0.

new Int8Array([0, null, undefined,,0])

даст нам следующее:

Int8Array(5) [ 0, 0, 0, 0, 0 ]

Давайте откажемся от этого трюка, вернув все нули:

let c4 = (code) => {
  const instrs = code.split` `.flatMap(
    (t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))
  );
  const len = instrs.length + 4;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, len, 1, len - 2, 0, ...instrs, 11
    ]),
  );
};

▍ Удалим лишние 4 байта в определении длины

В нашем коде есть переменная len, содержащая число, близкое к количеству байт-кодов в скомпилированном выражении, но не равно ему точно:

  const len = instrs.length + 4;

В модуле WebAssembly нам нужно использовать количество байтов в теле функции (вычисляемое выражение) в двух местах:

• Чтобы задать длину раздела кода.
• Чтобы задать длину тела функции.

Так как в разделе кода есть только одна функция, оба значения близки:

• Раздел занимает два дополнительных байта (идентификатор раздела и количество элементов кода).
• Тело функции занимает ещё два байта (количество локальных переменных и команда end).

Чтобы не писать b.length дважды, мы присваиваем l значение b.length + 4 в месте, где нужен подсчёт байтов раздела кода, а затем вычисляем l - 2 (b.length + 2) там, где нам нужен подсчёт байтов тела функции.

[
  ...
  l=(b=b.split` `.flatMap(t=>t>-1?[65,t]:107+'-*/'.indexOf(t))).length+4,1,l-2
  ...
]

Всё это трюк, позволяющий не записывать b.length дважды.

Давайте присвоим значение длины переменной len, и в каждом из мест вычислим точное значение:

let c5 = (code) => {
  const instrs = code.split` `.flatMap(
    (t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))
  );
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

▍ Удаляем строковый шаблонный литерал, используемый вместо вызова функции

Следующий трюк, который нужно откатить — это code.split` `. В данном случае мы используем фичу Tagged Template литерала String Template Literal.

Давайте посмотрим, как это работает, создав простой tagged template, преобразующий строку в верхний регистр:

function upper(s) {
  return s[0].toUpperCase();
}

и использовав его:

upper`Hello, World!`
> "HELLO, WORLD!"

Как видите, первый аргумент функции tagged template — это массив. К счастью, первый аргумент String.prototype.split обрабатывается следующим образом:

Все значения, не являющиеся неопределёнными, и объекты с методом [Symbol.split]() автоматически преобразуются в строки.

А автоматическое преобразование массива с одной строкой внутри эквивалентно самой строке:

["hello"].toString()
> "hello"

[" "].toString()
> " "

Так как функция, которую нам нужно вызывать, принимает один строковый аргумент, мы можем использовать её как tagged template и сэкономить скобки в вызове функции.

Давайте перепишем это в виде вызова функции:

let c6 = (code) => {
  const instrs = code.split(' ').flatMap(
    (t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))
  );
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

▍ Избавляемся от тернарного оператора

Теперь откатим тернарный оператор, превратив его в конструкцию if.

Тернарный оператор содержит выражения на каждой из ветвей, позволяя нам сэкономить на return. Вот как будет выглядеть код, если вместо него мы используем конструкцию if:

let c7 = (code) => {
  const instrs = code.split(" ").flatMap((t) => {
    if (t > -1) {
      return [65, t];
    } else {
      return 107 + "-*/".indexOf(t);
    }
  });
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

▍ Убираем проверку чисел при помощи автоматического преобразования типов

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

    if (t > -1) {
      return [65, t];
    }

Сначала мы используем автоматическое преобразование типов (coercion) в t > -1, чтобы проверить, является ли токен t строкой, представляющей положительное число. Затем мы повторно используем автоматическое преобразование типов в [65, t], чтобы JavaScript мог преобразовать t в Number в Int8Array:

new Int8Array([65, '42'])

Результатом этого будет следующее:

Int8Array(2) [ 65, 42 ]

Давайте перепишем парсинг и проверку в явном виде:

let c8 = (code) => {
  const instrs = code.split(" ").flatMap((t) => {
    const num = parseInt(t, 10);
    if (Number.isFinite(num)) {
      return [65, num];
    } else {
      return 107 + "-*/".indexOf(t);
    }
  });
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

Здесь семантика нашего компилятора немного меняется. Исходная версия принимала в качестве входных данных только положительные целые числа; если необходимо отрицательное целое, то нужно вычесть из нуля: 0 - 1, чтобы получить -1. Новая версия допускает отрицательные числа, потому что она выполняет проверку с помощью Number.isFinite(num) а не t > -1.

▍ Избавляемся от трюка с indexOf -1

Следующий трюк находится в ветви else:

      return 107 + "-*/".indexOf(t);

Наш компилятор калькулятора принимает только четыре арифметические операции: +, -, * и /. Но в приведённом выше коде мы видим только три: -*/ и магическое число: 107. Вот как это работает — это номера байт-кодов для арифметических операций в WebAssembly:

• +: 106,
• -: 107,
• *: 108,
• /: 109.

Мы попадаем в эту ветвь, только если токен t не является числом, то есть он может быть только одним из приведённых выше арифметических операторов. То есть для каждого символа, являющегося одной из четырёх операций, мы хотим сгенерировать соответствующий опкод.

Мы могли бы записать 106 + "+-*/".indexOf(t). Так мы находим индекс символа в строке:

• +: 0,
• -: 1,
• *: 2,
• /: 3.

…и прибавить к нему 106, чтобы получить номер байт-кода. Но если t — не строка, то "+-*/" indexOf возвращает -1. Мы можем этим воспользоваться, считая -1 «плюсом или любым другим токеном»:

• +: -1 (любой другой токен тоже будет -1),
• -: 0,
• *: 1,
• /: 2.

И поэтому мы добавили 107 вместо 106. Давайте избавимся от трюка с -1:

let c9 = (code) => {
  const instrs = code.split(" ").flatMap((t) => {
    const num = parseInt(t, 10);
    if (Number.isFinite(num)) {
      return [65, num];
    } else {
      return 106 + "+-*/".indexOf(t);
    }
  });
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

Семантика здесь снова немного меняется. Если ранее не удавалось найти токен t, то значением выражения становилось 107 + -1, что соответствовало сложению. Теперь значением станет 106 + -1, что соответствует байт-коду 105, то есть команде popcnt.

Но не волнуйтесь, на следующем шаге мы это исправим.

▍ Убираем трюк с indexOf

Разобравшись, как работает трюк с indexOf, и убрав часть с -1, давайте полностью избавимся от этого трюка. Для этого мы создадим объект, который будет сопоставлять токен арифметической операции с её байт-кодом:

const OP_TO_BYTECODE = {
  "+": 106,
  "-": 107,
  "*": 108,
  "/": 109,
};

let c10 = (code) => {
  const instrs = code.split(" ").flatMap((t) => {
    const num = parseInt(t, 10);
    if (Number.isFinite(num)) {
      return [65, num];
    } else {
      return OP_TO_BYTECODE[t] ?? 106;
    }
  });
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

Чтобы сохранить исходную семантику, если токен не является валидной операцией, будем возвращать байт-код для +: в OP_TO_BYTECODE[t] ?? 106.

▍ Избавляемся от пустого имени экспорта

В примере из начала статьи можно заметить, что имя экспортируемой функции представляет собой пустую строку:

(await c('11 11 1 - + 4 * 2 /')).instance.exports['']()

Мы сделали это, чтобы сэкономить байты, необходимые для указания имени экспорта, но также для экономии на лишнем байте/символе в коде, потому что если длина имени экспорта равна 0, то мы можем использовать синтаксис разреженного массива и оставить пустое место в массиве модуля WebAssembly.

Чтобы откатить этот трюк, мы назовём экспортируемую функцию a, что в UTF-8 соответствует байту 97:

> new TextEncoder().encode('a')[0]
97

const OP_TO_BYTECODE = {
  "+": 106,
  "-": 107,
  "*": 108,
  "/": 109,
};

let c11 = (code) => {
  const instrs = code.split(" ").flatMap((t) => {
    const num = parseInt(t, 10);
    if (Number.isFinite(num)) {
      return [65, num];
    } else {
      return OP_TO_BYTECODE[t] ?? 106;
    }
  });
  const len = instrs.length;
  return WebAssembly.instantiate(
    new Int8Array([
      0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 5, 1, 1, 97, 0, 0,
      10, 4 + len, 1, 2 + len, 0, ...instrs, 11
    ]),
  );
};

Теперь мы сможем вызывать её по более удобному имени:

(await c11('11 11 1 - + 4 * 2 /')).instance.exports.a()

▍ Неявные решения

Наша исходная реализация поддерживала только положительные числа, но это не единственное числовое ограничение в компиляторе.

Чтобы минимизировать размер модулей WebAssembly, числа кодируются алгоритмом кодирования с переменной длиной LEB128. Взглянув на часть кода, кодирующую числа, можно понять, что мы не реализуем алгоритм целиком: [65,t]. Мы предполагаем, что кодируемое число умещается в 7 битов — кратчайшее представление в LEB128.

Давайте проверим пределы нашей реализации:

(await c('63')).instance.exports['']();

> 63

(await c('64')).instance.exports['']();

> -64

Это значит, что корректно будут парситься только числа от 0 до 63.

(await c('127')).instance.exports['']();

> -1

Команда

(await c('128')).instance.exports['']();

Вылетает с ошибкой:

Uncaught CompileError: WebAssembly.instantiate(): Compiling function #0 failed: function body must end with “end” opcode @+33

В последней строке мы вышли за пределы 7 битов, поэтому модуль при валидации был отклонён.

Для объяснения и реализации LEB128 потребуется много текста и кода. Подробнее об этом алгоритме можно узнать из нашей книги.

▍ Трюк, который почти сработал

Во время фазы код-гольфинга мне в ду́ше пришла идея, которая, к сожалению, не сработала.

Можно было бы упростить 106 + "+-*/".indexOf(t), использовав код символа UTF-8 плюс смещение: 63 + t.charCodeAt(), сэкономив при этом 3 байта. Это не сработало, потому что символы +-*/ имеют разный порядок в UTF-8 и в байт-коде WebAssembly.

▍ Объяснение чисел в массиве

Последнее, что нуждается в объяснении — это массив чисел, используемый для построения модуля WebAssembly.

Чтобы объяснить каждый байт в массиве, придётся прочитать большую часть спецификации, но ниже мы приведём версию с комментариями, которая даст вам представление о том, что делает каждый элемент:

    [
      // Магическое число модуля Wasm '\0asm'
      [0, 97, 115, 109],
      // Версия Wasm 1.0
      [1, 0, 0, 0],

      // ----- раздел типов -----

      1, // Идентификатор раздела
      5, // Размер раздела в байтах

      1, // Количество последующих элементов

      // раздел типов - элемент 0
      96, // Тип `function`
      0,  // Количество параметров
      1,  // Количество возвращаемых значений

      127, // тип возвращаемого значения i32

      // ----- раздел функций -----

      3, // Идентификатор раздела
      2, // Размер раздела в байтах
      1, // Количество последующих элементов

      // раздел функций - элемент 0
      0, // Индекс элемента раздела функций

      // ----- раздел экспорта -----

      7, // Идентификатор раздела
      5, // Размер раздела в байтах
      1, // Количество последующих элементов

      // раздел экспорта - элемент 0
      1,  // Размер имени в байтах
      97, // Строка как байты utf-8, обозначающие 'a'
      0,  // Тип экспорта `function`
      0,  // Индекс функции

      // ----- раздел кода -----

      10, // Идентификатор раздела
      4 + len, // Размер раздела в байтах

      1, // Количество последующих элементов

      // раздел кода - элемент 0
      2 + len, // Размер элемента в байтах
      0, // Количество локальных переменных
      ...instrs,
      11, // Команда `end`
    ]

▍ Заключение

Вот и всё! Мы превратили довольно запутанный 192-байтный блок кода в почти читаемую программу. Надеюсь, вы узнали что-то новое о WebAssembly.

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

Выражаю особую благодарность lexi за то, что он подсказал некоторые из использованных выше трюков.

Telegram-канал со скидками, розыгрышами призов и новостями IT ?