21.07.2022 01:58
zubovdev 0 1400 Источник

В этой статье я хочу объяснить на пальцах, как из байтов преобразуются числа в нужные типы данных (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 бит 10000000 = 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
Результат 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
Результать Unit-тестов для VarLong

Заключение

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

Комментарии (0)