Consistent Overhead Byte Stuffing ( COBS ) es un algoritmo para codificar bytes de datos que da como resultado un entramado de paquetes eficiente, confiable y sin ambigüedades, independientemente del contenido del paquete, lo que facilita que las aplicaciones receptoras se recuperen de paquetes mal formados. Emplea un valor de byte particular, normalmente cero, para servir 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 para que no aparezcan bytes de datos cero en el paquete y, por lo tanto, se malinterpreten como límites del paquete.
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 ocurrencias de esos valores. La longitud adicional de la secuencia transformada se denomina típicamente la sobrecarga del algoritmo. El algoritmo COBS limita estrechamente la sobrecarga del peor de los casos, limitándola a un mínimo de un byte y un máximo de ⌈ n / 254⌉ bytes (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 su sobrecarga promedio es baja en comparación con otros algoritmos de entramado inequívocos. [1][2]
COBS, sin embargo, requiere hasta 254 bytes de anticipación . Antes de transmitir su primer byte, necesita conocer la posición del primer byte cero (si lo hay) en los siguientes 254 bytes.
Enmarcado y relleno de paquetes
Cuando los datos empaquetados se envían a través de cualquier medio en serie, se requiere algún protocolo para demarcar los límites de los paquetes. Esto se hace usando un marcador de entramado, una secuencia de bits especial o un valor de carácter que indica dónde caen 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 encuadre, de modo que cuando el receptor detecta un marcador, puede estar seguro de que el marcador 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]. Habiendo eliminado todos los bytes cero de los datos, ahora se puede usar un byte cero para marcar sin ambigüedades el final de los datos transformados. Esto se hace agregando un byte cero a los datos transformados, formando así un paquete que consta de los datos codificados en COBS (la carga útil ) para marcar sin ambigüedades 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 del bloque prefijado
- Para codificar algunos bytes, primero agregue un byte cero, luego divídalos en grupos de 254 bytes distintos de cero o 0-253 bytes distintos de cero seguidos de un byte cero. Debido al byte cero agregado, esto siempre es posible.
- Codifique cada grupo eliminando el byte cero final (si lo hubiera) y anteponiendo el número de bytes distintos de cero, más uno. Por lo tanto, cada grupo codificado tiene el mismo tamaño que el original, excepto que se codifican 254 bytes distintos de cero 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 al final. Esto ahorra un byte en algunas situaciones.
- Descripción de la lista vinculada
- Primero, inserte un byte cero al comienzo del paquete y después de cada ejecución de 254 bytes distintos de cero. Esta codificación es obviamente reversible. No es necesario insertar un byte cero al final del paquete si termina con exactamente 254 bytes distintos de cero.
- En segundo lugar, reemplace cada byte cero con el desplazamiento al siguiente byte cero, o al final del paquete. Debido a los ceros adicionales agregados en el primer paso, se garantiza que cada desplazamiento sea como máximo 255.
Ejemplos de codificación
Estos ejemplos muestran cómo el algoritmo COBS codificaría varias 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 varias características:
- 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 verde indica un byte de datos cero que fue alterado por 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 siguen). Efectivamente, es un puntero al siguiente byte de paquete que requiere interpretación: si el byte direccionado no es cero, entonces es el siguiente byte de encabezado de grupo el byte de datos cero 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 sobrecarga que también es un byte de encabezado de grupo que contiene un desplazamiento a un grupo siguiente, pero no corresponde a un byte de datos. Estos aparecen en dos lugares: al comienzo de cada paquete codificado y después de cada grupo de 254 bytes distintos de cero.
- Aparece un byte azul cero al final de cada paquete para indicar el final del paquete al receptor de datos. Este byte delimitador de paquetes no forma parte de COBS propiamente dicho; es un byte de entramado adicional que se agrega a la salida codificada.
Ejemplo | Datos no codificados (hexadecimal) | Codificado con COBS (hexadecimal) |
---|---|---|
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 |
A continuación se muestra un diagrama que utiliza el ejemplo 3 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 de la trama) 3+ --------------> | : Apunta a 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 sobrecarga (apunta al siguiente símbolo cero)EOP = Fin del paquete
Los ejemplos 7 a 10 muestran cómo varía la sobrecarga dependiendo de los datos que se codifican para paquetes de 255 o más.
Implementación
El siguiente código implementa un codificador y decodificador COBS en el lenguaje de programación C:
#include #include / ** COBS codifica datos para almacenar datos en el búfer @param data Puntero a los datos de entrada para codificar @param length Número de bytes para codificar @param buffer Puntero al búfer de salida codificado @return Longitud del búfer codificado en bytes @note No genera el byte delimitador de salida * / size_t cobsEncode ( const void * datos , tamaño_t longitud , uint8_t * búfer ) { aseverar ( datos && búfer );uint8_t * encode = búfer ; // Puntero de byte codificado uint8_t * codep = encode ++ ; // Puntero de 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 distinto de cero, escríbalo * encode ++ = * byte , ++ código ;if ( ! * byte || código == 0xff ) // La entrada es cero o el bloque se completó, reiniciar { * codep = código , código = 1 , codep = codificar ; if ( ! * byte || longitud ) ++ codificar ; } } * codep = código ; // Escribe el valor del código finalreturn codificar - búfer ; }/ ** COBS decodifica datos desde el búfer @param búfer Puntero a bytes de entrada codificados @param longitud Número de bytes para decodificar @param datos Puntero a 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 * búfer , tamaño_t longitud , void * datos ) { assert ( búfer && datos );const uint8_t * byte = búfer ; // Puntero de byte de entrada codificado uint8_t * decode = ( uint8_t * ) data ; // Puntero de byte de salida decodificadofor ( uint8_t código = 0xff , bloque = 0 ; byte < búfer + longitud ; - bloque ) { if ( bloque ) // Decodificar byte del bloque * decodificar ++ = * byte ++ ; else { if ( code ! = 0xff ) // Codificado cero, escríbalo * decode ++ = 0 ; bloque = código = * byte ++ ; // Longitud del siguiente bloque if ( código == 0x00 ) // Código delimitador encontrado break ; } }devuelve decodificar - ( uint8_t * ) datos ; }
Ver también
Referencias
- ^ Cheshire, Stuart; Baker, Mary (abril de 1999). "Relleno de bytes de sobrecarga coherente" (PDF) . Transacciones IEEE / ACM sobre redes . 7 (2): 159-172. CiteSeerX 10.1.1.108.3143 . doi : 10.1109 / 90.769765 . Consultado el 30 de noviembre de 2015 .
- ^ Cheshire, Stuart; Baker, Mary (17 de noviembre de 1997). Relleno coherente de bytes generales (PDF) . ACM SIGCOMM '97. Cannes . Consultado el 23 de noviembre de 2010 .