Вставка байтов с фиксированной избыточностью

Редактирование: Вставка байтов с фиксированной избыточностью (COBS) — это алгоритм кодирования, адаптированный для байтовых данных. COBS даёт эффективное, надежное, однозначное разделение пакетов на кадры независимо от их содержимого. Алгоритм использует зарезервированное значение (обычно ноль) в качестве разделителя кадров. При использовании нуля в качестве разделителя, алгоритм заменяет каждый нулевой байт в данных ненулевым значением, так что нулевые байты не могут присутствовать в теле закодированного кадра и не могут быть ошибочно приняты за границы кадра.

Вставка байтов (англ. Byte stuffing) — это процесс, преобразующий последовательность байтов данных, которые могут содержать «недопустимые» или «зарезервированные» значения (например, разделитель пакетов), в потенциально более длинную последовательность, не содержащую таких значений. Дополнительная длина преобразованной последовательности называется избыточностью алгоритма. Например, HDLC-кадрирование, используемое в PPP (см. RFC 1662 § 4.2), имеет среднюю избыточность менее 1%, но в худшем случае избыточность достигает 100%, удваивая размер входных данных.

Алгоритм COBS, напротив, строго ограничивает избыточность. Минимальная избыточность составляет 1 байт, а максимальная — ⌈n/254⌉ байта для n байтов данных (один байт на каждые 254 байта, округляя вверх). Благодаря этому время передачи закодированной последовательности байтов становится предсказуемым, что делает COBS полезным для приложений реального времени, где важна минимизация джиттера. Алгоритм отличается низкой вычислительной сложностью, а его средняя избыточность ниже, чем у других алгоритмов однозначного кадрирования, таких как HDLC.^[1]

Когда пакетированные данные передаются по любому последовательному каналу, необходим протокол для разграничения кадров / пакетов. Это делается с помощью маркера кадров, специальной бит-последовательности или символьного значения, которое указывает, где расположены границы между пакетами. Замена данных — это процесс, который преобразует пакеты данных перед передачей, чтобы устранить все вхождения разделителей кадров, таким образом при обнаружении разделителя приемником можно гарантировать, что разделитель указывает на границу между пакетами.

Алгоритм COBS преобразует произвольную строку байтов в диапазоне [0,255] в байты в диапазоне [1,255]. После устранения всех нулевых байтов из данных, нулевое значение может использоваться для однозначного обозначения конца преобразованных данных. Это делается путем добавления нулевых байтов в преобразованные данные, таким образом формируя пакет, состоящий из COBS-кодированных данных (полезной нагрузки) и нулевых байт, позволяющих однозначно обозначить начало и конец полезной нагрузки.

(Любые другие значения байта могут быть зарезервированы в качестве разделителя пакетов, использование нуля упрощает описание.)

Существует два способа описания процесса кодирования COBS:

Описание с префиксным блоком

Для кодирования данных сначала добавьте нулевой байт, затем разбейте данные на группы из 254 ненулевых байтов или 0–253 ненулевых байтов, завершающихся нулевым байтом. Благодаря добавлению нулевого байта это всегда возможно.

Закодируйте каждую группу, удалив завершающий нулевой байт (если он есть) и добавив в начало количество ненулевых байтов плюс один. Таким образом, каждая закодированная группа имеет тот же размер, что и исходная, за исключением случаев, когда 254 ненулевых байта кодируются в 255 байтов с добавлением заголовочного байта 255.

Если пакет заканчивается группой из 254 ненулевых байтов, добавление завершающего нулевого байта не требуется. Это позволяет сэкономить один байт в некоторых случаях.

Описание со связным списком

Сначала вставьте нулевой байт в начале пакета и после каждых 254 ненулевых байтов. Такая кодировка очевидно обратима. Нет необходимости вставлять нулевой байт в конце пакета, если он заканчивается ровно 254 ненулевыми байтами.

Затем замените каждый нулевой байт смещением к следующему нулевому байту или к концу пакета. Благодаря добавленным на первом этапе нулям каждое смещение гарантированно не превышает 255.

Эти примеры показывают кодирование различных последовательностей данных алгоритмом COBS. В примерах, все байты выражаются в виде шестнадцатеричных значений, и закодированные данные сопровождаются текстовым форматированием для иллюстрации различных особенностей:

• Жирный указывает на байт данных, который не изменился при кодировании. Все ненулевые байты остаются неизменными.
• Зеленый цвет указывает на нулевой байт данных, который был заменён при кодировании. Все нулевые байты заменяются смещением к следующему нулевому байту (т.е. 1 плюс количество последующих ненулевых байтов).
• Красный — это байт заголовка группы, содержащий смещение к следующей группе, но не соответствующий байту данных. Такие байты появляются в начале каждого закодированного пакета и после каждой группы из 254 ненулевых байтов.
• Синий нулевой байт появляется в конце каждого пакета, чтобы указать на конец пакета. Этот байт-разделитель не является частью алгоритма COBS, а добавляется дополнительно для кадрирования.

Ниже представлена схема, на примере 3 из вышеприведенной таблицы, чтобы показать, как каждый изменённый байт данных находится, и как он трактуется в качестве байта данных или байта конца кадра.

   [OHB]                                : Служебный байт - начало кадра (Overhead Byte)
     3+ -------------->|                : Указывает на относительное расположение первого нулевого символа
                       2+-------->|     : Это нулевой байт данных, указывающий на следующий нулевой символ
                                  [EOP] : Расположение нулевого символа конца пакета (End-of-packet).
     0     1     2     3     4    5     : Индекс байта
     03    11    22    02    33   00    : Кадр данных COBS 
           11    22    00    33         : Извлечённые данные
     
OHB = Overhead Byte (Указывает на следующий нулевой символ)
EOP = End Of Packet

Примеры с 7 по 10 показывают, как издержки варьируется в зависимости от данных, закодированных для длин пакетов 255 или больше.

Следующий код реализует COBS кодер и декодер на языке программирования Си:

/*
 * StuffData byte stuffs "length" bytes of data
 * at the location pointed to by "ptr", writing
 * the output to the location pointed to by "dst".
 *
 * Returns the length of the encoded data.
 */
#include <stdint.h>
#include <stddef.h>

#define StartBlock()	(code_ptr = dst++, code = 1)
#define FinishBlock()	(*code_ptr = code)

size_t StuffData(const uint8_t *ptr, size_t length, uint8_t *dst)
{
	const uint8_t *start = dst, *end = ptr + length;
	uint8_t code, *code_ptr; /* Where to insert the leading count */

	StartBlock();
	while (ptr < end) {
		if (code != 0xFF) {
			uint8_t c = *ptr++;
			if (c != 0) {
				*dst++ = c;
				code++;
				continue;
			}
		}
		FinishBlock();
		StartBlock();
	}
	FinishBlock();
	return dst - start;
}

/*
 * UnStuffData decodes "length" bytes of data at
 * the location pointed to by "ptr", writing the
 * output to the location pointed to by "dst".
 *
 * Returns the length of the decoded data
 * (which is guaranteed to be <= length).
 */
size_t UnStuffData(const uint8_t *ptr, size_t length, uint8_t *dst)
{
	const uint8_t *start = dst, *end = ptr + length;
	uint8_t code = 0xFF, copy = 0;

	for (; ptr < end; copy--) {
		if (copy != 0) {
			*dst++ = *ptr++;
		} else {
			if (code != 0xFF)
				*dst++ = 0;
			copy = code = *ptr++;
			if (code == 0)
				break; /* Source length too long */
		}
	}
	return dst - start;
}

• Реализация Python
• Альтернативная реализация C
• Другая реализация на C
• Еще одна реализация на C
• Уменьшенный COBS (COBS/R)
• Патент с описанием схемы с аналогичным результатом, но использующей другой метод