Согласованная вставка байтов служебных данных ( 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. В примерах все байты представлены в виде шестнадцатеричных значений, а закодированные данные показаны с текстовым форматированием для иллюстрации различных функций:
- Жирным шрифтом выделен байт данных, который не был изменен при кодировании. Все ненулевые байты данных остаются неизменными.
- Зеленый цвет указывает на нулевой байт данных, который был изменен при кодировании. Все нулевые байты данных заменяются во время кодирования смещением к следующему нулевому байту (т. Е. Один плюс количество последующих ненулевых байтов). Фактически это указатель на следующий байт пакета, который требует интерпретации: если адресованный байт не равен нулю, то следующий байт данных нулевого байта заголовка группы указывает на следующий байт, требующий интерпретации; если адресный байт равен нулю, то это конец пакета .
- Красный - это служебный байт, который также является байтом заголовка группы, содержащим смещение к следующей группе, но не соответствует байту данных. Они появляются в двух местах: в начале каждого закодированного пакета и после каждой группы из 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:
#include #include / ** COBS кодирует данные в буфер @param data Указатель на входные данные для кодирования @param length Число байтов для кодирования @param buffer Указатель на закодированный выходной буфер @return Длина закодированного буфера в байтах @note Не выводит байт-разделитель * / size_t cobsEncode ( const void * data , size_t length , uint8_t * buffer ) { assert ( data && buffer );uint8_t * кодировать = буфер ; // Закодированный байтовый указатель uint8_t * codep = encode ++ ; // Вывести указатель на код uint8_t code = 1 ; // Кодовое значениеfor ( const uint8_t * byte = ( const uint8_t * ) data ; length - ; ++ byte ) { if ( * byte ) // Байт не равен нулю, записываем его * encode ++ = * byte , ++ code ;if ( ! * byte || code == 0xff ) // Ввод равен нулю или блок завершен, перезапустите { * codep = code , code = 1 , codep = encode ; если ( ! * байт || длина ) ++ кодировать ; } } * codep = код ; // Записываем окончательное значение кода код возврата - буфер ; }/ ** COBS декодируют данные из буфера @param buffer Указатель на закодированные входные байты @param length Число байтов для декодирования @param data Указатель на декодированные выходные данные @return Число байтов, успешно декодированных @note Останавливает декодирование, если найден байт-разделитель * / size_t cobsDecode ( const uint8_t * буфер , размер size_t , void * data ) { assert ( buffer && data ); const uint8_t * байт = буфер ; // кодированного входного байта указателя uint8_t * расшифровывает = ( uint8_t * ) данные ; // Декодированный выходной байтовый указательfor ( uint8_t code = 0xff , block = 0 ; byte < buffer + length ; - block ) { if ( block ) // Декодировать байт блока * decode ++ = * byte ++ ; else { if ( code ! = 0xff ) // Зашифрованный ноль, записываем его * decode ++ = 0 ; блок = код = * байт ++ ; // Длина следующего блока if ( code == 0x00 ) // Найден код разделителя break ; } }Возвращение декодирования - ( uint8_t * ) данные ; }
Смотрите также
Рекомендации
- ^ Чешир, Стюарт; Бейкер, Мэри (апрель 1999). «Последовательная вставка байтов в служебные данные» (PDF) . Транзакции IEEE / ACM в сети . 7 (2): 159–172. CiteSeerX 10.1.1.108.3143 . DOI : 10.1109 / 90.769765 . Проверено 30 ноября 2015 года .
- ^ Чешир, Стюарт; Бейкер, Мэри (17 ноября 1997 г.). Последовательная вставка байтов в служебные данные (PDF) . ACM SIGCOMM '97. Канны . Проверено 23 ноября 2010 года .