Spójne wypełnianie bajtów narzutu — Consistent Overhead Byte Stuffing

Consistent Overhead Byte Stuffing ( COBS ) to algorytm kodowania bajtów danych, który zapewnia wydajne, niezawodne i jednoznaczne ramkowanie pakietów niezależnie od zawartości pakietu, co ułatwia odbieranie aplikacji w celu odzyskania uszkodzonych pakietów. Wykorzystuje określoną wartość bajtu, zwykle zero, która służy jako separator pakietów (specjalna wartość, która wskazuje granicę między pakietami). Gdy zero jest używane jako ogranicznik, algorytm zastępuje każdy zerowy bajt danych wartością niezerową, tak że żadne zerowe bajty danych nie pojawią się w pakiecie, a zatem nie będą błędnie interpretowane jako granice pakietu.

Wypełnianie bajtów to proces, który przekształca sekwencję bajtów danych, które mogą zawierać „nielegalne” lub „zarezerwowane” wartości (takie jak separator pakietów) w potencjalnie dłuższą sekwencję, która nie zawiera żadnych wystąpień tych wartości. Dodatkowa długość transformowanej sekwencji jest zwykle określana jako narzut algorytmu. Algorytm COBS ściśle ogranicza narzut najgorszego przypadku, ograniczając go do minimum jednego bajtu i maksimum ⌈ n /254⌉ bajtów (jeden bajt na 254, zaokrąglając w górę). W konsekwencji czas transmisji zakodowanej sekwencji bajtów jest wysoce przewidywalny, co sprawia, że ​​COBS jest użyteczny w aplikacjach czasu rzeczywistego, w których jitter może być problematyczny. Algorytm jest tani obliczeniowo, a jego średni narzut jest niski w porównaniu z innymi jednoznacznymi algorytmami ramkowania.

COBS wymaga jednak do 254 bajtów lookahead . Przed przesłaniem swojego pierwszego bajtu musi znać pozycję pierwszego bajtu zerowego (jeśli istnieje) w kolejnych 254 bajtach.

Obramowywanie i wypychanie pakietów

Gdy dane w pakietach są przesyłane przez dowolny nośnik szeregowy, do wyznaczenia granic pakietów wymagany jest pewien protokół . Odbywa się to za pomocą znacznika ramki, specjalnej sekwencji bitowej lub wartości znakowej, która wskazuje, gdzie znajdują się granice między pakietami. Wypychanie danych to proces, który przekształca dane pakietu przed transmisją w celu wyeliminowania wszystkich wystąpień znacznika ramek, tak aby po wykryciu znacznika przez odbiornik można było mieć pewność, że znacznik wskazuje granicę między pakietami.

COBS przekształca dowolny ciąg bajtów z zakresu [0,255] na bajty z zakresu [1,255]. Po wyeliminowaniu wszystkich bajtów zerowych z danych można teraz użyć bajtu zerowego do jednoznacznego oznaczenia końca transformowanych danych. Odbywa się to poprzez dodanie bajtu zerowego do przekształconych danych, tworząc w ten sposób pakiet składający się z danych zakodowanych w COBS ( ładunek danych ), aby jednoznacznie oznaczyć koniec pakietu.

(Każda inna wartość bajtu może być zarezerwowana jako separator pakietów, ale użycie zera upraszcza opis).

Istnieją dwa równoważne sposoby opisania procesu kodowania COBS:

Opis bloku z przedrostkiem

Aby zakodować niektóre bajty, najpierw dołącz bajt zerowy, a następnie podziel je na grupy po 254 niezerowych bajtów lub od 0 do 253 niezerowych bajtów, po których następuje bajt zerowy. Ze względu na dodany bajt zerowy jest to zawsze możliwe.

Zakoduj każdą grupę, usuwając końcowy bajt zerowy (jeśli istnieje) i dodając liczbę niezerowych bajtów plus jeden. Tak więc każda zakodowana grupa ma taki sam rozmiar jak oryginał, z wyjątkiem tego, że 254 niezerowe bajty są zakodowane w 255 bajtach przez dodanie bajtu 255.

W ramach specjalnego wyjątku, jeśli pakiet kończy się grupą 254 niezerowych bajtów, nie jest konieczne dodawanie końcowego bajtu zerowego. W niektórych sytuacjach oszczędza to jeden bajt.

Opis połączonej listy

Najpierw wstawiamy bajt zerowy na początku pakietu, a po każdym uruchomieniu 254 niezerowych bajtów. To kodowanie jest oczywiście odwracalne. Nie jest konieczne wstawianie zerowego bajtu na końcu pakietu, jeśli kończy się on dokładnie 254 niezerowymi bajtami.

Po drugie, zastąp każdy bajt zerowy przesunięciem do następnego bajtu zerowego lub końca pakietu. Ze względu na dodatkowe zera dodane w pierwszym kroku, każdy offset gwarantuje maksymalnie 255.

Przykłady kodowania

Te przykłady pokazują, jak różne sekwencje danych byłyby kodowane przez algorytm COBS. W przykładach wszystkie bajty są wyrażone jako wartości szesnastkowe , a zakodowane dane są wyświetlane z formatowaniem tekstu, aby zilustrować różne funkcje:

• Pogrubienie wskazuje bajt danych, który nie został zmieniony przez kodowanie. Wszystkie niezerowe bajty danych pozostają niezmienione.
• Zielony oznacza zerowy bajt danych, który został zmieniony przez kodowanie. Wszystkie zerowe bajty danych są zastępowane podczas kodowania przez przesunięcie do następnego bajtu zerowego (tj. jeden plus liczba kolejnych niezerowych bajtów). Jest to w rzeczywistości wskaźnik do następnego bajtu pakietu, który wymaga interpretacji: jeśli adresowany bajt jest niezerowy, to jest to kolejny bajt danych nagłówka grupy, który wskazuje na następny bajt wymagający interpretacji; jeśli adresowany bajt wynosi zero, to jest to koniec pakietu .
• Czerwony jest bajtem narzutu, który jest również bajtem nagłówka grupy zawierającym przesunięcie do następnej grupy, ale nie odpowiada bajtowi danych. Pojawiają się one w dwóch miejscach: na początku każdego zakodowanego pakietu i po każdej grupie 254 niezerowych bajtów.
• Na końcu każdego pakietu pojawia się niebieski bajt zerowy, który oznacza koniec pakietu dla odbiorcy danych. Ten bajt ogranicznika pakietów nie jest częścią właściwego COBS; jest to dodatkowy bajt ramki, który jest dołączany do zakodowanego wyjścia.

Poniżej znajduje się diagram wykorzystujący przykład 3 z powyższej tabeli, aby zilustrować, jak znajduje się każdy zmodyfikowany bajt danych i jak jest on identyfikowany jako bajt danych lub bajt końca ramki.

   [OHB]                                : Overhead byte (Start of frame)
     3+ -------------->|                : Points to relative location of first zero symbol
                       2+-------->|     : Is a zero data byte, pointing to next zero symbol
                                  [EOP] : Location of end-of-packet zero symbol.
     0     1     2     3     4    5     : Byte Position
     03    11    22    02    33   00    : COBS Data Frame
           11    22    00    33         : Extracted Data
     
OHB = Overhead Byte (Points to next zero symbol)
EOP = End Of Packet

Przykłady od 7 do 10 pokazują, jak narzut zmienia się w zależności od kodowanych danych dla pakietów o długości 255 lub większej.

Realizacja

Poniższy kod implementuje koder i dekoder COBS w języku programowania C:

#include <stddef.h>
#include <stdint.h>
#include <assert.h>

/** COBS encode data to buffer
	@param data Pointer to input data to encode
	@param length Number of bytes to encode
	@param buffer Pointer to encoded output buffer
	@return Encoded buffer length in bytes
	@note Does not output delimiter byte
*/
size_t cobsEncode(const void *data, size_t length, uint8_t *buffer)
{
	assert(data && buffer);

	uint8_t *encode = buffer; // Encoded byte pointer
	uint8_t *codep = encode++; // Output code pointer
	uint8_t code = 1; // Code value

	for (const uint8_t *byte = (const uint8_t *)data; length--; ++byte)
	{
		if (*byte) // Byte not zero, write it
			*encode++ = *byte, ++code;

		if (!*byte || code == 0xff) // Input is zero or block completed, restart
		{
			*codep = code, code = 1, codep = encode;
			if (!*byte || length)
				++encode;
		}
	}
	*codep = code; // Write final code value

	return (size_t)(encode - buffer);
}

/** COBS decode data from buffer
	@param buffer Pointer to encoded input bytes
	@param length Number of bytes to decode
	@param data Pointer to decoded output data
	@return Number of bytes successfully decoded
	@note Stops decoding if delimiter byte is found
*/
size_t cobsDecode(const uint8_t *buffer, size_t length, void *data)
{
	assert(buffer && data);

	const uint8_t *byte = buffer; // Encoded input byte pointer
	uint8_t *decode = (uint8_t *)data; // Decoded output byte pointer

	for (uint8_t code = 0xff, block = 0; byte < buffer + length; --block)
	{
		if (block) // Decode block byte
			*decode++ = *byte++;
		else
		{
			if (code != 0xff) // Encoded zero, write it
				*decode++ = 0;
			block = code = *byte++; // Next block length
			if (!code) // Delimiter code found
				break;
		}
	}

	return (size_t)(decode - (uint8_t *)data);
}

Zobacz też

• Protokół internetowy łącza szeregowego

Bibliografia

Zewnętrzne linki

• Implementacja Pythona
• Alternatywna implementacja C
• Kolejna implementacja w C
• Konsekwentne wypychanie bajtów narzutu — zredukowane (COBS/R)
• Patent opisujący schemat o podobnym wyniku, ale przy użyciu innej metody