Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Биты и целые по-зиговски

middle~110 мин

открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

Биты и целые по-зиговски

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

Цели урока

Проверять правила из книги не на бумаге, а перебором: сложение по модулю на u4, признак переполнения на i5.
Различать @bitCast, @intCast и @truncate по обещанию, которое каждое из них даёт компилятору.
Читать и писать числа из байтов через std.mem.readInt и std.mem.writeInt, менять порядок через @byteSwap и знать, зачем существует native_endian.
Понимать, почему счётчик сдвига имеет собственный тип std.math.Log2Int и почему сдвига ровно на ширину типа в Zig не существует.
Раскладывать умножение на константу в сдвиги и сложения двумя формами книги и сверять свою раскладку с тем, что реально выдал компилятор.
Объяснять, почему x >> k это не деление на 2^k для отрицательных чисел, и находить в дизассемблере поправку, которая это чинит.
Решить десять битовых головоломок из домашних задач второй главы с ограниченным набором операций.
Научить zt hexdump группировать байты словами и читать группы в обоих порядках.

Что уже сказано и что осталось за кадром

Три урока курса уже трогали эту тему, и каждый со своей стороны.

Где	Про что	Что оттуда нужно помнить
Биты и кодирование	почему двоичная, что такое разряд, как из битов получаются числа и символы	дополнительный код, вес старшего бита, сложение по модулю
Целые и дополнительный код	переполнение как реальная авария, `wrapping`, `checked`, `saturating`	переполнение это не редкость, а обычный случай на границе
Значения, типы и поток управления	целые любой ширины, `@as`, `@intCast`, `@truncate`, четыре семейства арифметики	ширина в имени типа, три преобразования, `+%` против `+`

Повторять это не будем. Урок закрывает четыре дыры, которые в тех уроках не поместились.

Первая. Книга рассуждает про машину шириной w бит и рисует таблицы для w = 4, потому что шестнадцать строк влезают на страницу. В C такой машины нет, и таблицы приходится принимать на веру. В Zig u4 это обычный тип, и таблица становится тестом, который либо зелёный, либо нет.

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

Третья. У сдвига в Zig есть отдельный тип счётчика, и это не мелочь синтаксиса, а способ убрать целый класс неопределённого поведения из языка.

Четвёртая. Умножение и деление на константу. Это единственное место главы, где книга прямо показывает работу оптимизатора, и у нас есть чем её проверить: дизассемблер под рукой с прошлого блока.

Таблицы книги становятся тестами

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

const std = @import("std");

/// Печатает таблицу всех значений w-битного типа: биты, беззнаковое, знаковое.
fn printTable(out: *std.Io.Writer, comptime w: u16) !void {
    const U = @Int(.unsigned, w);
    const I = @Int(.signed, w);
    try out.print("биты   u{d}  i{d}\n", .{ w, w });
    var raw: U = 0;
    while (true) : (raw += 1) {
        const signed: I = @bitCast(raw);
        try out.print("{b:0>4}  {d:>3} {d:>4}\n", .{ raw, raw, signed });
        if (raw == std.math.maxInt(U)) break;
    }
}

pub fn main(init: std.process.Init) !void {
    var buf: [1024]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    try printTable(&w.interface, 4);
    try w.interface.flush();
}

биты   u4  i4
0000    0   +0
0001    1   +1
0010    2   +2
0011    3   +3
0100    4   +4
0101    5   +5
0110    6   +6
0111    7   +7
1000    8   -8
1001    9   -7
1010   10   -6
1011   11   -5
1100   12   -4
1101   13   -3
1110   14   -2
1111   15   -1

Это буквально таблица 2.14 из книги, только не набранная в вёрстке, а посчитанная компилятором. @Int(.unsigned, w) строит тип из описания, поэтому одна функция печатает таблицу любой ширины: поставь printTable(out, 3) и получишь восемь строк, поставь 5 и получишь тридцать две. Старого @Type в Zig 0.16 больше нет, вместо него отдельные @Int и @Enum, про них было в прошлом уроке.

Обрати внимание на скачок между строками 0111 и 1000. Беззнаковое прочтение продолжает расти на единицу, знаковое падает с +7 на -8. Ровно эти шестнадцать значений в кольце, ровно в этом месте разрыв: всё, что книга называет переполнением, живёт в этой точке.

Перебор вместо доверия

Раз тип узкий, все пары значений можно перебрать целиком. Для u4 это 256 пар, для i5 уже 1024, и обе таблицы проверяются за миллисекунды.

const std = @import("std");

/// Полный перебор всех пар значений узкого типа. Для u4 это 256 пар,
/// для i5 уже 1024, и обе таблицы книги проверяются целиком, а не выборочно.
fn forEachPair(comptime T: type, body: fn (T, T) anyerror!void) !void {
    const min = std.math.minInt(T);
    const max = std.math.maxInt(T);
    var x: T = min;
    while (true) : (x += 1) {
        var y: T = min;
        while (true) : (y += 1) {
            try body(x, y);
            if (y == max) break;
        }
        if (x == max) break;
    }
}

test "u4: сложение это сложение по модулю шестнадцать" {
    try forEachPair(u4, struct {
        fn check(x: u4, y: u4) !void {
            const wide = @as(u32, x) + @as(u32, y);
            try std.testing.expectEqual(@as(u4, @truncate(wide)), x +% y);
        }
    }.check);
}

test "i5: переполнение видно по знакам" {
    try forEachPair(i5, struct {
        fn check(x: i5, y: i5) !void {
            const exact = @as(i32, x) + @as(i32, y);
            const fits = exact >= std.math.minInt(i5) and exact <= std.math.maxInt(i5);
            // Правило книги: переполнение это одинаковый знак у слагаемых
            // и другой знак у результата.
            const sum = x +% y;
            const same_sign = (x < 0) == (y < 0);
            const flipped = (sum < 0) != (x < 0);
            try std.testing.expectEqual(!fits, same_sign and flipped);
            // И то же самое одним встроенным вызовом.
            const pair = @addWithOverflow(x, y);
            try std.testing.expectEqual(@as(u1, if (fits) 0 else 1), pair[1]);
            try std.testing.expectEqual(sum, pair[0]);
        }
    }.check);
}

1/2 exhaustive.test.u4: сложение это сложение по модулю шестнадцать...OK
2/2 exhaustive.test.i5: переполнение видно по знакам...OK
All 2 tests passed.

Первый тест это утверждение книги про беззнаковое сложение: результат равен точной сумме, у которой отрезали всё выше w битов. Именно поэтому @truncate от широкой суммы совпадает с +% в узком типе, а не примерно совпадает.

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

Приём с анонимной структурой (struct { fn check(...) ... }.check) нужен, потому что в Zig нет замыканий: функцию-параметр негде взять, кроме как объявить рядом. Для теста это удобнее, чем разносить проверку и перебор по файлу.

Ещё несколько строк, которые стоит выписать отдельно.

const std = @import("std");
const expectEqual = std.testing.expectEqual;

test "u4: арифметика по модулю шестнадцать" {
    // Книга пишет сложение беззнаковых как (x + y) mod 2^w. При w = 4 это mod 16.
    const x: u4 = 9;
    const y: u4 = 12;
    try expectEqual(@as(u4, 5), x +% y); // 21 mod 16
    try expectEqual(@as(u4, 15), std.math.maxInt(u4));
    try expectEqual(@as(u4, 13), x -% y); // -3 mod 16
    try expectEqual(@as(u4, 12), x *% y); // 108 mod 16
}

test "i5: границы дополнительного кода" {
    try expectEqual(@as(i5, -16), std.math.minInt(i5));
    try expectEqual(@as(i5, 15), std.math.maxInt(i5));
    // Отрицание минимального числа не меняет его: классика главы 2.
    const min: i5 = -16;
    try expectEqual(min, -%min);
    // Переполнение вверх заворачивает в отрицательные.
    const big: i5 = 15;
    try expectEqual(@as(i5, -16), big +% 1);
}

Строка -%min == min это то самое свойство, из-за которого в C функция abs не является полной: у минимального числа нет положительного двойника, потому что отрицательных значений в дополнительном коде на одно больше. В i5 это видно голыми глазами: диапазон от -16 до 15, и шестнадцати с плюсом просто нет. В i32 тот же самый эффект, только границы длиннее.

Четвёртое преобразование: @bitCast

В уроке про значения было три преобразования: @as расширяет, @intCast сужает с проверкой, @truncate отрезает старшие биты. Четвёртое не меняет ни ширину, ни биты. Оно меняет только то, как эти биты читают.

const std = @import("std");
const expectEqual = std.testing.expectEqual;

test "@bitCast: те же биты, другой тип" {
    // Формула книги: значение со знаком равно беззнаковому минус 2^w,
    // если старший бит поднят. Проверяем её на всех шестнадцати значениях u4.
    var raw: u4 = 0;
    while (true) : (raw += 1) {
        const signed: i4 = @bitCast(raw);
        const expected: i32 = if (raw < 8) raw else @as(i32, raw) - 16;
        try expectEqual(expected, @as(i32, signed));
        if (raw == 15) break;
    }
}

test "@bitCast не меняет ширину, @intCast и @truncate меняют" {
    const byte: u8 = 0b1111_0000;
    try expectEqual(@as(i8, -16), @as(i8, @bitCast(byte))); // ширина та же, читаем иначе
    try expectEqual(@as(u4, 0), @as(u4, @truncate(byte))); // младшие четыре бита
    try expectEqual(@as(u16, 240), @as(u16, byte)); // расширение нулями
}

Первый тест это функции T2U и U2T из книги, только записанные не формулой, а перебором. Второй показывает три разных ответа на один и тот же байт 1111 0000: как i8 это -16, младшие четыре бита это ноль, расширение до u16 это 240. Ни один из трёх не «правильнее» остальных, они отвечают на разные вопросы.

Таблица, которую стоит держать в голове:

Что пишешь	Ширина	Биты	Что обещаешь компилятору
`@as(T, x)`	растёт	добавляются нули или копии знака	ничего, значение точно влезает
`@intCast(x)`	падает	старшие отрезаются	значение влезает, проверь меня в Debug
`@truncate(x)`	падает	старшие отрезаются	старшие биты не нужны, проверять нечего
`@bitCast(x)`	та же	не меняются вообще	я хочу прочитать эти биты как другой тип

Требование про ширину у @bitCast жёсткое, и нарушить его молча нельзя:

const x: u32 = 1;
const y: u16 = @bitCast(x);

bcerr.zig:4:20: error: @bitCast size mismatch: destination type 'u16' has 16 bits but source type 'u32' has 32 bits
    const y: u16 = @bitCast(x);
                   ^~~~~~~~~~~

Это и есть главное отличие от C, где (short)x и *(short*)&x пишутся почти одинаково, а значат разное. В Zig смена ширины и смена прочтения это две разные операции с двумя разными именами, и перепутать их не выйдет.

@bitCast пригодится буквально в каждой битовой головоломке дальше: маску удобно считать в беззнаковом типе, а сравнивать со знаковым исходником. В следующем уроке он же соединит u32 и f32, и станет понятно, что и число с плавающей точкой это просто биты.

Порядок байтов

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

Посмотреть на неё можно прямо, без всяких библиотек: взять срез поверх самого числа.

const std = @import("std");
const native_endian = @import("builtin").cpu.arch.endian();
const expectEqualSlices = std.testing.expectEqualSlices;

test "число и его байты" {
    const x: u32 = 0x1234_5678;
    // asBytes отдаёт срез поверх самого значения: копии нет, адрес тот же.
    const bytes = std.mem.asBytes(&x);
    switch (native_endian) {
        .little => try expectEqualSlices(u8, &.{ 0x78, 0x56, 0x34, 0x12 }, bytes),
        .big => try expectEqualSlices(u8, &.{ 0x12, 0x34, 0x56, 0x78 }, bytes),
    }
}

test "порядок байтов можно спросить у самой памяти" {
    const probe: u32 = 1;
    const first: *const u8 = @ptrCast(&probe);
    try std.testing.expectEqual(native_endian == .little, first.* == 1);
}

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

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

Читать числа из байтов правильно

Соблазн прочитать четыре байта как u32 через @ptrCast велик, но он неверен по двум причинам сразу. Во-первых, он даёт порядок байтов машины, а данные в файле или в пакете имеют свой, заранее оговорённый. Во-вторых, у указателя на u32 есть требование по выравниванию, и произвольный байт в середине буфера ему не удовлетворяет.

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

const std = @import("std");
const expectEqual = std.testing.expectEqual;
const expectEqualSlices = std.testing.expectEqualSlices;

test "одни и те же байты, два числа" {
    const bytes = [4]u8{ 0x7f, 0x45, 0x4c, 0x46 }; // начало любого ELF
    try expectEqual(@as(u32, 0x464c_457f), std.mem.readInt(u32, &bytes, .little));
    try expectEqual(@as(u32, 0x7f45_4c46), std.mem.readInt(u32, &bytes, .big));
}

test "writeInt раскладывает число обратно" {
    var buf: [4]u8 = undefined;
    std.mem.writeInt(u32, &buf, 0x1234_5678, .little);
    try expectEqualSlices(u8, &.{ 0x78, 0x56, 0x34, 0x12 }, &buf);
    std.mem.writeInt(u32, &buf, 0x1234_5678, .big);
    try expectEqualSlices(u8, &.{ 0x12, 0x34, 0x56, 0x78 }, &buf);
}

test "@byteSwap это перестановка байтов внутри числа" {
    try expectEqual(@as(u32, 0x7856_3412), @byteSwap(@as(u32, 0x1234_5678)));
    try expectEqual(@as(u16, 0x3412), @byteSwap(@as(u16, 0x1234)));
    // Двойная перестановка возвращает исходное число.
    const x: u64 = 0x0123_4567_89ab_cdef;
    try expectEqual(x, @byteSwap(@byteSwap(x)));
}

Три вещи, ради которых этот кусок стоит запомнить.

std.mem.readInt(T, ptr, endian) берёт указатель на массив ровно нужной длины, поэтому длину проверяет компилятор, а не рантайм: передать сюда срез из трёх байтов не выйдет. Порядок передаётся явно и всегда: параметра по умолчанию у него нет, и это осознанное решение языка. Всякий раз, когда ты читаешь число из чужих байтов, ты обязан сказать, чьи это байты.

std.mem.writeInt делает обратное и с той же строгостью. Вместе они закрывают весь разбор двоичных форматов: заголовок ELF, запись в файле, поле сетевого протокола.

@byteSwap это отдельная инструкция процессора (bswap на x86-64), а не цикл. Она нужна там, где число уже прочитано, а порядок оказался не тот. Пара readInt и writeInt в большинстве случаев удобнее, потому что не надо помнить, сделал ты уже перестановку или нет.

Ещё в стандартной библиотеке есть std.mem.nativeToBig, std.mem.bigToNative и их младшие родственники: те же перестановки, названные по направлению. Внутри они разворачиваются либо в @byteSwap, либо в ничто, в зависимости от целевой архитектуры.

У сдвига есть тип

Про счётчик сдвига в уроке 02 была одна строчка. Здесь она разворачивается в правило, из которого потом растёт половина головоломок.

Сдвинуть значение шириной w бит можно на 0, 1 и так далее до w - 1 позиций. Значит счётчику хватает ровно log2(w) бит, и Zig делает из этого тип.

const std = @import("std");
const expectEqual = std.testing.expectEqual;

test "тип счётчика сдвига считается из ширины" {
    try expectEqual(u3, std.math.Log2Int(u8));
    try expectEqual(u5, std.math.Log2Int(u32));
    try expectEqual(u6, std.math.Log2Int(i64));
    try expectEqual(u7, std.math.Log2Int(u128));
}

test "правый сдвиг знакового числа тянет знак" {
    const negative: i32 = -16;
    try expectEqual(@as(i32, -4), negative >> 2); // арифметический сдвиг
    const raw: u32 = @bitCast(negative);
    try expectEqual(@as(u32, 0x3fff_fffc), raw >> 2); // логический сдвиг
}

test "std.math.shl не паникует на слишком большом счётчике" {
    const x: u32 = 1;
    try expectEqual(@as(u32, 0), std.math.shl(u32, x, @as(u32, 32)));
    try expectEqual(@as(u32, 0x8000_0000), std.math.shl(u32, x, @as(u32, 31)));
}

Второй тест снимает вопрос, который в C решается сноской в стандарте: какой сдвиг вправо делает >>. В Zig ответ читается из типа. Знаковое значит арифметический, старший бит копируется; беззнаковое значит логический, сверху приезжают нули. Одно и то же битовое поле, прочитанное как i32 и как u32, даёт разные результаты, и @bitCast в середине теста показывает, что биты при этом были одни и те же.

Сдвиг ровно на ширину

Из того, что счётчик это u5, следует главное: сдвинуть u32 на 32 позиции нельзя. Ни во что не превращается, а просто не компилируется.

const x: u32 = 1;
std.debug.print("{d}\n", .{x << 32});

shifterr2.zig:5:37: error: type 'u5' cannot represent integer value '32'
    std.debug.print("{d}\n", .{x << 32});
                                    ^~

Если счётчик приезжает из переменной подходящего размера, ошибка приходит из системы типов:

const x: u32 = 1;
var by: u8 = 40;
_ = &by;
std.debug.print("{d}\n", .{x << by});

shifterr3.zig:6:37: error: expected type 'u5', found 'u8'
    std.debug.print("{d}\n", .{x << by});
                                    ^~
shifterr3.zig:6:37: note: unsigned 5-bit int cannot represent all possible unsigned 8-bit values

А если ты обещал компилятору, что счётчик влезет, и ошибся, обещание проверяется в рантайме:

fn shiftBy(x: u32, n: u32) u32 {
    return x << @intCast(n);
}

$ ./shiftpanic 31
1 << 31 = 2147483648
$ ./shiftpanic 32
thread 8272457 panic: integer does not fit in destination type
shiftpanic.zig:4:17: 0x1045128fb in shiftBy (shiftpanic)
    return x << @intCast(n);
                ^

Сравни с C, где x << 32 для 32-битного x это неопределённое поведение: на x86-64 процессор возьмёт счётчик по модулю 32 и вернёт x, на ARM вернёт ноль, а оптимизатор имеет право предположить, что такого не бывает, и выбросить проверку рядом. В Zig этот случай переехал из рантайма в компилятор, а там, где значение приходит извне, в честную панику.

Отсюда растёт ловушка, на которой спотыкается почти каждый в задаче про циклический сдвиг. Правая половина поворота на n позиций это x >> (32 - n), и при n равном нулю там оказывается 32, которого не существует. Решение простое: разбить один сдвиг на два.

pub fn rotateLeft(x: u32, n: u5) u32 {
    // Два сдвига вместо одного на 32 - n: при n = 0 правая часть даёт ноль,
    // а сдвига ровно на ширину типа в Zig не существует.
    return (x << n) | ((x >> 1) >> (31 - n));
}

Проверь на бумаге оба края. При n = 0: x << 0 это x, а (x >> 1) >> 31 это ноль, потому что от тридцати двух бит после тридцати двух сдвигов ничего не остаётся. При n = 31: x << 31 оставляет младший бит на самом верху, а (x >> 1) >> 0 даёт старшие тридцать один бит, сдвинутые вниз. Обе половины на месте.

Для повседневного кода в стандартной библиотеке есть std.math.rotl и std.math.rotr, а также std.math.shl и std.math.shr, которые принимают счётчик любого типа и честно возвращают ноль при слишком большом. В головоломках их звать нельзя: смысл упражнения именно в том, чтобы собрать поведение из примитивов.

Судоку на девяти битах

Один пример, который собирает сдвиг, его счётчик и unreachable в работающую вещь. Идея взята из заметки Нило Столте о Zig (ссылка в ресурсах урока) и упрощена до того, что нужно уроку. Сетка судоку это девять строк по девять клеток, в клетке цифра от 1 до 9 или пустота. Правило одно: цифра не повторяется в своей строке, своём столбце и своём квадрате 3 на 3. Вопрос «есть ли уже семёрка в этой строке» хочется задавать за одну операцию, а не перебором девяти клеток.

Ключ такой: цифру d представляет не число d, а единичный бит в позиции d - 1. Тогда строка целиком это девять бит, по одному на цифру, и тип для неё уже есть в языке: u9. Проверка «цифра уже стоит» это одно побитовое и, добавление цифры это одно побитовое или.

Цифра	Позиция бита	`code`
1	0	`0b0_0000_0001`
2	1	`0b0_0000_0010`
3	2	`0b0_0000_0100`
9	8	`0b1_0000_0000`
пустая клетка	нет	`0b0_0000_0000`

Сама сетка хранится плоско, 81 байт строка за строкой, а рядом с ней три массива по девять масок: строки, столбцы и квадраты.

const std = @import("std");

var grid = [_]u8{0} ** 81; // 9x9, строка за строкой
var lines = [_]u9{0} ** 9; // бит k поднят, если цифра k + 1 уже есть в строке
var columns = [_]u9{0} ** 9;
var cells = [_]u9{0} ** 9; // девять квадратов 3x3, тоже строка за строкой

// Номер квадрата по номеру строки или столбца: таблица вместо i / 3.
const cindx = [_]usize{ 0, 0, 0, 1, 1, 1, 2, 2, 2 };

/// Заполняет сетку из строки 81 символа: цифры, а '0' или '.' это пустая клетка.
/// Повтор цифры в строке, столбце или квадрате это ошибка входа, и она недостижима.
fn set(s: *const [81]u8) void {
    for (0..9) |i| {
        for (0..9) |j| {
            const ch = s[i * 9 + j];
            const c: u4 = if (ch == '.') 0 else @intCast(ch - '0');
            if (c != 0) {
                const code = @as(u9, 1) << (c - 1);
                const cell = cindx[i] * 3 + cindx[j];
                if ((lines[i] | columns[j] | cells[cell]) & code != 0) unreachable;
                lines[i] |= code;
                columns[j] |= code;
                cells[cell] |= code;
            }
            grid[i * 9 + j] = c;
        }
    }
}

test "правильная сетка раскладывается по маскам" {
    set("800000000003600000070090200" ++
        "050007000000045700000100030" ++
        "001000068008500010090000400");
    try std.testing.expectEqual(@as(u8, 8), grid[0]);
    try std.testing.expectEqual(@as(u9, 1 << 7), lines[0]); // в первой строке только восьмёрка
    try std.testing.expectEqual(@as(u9, 1 << 2 | 1 << 5), lines[1]); // тройка и шестёрка
    try std.testing.expectEqual(@as(u9, 1 << 6 | 1 << 4 | 1 << 8), columns[1]); // 7, 5, 9
    try std.testing.expectEqual(@as(u4, 3), @popCount(cells[0])); // 8, 3, 7
}

Три места в этом листинге стоят разбора.

Сдвиг проверяет диапазон сам. Строка @as(u9, 1) << (c - 1) компилируется без единого приведения, хотя c объявлена как u4: счётчик сдвига для u9 это std.math.Log2Int(u9), то есть тот же u4. Но в u4 помещаются значения до 15, а сдвинуть девять бит можно самое большее на восемь. Разрыв между «влезает в тип» и «имеет смысл» проверяется в рантайме. Поменяй в тестовой строке любой ноль на двоеточие, символ, который в ASCII идёт сразу за девяткой:

$ zig test sudoku.zig
1/1 sudoku.test.правильная сетка раскладывается по маскам...thread 54769048 panic: shift amount is greater than the type size
sudoku.zig:19:41: 0x100ae2063 in set (test)
                const code = @as(u9, 1) << (c - 1);
                                        ^

А если поставить косую черту, символ перед нулём, паника случится ещё раньше: ch - '0' для u8 уходит ниже нуля, и это integer overflow из урока 02. В set нет ни одной строчки, которая проверяла бы, что цифра лежит от 1 до 9, и тем не менее в Debug любой посторонний символ останавливает программу с точным адресом. Проверки дала система типов.

unreachable это утверждение. Повтор цифры ловится одной строкой: маски строки, столбца и квадрата складываются побитовым или, и если в результате бит code уже поднят, выполнение доходит до unreachable. В Debug и ReleaseSafe это паника reached unreachable code со стеком; поставь в тестовой строке две пятёрки рядом и увидишь её. Но помни таблицу режимов из первого урока: в ReleaseFast unreachable это обещание оптимизатору, что ветка не наступает, и он вправе выбросить и проверку, и всё, что из неё следует. Поэтому unreachable годится для инвариантов собственного кода, а для строки, которую напечатал пользователь, честнее вернуть error.Duplicate, как в уроке 05. Здесь вход это константа в тесте, и утверждение на месте.

Номер квадрата считается таблицей. Клетка в строке i лежит в квадрате номер i / 3, и в заметке деление заменено таблицей cindx, потому что «деление медленное». Это правда для деления двух переменных: инструкция div стоит десятки тактов, и в уроке 11 ты увидишь, сколько именно. Для деления на константу это неправда: компилятор сам не делит. Соберём обе версии и посмотрим.

const cindx = [_]u8{ 0, 0, 0, 1, 1, 1, 2, 2, 2 };

export fn byDivision(i: u8) u8 {
    return i / 3;
}

export fn byTable(i: u8) u8 {
    return cindx[i];
}

zig build-obj div3.zig -O ReleaseFast -fomit-frame-pointer -target x86_64-linux -femit-bin=div3.o
objdump -dr --no-show-raw-insn div3.o

0000000000000000 <div3.byTable>:
       0:      	movl	%edi, %eax
       2:      	movzbl	(%rax), %eax
		0000000000000005:  R_X86_64_32S	.rodata
       9:      	retq

0000000000000010 <div3.byDivision>:
      10:      	imull	$0xab, %edi, %eax
      16:      	shrl	$0x9, %eax
      19:      	retq

Деления нет. byDivision умножает на 0xab, то есть на 171, и отбрасывает девять младших бит, то есть делит на 512. Дробь 171/512 это 0,3339…, чуть больше трети, и запаса хватает, чтобы для всех 256 значений u8 результат совпал с целочисленным делением на 3. Не верь на слово, проверь так же, как таблицы в начале урока:

const std = @import("std");

test "умножить на 171 и сдвинуть на 9 это поделить на 3 для любого u8" {
    for (0..256) |i| {
        try std.testing.expectEqual(i / 3, (i * 171) >> 9);
    }
}

У byTable тоже две инструкции, но вторая читает память: R_X86_64_32S .rodata это релокация на адрес таблицы, к которой мы вернёмся в уроке 44. Умножение это три такта и ни одного обращения к памяти, чтение из таблицы это обращение к памяти, пусть и из кеша, а в ReleaseFast у cindx[i] нет проверки границ, и byTable(10) вернёт байт, который лежит за таблицей. Таблица не выиграла ничего и потеряла проверку. Отсюда правило, которое пригодится не раз: прежде чем оптимизировать арифметику с константой руками, посмотри листинг. Компилятор знает приём с обратной дробью для любого делителя, и в упражнении ты найдёшь его множитель для девятки.

Блок с меткой возвращает значение

Ещё один приём из той же заметки. В set индекс клетки считается как i * 9 + j, а автору хотелось писать matrix[i][j]. Массив из девяти указателей на начала строк можно собрать циклом, но const на уровне модуля требует инициализатора, а не цикла. Разрыв закрывает блок с меткой: у блока есть имя, и break с этим именем и значением делает всё выражение равным этому значению.

const std = @import("std");
var grid = [_]u8{0} ** 81;
const matrix = fill9x9: {
    var m: [9][*]u8 = undefined;
    var pt: [*]u8 = &grid;
    for (0..9) |i| {
        m[i] = pt;
        pt += 9;
    }
    break :fill9x9 m;
};
test "matrix[i][j] это grid[i * 9 + j]" {
    grid[4 * 9 + 7] = 42;
    try std.testing.expectEqual(@as(u8, 42), matrix[4][7]);
    matrix[8][8] = 7;
    try std.testing.expectEqual(@as(u8, 7), grid[80]);
}

matrix объявлена как const на уровне модуля, поэтому весь блок fill9x9 выполняется во время компиляции: адрес глобальной grid известен ещё до линковки, и девять указателей ложатся в секцию данных готовыми. То же самое ты видел в уроке 06, где break :blk table собирал таблицу для comptime. Указатель pt типа [*]u8 из урока 03 здесь на месте: строки идут через каждые девять байт, и это ровно арифметика адресов без длины. Заметь, что matrix[i][j] через такой указатель не проверяет границы, а grid[i * 9 + j] проверяет: два способа дать один и тот же байт, и второй безопаснее.

Умножение на константу глазами компилятора

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

Возьмём 60. В двоичной записи это 111100, то есть биты 5, 4, 3 и 2.

const std = @import("std");
const expectEqual = std.testing.expectEqual;

/// Форма A книги: по сдвигу на каждый единичный бит, всё складывается.
/// 60 это 0b111100, то есть биты 5, 4, 3 и 2.
fn mul60FormA(x: i32) i32 {
    return (x << 5) +% (x << 4) +% (x << 3) +% (x << 2);
}

/// Форма B: серия единиц с бита 5 по бит 2 это разность двух сдвигов.
fn mul60FormB(x: i32) i32 {
    return (x << 6) -% (x << 2);
}

test "обе формы дают одно и то же умножение" {
    const samples = [_]i32{ 0, 1, -1, 7, -7, 1000, -1000, 35_791_394, -35_791_394 };
    for (samples) |x| {
        try expectEqual(x *% 60, mul60FormA(x));
        try expectEqual(x *% 60, mul60FormB(x));
    }
}

test "переполнение обеим формам не мешает" {
    // Дополнительный код одинаково складывает знаковые и беззнаковые,
    // поэтому обрезанный результат совпадает даже там, где произведение не влезло.
    const x: i32 = std.math.maxInt(i32);
    try expectEqual(x *% 60, mul60FormA(x));
    try expectEqual(x *% 60, mul60FormB(x));
}

Форма A прямолинейна: каждая единица в двоичной записи это одно слагаемое. Форма B пользуется тем, что подряд идущие единицы с бита high по бит low это разность 2^(high+1) минус 2^low. Для 60 форма A стоит семи операций (четыре сдвига и три сложения), форма B трёх (два сдвига и вычитание).

Второй тест стоит прочитать внимательно. Он утверждает, что раскладка совпадает с умножением даже там, где произведение не помещается в i32. Это прямое следствие дополнительного кода: сложение, вычитание и умножение в младших w битах не зависят от того, знаковые операнды или нет. Именно поэтому компилятор имеет право менять умножение на сдвиги, не спрашивая про диапазон.

Конструктор

Виджет ниже собирает раскладку для любой константы. Кнопки сверху это заготовленные значения, рядом поле для своей K от -4096 до 4096. Строка битов показывает двоичную запись модуля, серии подряд идущих единиц подсвечены ярче: именно они дают выигрыш форме B. Обе формы книги посчитаны рядом со стоимостью в операциях, дешёвая отмечена рамкой.

Ниже кнопки-фишки: клик по + добавляет слагаемое со сдвигом, клик по - вычитает, повторный клик убирает. Собери своё выражение и посмотри вердикт: совпало ли оно с нужной константой и вышло ли дешевле формы книги. Ползунок проверки подставляет конкретный x и считает оба ответа. В самом низу лежит настоящий вывод компилятора для этой константы, снятый с zig build-obj -O ReleaseFast -target x86_64-linux и разобранный objdump.

Покрути пресеты и обрати внимание на три вещи.

Инструкция lea считает больше, чем кажется. Для тройки компилятор выдаёт одну строку leal (%rdi,%rdi,2), %eax. Это адресная арифметика, использованная как калькулятор: база плюс индекс, умноженный на масштаб. Масштаб бывает 1, 2, 4 и 8, поэтому за одну инструкцию lea умножает на 2, 3, 5 и 9. Разберём её подробно в уроке 11, а пока достаточно видеть, что дешёвых констант больше, чем степеней двойки.

Формы книги это нижняя граница, а не рецепт. Для 15 компилятор выдал цепочку из двух lea: сначала 5x, потом это же на 3. Ни форма A, ни форма B такого не предлагают, потому что книга раскладывает константу в сумму, а компилятор ищет её разложение на множители.

Иногда выгоднее просто умножить. Для 55, 60 и 100 в листинге стоит одна imull с константой прямо в инструкции. На современном процессоре целочисленное умножение занимает три такта и полностью конвейеризовано, а цепочка из трёх зависимых сложений это три такта плюс давление на планировщик. Правило «сдвиг всегда дешевле» устарело примерно тогда же, когда процессоры научились исполнять несколько инструкций за такт.

Проверить руками

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

export fn mul7(x: i32) i32 {
    return x *% 7;
}

export fn shiftForm7(x: i32) i32 {
    return (x << 3) -% x;
}

zig build-obj mulk.zig -O ReleaseFast -target x86_64-linux -femit-bin=mulk.o
objdump -d mulk.o

0000000000000010 <shiftForm7>:
      10: 55                           	pushq	%rbp
      11: 48 89 e5                     	movq	%rsp, %rbp
      14: 8d 04 fd 00 00 00 00         	leal	(,%rdi,8), %eax
      1b: 29 f8                        	subl	%edi, %eax
      1d: 5d                           	popq	%rbp
      1e: c3                           	retq

Функции mul7 в листинге нет, и это не ошибка дизассемблера. Загляни в таблицу символов:

objdump -t mulk.o | grep 'F .text'

0000000000000000 l     F .text	0000000000000009 mulk.mul60
0000000000000010 l     F .text	000000000000000f mulk.mul7
0000000000000010 g     F .text	000000000000000f shiftForm7
0000000000000000 g     F .text	0000000000000009 mul60
0000000000000010 g     F .text	000000000000000f mul7

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

Деление на степень двойки

С делением история несимметричная, и это самое частое место, где интуиция про сдвиги врёт.

Для беззнаковых всё просто: x / 8 это x >> 3, потому что логический сдвиг отбрасывает младшие биты и приводит к остатку, а беззнаковое деление и есть отбрасывание дробной части вниз. Для знаковых сдвиг вправо тоже округляет вниз, а деление в языках семейства C округляет к нулю. Для положительных чисел это одно и то же, для отрицательных нет.

const std = @import("std");
const expectEqual = std.testing.expectEqual;

/// То же, что @divTrunc(x, 1 << k), но написанное руками: отрицательному
/// числу перед сдвигом добавляется 2^k - 1, положительному ноль.
fn dividePower2(x: i32, k: u5) i32 {
    const bias = (x >> 31) & ((@as(i32, 1) << k) -% 1);
    return (x +% bias) >> k;
}

test "сдвиг вправо это деление вниз, а не к нулю" {
    try expectEqual(@as(i32, -3), @as(i32, -17) >> 3); // -17/8 вниз это -3
    try expectEqual(@as(i32, -2), @divTrunc(@as(i32, -17), 8)); // к нулю это -2
    try expectEqual(@as(i32, -3), @divFloor(@as(i32, -17), 8));
}

test "поправка совпадает с @divTrunc на всех интересных случаях" {
    const samples = [_]i32{
        0,    1,     7,     8,     9,
        1000, -1,    -7,    -8,    -9,
        -1000,
    };
    for (samples) |x| {
        for (0..5) |k| {
            const shift: u5 = @intCast(k);
            try expectEqual(@divTrunc(x, @as(i32, 1) << shift), dividePower2(x, shift));
        }
    }
}

Приём с поправкой из книги устроен так. Выражение x >> 31 для i32 даёт либо все единицы (для отрицательного x), либо все нули. Конъюнкция с маской 2^k - 1 превращает это в саму маску или в ноль. Прибавили и сдвинули: отрицательное число подтолкнули вверх ровно настолько, чтобы округление вниз стало округлением к нулю, а положительное не тронули вовсе. Ветвления нет, а значит нет и предсказателя переходов, которому можно ошибиться.

Ровно это делает компилятор. Соберём три функции и посмотрим.

export fn divTrunc8(x: i32) i32 {
    return @divTrunc(x, 8);
}

export fn divFloor8(x: i32) i32 {
    return @divFloor(x, 8);
}

export fn shiftRight3(x: i32) i32 {
    return x >> 3;
}

zig build-obj divk.zig -O ReleaseFast -target x86_64-linux -femit-bin=divk.o
objdump -d divk.o

0000000000000010 <shiftRight3>:
      10: 55                           	pushq	%rbp
      11: 48 89 e5                     	movq	%rsp, %rbp
      14: 89 f8                        	movl	%edi, %eax
      16: c1 f8 03                     	sarl	$0x3, %eax
      19: 5d                           	popq	%rbp
      1a: c3                           	retq
      1b: 0f 1f 44 00 00               	nopl	(%rax,%rax)

0000000000000020 <divk.divTrunc8>:
      20: 55                           	pushq	%rbp
      21: 48 89 e5                     	movq	%rsp, %rbp
      24: 8d 47 07                     	leal	0x7(%rdi), %eax
      27: 85 ff                        	testl	%edi, %edi
      29: 0f 49 c7                     	cmovnsl	%edi, %eax
      2c: c1 f8 03                     	sarl	$0x3, %eax
      2f: 5d                           	popq	%rbp
      30: c3                           	retq

Читаем divTrunc8 построчно. leal 0x7(%rdi), %eax кладёт в eax значение x + 7, то есть x плюс маска 2^3 - 1. testl %edi, %edi выставляет флаги по знаку самого x, ничего не записывая. cmovnsl %edi, %eax возвращает в eax исходный x, если знак оказался неотрицательным: буквально «взять поправку только для отрицательных». sarl $0x3, %eax делит арифметическим сдвигом. Четыре инструкции, ни одного перехода, ни одной инструкции деления.

Компилятор выбрал cmov вместо маски, но идея та же самая, что и в dividePower2 выше: поправку получает только отрицательное число. Про cmov и цену ошибки предсказания поговорим отдельно в уроке 12.

А divFloor8 в листинге снова нет, и снова по той же причине:

0000000000000010 l     F .text	000000000000000b divk.divFloor8
0000000000000010 g     F .text	000000000000000b shiftRight3

@divFloor(x, 8) и x >> 3 это побайтно один и тот же код. Отсюда практический вывод, который стоит записать: если тебе нужно деление вниз, пиши @divFloor или сдвиг, они бесплатны. Если нужно деление к нулю, пиши @divTrunc и плати три лишние инструкции. Разница между ними существует только для отрицательных чисел, и именно поэтому её так легко не заметить в тестах на положительных данных.

Тот же кусок в листинге самого компилятора выглядит так (напомню, zig build-obj -femit-asm печатает Intel-синтаксис):

divk.divTrunc8:
	.cfi_startproc
	push	rbp
	mov	rbp, rsp
	lea	eax, [rdi + 7]
	test	edi, edi
	cmovns	eax, edi
	sar	eax, 3
	pop	rbp
	ret

Практика

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

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

Первая задача, пять функций про байты и биты. isLittleEndian отвечает, идут ли байты числа от младшего к старшему, и обязана узнать это у самой памяти, а не у @import("builtin"): ровно тот приём, который был выше в тесте с probe. replaceByte(x, index, byte) заменяет в числе байт с заданным номером. anyOddOne отвечает, есть ли единица хотя бы на одной нечётной позиции. leftmostOne оставляет от числа только самый старший единичный бит. rotateLeft крутит биты по кругу влево. Нельзя if, while, for, switch, orelse, нельзя звать готовые @popCount, @clz, @ctz, @byteSwap, std.math.rotl и std.math.rotr.

Две ловушки известны заранее. В leftmostOne не ищи бит перебором: размажь старшую единицу вправо серией x |= x >> 1, x |= x >> 2 и так далее, а потом вычти сдвинутую копию. В rotateLeft вспомни разбор про сдвиг ровно на ширину, он был десять минут назад.

Вторая задача жёстче, и она вся про знак. fitsBits(x, n) отвечает, помещается ли число в n разрядов дополнительного кода. saturatingAdd складывает с насыщением: вместо переполнения возвращает границу типа. tsubOk отвечает, не переполнится ли вычитание, и обязана правильно ответить, когда вычитаемое это минимальное число. dividePower2 делит на степень двойки с округлением к нулю, то есть повторяет ту самую поправку из предыдущего раздела. threeFourths считает три четверти так, чтобы ни одно промежуточное значение не переполнилось.

Ограничения здесь строже: дополнительно нельзя сравнивать через <, >, <= и >= (сдвиги при этом можно), нельзя звать @divTrunc, @divFloor, @abs, @min, @max, семейство @addWithOverflow, насыщающие операторы и вообще что-либо из std.math. Признак переполнения придётся собрать руками, как в тесте на i5 в начале урока.

И важная деталь именно про Zig: задача собирается в отладочном режиме, где обычные +, - и * паникуют при переполнении. В головоломках переполнение это рабочий инструмент, а не авария, поэтому бери оборачивающиеся +%, -% и *%.

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

В шестом уроке ты собрал скелет zt и подкоманду hexdump, которая печатает по шестнадцать байт в строке. Сегодняшний шаг маленький и очень наглядный: научить её группировать байты по 2, 4 или 8 и читать каждую группу как число выбранного порядка.

Зачем это нужно, видно на одном примере. Возьмём начало заголовка ELF, тридцать два байта.

$ zt hexdump elf-head.bin
00000000  7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00  |.ELF............|
00000010  01 00 3e 00 01 00 00 00 00 00 00 00 00 00 00 00  |..>.............|

$ zt hexdump --words=4 elf-head.bin
00000000  464c457f 00010102 00000000 00000000  |.ELF............|
00000010  003e0001 00000001 00000000 00000000  |..>.............|

$ zt hexdump --words=4 --big elf-head.bin
00000000  7f454c46 02010100 00000000 00000000  |.ELF............|
00000010  01003e00 01000000 00000000 00000000  |..>.............|

Одна и та же память, три прочтения. Побайтно видно 7f 45 4c 46, то есть знак ELF. При --words=4 те же четыре байта превратились в число 0x464c457f, потому что машина читает младший байт первым. При --big число стало 0x7f454c46, то есть цифры выстроились в том же порядке, что и байты. Разница между второй и третьей строкой это и есть порядок байтов, увиденный своими глазами, а не прочитанный в определении.

Все настройки едут в одной структуре:

/// Настройки дампа. Группировка по словам показывает то же самое место
/// памяти двумя способами, и разница между ними это и есть порядок байтов.
pub const Options = struct {
    /// Размер группы в байтах: 1, 2, 4 или 8.
    group: u8 = 1,
    /// Порядок байтов внутри группы. При `group == 1` не влияет ни на что.
    endian: std.builtin.Endian = .little,
    /// Адрес первого байта: с него начинается колонка смещений.
    base: u64 = 0,
};

/// Проверка значения для `--words`: читать словом можно только 1, 2, 4 или 8 байтов,
/// потому что других целых ширин у машины нет.
pub fn isValidGroup(group: u8) bool {
    return group == 1 or group == 2 or group == 4 or group == 8;
}

Ограничение на 1, 2, 4 и 8 не произвол. Группа это машинное слово, а слов другой ширины у процессора нет, и std.mem.readInt тоже принимает только настоящие целые типы. Проверка живёт рядом с дампом, а не в разборе командной строки, потому что это свойство формата, а не флага.

Вся новая работа сосредоточена в одной функции:

/// Одна группа: полная читается как целое число выбранного порядка байтов,
/// неполный хвост печатается побайтно, потому что числа там ещё нет.
fn printGroup(out: *std.Io.Writer, group: []const u8, options: Options) !void {
    if (group.len < options.group) {
        try out.writeByte(' ');
        for (group) |byte| try out.print("{x:0>2}", .{byte});
        try out.splatByteAll(' ', 2 * (@as(usize, options.group) - group.len));
        return;
    }

    switch (options.group) {
        1 => try out.print(" {x:0>2}", .{group[0]}),
        2 => try out.print(" {x:0>4}", .{std.mem.readInt(u16, group[0..2], options.endian)}),
        4 => try out.print(" {x:0>8}", .{std.mem.readInt(u32, group[0..4], options.endian)}),
        8 => try out.print(" {x:0>16}", .{std.mem.readInt(u64, group[0..8], options.endian)}),
        else => unreachable,
    }
}

Здесь стоит заметить две вещи.

Ветка group.len < options.group это хвост файла, которого не хватило на полную группу. Числа там нет, собирать его из имеющихся байтов было бы враньём, поэтому печатаем побайтно и добиваем пробелами, чтобы колонка с текстом не съехала. Настоящие hexdump и xxd ведут себя так же.

Выражение group[0..4] даёт указатель на массив ровно из четырёх байтов, а не срез, и именно этого ждёт readInt. Длину проверил компилятор в момент, когда ты написал границы среза, поэтому в рантайме проверять уже нечего.

Разбор флагов в main прямолинейный:

for (args) |arg| {
    if (std.mem.startsWith(u8, arg, "--words=")) {
        const text = arg["--words=".len..];
        const group = std.fmt.parseInt(u8, text, 10) catch
            return fail(out, "zt hexdump: --words ждёт число 1, 2, 4 или 8\n");
        if (!zt.hexdump.isValidGroup(group))
            return fail(out, "zt hexdump: --words ждёт число 1, 2, 4 или 8\n");
        options.group = group;
    } else if (std.mem.eql(u8, arg, "--big")) {
        options.endian = .big;
    } else if (std.mem.startsWith(u8, arg, "-")) {
        try out.print("zt hexdump: неизвестный флаг {s}\n", .{arg});
        return error.BadUsage;
    } else {
        if (path != null) return fail(out, "zt hexdump: нужен ровно один файл\n");
        path = arg;
    }
}

Тесты шага проверяют ровно то утверждение, ради которого шаг и делался:

/// Заголовок ELF начинается ровно с этих байтов, поэтому дамп узнаётся глазами.
const elf_magic = "\x7fELF\x02\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00";

test "группы по четыре в little endian переворачивают цифры" {
    const text = try render(elf_magic, .{ .group = 4 });
    defer std.testing.allocator.free(text);

    try std.testing.expectEqualStrings(
        "00000000  464c457f 00010102 00000000 00000000  |.ELF............|\n",
        text,
    );
}

test "группа по одному байту не зависит от порядка байтов" {
    const little = try render(elf_magic, .{ .group = 1 });
    defer std.testing.allocator.free(little);
    const big = try render(elf_magic, .{ .group = 1, .endian = .big });
    defer std.testing.allocator.free(big);

    try std.testing.expectEqualStrings(little, big);
}

test "неполный хвост печатается побайтно и не ломает колонку ASCII" {
    const text = try render("zt hexdump!", .{ .group = 4 });
    defer std.testing.allocator.free(text);

    // Восемь байтов сложились в две группы, оставшиеся три показаны как байты.
    try std.testing.expectEqualStrings(
        "00000000  6820747a 75647865 6d7021             |zt hexdump!|\n",
        text,
    );
}

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

Прогон:

zig build test -Dstep=7
zig build run -- hexdump --words=4 --big fixtures/step_09.o

Упражнения

CHK-1★

Выведи таблицу из первого раздела для w = 3 и w = 5, поменяв одно число в вызове. Для i5 найди в ней строку, где беззнаковое прочтение равно 16, и объясни, почему знаковое там равно -16, а не -15.

CHK-2★

Напиши тест, который перебирает все значения u8 и проверяет, что @bitCast в i8 совпадает с формулой книги. Затем поменяй в тесте @bitCast на @intCast и выпиши, на каком значении и с каким сообщением он упадёт.

CHK-3★★

Возьми четыре байта de ad be ef и посчитай на бумаге, какое число даст readInt с каждым из двух порядков. Проверь тестом. Потом напиши writeInt обратно тем же порядком и убедись, что байты вернулись; а затем не тем же, и объясни результат.

CHK-4★★

Собери x *% 23 в ReleaseFast под x86_64-linux и сними дизассемблер. Разложи 23 обеими формами книги в виджете урока, посчитай операции и сравни с тем, что выбрал компилятор. Затем найди константу в диапазоне от 2 до 100, для которой компилятор выдаёт ровно три инструкции, и объясни, почему именно эту раскладку он предпочёл.

CHK-5★★

Напиши две функции: @divTrunc(x, 16) и x >> 4. Собери обе, сними дизассемблер и посчитай инструкции. Затем найди все значения x в диапазоне от -100 до 100, на которых их результаты различаются, и убедись, что это ровно те, где остаток от деления не нулевой.

CHK-6★★★

Доведи шаг проекта у себя и проверь его на настоящем файле: собери любой объектник и посмотри его первые тридцать два байта с --words=2, --words=4 и --words=8. Найди в дампе поле e_machine по смещению 0x12 и объясни, при какой группировке его значение читается прямо из вывода, а при какой приходится собирать цифры руками.

CHK-7★★

В примере с судоку замени unreachable на ошибку error.Duplicate и заставь set вернуть !void; проверь тестом через expectError, что сетка с двумя пятёрками в одной строке отклоняется. Затем собери i / 9 для u8 в ReleaseFast, найди в листинге множитель и сдвиг и докажи перебором всех 256 значений, что они дают то же, что деление.

Итоги

Целые произвольной ширины превращают таблицы книги в тесты: u4 перебирается за 256 пар, i5 за 1024, и правило про переполнение по знакам проверяется целиком, а не на примерах.
@Int(.unsigned, w) строит целый тип из описания, поэтому одна comptime-функция печатает таблицу любой ширины. Старого @Type в 0.16 нет.
@bitCast это четвёртое преобразование: ширина та же, биты те же, меняется только прочтение. Несовпадение ширин это ошибка компиляции, а не молчаливое усечение.
@as расширяет, @intCast сужает с проверкой в Debug и ReleaseSafe, @truncate отрезает старшие биты без проверок, @bitCast не трогает биты вовсе.
Порядок байтов у машины можно спросить у самой памяти: положить единицу и посмотреть на первый байт. native_endian знает ответ уже во время компиляции.
Числа из чужих байтов читаются через std.mem.readInt с явным порядком, а не через @ptrCast: последний даёт порядок машины и требует выравнивания.
@byteSwap это одна инструкция процессора. std.mem.nativeToBig и родня разворачиваются в неё или в ничто, в зависимости от целевой архитектуры.
Счётчик сдвига имеет собственный тип std.math.Log2Int(T): u3 для u8, u5 для u32, u6 для u64. Сдвига ровно на ширину типа не существует, и это ошибка компиляции, а не неопределённое поведение.
Циклический сдвиг пишется двумя сдвигами вместо одного на w - n, иначе при нулевом повороте попадаешь в несуществующий счётчик.
Девять бит на строку судоку: цифра это бит, проверка повтора это одно побитовое и. Сдвиг со счётчиком u4 сам отбрасывает цифры вне диапазона паникой, unreachable утверждает инвариант только в Debug и ReleaseSafe, а деление на константу компилятор заменяет умножением на обратную дробь, так что таблица вместо i / 3 не выигрывает ничего.
Правый сдвиг знакового значения арифметический, беззнакового логический. Выбор делает тип, а не оператор.
Умножение на константу раскладывается двумя формами: сумма сдвигов по единичным битам и разность сдвигов по сериям единиц. Компилятор знает обе, добавляет к ним lea и разложение на множители, а для дорогих констант просто берёт imul.
x >> k для знакового x это деление вниз, а @divTrunc это деление к нулю. Разница только на отрицательных числах, и компилятор платит за неё поправкой 2^k - 1 плюс cmov.
@divFloor(x, 8) и x >> 3 компилируются в побайтно одинаковый код, и линковщик складывает их в одну функцию с двумя именами.

Дальше

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

Число с плавающей точкой это не одно поле, а три: знак, порядок и мантисса, упакованные в те же тридцать два или шестьдесят четыре бита. Из одной этой упаковки следует всё остальное: почему 0.1 + 0.2 не равно 0.3, почему рядом с нулём числа гуще, чем рядом с миллионом, откуда берутся два нуля и целое семейство значений NaN. В следующем уроке мы соберём мини-формат из пяти бит, где все значения выписываются руками на одну страницу, а потом развернём его до настоящих f16, f32, f64, f80 и f128 в Zig. @bitCast из сегодняшнего урока окажется главным инструментом: удвоить число, поделить пополам и превратить его в целое можно прямо на битах, не трогая арифметику с плавающей точкой вовсе.

домашка

Домашка

Напиши программу, которая печатает байты одного и того же числа четырьмя способами: через asBytes, через writeInt с little, через writeInt с big и через byteSwap. Собери её под x86_64-linux и под большой порядок байтов (например s390x-linux) и объясни, какие строки совпали.M
Для констант 5, 12, 23, 100 и 255 выпиши обе формы книги (сумма сдвигов и разность сдвигов), посчитай операции, а потом собери x умножить на каждую из них в ReleaseFast и сверь свой ответ с дизассемблером. Отметь, где компилятор взял imul вместо сдвигов.M
Доведи шаг проекта до зелёных тестов: zt hexdump понимает --words=N и --big, группы читаются через std.mem.readInt, неполный хвост строки печатается побайтно. Проверь на заголовке любого ELF, что --words=4 и --words=4 --big дают разный порядок цифр.MS