Minecraft protocol VarInt и VarLong. Как из единиц и нулей сделать число на примере Go?
В этой статье я хочу объяснить на пальцах, как из байтов преобразуются числа в нужные типы данных (VarInt, VarLong). Детально рассмотрим реализацию, примеры и напишем unit-тесты. Вспомним бинарные операции, двоичную и шеснадцатиричную систему счисления.
Предыстория
Я уже не раз разворачивал свой сервер Minecraft, используя разные ядра: Vanilla, Spigot, SpongeForge, Paper, Velocity(хотя это прокси, но все же) — все они написаны на Java. В один момент мне стало интересно, а можно ли написать свою имплементацию сервера Minecraft с нуля (from scratch). Ответ на мой вопрос лежит по этой ссылке. Перейдя по ней я увидел заголовок »Before You Get Started», в котором есть три небольших тезиса:
«Убедитесь, что вы не хотите форкнуть, или присоединиться к уже существующему форку», — интересное предложение, но я бы хотел смотреть на форки, как на пример реализации.
«Подумайте, почему вы хотите это сделать?», — я хочу более углубленно разобраться в логике взаимодействия клиент-сервер Minecraft’а.
«Выберите язык с хорошим сетевым взаимодействием, например Java, C# или Python», — Хорошо, попробую написать на Go, у него как раз отличные встроенные инструменты для таких задач.
Как вы уже поняли, выбрал я Go, в частности потому что это сейчас мой основной язык, на котором я выполняю свою работу, мне нравится Go потому что он простой, быстрый, да и памяти будет кушать намного меньше чем Java, а значит может стать хорошим вариантом для написания своего собственного сервера. Хочу попробовать!
Реализация
Взаимодействие между клиентом и сервером Minecraft происходит путем установления подключения через TCP протокол, через который обе стороны начинают обмениваться пакетами данных. Структура пакетов описана так же в документации (ссылка).
Чтобы извлекать информацию из пакетов, нужно научиться их декодировать. Абстрагируемся от лишней информации и сконцентрируемся на двух типах данных VarInt и VarLong. В документации для них уделено достаточно много внимания и даже описаны примеры, как правильно производить decode и encode.
These are very similar to Protocol Buffer Varints.
(перевод) Эти два типа очень похожи на Protocol Buffer Varints.
В документации сказано, что 7 младших битов используются для кодирования значения, а старший 8 (восьмой) для определения будут ли еще последуюбщие байты числа после текущего. Так же есть условия:
Давайте приступать к реализации! Напишем код, в котором определим наши два типа
// Package packet назвал его именно так,
// потому что типы данным принадлежат пакетам.
// Сейчас мы находимя в файле data_types.go
package packet
const (
// MaxVarIntLen максимальное кол-во байтов для VarInt.
MaxVarIntLen = 5
// MaxVarLongLen максимальное кол-во байтов для VarLong.
MaxVarLongLen = 10
)
type (
// VarInt обычный int (-2147483648 -- 2147483647)
VarInt int
// VarLong обычный int64 (-9223372036854775808 -- 9223372036854775807)
VarLong int64
)Нам нужно будет считывать байты из какого-то буфера, поэтому будем реализовывать интерфейс io.ReaderFrom. Определим новые методы для наших типов.
func (v *VarInt) ReadFrom(r io.Reader) (n int64, err error) {
return 0, nil
}
func (v *VarLong) ReadFrom(r io.Reader) (n int64, err error) {
return 0, nil
}Приступим к разбору реализации. На просторах интернета я нашел библиотеку https://github.com/Tnze/go-mc. По словам разработчиков в ней уже реализована имплементация протокола для сервера Minecraft, парсинг пакетов и т.п. Мой код будет очень похожим на реализацию https://github.com/Tnze/go-mc/blob/master/net/packet/types.go#L265, но я хочу понять, почему этот алгоритм верный и как вообще из последовательности [101010001] получаются числа.
Сама реализация интерфейса io.ReaderFrom для VarInt и VarLong не отличается, разве что использованием разных констант для максимальной возможной длины последовательности байтов.
Для начала определем две константы, ошибку, если кол-во байтов превышает максимально допустимый разбер типа данных и небольшую функцию, которая считывает один байт из буфера:
const (
// segmentBits 7 бит 01111111 = int(127)
segmentBits byte = 0x7F
// continueBit 8 бит 11111111 = int(128)
continueBit 8 byte = 0x80
)
// ErrTooBig ошибка, если какой-то тип превышает максимально доступное кол-во байтов
var ErrTooBig = errors.New("too big")
// readByte считывает только ОДИН байт из буфера и возвращает его.
func readByte(r io.Reader) (byte, error) {
if r, ok := r.(io.ByteReader); ok {
return r.ReadByte()
}
var b [1]byte
if _, err := io.ReadFull(r, b[:]); err != nil {
return 0, errors.Wrap(err, "failed to perform read full")
}
return b[0], nil
}Реализуем интерфейс io.ReaderFrom для VarInt.
// ReadFrom ...
func (v *VarInt) ReadFrom(r io.Reader) (n int64, err error) {
var val uint32
for sec := continueBit; sec&continueBit != 0; n++ {
if n > VarIntMaxLen {
return 0, ErrTooBig
}
sec, err = readByte(r)
if err != nil {
return 0, errors.Wrap(err, "failed to read a byte")
}
val |= uint32(sec&segmentBits) << uint32(7*n)
}
*v = VarInt(val)
return n, nil
}Давайте подробнее пройдемся по этому коду и посмотрим, как из последовательности байтов, состоящих из нулей и единиц получаются числа.
Рассмотрим на примере числа 25565.
Число 25565 в нашем буфере можно представить следующими способами:
В шеснадцатиричной системе =
[0xdd, 0xc7, 0x01]В десятичной системе =
[221, 199, 1]В двоичной системе =
[11011101, 11000111, 00000001]
В буфере мы имеем[..., 11011101, 11000111, 00000001, ...].
Эта последовательность может быть разной длины, для примера мы откинем переднюю часть и будем считать, что мы уже произвели считывание до нашего первого байта,
а наш указатель находится на нем -11011101.
Переменная в которую мы будем записывать результат: var val uint32
Рассмотрим детально каждую итерацию, их здесь будет всего 3.
Итерация #1
Считываем байт sec, err = readByte(r), в результате в sec лежит значение 11011101
V |= uint32(sec&segmentBits) << uint32(7*n) будет эквиваленто0 |= uint32(11011101 & 01111111) << uint32(7*0)
11011101
&
01111111
--------
01011101В результате получаем число 01011101 = uint32(93).
Далее производим логический сдвиг влево на 7*0, т.е. на 0 битов.
01011101 << 0 = 01011101Вычисляем значение val, тут все просто:
val |= 01011101
00000000
|
01011101
--------
01011101К концу первой итерации значение val = uint32(93).
Итерация #2
Считываем байт sec, err = readByte(r), в результате в sec лежит значение 11000111.
V |= uint32(sec&segmentBits) << uint32(7*n) будет эквиваленто93 |= uint32(11000111 & 01111111) << uint32(7*1)
11000111
&
01111111
--------
01000111В результате получаем число 01000111 = uint32(71).
Далее производим логический сдвиг влево на 7*1, т.е. на 7 битов.
01000111 << 7 = 010111010000000Вычисляем значение val:
val |= 010111010000000
000000001011101
|
010111010000000
---------------
010001111011101К концу второй итерации значение val = uint32(9181).
Итерация #3
Считываем байт sec, err = readByte(r), в результате в sec лежит значение 00000001.
V |= uint32(sec&segmentBits) << uint32(7*n) будет эквиваленто9181 |= uint32(00000001& 01111111) << uint32(7*2)
00000001
&
01111111
--------
00000001В результате получаем число 00000001 = uint32(1).
Далее производим логический сдвиг влево на 7*2, т.е. на 14 битов.
00000001 << 7 = 0000000100000000000000Вычисляем значение val:
val |= 0000000100000000000000
0000000010001111011101
|
0000000100000000000000
----------------------
0000000110001111011101К концу второй итерации значение val = uint32(25565).
Почему эта итерация последняя, потому что выражение sec&continueBit = 0
00000001 - sec
&
10000000 - continueBit
--------
00000000Реализация для VarLong
Как я уже упомянул раньше, реализация для данного типа практически не отличается:
// ReadFrom ...
func (v *VarLong) ReadFrom(r io.Reader) (n int64, err error) {
var val uint64
for sec := continueBit; sec&continueBit != 0; n++ {
if n > VarLongMaxLen {
return 0, ErrTooBig
}
sec, err = readByte(r)
if err != nil {
return 0, errors.Wrap(err, "failed to read a byte")
}
val |= uint64(sec&segmentBits) << uint64(7*n)
}
*v = VarLong(val)
return n, nil
}Отрицательные числа
Как получаются отрицательные числа? Расписывать такой громозкий кусок достаточно проблематично, но вкратце на примере числа -1: в последней итерации получается 11111111 11111111 11111111 11111111 . Это число в двоичной системе и в формате uint32 = 4294967295 . Далее мы уже приводим к нужному типу int32, в итоге получаем число -1.
Unit-тесты
Куда же без них, покроем только те места, которые нас итересуют, а именно упустим случаи возвращаения ошибок. Тест кейсы брал из примеров, описанные в документации.
package packet
import (
"bytes"
"github.com/stretchr/testify/assert"
"strconv"
"testing"
)
func TestVarInt_ReadFrom(t *testing.T) {
a := assert.New(t)
type testCase struct {
Bytes []byte
Expected VarInt
}
testCases := []testCase{
{
Bytes: []byte{0x00},
Expected: 0,
},
{
Bytes: []byte{0x01},
Expected: 1,
},
{
Bytes: []byte{0x10},
Expected: 16,
},
{
Bytes: []byte{0x7f},
Expected: 127,
},
{
Bytes: []byte{0xac, 0x02},
Expected: 300,
},
{
Bytes: []byte{0xdd, 0xc7, 0x01},
Expected: 25565,
},
{
Bytes: []byte{0xff, 0xff, 0xff, 0xff, 0x07},
Expected: 2147483647,
},
{
Bytes: []byte{0x80, 0x80, 0x80, 0x80, 0x08},
Expected: -2147483648,
},
{
Bytes: []byte{0xff, 0xff, 0xff, 0xff, 0x0f},
Expected: -1,
},
}
for _, tc := range testCases {
t.Run(strconv.FormatInt(int64(tc.Expected), 10), func(t *testing.T) {
var varInt VarInt
n, err := varInt.ReadFrom(bytes.NewReader(tc.Bytes))
// No error should be here.
a.NoError(err)
// Length of the VarInt must be equal to the bytes size.
a.EqualValues(len(tc.Bytes), n)
// Asserting to the expected VarInt value.
a.EqualValues(tc.Expected, varInt)
})
}
}
Результат Unit-тестов для VarInt
func TestVarLong_ReadFrom(t *testing.T) {
a := assert.New(t)
type testCase struct {
Bytes []byte
Expected VarLong
}
testCases := []testCase{
{
Bytes: []byte{0x00},
Expected: 0,
},
{
Bytes: []byte{0x01},
Expected: 1,
},
{
Bytes: []byte{0x10},
Expected: 16,
},
{
Bytes: []byte{0x7f},
Expected: 127,
},
{
Bytes: []byte{0xac, 0x02},
Expected: 300,
},
{
Bytes: []byte{0xdd, 0xc7, 0x01},
Expected: 25565,
},
{
Bytes: []byte{0xff, 0xff, 0xff, 0xff, 0x07},
Expected: 2147483647,
},
{
Bytes: []byte{0x80, 0x80, 0x80, 0x80, 0xf8, 0xff, 0xff, 0xff, 0xff, 0x01},
Expected: -2147483648,
},
{
Bytes: []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01},
Expected: -1,
},
{
Bytes: []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f},
Expected: 9223372036854775807,
},
{
Bytes: []byte{0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01},
Expected: -9223372036854775808,
},
}
for _, tc := range testCases {
t.Run(strconv.FormatInt(int64(tc.Expected), 10), func(t *testing.T) {
var varLong VarLong
n, err := varLong.ReadFrom(bytes.NewReader(tc.Bytes))
// No error should be here.
a.NoError(err)
// Length of the VarInt must be equal to the bytes size.
a.EqualValues(len(tc.Bytes), n)
// Asserting to the expected VarInt value.
a.EqualValues(tc.Expected, varLong)
})
}
}
Результать Unit-тестов для VarLong
Заключение
Данная статья получилось достаточно длинной и возможно сложной для понимания, но я постарался все изложить максимально подробно. Думаю над написанием второй части про данные два типа, в котором детально разберу как VarInt и VarLong обратно преобразуются в последовательность байтов. Очень будут рад почитать ваше мнение, ответить на ваши вопросы в комментариях!
