EIP-145: даём 256-битной машине инструкцию сдвига
У EVM с первого дня были AND, OR, XOR и NOT — но не было битового сдвига. Контракты имитировали сдвиг умножением и делением на степени двойки: дороже, громоздче и неспособно корректно сдвигать знаковые числа. EIP-145 добавляет нативные SHL, SHR и SAR.
- словные и битовые операции EVM
Constantinople, февраль 2019. EVM работает со 256-битными словами и с генезиса имеет привычные битовые операторы — AND, OR, XOR, NOT. Но не хватало того, к которому любой ассемблерный программист потянулся бы немедленно: битового сдвига. Сдвиг битов влево или вправо — это способ упаковать несколько полей в одно слово, обойти битовую карту, сделать арифметику с фиксированной точкой или реализовать хеш. На машине, построенной вокруг 256-битных слов, его отсутствие бросается в глаза — а обходным решением было привлечь на помощь арифметику. EIP-145 наконец даёт машине ту инструкцию, которая должна была быть у неё с самого начала. Давайте выведем её.
Проблема: нет сдвига, значит — умножаем и делим
Без опкода сдвига контракты опирались на тождество теории чисел: сдвиг влево на n битов — то же самое, что умножение на 2ⁿ, а сдвиг вправо на n — деление на 2ⁿ. Так что сдвиг влево превращался в MUL, а сдвиг вправо — в DIV, причём каждый из них требовал сначала протолкнуть на стек константу 2ⁿ, добавляя байткод и газ. Это работает для беззнаковых значений, но это долгий обходной путь для того, что CPU делает за один такт. Хуже того, не было чистого способа выразить arithmetic right shift Сдвиг вправо, сохраняющий знаковый бит, так что сдвиг отрицательного числа вправо оставляет его отрицательным (эквивалент деления на степень двойки с округлением вниз). DIV округляет к нулю, а не в сторону минус бесконечности, поэтому не может воспроизвести корректный знаковый сдвиг — знак приходилось обрабатывать отдельным случаем вручную. (арифметический сдвиг вправо): DIV округляет к нулю, а не в сторону минус бесконечности, так что сдвиг знакового (отрицательного) числа вправо давал неверный результат, если только вы сами не обрабатывали знак отдельным случаем.
→ Шаг 2: добавляем все три сдвига напрямую.
EIP-145: три нативных опкода сдвига
Исправление добавляет ровно те три сдвига, которые нужны знаковой/беззнаковой машине. SHL Shift Left (0x1b): снимает со стека величину сдвига и значение, сдвигает значение влево на это число битов, заполняя нулями. Эквивалент старого MUL на 2ⁿ, но одна нативная инструкция за 3 газа. (0x1b) сдвигает влево; SHR Logical Shift Right (0x1c): сдвигает вправо, заполняя верх нулями — беззнаковый сдвиг вправо, эквивалент DIV на 2ⁿ для неотрицательных значений. (0x1c) — это логический (заполняющий нулями) сдвиг вправо; а SAR Arithmetic Shift Right (0x1d): сдвигает вправо, сохраняя знаковый бит, так что отрицательные числа остаются отрицательными (семантика деления с округлением вниз). Это та операция, которую DIV никогда не мог выразить чисто. (0x1d) — это арифметический (сохраняющий знак) сдвиг вправо, который старый трюк с DIV не мог сделать. Каждый снимает со стека величину сдвига и значение, сдвигает напрямую и стоит базовых 3 газа, как и другие битовые операции, — никаких MUL/DIV, никакой константы для проталкивания.
→ Шаг 3: всё, что сдвигает биты, становится компактнее.
Выигрыш: дешевле, компактнее и корректно
Битовый сдвиг повсюду под поверхностью — упаковка нескольких значений в один 256-битный слот, чтение и запись битовых карт, арифметика с фиксированной точкой и особенно криптографические процедуры, перемешивающие биты тысячами. Превращение его в одну инструкцию за 3 газа (вместо MUL/DIV плюс проталкивание константы) урезает газ и байткод во всём этом, а SAR устраняет целый класс ошибок знакового сдвига. Как и с каждым EIP типа «недостающий примитив» — PUSH0, MCOPY, — выигрыш тихий и автоматический: компиляторы генерируют новые опкоды там, где раньше генерировали арифметический обходной путь, так что контракты становятся дешевле и компактнее просто от перекомпиляции.