Участник:Alexraynepe196/Связная подмена дополнительным байтом (Consistent Overhead Byte Stuffing)
Связная подмена дополнительным байтом (COBS)- это алгоритм для кодирования байтовых данных, дающий эффективное, надежное, однозначное кадрирование/фрейминг пакетов независимо от содержимого пакета, что делает его простым для восстановления приемника на искаженных пакеты. Он использует конкретное значение байта, обычно ноль, в качестве разделителя пакетов (специальное значение, указывающее границы между пакетами). Когда ноль используется в качестве разделителя, алгоритм заменяет каждый нулевой байт данных ненулевым значением, так что нули не появятся в пакете и, чтобы не быть истолкованными как границы пакетов.
Подмена байт - это процесс, который преобразует последовательность байтов данных, которые могут содержать "нелегальные" или "зарезервированные" значения (такие как разделитель пакетов) в потенциально более длинную последовательность, которая не содержит этих значений. Сверх-длина преобразуемой последовательности обычно называется издержкой алгоритма. 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 (April 1999). "Consistent Overhead Byte Stuffing" (PDF). IEEE/ACM Transactions on Networking. 7. doi:10.1109/90.769765. Дата обращения: 30 ноября 2015.
- ↑ Cheshire, Stuart (17 November 1997). Consistent Overhead Byte Stuffing (PDF). ACM SIGCOMM '97. Cannes. Дата обращения: 23 ноября 2010.
Внешние ссылки
[править | править код]- Реализация Python
- Альтернативная реализация с
- Другая реализация на C
- Еще одна реализация на C
- Последовательный байт вброс—уменьшается (ПОЧАТКОВ/Р)
- Патент с описанием схема с аналогичным результатом, но используя другой метод
[[Категория:Кодировки]]