Последовательное заполнение служебных байтов
Согласованное заполнение служебных байтов ( COBS ) — это алгоритм кодирования байтов данных, который приводит к эффективному, надежному и однозначному кадрированию пакетов независимо от их содержимого, что позволяет принимающим приложениям легко восстанавливаться после некорректных пакетов. Он использует определенное значение байта, обычно нулевое, в качестве пакетов разделителя (специальное значение, указывающее границу между пакетами). Когда в качестве разделителя используется ноль, алгоритм заменяет каждый нулевой байт данных ненулевым значением, чтобы в пакете не появлялось нулевых байтов данных и, таким образом, они были ошибочно интерпретированы как границы пакета.
Вставка байтов — это процесс, который преобразует последовательность байтов данных, которые могут содержать «недопустимые» или «зарезервированные» значения (например, разделитель пакетов), в потенциально более длинную последовательность, не содержащую вхождений этих значений. Дополнительную длину преобразованной последовательности обычно называют накладными расходами алгоритма. Кадрирование HDLC — хорошо известный пример, используемый, в частности, в PPP (см. RFC 1662 § 4.2 ). Хотя кадрирование HDLC имеет накладные расходы <1% в среднем случае, в худшем случае накладные расходы составляют 100%; для входных данных, которые полностью состоят из байтов, требующих экранирования, вставка байтов HDLC удвоит размер входных данных.
Алгоритм COBS, с другой стороны, жестко ограничивает накладные расходы в худшем случае. COBS требует минимум 1 байта служебных данных и максимум ⌈n / 254⌉ байт для n байтов данных (один байт из 254, округленный вверх). Следовательно, время передачи закодированной последовательности байтов очень предсказуемо, что делает COBS полезным для приложений реального времени, в которых дрожание может быть проблематичным. Алгоритм не требует больших вычислительных затрат, и, помимо желательных накладных расходов в худшем случае , его средние накладные расходы также низки по сравнению с другими алгоритмами однозначного кадрирования, такими как HDLC. [1] [2] Однако COBS требует до 254 байтов опережающего просмотра . Прежде чем передать свой первый байт, ему необходимо знать позицию первого нулевого байта (если он есть) в следующих 254 байтах.
1999 года В Интернет-проекте предлагалось стандартизировать COBS в качестве альтернативы кадрированию HDLC в PPP из-за вышеупомянутых плохих накладных расходов при кадрировании HDLC в наихудшем случае. [3]
Формирование и начинка пакетов
[ редактировать ]Когда пакетированные данные передаются по любой последовательной среде, некоторый протокол требуется для разграничения границ пакета. Это делается с помощью маркера кадра, специальной битовой последовательности или символьного значения, которое указывает, где проходят границы между пакетами. Заполнение данных — это процесс, который преобразует пакетные данные перед передачей для устранения всех вхождений маркера кадра, чтобы, когда получатель обнаруживает маркер, он мог быть уверен, что этот маркер указывает границу между пакетами.
COBS преобразует произвольную строку байтов в диапазоне [0,255] в байты в диапазоне [1255]. Удалив из данных все нулевые байты, теперь нулевой байт можно использовать для однозначного обозначения конца преобразованных данных. Это делается путем добавления нулевого байта к преобразованным данным, таким образом формируя пакет, состоящий из данных, закодированных в COBS ( полезная нагрузка ), чтобы однозначно отметить конец пакета.
(Любое другое значение байта может быть зарезервировано в качестве разделителя пакетов, но использование нуля упрощает описание.)
Существует два эквивалентных способа описания процесса кодирования COBS:
- Описание префиксного блока
- Чтобы закодировать некоторые байты, сначала добавьте нулевой байт, а затем разбейте их на группы по 254 ненулевых байта или по 0–253 ненулевых байта, за которыми следует нулевой байт. Из-за добавленного нулевого байта это всегда возможно.
- Закодируйте каждую группу, удалив конечный нулевой байт (если он есть) и добавив в начале количество ненулевых байтов плюс один. Таким образом, каждая закодированная группа имеет тот же размер, что и исходная, за исключением того, что 254 ненулевых байта кодируются в 255 байтов путем добавления байта со значением 255.
- В качестве особого исключения, если пакет заканчивается группой из 254 ненулевых байтов, нет необходимости добавлять завершающий нулевой байт. В некоторых ситуациях это экономит один байт.
- Описание связанного списка
- Сначала вставьте нулевой байт в начале пакета и после каждого запуска 254 ненулевых байтов. Очевидно, что это кодирование обратимо. Нет необходимости вставлять нулевой байт в конец пакета, если он заканчивается ровно 254 ненулевыми байтами.
- Во-вторых, замените каждый нулевой байт смещением до следующего нулевого байта или конца пакета. Из-за дополнительных нулей, добавленных на первом этапе, каждое смещение гарантированно будет не более 255.
Примеры кодирования
[ редактировать ]Эти примеры показывают, как различные последовательности данных будут кодироваться алгоритмом COBS. В примерах все байты представлены в виде шестнадцатеричных значений, а закодированные данные показаны с форматированием текста для иллюстрации различных функций:
- Жирным шрифтом обозначен байт данных, который не был изменен при кодировании. Все ненулевые байты данных остаются неизменными.
- Зеленый цвет указывает на нулевой байт данных, который был изменен при кодировании. Все нулевые байты данных заменяются во время кодирования смещением до следующего нулевого байта (т.е. один плюс количество следующих за ним ненулевых байтов). По сути, это указатель на следующий байт пакета, который требует интерпретации: если адресованный байт ненулевой, то это следующий байт заголовка группы, нулевой байт данных , который указывает на следующий байт, требующий интерпретации; если адресованный байт равен нулю, то это конец пакета .
- Красный — это служебный байт, который также является байтом заголовка группы, содержащим смещение к следующей группе, но не соответствует байту данных. Они появляются в двух местах: в начале каждого закодированного пакета и после каждой группы из 254 ненулевых байтов.
- Синий нулевой байт появляется в конце каждого пакета , указывая получателю данных на конец пакета. Этот байт-разделитель пакетов не является частью собственно COBS; это дополнительный байт кадра, который добавляется к закодированному выводу.
| Пример | Некодированные данные (шестнадцатеричный) | Закодировано с помощью COBS (шестнадцатеричное) |
|---|---|---|
| 1 | 00 | 01 01 00 |
| 2 | 00 00 | 01 01 01 00 |
| 3 | 00 11 00 | 01 02 11 01 00 |
| 4 | 11 22 00 33 | 03 11 22 02 33 00 |
| 5 | 11 22 33 44 | 05 11 22 33 44 00 |
| 6 | 11 00 00 00 | 02 11 01 01 01 00 |
| 7 | 01 02 03 ... ФД ФЭ | ФФ 01 02 03 ... ФД ФЭ 00 |
| 8 | 00 01 02 ... ФК ФД ФЭ | 01 FF 01 02 ... FC FD FE 00 |
| 9 | 01 02 03 ... ФД ФФ ФФ | ФФ 01 02 03 ... ФД ФЭ 02 ФФ 00 |
| 10 | 02 03 04 ... ФЭ ФФ 00 | ФФ 02 03 04 ... ФФ ФФ 01 01 00 |
| 11 | 03 04 05 ... ФФ 00 01 | ФЭ 03 04 05 ... ФФ 02 01 00 |
Ниже приведена диаграмма с использованием примера 4 из приведенной выше таблицы, чтобы проиллюстрировать, как расположен каждый измененный байт данных и как он идентифицируется как байт данных или байт конца кадра.
[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 на языке программирования C:
#include <stddef.h>
#include <stdint.h>
#include <assert.h>
/** COBS encode data to buffer
@param data Pointer to input data to encode
@param length Number of bytes to encode
@param buffer Pointer to encoded output buffer
@return Encoded buffer length in bytes
@note Does not output delimiter byte
*/
size_t cobsEncode(const void *data, size_t length, uint8_t *buffer)
{
assert(data && buffer);
uint8_t *encode = buffer; // Encoded byte pointer
uint8_t *codep = encode++; // Output code pointer
uint8_t code = 1; // Code value
for (const uint8_t *byte = (const uint8_t *)data; length--; ++byte)
{
if (*byte) // Byte not zero, write it
*encode++ = *byte, ++code;
if (!*byte || code == 0xff) // Input is zero or block completed, restart
{
*codep = code, code = 1, codep = encode;
if (!*byte || length)
++encode;
}
}
*codep = code; // Write final code value
return (size_t)(encode - buffer);
}
/** COBS decode data from buffer
@param buffer Pointer to encoded input bytes
@param length Number of bytes to decode
@param data Pointer to decoded output data
@return Number of bytes successfully decoded
@note Stops decoding if delimiter byte is found
*/
size_t cobsDecode(const uint8_t *buffer, size_t length, void *data)
{
assert(buffer && data);
const uint8_t *byte = buffer; // Encoded input byte pointer
uint8_t *decode = (uint8_t *)data; // Decoded output byte pointer
for (uint8_t code = 0xff, block = 0; byte < buffer + length; --block)
{
if (block) // Decode block byte
*decode++ = *byte++;
else
{
block = *byte++; // Fetch the next block length
if (block && (code != 0xff)) // Encoded zero, write it unless it's delimiter.
*decode++ = 0;
code = block;
if (!code) // Delimiter code found
break;
}
}
return (size_t)(decode - (uint8_t *)data);
}
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Чешир, Стюарт ; Бейкер, Мэри (апрель 1999 г.). «Последовательное заполнение служебных байтов» (PDF) . Транзакции IEEE/ACM в сети . 7 (2): 159–172. CiteSeerX 10.1.1.108.3143 . дои : 10.1109/90.769765 . S2CID 47267776 . Проверено 30 ноября 2015 г.
- ^ Чешир, Стюарт ; Бейкер, Мэри (17 ноября 1997 г.). Согласованное заполнение служебных байтов (PDF) . ACM SIGCOMM '97. Канны . Проверено 23 ноября 2010 г.
- ^ Карлсон, Джеймс; Чешир, Стюарт ; Бейкер, Мэри (ноябрь 1997 г.). Согласованное заполнение служебных байтов PPP (COBS) . Идентификатор черновика-ietf-pppext-cobs-00.txt.