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 (восьмой) для определения будут ли еще последуюбщие байты числа после текущего. Так же есть условия:

• VarInt не может быть больше 5 байтов

• VarLong не может быть больше 10 байтов

Давайте приступать к реализации! Напишем код, в котором определим наши два типа

// 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)         })     } }

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)         })     } }

Заключение

Данная статья получилось достаточно длинной и возможно сложной для понимания, но я постарался все изложить максимально подробно. Думаю над написанием второй части про данные два типа, в котором детально разберу как VarInt и VarLong обратно преобразуются в последовательность байтов. Очень будут рад почитать ваше мнение, ответить на ваши вопросы в комментариях!