最初に
わけわからんタイトルですが文句はChatGPT君に。
(COBS自体は1999年のInternet Draftで提案されているので革命でもなんでもないです。昔からあります。)
研究を進める中で出てきたことをまとめました。
概要
シンプルなデータのエンコード方式としてはSLIP(Serial Line Internet Protocol)というものがあります。
しかし、SLIPは最悪の場合、元データの二倍の大きさになるという問題があります。
そこで、COBS(Consistent Overhead Byte Stuffing)という手法を頭のいい人が考案。
最大パケットが255byteの条件下では、最悪でも元データ+5に収めることを可能にしました。
本題
SLIP
では、もう少し細かい話をしていきます。
データが連続して送られてくる状況では、どこからどこまでがパケットか分からなくなります。
(0101011011101から必要なデータはこれとこれ、なんてわからないですよね）
そこで、特定の文字(デリミタ)を目印にする「SLIP」というシンプルな方法が考案されました。
データ中にデリミタ0xFFで挟まれた部分をパケットとして認識するという感じです。
SLIPはデータ中にデリミタが出現した場合、ほかの文字に置換します。(例 0xFF -> 0x01FD)
1byteのデリミタを2byteで置き換えるので、全てがデリミタと同じ値のデータではサイズが2倍になってしまいます。
COBS
エンコード
COBSはこの課題をクリアしたエンコード方式です。
ざっくりと言うと、デリミタの出現を置換で表現したSLIPに対し、ブロックの長さで表現したのがCOBSです。
COBSでは1パケットを複数のブロックに分けます。
また、MBS(Max Block Size)を定義しておきます。
具体的なエンコード方式は以下のようになります。
- 元データに末尾にデリミタを追加
- 元データを先頭からサーチします。
・デリミタが出現した
・連続してMBS分、読み込んだ
上の2パターンの内、どちらかを満たした場合ブロックを確定 - ・デリミタが出現したブロックはデリミタを削除。
・MBS読み込んだブロックはなにもしない - 各ブロックの長さを表すデータをブロックの先頭に挿入。これをOHB(OverHead Byte)といいます
- 以下2~4を元データ末尾まで繰り返す
デコード
デコードの場合はOHBを読み込み、各OHB分のブロックを切り取ります。
ここでOHBがMBS未満ならば、デリミタが出現したデータとみなしてブロックの末尾にデリミタを追加します。
もし、MBSの場合はデリミタ未出現として操作はしません。
この操作をOHB後のデータがデリミタを指すまで繰り返します。
##Pythonによる実装
def blockize_data(data, delimiter, mbs):
blocks = []
block = ''
delimiter_found = False
# Step 1: Append delimiter to the end of the data
data += delimiter
# Step 2 and 3: Search for delimiter or consecutive non-delimiter characters
for char in data:
if char == delimiter:
if block:
blocks.append(block)
block = ''
delimiter_found = True
elif delimiter_found or len(block) == mbs:
blocks.append(block)
block = char
delimiter_found = False
else:
block += char
# Step 4: Output blocks
for block in blocks:
if block.endswith(delimiter):
block_size = len(block) - 1
block = block[:-1]
else:
block_size = len(block)
print(f"OH: {block_size}")
print(block)
# Step 5: Append delimiter to the end
print(f"OH: 0")
print(delimiter)
参考文献
Consistent Overhead Byte Stuffing
最後に
記事の誤り等がありましたら、教えていただけたら幸いです。
大学では衛星の開発と衛星データの処理をやってます。
中々大変です