Арифметика: lea, сдвиги и полное произведение

В прошлом уроке ты научился читать операнды и понял, что спецификатор Imm(rb,ri,s) это формула адреса. Сегодня та же формула работает без единого обращения к памяти: инструкция leaq считает её и кладёт число в регистр. Из этого одного факта компилятор собирает умножение на константу, и 9*x превращается в одну команду. Дальше пойдут четыре группы целочисленной арифметики, сдвиги с их единственным разрешённым регистром %cl, полное 128-битное произведение в паре %rdx:%rax и деление, у которого делимое приходится готовить отдельной инструкцией. В конце разберёмся, почему обнуление регистра пишут через xor, и восстановим пару функций по их ассемблеру.

Цели урока

• Читать leaq как арифметическое выражение вида Imm + rb + s*ri и понимать, что памяти инструкция не касается.
• Видеть, как компилятор собирает x*K из lea, shl, add и sub, и знать, на каком K он сдаётся и берёт imulq.
• Различать четыре группы целочисленных операций и правильно читать суффиксы b, w, l, q.
• Понимать, почему величина сдвига живёт либо в непосредственном операнде, либо ровно в регистре %cl, и как это связано с типом Log2Int в Zig.
• Видеть в дизассемблере разницу между ReleaseSafe и ReleaseFast: jo и seto вокруг обычного add.
• Знать три формы imul и понимать, что mulq и imulq с одним операндом дают полное произведение в %rdx:%rax.
• Готовить делимое через cqto и читать idivq, отличать cltq от cltd.
• Объяснять, почему поле reg в байте ModRM иногда содержит не регистр, а расширение опкода.
• Восстанавливать исходную функцию по ассемблерному листингу.

Идея: инструкция, которая считает адрес, но никуда не идёт

Возьми любую строку из урока про операнды: movq 8(%rdi,%rcx,4), %rax. Процессор сначала считает адрес по формуле 8 + rdi + 4*rcx, потом идёт в память по этому адресу и приносит восемь байт. Инструкция leaq делает ровно первую половину работы и останавливается: адрес посчитан, но никто по нему не ходит. Результат просто ложится в регистр-приёмник.

leaq это единственная инструкция в таблице арифметики, у которой нет вариантов по размеру: она всегда работает с 64-битным результатом. И у неё есть свойство, ради которого компилятор любит её больше всех остальных: аппаратура считает Imm + rb + s*ri за один такт, а это уже сложение двух чисел и умножение одного из них на 1, 2, 4 или 8. То есть маленький арифметический сопроцессор, случайно доставшийся нам от механизма адресации.

Посмотри на форму и на то, что она вычисляет, если x лежит в %rdi, а y в %rsi (первые два целых аргумента по System V ABI):

Инструкция	Что окажется в %rax
leaq 6(%rdi), %rax	6 + x
leaq (%rdi,%rsi), %rax	x + y
leaq (%rdi,%rsi,4), %rax	x + 4*y
leaq 7(%rdi,%rdi,8), %rax	7 + 9*x
leaq 10(,%rsi,4), %rax	10 + 4*y
leaq 9(%rdi,%rsi,2), %rax	9 + x + 2*y

Четвёртая строка это весь фокус: база и индекс могут быть одним и тем же регистром, и тогда rb + s*ri превращается в (1+s)*x. Масштаб бывает 1, 2, 4 и 8, значит одна leaq умеет умножить на 2, 3, 5 или 9. А если базу не указывать вовсе, доступны 2, 4 и 8. Это упражнение 3.6 из книги, и оно ровно про это: научиться читать форму как формулу.

Есть ещё одно отличие leaq от арифметических инструкций, и оно важнее, чем кажется: leaq не трогает флаги. addq выставит флаг переноса и флаг переполнения, leaq не выставит ничего. Компилятор пользуется этим, когда надо посчитать сумму, но сохранить результат предыдущего сравнения. Флагами мы займёмся в следующем уроке, но привычку замечать это заведи сейчас.

Три leaq подряд: одно выражение

Возьмём функцию из книги и посмотрим, что с ней сделает наш компилятор. Файл целиком:

export fn scale(x: i64, y: i64, z: i64) i64 {
    const t = x + 4 * y + 12 * z;
    return t;
}

export fn scale2(x: i64, y: i64, z: i64) i64 {
    const t = 5 * x + 2 * y + 8 * z;
    return t;
}

Собираем объектник под нашу платформу и читаем дизассемблер. Ассемблерный листинг берём именно из objdump, потому что zig build-exe -femit-asm печатает Intel-синтаксис, а книга и весь этот раздел используют AT&T:

$ zig build-obj lea.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=lea.o
$ objdump -d lea.o

0000000000000090 <scale>:
      90: 48 8d 04 b7      leaq    (%rdi,%rsi,4), %rax     # x + 4*y
      94: 48 8d 0c 52      leaq    (%rdx,%rdx,2), %rcx     # 3*z
      98: 48 8d 04 88      leaq    (%rax,%rcx,4), %rax     # (x+4*y) + 4*(3*z)
      9c: c3               retq

0000000000000080 <scale2>:
      80: 48 8d 04 bf      leaq    (%rdi,%rdi,4), %rax     # 5*x
      84: 48 8d 04 70      leaq    (%rax,%rsi,2), %rax     # 5*x + 2*y
      88: 48 8d 04 d0      leaq    (%rax,%rdx,8), %rax     # 5*x + 2*y + 8*z
      8c: c3               retq

Разбери, что тут произошло.

1. Ни одного imul и ни одного add. Три сложения и три умножения уместились в три инструкции, потому что каждая leaq делает одно сложение и одно умножение сразу.
2. Множитель 12 никакая одиночная leaq не даёт: 12 это не 2, не 3, не 5 и не 9. Компилятор разложил его на 3 и 4: сначала 3*z через (%rdx,%rdx,2), потом умножение на 4 приехало бесплатно как масштаб в третьей инструкции.
3. Третья инструкция складывает накопленное x + 4*y с учетверённым 3*z. Аккумулятор здесь %rax, и промежуточные значения переезжают между регистрами, а не пишутся в память.
4. Каждая leaq занимает четыре байта: префикс 48 с битом W, опкод 8d, байт ModRM и байт SIB. Никаких обращений к памяти в этих байтах нет, потому что инструкция и не собиралась туда идти.

Функция scale2 устроена так же и отвечает на упражнение 3.7 из книги: по трём leaq восстанавливается выражение 5*x + 2*y + 8*z. Приём один и тот же: подписывай справа от каждой строки, что оказалось в приёмнике, и к концу листинга ответ соберётся сам.

Покрути формулу

Виджет ниже работает в двух режимах. В первом ты собираешь форму Imm(rb,ri,s) по кусочкам и сразу видишь три вещи: текст инструкции так, как его напечатает objdump, выражение, которое она вычисляет, и подстановку конкретных чисел. Поставь базу и индекс на один регистр и проведи масштаб по всем четырём значениям: получишь ровно множители 2, 3, 5 и 9. Потом убери базу и посмотри, как из тех же полей выходят 2, 4 и 8.

Второй режим переворачивает задачу. Ты задаёшь константу K, а поиск в ширину перебирает цепочки из leaq, shlq, addq, subq и negq и показывает кратчайшую. Рядом лежит то, что на самом деле выдал компилятор для K * x. На K = 29 видно, что поиск иногда оказывается умнее: компилятор потратил четыре инструкции, а трёх достаточно.

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

Умножение на константу: где проходит граница

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

Файл с одинаковыми по форме функциями:

export fn times5(x: i64) i64 {
    return 5 * x;
}

export fn times9(x: i64) i64 {
    return 9 * x;
}

export fn times12(x: i64) i64 {
    return 12 * x;
}

export fn times15(x: i64) i64 {
    return 15 * x;
}

export fn times7(x: i64) i64 {
    return 7 * x;
}

export fn times255(x: i64) i64 {
    return 255 * x;
}

export fn times100(x: i64) i64 {
    return 100 * x;
}

Тот же objdump -d lea.o, только теперь смотрим на эти функции:

0000000000000070 <times5>:
      70: 48 8d 04 bf      leaq    (%rdi,%rdi,4), %rax

0000000000000060 <times9>:
      60: 48 8d 04 ff      leaq    (%rdi,%rdi,8), %rax

0000000000000050 <times12>:
      50: 48 c1 e7 02      shlq    $0x2, %rdi
      54: 48 8d 04 7f      leaq    (%rdi,%rdi,2), %rax

0000000000000040 <times15>:
      40: 48 8d 04 bf      leaq    (%rdi,%rdi,4), %rax
      44: 48 8d 04 40      leaq    (%rax,%rax,2), %rax

0000000000000030 <times7>:
      30: 48 8d 04 fd 00 00 00 00    leaq    (,%rdi,8), %rax
      38: 48 29 f8                   subq    %rdi, %rax

0000000000000010 <times255>:
      10: 48 89 f8         movq    %rdi, %rax
      13: 48 c1 e0 08      shlq    $0x8, %rax
      17: 48 29 f8         subq    %rdi, %rax

0000000000000020 <times100>:
      20: 48 6b c7 64      imulq   $0x64, %rdi, %rax

Семь функций и пять разных стратегий.

1. 5*x и 9*x берутся одной leaq, потому что 5 и 9 это 1+4 и 1+8.
2. 12*x это 4 * (3*x), но компилятор переставил множители: сначала shlq $2 умножил на 4 прямо в %rdi, потом leaq (%rdi,%rdi,2) умножила результат на 3. Порядок не важен, а вот то, что сдвиг работает по месту в %rdi, экономит копирование.
3. 15*x это 3 * (5*x): две leaq подряд, вторая берёт результат первой и как базу, и как индекс.
4. 7*x и 255*x собраны вычитанием: 8*x - x и 256*x - x. Это общий приём для констант вида 2^n - 1.
5. На 100 компилятор сдался и взял imulq с непосредственным операндом. Одна инструкция вместо цепочки, но умножение считается дольше сложения.

Обрати внимание на длину leaq (,%rdi,8), %rax: восемь байт против четырёх у leaq (%rdi,%rdi,8), %rax. Причина в кодировании, которое ты разбирал в прошлом уроке: форма без базы требует в байте SIB поле базы со значением 101, а оно означает, что дальше идёт четырёхбайтовое смещение. Четыре нулевых байта смещения и делают инструкцию длиннее. Умножить на 9 буквально дешевле по размеру кода, чем умножить на 8.

Вот срез той же таблицы для нескольких K, снятый одной командой с одного объектника:

K	Что выдал компилятор	Инструкций
3	leaq (%rdi,%rdi,2), %rax	1
9	leaq (%rdi,%rdi,8), %rax	1
11	leaq (%rdi,%rdi,4), %rax плюс leaq (%rdi,%rax,2), %rax	2
21	leaq (%rdi,%rdi,4), %rax плюс leaq (%rdi,%rax,4), %rax	2
23	leaq (%rdi,%rdi,2), %rax, shlq $3, %rax, subq %rdi, %rax	3
29	две leaq и два addq %rdi, %rax	4
35	imulq $35, %rdi, %rax	1
39	imulq $39, %rdi, %rax	1
45	leaq (%rdi,%rdi,8), %rax плюс leaq (%rax,%rax,4), %rax	2

Закономерность видна: пока константа раскладывается в две или три инструкции, компилятор раскладывает. На 35 и 39 короткой цепочки нет, и он предпочитает одну imulq. А на 29 он остановился на четырёх инструкциях, хотя трёх хватало: shlq $3 даёт 8*x, subq %rdi даёт 7*x, leaq (%rdi,%rax,4) даёт 4*(7*x) + x = 29*x. Это не ошибка компилятора, а его эвристика: она перебирает не все формы, а типовые.

Заметь ещё одну деталь в форме leaq (%rdi,%rax,4), %rax. Здесь база и индекс это разные регистры: индекс несёт накопленное значение, а база подмешивает исходный x. Так одна инструкция делает 4*m + 1 там, где иначе понадобились бы умножение и сложение.

Четыре группы целочисленных операций

Книга делит целочисленную арифметику x86-64 на четыре группы, и это деление стоит запомнить, потому что от него зависит, сколько операндов у инструкции и кто из них меняется.

Загрузка эффективного адреса: только leaq. Два операнда, приёмник обязан быть регистром, флаги не меняются.

Унарные операции: один операнд, он же источник и приёмник. Может быть регистром или ячейкой памяти.

Инструкция	Действие
INC D	D = D + 1
DEC D	D = D - 1
NEG D	D = -D
NOT D	D = ~D

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

Инструкция	Действие
ADD S, D	D = D + S
SUB S, D	D = D - S
IMUL S, D	D = D * S
XOR S, D	D = D ^ S
OR S, D	D = D | S
AND S, D	D = D & S

Сдвиги: величина сдвига первым операндом, сдвигаемое значение вторым.

Инструкция	Действие
SAL k, D и SHL k, D	D = D << k
SAR k, D	арифметический сдвиг вправо, слева копии знакового бита
SHR k, D	логический сдвиг вправо, слева нули

Порядок операндов в AT&T читается наоборот привычному: subq %rax, %rdx это “вычесть %rax из %rdx”, а не “вычесть %rdx из %rax”. Для коммутативных операций разницы нет, для sub она принципиальна, и именно на этом чаще всего ошибаются при чтении листинга.

Каждая инструкция из таблиц существует в четырёх размерах: addb, addw, addl, addq для байта, слова, двойного слова и четверного слова. Исключение одно, и это leaq.

Унарные операции по месту в памяти

Проверим, что унарные операции действительно умеют работать прямо с памятью:

export fn bumpMem(counter: *i64) void {
    counter.* += 1;
}

export fn dropMem(counter: *i64) void {
    counter.* -= 1;
}

export fn negMem(v: *i64) void {
    v.* = -%v.*;
}

export fn flipMem(v: *u32) void {
    v.* = ~v.*;
}

export fn addMem(counter: *i64, delta: i64) void {
    counter.* +%= delta;
}

export fn scaleMem(counter: *i64) void {
    counter.* *%= 16;
}

$ zig build-obj unary.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=unary.o
$ objdump -d unary.o

0000000000000050 <bumpMem>:
      50: 48 83 07 01      addq    $0x1, (%rdi)

0000000000000040 <dropMem>:
      40: 48 83 07 ff      addq    $-0x1, (%rdi)

0000000000000030 <negMem>:
      30: 48 f7 1f         negq    (%rdi)

0000000000000020 <flipMem>:
      20: f7 17            notl    (%rdi)

0000000000000010 <addMem>:
      10: 48 01 37         addq    %rsi, (%rdi)

0000000000000000 <scaleMem>:
       0: 48 c1 27 04      shlq    $0x4, (%rdi)

Пять наблюдений.

1. Ни одной пары “загрузить, посчитать, записать”. Инструкция читает память, считает и пишет обратно сама.
2. Компилятор не выбрал incq и decq, хотя они существуют. Вместо них addq $1 и addq $-1. Причина историческая и про флаги: inc и dec меняют не все флаги, а все остальные, и на конвейерных процессорах это создаёт зависимость по частично обновлённому регистру флагов. Ассемблер, написанный руками, часто использует incq, компилятор почти никогда.
3. negq и notl компилятор взял без раздумий, потому что альтернативы у них нет.
4. Суффикс следует за типом: у *i64 он q, у *u32 он l. И у notl нет префикса 48, потому что операция 32-битная.
5. Умножение на 16 стало shlq $4 прямо в памяти. Сдвиг тоже умеет работать по месту.

Как в один опкод помещается восемь операций

В байте ModRM есть поле reg из трёх бит. В инструкциях с двумя операндами оно называет регистр. Но у унарных операций и сдвигов второго регистра нет, и три бита стоят без дела. Разработчики набора команд их не выбросили: они сложили несколько разных инструкций под один опкод и стали различать их по полю reg. В документации Intel это записывается как /digit, где digit это значение поля.

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

$ zig cc -c -target x86_64-linux groups.s -o groups.o
$ objdump -d groups.o

       0: 48 ff 07         incq    (%rdi)
       3: 48 ff 0f         decq    (%rdi)
       6: 48 f7 17         notq    (%rdi)
       9: 48 f7 1f         negq    (%rdi)
       c: 48 f7 e6         mulq    %rsi
       f: 48 f7 ee         imulq   %rsi
      12: 48 f7 f6         divq    %rsi
      15: 48 f7 fe         idivq   %rsi
      18: 48 83 07 01      addq    $0x1, (%rdi)
      1c: 48 83 0f 01      orq     $0x1, (%rdi)
      20: 48 83 27 01      andq    $0x1, (%rdi)
      24: 48 83 2f 01      subq    $0x1, (%rdi)
      28: 48 81 07 e8 03 00 00      addq    $0x3e8, (%rdi)
      36: 48 c1 e0 04      shlq    $0x4, %rax
      3a: 48 c1 e8 04      shrq    $0x4, %rax
      3e: 48 c1 f8 04      sarq    $0x4, %rax
      42: 48 d3 e0         shlq    %cl, %rax
      45: 48 d3 e8         shrq    %cl, %rax
      48: 48 d3 f8         sarq    %cl, %rax

Смотри на второй байт каждой строки, это опкод, и на третий, это ModRM.

Первые четыре строки: опкод ff для incq и decq, опкод f7 для notq и negq. ModRM у всех четырёх заканчивается на 111, это %rdi в поле rm, а режим 00 означает “по адресу из регистра”. Различаются они полем reg: 07 это 00 000 111, поле reg равно 0; 0f это 00 001 111, поле равно 1; 17 даёт 2, 1f даёт 3. Вот и обещанные /0, /1, /2, /3.

Следующие четыре строки продолжают тот же опкод f7: mulq это /4, imulq с одним операндом это /5, divq это /6, idivq это /7. Байт ModRM у них начинается с 11, потому что операнд теперь регистр, а не память: e6 это 11 100 110, где 110 это %rsi, а 100 это четвёрка.

Строки с непосредственным операндом идут под опкодом 83: addq это /0, orq это /1, andq это /4, subq это /5. Восемь арифметических операций живут под одним байтом. А когда константа перестаёт помещаться в один байт, опкод меняется на 81, и следом идут четыре байта значения: addq $1000 весит семь байт против четырёх у addq $1.

Сдвиги устроены так же: опкод c1 для сдвига на константу, d3 для сдвига на %cl, а поле reg выбирает направление и вид: /4 это shl, /5 это shr, /7 это sar. Отсюда, кстати, видно, почему sal и shl это одна и та же инструкция: у них одно и то же значение поля reg, разными их делает только мнемоника ассемблера.

Теперь противопоставление. Вот две формы imul, где поле reg работает по прямому назначению:

      4b: 48 0f af c6      imulq   %rsi, %rax
      4f: 48 6b c7 64      imulq   $0x64, %rdi, %rax

В первой опкод двухбайтовый, 0f af, ModRM c6 это 11 000 110: поле reg равно 000 и означает %rax, поле rm равно 110 и означает %rsi. Во второй опкод 6b, ModRM c7 это 11 000 111: приёмник %rax в поле reg, источник %rdi в поле rm, а константа идёт следом одним байтом. Одно и то же поле в одном случае номер регистра, в другом продолжение опкода, и понять, что именно, можно только зная опкод.

Это ровно та развилка, которую придётся зашить в дизассемблер: таблица должна помнить не только мнемонику опкода, но и то, что делать с полем reg.

Сдвиги: константа или единственный регистр

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

%cl занимает один байт, то есть теоретически задаёт величину от 0 до 255. Но сдвигать 64-битное значение на 200 бессмысленно, и процессор поступает просто: он берёт от %cl столько младших бит, сколько нужно для ширины операнда. Для salq это шесть бит (значения от 0 до 63), для sall пять, для salw четыре, для salb три. Старшие биты игнорируются молча. Поэтому %cl со значением 0xFF даст сдвиг на 7 в байтовой инструкции и на 63 в четверной.

В Zig это правило не спрятано, а поднято в систему типов. Величина сдвига обязана иметь тип Log2Int, и компилятор не даст сдвинуть i64 на значение типа u64, пока ты явно не сузишь его.

const std = @import("std");

test "величина сдвига это отдельный тип, а не просто число" {
    // Log2Int(T) это самый узкий беззнаковый тип, которым можно задать сдвиг T.
    try std.testing.expectEqual(u6, std.math.Log2Int(i64));
    try std.testing.expectEqual(u5, std.math.Log2Int(u32));
    try std.testing.expectEqual(u3, std.math.Log2Int(u8));
    try std.testing.expectEqual(u7, std.math.Log2Int(u128));
}

test "сдвиг переменной величины требует Log2Int" {
    var n: u64 = 300;
    _ = &n;
    const k: u6 = @truncate(n);
    // 300 = 0b100101100, младшие шесть бит это 0b101100 = 44.
    try std.testing.expectEqual(@as(u6, 44), k);

    var x: i64 = 1;
    _ = &x;
    try std.testing.expectEqual(@as(i64, 1) << 44, x << k);
}

test "арифметический и логический сдвиг вправо это разные инструкции" {
    const signed: i64 = -16;
    const unsigned: u64 = @bitCast(signed);

    try std.testing.expectEqual(@as(i64, -1), signed >> 4);
    try std.testing.expectEqual(@as(u64, 0x0FFF_FFFF_FFFF_FFFF), unsigned >> 4);
}

$ zig test shifts.zig
1/3 shifts.test.величина сдвига это отдельный тип, а не просто число...OK
2/3 shifts.test.сдвиг переменной величины требует Log2Int...OK
3/3 shifts.test.арифметический и логический сдвиг вправо это разные инструкции...OK
All 3 tests passed.

Обрати внимание, что @truncate(n) до u6 это буквально то же самое, что делает процессор с %cl: берёт младшие шесть бит и выбрасывает остальные. Zig заставляет тебя написать это усечение руками, потому что молчаливая потеря старших бит это как раз тот класс ошибок, который язык обещает не прятать.

Теперь посмотрим на машинный код. Функция из упражнения 3.9 книги и её родственница:

export fn shiftLeft4RightN(x: i64, n: u64) i64 {
    const k: u6 = @truncate(n);
    var v = x;
    v <<= 4;
    v >>= k;
    return v;
}

export fn shiftPair(x: i64, u: u64, n: u64) i64 {
    const k: u6 = @truncate(n);
    const a = x >> k;
    const b = u >> k;
    return a + @as(i64, @bitCast(b));
}

$ zig build-obj ops.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=ops.o
$ objdump -d ops.o

0000000000000020 <shiftLeft4RightN>:
      20: 48 89 f1         movq    %rsi, %rcx      # n в %rcx, важен только %cl
      23: 48 89 f8         movq    %rdi, %rax      # x в приёмник
      26: 48 c1 e0 04      shlq    $0x4, %rax      # x <<= 4, величина в инструкции
      2a: 48 d3 f8         sarq    %cl, %rax       # x >>= n, величина в %cl
      2d: c3               retq

0000000000000010 <shiftPair>:
      10: 48 89 d1         movq    %rdx, %rcx      # n в %rcx
      13: 48 d3 ff         sarq    %cl, %rdi       # знаковый сдвиг
      16: 48 d3 ee         shrq    %cl, %rsi       # беззнаковый сдвиг
      19: 48 8d 04 3e      leaq    (%rsi,%rdi), %rax
      1d: c3               retq

Что тут стоит заметить.

1. Первое, что делает каждая функция, это перекладывает величину сдвига в %rcx. Не потому, что там ей место по смыслу, а потому что инструкция другого регистра не примет.
2. Никакого усечения до шести бит в машинном коде нет. @truncate в исходнике не породил ни одной инструкции, потому что процессор всё равно возьмёт только младшие шесть бит. Проверка типов сработала на этапе компиляции и исчезла.
3. В shiftPair два сдвига вправо разными инструкциями над одинаковыми битами: sarq для знакового i64 и shrq для беззнакового u64. Это единственное место в целочисленной арифметике, где знаковость меняет инструкцию, всё остальное работает одинаково для обоих представлений. Именно поэтому дополнительный код и стал стандартом.
4. Финальное сложение снова досталось leaq, потому что результат кладут в третий регистр и портить операнды нельзя.

Что добавляет ReleaseSafe

В уроке про значения и типы ты видел, что обычный + в Zig паникует при переполнении, а +% заворачивается. Теперь можно посмотреть, во сколько это обходится.

export fn addChecked(x: i64, y: i64) i64 {
    return x + y;
}

export fn addWrapping(x: i64, y: i64) i64 {
    return x +% y;
}

export fn addFlag(x: i64, y: i64, out: *i64) u8 {
    const pair = @addWithOverflow(x, y);
    out.* = pair[0];
    return pair[1];
}

Сначала быстрый режим:

$ zig build-obj safe.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=safe-rf.o
$ objdump -d safe-rf.o

0000000000000020 <addChecked>:
      20: 48 8d 04 37      leaq    (%rdi,%rsi), %rax
      24: c3               retq

0000000000000010 <addWrapping>:
      10: 48 8d 04 37      leaq    (%rdi,%rsi), %rax
      14: c3               retq

Обе функции скомпилировались в одну и ту же инструкцию, и это leaq. В ReleaseFast проверяемое сложение и заворачивающееся неотличимы, потому что переполнение объявлено неопределённым поведением и проверять нечего.

Теперь безопасный режим:

$ zig build-obj safe.zig -O ReleaseSafe -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=safe-rs.o
$ objdump -d safe-rs.o

0000000000000020 <addChecked>:
      20: 48 01 f7         addq    %rsi, %rdi
      23: 70 04            jo      0x29        # переполнение, уходим в панику
      25: 48 89 f8         movq    %rdi, %rax
      28: c3               retq
      29: 50               pushq   %rax
      2a: e8 00 00 00 00   callq   <panic>

0000000000000000 <addFlag>:
       0: 50               pushq   %rax
       1: 48 01 f7         addq    %rsi, %rdi
       4: 0f 90 04 24      seto    (%rsp)
       8: 0f 90 c0         seto    %al          # флаг переполнения как значение
       b: 48 89 3a         movq    %rdi, (%rdx)
       e: 59               popq    %rcx
       f: c3               retq

Разбор по пунктам.

1. leaq исчезла. Она не выставляет флаги, а безопасному режиму флаг переполнения нужен, поэтому сложение делает настоящий addq.
2. Проверка стоит две инструкции: сам jo и переход в хвост функции с вызовом паники. Хвост лежит после retq, то есть на горячем пути его никто не читает.
3. jo и seto читают один и тот же флаг, но по-разному: первый ветвится, второй превращает флаг в байт.
4. @addWithOverflow компилируется без единого перехода: addq, потом seto, и бит переполнения уезжает в возвращаемое значение. Это и есть цена, которую ты платишь за явную работу с переполнением: одна лишняя инструкция и ни одной ветки.

Вывод для чтения листингов: если рядом с обычной арифметикой стоит jo или seto, перед тобой сборка в безопасном режиме. В ReleaseFast этих инструкций не бывает.

Полное произведение: пара %rdx:%rax

Произведение двух 64-битных чисел вообще-то не помещается в 64 бита. Обычный imulq S, D этого не замечает: он считает младшие 64 бита результата и выбрасывает старшие. Для усечённого произведения знаковость не важна, биты получаются одинаковые, поэтому одной инструкции хватает на оба случая.

Но иногда старшая половина нужна. Для этого есть отдельные формы с одним операндом: mulq для беззнаковых и imulq для знаковых. Один множитель обязан быть в %rax, второй указывается операндом, а результат раскладывается по двум регистрам: младшие 64 бита в %rax, старшие в %rdx. Пару %rdx:%rax Intel называет восьмерным словом.

Итого у imul три разных формы, и различает их ассемблер по числу операндов:

Форма	Что делает
imulq S	полное знаковое произведение S * %rax в %rdx:%rax
imulq S, D	D = D * S, только младшие 64 бита
imulq $Imm, S, D	D = S * Imm, только младшие 64 бита

В Zig полное произведение записывается естественно: расширь оба множителя до 128 бит и перемножь.

export fn storeUProd(dest: *u128, x: u64, y: u64) void {
    dest.* = @as(u128, x) * @as(u128, y);
}

export fn storeProd(dest: *i128, x: i64, y: i64) void {
    dest.* = @as(i128, x) * @as(i128, y);
}

export fn mult2(x: i64, y: i64) i64 {
    return x *% y;
}

$ zig build-obj muldiv.zig -O ReleaseFast -target x86_64-linux \
      -fomit-frame-pointer -femit-bin=muldiv.o
$ objdump -d muldiv.o

00000000000000a0 <storeUProd>:
      a0: 48 89 d0         movq    %rdx, %rax       # y в множимое
      a3: 48 f7 e6         mulq    %rsi             # умножить на x
      a6: 48 89 57 08      movq    %rdx, 0x8(%rdi)  # старшие 8 байт в dest+8
      aa: 48 89 07         movq    %rax, (%rdi)     # младшие 8 байт в dest
      ad: c3               retq

0000000000000090 <storeProd>:
      90: 48 89 d0         movq    %rdx, %rax
      93: 48 f7 ee         imulq   %rsi             # знаковый вариант, один операнд
      96: 48 89 57 08      movq    %rdx, 0x8(%rdi)
      9a: 48 89 07         movq    %rax, (%rdi)
      9d: c3               retq

0000000000000080 <mult2>:
      80: 48 89 f8         movq    %rdi, %rax
      83: 48 0f af c6      imulq   %rsi, %rax       # два операнда, младшие 64 бита
      87: c3               retq

Четыре наблюдения.

1. Умножение занимает ровно одну инструкцию, а запись результата две: младшая половина по адресу dest, старшая по dest+8. Порядок байтов little-endian, поэтому старшие байты уезжают на большие адреса.
2. mulq и imulq с одним операндом отличаются одним битом в поле reg: /4 против /5. Это те самые байты f7 e6 и f7 ee из таблицы выше.
3. Второй множитель не назван нигде, кроме как через %rax. Компилятор обязан положить его туда сам, отсюда movq %rdx, %rax в начале.
4. Обычное усечённое умножение mult2 использует форму с двумя операндами и трёхбайтовый опкод 0f af, никакого %rdx там нет.

Домашнее задание 3.59 из книги показывает, что GCC на этой же функции выдаёт три умножения вместо одного. Так бывает, когда компилятор раскладывает 128-битное произведение на 64-битные части вручную. Наш компилятор до такой раскладки не доходит, пока оба множителя 64-битные: он видит, что аппаратура умеет это одной инструкцией. Но заставить его показать алгоритм несложно, надо только сделать оба множителя по-настоящему 128-битными:

export fn prod128(dest: *i128, x: i128, y: i128) void {
    dest.* = x *% y;
}

0000000000000000 <prod128>:
       0: 49 89 d1         movq    %rdx, %r9        # младшая половина x
       3: 48 89 c8         movq    %rcx, %rax       # младшая половина y
       6: 48 f7 e6         mulq    %rsi             # xl * yl, полные 128 бит
       9: 4c 0f af c9      imulq   %rcx, %r9        # xh * yl, только младшие
       d: 4c 01 ca         addq    %r9, %rdx
      10: 4c 0f af c6      imulq   %rsi, %r8        # xl * yh, только младшие
      14: 49 01 d0         addq    %rdx, %r8
      17: 48 89 07         movq    %rax, (%rdi)
      1a: 4c 89 47 08      movq    %r8, 0x8(%rdi)
      1e: c3               retq

Вот он, алгоритм из 3.59, только теперь на 128-битных числах. Разложи каждый множитель на половины: x = 2^64 * xh + xl и то же для y. Тогда произведение это 2^128 * xh*yh + 2^64 * (xh*yl + xl*yh) + xl*yl. Первое слагаемое целиком уезжает за границу 128 бит и не нужно, поэтому умножений остаётся три: одно полное для xl*yl и два усечённых для перекрёстных членов, чьи старшие половины тоже уедут за границу. Ровно эту арифметику ты и напишешь в задаче урока, только на 64-битных половинах.

Поведение полного произведения удобно проверять тестом:

const std = @import("std");

test "полное произведение как одно число" {
    const x: u64 = std.math.maxInt(u64);
    const wide = @as(u128, x) * @as(u128, x);

    try std.testing.expectEqual(@as(u64, 1), @as(u64, @truncate(wide)));
    try std.testing.expectEqual(@as(u64, 0xFFFF_FFFF_FFFF_FFFE), @as(u64, @truncate(wide >> 64)));

    // Усечённое произведение теряет старшую половину и не жалуется.
    const narrow = x *% x;
    try std.testing.expectEqual(@as(u64, 1), narrow);

    // @mulWithOverflow отдаёт усечённое произведение и бит "не влезло".
    const pair = @mulWithOverflow(x, x);
    try std.testing.expectEqual(@as(u64, 1), pair[0]);
    try std.testing.expectEqual(@as(u1, 1), pair[1]);
}

test "знаковое и беззнаковое усечённое умножение совпадают по битам" {
    const x: i64 = -3;
    const y: i64 = 5;
    const signed = x *% y;
    const unsigned = @as(u64, @bitCast(x)) *% @as(u64, @bitCast(y));
    try std.testing.expectEqual(@as(u64, @bitCast(signed)), unsigned);
}

$ zig test wide.zig
1/2 wide.test.полное произведение как одно число...OK
2/2 wide.test.знаковое и беззнаковое усечённое умножение совпадают по битам...OK
All 2 tests passed.

Первый тест показывает, почему maxInt(u64) в квадрате даёт младшую половину 1: это (2^64 - 1)^2 = 2^128 - 2^65 + 1, и младшие 64 бита у такого числа единица. Второй тест это то самое утверждение книги, что усечённое умножение одинаково для знакового и беззнакового случая.

Деление: делимое надо готовить

Деления в таблице арифметических операций нет, и это не случайность. Деление устроено как умножение наоборот: делимое 128-битное и лежит в паре %rdx:%rax, делитель указывается операндом, частное возвращается в %rax, а остаток в %rdx. Одна инструкция отдаёт сразу и частное, и остаток.

Инструкция	Что делает
idivq S	знаковое деление %rdx:%rax на S, частное в %rax, остаток в %rdx
divq S	то же без знака
cqto	расширяет знак %rax на весь %rdx

Почти всегда делимое у нас 64-битное, а не 128-битное. Значит, перед делением надо заполнить %rdx: нулями для беззнакового случая и копиями знакового бита для знакового. Второе делает cqto, одна из немногих инструкций, у которой имя в AT&T и в Intel не совпадает: Intel зовёт её cqo.

export fn remdiv(x: i64, y: i64, qp: *i64, rp: *i64) void {
    qp.* = @divTrunc(x, y);
    rp.* = @rem(x, y);
}

export fn uremdiv(x: u64, y: u64, qp: *u64, rp: *u64) void {
    qp.* = x / y;
    rp.* = x % y;
}

0000000000000050 <remdiv>:
      50: 49 89 d0         movq    %rdx, %r8        # qp уходит из %rdx, он нужен делению
      53: 48 89 f8         movq    %rdi, %rax       # x в младшую половину делимого
      56: 48 89 fa         movq    %rdi, %rdx
      59: 48 09 f2         orq     %rsi, %rdx
      5c: 48 c1 ea 20      shrq    $0x20, %rdx      # оба ли операнда влезают в 32 бита?
      60: 74 0c            je      0x6e             # да, тогда короткий путь
      62: 48 99            cqto                     # расширить знак x на %rdx
      64: 48 f7 fe         idivq   %rsi             # разделить на y
      67: 49 89 00         movq    %rax, (%r8)      # частное
      6a: 48 89 11         movq    %rdx, (%rcx)     # остаток
      6d: c3               retq
      6e: 31 d2            xorl    %edx, %edx
      70: f7 f6            divl    %esi             # 32-битное деление, оно быстрее
      72: 49 89 00         movq    %rax, (%r8)
      75: 48 89 11         movq    %rdx, (%rcx)
      78: c3               retq

Три вещи, которые тут стоит разобрать.

1. Первая инструкция спасает аргумент. Указатель qp пришёл в %rdx, а %rdx через две инструкции станет старшей половиной делимого. Компилятор переложил его в %r8. Это общая беда специальных операций: они требуют конкретные регистры, и всё, что там лежало, приходится двигать.
2. cqto стоит ровно перед idivq и ничего не считает, только готовит %rdx. Забыть её нельзя: в %rdx окажется мусор, и частное будет неправильным или инструкция вызовет исключение.
3. Четыре инструкции с orq и shrq $32 это оптимизация, которой в книге нет. Компилятор проверяет, помещаются ли оба операнда в 32 бита, и если да, идёт коротким путём через divl. Делает он это потому, что 64-битное деление на порядок медленнее 32-битного: это самая долгая целочисленная инструкция в наборе.

Беззнаковый вариант из упражнения 3.12 отличается ровно одной инструкцией:

0000000000000020 <uremdiv>:
      20: 49 89 d0         movq    %rdx, %r8
      23: 48 89 f8         movq    %rdi, %rax
      26: 48 89 fa         movq    %rdi, %rdx
      29: 48 09 f2         orq     %rsi, %rdx
      2c: 48 c1 ea 20      shrq    $0x20, %rdx
      30: 74 0c            je      0x3e
      32: 31 d2            xorl    %edx, %edx       # вместо cqto просто ноль
      34: 48 f7 f6         divq    %rsi             # divq вместо idivq
      37: 49 89 00         movq    %rax, (%r8)
      3a: 48 89 11         movq    %rdx, (%rcx)
      3d: c3               retq

Вместо cqto идёт xorl %edx, %edx, а idivq меняется на divq. Логика простая: беззнаковое число расширяется нулями, а не знаком, а знаковое деление и беззнаковое это разные инструкции, потому что при делении знак важен так же, как при сдвиге вправо.

Три инструкции расширения знака

cqto не одинока. У неё есть родственницы для меньших ширин, и все три встречаются в реальных листингах:

export fn divWiden(x: i32, y: i32) i64 {
    return @divTrunc(x, y);
}

0000000000000020 <divWiden>:
      20: 89 f8            movl    %edi, %eax
      22: 99               cltd                     # знак %eax на весь %edx
      23: f7 fe            idivl   %esi             # 32-битное деление
      25: 48 98            cltq                     # знак %eax на весь %rax
      27: c3               retq

Пять инструкций и три разные роли.

• cltd готовит делимое: расширяет %eax в пару %edx:%eax.
• cltq расширяет результат: 32-битное частное превращается в 64-битное с сохранением знака.
• cqto из предыдущего листинга делает то же, что cltd, но на ширину выше.

Имена читаются как сокращения: l это long, то есть 32 бита, q это quad, 64 бита, d это double long, тоже 64 бита, но в паре регистров, o это oct, 128 бит в паре. Отсюда cltq это “32 бита в 64”, а cqto это “64 бита в 128”.

Проверить семантику деления в Zig полезно отдельно, потому что языки расходятся в том, как округлять отрицательное частное:

const std = @import("std");

test "четыре деления Zig на одной паре чисел" {
    const x: i64 = -7;
    const y: i64 = 2;

    // Усечение к нулю: ровно то, что делает idivq.
    try std.testing.expectEqual(@as(i64, -3), @divTrunc(x, y));
    try std.testing.expectEqual(@as(i64, -1), @rem(x, y));

    // Округление вниз: одной инструкции для этого нет.
    try std.testing.expectEqual(@as(i64, -4), @divFloor(x, y));
    try std.testing.expectEqual(@as(i64, 1), @mod(x, y));
}

$ zig test divs.zig
1/1 divs.test.четыре деления Zig на одной паре чисел...OK
All 1 tests passed.

@divTrunc и @rem ложатся на idivq один в один. @divFloor и @mod требуют поправки после деления, поэтому в дизассемблере у них появляются лишние инструкции. Zig не выбирает за тебя, какое из двух округлений имел в виду ты, и заставляет назвать его явно.

Отдельная история с безопасным режимом. У деления два способа сломаться: делитель ноль и переполнение частного, когда minInt(i64) делят на минус единицу. Обе проверки компилятор ставит перед инструкцией:

0000000000000000 <divSafe>:
       0: 50               pushq   %rax
       1: 48 b8 00 00 00 00 00 00 00 80   movabsq $-0x8000000000000000, %rax
       b: 48 31 f8         xorq    %rdi, %rax       # x равен minInt?
       e: 48 89 f1         movq    %rsi, %rcx
      11: 48 f7 d1         notq    %rcx             # y равен -1?
      14: 48 09 c1         orq     %rax, %rcx
      17: 74 23            je      0x3c             # оба сразу, это переполнение
      19: 48 85 f6         testq   %rsi, %rsi
      1c: 74 23            je      0x41             # делитель ноль
      1e: 48 89 f8         movq    %rdi, %rax
      ...
      2d: 48 99            cqto
      2f: 48 f7 fe         idivq   %rsi

Проверка на переполнение написана изящно: x ^ minInt даёт ноль ровно тогда, когда x равен minInt, а ~y даёт ноль ровно тогда, когда y равен минус единице. Их логическое ИЛИ равно нулю только если оба условия выполнились, и тогда je уводит в панику. Два сравнения свернулись в одно.

Идиома xor: почему не movq $0

Обнуление регистра встречается в машинном коде чаще любой другой операции, и пишут его почти всегда через исключающее ИЛИ регистра с самим собой. В исходнике при этом никакого XOR нет:

export fn zeroOut() i64 {
    return 0;
}

0000000000000000 <zeroOut>:
       0: 31 c0            xorl    %eax, %eax
       2: c3               retq

Почему не movq $0, %rax? Посмотри на байты четырёх способов записать одно и то же:

      53: 31 c0                        xorl    %eax, %eax      # 2 байта
      55: 48 31 c0                     xorq    %rax, %rax      # 3 байта
      58: b8 00 00 00 00               movl    $0x0, %eax      # 5 байт
      5d: 48 c7 c0 00 00 00 00         movq    $0x0, %rax      # 7 байт

Разница в три с половиной раза по размеру. Работает это потому, что x ^ x равно нулю для любого x, и потому, что любая 32-битная запись в регистр обнуляет его старшую половину. Это правило из прошлого урока здесь окупается вдвойне: xorl %eax, %eax обнуляет весь %rax, а префикс 48 для этого не нужен.

Есть и вторая причина, невидимая в байтах. Процессор распознаёт xor регистра с самим собой как особый случай и не считает его зависимостью от прежнего значения регистра. Инструкция разрывает цепочку зависимостей, а не продолжает её, и планировщик может выполнить её сразу.

У приёма есть побочный эффект: xor выставляет флаги, а mov нет. Если между сравнением и переходом нужно обнулить регистр, xor туда ставить нельзя, и там появляется movl $0. Это ровно упражнение 3.11 из книги, и теперь у тебя есть ответ со всеми тремя частями: что делает инструкция, чем её можно заменить и сколько байт стоит каждый вариант.

Реверс: восстанови функцию по ассемблеру

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

Начнём с разобранного примера. Аргументы x, y и z по System V ABI лежат в %rdi, %rsi и %rdx, результат возвращается в %rax.

0000000000000020 <mystery>:
      20: 48 8d 04 b7      leaq    (%rdi,%rsi,4), %rax
      24: 48 8d 04 c0      leaq    (%rax,%rax,8), %rax
      28: 48 c1 fe 02      sarq    $0x2, %rsi
      2c: 48 29 f0         subq    %rsi, %rax
      2f: c3               retq

Идём по строкам.

1. leaq (%rdi,%rsi,4), %rax это x + 4*y. Обозначим t1.
2. leaq (%rax,%rax,8), %rax это t1 + 8*t1, то есть 9*t1. Обозначим t2.
3. sarq $0x2, %rsi это арифметический сдвиг y вправо на два. Сдвиг арифметический, значит y знаковый. Обозначим t3.
4. subq %rsi, %rax это t2 - t3, и он же результат.

Собираем:

export fn mystery(x: i64, y: i64) i64 {
    const t1 = x + 4 * y;
    const t2 = t1 * 9;
    const t3 = y >> 2;
    return t2 - t3;
}

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

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

decode2:
  subq   %rdx, %rsi
  imulq  %rsi, %rdi
  movq   %rsi, %rax
  salq   $63, %rax
  sarq   $63, %rax
  xorq   %rdi, %rax
  ret

Читаем по строкам.

1. subq %rdx, %rsi записывает y - z в %rsi. Дальше зовём это t.
2. imulq %rsi, %rdi кладёт x * t в %rdi.
3. movq %rsi, %rax копирует t в %rax.
4. salq $63, %rax двигает t влево на 63 бита. От всего числа остаётся только младший бит, и он оказывается знаковым.
5. sarq $63, %rax двигает обратно вправо арифметически, размножая знаковый бит на все 64. Итог: если младший бит t был единицей, в %rax теперь все единицы, то есть минус один; иначе ноль.
6. xorq %rdi, %rax складывает произведение с этой маской по модулю два. Исключающее ИЛИ с числом из одних единиц это побитовое отрицание, а исключающее ИЛИ с нулём не меняет ничего.

Значит, функция возвращает x * (y - z), инвертируя все биты результата, когда y - z нечётное. Пара salq $63 плюс sarq $63 это идиома “размножить младший бит на всё слово”, и её стоит запомнить: она встречается везде, где хотят получить маску из условия без ветвления.

Пишем на Zig. Умножение и вычитание берём заворачивающимися, потому что листинг никаких проверок не делал:

export fn decode2(x: i64, y: i64, z: i64) i64 {
    const t = y -% z;
    const product = x *% t;
    const mask = (t << 63) >> 63;
    return product ^ mask;
}

А вот что из этого вышло у нашего компилятора:

0000000000000000 <decode2>:
       0: 48 89 f0         movq    %rsi, %rax
       3: 48 29 d0         subq    %rdx, %rax       # t = y - z
       6: 48 0f af f8      imulq   %rax, %rdi       # x * t
       a: 83 e0 01         andl    $0x1, %eax       # взять младший бит
       d: 48 f7 d8         negq    %rax             # 0 или -1
      10: 48 31 f8         xorq    %rdi, %rax
      13: c3               retq

Пара сдвигов превратилась в пару andl $1 плюс negq, и это тот же результат другим путём: отрицание единицы в дополнительном коде даёт число из одних единиц, отрицание нуля даёт ноль. Обе идиомы весят по две инструкции, но у второй короче зависимость и она не занимает лишний регистр.

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

const std = @import("std");

fn decode2(x: i64, y: i64, z: i64) i64 {
    const t = y -% z;
    const product = x *% t;
    const mask = (t << 63) >> 63;
    return product ^ mask;
}

test "decode2 повторяет ассемблер" {
    // Младший бит y - z решает, инвертируется результат или нет.
    try std.testing.expectEqual(@as(i64, 12), decode2(3, 7, 3));
    try std.testing.expectEqual(@as(i64, -16), decode2(3, 8, 3));
    try std.testing.expectEqual(@as(i64, 0), decode2(0, 1, 1));
    try std.testing.expectEqual(@as(i64, -1), decode2(0, 2, 1));
}

$ zig test decode2_test.zig
1/1 decode2_test.test.decode2 повторяет ассемблер...OK
All 1 tests passed.

Первые два случая показывают развилку: при y - z равном 4 маска нулевая и ответ это просто 3 * 4, при y - z равном 5 маска это минус один и ответ это побитовое отрицание пятнадцати, то есть минус шестнадцать.

Шаг проекта: zt учится считать

После прошлого шага zt disasm читает адрес в любой форме и всё семейство mov. Но возьми любую настоящую функцию, и уже вторая или третья строка окажется (bad): addq, leaq, shlq, imulq декодер пока не знает. Сегодня он узнает всё, что было в этом уроке: lea, восемь операций арифметики и логики, сдвиги и повороты, три формы imul, группу с mul, div, neg и not, инкремент и декремент. Заодно и многобайтный nop, которым компилятор заполняет промежутки между функциями.

Три файла вместо одного

Таблица опкодов на этом шаге вырастает втрое, и держать разбор всех семейств в decoder.zig становится неудобно. Разложим его по файлам: decoder.zig остаётся таблицей «какой байт к какому семейству», src/x86/ops_data.zig забирает пересылки данных, src/x86/ops_alu.zig получает арифметику. Функции семейства mov переезжают из decoder.zig целиком.

Первым делом помощники в курсоре. На прошлом шаге каждая функция собирала операнды руками: result.operands[0] = ..., result.operands[1] = ..., result.operand_count = 2. Таких функций теперь будет два десятка, поэтому рядом с one в src/x86/cursor.zig появляются two и three:

    /// Инструкция с одним операндом.
    pub fn one(cursor: Cursor, mnemonic: []const u8, suffix: ?u8, first: Operand) Instruction {
        var result = cursor.done(mnemonic, suffix);
        result.operands[0] = first;
        result.operand_count = 1;
        return result;
    }

    /// Инструкция с двумя операндами. Порядок уже такой, каким его печатает
    /// AT&T: сначала источник, потом приёмник.
    pub fn two(
        cursor: Cursor,
        mnemonic: []const u8,
        suffix: ?u8,
        first: Operand,
        second: Operand,
    ) Instruction {
        var result = cursor.done(mnemonic, suffix);
        result.operands[0] = first;
        result.operands[1] = second;
        result.operand_count = 2;
        return result;
    }

    /// Инструкция с тремя операндами: так выглядит трёхоперандный imul.
    pub fn three(
        cursor: Cursor,
        mnemonic: []const u8,
        suffix: ?u8,
        first: Operand,
        second: Operand,
        third: Operand,
    ) Instruction {
        var result = cursor.two(mnemonic, suffix, first, second);
        result.operands[2] = third;
        result.operand_count = 3;
        return result;
    }

Три операнда бывают у единственной инструкции нашего подмножества, у imul с константой. Под них в Instruction с самого начала заведён массив operands длиной max_operands, равной трём, и вот он наконец заполняется целиком.

Пересылки данных: mov переезжает, lea приходит

Файл src/x86/ops_data.zig целиком:

//! Инструкции пересылки данных: `mov` во всех видах, расширение узкого
//! значения до широкого, `lea`, `push` и `pop`.
//!
//! Общая для всего декодера идея: у опкода есть форма, и форма говорит, откуда
//! берутся операнды. Форма MR значит «поле reg байта ModRM это источник»,
//! форма RM значит «источник это r/m». В синтаксисе AT&T источник печатается
//! первым, поэтому обе формы отличаются только порядком двух присваиваний.

const std = @import("std");

const cursor_mod = @import("cursor.zig");
const instruction = @import("instruction.zig");

const Cursor = cursor_mod.Cursor;
const Instruction = instruction.Instruction;
const Operand = instruction.Operand;
const Size = instruction.Size;

/// Форма MR: `op %reg, r/m`.
pub fn regToRm(cursor: *Cursor, mnemonic: []const u8, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return cursor.two(
        mnemonic,
        size.suffix(),
        .{ .register = cursor.register(modrm.reg, size) },
        modrm.rm,
    );
}

/// Форма RM: `op r/m, %reg`.
pub fn rmToReg(cursor: *Cursor, mnemonic: []const u8, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return cursor.two(
        mnemonic,
        size.suffix(),
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, size) },
    );
}

/// Опкоды 0xB0 и 0xB8: номер регистра прямо в опкоде, значение сразу за ним.
/// При REX.W значение занимает все восемь байтов, и это единственный способ
/// положить в регистр произвольную 64-битную константу.
pub fn immediateToRegister(cursor: *Cursor, low_bits: u8, size: Size) ?Instruction {
    const index: u4 = @as(u4, @truncate(low_bits)) | cursor.prefixes.rexB();
    const wide = size == .qword;
    const value = (if (wide) cursor.readSigned(8) else cursor.readImmediate(size)) orelse return null;

    return cursor.two(
        if (wide) "movabs" else "mov",
        size.suffix(),
        .{ .immediate = value },
        .{ .register = cursor.register(index, size) },
    );
}

/// Опкоды 0xC6 и 0xC7: непосредственное значение в r/m.
/// Поле reg байта ModRM здесь обязано быть нулём.
pub fn immediateToRm(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    if (modrm.digit != 0) return null;
    const value = cursor.readImmediate(size) orelse return null;
    return cursor.two("mov", size.suffix(), .{ .immediate = value }, modrm.rm);
}

/// Расширение узкого значения до широкого. Мнемоника несёт обе ширины сразу:
/// `movzbl` это «нулями из одного байта в четыре».
pub fn extend(cursor: *Cursor, mnemonic: []const u8, from: Size, to: Size) ?Instruction {
    const modrm = cursor.readModRm(from) orelse return null;
    return cursor.two(
        mnemonic,
        to.suffix(),
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, to) },
    );
}

/// `lea` считает адрес по тем же полям, что и обращение в память, но в память
/// не ходит: результат это само вычисленное число. Поэтому r/m обязан быть
/// адресом, а не регистром.
pub fn loadEffectiveAddress(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    switch (modrm.rm) {
        .memory => {},
        else => return null,
    }
    return cursor.two(
        "lea",
        size.suffix(),
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, size) },
    );
}

/// Однобайтные `push` и `pop`: номер регистра сидит в трёх младших битах
/// самого опкода, а REX.B добавляет к нему четвёртый бит.
pub fn pushPop(cursor: *Cursor, mnemonic: []const u8, low_bits: u8) Instruction {
    const index: u4 = @as(u4, @truncate(low_bits)) | cursor.prefixes.rexB();
    // В 64-битном режиме push и pop работают с восемью байтами без REX.W.
    return cursor.one(mnemonic, 'q', .{ .register = cursor.register(index, .qword) });
}

test "lea отказывается работать с регистром вместо адреса" {
    // mod равен 3, значит r/m это регистр, и такой lea не бывает.
    var cursor: Cursor = .{ .bytes = &.{0xc1}, .address = 0 };
    try std.testing.expectEqual(@as(?Instruction, null), loadEffectiveAddress(&cursor, .qword));
}

Две вещи здесь новые. Первая: regToRm и rmToReg получили параметр mnemonic. Форма MR и форма RM не принадлежат mov, ими кодируется половина таблицы, и уже в следующем шаге test использует regToRm как есть.

Вторая это loadEffectiveAddress. Опкод 0x8d читает ModRM с той же формулой адреса, что и mov, только ничего не читает из памяти. Отсюда проверка на .memory: если mod равен трём, поле r/m называет регистр, а у регистра нет адреса. Такой lea процессор отвергает как недопустимую инструкцию, и декодер обязан вернуть null, а не напечатать бессмыслицу вроде leaq %rcx, %rax.

Арифметика: регулярная часть таблицы

Файл src/x86/ops_alu.zig:

//! Арифметика, логика, сдвиги, умножение и деление.
//!
//! Эта часть таблицы опкодов устроена регулярно, и на регулярности всё
//! держится. Восемь операций (`add`, `or`, `adc`, `sbb`, `and`, `sub`, `xor`,
//! `cmp`) занимают подряд идущие блоки по восемь опкодов: у `add` блок
//! начинается с 0x00, у `or` с 0x08, и так далее до `cmp` с 0x38. Внутри
//! блока смещение говорит форму: 0 и 1 это «регистр в r/m» для байта и для
//! широкого операнда, 2 и 3 это обратное направление, 4 и 5 это работа
//! с аккумулятором и непосредственным значением.
//!
//! Остальное это группы: один опкод, а какая именно операция, говорит поле
//! reg байта ModRM. Так устроены 0x80, 0x81, 0x83 (арифметика с константой),
//! 0xC0 и дальше (сдвиги), 0xF6 и 0xF7, 0xFE и 0xFF.

const std = @import("std");

const cursor_mod = @import("cursor.zig");
const instruction = @import("instruction.zig");

const Cursor = cursor_mod.Cursor;
const Instruction = instruction.Instruction;
const Operand = instruction.Operand;
const Size = instruction.Size;

/// Восемь операций в порядке их блоков опкодов. Индекс в этой таблице
/// это и есть номер блока, и он же номер операции в группе 0x80.
pub const alu_names = [8][]const u8{ "add", "or", "adc", "sbb", "and", "sub", "xor", "cmp" };

/// Сдвиги и повороты в порядке поля reg байта ModRM. Номера 4 и 6 дают одну
/// и ту же операцию: у сдвига влево два кодирования, и второе почти не
/// встречается, но кодировщики его выдают.
pub const shift_names = [8][]const u8{ "rol", "ror", "rcl", "rcr", "shl", "shr", "shl", "sar" };

/// Блок из восьми опкодов, отведённый одной операции. Возвращает номер
/// операции и смещение внутри блока, если опкод вообще из этой области.
pub fn aluSlot(opcode: u8) ?struct { operation: u3, form: u3 } {
    if (opcode >= 0x40) return null;
    const form: u3 = @truncate(opcode & 0b111);
    // Смещения 6 и 7 в блоке заняты старыми инструкциями, которых
    // в 64-битном режиме нет вовсе.
    if (form > 5) return null;
    return .{ .operation = @truncate(opcode >> 3), .form = form };
}

/// Опкоды с 0x00 по 0x3D: одна из восьми операций в одной из шести форм.
pub fn aluOperation(cursor: *Cursor, operation: u3, form: u3) ?Instruction {
    const mnemonic = alu_names[operation];
    const wide = cursor.width();

    return switch (form) {
        0 => regToRm(cursor, mnemonic, .byte),
        1 => regToRm(cursor, mnemonic, wide),
        2 => rmToReg(cursor, mnemonic, .byte),
        3 => rmToReg(cursor, mnemonic, wide),
        // Формы 4 и 5 работают с аккумулятором, и он в коде не записан:
        // его номер ноль подразумевается самим опкодом.
        4 => accumulator(cursor, mnemonic, .byte),
        5 => accumulator(cursor, mnemonic, wide),
        else => null,
    };
}

/// Группа 0x80, 0x81, 0x83: арифметика с непосредственным значением.
/// У 0x83 значение занимает один байт и расширяется знаком до ширины
/// операнда: так `subq $8, %rsp` укладывается в четыре байта вместо семи.
pub fn aluImmediate(cursor: *Cursor, size: Size, immediate_size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    const value = cursor.readImmediate(immediate_size) orelse return null;
    return cursor.two(alu_names[modrm.digit], size.suffix(), .{ .immediate = value }, modrm.rm);
}

/// Группы сдвигов. Счётчик приходит тремя способами: непосредственным
/// значением, единицей, которую никто не записывает, или регистром cl.
pub const ShiftCount = union(enum) {
    immediate,
    one,
    register_cl,
};

pub fn shift(cursor: *Cursor, size: Size, count: ShiftCount) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    const mnemonic = shift_names[modrm.digit];

    return switch (count) {
        .immediate => blk: {
            const value = cursor.readSigned(1) orelse break :blk null;
            break :blk cursor.two(mnemonic, size.suffix(), .{ .immediate = value }, modrm.rm);
        },
        // Сдвиг на единицу печатается одним операндом: единица подразумевается.
        .one => cursor.one(mnemonic, size.suffix(), modrm.rm),
        .register_cl => cursor.two(
            mnemonic,
            size.suffix(),
            .{ .register = cursor.register(1, .byte) },
            modrm.rm,
        ),
    };
}

/// Группа 0xF6 и 0xF7. Поле reg выбирает одну из восьми операций.
/// Умножение и деление работают с парой регистров молча, не записывая их.
/// Номера 0 и 1 это `test` с непосредственным значением, до него дойдём
/// в следующем шаге.
pub fn group3(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return switch (modrm.digit) {
        0, 1 => null,
        2 => cursor.one("not", size.suffix(), modrm.rm),
        3 => cursor.one("neg", size.suffix(), modrm.rm),
        4 => cursor.one("mul", size.suffix(), modrm.rm),
        5 => cursor.one("imul", size.suffix(), modrm.rm),
        6 => cursor.one("div", size.suffix(), modrm.rm),
        7 => cursor.one("idiv", size.suffix(), modrm.rm),
    };
}

/// Группа 0xFE и 0xFF в той части, что относится к арифметике.
/// Переходы и вызовы из той же группы разбираются отдельно.
pub fn incrementDecrement(cursor: *Cursor, digit: u3, rm: Operand, size: Size) ?Instruction {
    return switch (digit) {
        0 => cursor.one("inc", size.suffix(), rm),
        1 => cursor.one("dec", size.suffix(), rm),
        else => null,
    };
}

/// Двухоперандный `imul`: опкод 0x0F 0xAF, результат ложится в поле reg.
pub fn imulTwoOperand(cursor: *Cursor, size: Size) ?Instruction {
    return rmToReg(cursor, "imul", size);
}

/// Трёхоперандный `imul`: опкоды 0x69 и 0x6B. Множитель записан прямо
/// в инструкции, поэтому операндов три, а не два.
pub fn imulThreeOperand(cursor: *Cursor, size: Size, immediate_size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    const value = cursor.readImmediate(immediate_size) orelse return null;
    return cursor.three(
        "imul",
        size.suffix(),
        .{ .immediate = value },
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, size) },
    );
}

/// Аккумулятор и непосредственное значение: `add $0x1, %eax`.
/// Номер регистра здесь нулевой и в машинном коде не записан.
fn accumulator(cursor: *Cursor, mnemonic: []const u8, size: Size) ?Instruction {
    const value = cursor.readImmediate(size) orelse return null;
    return cursor.two(
        mnemonic,
        size.suffix(),
        .{ .immediate = value },
        .{ .register = cursor.register(0, size) },
    );
}

fn regToRm(cursor: *Cursor, mnemonic: []const u8, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return cursor.two(
        mnemonic,
        size.suffix(),
        .{ .register = cursor.register(modrm.reg, size) },
        modrm.rm,
    );
}

fn rmToReg(cursor: *Cursor, mnemonic: []const u8, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return cursor.two(
        mnemonic,
        size.suffix(),
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, size) },
    );
}

test "блоки опкодов идут по восемь на операцию" {
    try std.testing.expectEqualStrings("add", alu_names[aluSlot(0x01).?.operation]);
    try std.testing.expectEqualStrings("sub", alu_names[aluSlot(0x29).?.operation]);
    try std.testing.expectEqualStrings("cmp", alu_names[aluSlot(0x3b).?.operation]);
    try std.testing.expectEqual(@as(u3, 3), aluSlot(0x3b).?.form);
    // Смещения 6 и 7 внутри блока в 64-битном режиме не используются.
    try std.testing.expectEqual(@as(?@TypeOf(aluSlot(0).?), null), aluSlot(0x06));
}

Главная функция файла самая короткая, aluSlot. Посмотри на первые шестьдесят четыре опкода в двоичной записи: 00 000 001 это addl %reg, r/m, 00 101 001 это subl, 00 111 001 это cmpl. Три средних бита это номер операции, три младших это форма. Поэтому opcode >> 3 сразу даёт индекс в alu_names, opcode & 0b111 даёт форму, и сорок восемь опкодов разбираются одной функцией на шести ветках. Формы 6 и 7 в блоках заняты чем-то другим: старыми инструкциями вроде push %es и daa, которых в 64-битном режиме нет, префиксами замены сегмента (до них дойдём в следующем уроке) и байтом 0x0f. Он форма 7 блока or и ведёт к двухбайтным опкодам, поэтому проверка form > 5 обязательна: без неё 0x0f ушёл бы в арифметику.

Остальное это группы, и в каждой повторяется приём из урока: опкод один, а операцию выбирает поле reg байта ModRM. В курсоре оно лежит в digit, без бита REX.R, потому что здесь это не регистр, а продолжение опкода.

• aluImmediate обслуживает 0x80, 0x81 и 0x83, и номер операции в группе совпадает с номером блока: /5 это sub и там, и там. У 0x83 значение занимает один байт и расширяется знаком, поэтому subq $0x20, %rsp укладывается в четыре байта.
• shift получает счётчик тремя способами, ровно по разделу про сдвиги: байт в инструкции, подразумеваемая единица (у 0xd1 операнд печатается один) и регистр %cl (в байтах инструкции он не записан, его номер зашит в саму функцию).
• В shift_names номер 6 повторяет номер 4. У сдвига влево два кодирования, и ассемблер sal и shl кодирует одинаково, через /4. Поэтому в фикстуре написано sall %cl, %edx, а напечатано shll: мнемоник две, инструкция одна.
• group3 это та самая группа 0xf7 из упражнения про байты 48 f7 e6 и 48 f7 ee. Умножение и деление с одним операндом печатаются одним операндом, хотя работают с парой %rdx:%rax: неявные регистры в машинном коде не записаны, и AT&T их не показывает. Номера 0 и 1 пока возвращают null: это test, до него дойдём в следующем уроке.
• imulTwoOperand и imulThreeOperand закрывают остальные две формы imul. Трёхоперандная читает непосредственное значение после ModRM, и у 0x6b оно однобайтное, как у 0x83.

Две последние функции файла повторяют формы из ops_data.zig слово в слово. Так файл читается сам по себе, без прыжков к соседу; если такое повторение тебе не нравится, импортируй их из ops_data.zig, на поведение это не влияет.

Таблица декодера

В src/x86/decoder.zig функции decode, bad и fixupRip остались как были. Меняются импорты и сама таблица:

const alu = @import("ops_alu.zig");
const cursor_mod = @import("cursor.zig");
const data = @import("ops_data.zig");
const instruction = @import("instruction.zig");

pub const Cursor = cursor_mod.Cursor;
pub const Instruction = instruction.Instruction;
pub const Operand = instruction.Operand;
pub const Register = instruction.Register;
pub const Size = instruction.Size;

/// Таблица однобайтных опкодов. `null` означает «не наш байт»:
/// вызывающий превратит это в `(bad)`.
fn decodeOpcode(cursor: *Cursor, opcode: u8) ?Instruction {
    const wide = cursor.width();

    // Первые шестьдесят четыре опкода это восемь арифметических и логических
    // операций по восемь форм на каждую.
    if (alu.aluSlot(opcode)) |slot| {
        return alu.aluOperation(cursor, slot.operation, slot.form);
    }

    return switch (opcode) {
        0x50...0x57 => data.pushPop(cursor, "push", opcode - 0x50),
        0x58...0x5f => data.pushPop(cursor, "pop", opcode - 0x58),

        // Знаковое расширение четырёх байтов в восемь.
        0x63 => data.extend(cursor, "movsl", .dword, .qword),

        // Трёхоперандный imul: множитель записан прямо в инструкции.
        0x69 => alu.imulThreeOperand(cursor, wide, wide),
        0x6b => alu.imulThreeOperand(cursor, wide, .byte),

        // Арифметика с непосредственным значением. У 0x83 значение занимает
        // один байт и расширяется знаком до ширины операнда.
        0x80 => alu.aluImmediate(cursor, .byte, .byte),
        0x81 => alu.aluImmediate(cursor, wide, wide),
        0x83 => alu.aluImmediate(cursor, wide, .byte),

        // Семейство mov между регистром и памятью.
        0x88 => data.regToRm(cursor, "mov", .byte),
        0x89 => data.regToRm(cursor, "mov", wide),
        0x8a => data.rmToReg(cursor, "mov", .byte),
        0x8b => data.rmToReg(cursor, "mov", wide),
        0x8d => data.loadEffectiveAddress(cursor, wide),

        0x90 => cursor.done("nop", null),
        // Расширение аккумулятора со знаком. Мнемоника целиком зависит
        // от ширины, суффикса у неё нет.
        0x98 => cursor.done(widthName(cursor.*, "cbtw", "cwtl", "cltq"), null),
        0x99 => cursor.done(widthName(cursor.*, "cwtd", "cltd", "cqto"), null),

        // mov с непосредственным значением прямо в регистр из опкода.
        0xb0...0xb7 => data.immediateToRegister(cursor, opcode - 0xb0, .byte),
        0xb8...0xbf => data.immediateToRegister(cursor, opcode - 0xb8, wide),

        // Сдвиги: на константу, на единицу и на значение регистра cl.
        0xc0 => alu.shift(cursor, .byte, .immediate),
        0xc1 => alu.shift(cursor, wide, .immediate),
        0xd0 => alu.shift(cursor, .byte, .one),
        0xd1 => alu.shift(cursor, wide, .one),
        0xd2 => alu.shift(cursor, .byte, .register_cl),
        0xd3 => alu.shift(cursor, wide, .register_cl),

        0xc3 => cursor.done("ret", 'q'),
        0xc6 => data.immediateToRm(cursor, .byte),
        0xc7 => data.immediateToRm(cursor, wide),
        0xc9 => cursor.done("leave", null),

        0xf4 => cursor.done("hlt", null),
        0xf6 => alu.group3(cursor, .byte),
        0xf7 => alu.group3(cursor, wide),
        0xfe => group5(cursor, .byte),
        0xff => group5(cursor, wide),

        0x0f => decodeTwoByte(cursor),
        else => null,
    };
}

/// Опкоды с ведущим байтом 0x0F.
fn decodeTwoByte(cursor: *Cursor) ?Instruction {
    const opcode = cursor.next() orelse return null;
    const wide = cursor.width();

    return switch (opcode) {
        // ud2 компилятор ставит в конец функции, из которой нет выхода.
        0x0b => cursor.done("ud2", null),

        // Многобайтный nop: им компилятор выравнивает начало следующей
        // функции. Занимает столько байтов, сколько нужно, а делает ничего.
        0x1f => multiByteNop(cursor, wide),

        0xaf => alu.imulTwoOperand(cursor, wide),

        // Расширение узкого значения до широкого: нулями и знаком.
        0xb6 => data.extend(cursor, "movzb", .byte, wide),
        0xb7 => data.extend(cursor, "movzw", .word, wide),
        0xbe => data.extend(cursor, "movsb", .byte, wide),
        0xbf => data.extend(cursor, "movsw", .word, wide),

        else => null,
    };
}

/// Опкод 0x0F 0x1F: nop с операндом в памяти. Адрес нужен только затем,
/// чтобы задать длину: чем сложнее форма адреса, тем длиннее инструкция.
fn multiByteNop(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    if (modrm.digit != 0) return null;
    return cursor.one("nop", size.suffix(), modrm.rm);
}

/// Группа 0xFE и 0xFF: инкремент, декремент, а дальше переходы и вызовы,
/// до которых декодер дорастёт на следующих шагах.
fn group5(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return alu.incrementDecrement(cursor, modrm.digit, modrm.rm, size);
}

Проверка aluSlot стоит до switch, и это не вкусовщина. Иначе пришлось бы выписать сорок восемь веток руками, и таблица превратилась бы в список, где опечатку в одном опкоде глазами не найдёшь.

Функция group5 пока знает только инкремент и декремент. Номера со второго по шестой в той же группе 0xff это косвенные вызовы и переходы и push из памяти. До косвенных вызовов и переходов декодер дорастёт в уроке 13, а до push из памяти в уроке про динамическую компоновку.

multiByteNop нужен не ради арифметики, а ради фикстуры: компилятор выравнивает начало каждой функции по шестнадцати байтам и заполняет промежуток одной длинной инструкцией nop. Её операнд в памяти ничего не значит, он нужен только затем, чтобы инструкция получилась нужной длины. Без этой строки декодер споткнулся бы о 0f 1f и вместо одной строки напечатал бы несколько строк мусора.

Осталось сослаться на новые файлы из корня модуля, чтобы их встроенные тесты попали в прогон. В src/root.zig структура x86 получает две строки:

pub const x86 = struct {
    pub const cursor = @import("x86/cursor.zig");
    pub const decoder = @import("x86/decoder.zig");
    pub const formatter = @import("x86/formatter.zig");
    pub const instruction = @import("x86/instruction.zig");
    pub const ops_alu = @import("x86/ops_alu.zig");
    pub const ops_data = @import("x86/ops_data.zig");
    pub const registers = @import("x86/registers.zig");
};

И номер шага в build.zig: const project_steps = [_]u8{ 6, 7, 9, 10, 11 };.

Фикстура и тесты шага

Фикстура собрана тем же приёмом, что и на прошлом шаге: asm volatile внутри функции с соглашением naked, чтобы в секции лежали ровно наши инструкции.

//! Фикстура шага 11: lea, арифметика, сдвиги, умножение и деление.
//!
//! Собирается так:
//!   zig build-obj fixtures/step_11.zig -O ReleaseFast \
//!       -target x86_64-linux-musl -femit-bin=fixtures/step_11.o

/// Все восемь операций блока и все формы, в которых они кодируются.
export fn ztArithmetic() callconv(.naked) void {
    asm volatile (
        \\addl %eax, %ebx
        \\addq %r8, %r9
        \\addb %al, %cl
        \\addl %eax, (%rdx)
        \\addl (%rdx), %eax
        \\addl $1, %eax
        \\addb $1, %al
        \\orl %eax, %ebx
        \\adcl %eax, %ebx
        \\sbbl %eax, %ebx
        \\andq %rax, %rbx
        \\subq %rax, %rbx
        \\subl (%rdi), %esi
        \\xorl %eax, %eax
        \\cmpq %rax, %rbx
        \\cmpl (%rdi), %esi
        \\addq $8, %rsp
        \\subq $0x20, %rsp
        \\andl $0xff, %eax
        \\cmpl $0x1234, %eax
        \\cmpq $0, (%rdi)
        \\orb $0x10, (%rsi)
        \\ret
    );
}

/// lea, сдвиги, умножение, деление и одноместные операции.
export fn ztShiftsAndMul() callconv(.naked) void {
    asm volatile (
        \\leaq 8(%rax), %rdx
        \\leaq (%rax,%rcx,4), %rdx
        \\leaq 0x10(%rax,%rcx,8), %rdx
        \\leal (%rdi,%rdi,2), %eax
        \\shlq $3, %rax
        \\shrl $1, %eax
        \\sarq $0x3f, %rax
        \\roll $4, %eax
        \\rorq $8, %rbx
        \\shll %eax
        \\sarq %rax
        \\shrq %cl, %rax
        \\sall %cl, %edx
        \\imulq %rbx, %rax
        \\imull %esi, %edi
        \\imull $10, %eax, %ecx
        \\imulq $0x1234, %rbx, %rdx
        \\imulq %rcx
        \\mulq %rcx
        \\idivq %rcx
        \\divl %esi
        \\negq %rax
        \\notl %eax
        \\incq %rax
        \\decl %eax
        \\incb (%rdi)
        \\decq 8(%rsp)
        \\ret
    );
}

zig build-obj fixtures/step_11.zig -O ReleaseFast \
    -target x86_64-linux-musl -femit-bin=fixtures/step_11.o
objdump -d fixtures/step_11.o > fixtures/step_11.objdump.txt

Эталон заодно показывает две вещи, которых в исходнике нет. Функции легли в секцию в обратном порядке: ztShiftsAndMul с адреса 0x0, ztArithmetic с 0x60. А между ними, на 0x59, стоит тот самый семибайтный nopl (%rax), который добивает первую функцию до границы в шестнадцать байт.

Тесты шага в tests/step_11.zig. Две главные проверки те же, что и раньше: ни одного (bad) и совпадение с objdump построчно. Остальные ловят по одной ловушке кодирования:

//! Шаг 11: lea, арифметика, сдвиги, умножение и деление.
//!
//! Первые шестьдесят четыре опкода устроены регулярно: восемь операций,
//! у каждой блок из восьми кодировок. Всё остальное в этом шаге это группы,
//! где сама операция выбирается полем reg байта ModRM.

const std = @import("std");

const fixtures = @import("fixtures");
const zt = @import("zt");

const support = @import("support.zig");

const decode = zt.x86.decoder.decode;

test "фикстура шага разбирается целиком" {
    try support.expectNoBadInstructions(fixtures.step_11);
}

test "вывод совпадает с objdump построчно" {
    try support.expectMatchesObjdump(fixtures.step_11);
}

test "предыдущие шаги остались зелёными" {
    try support.expectMatchesObjdump(fixtures.step_09);
    try support.expectMatchesObjdump(fixtures.step_10);
}

test "восемь операций живут в подряд идущих блоках по восемь опкодов" {
    try expectOne(&.{ 0x01, 0xc3 }, "addl\t%eax, %ebx");
    try expectOne(&.{ 0x09, 0xc3 }, "orl\t%eax, %ebx");
    try expectOne(&.{ 0x11, 0xc3 }, "adcl\t%eax, %ebx");
    try expectOne(&.{ 0x19, 0xc3 }, "sbbl\t%eax, %ebx");
    try expectOne(&.{ 0x48, 0x21, 0xc3 }, "andq\t%rax, %rbx");
    try expectOne(&.{ 0x48, 0x29, 0xc3 }, "subq\t%rax, %rbx");
    try expectOne(&.{ 0x31, 0xc0 }, "xorl\t%eax, %eax");
    try expectOne(&.{ 0x48, 0x39, 0xc3 }, "cmpq\t%rax, %rbx");
}

test "шесть форм внутри блока одной операции" {
    // Смещение в блоке задаёт ширину и направление, а не операцию.
    try expectOne(&.{ 0x00, 0xc1 }, "addb\t%al, %cl");
    try expectOne(&.{ 0x01, 0x02 }, "addl\t%eax, (%rdx)");
    try expectOne(&.{ 0x03, 0x02 }, "addl\t(%rdx), %eax");
    try expectOne(&.{ 0x04, 0x01 }, "addb\t$0x1, %al");
    try expectOne(&.{ 0x25, 0xff, 0x00, 0x00, 0x00 }, "andl\t$0xff, %eax");
}

test "у 0x83 значение занимает один байт и расширяется знаком" {
    // Четыре байта вместо семи: так кодируется почти вся работа со стеком.
    const short = [_]u8{ 0x48, 0x83, 0xec, 0x20 };
    try expectOne(&short, "subq\t$0x20, %rsp");
    try std.testing.expectEqual(@as(usize, 4), decode(&short, 0).length());
    try expectOne(&.{ 0x48, 0x83, 0x3f, 0x00 }, "cmpq\t$0x0, (%rdi)");
    try expectOne(&.{ 0x80, 0x0e, 0x10 }, "orb\t$0x10, (%rsi)");
}

test "lea считает адрес, но в память не ходит" {
    try expectOne(&.{ 0x48, 0x8d, 0x50, 0x08 }, "leaq\t0x8(%rax), %rdx");
    try expectOne(&.{ 0x48, 0x8d, 0x14, 0x88 }, "leaq\t(%rax,%rcx,4), %rdx");
    // Умножение на три одной инструкцией: база плюс индекс с множителем два.
    try expectOne(&.{ 0x8d, 0x04, 0x7f }, "leal\t(%rdi,%rdi,2), %eax");
}

test "счётчик сдвига приходит тремя способами" {
    try expectOne(&.{ 0x48, 0xc1, 0xe0, 0x03 }, "shlq\t$0x3, %rax");
    // Сдвиг на единицу печатается одним операндом: единица подразумевается.
    try expectOne(&.{ 0xd1, 0xe8 }, "shrl\t%eax");
    try expectOne(&.{ 0x48, 0xd3, 0xe8 }, "shrq\t%cl, %rax");
}

test "поле reg выбирает операцию сдвига" {
    try expectOne(&.{ 0xc1, 0xc0, 0x04 }, "roll\t$0x4, %eax");
    try expectOne(&.{ 0x48, 0xc1, 0xcb, 0x08 }, "rorq\t$0x8, %rbx");
    try expectOne(&.{ 0x48, 0xc1, 0xf8, 0x3f }, "sarq\t$0x3f, %rax");
}

test "группа 0xF7 это восемь разных инструкций под одним опкодом" {
    try expectOne(&.{ 0x48, 0xf7, 0xd8 }, "negq\t%rax");
    try expectOne(&.{ 0xf7, 0xd0 }, "notl\t%eax");
    try expectOne(&.{ 0x48, 0xf7, 0xe1 }, "mulq\t%rcx");
    try expectOne(&.{ 0x48, 0xf7, 0xe9 }, "imulq\t%rcx");
    try expectOne(&.{ 0xf7, 0xf6 }, "divl\t%esi");
    try expectOne(&.{ 0x48, 0xf7, 0xf9 }, "idivq\t%rcx");
}

test "три вида imul отличаются числом операндов" {
    try expectOne(&.{ 0x48, 0xf7, 0xe9 }, "imulq\t%rcx");
    try expectOne(&.{ 0x48, 0x0f, 0xaf, 0xc3 }, "imulq\t%rbx, %rax");
    try expectOne(&.{ 0x6b, 0xc8, 0x0a }, "imull\t$0xa, %eax, %ecx");
    try expectOne(
        &.{ 0x48, 0x69, 0xd3, 0x34, 0x12, 0x00, 0x00 },
        "imulq\t$0x1234, %rbx, %rdx",
    );
}

test "инкремент и декремент" {
    try expectOne(&.{ 0x48, 0xff, 0xc0 }, "incq\t%rax");
    try expectOne(&.{ 0xff, 0xc8 }, "decl\t%eax");
    try expectOne(&.{ 0xfe, 0x07 }, "incb\t(%rdi)");
    try expectOne(&.{ 0x48, 0xff, 0x4c, 0x24, 0x08 }, "decq\t0x8(%rsp)");
}

test "многобайтный nop выравнивает начало функции" {
    // Семь байтов, которые не делают ничего: адрес нужен только для длины.
    const padding = [_]u8{ 0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00 };
    try expectOne(&padding, "nopl\t(%rax)");
    try std.testing.expectEqual(@as(usize, 7), decode(&padding, 0).length());
}

/// Прогоняет байты через декодер и форматтер и сверяет мнемонику с операндами.
fn expectOne(code: []const u8, expected: []const u8) !void {
    const decoded = decode(code, 0);
    try std.testing.expectEqual(code.len, decoded.length());

    var buffer: [256]u8 = undefined;
    var out: std.Io.Writer = .fixed(&buffer);
    try zt.x86.formatter.format(&out, decoded);
    try std.testing.expectEqualStrings(expected, out.buffered());
}

Прогон

$ zig build test --summary all
Build Summary: 13/13 steps succeeded; 68/68 tests passed
test success
+- run test 19 pass (19 total) 24ms MaxRSS:2M
|  +- compile test Debug native cached 92ms MaxRSS:35M
+- run test 5 pass (5 total) 10ms MaxRSS:2M
|  +- compile test Debug native cached 89ms MaxRSS:35M
+- run test 7 pass (7 total) 25ms MaxRSS:2M
|  +- compile test Debug native cached 95ms MaxRSS:35M
+- run test 10 pass (10 total) 11ms MaxRSS:2M
|  +- compile test Debug native cached 92ms MaxRSS:35M
+- run test 14 pass (14 total) 10ms MaxRSS:2M
|  +- compile test Debug native cached 92ms MaxRSS:35M
+- run test 13 pass (13 total) 27ms MaxRSS:2M
   +- compile test Debug native cached 93ms MaxRSS:35M

Шесть строк run test это тесты внутри модулей и шаги 06, 07, 09, 10 и 11 по порядку. Шаги 09 и 10 зелёные не случайно: в tests/step_11.zig есть отдельный тест, который снова сверяет их фикстуры с эталоном, так что переезд mov в новый файл ничего не сломал.

Дизассемблер на фикстуре:

$ zig build && ./zig-out/bin/zt disasm fixtures/step_11.o
       0: 48 8d 50 08                  	leaq	0x8(%rax), %rdx
       4: 48 8d 14 88                  	leaq	(%rax,%rcx,4), %rdx
       8: 48 8d 54 c8 10               	leaq	0x10(%rax,%rcx,8), %rdx
       d: 8d 04 7f                     	leal	(%rdi,%rdi,2), %eax
      10: 48 c1 e0 03                  	shlq	$0x3, %rax
      14: d1 e8                        	shrl	%eax
      16: 48 c1 f8 3f                  	sarq	$0x3f, %rax
      1a: c1 c0 04                     	roll	$0x4, %eax
      1d: 48 c1 cb 08                  	rorq	$0x8, %rbx
      21: d1 e0                        	shll	%eax
      23: 48 d1 f8                     	sarq	%rax
      26: 48 d3 e8                     	shrq	%cl, %rax
      29: d3 e2                        	shll	%cl, %edx
      2b: 48 0f af c3                  	imulq	%rbx, %rax
      2f: 0f af fe                     	imull	%esi, %edi
      32: 6b c8 0a                     	imull	$0xa, %eax, %ecx
      35: 48 69 d3 34 12 00 00         	imulq	$0x1234, %rbx, %rdx
      3c: 48 f7 e9                     	imulq	%rcx
      3f: 48 f7 e1                     	mulq	%rcx
      42: 48 f7 f9                     	idivq	%rcx
      45: f7 f6                        	divl	%esi
      47: 48 f7 d8                     	negq	%rax
      4a: f7 d0                        	notl	%eax
      4c: 48 ff c0                     	incq	%rax
      4f: ff c8                        	decl	%eax
      51: fe 07                        	incb	(%rdi)
      53: 48 ff 4c 24 08               	decq	0x8(%rsp)
      58: c3                           	retq
      59: 0f 1f 80 00 00 00 00         	nopl	(%rax)
      60: 01 c3                        	addl	%eax, %ebx
      62: 4d 01 c1                     	addq	%r8, %r9
      65: 00 c1                        	addb	%al, %cl
      67: 01 02                        	addl	%eax, (%rdx)
      69: 03 02                        	addl	(%rdx), %eax
      6b: 83 c0 01                     	addl	$0x1, %eax
      6e: 04 01                        	addb	$0x1, %al
      70: 09 c3                        	orl	%eax, %ebx
      72: 11 c3                        	adcl	%eax, %ebx
      74: 19 c3                        	sbbl	%eax, %ebx
      76: 48 21 c3                     	andq	%rax, %rbx
      79: 48 29 c3                     	subq	%rax, %rbx
      7c: 2b 37                        	subl	(%rdi), %esi
      7e: 31 c0                        	xorl	%eax, %eax
      80: 48 39 c3                     	cmpq	%rax, %rbx
      83: 3b 37                        	cmpl	(%rdi), %esi
      85: 48 83 c4 08                  	addq	$0x8, %rsp
      89: 48 83 ec 20                  	subq	$0x20, %rsp
      8d: 25 ff 00 00 00               	andl	$0xff, %eax
      92: 3d 34 12 00 00               	cmpl	$0x1234, %eax
      97: 48 83 3f 00                  	cmpq	$0x0, (%rdi)
      9b: 80 0e 10                     	orb	$0x10, (%rsi)
      9e: c3                           	retq

И сравнение с эталоном:

$ objdump -d fixtures/step_11.o | tail -n +6 > od11.txt
$ ./zig-out/bin/zt disasm fixtures/step_11.o > zt11.txt
$ diff od11.txt zt11.txt
1d0
< 0000000000000000 <ztShiftsAndMul>:
18c17
<       35: 48 69 d3 34 12 00 00         	imulq	$0x1234, %rbx, %rdx     # imm = 0x1234
---
>       35: 48 69 d3 34 12 00 00         	imulq	$0x1234, %rbx, %rdx
31,32d29
< 
< 0000000000000060 <ztArithmetic>:
52c49
<       92: 3d 34 12 00 00               	cmpl	$0x1234, %eax           # imm = 0x1234
---
>       92: 3d 34 12 00 00               	cmpl	$0x1234, %eax

Расхождений два вида. Заголовки функций требуют таблицы символов, это по-прежнему дело будущего. А комментарий # imm = 0x1234 objdump из LLVM дописывает к большим непосредственным значениям. zt его не печатает, и тесты убирают комментарии с обеих сторон. Всё остальное совпадает посимвольно, вплоть до колонок и табуляций.

Практика

Задача урока собирает умножение и деление в одно место. Шесть функций, и главные две это mulFullUnsigned и mulFullSigned: они возвращают полное 128-битное произведение парой Pair{ low, high }, ровно так, как процессор раскладывает его по %rax и %rdx. Правило задачи: в телах этих двух функций нельзя упоминать ни u128, ни i128, ни само число 128. Отдельный тест читает исходник и ищет эту подстроку, так что комментарий с ней тоже не пройдёт. Раскладывай каждый аргумент на половины по 32 бита, собирай ответ из четырёх произведений и следи за переносом из суммы средних: именно он чаще всего теряется. Знаковый случай выражается через беззнаковый поправкой старшей половины по знакам аргументов.

Остальные четыре функции короче. storeUProd и storeSProd кладут собранное число по указателю, как пара movq в скомпилированном коде, uremdiv отдаёт частное и остаток от беззнакового деления, а arith2 надо восстановить по ассемблеру из условия задачи. Сложение и вычитание пиши через +% и -%: задача собирается в отладочном режиме, где обычный минус паникует на переполнении.

Упражнения

Итоги

• leaq считает формулу Imm + rb + s*ri и кладёт результат в регистр, не касаясь памяти. Приёмник обязан быть регистром, размер всегда 64 бита, флаги не меняются.
• Если база и индекс это один и тот же регистр, rb + s*ri превращается в (1+s)*x, и одна инструкция умножает на 2, 3, 5 или 9. Без базы доступны 2, 4 и 8.
• Умножение на константу компилятор собирает из lea, shl, add, sub и neg, пока цепочка короткая. Константы вида 2^n - 1 берутся вычитанием, а на неудобных значениях компилятор переходит к imulq.
• Форма без базы длиннее формы с базой: поле базы 101 в байте SIB означает четырёхбайтовое смещение, и оно дописывается нулями. Умножить на 9 дешевле по размеру кода, чем на 8.
• Целочисленные операции делятся на четыре группы: leaq, унарные, бинарные и сдвиги. Все, кроме leaq, существуют в четырёх размерах и выставляют флаги.
• Унарные и бинарные операции умеют работать прямо по памяти, без пары «загрузить и записать». Компилятор предпочитает addq $1 вместо incq из-за частичного обновления флагов.
• Поле reg байта ModRM иногда содержит не номер регистра, а расширение опкода. Так под одним байтом f7 живут notq, negq, mulq, imulq, divq и idivq, а под 83 восемь операций с непосредственным операндом.
• Величина сдвига живёт либо в самой инструкции, либо ровно в регистре %cl, третьего не дано. Процессор берёт от него столько младших бит, сколько нужно по ширине операнда, а Zig поднимает это правило в тип Log2Int.
• В ReleaseSafe рядом с арифметикой появляются jo и seto: это чтение флага переполнения. В ReleaseFast их не бывает, потому что проверять нечего.
• Полное произведение дают формы с одним операндом, mulq и imulq: один множитель обязан лежать в %rax, результат раскладывается в пару %rdx:%rax. У imul три формы, и различает их число операндов.
• Деление устроено зеркально умножению: делимое в паре %rdx:%rax, частное в %rax, остаток в %rdx. Старшую половину надо подготовить: cqto для знакового случая, обнуление %rdx для беззнакового.
• Имена cltq, cltd и cqto читаются как сокращения ширин: l это 32 бита, q это 64, d и o это пара регистров вдвое шире.
• Обнуление регистра пишут через xorl %eax, %eax: два байта против семи у movq $0, плюс процессор не считает такой xor зависимостью от прежнего значения. Цена приёма в том, что он выставляет флаги, а mov нет.
• Чтобы восстановить исходник по листингу, подписывай справа от каждой инструкции, что оказалось в приёмнике, выражая это через имена аргументов.
• В шаге проекта zt disasm научился арифметике: шестьдесят четыре первых опкода разбираются по номеру (три средних бита это операция, три младших это форма), а группы 0x83, 0xc1, 0xf7 и 0xff выбирают операцию по полю reg байта ModRM.

Дальше

Ты научился читать арифметику: формулу внутри leaq, цепочки из сдвигов и сложений вместо умножения, пару %rdx:%rax для полного произведения и ритуал подготовки делимого. Но во всех листингах этого урока управление шло сверху вниз, без единой развилки. Следующий шаг это флаги, переходы и cmov: четыре бита, которые арифметика оставляет после себя, инструкции cmp и test, созданные только ради этих битов, кодирование условного перехода относительно счётчика команд и инструкция, которая выбирает значение вместо пути. Заодно станет понятно, зачем компилятору инструкция, которая считает, но молчит: leaq можно поставить между сравнением и переходом, не испортив условие.