硬汉嵌入式论坛

 找回密码
 立即注册
查看: 10186|回复: 37
收起左侧

高效可靠的数据字节编码算法COBS,可用于串口通信

  [复制链接]

1万

主题

7万

回帖

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
121991
QQ
发表于 2022-9-13 05:24:04 | 显示全部楼层 |阅读模式
https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing

以modbus rtu通信为例,一般是3.5字符作为帧间隔区分,而使用COBS就不需要这样了,他是将范围 [0,255] 内的任意字节字符串转换为 [1,255] 范围内的字节。从数据中消除所有0,现在可以使用0来明确标记转换后数据的结束
.






[C] 纯文本查看 复制代码
#include <stddef.h>
#include <stdint.h>
#include <assert.h>
 
/** COBS encode data to buffer
        @param data Pointer to input data to encode
        @param length Number of bytes to encode
        @param buffer Pointer to encoded output buffer
        @return Encoded buffer length in bytes
        @note Does not output delimiter byte
*/
size_t cobsEncode(const void *data, size_t length, uint8_t *buffer)
{
        assert(data && buffer);
 
        uint8_t *encode = buffer; // Encoded byte pointer
        uint8_t *codep = encode++; // Output code pointer
        uint8_t code = 1; // Code value
 
        for (const uint8_t *byte = (const uint8_t *)data; length--; ++byte)
        {
                if (*byte) // Byte not zero, write it
                        *encode++ = *byte, ++code;
 
                if (!*byte || code == 0xff) // Input is zero or block completed, restart
                {
                        *codep = code, code = 1, codep = encode;
                        if (!*byte || length)
                                ++encode;
                }
        }
        *codep = code; // Write final code value
 
        return (size_t)(encode - buffer);
}
 
/** COBS decode data from buffer
        @param buffer Pointer to encoded input bytes
        @param length Number of bytes to decode
        @param data Pointer to decoded output data
        @return Number of bytes successfully decoded
        @note Stops decoding if delimiter byte is found
*/
size_t cobsDecode(const uint8_t *buffer, size_t length, void *data)
{
        assert(buffer && data);
 
        const uint8_t *byte = buffer; // Encoded input byte pointer
        uint8_t *decode = (uint8_t *)data; // Decoded output byte pointer
 
        for (uint8_t code = 0xff, block = 0; byte < buffer + length; --block)
        {
                if (block) // Decode block byte
                        *decode++ = *byte++;
                else
                {
                        if (code != 0xff) // Encoded zero, write it
                                *decode++ = 0;
                        block = code = *byte++; // Next block length
                        if (!code) // Delimiter code found
                                break;
                }
        }
 
        return (size_t)(decode - (uint8_t *)data);
}

回复

使用道具 举报

0

主题

4

回帖

4

积分

新手上路

积分
4
发表于 2022-9-13 08:05:23 | 显示全部楼层
这个方便
回复

使用道具 举报

4

主题

121

回帖

133

积分

初级会员

积分
133
发表于 2022-9-13 09:18:26 | 显示全部楼层
网页版本PDF可以参考!

Consistent Overhead Byte Stuffing - Wikipedia.pdf

519.57 KB, 下载次数: 346

回复

使用道具 举报

1万

主题

7万

回帖

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
121991
QQ
 楼主| 发表于 2022-9-13 17:29:55 | 显示全部楼层
滴滴滴 发表于 2022-9-13 09:18
网页版本PDF可以参考!

谢谢整理分享。
回复

使用道具 举报

1

主题

71

回帖

74

积分

初级会员

积分
74
发表于 2022-9-15 15:43:47 | 显示全部楼层
这种稍难理解
跟一般用c0 做起始 终止 db dc dd 转义 比起来有什么优势
回复

使用道具 举报

1

主题

17

回帖

20

积分

新手上路

积分
20
发表于 2022-9-15 17:14:29 | 显示全部楼层
252514251 发表于 2022-9-15 15:43
这种稍难理解
跟一般用c0 做起始 终止 db dc dd 转义 比起来有什么优势

你这种是不是交通信号机的协议?
回复

使用道具 举报

1

主题

71

回帖

74

积分

初级会员

积分
74
发表于 2022-9-15 19:55:09 | 显示全部楼层
qq371833846 发表于 2022-9-15 17:14
你这种是不是交通信号机的协议?

算比较标准的转义吧
COBS看代码算法不大好理解,但在 数据中c0非常多时 确实效率高多了
回复

使用道具 举报

761

主题

1054

回帖

3342

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3342
发表于 2022-9-16 00:04:01 | 显示全部楼层
我觉得优势是
1、它只增加固定开销的字节,因此接收和解压不需要预留2倍最大帧长的缓冲区。
2、0结束很香,很多字符串处理函数可以使用

回复

使用道具 举报

0

主题

4

回帖

4

积分

新手上路

积分
4
发表于 2022-9-19 23:14:46 | 显示全部楼层
一直在想是不是有一种方法可以去掉超时来区分十六进制数据帧的办法
没想到竟然有人创作了,太流弊了,佩服佩服~
同时也感谢楼主分享~~
回复

使用道具 举报

3

主题

96

回帖

105

积分

初级会员

积分
105
发表于 2022-9-27 07:54:11 来自手机 | 显示全部楼层
这个能实时解析吗?如果要收齐数据包才能解析的话,数据输出又占一份ram,数据包大的话,对ram小的MCU来说压力比较大了,还不如自己做个转义方便,实时解析不会占用2份ram,而且这种转义效率不高
回复

使用道具 举报

7

主题

171

回帖

192

积分

初级会员

积分
192
发表于 2022-10-7 14:59:16 | 显示全部楼层
maoxia007 发表于 2022-9-19 23:14
一直在想是不是有一种方法可以去掉超时来区分十六进制数据帧的办法
没想到竟然有人创作了,太流弊了,佩服 ...

早就有方法了,都是通过头+数据结构,头中有包序号和包长度,接收就先接固定头,然后从头中得到到大小
回复

使用道具 举报

11

主题

157

回帖

190

积分

初级会员

积分
190
发表于 2022-10-10 09:19:57 | 显示全部楼层
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第一个0出现的位置,然后是实际的数据,到0的位置时,填充后续数据中下一个0的位置,直到最后数据结束,编码增加一个0字节作为编码结束。
想法很巧妙,最多也就是额外占用两个字节,秒杀了ppp编码的利用率,编码解码也很简单。
然而,因为使用了一个字节来标记数据中0的位置,就导致实际数据的长度限制在了256字节以内。如果使用两个字节标记位置,利用率就和ppp编码一样了。
我实际使用的通信协议,都是自定义的,大部分数据都是几百到上K字节,分包虽然开发难度不大,但是维护、效率和对外接口的沟通等等成本很高,大包数据实属无奈。
有没有像这样简单高效,又能支持几K以上数据的编码方式呢。
回复

使用道具 举报

1

主题

19

回帖

22

积分

新手上路

积分
22
发表于 2022-10-16 15:30:37 | 显示全部楼层
好东西,计划项目上使用
回复

使用道具 举报

0

主题

49

回帖

49

积分

初级会员

积分
49
发表于 2022-10-17 09:54:43 | 显示全部楼层
amfy 发表于 2022-10-10 09:19
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第 ...

如果做成每255个字节作为一个段,每个段都用这个方式进行标记的话是不是能满足你的要求呢
回复

使用道具 举报

0

主题

49

回帖

49

积分

初级会员

积分
49
发表于 2022-10-17 11:20:39 | 显示全部楼层
Zhyolo 发表于 2022-10-17 09:54
如果做成每255个字节作为一个段,每个段都用这个方式进行标记的话是不是能满足你的要求呢

刚分析了下提供的代码,我上面说的这个方式好像是实现了的
回复

使用道具 举报

85

主题

806

回帖

1061

积分

至尊会员

积分
1061
发表于 2022-10-17 15:19:50 | 显示全部楼层
amfy 发表于 2022-10-10 09:19
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第 ...

有幸接触到一些老外牛逼的模块,数据量大他们的协议都是自定义,而且预留很多保留位便于扩展。老外基础研究比我们深入,他们都没轻易用什么大包支持的标准协议,应该是没有
回复

使用道具 举报

11

主题

157

回帖

190

积分

初级会员

积分
190
发表于 2022-10-17 17:05:49 | 显示全部楼层
Zhyolo 发表于 2022-10-17 11:20
刚分析了下提供的代码,我上面说的这个方式好像是实现了的

那就是数据分包了,这个东西原理简单,实现起来也不算难。
只是我们开发产品经常和客户对接通信协议,对方做什么开发的都有,网页,plc,c++等。给他们讲明白现在的协议就已经很费劲了,要让他们再开发分包功能,估计更加要命。
回复

使用道具 举报

11

主题

157

回帖

190

积分

初级会员

积分
190
发表于 2022-10-17 17:08:38 | 显示全部楼层
庄永 发表于 2022-10-17 15:19
有幸接触到一些老外牛逼的模块,数据量大他们的协议都是自定义,而且预留很多保留位便于扩展。老外基础研 ...

ppp编码支持无限大的包,
问题是数据包大了之后,对通信的稳定性要求就会很高。重传的代价也会很大。
这东西没有万金油,只有最适合自己的。
回复

使用道具 举报

85

主题

806

回帖

1061

积分

至尊会员

积分
1061
发表于 2022-10-17 21:55:40 | 显示全部楼层
amfy 发表于 2022-10-17 17:08
ppp编码支持无限大的包,
问题是数据包大了之后,对通信的稳定性要求就会很高。重传的代价也会很大。
...

ppp编码没了解过
回复

使用道具 举报

14

主题

69

回帖

111

积分

初级会员

积分
111
发表于 2022-11-4 13:06:23 | 显示全部楼层
amfy 发表于 2022-10-10 09:19
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第 ...

并没有限制在256内,只不过每增加256字节数据要增加一字节额外编码
回复

使用道具 举报

11

主题

157

回帖

190

积分

初级会员

积分
190
发表于 2023-3-2 13:06:42 | 显示全部楼层
今天和某个牛逼的AI讨论了cobs编码, 受到了很大的启发. 想到了一种扩展cobs编码, 能支持无限长的数据长度. 依旧保持超高的字节效率.
现在的编码方式, 第一个字节表明后续第一个0出现的位置, 在最后编码结尾00之后, 增加一个字节, 表明在本段编码结束之后,是否还有下一段编码. 比如0a表示没有下一段数据了, 0c表示还有下一段数据.
如果是0c,则从下一个字节开始, 重新执行一遍解码, 结束之后再判断下一个字节是0a还是0c, 直到最后是0a为止.
这样,原有的编码机制和传输机制不变, 如果程序是传统cobs编码机制, 则只需要遵循传统, 什么也不需要改动, 如果程序支持扩展的cobs编码, 则可以传输无限长的数据.
这样, 每256字节仅需要增加一个字节的额外消耗, 不增加编码解码的负担. 可以无缝兼容已有的cobs设备, 对方不需要做任何改动.
回复

使用道具 举报

11

主题

157

回帖

190

积分

初级会员

积分
190
发表于 2023-3-2 15:22:07 | 显示全部楼层
apleilx 发表于 2022-11-4 13:06
并没有限制在256内,只不过每增加256字节数据要增加一字节额外编码

一开始我一直都没看懂, 还是水平问题. 中间找资料也没看到明确说支持超过254长度的信息. 看你说的这个, 仔细琢磨了一下, 确实是支持超过254的.
我又找了相关的论文, 找到了明确支持超过254字节的例子. 在我看来, 目前这个就已经很好了, 足够简单, 足够灵活.

2023-03-02_151746.png
回复

使用道具 举报

2

主题

18

回帖

24

积分

新手上路

积分
24
发表于 2024-5-26 16:59:52 | 显示全部楼层
amfy 发表于 2022-10-10 09:19
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第 ...

这就是嵌入式嘛,数据处理部分。楼主分析的很好
回复

使用道具 举报

2

主题

18

回帖

24

积分

新手上路

积分
24
发表于 2024-5-26 17:15:37 | 显示全部楼层
amfy 发表于 2023-3-2 15:22
一开始我一直都没看懂, 还是水平问题. 中间找资料也没看到明确说支持超过254长度的信息. 看你说的这个,  ...

但是他这个是不是限定了,只能最后一个字节是0,其他字节都不是0的长数据包才能这样编码呢?
回复

使用道具 举报

0

主题

39

回帖

39

积分

新手上路

积分
39
发表于 2024-5-31 15:52:22 | 显示全部楼层
回复

使用道具 举报

0

主题

39

回帖

39

积分

新手上路

积分
39
发表于 2024-5-31 15:53:30 | 显示全部楼层
回复

使用道具 举报

9

主题

169

回帖

196

积分

初级会员

积分
196
发表于 2024-5-31 17:36:50 | 显示全部楼层
amfy 发表于 2022-10-10 09:19
每次看到这个帖子都会琢磨一下,今天总算是看明白这个编码的算法了:编码后数据的第一个字节,标明数据中第 ...

这样应该可以,00表示一帧数据结束, 01~0xFE表示下一个0数据的位置, 0xFF表示此后的254字节内没有0x00,然后再用一个字节表示接下来0的位置
回复

使用道具 举报

41

主题

244

回帖

367

积分

高级会员

积分
367
发表于 2024-6-29 11:22:53 | 显示全部楼层
tcs_stm32 发表于 2024-5-31 17:36
这样应该可以,00表示一帧数据结束, 01~0xFE表示下一个0数据的位置, 0xFF表示此后的254字节内没有0x00, ...

你这个设计的话,万一后面254字节还是没有数据0呢

我觉着可以在0x00结尾之后加一个字节,用于表示分段。
0x00表示本段结束
如果后面跟着0x00表示后续没有新段了,接收结束
如果后面跟着0x01表示后续还有新段,那边再按照这个逻辑进行解析,直至到0x00 0x00结束

就是在原有基础上再加一个字节
回复

使用道具 举报

9

主题

48

回帖

75

积分

初级会员

积分
75
发表于 2024-7-19 16:10:14 | 显示全部楼层
mark一下,从未了解过的算法
回复

使用道具 举报

4

主题

66

回帖

78

积分

初级会员

积分
78
发表于 2024-8-6 11:34:48 | 显示全部楼层
这个COBS编码是针对00来的,那同样也可以针对其他的数据来呢,比如FF啥的
回复

使用道具 举报

1万

主题

7万

回帖

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
121991
QQ
 楼主| 发表于 2024-8-7 09:26:34 | 显示全部楼层
小麦吉 发表于 2024-8-6 11:34
这个COBS编码是针对00来的,那同样也可以针对其他的数据来呢,比如FF啥的

00做结束后,效果更好些,因为字符串处理结束符也是‘\0’ = 0
回复

使用道具 举报

13

主题

39

回帖

78

积分

初级会员

积分
78
发表于 2024-9-23 18:04:27 | 显示全部楼层
挖个坟,4个数据编码函数返回的值是5,转换后的buf第一个数指示第一次出现0的字节数,最后一个字节数是0,也就是说,实际长度应该是6吧,按函数返回的5来发送的话,缺了最后一个0,解码会出错吗?没太理解为什么这里会少1
回复

使用道具 举报

13

主题

39

回帖

78

积分

初级会员

积分
78
发表于 2024-9-23 18:07:23 | 显示全部楼层
编码函数返回的是长度吗?4个字节编码后返回的是5,但是算上结尾的0长度应该是6才对,缺个末尾的0会影响解码吗?不太理解为什么会少1。
回复

使用道具 举报

1万

主题

7万

回帖

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
121991
QQ
 楼主| 发表于 2024-9-24 10:03:57 | 显示全部楼层
紫苑Yoo梦 发表于 2024-9-23 18:04
挖个坟,4个数据编码函数返回的值是5,转换后的buf第一个数指示第一次出现0的字节数,最后一个字节数是0, ...

这个我自己还真没测试过。
回复

使用道具 举报

30

主题

445

回帖

535

积分

金牌会员

积分
535
发表于 2025-5-13 11:25:12 | 显示全部楼层
小麦吉 发表于 2024-8-6 11:34
这个COBS编码是针对00来的,那同样也可以针对其他的数据来呢,比如FF啥的

是不是可以在编码后所有数据都抬高0xFF,就可以用0xFF做间隔了
回复

使用道具 举报

1

主题

19

回帖

22

积分

新手上路

积分
22
发表于 4 天前 | 显示全部楼层
高效可靠的数据字节编码算法COBS,可用于串口通信
回复

使用道具 举报

1

主题

100

回帖

103

积分

初级会员

积分
103
发表于 4 天前 | 显示全部楼层
本帖最后由 dukelec 于 2026-4-7 17:53 编辑

比 ppp 转译后数据长很多要好不少

除了开头和结尾共两个字节协议开销,如果每连续 254 字节没有 0, 那么要多插入一个字节(对应楼主位 example 9 和 10 的尾部红色字节)
虽然插入的不多,但中间只要插入一个字节,就需要内存拷贝

即便 payload 数据长度不超过 254 字节,如果 254 字节都是 0, 那么处理的时候,要循环 254 次,并替换数据内容,对 mcu 来说开销也不小

其实串口有一个特殊字符:break 字符,使用 break 字符来分帧就不需要转译
由于 break 字符不方便以字节数据存储,所以底层串口收到数据后,确认数据无误后,可保存为文件或转成其它以块为单位的通讯方式,
譬如 msgpack 文件格式、udp 数据包、usb bulk 数据包 等等

break 字符是 10 个 bit 长度,电平为 0 的特殊串口字符(10 bits 是对于 8N1 来说,停止位也变成了 0)
进一步思考,使用 10 个 bit 长度,电平为 1 的空闲字符来分帧是否可以呢?
当然可以,和 break 字符没有区别,而且不需要浪费 break 字符,break 字符可以用于更重要的场合
(譬如嵌入式 linux 系统是使用 break 字符做为魔法键,可以调用内核钩子执行一些紧急操作)

空闲字符来分帧实际上就是 modbus 的方式

为何很多人不喜欢使用 modbus 的分帧方式:
1. modbus 定义死了分帧的空闲时间长度为 1.5 字节,发送为 3.5 字节,按照标准,mcu 要启一个定时器去处理接收和发送,很麻烦,如果 modbus 定义一个字节时间就为空闲会好很多
2. 单纯不喜欢 modbus:modbus 标准不是 8N1, 启用校验位开销大;协议不是 ios/osi 架构,各种线圈概念过时

如果串口也能有一个更通用的底层数据包格式,那么 mcu 这种实时性好的器件,靠空闲分帧不会有问题
对于 pc 来说,只要使用专门收发这种通用数据包的 usb 转串口工具,以数据包为最小单位,而不是传统以字节为最小单位的串口工具,也不会有问题
更进一步,这种通用的串口数据包直接映射为 IP/UDP 数据包发送给 pc

非常有潜力成为这种通用的串口底层的数据包格式 —— CDBUS/CDNET:
https://forum.anfulai.cn/forum.p ... 51668&fromuid=85792


回复

使用道具 举报

2

主题

9

回帖

15

积分

新手上路

积分
15
发表于 3 天前 | 显示全部楼层
如果数据都是0的话。好像效率有点低。感觉传字符串合适。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|Archiver|手机版|硬汉嵌入式论坛

GMT+8, 2026-4-11 05:53 , Processed in 6.527669 second(s), 27 queries .

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2023, Tencent Cloud.

快速回复 返回顶部 返回列表