Relleno de bytes de sobrecarga consistente

El Consistent Overhead Byte Stuffing ( COBS ) es un algoritmo para codificar bytes de datos que da como resultado un encuadre de paquetes eficiente, confiable y sin ambigüedades independientemente del contenido del paquete, lo que facilita que las aplicaciones receptoras se recuperen de paquetes malformados. Emplea un valor de byte particular, generalmente cero, para que sirva como delimitador de paquetes (un valor especial que indica el límite entre paquetes). Cuando se utiliza cero como delimitador, el algoritmo reemplaza cada byte de datos cero con un valor distinto de cero para que no aparezcan bytes de datos cero en el paquete y, por lo tanto, se malinterpreten como límites de paquetes.

El relleno de bytes es un proceso que transforma una secuencia de bytes de datos que pueden contener valores "ilegales" o "reservados" (como el delimitador de paquetes) en una secuencia potencialmente más larga que no contiene ninguna ocurrencia de esos valores. La longitud adicional de la secuencia transformada se conoce normalmente como la sobrecarga del algoritmo. El entramado HDLC es un ejemplo bien conocido, utilizado particularmente en PPP (consulte RFC 1662 § 4.2). Aunque el entramado HDLC tiene una sobrecarga de <1% en el caso promedio , sufre de una sobrecarga muy pobre en el peor de los casos del 100%; para las entradas que consisten completamente en bytes que requieren escape, el relleno de bytes HDLC duplicará el tamaño de la entrada.

El algoritmo COBS, por otro lado, limita estrictamente la sobrecarga en el peor de los casos. COBS requiere un mínimo de 1 byte de sobrecarga y un máximo de ⌈ n /254⌉ bytes para n bytes de datos (un byte en 254, redondeado hacia arriba). En consecuencia, el tiempo para transmitir la secuencia de bytes codificada es altamente predecible, lo que hace que COBS sea útil para aplicaciones en tiempo real en las que el jitter puede ser problemático. El algoritmo es computacionalmente económico y, además de su deseable sobrecarga en el peor de los casos, su sobrecarga promedio también es baja en comparación con otros algoritmos de encuadre inequívocos como HDLC. ^{[1] [2]} Sin embargo, COBS requiere hasta 254 bytes de lookahead . Antes de transmitir su primer byte, necesita saber la posición del primer byte cero (si lo hay) en los siguientes 254 bytes.

Un borrador de Internet de 1999 propuso estandarizar COBS como una alternativa para el encuadre HDLC en PPP , debido a la sobrecarga en el peor de los casos antes mencionada del encuadre HDLC. ^[3]

Cuando se envían datos en paquetes a través de cualquier medio serial, se requiere algún protocolo para delimitar los límites de los paquetes. Esto se hace mediante un marcador de trama, una secuencia de bits especial o un valor de carácter que indica dónde se encuentran los límites entre los paquetes. El relleno de datos es el proceso que transforma los datos del paquete antes de la transmisión para eliminar todas las apariciones del marcador de trama, de modo que cuando el receptor detecte un marcador, pueda estar seguro de que el marcador indica un límite entre los paquetes.

COBS transforma una cadena arbitraria de bytes en el rango [0,255] en bytes en el rango [1,255]. Una vez eliminados todos los bytes cero de los datos, se puede utilizar un byte cero para marcar de forma inequívoca el final de los datos transformados. Esto se hace añadiendo un byte cero a los datos transformados, formando así un paquete que consta de los datos codificados con COBS (la carga útil ) para marcar de forma inequívoca el final del paquete.

(Se puede reservar cualquier otro valor de byte como delimitador de paquete, pero el uso de cero simplifica la descripción).

Hay dos formas equivalentes de describir el proceso de codificación COBS:

Descripción de bloque con prefijo

Para codificar algunos bytes, primero se añade un byte cero y luego se dividen en grupos de 254 bytes distintos de cero o de 0 a 253 bytes distintos de cero seguidos de un byte cero. Esto siempre es posible gracias al byte cero añadido.

Codifique cada grupo eliminando el byte cero final (si lo hay) y anteponiendo el número de bytes distintos de cero, más uno. De este modo, cada grupo codificado tiene el mismo tamaño que el original, excepto que 254 bytes distintos de cero se codifican en 255 bytes anteponiendo un byte de 255.

Como excepción especial, si un paquete termina con un grupo de 254 bytes distintos de cero, no es necesario agregar el byte cero final. Esto permite ahorrar un byte en algunas situaciones.

Descripción de lista enlazada

En primer lugar, inserte un byte cero al principio del paquete y después de cada serie de 254 bytes distintos de cero. Obviamente, esta codificación es reversible. No es necesario insertar un byte cero al final del paquete si termina exactamente con 254 bytes distintos de cero.

En segundo lugar, reemplace cada byte cero con el desplazamiento hasta el siguiente byte cero, o el final del paquete. Debido a los ceros adicionales agregados en el primer paso, se garantiza que cada desplazamiento sea como máximo 255.

Estos ejemplos muestran cómo se codificarían varias secuencias de datos mediante el algoritmo COBS. En los ejemplos, todos los bytes se expresan como valores hexadecimales y los datos codificados se muestran con formato de texto para ilustrar varias funciones:

• El texto en negrita indica un byte de datos que no se ha modificado mediante la codificación. Todos los bytes de datos distintos de cero permanecen inalterados.
• El color verde indica un byte de datos cero que se modificó mediante la codificación. Todos los bytes de datos cero se reemplazan durante la codificación por el desplazamiento hasta el siguiente byte cero (es decir, uno más el número de bytes distintos de cero que siguen). Es efectivamente un puntero al siguiente byte de paquete que requiere interpretación: si el byte direccionado no es cero, entonces es el siguiente byte de datos cero del encabezado de grupo el que apunta al siguiente byte que requiere interpretación; si el byte direccionado es cero, entonces es el final del paquete .
• El rojo es un byte de cabecera que también es un byte de encabezado de grupo que contiene un desplazamiento hacia un grupo siguiente, pero no corresponde a un byte de datos. Estos aparecen en dos lugares: al principio de cada paquete codificado y después de cada grupo de 254 bytes distintos de cero.
• Al final de cada paquete aparece un byte cero azul para indicar al receptor de datos que el paquete ha finalizado. Este byte delimitador de paquete no forma parte del COBS propiamente dicho; es un byte de encuadre adicional que se añade a la salida codificada.

A continuación se muestra un diagrama que utiliza el ejemplo 4 de la tabla anterior para ilustrar cómo se ubica cada byte de datos modificado y cómo se identifica como un byte de datos o un byte de final de trama.

 [OHB] : Byte de sobrecarga (inicio del marco) 3+ -------------->| : Señala la ubicación relativa del primer símbolo cero 2+-------->| : Es un byte de datos cero, que apunta al siguiente símbolo cero [EOP] : Ubicación del símbolo cero de final de paquete. 0 1 2 3 4 5 : Posición del byte 03 11 22 02 33 00 : Marco de datos COBS 11 22 00 33 : Datos extraídos OHB = Byte de sobrecarga (apunta al siguiente símbolo cero)EOP = Fin del paquete

Los ejemplos 7 a 10 muestran cómo varía la sobrecarga según los datos que se codifican para longitudes de paquetes de 255 o más.

El siguiente código implementa un codificador y decodificador COBS en el lenguaje de programación C:

#include <stddef.h> #include <stdint.h> #include <assert.h>   /** COBS codifica datos en el búfer @param data Puntero a los datos de entrada a codificar @param length Número de bytes a codificar @param buffer Puntero al búfer de salida codificado @return Longitud del búfer codificado en bytes @note No genera el byte delimitador */ size_t cobsEncode ( const void * data , size_t length , uint8_t * buffer ) { assert ( data && buffer );         uint8_t * encode = buffer ; // Puntero de byte codificado uint8_t * codep = encode ++ ; // Puntero de código de salida uint8_t code = 1 ; // Valor del código            para ( const uint8_t * byte = ( const uint8_t * ) datos ; longitud -- ; ++ byte ) { si ( * byte ) // Byte no es cero, escríbelo * codificar ++ = * byte , ++ código ;              if ( !* byte || code == 0xff ) // La entrada es cero o el bloque está completo, reiniciar { * codep = code , code = 1 , codep = encode ; if ( !* byte || length ) ++ encode ; } } * codep = code ; // Escribir el valor del código final                    devolver ( tamaño_t ) ( codificar - buffer ); }   /** COBS decodifica datos del buffer @param buffer Puntero a bytes de entrada codificados @param length Número de bytes a decodificar @param data Puntero a datos de salida decodificados @return Número de bytes decodificados exitosamente @note Detiene la decodificación si se encuentra el byte delimitador */ size_t cobsDecode ( const uint8_t * buffer , size_t length , void * data ) { assert ( buffer && data );         const uint8_t * byte = buffer ; // Puntero de byte de entrada codificado uint8_t * decode = ( uint8_t * ) data ; // Puntero de byte de salida decodificado          para ( uint8_t código = 0xff , bloque = 0 ; byte < buffer + length ; -- bloque ) { si ( bloque ) // Descodificar bloque byte * decodificar ++ = * byte ++ ; de lo contrario { bloque = * byte ++ ; // Obtener la siguiente longitud de bloque si ( bloque && ( código != 0xff )) // Cero codificado, escríbalo a menos que sea delimitador. * decodificar ++ = 0 ; código = bloque ; si ( ! código ) // Código delimitador encontrado break ; } }                                devolver ( tamaño_t )( decodificar - ( uint8_t * ) datos ); }    

• Relleno de bits
• Protocolo de Internet de línea serial

• Implementación de Python
• Implementación alternativa de C
• Otra implementación en C
• Relleno de bytes de sobrecarga consistente: reducido (COBS/R)
• Una patente que describe un esquema con un resultado similar pero que utiliza un método diferente