An efficient method to escape multiple characters

[gspeed]

Hello,

Recently I was faced with the task of escaping multiple chars in a frame payload, and it has to be done with minimal worst-case overhead on a microcontroller. That rules out classic escape chars since it has a worst-case overhead of 100%.

I was looking at https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing, which escapes only one char, then came up with the realization that if one limits its block length to less than 254, the overhead byte is likewise limited in range, and the unused bits can be used for recovering the original char. I searched the web but couldn't find anything, so I decided to post it here, in case anyone finds it useful:

1. Suppose we need to escape 3 bits (0x00-0x07)

2. To encode a string, first append a 0x00, then break it into blocks of either (a) 30 non-escape chars, or (b) 0-29 non escape chars + 1 escape char. For (a), prepend the block with 0xF8; for (b), move the escape char to the beginning of block, and set its high 5 bit to the block length (1-30).

3. To decode a string, read it sequentially. If the current char is 0xF8, drop it and output the next 30 chars. If the current char is less than 0xF8, let the low 3 bit of the current char be the non-escaped char, the high 5 bit be the block length; output the next (block length - 1) chars, then append the non-escaped char. At the end, remove the prepended 0x00.

4. Obviously you could modify how many bits are used. If you need to escape other specific chars, simply exchange them with 0x00-0x07 after encode, and exchange again before decode.

I call it the PolyCOBS algorithm, since it's a strict extension of the original COBS (if you set number of bits to zero, it's exactly equivalent to the original COBS).

In the case above (3 bits), the worst-case overhead is ~3%. The smaller block length also helps decoding on microcontrollers, making https://github.com/Dirbaio/rcobs almost unnecessary, but if you are really limited in RAM, you can even combine that.

[westfw]

Can you still encode/decode using a state machine in the transmit/receive stream?  I couldn't tell immediately from the wikipedia article...
Needing a separate step seems to violate the efficiency principle of touching the data as little as possible...

[gspeed]

Can you still encode/decode using a state machine in the transmit/receive stream?  I couldn't tell immediately from the wikipedia article...
Needing a separate step seems to violate the efficiency principle of touching the data as little as possible...

Yes of course, streaming is definitely possible, decoding is straightforward; for encoding you need to maintain a ~30 byte buffer.

The separate step (I assume you're talking about the appended 0x00) is purely theoretical. For implementation it's possible to inline the EOF check.

[peter-h]

Reminds me of the SDLC bit stuffing method

[voltsandjolts]

In the case above (3 bits), the worst-case overhead is ~3%. The smaller block length also helps decoding on microcontrollers, making https://github.com/Dirbaio/rcobs almost unnecessary, but if you are really limited in RAM, you can even combine that.

Example COBS overhead for some random content and random length (max 200 bytes) messages:

Code: [Select]

Test            Message length          Encoded length          Overhead
0               120                     121                     1       (0.83%)
1               137                     138                     1       (0.73%)
2               178                     179                     1       (0.56%)
3               23                      24                      1       (4.35%)
4               29                      30                      1       (3.45%)
5               101                     102                     1       (0.99%)
6               151                     152                     1       (0.66%)
7               50                      51                      1       (2.00%)
8               155                     156                     1       (0.65%)
9               65                      66                      1       (1.54%)
10              141                     142                     1       (0.71%)
11              45                      46                      1       (2.22%)
12              169                     170                     1       (0.59%)
13              168                     169                     1       (0.60%)
14              168                     169                     1       (0.60%)
15              21                      22                      1       (4.76%)
16              35                      36                      1       (2.86%)
17              50                      51                      1       (2.00%)
18              46                      47                      1       (2.17%)
19              52                      53                      1       (1.92%)
20              56                      57                      1       (1.79%)
21              63                      64                      1       (1.59%)
22              40                      41                      1       (2.50%)
23              125                     126                     1       (0.80%)
24              184                     185                     1       (0.54%)
25              44                      45                      1       (2.27%)
26              194                     195                     1       (0.52%)
27              37                      38                      1       (2.70%)
28              48                      49                      1       (2.08%)
29              157                     158                     1       (0.64%)
30              5                       6                       1       (20.00%)
31              177                     178                     1       (0.56%)
32              103                     104                     1       (0.97%)
33              149                     150                     1       (0.67%)
34              168                     169                     1       (0.60%)
35              99                      100                     1       (1.01%)
36              48                      49                      1       (2.08%)
37              92                      93                      1       (1.09%)
38              74                      75                      1       (1.35%)
39              132                     133                     1       (0.76%)
40              175                     176                     1       (0.57%)
41              65                      66                      1       (1.54%)
42              41                      42                      1       (2.44%)
43              193                     194                     1       (0.52%)
44              10                      11                      1       (10.00%)
45              48                      49                      1       (2.08%)
46              184                     185                     1       (0.54%)
47              192                     193                     1       (0.52%)
48              194                     195                     1       (0.52%)
49              16                      17                      1       (6.25%)

That was produced by the attached script.
Maybe you can modify it to demonstrate your idea?

[gspeed]

Example COBS overhead for some random content and random length (max 200 bytes) messages:

That was produced by the attached script.
Maybe you can modify it to demonstrate your idea?

COBS has a worst case overhead of floor(n/254) + 1, where n is the length.

For PolyCOBS with b bits, the formula becomes floor(n/blklen) + 1 where blklen = 2^(8-b)-2. For 3 bits, the worst case overhead is floor(n/30) + 1, which is 3.3% for large n.

I have modified your script and here's the output:

Code: [Select]

An modified example from the Cheshire & Baker COBS paper (figure 3):
Message input: 45 00 00 2C 4C 79 00 00 40 06 4F 37
COBS output: 10 45 08 20 2C 4C 79 08 16 40 18 4F 37 <<< Look, no 0x00-0x07 bytes!
COBS decoded: 45 00 00 2C 4C 79 00 00 40 06 4F 37
Message decoded fine

Test Message length Encoded length Overhead
0 149 151 2 (1.34%)
1 40 41 1 (2.50%)
2 34 36 2 (5.88%)
3 67 69 2 (2.99%)
4 46 47 1 (2.17%)
5 21 22 1 (4.76%)
6 25 26 1 (4.00%)
7 138 142 4 (2.90%)
8 198 202 4 (2.02%)
9 192 195 3 (1.56%)
10 51 52 1 (1.96%)
11 109 112 3 (2.75%)
12 96 99 3 (3.12%)
13 3 4 1 (33.33%)
14 60 62 2 (3.33%)
15 16 17 1 (6.25%)
16 181 186 5 (2.76%)
17 99 102 3 (3.03%)
18 145 149 4 (2.76%)
19 41 43 2 (4.88%)
20 57 59 2 (3.51%)
21 178 182 4 (2.25%)
22 113 117 4 (3.54%)
23 199 204 5 (2.51%)
24 95 97 2 (2.11%)
25 37 38 1 (2.70%)
26 83 85 2 (2.41%)
27 114 117 3 (2.63%)
28 119 123 4 (3.36%)
29 191 194 3 (1.57%)
30 136 139 3 (2.21%)
31 21 22 1 (4.76%)
32 89 92 3 (3.37%)
33 91 93 2 (2.20%)
34 181 184 3 (1.66%)
35 66 68 2 (3.03%)
36 84 86 2 (2.38%)
37 80 82 2 (2.50%)
38 34 35 1 (2.94%)
39 75 77 2 (2.67%)
40 25 26 1 (4.00%)
41 192 196 4 (2.08%)
42 97 100 3 (3.09%)
43 134 139 5 (3.73%)
44 144 149 5 (3.47%)
45 48 50 2 (4.17%)
46 48 49 1 (2.08%)
47 143 145 2 (1.40%)
48 89 91 2 (2.25%)
49 140 144 4 (2.86%)

I do have some C code which I intend to post later when I have the time.