Вставка байтов с фиксированной избыточностью (COBS)

aquaratixc Dlang, Рецепты

Вставка байтов с фиксированной избыточностью (COBS) — это один из алгоритмов кодирования байтов данных, который приводит к эффективному, надежному и однозначному кадрированию пакетов независимо от их содержимого, что упрощает для принимающих приложений восстановление искаженных пакетов. Он использует конкретное значение байта, обычно ноль, в качестве разделителя пакетов. Когда в качестве разделителя используется ноль, алгоритм заменяет каждый нулевой байт данных ненулевым значением, чтобы в пакете не появлялись нулевые байты данных и, таким образом, не случалось неверной интерпретации конца пакета.

Заполнение байтов — это процесс, который преобразует последовательность байтов данных, которые могут содержать недопустимые или зарезервированные значения, такие как разделитель пакетов, в потенциально более длинную последовательность, которая не содержит вхождений этих значений. Дополнительная длина преобразованной последовательности обычно называется накладными расходами алгоритма. Алгоритм COBS жестко ограничивает накладные расходы для наихудшего случая, ограничивая их минимум одним байтом и максимум n/254 байтов на один байт из 254 с округлением в большую сторону. Следовательно, время передачи закодированной последовательности байтов очень предсказуемо, что делает COBS полезным для приложений реального времени. Алгоритм является недорогим в вычислительном отношении, а его средние накладные расходы низки по сравнению с другими однозначными алгоритмами кадрирования. COBS, однако, требует до 254 байтов опережающего просмотра. То есть перед передачей своего первого байта ему необходимо знать позицию первого нулевого байта, если таковой имеется, в следующих 254 байтах.

Ниже представлена реализация COBS кодера/декодера портированная с C, с врапперами на D.

extern(C) size_t StuffData(ubyte* ptr, size_t length, ubyte* dst)
{
    ubyte* start = dst;
    ubyte* end = ptr + length;
    ubyte code;
    ubyte* code_ptr;

    code_ptr = dst++; code = 1;
    
    while (ptr < end) {
        if (code != 0xFF) {
            ubyte c = *ptr++;
            if (c != 0) {
                *dst++ = c;
                code++;
                continue;
            }
        }
        
        *code_ptr = code;
        code_ptr = dst++; code = 1;
    }
    
    *code_ptr = code;
    return dst - start;
}

auto StuffData(ubyte[] data)
{
    ubyte[] stuffedData = new ubyte[data.length + 1];
    
    StuffData(data.ptr, data.length, stuffedData.ptr);
    
    return stuffedData;
}

extern(C) size_t UnStuffData(ubyte* ptr, size_t length, ubyte* dst)
{
    ubyte* start = dst, end = ptr + length;
    ubyte 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; 
        }
    }
    return dst - start;
}

auto UnStuffData(ubyte[] data)
{
    ubyte[] unstuffedData = new ubyte[data.length - 1];
    
    UnStuffData(data.ptr, data.length, unstuffedData.ptr);
    
    return unstuffedData;
}

void main()
{
    ubyte[] dw = [11, 22, 00, 33];
    
    StuffData(dw).writeln;
    UnStuffData(StuffData(dw)).writeln;
}

Дополнительную информацию о COBS можно найти на следующих ресурсах:

Добавить комментарий