Войти
Согласованное заполнение байтов служебных данных (COBS ) - это алгоритм для кодирования байтов данных, который приводит к эффективному, надежному и однозначному кадрированию пакета независимо от содержимого пакета, что упрощает для принимающих приложений восстановление после искаженных пакетов. Он использует конкретное значение байта, обычно ноль, чтобы служить разделителем пакета (специальное значение, которое указывает границу между пакетами). Когда ноль используется в качестве разделителя, алгоритм заменяет каждый нулевой байт данных ненулевым значением, чтобы в пакете не появлялись нулевые байты данных, и, таким образом, они были неверно интерпретированы как границы пакета.
Заполнение байтов - это процесс, который преобразует последовательность байтов данных, которые могут содержать «недопустимые» или «зарезервированные» значения (например, разделитель пакетов), в потенциально более длинную последовательность, которая не содержит повторений этих значений. Дополнительная длина преобразованной последовательности обычно упоминается как накладные расходы алгоритма. Алгоритм COBS жестко ограничивает накладные расходы наихудшего случая, ограничивая их минимум одним байтом и максимум ⌈n / 254⌉ байтами (один байт из 254, с округлением в большую сторону). Следовательно, время передачи закодированной последовательности байтов очень предсказуемо, что делает COBS полезным для приложений реального времени, в которых дрожание может быть проблематичным. Алгоритм является недорогим в вычислительном отношении, а его средние накладные расходы низки по сравнению с другими алгоритмами однозначного кадрирования.
COBS, однако, требует до 254 байтов опережающего просмотра. Перед передачей своего первого байта ему необходимо знать позицию первого нулевого байта (если есть) в следующих 254 байтах.
Когда пакетированные данные отправляются через любой последовательный носитель, требуется некоторый протокол для разграничения границ пакета. Это делается с помощью маркера кадрирования, специальной битовой последовательности или символьного значения, которое указывает, где проходят границы между пакетами. Вставка данных - это процесс, который преобразует пакетные данные перед передачей, чтобы исключить все вхождения маркера кадрирования, так что, когда получатель обнаруживает маркер, он может быть уверен, что маркер указывает границу между пакетами.
COBS преобразует произвольную строку байтов в диапазоне [0,255] в байты в диапазоне [1,255]. После удаления всех нулевых байтов из данных, нулевой байт теперь можно использовать для однозначной отметки конца преобразованных данных. Это делается путем добавления нулевого байта к преобразованным данным, таким образом формируя пакет, состоящий из данных в кодировке COBS (полезная нагрузка ), чтобы однозначно обозначить конец пакета.
(Любое другое значение байта может быть зарезервировано в качестве разделителя пакетов, но использование нуля упрощает описание.)
Существует два эквивалентных способа описания процесса кодирования COBS:
Эти примеры показывают, как различные последовательности данных будут кодироваться алгоритмом COBS. В примерах все байты выражены как шестнадцатеричные значения, а закодированные данные показаны с текстовым форматированием, чтобы проиллюстрировать различные функции:
| Пример | Незакодированные данные (шестнадцатеричный) | Закодированные с помощью COBS (шестнадцатеричный) |
|---|---|---|
| 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]: служебный байт (начало кадра) 3+ -------------->| : Указывает на относительное расположение первого символа нуля 2 + -------->| : Нулевой байт данных, указывающий на следующий нулевой символ [EOP]: расположение нулевого символа конца пакета. 0 1 2 3 4 5: Позиция байта 03 11 22 02 33 00: Кадр данных COBS 11 22 00 33: Извлеченные данные OHB = Байт заголовка (указывает на следующий нулевой символ) EOP = Конец пакета
Примеры 7 по 10 показывают, как служебные данные меняются в зависимости от кодируемых данных для пакетов длиной 255 или более.
Следующий код реализует кодировщик и декодер COBS на языке программирования C:
/ * * Байт StuffData заполняет байты «длины» * в месте, на которое указывает «ptr», записывая * вывод в место, указанное «dst». * * Возвращает длину закодированных данных. * / #include#include size_t StuffData (const uint8_t * ptr, size_t length, uint8_t * dst) {uint8_t * start = dst; uint8_t code = 1, * code_ptr = dst ++; / * Куда вставить начальный счетчик * / while (length--) {if (* ptr) / * Входной байт не равен нулю * / * dst ++ = * ptr, ++ code; if (! * ptr ++ || code == 0xFF) / * Ввод нулевой или полный блок * / * code_ptr = code, code = 1, code_ptr = dst ++; } * code_ptr = код; / * Окончательный код * / return dst - start; } / * * UnStuffData декодирует байты «длины» в * месте, на которое указывает «ptr», записывая * вывод в место, на которое указывает «dst». * * Возвращает длину декодированных данных * (которая гарантированно будет <= 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; }
