Последовательное заполнение служебных байтов - Consistent Overhead Byte Stuffing - Wikipedia
Последовательное заполнение служебных байтов (COBS) является алгоритм для кодирования байтов данных, что приводит к эффективному, надежному, однозначному кадрирование пакета независимо от содержимого пакета, что упрощает для принимающих приложений восстановление после искаженных пакетов. Он использует конкретное значение байта, обычно ноль, чтобы служить пакет разделитель (специальное значение, указывающее границу между пакетами). Когда в качестве разделителя используется ноль, алгоритм заменяет каждый нулевой байт данных ненулевым значением, чтобы в пакете не появлялись нулевые байты данных и, таким образом, их неправильно интерпретировали как границы пакета.
Байтовая начинка - это процесс, преобразующий последовательность байтов данных, которые могут содержать «недопустимые» или «зарезервированные» значения (например, разделитель пакетов), в потенциально более длинную последовательность, которая не содержит вхождений этих значений. Дополнительная длина преобразованной последовательности обычно упоминается как накладные расходы алгоритма. Алгоритм COBS жестко ограничивает накладные расходы наихудшего случая, ограничивая их минимум одним байтом и максимум ⌈п/ 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. В примерах все байты выражаются как шестнадцатеричный значения, а закодированные данные показаны с форматированием текста для иллюстрации различных функций:
- Смелый указывает на байт данных, который не был изменен при кодировании. Все ненулевые байты данных остаются неизменными.
- Зеленый указывает нулевой байт данных, который был изменен кодированием. Все нулевые байты данных заменяются во время кодирования смещением к следующему нулевому байту (т. Е. Один плюс количество следующих за ним ненулевых байтов). По сути, это указатель на следующий байт пакета, который требует интерпретации: если адресный байт не равен нулю, то это следующий байт заголовка группы нулевой байт данных это указывает на следующий байт, требующий интерпретации; если адресный байт равен нулю, то это конец пакета.
- красный это служебный байт, который также является байтом заголовка группы, содержащим смещение к следующей группе, но не соответствует байту данных. Они появляются в двух местах: в начале каждого закодированного пакета и после каждой группы из 254 ненулевых байтов.
- А синий нулевой байт появляется в конце каждого пакета, чтобы указать приемнику данных конец пакета. Этот байт-ограничитель пакетов не является частью собственно 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 byte заполняет "длину" байтов данных * в месте, обозначенном "ptr", напишите * вывод в место, на которое указывает "dst". * * Возвращает длину закодированных данных. */#включают <stdint.h>#включают <stddef.h>size_t StuffData(const uint8_t *ptr, size_t длина, uint8_t *dst){ uint8_t *Начните = dst; uint8_t *code_ptr = dst++; *code_ptr = 1; пока (длина--) { если (*ptr) { *dst++ = *ptr++; *code_ptr += 1; } еще { code_ptr = dst++; *code_ptr = 1; ptr++; } если (*code_ptr == 0xFF && длина > 0) { code_ptr = dst++; *code_ptr = 1; } } *dst++ = 0; возвращаться dst - Начните;}/* * UnStuffData декодирует байты "длины" данных в * место, на которое указывает "ptr", написание * вывод в место, указанное "dst". * * Возвращает длину декодированных данных * (что гарантированно будет <= length). */size_t UnStuffData(const uint8_t *ptr, size_t длина, uint8_t *dst){ const uint8_t *Начните = dst, *конец = ptr + длина; uint8_t код = 0xFF, копировать = 0; bool флаг = истинный; за (; ptr < конец; копировать--) { если (копировать != 0) { флаг = ложный; *dst++ = *ptr++; } еще { если (код != 0xFF) { флаг = истинный; *dst++ = 0; } копировать = код = *ptr++; если (код == 0) { перемена; } } } если (флаг) --dst; возвращаться dst - Начните;}Рекомендации
- ^ Чешир, Стюарт; Бейкер, Мэри (апрель 1999). «Последовательное заполнение байтами служебных данных» (PDF). Транзакции IEEE / ACM в сети. 7 (2): 159–172. CiteSeerX 10.1.1.108.3143. Дои:10.1109/90.769765. Получено 30 ноября, 2015.
- ^ Чешир, Стюарт; Бейкер, Мэри (17 ноября 1997 г.). Последовательное заполнение служебных байтов (PDF). ACM SIGCOMM '97. Канны. Получено 23 ноября, 2010.