Consistent Overhead Byte Stuffing学习

简介

Consistent Overhead Byte Stuffing(COBS)是一种实现串行链路上帧识别（数据透传）的编码算法，作者Stuart Cheshire在1997年发表的《Consistent Overhead Byte Stuffing》的技术报告中首次提出。

在常见的数据透传实现，如PPP协议，PPP协议通过开始和结束的标志字段Flag（0x7E）标识一帧的边界，因此对数据载荷包含的标志字段需要进行相应的转义，考虑最差的情况，所有的净荷都是标志字符，会直接引入100%的插入字符，HDLC的零比特填充法最坏的情况也会引入20%的插入信息。而且，由于头尾都有标志字段，接收端要准备至少最大帧长长度的缓存才能保证正常接收。在ISM频段工作的许多协议，受此影响一定程度上大大降低了最大帧长。

在网络设备中，数据是突发且随机的，传统的数据链路层协议的透传方案会导致抖动且无法预测的额外开销。

算法原理

  1. 读取一个上层交付的数据包，在包末尾添加一个0x00（逻辑上添加）
  2. 将数据按照所有的0x00字节进行分块，称为chunk（分成以0x00结尾的数据块，每个块只有一个0x00，若以0x00开头，则分为长度为1的chunk）
  3. COBS将每个chunk编码为变长的COBS码块，每个COBS码块开头有一个编码字节，指示原chunk的长度，并从COBS码块中去除最后的0x00
    • 长度为n，且n小于等于254的chunk，映射为一个长度为n的chunk块，隐含一个0x00的结尾
    • 长度为n，且n大于254的chunk，会被映射为多个chunk块，完整的块，块首的编码为0xff，表示之后由254个不为0的数据，且后续一个块依然属于一个chunk
  4. 编码后每一个COBS码块都不包含0x00，之后就可以使用0x00来区分包的边界
  5. 每一个COBS块只在块首包含一个编码用字节，这个编码字节指示的是该chunk包含的字节数，并将zero byte省略（implict）因为一个块最少包含1个长度（zero，表明这个分块只有一个zero，所以编码字节的范围为0x01~0xFE）
    • 0x00: 不支持
    • 0x01：表示一个zero byte
    • n: 表示后面有n-1个数据
    • 0xFF 表示后面后254个不以0结尾的数据（大于254的块分块结果，和后面的COBS code blocks是连续的，不在中间插入zero byte）
  6. 这样一个长度小于等于254的chunk可以都是无overhead的完成编码，只有当chunk大于254，编码字节为0xff时才会引入overhead

算法改进

在使用一个编码字节表示长度，并隐含表示0，最差的情况是每254字节一个额外开销，在此基础上，如果保留部分编码字节的值用于其他用于，如表示结尾隐含两个0，或者表示结尾不隐含0，这样编码字节表示的长度变短，最差情况下的开销会增多，但根据数据分布，平均开销会相应下降。

比如，在网络数据转发应用中，若COBS的净荷为IP数据报，在IP数据报中包含许多连0，使用一对二的编码字节甚至可以实现对数据的压缩。

数据链路层

编码过程

  1. 初始化长度为255的缓存（缓存的第一个字节为计数器）
  2. 从字节流中读入一个字符（先不写入缓存），计数器加一
  3. 若计数器达到255，进行步骤5
  4. 若字符为0x00，进行步骤5，否则回到步骤2
  5. 完成一个码块编码（编码字节为计数器，数据为缓存），向下传递，回到步骤1，否则进行步骤4
  6. 完成数据编码后，末尾添加一个0x00分割包

解码过程

物理层

在数据链路层是按字节，区分不同的数据包，下发到物理层后还要完成按bit识别一帧数据，传统方法如高级数据链路控制协议（HDLC）使用的是零比特填充法进行转义。经过COBS编码的数据中本身就不会出现为0的字节，如果在物理层标识数据帧的话，在数据部分不会出现超过14个连零的情况（0b1000,0000,0000,0001），在数据帧之间使用两个字节(0b1000,0000,0000,0000)十五个连0标识边界，针对这个帧边界标识法，作者提出了异步与同步实现两种。

  1. 同步COBS比特边界
    在同步情况下，一帧数据发送完毕后，发送方循环发送0b1000,0000,0000,0000，表示线路的IDLE，当需要发送数据时，需要等待当前的边界标识发送完毕，最差的情况下会延迟16个bit的时间才能发送。

  2. 异步COBS比特边界
    在异步的情况下，一帧数据发送完毕后，发送方在发送完0b1000,0000,0000,0000之后，继续发送0标识线路的IDLE，接收方当检测到超过15bit连零时判断接收成功，发送方将要发送数据时，再发送一个1bit告知将要发送数据。

C语言实现

编码程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int cobs_encode(uint8_t *buf, int size) {
    uint8_t ram[255];
    uint8_t *cnt_num = (uint8_t *) ram;
    uint8_t *ram_ptr = ram + 1;
    uint8_t *buf_ptr = buf;
    uint8_t *end = buf + size;
    while (buf_ptr < end) {
        (*cnt_num)++;
        if (*buf_ptr == 0) {
            /* 遇到0字节，下发码块 */
            phys_layer(ram, (int) *cnt_num);
            /* 码块初始化 */
            *cnt_num = 0;
            ram_ptr = ram + 1;
        } else {
            /* 不是0的数据可以写入缓存 */
            *ram_ptr++ = *buf_ptr;
            /* 此时缓存中一共有cnt_num个有效数据，当数据个数为254时，下发 */
            if (*cnt_num == 0xfe) {
                (*cnt_num)++;
                /* 下发码块，清空缓存 */
                phys_layer(ram, (int) *cnt_num);
                /* 码块初始化 */
                *cnt_num = 0;
                ram_ptr = ram + 1;
            }
        }
        buf_ptr++;
    }
    /* 结束后直接将当前包下发（数据后添加的逻辑0） */
    (*cnt_num)++;
    phys_layer(ram, (int) *cnt_num);

    /* 传输0，标记数据包边界 */
    ram[0] = 0x00;
    phys_layer(ram, 1);
    return 0;
}

译码程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int cobs_decode(uint8_t *buf, int size) {
    static uint8_t code_byte = 0x00;
    static uint8_t ram [2048] = {0x00};
    static uint8_t *ram_ptr = ram;
    typedef enum {
        STATE_IDLE = 0,
        STATE_RECEIVE_1,
        STATE_RECEIVE_2,
        STATE_BLOCK_END,
    } state_t;
    static state_t state = STATE_IDLE;

    uint8_t *buf_ptr = buf;
    uint8_t *end = buf + size;
    while (buf_ptr < end){
        switch (state) {
            case STATE_IDLE:
                if (*buf_ptr != 0x00) {
                    code_byte = *buf_ptr;
                    state = code_byte < 0xff ? STATE_RECEIVE_1 : STATE_RECEIVE_2;
                } else {
                    state = STATE_IDLE;
                }
                break;
            case STATE_RECEIVE_1:
                code_byte--;
                *ram_ptr++ = *buf_ptr;
                if (code_byte == 1) {
                    *ram_ptr++ = 0x00;
                    state = STATE_BLOCK_END;
                }
                break;
            case STATE_RECEIVE_2:
                code_byte--;
                *ram_ptr++ = *buf_ptr;
                if (code_byte == 1) {
                    state = STATE_BLOCK_END;
                }
                break;
            case STATE_BLOCK_END:
                if (*buf_ptr != 0x00) {
                    code_byte = *buf_ptr;
                    state = code_byte < 0xff ? STATE_RECEIVE_1 : STATE_RECEIVE_2;
                } else { // 识别到数据包结束标志
                    // 去除添加的逻辑0
                    ram_ptr--;
                    // 上报数据
                    dl_layer(ram, (int) (ram_ptr - ram));
                    ram_ptr   = ram;
                    code_byte = 0x00;
                    state     = STATE_IDLE;
                }
                break;
            default:
                state = STATE_IDLE;
                ram_ptr   = ram;
                code_byte = 0x00;
                state     = STATE_IDLE;
        }
        buf_ptr++;
    }
}

参考资料

  1. Cheshire, Stuart; Baker, Mary (April 1999). “Consistent Overhead Byte Stuffing”. IEEE/ACM Transactions on Networking. 7 (2): 159–172. CiteSeerX 10.1.1.108.3143. doi:10.1109/90.769765. S2CID 47267776. Retrieved November 30, 2015.