硬汉嵌入式论坛

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

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

  [复制链接]

1万

主题

7万

回帖

11万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
111540
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

主题

84

回帖

96

积分

初级会员

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

Consistent Overhead Byte Stuffing - Wikipedia.pdf

519.57 KB, 下载次数: 290

回复

使用道具 举报

1万

主题

7万

回帖

11万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
111540
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非常多时 确实效率高多了
回复

使用道具 举报

757

主题

1049

回帖

3325

积分

管理员

Rank: 9Rank: 9Rank: 9

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

回复

使用道具 举报

0

主题

4

回帖

4

积分

新手上路

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

使用道具 举报

3

主题

70

回帖

79

积分

初级会员

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

使用道具 举报

7

主题

134

回帖

155

积分

初级会员

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

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

使用道具 举报

9

主题

135

回帖

162

积分

初级会员

积分
162
发表于 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

主题

23

回帖

23

积分

新手上路

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

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

使用道具 举报

0

主题

23

回帖

23

积分

新手上路

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

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

使用道具 举报

85

主题

774

回帖

1029

积分

至尊会员

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

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

使用道具 举报

9

主题

135

回帖

162

积分

初级会员

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

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

使用道具 举报

9

主题

135

回帖

162

积分

初级会员

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

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

使用道具 举报

85

主题

774

回帖

1029

积分

至尊会员

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

ppp编码没了解过
回复

使用道具 举报

14

主题

65

回帖

107

积分

初级会员

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

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

使用道具 举报

9

主题

135

回帖

162

积分

初级会员

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

使用道具 举报

9

主题

135

回帖

162

积分

初级会员

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

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

2023-03-02_151746.png
回复

使用道具 举报

1

主题

16

回帖

19

积分

新手上路

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

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

使用道具 举报

1

主题

16

回帖

19

积分

新手上路

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

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

使用道具 举报

0

主题

27

回帖

27

积分

新手上路

积分
27
发表于 2024-5-31 15:52:22 | 显示全部楼层
我来转译一下
回复

使用道具 举报

0

主题

27

回帖

27

积分

新手上路

积分
27
发表于 2024-5-31 15:53:30 | 显示全部楼层
我来转译一下
回复

使用道具 举报

8

主题

151

回帖

175

积分

初级会员

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

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

使用道具 举报

29

主题

178

回帖

265

积分

高级会员

积分
265
发表于 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结束

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

使用道具 举报

5

主题

25

回帖

40

积分

新手上路

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

使用道具 举报

3

主题

56

回帖

65

积分

初级会员

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

使用道具 举报

1万

主题

7万

回帖

11万

积分

管理员

Rank: 9Rank: 9Rank: 9

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

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

使用道具 举报

12

主题

37

回帖

73

积分

初级会员

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

使用道具 举报

12

主题

37

回帖

73

积分

初级会员

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

使用道具 举报

1万

主题

7万

回帖

11万

积分

管理员

Rank: 9Rank: 9Rank: 9

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

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

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-11-1 06:57 , Processed in 0.964585 second(s), 28 queries .

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2023, Tencent Cloud.

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