Кодируем битики: bit reader, varint, zigzag

Финал машинного блока и первый инженерный артефакт раздела: библиотечка упаковки данных в байты, написанная руками от начала до конца. Varint и zigzag как в protobuf, поток бит поверх потока байтов, однобайтовый заголовок с полями. Этот код ещё всплывёт трижды: в эмуляторе, в сетевом протоколе и в блокчейне.

Идея

Сервер игры рассылает шестнадцати игрокам обновление позиции тридцать раз в секунду. Наивный вариант, JSON:

{"id":42,"dx":-3,"dy":1,"on_ground":true}

41 байт. Кодек, который мы соберём к концу урока, упакует то же сообщение в четыре байта: [0x21, 0x2A, 0x05, 0x02]. В десять раз меньше, и читается не парсером текста, а несколькими сдвигами по заранее известному плану.

Такой план называется форматом, и формат это контракт: писатель и читатель заранее договорились, в каком порядке лежат поля, какой они ширины и каким порядком байтов записаны. Все инструменты для исполнения контракта у тебя уже есть, блок выдал их по частям: интерпретация байтов и endianness из урока про биты, поведение целых на границах из урока про дополнительный код, и прошлый урок объяснил, почему нельзя просто сдампить структуру как лежит: раскладка не обещана, а padding содержит мусор. Сериализация и есть ответ: мы сами, явно, поле за полем, решаем судьбу каждого байта.

Честный вопрос: зачем руками, если в экосистеме есть serde. В проде для своих структур ты возьмёшь serde, это правильно. Но чужие форматы, protobuf, бинарный WASM, заголовок TCP, ROM-файл для эмулятора, читаются по спецификации, а не через derive. А свои форматы, вроде сетевого протокола третьего проекта, проектируются с пониманием цены каждого байта. Один раз написав кодек руками, ты будешь читать спецификации форматов как код, а в serde видеть автоматизацию, а не магию.

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

Этаж первый: байты и контракт формата

Писатель тривиален: Vec<u8> плюс явный порядок байтов:

fn write_u8(out: &mut Vec<u8>, x: u8) {
    out.push(x);
}

fn write_u32_le(out: &mut Vec<u8>, x: u32) {
    out.extend_from_slice(&x.to_le_bytes());
}

Суффикс le в имени не украшение, а пункт контракта: наш формат little endian, и решение проговорено в каждом имени, ровно как в to_le_bytes.

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

#[derive(Debug, PartialEq)]
enum DecodeError {
    UnexpectedEnd,
    Overflow,
    BadVersion(u8),
}

struct Reader<'a> {
    data: &'a [u8],
    pos: usize,
}

impl<'a> Reader<'a> {
    fn new(data: &'a [u8]) -> Self {
        Reader { data, pos: 0 }
    }

    fn read_u8(&mut self) -> Result<u8, DecodeError> {
        let byte = *self.data.get(self.pos).ok_or(DecodeError::UnexpectedEnd)?;
        self.pos += 1;
        Ok(byte)
    }

    fn read_u32_le(&mut self) -> Result<u32, DecodeError> {
        let end = self.pos + 4;
        let bytes = self.data.get(self.pos..end).ok_or(DecodeError::UnexpectedEnd)?;
        self.pos = end;
        Ok(u32::from_le_bytes(bytes.try_into().expect("ровно четыре байта")))
    }
}

Reader держит ссылку на срез и позицию в нём; пометка 'a говорит, что читатель не переживёт данные, которые читает. Обрати внимание на get вместо индексации: входящие байты это данные с улицы, и паника на обрезанном пакете означала бы, что любой желающий роняет твой сервер одним битым сообщением. Тот же рефлекс, что в уроке про защитный стиль: на границе доверия ошибки возвращаются, а не взрываются.

Фиксированная ширина хороша для float, хешей и координат известного диапазона. Но для счётчиков и идентификаторов она расточительна: id объявлен как u64, а реальные значения почти всегда меньше тысячи, и семь старших байт из восьми везут нули.

Этаж второй: varint

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

fn write_varint(out: &mut Vec<u8>, mut x: u64) {
    while x >= 0x80 {
        out.push((x as u8) | 0x80);
        x >>= 7;
    }
    out.push(x as u8);
}

Разбор по битам для числа 300:

300 в двоичной записи:  1_0010_1100

младшие семь бит: 010_1100  плюс флаг продолжения 1 →  1010_1100 = 0xAC
остаток после >>7: 10       плюс флаг конца 0       →  0000_0010 = 0x02

итого 300 → [0xAC, 0x02]

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

fn read_varint(r: &mut Reader) -> Result<u64, DecodeError> {
    let mut result = 0u64;
    let mut shift = 0u32;
    loop {
        let byte = r.read_u8()?;
        result |= u64::from(byte & 0x7f) << shift;
        if byte & 0x80 == 0 {
            return Ok(result);
        }
        shift += 7;
        if shift >= 64 {
            return Err(DecodeError::Overflow);
        }
    }
}

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

Теперь цена в байтах:

Маленькие числа стоят байт, гиганты переплачивают два. Реальные данные скошены в мелочь: длины, счётчики, идентификаторы, дельты. Поэтому varint живёт повсюду: в protobuf так закодированы ключи полей и все целые, бинарный формат WASM держит на LEB128 все свои счётчики и смещения, его же берёт postcard из экосистемы Rust и формат отладочной информации DWARF. Обратная сторона: ветвление на каждом байте. Фиксированная ширина декодируется без ветвлений и предсказуема по размеру, поэтому протоколы с жёстким бюджетом латентности выбирают её сознательно; в финале серии, в HFT-блоке, ты увидишь этот выбор вживую.

И одна тонкость на вырост. Последовательность 0x80 0x00 раскодируется в тот же ноль, что и одиночный 0x00: у числа два представления. Для игрового протокола это пустяк, для криптографии дыра: хеш и подпись считаются над байтами, а не над числами, и два представления одного значения это два разных хеша «одинаковых» сообщений. Форматы под подпись требуют каноничности, одно число кодируется ровно одной последовательностью байтов, а перекодировки отвергаются декодером. Запомни эту мысль до блокчейна, там она станет вопросом консенсуса.

Zigzag: знаковые без переплаты

У varint есть слепое пятно, и оно знаковое:

let mut buf = Vec::new();
write_varint(&mut buf, -1i64 as u64);
assert_eq!(buf.len(), 10);

Минус один в дополнительном коде это все единицы, для varint худшее число на свете: десять байт. А маленькие отрицательные числа в данных сплошь и рядом: дельты координат, разности времени, изменения счёта.

Решение не менять varint, а перенумеровать числа перед ним. Кодировка zigzag перемежает знаки, раскладывая числа с маленьким модулем на маленькие коды:

Название отсюда же: нумерация зигзагом скачет вокруг нуля. Обе формулы укладываются в строку:

fn zigzag_encode(x: i64) -> u64 {
    ((x << 1) ^ (x >> 63)) as u64
}

fn zigzag_decode(n: u64) -> i64 {
    ((n >> 1) as i64) ^ -((n & 1) as i64)
}

Разберём кодер по битам. x << 1 удваивает число. x >> 63 это арифметический сдвиг из урока про биты: для неотрицательных он даёт ноль, для отрицательных все единицы. Дальше работает исключающее ИЛИ: с нулём оно ничего не меняет, неотрицательные просто удвоились и стали чётными; со все-единицами оно превращается в побитовое НЕ, и отрицательные после удвоения инвертируются на нечётные. Проверь на минус единице: сдвиг даёт ...11110, инверсия ...00001, единица. Знак переехал в младший бит, модуль в остальные.

Декодер зеркален: n >> 1 восстанавливает модуль, n & 1 достаёт бит знака, минус разворачивает его в ноль или все-единицы, и то же исключающее ИЛИ доделывает работу:

assert_eq!(zigzag_encode(-3), 5);

let mut buf = Vec::new();
write_varint(&mut buf, zigzag_encode(-3));
assert_eq!(buf, [0x05]);

for x in [-300i64, -1, 0, 1, 300] {
    assert_eq!(zigzag_decode(zigzag_encode(x)), x);
}

Один байт вместо десяти. В protobuf это типы sint32 и sint64; обычный int32 кодируется без zigzag, и отрицательные значения в нём стоят десять байт, классические грабли, на которые наступает каждое второе API. Avro и compact-протокол Thrift включают zigzag для знаковых всегда.

Этаж третий: отдельные биты

Остался уровень ниже байта. Флаг занимает один бит, версия формата три, регистр в опкоде эмулятора пять, а коды Хаффмана в DEFLATE вообще дробной длины. Для таких полей нужен слой, который превращает поток байтов в поток бит.

Сначала контракт, потому что у бит внутри байта нет физического порядка, порядок назначает формат. Наш выбор: LSB-first, первый записанный бит ложится в младший разряд первого байта. Так устроен DEFLATE; JPEG и MPEG живут наоборот. Спорить не о чем, важно одно: писатель и читатель согласны.

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

struct BitWriter {
    out: Vec<u8>,
    acc: u64, // биты, не дотянувшие до целого байта
    len: u32, // сколько их в накопителе
}

impl BitWriter {
    fn new() -> Self {
        BitWriter { out: Vec::new(), acc: 0, len: 0 }
    }

    fn write_bits(&mut self, value: u64, n: u32) {
        debug_assert!(n >= 1 && n <= 32 && value >> n == 0);
        self.acc |= value << self.len;
        self.len += n;
        while self.len >= 8 {
            self.out.push(self.acc as u8);
            self.acc >>= 8;
            self.len -= 8;
        }
    }

    fn finish(mut self) -> Vec<u8> {
        if self.len > 0 {
            self.out.push(self.acc as u8); // добор нулями до границы байта
        }
        self.out
    }
}

Механика в три такта. Новые биты встают в acc выше уже накопленных: value << self.len. Как только накопилось восемь, младший байт уезжает в выход, остаток сдвигается на его место. finish добирает хвост нулями до границы байта, потому что меньше байта записать в память нельзя. debug_assert проговаривает контракт: не больше 32 бит за раз и значение влезает в заявленную ширину; при таких границах 64-битному накопителю не грозит переполнение.

Читатель зеркален до последнего сдвига:

struct BitReader<'a> {
    data: &'a [u8],
    pos: usize,
    acc: u64,
    len: u32,
}

impl<'a> BitReader<'a> {
    fn new(data: &'a [u8]) -> Self {
        BitReader { data, pos: 0, acc: 0, len: 0 }
    }

    fn read_bits(&mut self, n: u32) -> Result<u64, DecodeError> {
        debug_assert!(n >= 1 && n <= 32);
        while self.len < n {
            let byte = *self.data.get(self.pos).ok_or(DecodeError::UnexpectedEnd)?;
            self.pos += 1;
            self.acc |= u64::from(byte) << self.len;
            self.len += 8;
        }
        let value = self.acc & ((1u64 << n) - 1);
        self.acc >>= n;
        self.len -= n;
        Ok(value)
    }
}

Вырезание self.acc & ((1u64 << n) - 1) это маска из урока про биты, тот же приём, что в RGB565, только ширина поля приходит параметром.

Главный тест любого кодека называется round-trip: что записали, то и прочитали.

let fields = [(0b1u64, 1u32), (0b101, 3), (300, 9), (77, 7)];

let mut w = BitWriter::new();
for &(value, width) in &fields {
    w.write_bits(value, width);
}
let bytes = w.finish();
assert_eq!(bytes, [0xCB, 0xB2, 0x09]); // 20 бит улеглись в три байта

let mut r = BitReader::new(&bytes);
for &(value, width) in &fields {
    assert_eq!(r.read_bits(width).unwrap(), value);
}

И важная оговорка про природу битового потока: он не самоописываем. Varint сам знает, где кончается, флаг продолжения встроен в данные. А read_bits надо звать с теми же ширинами и в том же порядке, что write_bits: схема ширин это и есть формат, она живёт в коде и документации, и менять её можно только вместе с версией.

Заголовок: битовые поля при деле

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

бит:    7 6 5     4 3     2 1 0
поле:   версия    тип     флаги

const VERSION: u8 = 1;
const KIND_PLAYER_UPDATE: u8 = 0;
const FLAG_ON_GROUND: u8 = 1 << 0;

fn pack_header(kind: u8, flags: u8) -> u8 {
    debug_assert!(kind < 4 && flags < 8);
    (VERSION << 5) | (kind << 3) | flags
}

fn unpack_header(byte: u8) -> (u8, u8, u8) {
    (byte >> 5, (byte >> 3) & 0b11, byte & 0b111)
}

Сборка это сдвиг и ИЛИ, разборка это сдвиг и маска: паттерн RGB565 из урока про биты, впервые при деле в настоящем формате. Версия стоит в старших битах не случайно: незнакомую версию декодер отвергает первой же проверкой, до чтения остальных полей. Три бита дают версии от 0 до 7: когда формат поменяется несовместимо, число вырастет, и старые клиенты честно скажут «не понимаю» вместо того, чтобы прочитать мусор и поверить ему.

Собираем кодек

Все три этажа сходятся в сообщение из начала урока:

#[derive(Debug, PartialEq)]
struct PlayerUpdate {
    id: u64,
    dx: i64,
    dy: i64,
    on_ground: bool,
}

fn encode(msg: &PlayerUpdate) -> Vec<u8> {
    let mut out = Vec::new();
    let flags = if msg.on_ground { FLAG_ON_GROUND } else { 0 };
    out.push(pack_header(KIND_PLAYER_UPDATE, flags));
    write_varint(&mut out, msg.id);
    write_varint(&mut out, zigzag_encode(msg.dx));
    write_varint(&mut out, zigzag_encode(msg.dy));
    out
}

fn decode(data: &[u8]) -> Result<PlayerUpdate, DecodeError> {
    let mut r = Reader::new(data);
    let (version, _kind, flags) = unpack_header(r.read_u8()?);
    if version != VERSION {
        return Err(DecodeError::BadVersion(version));
    }
    Ok(PlayerUpdate {
        id: read_varint(&mut r)?,
        dx: zigzag_decode(read_varint(&mut r)?),
        dy: zigzag_decode(read_varint(&mut r)?),
        on_ground: flags & FLAG_ON_GROUND != 0,
    })
}

Посмотри на сигнатуры: encode возвращает голый Vec<u8>, а decode обязан вернуть Result. Асимметрия не случайна: закодировать можно любое состояние, а раскодировать приходится любые байты, в том числе обрезанные и враждебные. Это свойство всех кодеков на свете.

Теперь тесты, и их два вида по делу:

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn round_trip() {
        let msg = PlayerUpdate { id: 42, dx: -3, dy: 1, on_ground: true };
        assert_eq!(decode(&encode(&msg)).unwrap(), msg);
    }

    #[test]
    fn golden_bytes() {
        let msg = PlayerUpdate { id: 42, dx: -3, dy: 1, on_ground: true };
        assert_eq!(encode(&msg), [0x21, 0x2a, 0x05, 0x02]);
    }

    #[test]
    fn truncated_input_is_an_error() {
        let bytes = encode(&PlayerUpdate { id: 42, dx: -3, dy: 1, on_ground: true });
        assert_eq!(decode(&bytes[..2]), Err(DecodeError::UnexpectedEnd));
    }
}

Разбери золотые байты руками: 0x21 это 0b0010_0001, версия 001, тип 00, флаг on_ground 1. Дальше 0x2A, это id 42 одним байтом. Потом 0x05: dx минус три прошёл через zigzag и стал пятёркой. И 0x02: dy единица стала двойкой. Четыре байта против сорока одного у JSON.

Второй тест называется golden-тест, и он не дублирует round-trip, а закрывает его слепую зону. Round-trip ловит рассинхрон кодера с декодером, но если оба синхронно изменились, он зелёный, а формат уже другой: старые сохранения и чужие клиенты перестали читаться. Golden фиксирует сами байты. Упал golden, значит ты изменил формат: либо это намеренно, и тогда поднимай VERSION и думай про миграцию, либо откатывай.

Куда этот код растёт дальше. Декодер инструкций эмулятора это read_bits по полям 16-битного слова: опкод, регистр, непосредственное значение. Сетевой протокол третьего проекта это этот же кодек плюс дельта-компрессия и надёжность поверх UDP. Сериализация блока в блокчейне это те же writer-функции, только байты пойдут под хеш, и каноничность из раздела про varint станет вопросом консенсуса. А когда возьмёшь serde, увидишь знакомое: derive(Serialize) генерирует те же последовательности writer-вызовов, что ты писал сегодня руками, и bincode с postcard внутри устроены ровно так.

ДЗ

Дальше

Машинный блок закрыт. Ты прошёл его насквозь: биты и endianness, дополнительный код, IEEE-754, дизассемблер, раскладка структур, и в финале собрал из всего этого работающий кодек с тестами. Дальше раздел разворачивается обратно вверх, к языку, но уже с этим фундаментом: впереди глубокий core. Box, Rc и RefCell изнутри, внутренняя мутабельность, цена подсчёта ссылок и первый шаг на территорию Rustonomicon.