Consistent overhead byte stuffing

Consistent overhead byte stuffing^[a] (COBS) – algorytm kodowania ciągu liczb (zwykle bajtów) w postaci ciągu, w którym nie występuje jeden wyróżniony symbol (zwykle zero). Jego pomysłodawcą i autorem jest Stuart David Cheshire(inne języki). Podstawową zaletą algorytmu jest znikomy narzut zwiększający rozmiar zakodowanych danych. Głównym zastosowaniem algorytmu jest wspomaganie pakietyzacji strumienia danych w transmisji szeregowej.

Historia

Prezentacja algorytmu miała miejsce na konferencji SIGCOMM poświęconej zagadnieniom komunikacyjnym^[1]  jak również został on zgłoszony jako propozycja do wykorzystania w protokole PPP^[2]. Algorytm kodowania był tematem pracy doktorskiej, którą Stuart David Cheshire(inne języki) przedłożył na Uniwersytecie Stanforda w 1998^[3] . Rok później artykuł z opisem algorytmu został opublikowany czasopiśmie organizacji IEEE^[4] . W 2020 zaadaptowano wykorzystanie algorytmu dla półbajtów^[5]. W 2022 roku zauważono, że w sprzyjających okolicznościach działanie algorytmu można przeprowadzić równolegle na fragmentach danych co znacznie skraca czas przetwarzania zwłaszcza w realizacji sprzętowej^[6] .

Motywacja

W transmisji danych z wykorzystaniem łącza szeregowego w warstwie fizycznej warstwa łącza danych tworzy ramki, które kapsułkują dane z wyższej warstwy^[7]. Każda ramka zawiera znaczniki, które jednoznacznie pozwalają określić jej początek i koniec^[7][8]. W systemach opartych na transmisji danych w postaci ciągów tekstowych znacznik startu to jeden ze znaków, który nie jest używany w kodowaniu danych^[b][9]. W przypadku, gdy łącze danych ma przesyłać dowolne dane binarne, może się zdarzyć, że wśród nich pojawią się takie, które będą przyjmowały wartości tożsame z używanymi do rozpoznawania początku i końca ramki. Aby uniknąć takich kolizji stosowane są metody pozwalające na ich eliminację ze strumienia danych. Za przykład można wskazać SLIP lub PPP^[10]. Polegają one głównie na podmianie każdego bajtu mającego specjalne znaczenie przez odpowiednie zastąpienie sekwencją dwóch bajtów^[11]. Jeśli nastąpi próba wysłania danych składających się z samych „zarezerwowanych” wartości, to w takim przypadku długość danych do przesłania w warstwie fizycznej ulegnie podwojeniu^[12].

W proponowanym algorytmie narzut związany z eliminacją wartości zarezerwowanych nie przekracza 1 bajta na każde 254 bajty danych^[13].

Opis

W wersji podstawowej algorytm skupia się na sposobie zapisu ciągu liczb z pełnego zakresu liczb ośmiobitowych od 0 do 255 na odpowiadający mu ciąg liczb z zakresu od 1 do 255. Jeśli zachodzi konieczność eliminacji wartości innej niż zero, to można wszystkie bajty wyniku zamienić wykonując na nich funkcję XOR z wartością do usunięcia^[14].

Kody

Do reprezentacji wartości oryginalnego ciągu COBS używa następujących kodów^[14]:

Kod (hex)	Znaczenie	Opis
01	00	bajt o wartości zero
02 XX	XX 00	dowolny niezerowy bajt danych + bajt o wartości zero
03 XX XX	XX XX 00	dowolne dwa niezerowe bajty danych + bajt o wartości zero
nn XX … XX	XX … XX 00	(nn-1) niezerowych bajtów danych + bajt o wartości zero
FE XX … XX	XX … XX 00	253 niezerowe bajty danych + bajt o wartości zero
FF XX … XX	XX … XX	254 niezerowe bajty danych, po których nie ma bajtu o wartości zero

W powyższym zestawieniu kodów nie istnieje wartość 00, która jest niedozwolona^[14].

Kodowanie

Ciąg wejściowy o dowolnej długości dzielony jest na fragmenty nie dłuższe niż 254 bajty, w których bajt o wartości zero występuje dokładnie na końcu. Jest on zastępowany w ciągu wyjściowym odpowiadającym mu kodem z domyślnym zerem. Jeśli taki podciąg nie istnieje to w jego miejsce jest wstawiany wyjątek zaczynający się kodem 255, który pozwala na kodowanie długich bezzerowych ciągów danych^[14]. Wyjątek stanowi również ostatni fragment nie dłuższy niż 253 bajty, który domyślnie zakłada istnienie wirtualnego zera tuż za ostatnim bajtem pakietu^[14]. Po zakodowaniu w wyjściowym strumieniu danych nie ma wartości zero, które można jednoznacznie wykorzystać do wskazania granic między pakietami^[14].

Przykłady

Pusta kratka na końcu to wirtualne zero. Pogrubiona czcionka oznacza pierwszy bajt kodu. Wielokropek to ciąg niezerowych wartości.

Oryginalny przykład ze specyfikacji^[15]

dane	45	00	00	2C	4C	79	00	00	40	06	4F	37
kod	02	45	01	04	2C	4C	79	01	05	40	06	4F	37

Ciąg z sekwencją niezerowych bajtów od pozycji 9 do 264^[16]

pozycja	1	2	3	4	5	6	7	8	…	263	264	265	266
dane	44	69	6C	65	00	00	74	00	…	54	61		—
kod	05	44	69	6C	65	01	02	74	FF	…	03	54	61

Ciąg z sekwencją 254 niezerowych bajtów na końcu^[16]

pozycja	1	2	3	4	5	6	7	…	258	259	260
dane	F0	9F	8D	86	00	F0	9F	…	92	A6	—
kod	05	F0	9F	8D	86	FF	F0	9F	…	92	A6

Pusty pakiet^[17]

dane
kod	01

Bajt zero

dane	00
kod	01	01

Własności

• Bardzo mały narzut na rozmiar danych po kodowaniu^[18].
• Bardzo prosta synchronizacja^[18].
• Kodowanie wymaga bufora o rozmiarze 254 bajtów^[19]
• Trywialna implementacja w każdym języku programowania^[20]

Obserwacje

• Strumień danych zakodowanych algorytmem COBS dzielony jest na pakiety w miejscu napotkania wartości specjalnej 0x00. Zachowanie na okoliczność występowania sekwencji zer w takim ciągu nie jest zdefiniowane. Jednym z rozwiązań jest przyjęcie, że oznacza ona brak pakietu^[17].
• Ciąg zerowych bajtów może być więc wykorzystany jako wypełnienie jeżeli brakuje danych do transmisji^[21].
• Protokół MS/TP, używany jako warstwa łącza danych w transmisji po RS-485 w protokole BACnet, stosuje algorytm COBS do eliminacji wartości specjalnej 0x55 z bloku danych i sumy kontrolnej. Sekwencja bajtów 0x55 0xFF oznacza w nim początek nowej ramki^[22].
• Algorytm COBS może być dobrym wyborem w przypadku implementacji pakietyzacji przy połączeniach z wykorzystaniem protokołu TCP^[23].
• Algorytm nie jest powszechnie stosowany w praktyce^[19]. Jednym z powodów może być brak oficjalnego wsparcia w ramach standardu PPP^[24].
• Algorytm operuje na buforach danych, wobec czego nie może być stosowany w przypadku gdy oczekiwane jest natychmiastowe generowanie danych wyjściowych w przetwarzaniu potokowym^[25].
• W przypadku obsługi pakietów o niewielkich rozmiarach, stały jednobajtowy narzut może być odbierany jako znaczny^[26]. Dla pakietów jednobajtowych narzut stanowi 100%, a dla czterobajtowych 25% oryginalnej wiadomości^[27].

Uwagi

1. Literalnie Niesprzeczne^[28] nagłówkowe^[29] dopełnianie bajtowe^[30].
2. Na przykład w systemie Modbus jest to dwukropek^[9].