Анализ целочисленного кодирования Protobuf: Varint и Zigzag

protobuf

Protocol Buffer (сокращенно Protobuf) — это высокопроизводительная межъязыковая кроссплатформенная библиотека сериализации, разработанная Google.

Для большей эффективности оборудования числа в компьютерах обычно представляются целыми числами фиксированной длины. Однако сегодня, когда микросервисы повсюду, необходим более гибкий способ передачи чисел для экономии полосы пропускания. Varint (целые числа переменной длины) — это метод кодирования целых чисел, с помощью которого можно гибко настроить пространство, необходимое для целочисленных значений.

Кодировка варинта

Varint в Protobuf выполняет двоичное кодирование переменной длины в соответствии с размером целого числа, меньше 128 (2^{7}) занимает 1 байт после целочисленного кодирования, меньше 16384 (2^{14}) после целочисленного кодирования, занять 2 и т. д., до 10 байтов можно использовать для указания больше или равно2^{63}Целочисленный тип , принцип его реализации показан на следующем рисунке:

image.png

Для каждого закодированного байта первый бит идентифицирует, является ли он хвостом, а последующие 7 битов используются для записи двоичных битов исходного числа.Например, двоичное число 299 в int32 равно

00000000 00000000 00000001 00101011

Закодированный результат10101011 00000010, что экономит 2 байта на передачу.

Поскольку только 7 бит каждого байта в результате кодирования Varint являются значимыми битами (хранят исходные данные), менее2^{28}Int32 или int64 могут быть сжаты кодировкой Varint. Конечно, использование небольших чисел обычно намного больше, чем использование больших чисел, поэтому кодирование Varint может сжиматься для большинства сценариев.

Кодировка варинта реализована следующим образом:

const maxVarintBytes = 10 // maximum length of a varint

// EncodeVarint returns the varint encoding of x.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
// Not used by the package itself, but helpful to clients
// wishing to use the same encoding.
func EncodeVarint(x uint64) []byte {
	var buf [maxVarintBytes]byte
	var n int
	for n = 0; x > 127; n++ {
		// 首位记 1, 写入原始数字从低位始的 7 个 bit
		buf[n] = 0x80 | uint8(x&0x7F)
		// 移走记录过的 7 位
		x >>= 7
	}
	// 剩余不足 7 位的部分直接以 8 位形式存下来，故首位为 0
	buf[n] = uint8(x)
	n++
	return buf[0:n]
}

В нем используются 2 магических числа, это можно понять, взглянув на их двоичный код.& 0x7fПолучите 7 бит,| 0x80Отметьте первую позицию как 1.

0x80 => 0000000010000000
0x7f => 0000000001111111

Таким образом, метод десериализации Varint состоит в том, чтобы взять последние 7 битов каждого байта и объединить их в обратном порядке, как показано на следующем рисунке (в качестве примера взят результат кодирования 299):

image.png

Исходный код выглядит следующим образом:

// DecodeVarint reads a varint-encoded integer from the slice.
// It returns the integer and the number of bytes consumed, or
// zero if there is not enough.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
func DecodeVarint(buf []byte) (x uint64, n int) {
	for shift := uint(0); shift < 64; shift += 7 {
		if n >= len(buf) {
			return 0, 0
		}
		b := uint64(buf[n])
		n++
		// 弃首位取 7 位并加回 x
		x |= (b & 0x7F) << shift
		// 首位为 0
		if (b & 0x80) == 0 {
			return x, n
		}
	}

	// The number is too large to represent in a 64-bit value.
	return 0, 0
}

Здесь есть проблема,EncodeVarintа такжеDecodeVarintВсе типы uint64, что, если нам нужно иметь дело с отрицательными числами? Посмотрите, что вы получите, напрямую закодировав отрицательные числа как uint64:

fmt.Println(EncodeVarint(uint64(-299)))
// output:
// [213 253 255 255 255 255 255 255 255 1]

Результатом будет 10-байтовая кодировка, т.к.uint64(-299)Значение - это дополнение 299, которое должно быть представлено в 64 битах! То есть в итоге будет получена максимальная длина варинтной кодировки.Исходный код для расчета длины закодированных байтов в официальной библиотеке выглядит следующим образом:

// SizeVarint returns the varint encoding size of an integer.
func SizeVarint(x uint64) int {
	switch {
	case x < 1<<7:
		return 1
	case x < 1<<14:
		return 2
	case x < 1<<21:
		return 3
	case x < 1<<28:
		return 4
	case x < 1<<35:
		return 5
	case x < 1<<42:
		return 6
	case x < 1<<49:
		return 7
	case x < 1<<56:
		return 8
	case x < 1<<63:
		return 9
	}
	return 10
}

Zigzag

Зигзагообразное кодирование сопоставляет целые числа со знаком с целыми числами без знака, как следует из названия, а закодированное значение колеблется между положительными и отрицательными целыми числами, как показано в следующей таблице:

Signed Original Encoded As
0 0
-1 1
1 2
-2 3
2147483647 4294967294
-2147483648 4294967295

Он реализован следующим образом:

func Zigzag64(x uint64) uint64 {
	// 左移一位 XOR (-1 / 0 的 64 位补码)
	return (x << 1) ^ uint64(int64(x) >> 63)
}

Здесь следует отметить, что если x отрицательно, левая часть XOR является дополнением -x и сдвигается влево на единицу. На следующем рисунке в качестве примера используется -299, сначала вычислите дополнение 299, затем дополнение знака XOR (-1 / 0), результат равен 597; если это положительное число, результат зигзага в 2 раза больше оригинальный номер.

image.png

резюме

При написании этой статьи я просмотрел волну базовых знаний, например, почему результат кодирования Varint отрицательного числа составляет 10 байт, потому что отрицательное число хранится в виде дополнения. Таким образом, концепции, которые кажутся вводными в университете, на самом деле встречаются в программировании, а путь долог.

обновление: 2020.01.22 исправить описание ошибки

Категории