Целое безразмерное

Часто возникает задача передавать числовые значения по какому-либо каналу связи.
«Ну берешь и передаешь! Чё тут думать?». Допустим на одной из сторон — микроконтроллер слабенький да еще и канал связи ооочень медленный.
Тогда уже каждый байт на счету. Однажды мне встретилось интересное решение — сериализация чисел как varint.

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

Алгоритм позаимствован из protobuf. Идея заключается в том, что число кодируется различным количеством байт от 1 и выше. В числе varint все байты, кроме последнего содержат с старшем бите 1, а замыкающий байт содержит 0, что и сигнализирует об окончании числа. Т.е., число перед сериализацией разбивается на 7-битные блоки.

Например, число 4 будет представлено как 0000 0100 (как и в обычном бинарном представлении). Число 312 (1 0011 1000) разбивается на 7-битные блоки (0000010 0111000) и передается в виде 10000100 00111000.

Очевидно, что для многих чисел такое кодирование будет избыточным. А именно, многие 32-битные числа будут кодироваться пятью байтами вместо четырех, однобайтные числа от 128 до 255 будут занимать по 2 байта и т.д.
Но если исходить из контекста — скажем, нужно передать размер пакета. Допустим, обычно пакеты небольшие — до 100 байт, но не исключена отправка пакета в несколько килобайт. Выберем тип uint16_t для хранения размера — получим один избыточный байт для всех маленьких пакетов. А используя varint возможные потери будут только для больших пакетов, где дополнительный байт не настолько критичен.

Вот для примера реализации кодера и декодера для varint:

/* Наибольшее теоретически возможное число */
typedef uint64_t maxint_t; 

int vintenc(maxint_t val, uint8_t *buf, size_t len) {
	unsigned int offset = 0;
	uint8_t bits;
	bits = val & 0x7f;
	val >>= 7;
	while (val != (int64_t)0) {
		if (offset == len) return -1;
		buf[offset++] = bits | 0x80;
		bits = val & 0x7f;
		val >>= 7;
	}
	if (offset == len) return -1;
	buf[offset++] = bits;;
	return offset;
}

int vintdec(uint8_t buf[], size_t len, maxint_t *res) {
	unsigned int shift = 0;
	unsigned int pos = 0;
	*res = 0;
	while (1) {
		uint8_t b;
		if (pos == len) return -1;
		b = buf[pos];
		*res |= (maxint_t) ((b & 0x7f)) << shift;
		pos++;
		if ((b & 0x80) == 0) {
			return 0;
		}
		shift += 7;
		if (shift >= 8 * sizeof(*res)) {
			return -1;
		}
	}
}

maxint_t x;

/* n - размер полученного varint в байтах или -1 в случае ошибки */
n = vintenc(x, buf, sizeof(buf)); 
vintdec(buf, sizeof(buf), &x);

Разумеется, если maxint_t сответствует uint16_t, то циклы можно поразворачивать для пущей оптимизации.

А отрицательные числа?

Привычное нам кодирование предполагает, что 8-битное число со значением -1 представляется в виде 1111 1111. Это значит, что все отрицательные числа будут кодироваться в varint числом с максимальным размером. Если в протоколе используются отрицательные числа (коды ошибок, значения с датчиков), то можно использовать кодирование зигзагом, при котором порядок положительных и отрицательных чисел чередуется (т.е. вместо -2, -1, 0, 1, 2, 3, … получим 0, -1, 1, -2, 2, -3, 3, …). Вот как это может быть реализовано:

maxint_t zzenc(maxint_t n) {
	return (n << 1) ^ (n >> (8 * sizeof(n) - 1));
}

maxint_t zzdec(maxint_t n) {
	return (n & 1 ? (n >> 1) : -(n >> 1));
}

Фактически, младший бит определяет знак числа вместо старшего и все числа хранятся по абсолютному значению.

Вообщем, замысел varint на мой взгляд интересный, да и реализация довольно простая. Странно, что раньше об этом приеме ничего не слышал.

Реклама

2 comments on “Целое безразмерное

  1. Ation:

    Декодирование по-моему не работает.
    Да и лучше переписать без if использую просто обратную операцию
    return n>>1 ^ (n << (8 * sizeof(n) — 1));

    • да, в zzdec я со знаком явно напутал, пасибо.
      А if тут так сказать для наглядности — что реально по младшему биту судим о знаке. Обратная операция, конечно, тоже будет работать точно так же.

Добавить комментарий

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

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s