Relleno de bytes de sobrecarga constante

El algoritmo COBS ( Consistent Overhead Byte Stuffing ) codifica bytes de datos, lo que resulta en un encuadre de paquetes eficiente, fiable y sin ambigüedades , independientemente del contenido del paquete. Esto facilita que las aplicaciones receptoras se recuperen de paquetes mal formados. Emplea un valor de byte específico, generalmente cero, como delimitador de paquetes (un valor especial que indica el límite entre paquetes). Cuando se usa cero como delimitador, el algoritmo reemplaza cada byte de datos cero con un valor distinto de cero, de modo que no aparezcan bytes de datos cero en el paquete y, por lo tanto, no se interpreten erróneamente 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 paquete) 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 enmarcado HDLC es un ejemplo bien conocido, utilizado particularmente en PPP (véase RFC 1662 § 4.2 ). Aunque el enmarcado HDLC tiene una sobrecarga inferior al 1 % en el caso promedio , sufre una sobrecarga muy alta en el peor de los casos del 100 %; para entradas que consisten enteramente 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 una sobrecarga mínima de 1 byte y una máxima 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 la fluctuación puede ser problemática. 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 trama no ambiguos como HDLC. ^{[ 1 ] [ 2 ]} Sin embargo, COBS requiere hasta 254 bytes de anticipación . 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 enmarcado HDLC en PPP , debido a la sobrecarga en el peor de los casos del enmarcado HDLC antes mencionada. ^{[ 3 ]}

Cuando se envían datos empaquetados a través de cualquier medio serial, se requiere un protocolo para delimitar los límites de los paquetes. Esto se logra mediante un marcador de trama, una secuencia de bits o un valor de carácter especial 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 detecta un marcador, puede estar seguro de que este indica un límite entre paquetes.

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

(Cualquier otro valor de byte puede reservarse como delimitador de paquete, pero usar cero simplifica la descripción).

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

Descripción del 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. Gracias al byte cero añadido, esto siempre es posible.

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, salvo que 254 bytes distintos de cero se codifican en 255 bytes añadiendo un byte con el valor 255.

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

Descripción de la lista enlazada

Primero, inserte un byte cero al inicio del paquete y después de cada secuencia de 254 bytes distintos de cero. Esta codificación es reversible. No es necesario insertar un byte cero al final del paquete si este termina con exactamente 254 bytes distintos de cero.

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

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

• El texto en negrita indica un byte de datos que no ha sido alterado por la codificación. Todos los bytes de datos distintos de cero permanecen inalterados.
• El color verde indica un byte de datos cero que fue alterado por la codificación. Todos los bytes de datos cero se reemplazan durante la codificación por el desplazamiento al siguiente byte cero (es decir, uno más el número de bytes distintos de cero que le siguen). Es, en efecto, un puntero al siguiente byte del paquete que requiere interpretación: si el byte direccionado no es cero, entonces es el siguiente byte de datos cero del encabezado del grupo que apunta al siguiente byte que requiere interpretación; si el byte direccionado es cero, entonces es el final del paquete .
• El byte rojo es un byte de cabecera que también contiene un desplazamiento al grupo siguiente, pero no corresponde a un byte de datos. Estos bytes aparecen en dos lugares: al principio de cada paquete codificado y después de cada grupo de 254 bytes distintos de cero.
• Un byte azul cero aparece al final de cada paquete para indicar el final del paquete al receptor de datos. Este byte delimitador de paquete no forma parte de COBS propiamente dicho; es un byte de trama 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 localiza cada byte de datos modificado y cómo se identifica como un byte de datos o un byte de fin de trama.

 [OHB] : Byte de cabecera (Inicio de trama) 3+ -------------->| : Indica 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 fin 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 cabecera (Apunta al siguiente símbolo cero) EOP = Fin del paquete 

Los ejemplos 7 al 10 muestran cómo varía la sobrecarga dependiendo de los datos que se codifican para longitudes de paquete de 255 o más.

El siguiente código implementa un codificador y decodificador COBS en el lenguaje de programación C , procesando los datos byte a byte.

#include <stddef.h> #include <stdint.h> #include <assert.h>/** Codifica datos COBS en un 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 al byte codificado uint8_t * codep = encode ++ ; // Puntero al código de salida uint8_t code = 1 ; // Valor del códigofor ( const uint8_t * byte = ( const uint8_t * ) data ; length -- ; ++ byte ) { if ( * byte ) // Byte no es cero, escríbelo * encode ++ = * byte , ++ code ;if ( !* byte || code == 0xff ) // La entrada es cero o el bloque se ha completado, reiniciar { * codep = code , code = 1 , codep = encode ; if ( !* byte || length ) ++ encode ; } } * codep = code ; // Escribir el valor final del códigoreturn ( size_t )( encode - buffer ); }/** COBS decodifica datos desde un búfer  @param buffer Puntero a los bytes de entrada codificados  @param length Número de bytes a decodificar  @param data Puntero a los datos de salida decodificados  @return Número de bytes decodificados correctamente  @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 al byte de entrada codificado uint8_t * decode = ( uint8_t * ) data ; // Puntero al byte de salida decodificadofor ( uint8_t code = 0xff , block = 0 ; byte < buffer + length ; -- block ) { if ( block ) // Decodificar el byte del bloque * decode ++ = * byte ++ ; else { block = * byte ++ ; // Obtener la siguiente longitud de bloque if ( block && ( code != 0xff )) // Cero codificado, escribirlo a menos que sea un delimitador. * decode ++ = 0 ; code = block ; if ( ! code ) // Código delimitador encontrado break ; } }return ( size_t )( decode - ( uint8_t * ) data ); }

• Relleno de un poco
• Protocolo de Internet de línea serie

• Implementación en Python
• Implementación alternativa en 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 utilizando un método diferente.