一貫したオーバーヘッドバイトスタッフィング

一貫性オーバーヘッドバイトスタッフィング( COBS ) は、データバイトをエンコードするアルゴリズムです。パケットの内容に関係なく、効率的で信頼性が高く、明確なパケットフレーミングを実現し、受信側アプリケーションが不正なパケットから簡単に回復できるようにします。特定のバイト値 (通常はゼロ) をパケット区切り文字(パケット間の境界を示す特別な値) として使用します。ゼロを区切り文字として使用すると、アルゴリズムは各ゼロデータバイトをゼロ以外の値に置き換えます。これにより、ゼロデータバイトがパケットに現れず、パケット境界として誤って解釈されることがなくなります。

バイト スタッフィングは、不正な値や予約済みの値 (パケット区切り文字など) を含む可能性のあるデータ バイトのシーケンスを、それらの値を含まない、潜在的に長いシーケンスに変換するプロセスです。変換されたシーケンスの余分な長さは、通常、アルゴリズムのオーバーヘッドと呼ばれます。HDLCフレーミング はよく知られた例で、特にPPPで使用されます(RFC 1662 § 4.2 を参照)。HDLC フレーミングのオーバーヘッドは平均ケースでは 1% 未満ですが、最悪のケースでは 100% という非常に悪いオーバーヘッドが発生します。入力がすべてエスケープを必要とするバイトで構成されている場合、HDLC バイト スタッフィングによって入力のサイズが 2 倍になります。

一方、COBS アルゴリズムは、最悪の場合のオーバーヘッドを厳しく制限します。COBS では、nデータ バイトに対して最小 1 バイトのオーバーヘッド、最大 ⌈ n /254⌉ バイトのオーバーヘッドが必要です(254 分の 1 バイト、切り上げ)。その結果、エンコードされたバイト シーケンスの送信時間は非常に予測可能になり、COBS はジッタが問題となる可能性のあるリアルタイム アプリケーションに役立ちます。このアルゴリズムは計算コストが低く、望ましい最悪の場合のオーバーヘッドに加えて、平均オーバーヘッドも HDLC などの他の明確なフレーミング アルゴリズムと比較して低くなっています。^{[1] [2]} ただし、COBS では最大 254 バイトの先読みが必要です。最初のバイトを送信する前に、次の 254 バイトの最初のゼロ バイト (ある場合) の位置を知る必要があります。

1999年のインターネットドラフトでは、 HDLCフレーミングの最悪のケースでのオーバーヘッドが劣悪であることから、PPPにおけるHDLCフレーミングの代替としてCOBSを標準化することが提案されました。 ^[3]

パケット化されたデータをシリアル メディア経由で送信する場合、パケットの境界を区切るためのプロトコルが必要です。これは、パケット間の境界を示す特別なビット シーケンスまたは文字値であるフレーミング マーカーを使用して行われます。データ スタッフィングは、送信前にパケット データを変換してフレーミング マーカーの発生をすべて排除するプロセスです。これにより、受信側がマーカーを検出したときに、そのマーカーがパケット間の境界を示していることが確実になります。

COBS は、[0,255] の範囲の任意のバイト文字列を [1,255] の範囲のバイトに変換します。データからすべてのゼロ バイトが削除されたので、ゼロ バイトを使用して変換されたデータの終わりを明確に示すことができます。これは、変換されたデータにゼロ バイトを追加することで行われ、COBS エンコード データ (ペイロード)で構成されるパケットが形成され、パケットの終わりを明確に示します。

(他のバイト値をパケット区切り文字として予約することもできますが、ゼロを使用すると説明が簡単になります。)

COBS エンコーディング プロセスを説明する同等の方法が 2 つあります。

プレフィックス付きブロックの説明

いくつかのバイトをエンコードするには、まずゼロ バイトを追加し、次に 254 個の非ゼロ バイトのグループ、または 0 ～ 253 個の非ゼロ バイトの後にゼロ バイトが続くグループに分割します。ゼロ バイトが追加されているため、これは常に可能です。

各グループをエンコードするときは、末尾のゼロ バイト (存在する場合) を削除し、非ゼロ バイトの数に 1 を加えた数を先頭に追加します。したがって、エンコードされた各グループは元のグループと同じサイズになりますが、254 の非ゼロ バイトは、先頭に 255 バイトを追加して 255 バイトにエンコードされます。

特別な例外として、パケットが 254 個の非ゼロ バイトのグループで終わる場合、末尾のゼロ バイトを追加する必要はありません。これにより、状況によっては 1 バイトを節約できます。

リンクリストの説明

まず、パケットの先頭と、254 個の非ゼロ バイトが続くたびに、ゼロ バイトを挿入します。このエンコードは明らかに可逆です。パケットがちょうど 254 個の非ゼロ バイトで終わる場合は、パケットの最後にゼロ バイトを挿入する必要はありません。

次に、各ゼロ バイトを次のゼロ バイトまたはパケットの末尾へのオフセットに置き換えます。最初の手順で追加された余分なゼロにより、各オフセットは最大 255 になることが保証されます。

これらの例は、さまざまなデータ シーケンスが COBS アルゴリズムによってどのようにエンコードされるかを示しています。例では、すべてのバイトが16 進数値として表現され、エンコードされたデータはさまざまな機能を示すためにテキスト形式で表示されます。

• 太字は、エンコードによって変更されていないデータ バイトを示します。ゼロ以外のデータ バイトはすべて変更されません。
• 緑は、エンコードによって変更されたゼロ データ バイトを示します。すべてのゼロ データ バイトは、エンコード中に、次のゼロ バイトへのオフセット (つまり、1 に続く非ゼロ バイトの数を加えた数) によって置き換えられます。これは、解釈を必要とする次のパケット バイトへのポインターです。アドレス指定されたバイトがゼロでない場合は、次のグループ ヘッダー バイトのゼロ データ バイトが、解釈を必要とする次のバイトを指します。アドレス指定されたバイトがゼロの場合は、パケットの終わりです。
• 赤はオーバーヘッド バイトであり、後続のグループへのオフセットを含むグループ ヘッダー バイトでもありますが、データ バイトには対応していません。これらは、エンコードされたすべてのパケットの先頭と、254 個の非ゼロ バイトの各グループの後の 2 か所に表示されます。
• 各パケットの末尾には青いゼロバイトが表示され、データ受信側にパケットの終了を示します。このパケット区切りバイトは COBS 自体の一部ではなく、エンコードされた出力に追加されるフレーミング バイトです。

以下は、上記の表の例 4 を使用して、変更された各データ バイトがどのように配置され、それがデータ バイトまたはフレーム終了バイトとしてどのように識別されるかを示す図です。

   [OHB] : オーバーヘッドバイト（フレームの開始）
     3+ -------------->| : 最初のゼロ記号の相対位置を指す
                       2+-------->| : ゼロデータバイトで、次のゼロシンボルを指します
                                  [EOP] : パケット終了ゼロシンボルの位置。
     0 1 2 3 4 5 : バイト位置
     03 11 22 02 33 00 : COBS データフレーム
           11 22 00 33 : 抽出されたデータ
     
OHB = オーバーヘッドバイト（次のゼロシンボルを指す）
EOP = パケットの終了

例 7 から 10 は、パケット長が 255 以上の場合にエンコードされるデータに応じてオーバーヘッドがどのように変化するかを示しています。

次のコードは、C プログラミング言語で COBS エンコーダーとデコーダーを実装します。

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

/** COBS エンコードデータをバッファに格納します
	@param data エンコードする入力データへのポインタ
	@param length エンコードするバイト数
	@param buffer エンコードされた出力バッファへのポインタ
	@return エンコードされたバッファの長さ（バイト単位） 
	@note 区切りバイトは出力しません
*/ 
size_t cobsEncode ( const void * data , size_t length , uint8_t * buffer ) { assert ( data && buffer );       

	  

	uint8_t * encode = buffer ; // エンコードされたバイトポインタuint8_t * codep = encode ++ ; // 出力コードポインタuint8_t code = 1 ; // コード値    
	    
	    

	for ( const uint8_t * byte = ( const uint8_t * ) data ; length -- ; ++ byte ) { if ( * byte ) // バイトがゼロでない場合は書き込みます* encode ++ = * byte , ++ code ;         
	
		  
			   

		if ( !* byte || code == 0xff ) // 入力がゼロまたはブロックが完了したら、再起動します{ * codep = code 、code = 1 、codep = encode ; if ( !* byte || length ) ++ encode ; } } * codep = code ; // 最終コード値を書き込む      
		
			        
			   
				
		
	
	   

	戻り値( size_t )(エンコード-バッファ); }   


/** COBS はバッファからデータをデコードします
	@param buffer エンコードされた入力バイトへのポインタ
	@param length デコードするバイト数
	@param data デコードされた出力データへのポインタ
	@return 正常にデコードされたバイト数
	@note 区切りバイトが見つかった場合はデコードを停止します
*/ 
size_t cobsDecode ( const uint8_t * buffer , size_t length , void * data ) { assert ( buffer && data );       

	  

	const uint8_t * byte = buffer ; // エンコードされた入力バイトポインタuint8_t * decode = ( uint8_t * ) data ; // デコードされた出力バイトポインタ     
	     

	for ( uint8_t code = 0xff , block = 0 ; byte < buffer + length ; -- block ) { if ( block ) // ブロックバイトをデコードします* decode ++ = * byte ++ ; else { block = * byte ++ ; // 次のブロック長を取得しますif ( block && ( code != 0xff )) // エンコードされたゼロ。区切り文字でない限り、それを書き込みます。* decode ++ = 0 ; code = block ; if ( ! code ) // 区切りコードが見つかりましたbreak ; } }             
	
		  
			  
		
		
			               
			      
				  
			  
			  
				
		
	

	戻り値( size_t )(デコード- ( uint8_t * )データ); }    

• ビット詰め
• シリアルラインインターネットプロトコル

• Python実装
• 代替C実装
• Cでの別の実装
• 一貫したオーバーヘッド バイト スタッフィング - 削減 (COBS/R)
• 同様の結果をもたらすが、異なる方法を使用する方式を説明する特許