VarInt

VarInt — универсальный способ кодировать целое число переменной длиной, чтобы маленькие числа занимали меньше байт. Используется в Minecraft, Protocol Buffers, QUIC и десятках других бинарных форматов.

Идея

Число режется на группы по 7 бит. Каждый байт хранит:

• Старший бит (MSB) — continuation flag. 1 = «дальше есть ещё байты», 0 = «это последний».
• Младшие 7 бит — payload (кусок числа).

Байты идут little-endian — младшие биты числа в первом байте.

Кодирование пошагово

Число 300 = 0b100101100

Шаг 1: младшие 7 бит = 0101100. Остались биты 10 = 2.
Шаг 2: continuation=1 (ещё есть), payload=0101100.
     Байт 1 = 10101100 = 0xAC

Шаг 3: следующие 7 бит = 0000010. Больше ничего нет.
Шаг 4: continuation=0, payload=0000010.
     Байт 2 = 00000010 = 0x02

Итого: 300 = 0xAC 0x02  (2 байта)

Размерность

32-битное число в худшем случае — 5 байт (5*7 = 35 бит). Это больше обычного uint32! Но малые числа выигрывают: ID пакетов Minecraft обычно 0-127 → 1 байт вместо 4.

Reference-реализация (Java, Minecraft)

void writeVarInt(int value, OutputStream out) throws IOException {
    while (true) {
        if ((value & ~0x7F) == 0) {         // все старшие биты нулевые
            out.write(value);                // последний байт, MSB=0
            return;
        }
        out.write((value & 0x7F) | 0x80);   // 7 бит + continuation
        value >>>= 7;                        // unsigned right shift
    }
}

int readVarInt(InputStream in) throws IOException {
    int value = 0;
    int position = 0;
    while (true) {
        int b = in.read();
        value |= (b & 0x7F) << position;
        if ((b & 0x80) == 0) return value;   // MSB=0 → конец
        position += 7;
        if (position >= 32) throw new IOException("VarInt too big");
    }
}

ZigZag для знаковых

Проблема: отрицательные числа в two's complement имеют старшие биты = 1 → всегда 5 байт (максимум).

ZigZag encoding ремапит знаковые в беззнаковые так что маленькие |x| → маленькие ZigZag(x):

zigzag(n) = (n << 1) ^ (n >> 31)   // для int32
unzigzag(n) = (n >>> 1) ^ -(n & 1)

Используется в Protocol Buffers для sint32/sint64.

Варианты VarInt

QUIC VarInt

2MSB   Length   Range
──────────────────────────
00     1 байт   0-63
01     2 байта  0-16383
10     4 байта  0-1073741823
11     8 байт   0-2^62-1

Два старших бита первого байта определяют размер. Легко декодировать без цикла — прочитал первый байт, знаешь сколько ещё читать. Используется во всех заголовках QUIC/HTTP-3.

Плюсы и минусы

См. также

• Minecraft protocol, QUIC