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:
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:
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 ); }