一貫したオーバーヘッドバイトスタッフィング
一貫性オーバーヘッドバイトスタッフィング（COBS）は、データバイトをエンコードするためのアルゴリズムです。パケットの内容に関わらず、効率的で信頼性が高く、明確なパケットフレーミングを実現し、受信側アプリケーションが不正なパケットから容易に回復できるようにします。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自体の一部ではなく、エンコードされた出力に付加されるフレーミングバイトです。
| 例 | エンコードされていないデータ（16進数） | COBS（16進数）でエンコード |
|---|---|---|
| 1 | 00 | 01 01 00 |
| 2 | 00 00 | 01 01 01 00 |
| 3 | 00 11 00 | 01 02 11 01 00 |
| 4 | 11 22 00 33 | 03 11 22 02 33 00 |
| 5 | 11 22 33 44 | 05 11 22 33 44 00 |
| 6 | 11 00 00 00 | 02 11 01 01 01 00 |
| 7 | 01 02 03 ... FD FE | FF 01 02 03 ... FD FE 00 |
| 8 | 00 01 02 ... FC FD FE | 01 FF 01 02 ... FC FD FE 00 |
| 9 | 01 02 03 ... FD FE FF | FF 01 02 03 ... FD FE 02 FF 00 |
| 10 | 02 03 04 ... FE FF 00 | FF 02 03 04 ...FE FF 01 01 00 |
| 11 | 03 04 05 ... FF 00 01 | FE 03 04 05 ... FF 02 01 00 |
以下は、上記の表の例 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 ; // 最終コード値を書き込む return ( size_t )( encode - buffer ); } /** 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 ) // ブロック byte をデコードします* decode ++ = * byte ++ ; else { block = * byte ++ ; // 次のブロック長を取得しますif ( block && ( code != 0xff )) // エンコードされたゼロ。区切り文字でない限り、これを書き出します。* decode ++ = 0 ; code = block ; if ( ! code ) // 区切りコードが見つかりましたbreak ; } } return ( size_t )(デコード- ( uint8_t * )データ); } 参照
参考文献
- ^ Cheshire, Stuart ; Baker, Mary (1999年4月). 「Consistent Overhead Byte Stuffing」(PDF) . IEEE/ACM Transactions on Networking . 7 (2): 159– 172. CiteSeerX 10.1.1.108.3143 . doi :10.1109/90.769765. S2CID 47267776. 2015年11月30日閲覧.
- ^ Cheshire, Stuart ; Baker, Mary (1997年11月17日). Consistent Overhead Byte Stuffing (PDF) . ACM SIGCOMM '97.カンヌ. 2010年11月23日閲覧。
- ^ Carlson, James; Cheshire, Stuart ; Baker, Mary (1997年11月). PPP Consistent Overhead Byte Stuffing (COBS). ID draft-ietf-pppext-cobs-00.txt.
外部リンク
- Python実装
- 代替C実装
- C言語での別の実装
- 一貫性のあるオーバーヘッドバイトスタッフィングの削減 (COBS/R)
- 同様の結果をもたらすが異なる方法を使用する方式を記載した特許
