Вставка байтов с фиксированной избыточностью
 | Этот перевод статьи с другого языка требует улучшения (см. Рекомендации по переводу). |
Редактирование: Вставка байтов с фиксированной избыточностью (COBS) — это алгоритм кодирования, адаптированный для байтовых данных. COBS даёт эффективное, надежное, однозначное разделение пакетов на кадры независимо от их содержимого. Алгоритм использует зарезервированное значение (обычно ноль) в качестве разделителя кадров. При использовании нуля в качестве разделителя, алгоритм заменяет каждый нулевой байт в данных ненулевым значением, так что нулевые байты не могут присутствовать в теле закодированного кадра и не могут быть ошибочно приняты за границы кадра.
Вставка байтов (Byte stuffing) — это процесс, который преобразует последовательность байтов данных, которые могут содержать «некорректные» или «зарезервированные» значения (такие как разделитель кадров) в потенциально более длинную последовательность, которая не содержит этих значений. Добавочная длина преобразуемой последовательности обычно называется избыточностью алгоритма. Алгоритм COBS ограничивает избыточность для худшего случая входных данных в минимум один байт и максимум [n/254] байта (один байт из 254, с округлением в большую сторону). Следовательно, время для передачи кодированных байтов последовательности является предсказуемым (по верхней границе), что делает COBS полезным для приложений реального времени, в которых может быть проблематичен джиттер. Алгоритм обладает невысокой вычислительной сложностью и средняя избыточность довольно низкая по сравнению с другими алгоритмами однозначного кадрирования.[1][2]
Однако, алгоритм COBS требует наличия буфера данных, размером не менее 254 байт, для просмотра вперед. Перед передачей первого байта, необходимо знать позицию первого нулевого байта (если таковые имеются) в следующих 254 байтах.
Кадрирование пакетов и замена данных
[править | править код]Когда пакетированные данные передаются по любому последовательному каналу, необходим протокол для разграничения кадров / пакетов. Это делается с помощью маркера кадров, специальной бит-последовательности или символьного значения, которое указывает, где расположены границы между пакетами. Замена данных — это процесс, который преобразует пакеты данных перед передачей, чтобы устранить все вхождения разделителей кадров, таким образом при обнаружении разделителя приемником можно гарантировать, что разделитель указывает на границу между пакетами.
Алгоритм COBS преобразует произвольную строку байтов в диапазоне [0,255] в байты в диапазоне [1,255]. После устранения всех нулевых байтов из данных, нулевое значение может использоваться для однозначного обозначения конца преобразованных данных. Это делается путем добавления нулевых байтов в преобразованные данные, таким образом формируя пакет, состоящий из COBS-кодированных данных (полезной нагрузки) и нулевых байт, позволяющих однозначно обозначить начало и конец полезной нагрузки.
(Любые другие значения байта могут быть зарезервированы в качестве разделителя пакетов, использование нуля упрощает описание.)
Существует два способа описания процесса кодирования COBS:
- Описание блока с префиксом
- Для кодирования некоторых байтов, сначала добавить нулевой байт, затем разбить их на группы из 254 ненулевых байт, или 0-253 ненулевой байт, завершающиеся нулевым байтом. Из-за добавления нулевого байта, это всегда возможно.
- Кодировать каждую группу удаляя завершающий нулевой байт (если таковые имеются) и добавляя в начало количество ненулевых байт, плюс один. Таким образом, каждая закодированная группа одинаковый размер с исходной, за исключением того, что группа в 254 ненулевых байт кодируются в 255 байт с заголовочным байтом 255.
- Как особое исключение, если пакет заканчивается группой 254 ненулевых байт, не нужно добавлять завершающий нулевой байт. Это экономит один байт в некоторых ситуациях.
- Описание связным списком
- Во-первых, вставить нулевой байт в начале пакета, и после каждых 254 ненулевой байт. Такая кодировка является, очевидно, обратимой. Нет необходимости вставлять нулевой байт в конце пакета, если до конца ровно 254 ненулевых байт.
- Во-вторых, заменить каждый нулевой байт смещением к следующему нулевому байту, или к концу пакета. Из-за лишних нулей, добавленных на первом этапе, каждое смещение гарантировано не более 255.
Примеры кодирования
[править | править код]Эти примеры показывают кодирование различных последовательностей данных алгоритмом COBS. В примерах, все байты выражаются в виде шестнадцатеричных значений, и закодированные данные показываются форматированием текста, иллюстрирующим различные функции:
- Жирный указывает на байт данных, который не был изменён путем кодирования. Все ненулевые байты данных остаются неизменными.
- Зеленый цвет указывает на нулевой байт данных, который был изменён путем кодирования. Все нулевые байты данных будут заменены при кодировании смещением к следующему нулевому байту (то есть 1+ число последующих ненулевых байт). Это фактически указатель на следующий байт пакета, который требует обработки: если адресуемый байт является ненулевым, то это следующие группы заголовка байт данных байт, который указывает на следующий байт, требующий интерпретации; если адресуемый байт равен нулю, то это конец пакета.
- Красный — это байт, который является также байтом заголовка группы, содержащий смещение на следующую группу, но не соответствует байту данных. Они появляются в двух местах: в начале каждого кодированного пакета, и после каждой группы 254 ненулевых байт.
- синий нулевой байт появляется в конце каждого пакета, чтобы указать на конец пакета данных приемнику. Этот байт-разделитель пакетов не является частью COBS последовательности; это дополнительный кадрирующий байт, который добавляется в кодированных выходных данных.
| Example | Некодированные данные (hex) | Кодирование COBS (hex) |
|---|---|---|
| 1 | 00 | 01 01 00 |
| 2 | 00 00 | 01 01 01 00 |
| 3 | 11 22 00 33 | 03 11 22 02 33 00 |
| 4 | 11 22 33 44 | 05 11 22 33 44 00 |
| 5 | 11 00 00 00 | 02 11 01 01 01 00 |
| 6 | 01 02 03 ... FD FE | FF 01 02 03 ... FD FE 00 |
| 7 | 00 01 02 ... FC FD FE | 01 FF 01 02 ... FC FD FE 00 |
| 8 | 01 02 03 ... FD FE FF | FF 01 02 03 ... FD FE 02 FF 00 |
| 9 | 02 03 04 ... FE FF 00 | FF 02 03 04 ... FE FF 01 01 00 |
| 10 | 03 04 05 ... FF 00 01 | FE 03 04 05 ... FF 02 01 00 |
Ниже представлена схема, на примере 3 из вышеприведенной таблицы, чтобы показать, как каждый изменённый байт данных находится, и как он трактуется в качестве байта данных или байта конца кадра.
[OHB] : Overhead byte (Start of frame)
3+ -------------->| : Points to relative location of first zero symbol
2+-------->| : Is a zero data byte, pointing to next zero symbol
[EOP] : Location of end-of-packet zero symbol.
0 1 2 3 4 5 : Byte Position
03 11 22 02 33 00 : COBS Data Frame
11 22 00 33 : Extracted Data
OHB = Overhead Byte (Points to next zero symbol)
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;
}
Примечания
[править | править код]- ↑ Cheshire, Stuart. Consistent Overhead Byte Stuffing (англ.) // IEEE/ACM Transactions on Networking[англ.] : journal. — 1999. — April (vol. 7). — doi:10.1109/90.769765. Архивировано 27 августа 2018 года.
- ↑ Cheshire, Stuart (17 November 1997). Consistent Overhead Byte Stuffing (PDF). ACM SIGCOMM '97. Cannes. Архивировано из оригинала (PDF) 31 декабря 2010. Дата обращения: 23 ноября 2010.