Consistent overhead byte stuffing
Consistent overhead byte stuffing is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The Consistent Overhead Byte Stuffing (COBS) algorithm is used to demarcate a byte stream into frames. Examples can be found in its Wikipedia article.
- Task
To encode, instances of the byte 0x00 in the unencoded stream are substituted with the number of bytes until the next instance of 0x00 (we'll call this a milestone).
If 0x00 does not appear within the next 254 bytes after a milestone the algorithm must emit an extra milestone at the 255th byte.
Of the encoded output, the first byte is the first milestone, and the final milestone will be the number of bytes until the final byte - 0x00.
- Bonus tasks
- Decode an encoded packet
- Report an error if the final milestone exceeds the length of the end of the packet
- Support encoding with a non-zero marker
C
Taken from the Wikipedia article Consistent Overhead Byte Stuffing.
Encoder:
#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);
}
Decoder:
/** 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);
}
F#
The functions
// Consistent overhead byte stuffing. Nigel Galloway: September 28th., 20
let rec fN g=if Seq.isEmpty g then Seq.empty else let n,_=g|>Seq.indexed|>Seq.find(fun(n,g)->n>253 || g=0uy)
seq{match n with 254->yield 255uy; yield!(g|>Seq.take 254); yield! fN(g|>Seq.skip 254)
|n->yield byte(n+1); yield!(g|>Seq.take n); yield! fN(g|>Seq.skip(n+1))}
let encode g=seq{yield! fN(seq{yield! g; yield 0uy}); yield 0uy}
let fI n=if n then [0uy] else []
let rec fG n g=seq{match Seq.head g with 0uy->() |255uy->yield! fI n; yield! g|>Seq.take 255|>Seq.skip 1; yield! fG false (g|>Seq.skip 255)
|i->yield! fI n; yield! g|>Seq.take(int i)|>Seq.skip 1; yield! fG true (g|>Seq.skip(int i))}
let decode g=fG false g
Tests
let examples = [[0x00uy];
[0x00uy; 0x00uy];
[0x00uy; 0x11uy; 0x00uy];
[0x11uy; 0x22uy; 0x00uy; 0x33uy];
[0x11uy; 0x22uy; 0x33uy; 0x44uy];
[0x11uy; 0x00uy; 0x00uy; 0x00uy];
[0x01uy..0xfeuy];
[0x00uy..0xfeuy];
[0x01uy..0xffuy];
[0x02uy..0xffuy]@[0x00uy];
[0x03uy..0xffuy]@[0x00uy; 0x01uy]]
examples|>List.iter(fun g->printf "\nexample\n "
for n in g do printf "%4d" n
printfn "\nencoded"
let n=encode g
for n in n do printf "%4d" n
printf "\ndecoded\n "
for n in decode n do printf "%4d" n
printfn "")
- Output:
example
0
encoded
1 1 0
decoded
0
example
0 0
encoded
1 1 1 0
decoded
0 0
example
0 17 0
encoded
1 2 17 1 0
decoded
0 17 0
example
17 34 0 51
encoded
3 17 34 2 51 0
decoded
17 34 0 51
example
17 34 51 68
encoded
5 17 34 51 68 0
decoded
17 34 51 68
example
17 0 0 0
encoded
2 17 1 1 1 0
decoded
17 0 0 0
example
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
encoded
255 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 1 0
decoded
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
example
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
encoded
1 255 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 1 0
decoded
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
example
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
encoded
255 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 2 255 0
decoded
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
example
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0
encoded
255 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 1 1 0
decoded
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0
example
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0 1
encoded
254 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 2 1 0
decoded
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0 1
FreeBASIC
Const NULL As Any Ptr = 0
Type ByteArray
dato As Ubyte Ptr
longitud As Integer
capacidad As Integer
End Type
Function CreateByteArray() As ByteArray
Dim As ByteArray arr
arr.capacidad = 16
arr.longitud = 0
arr.dato = Callocate(arr.capacidad)
Return arr
End Function
Sub AddByte(Byref arr As ByteArray, value As Ubyte)
If arr.longitud >= arr.capacidad Then
arr.capacidad *= 2
arr.dato = Reallocate(arr.dato, arr.capacidad)
End If
arr.dato[arr.longitud] = value
arr.longitud += 1
End Sub
Sub FreeByteArray(Byref arr As ByteArray)
If arr.dato <> NULL Then
Deallocate(arr.dato)
arr.dato = NULL
End If
arr.longitud = 0
arr.capacidad = 0
End Sub
Function COBSEncode(Byref dato As ByteArray, delim As Ubyte) As ByteArray
Dim As ByteArray enc = CreateByteArray()
AddByte(enc, 0)
Dim As Integer i, ins = 0, code = 1
Dim As Boolean addLastCode = True
For i = 0 To dato.longitud - 1
Dim As Ubyte bite = dato.dato[i]
If bite <> 0 Then
AddByte(enc, bite)
code += 1
End If
addLastCode = True
If bite = 0 Orelse code = 255 Then
If code = 255 Then addLastCode = False
enc.dato[ins] = code
code = 1
ins = enc.longitud
AddByte(enc, 0)
End If
Next
If addLastCode Then
enc.dato[ins] = code
If delim <> 0 Then
For i = 0 To enc.longitud - 1
enc.dato[i] Xor= delim
Next
End If
AddByte(enc, delim)
Else
If delim <> 0 Then
For i = 0 To enc.longitud - 1
enc.dato[i] Xor= delim
Next
End If
enc.dato[ins] = delim
End If
Return enc
End Function
Function COBSDecode(Byref enc As ByteArray, delim As Ubyte) As ByteArray
If enc.longitud = 0 Orelse enc.dato[enc.longitud - 1] <> delim Then
Print "Error: Invalid encoded data"
Return CreateByteArray()
End If
Dim As ByteArray dec = CreateByteArray()
Dim As ByteArray enc2 = CreateByteArray()
Dim As Integer i, length = enc.longitud - 1
For i = 0 To length - 1
AddByte(enc2, enc.dato[i] Xor Iif(delim <> 0, delim, 0))
Next
Dim As Integer code = 255, block = 0
For i = 0 To length - 1
Dim As Ubyte bite = enc2.dato[i]
If block <> 0 Then
AddByte(dec, bite)
Else
If i + bite > length Then
Print "Error: Marker pointing beyond packet end"
FreeByteArray(dec)
FreeByteArray(enc2)
Return CreateByteArray()
End If
If code <> 255 Then AddByte(dec, 0)
code = bite
block = code
If code = 0 Then Exit For
End If
block -= 1
Next
FreeByteArray(enc2)
Return dec
End Function
Sub PrintByteArrayHex(Byref arr As ByteArray)
Dim As Integer i
If arr.longitud <= 5 Then
For i = 0 To arr.longitud - 1
Print Hex(arr.dato[i], 2);
If i < arr.longitud - 1 Then Print " ";
Next
Print Space(35 - (arr.longitud * 3));
Else
For i = 0 To 4
Print Hex(arr.dato[i], 2); " ";
Next
Print "... ";
For i = arr.longitud - 5 To arr.longitud - 1
Print Hex(arr.dato[i], 2);
If i < arr.longitud - 1 Then Print " ";
Next
Print " ";
End If
End Sub
' Main program
Dim As Integer i, d
Dim As ByteArray examples(10)
For i = 0 To 10 : examples(i) = CreateByteArray() : Next
' Initialize examples
AddByte(examples(0), &h00)
With examples(1)
AddByte(examples(1), &h00): AddByte(examples(1), &h00)
End With
With examples(2)
AddByte(examples(2), &h00): AddByte(examples(2), &h11): AddByte(examples(2), &h00)
End With
With examples(3)
AddByte(examples(3), &h11): AddByte(examples(3), &h22): AddByte(examples(3), &h00): AddByte(examples(3), &h33)
End With
With examples(4)
AddByte(examples(4), &h11): AddByte(examples(4), &h22): AddByte(examples(4), &h33): AddByte(examples(4), &h44)
End With
With examples(5)
AddByte(examples(5), &h11): AddByte(examples(5), &h00): AddByte(examples(5), &h00): AddByte(examples(5), &h00)
End With
For i = 1 To 254 : AddByte(examples(6), i) : Next
For i = 0 To 254 : AddByte(examples(7), i) : Next
For i = 1 To 255 : AddByte(examples(8), i) : Next
With examples(9)
For i = 2 To 255 : AddByte(examples(9), i) :Next
AddByte(examples(9), 0)
End With
With examples(10)
For i = 3 To 255 : AddByte(examples(10), i) : Next
AddByte(examples(10), 0)
AddByte(examples(10), 1)
End With
Dim As Ubyte delims(1) = {0, 2}
For d = 0 To 1
Print "COBS encoding (hex) with delimiter 0x"; Hex(delims(d), 2); ":"
Dim As ByteArray encoded(10)
For i = 0 To 10
encoded(i) = COBSEncode(examples(i), delims(d))
PrintByteArrayHex(examples(i)): Print " -> "; : PrintByteArrayHex(encoded(i))
Print
Next
Print !"\nCOBS decoding (hex) with delimiter 0x"; Hex(delims(d), 2); ":"
For i = 0 To 10
Dim As ByteArray decoded = COBSDecode(encoded(i), delims(d))
PrintByteArrayHex(encoded(i)): Print " -> "; : PrintByteArrayHex(decoded)
Print
FreeByteArray(decoded)
Next
Print
For i = 0 To 10 : FreeByteArray(encoded(i)) : Next
Next
For i = 0 To 10 : FreeByteArray(examples(i)) : Next
Sleep
- Output:
COBS encoding (hex) with delimiter 0x00: 00 -> 01 01 00 00 00 -> 01 01 01 00 00 11 00 -> 01 02 11 01 00 11 22 00 33 -> 03 11 22 02 33 00 11 22 33 44 -> 05 11 22 33 44 00 11 00 00 00 -> 02 11 01 01 01 00 01 02 03 04 05 ... FA FB FC FD FE -> FF 01 02 03 04 ... FB FC FD FE 00 00 01 02 03 04 ... FA FB FC FD FE -> 01 FF 01 02 03 ... FB FC FD FE 00 01 02 03 04 05 ... FB FC FD FE FF -> FF 01 02 03 04 ... FD FE 02 FF 00 02 03 04 05 06 ... FC FD FE FF 00 -> FF 02 03 04 05 ... FE FF 01 01 00 03 04 05 06 07 ... FD FE FF 00 01 -> FE 03 04 05 06 ... FE FF 02 01 00 COBS decoding (hex) with delimiter 0x00: 01 01 00 -> 00 01 01 01 00 -> 00 00 01 02 11 01 00 -> 00 11 00 03 11 22 02 33 00 -> 11 22 00 33 05 11 22 33 44 00 -> 11 22 33 44 02 11 01 01 01 00 -> 11 00 00 00 FF 01 02 03 04 ... FB FC FD FE 00 -> 01 02 03 04 05 ... FA FB FC FD FE 01 FF 01 02 03 ... FB FC FD FE 00 -> 00 01 02 03 04 ... FA FB FC FD FE FF 01 02 03 04 ... FD FE 02 FF 00 -> 01 02 03 04 05 ... FB FC FD FE FF FF 02 03 04 05 ... FE FF 01 01 00 -> 02 03 04 05 06 ... FC FD FE FF 00 FE 03 04 05 06 ... FE FF 02 01 00 -> 03 04 05 06 07 ... FD FE FF 00 01 COBS encoding (hex) with delimiter 0x02: 00 -> 03 03 02 00 00 -> 03 03 03 02 00 11 00 -> 03 00 13 03 02 11 22 00 33 -> 01 13 20 00 31 02 11 22 33 44 -> 07 13 20 31 46 02 11 00 00 00 -> 00 13 03 03 03 02 01 02 03 04 05 ... FA FB FC FD FE -> FD 03 00 01 06 ... F9 FE FF FC 02 00 01 02 03 04 ... FA FB FC FD FE -> 03 FD 03 00 01 ... F9 FE FF FC 02 01 02 03 04 05 ... FB FC FD FE FF -> FD 03 00 01 06 ... FF FC 00 FD 02 02 03 04 05 06 ... FC FD FE FF 00 -> FD 00 01 06 07 ... FC FD 03 03 02 03 04 05 06 07 ... FD FE FF 00 01 -> FC 01 06 07 04 ... FC FD 00 03 02 COBS decoding (hex) with delimiter 0x02: 03 03 02 -> 00 03 03 03 02 -> 00 00 03 00 13 03 02 -> 00 11 00 01 13 20 00 31 02 -> 11 22 00 33 07 13 20 31 46 02 -> 11 22 33 44 00 13 03 03 03 02 -> 11 00 00 00 FD 03 00 01 06 ... F9 FE FF FC 02 -> 01 02 03 04 05 ... FA FB FC FD FE 03 FD 03 00 01 ... F9 FE FF FC 02 -> 00 01 02 03 04 ... FA FB FC FD FE FD 03 00 01 06 ... FF FC 00 FD 02 -> 01 02 03 04 05 ... FB FC FD FE FF FD 00 01 06 07 ... FC FD 03 03 02 -> 02 03 04 05 06 ... FC FD FE FF 00 FC 01 06 07 04 ... FC FD 00 03 02 -> 03 04 05 06 07 ... FD FE FF 00 01
Insitux
(function COBS unencoded _encoded
(let chunk (take-until [0] unencoded)
length (len chunk)
encoded (append (first 254 chunk) (or _encoded []))
more? (< length (len unencoded)))
(when (or (< 254 length) (and (= length 254) more?) more?)
(recur (skip (min 254 (inc length)) unencoded) encoded))
(append 0 (flat-map @(.. vec (inc (len %))) encoded)))Unit tests:
(for [a b] [
[[0x00] [0x01 0x01 0x00]]
[[0x00 0x00] [0x01 0x01 0x01 0x00]]
[[0x00 0x11 0x00] [0x01 0x02 0x11 0x01 0x00]]
[[0x11 0x22 0x00 0x33] [0x03 0x11 0x22 0x02 0x33 0x00]]
[[0x11 0x22 0x33 0x44] [0x05 0x11 0x22 0x33 0x44 0x00]]
[[0x11 0x00 0x00 0x00] [0x02 0x11 0x01 0x01 0x01 0x00]]
[(range 1 255) (.. vec 0xFF (range 1 255) 0x00)]
[(range 255) (.. vec 0x01 0xFF (range 1 255) 0x00)]
[(range 1 256) (.. vec 0xFF (range 1 255) 0x02 0xFF 0x00)]
[(.. vec (range 2 256) 0x00) (.. vec 0xFF (range 2 256) 0x01 0x01 0x00)]
[(.. vec (range 3 256) 0x00 0x01) (.. vec 0xFE (range 3 256) 0x02 0x01 0x00)]
]
(assert (= (COBS a) b)))Julia
From Wren code for encode and tests, from Phix code for decode.
module COBSPackets
export cobs_encode, cobs_decode, cencode, cdecode, crencode, crdecode, setCOBSerrormode
const _errormode = [:IGNORE]
"""
setCOBSerrormode(mode::Symbol)
Set decoding error reporting mode.
Default is :IGNORE. :WARN prints to stderr, :THROW will cause error exit.
"""
setCOBSerrormode(mode::Symbol) = begin _errormode[begin] = mode end
""" reporting for decoding errors (a marker byte in the wrong location) """
function _err(marker, position)
if _errormode[begin] == :WARN
@warn("packet error: found $marker at $position")
elseif _errormode[begin] == :THROW
error("packet error: found $marker at $position")
end
end
"""
cobs_encode(data; reduced = false, marker = 0x00)
Return result of encoding `inputdata` into COBS or COBS/R packet format.
If `reduced` is true will use the COBS/R protocol, if false the COBS protocol.
The `marker` defaults to zero but may be any byte from 0 to 254.
See also: COBS: www.stuartcheshire.org/papers/COBSforToN.pdf
COBS/R: pythonhosted.org/cobs/cobsr-intro.html
"""
function cobs_encode(inputdata; reduced = false, marker = 0x00)
output = [0xff]
codeindex, lastindex, code = 1, 1, 1
addlastcode = true
for byte in inputdata
if byte != 0x00
push!(output, byte)
code += 1
end
addlastcode = true
if byte == 0x00 || code == 255
code == 255 && (addlastcode = false)
output[codeindex] = code
code = 1
push!(output, 0xff)
codeindex = length(output)
byte == 0x00 && (lastindex = codeindex)
end
end
if addlastcode
output[codeindex] = code
push!(output, 0x00)
else
output[codeindex] = 0x00
end
# Reduce size output of by 1 char if can
if reduced && lastindex > 1 && output[end-1] + lastindex > length(output)
output[lastindex] = output[end-1]
output[end-1] = 0x00
pop!(output)
end
return marker == 0x00 ? output : UInt8.(output .⊻ marker)
end
""" short name for COBS encoding """
cencode(data; marker = 0x00) = cobs_encode(data, marker = marker, reduced = false)
""" short name for COBS/R encoding """
crencode(data; marker = 0x00) = cobs_encode(data, marker = marker, reduced = true)
"""
cobs_decode(buffer; reduced = false, marker = 0x00)
Return result of decoding `inputdata` from COBS or COBS/R packet format.
If `reduced` is true will use the COBS/R protocol, if false the COBS protocol.
The `marker` defaults to zero but may be any byte from 0 to 254.
See also: COBS: www.stuartcheshire.org/papers/COBSforToN.pdf
COBS/R: pythonhosted.org/cobs/cobsr-intro.html
"""
function cobs_decode(buffer::AbstractVector; reduced = false, marker = 0x00)
buffer[end] != marker && _err(buffer[end], "end")
buf = marker == 0 ? buffer : UInt8.(copy(buffer) .⊻ marker)
decoded = UInt8[]
bdx, len = 1, length(buf)
lpos, lchar = 1, 0
while bdx < len
code = buf[bdx]
code == 0x00 && bdx != 1 && _err(marker, bdx)
lpos, lchar = bdx, code
bdx += 1
for _ = 1:code-1
byte = buf[bdx]
byte == 0x00 && bdx < len && _err(marker, bdx)
push!(decoded, byte)
bdx += 1
if bdx > len
!reduced && _err("index", "\b\b\bpast end of packet")
break
end
end
code < 0xff && bdx < len && push!(decoded, 0x00)
end
# Restore from reduced format if present
reduced && lchar != 0x00 && lchar + lpos > len && (decoded[end] = lchar)
return decoded
end
""" short name for COBS decoding """
cdecode(data; marker = 0x00) = cobs_decode(data, marker = marker, reduced = false)
""" short name for COBS/R decoding """
crdecode(data; marker = 0x00) = cobs_decode(data, marker = marker, reduced = true)
end # module
using .COBSPackets
const tests = [
[0x00],
[0x00, 0x00],
[0x00, 0x11, 0x00],
[0x11, 0x22, 0x00, 0x33],
[0x11, 0x22, 0x33, 0x44],
[0x11, 0x00, 0x00, 0x00],
collect(0x01:0xfe),
collect(0x00:0xfe),
collect(0x01:0xff),
[collect(0x02:0xff); 0x00],
[collect(0x03:0xff); 0x00; 0x01],
]
function ab(arr)
hx = join(map(c -> string(c, base = 16, pad = 2), arr), " ")
return length(hx) < 20 ? hx : hx[begin:begin+10] * " ... " * hx[end-10:end]
end
for t in tests
println(ab(t), " -> ", ab(cencode(t, marker = 3)), " -> ",
ab(cdecode(cencode(t, marker = 3), marker = 3)))
end
using Test # module unit tests for error handling, etc.
for t in tests
setCOBSerrormode(:THROW)
@test t == crdecode(crencode(t))
@test t == crdecode(crencode(t, marker = 3), marker = 3)
@test t == cdecode(cencode(t, marker = 0xfe), marker = 0xfe)
if length(t) > 14
for m in 0:255
t2 = cencode(t, marker = m)
t2[3:10] .= m # introduce error
setCOBSerrormode(:WARN)
@test_warn "error" length(t2) > 15 && t != cdecode(t2, marker = m)
setCOBSerrormode(:THROW)
@test_throws "error" t != cdecode(t2, marker = m)
setCOBSerrormode(:IGNORE)
@test_nowarn t != cdecode(t2, marker = m)
end
end
@test t == crdecode(crencode(t))
@test t == crdecode(crencode(t, marker = 3), marker = 3)
@test t == crdecode(crencode(t, marker = 0xfe), marker = 0xfe)
setCOBSerrormode(:IGNORE)
if length(t) > 10
for m in 1:255 # marker type change
@test t != cdecode(cencode(t, marker = m), marker = 0)
@test t != crdecode(crencode(t, marker = m), marker = 0)
end
end
setCOBSerrormode(:WARN)
if !isempty(setdiff(cencode(t), crencode(t)))
@test_warn "past" t != cdecode(crencode(t))
end
end
- Output:
00 -> 02 02 03 -> 00 00 00 -> 02 02 02 03 -> 00 00 00 11 00 -> 02 01 12 02 03 -> 00 11 00 11 22 00 33 -> 00 12 21 01 30 03 -> 11 22 00 33 11 22 33 44 -> 06 12 21 30 47 03 -> 11 22 33 44 11 00 00 00 -> 01 12 02 02 02 03 -> 11 00 00 00 01 02 03 04 ... fb fc fd fe -> fc 02 01 00 ... ff fe fd 03 -> 01 02 03 04 ... fb fc fd fe 00 01 02 03 ... fb fc fd fe -> 02 fc 02 01 ... ff fe fd 03 -> 00 01 02 03 ... fb fc fd fe 01 02 03 04 ... fc fd fe ff -> fc 02 01 00 ... fd 01 fc 03 -> 01 02 03 04 ... fc fd fe ff 02 03 04 05 ... fd fe ff 00 -> fc 01 00 07 ... fc 02 02 03 -> 02 03 04 05 ... fd fe ff 00 03 04 05 06 ... fe ff 00 01 -> fd 00 07 06 ... fc 01 02 03 -> 03 04 05 06 ... fe ff 00 01
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Consistent_overhead_byte_stuffing
use warnings;
my @data = map { pack 'H*', tr/ //dr } split /\n/, <<END;
00
00 00
00 11 00
11 22 00 33
11 22 33 44
11 00 00 00
00 00 00 00 00 00
33 33 33 33 33 33 33
END
push @data, ( " " x $_ ) for 1269 .. 1272;
sub showbytes
{
my @bytes = map /../g, unpack 'H*', pop;
print "@_: ",
"@bytes\n" =~ s!(\w\w)\K(( \1){7,})! 'x' . (1 + length($2) / 3) !ger;
}
my $marker = "\0"; # the byte that is eliminated from string
sub encode
{
return join '',
(map chr(1 + length) . $_, # prepend length
map /.{1,254}|^\z/gs, # break up long sections
split /\Q$marker/, shift, -1), $marker;
}
sub decode
{
(local $_, my $keep, my $answer) = (shift, 0, '');
while( /\G[^\Q$marker\E]/g ) # advance over count byte
{
my $len = -1 + ord $&; # length of data block
$answer .= $marker x $keep . (/\G[^\Q$marker\E]{$len}/g, $&);
$keep = $len < 254; # was split on marker, not size
}
return $answer;
}
for my $original ( @data )
{
showbytes 'original', $original;
showbytes ' encoded', my $answer = encode $original;
showbytes ' decoded', my $decoded = decode $answer;
$original eq $decoded or die "MISMATCH";
print "\n";
}
- Output:
original: 00 encoded: 01 01 00 decoded: 00 original: 00 00 encoded: 01 01 01 00 decoded: 00 00 original: 00 11 00 encoded: 01 02 11 01 00 decoded: 00 11 00 original: 11 22 00 33 encoded: 03 11 22 02 33 00 decoded: 11 22 00 33 original: 11 22 33 44 encoded: 05 11 22 33 44 00 decoded: 11 22 33 44 original: 11 00 00 00 encoded: 02 11 01 01 01 00 decoded: 11 00 00 00 original: 00 00 00 00 00 00 encoded: 01 01 01 01 01 01 01 00 decoded: 00 00 00 00 00 00 original: 33 33 33 33 33 33 33 encoded: 08 33 33 33 33 33 33 33 00 decoded: 33 33 33 33 33 33 33 original: 20x1269 encoded: ff 20x254 ff 20x254 ff 20x254 ff 20x254 fe 20x253 00 decoded: 20x1269 original: 20x1270 encoded: ff 20x254 ff 20x254 ff 20x254 ff 20x254 ff 20x254 00 decoded: 20x1270 original: 20x1271 encoded: ff 20x254 ff 20x254 ff 20x254 ff 20x254 ff 20x254 02 20 00 decoded: 20x1271 original: 20x1272 encoded: ff 20x254 ff 20x254 ff 20x254 ff 20x254 ff 20x254 03 20 20 00 decoded: 20x1272
Phix
with javascript_semantics function cobs_encode(string data, integer delim=0) string enc = "?" integer ins = 1, code = 1, addLastCode = true for b in data do if b!=0 then enc &= b code += 1 end if addLastCode = true if b==0 or code == 255 then if code==255 then addLastCode = false end if enc[ins] = code code = 1 enc &= '?' ins = length(enc) end if end for if addLastCode then enc[ins] = code if delim!=0 then enc = sq_xor_bits(enc,delim) end if enc &= delim else if delim!=0 then enc = sq_xor_bits(enc,delim) end if enc[ins] = delim end if return enc end function function cobs_decode(string enc, integer delim=0) assert(enc[$]==delim) enc = enc[1..-2] integer l = length(enc), code = 255, block = 0 if delim then enc = sq_xor_bits(enc,delim) end if string data = "" for i=1 to l do integer b = enc[i] if block!=0 then data &= b else assert((i+b-1)<=l,"marker pointing beyond the end of packet") if code!=255 then data &= 0 end if code = b block = code if code==0 then exit end if end if block -= 1 end for return data end function function string00FF() string res = "" for ch=0x00 to 0xFF do res &= ch end for return res end function constant t00toFF = string00FF(), t00FE = t00toFF[1..-2], t01FE = t00toFF[2..-2], t01FF = t00toFF[2..-1], t02FF = t00toFF[3..-1], t03FF = t00toFF[4..-1], tests = {{x"00", x"010100"}, {x"0000", x"01010100"}, {x"001100", x"0102110100"}, {x"11220033", x"031122023300"}, {x"11223344", x"051122334400"}, {x"11000000", x"021101010100"}, {t01FE, 0xFF & t01FE & 0x00}, {t00FE, x"01FF" & t01FE & 0x00}, {t01FF, 0xFF & t01FE & x"02FF00"}, {t02FF & 0x00, 0xFF & t02FF & x"010100"}, {t03FF & x"0001", 0xFE & t03FF & x"020100"}} function ab(sequence s, integer m,f,l) s = iff(length(s)<m?join(s,fmt:="%02x") :join(s[1..f],fmt:="%02x") & " ... " & join(s[l..$],fmt:="%02x")) return s end function for delim in {0x00, 0x02} do printf(1,"%nUsing delim 0x%02x:\n",delim) for t in tests do sequence {orig,expected} = t, actual = cobs_encode(orig,delim), decoded = cobs_decode(actual,delim) if delim then expected = sq_xor_bits(expected,delim) end if bool eOK = (actual==expected), dOK = (decoded==orig) printf(1,"%-23s -> %-33s encode:%t, decode:%t\n", {ab(orig,5,3,253),ab(actual,7,4,254),eOK,dOK}) end for end for
- Output:
Using delim 0x00: 00 -> 01 01 00 encode:true, decode:true 00 00 -> 01 01 01 00 encode:true, decode:true 00 11 00 -> 01 02 11 01 00 encode:true, decode:true 11 22 00 33 -> 03 11 22 02 33 00 encode:true, decode:true 11 22 33 44 -> 05 11 22 33 44 00 encode:true, decode:true 11 00 00 00 -> 02 11 01 01 01 00 encode:true, decode:true 01 02 03 ... FD FE -> FF 01 02 03 ... FD FE 00 encode:true, decode:true 00 01 02 ... FC FD FE -> 01 FF 01 02 ... FC FD FE 00 encode:true, decode:true 01 02 03 ... FD FE FF -> FF 01 02 03 ... FD FE 02 FF 00 encode:true, decode:true 02 03 04 ... FE FF 00 -> FF 02 03 04 ... FE FF 01 01 00 encode:true, decode:true 03 04 05 ... FF 00 01 -> FE 03 04 05 ... FF 02 01 00 encode:true, decode:true Using delim 0x02: 00 -> 03 03 02 encode:true, decode:true 00 00 -> 03 03 03 02 encode:true, decode:true 00 11 00 -> 03 00 13 03 02 encode:true, decode:true 11 22 00 33 -> 01 13 20 00 31 02 encode:true, decode:true 11 22 33 44 -> 07 13 20 31 46 02 encode:true, decode:true 11 00 00 00 -> 00 13 03 03 03 02 encode:true, decode:true 01 02 03 ... FD FE -> FD 03 00 01 ... FF FC 02 encode:true, decode:true 00 01 02 ... FC FD FE -> 03 FD 03 00 ... FE FF FC 02 encode:true, decode:true 01 02 03 ... FD FE FF -> FD 03 00 01 ... FF FC 00 FD 02 encode:true, decode:true 02 03 04 ... FE FF 00 -> FD 00 01 06 ... FC FD 03 03 02 encode:true, decode:true 03 04 05 ... FF 00 01 -> FC 01 06 07 ... FD 00 03 02 encode:true, decode:true
Python
Based on several existing solutions. Assumes a zero byte packet delimiter.
"""Consistent overhead byte stuffing. Requires Python >= 3.10."""
from itertools import islice
def cob_encode(data: bytes | bytearray) -> bytearray:
buffer = bytearray([0])
code_index = 0
code = 1
final_code = True
for byte in data:
final_code = True
if byte:
buffer.append(byte)
code += 1
if not byte or code == 0xFF:
if code == 0xFF:
final_code = False
buffer[code_index] = code
code = 1
buffer.append(0)
code_index = len(buffer) - 1
if final_code:
assert not buffer[code_index]
buffer[code_index] = code
if buffer[-1]:
buffer.append(0)
return buffer
def cob_decode(encoded: bytes | bytearray) -> bytearray:
buffer = bytearray()
code = 0xFF
block = 0
for byte in islice(encoded, len(encoded) - 1):
if block:
buffer.append(byte)
else:
if code != 0xFF:
buffer.append(0)
block = code = byte
if not code:
break
block -= 1
return buffer
EXAMPLES = [
(bytearray.fromhex("00"), bytearray.fromhex("01 01 00")),
(bytearray.fromhex("00 00"), bytearray.fromhex("01 01 01 00")),
(bytearray.fromhex("00 11 00"), bytearray.fromhex("01 02 11 01 00")),
(bytearray.fromhex("11 22 00 33"), bytearray.fromhex("03 11 22 02 33 00")),
(bytearray.fromhex("11 22 33 44"), bytearray.fromhex("05 11 22 33 44 00")),
(bytearray.fromhex("11 00 00 00"), bytearray.fromhex("02 11 01 01 01 00")),
(
bytearray(range(0x01, 0xFE + 1)),
bytearray([0xFF, *range(1, 0xFE + 1), 0x00]),
),
(
bytearray(range(0x00, 0xFE + 1)),
bytearray([0x01, 0xFF, *range(1, 0xFE + 1), 0x00]),
),
(
bytearray(range(1, 0xFF + 1)),
bytearray([0xFF, *range(1, 0xFE + 1), 0x02, 0xFF, 0x00]),
),
(
bytearray([*range(0x02, 0xFF + 1), 0x00]),
bytearray([0xFF, *range(2, 0xFF + 1), 0x01, 0x01, 0x00]),
),
(
bytearray([*range(0x03, 0xFF + 1), 0x00, 0x01]),
bytearray([0xFE, *range(0x03, 0xFF + 1), 0x02, 0x01, 0x00]),
),
]
def pretty_hex(bytes: bytearray, m: int, n: int) -> str:
if len(bytes) < m:
return bytes.hex(" ").upper()
return f"{bytes[:n].hex(' ').upper()} ... {bytes[-n:].hex(' ').upper()}"
def main():
for data, expect in EXAMPLES:
encoded = cob_encode(data)
assert encoded == expect
assert cob_decode(encoded) == data
print(f"{pretty_hex(data, 5, 3):<23} -> {pretty_hex(encoded, 7, 4):<33}")
if __name__ == "__main__":
main()
- Output:
00 -> 01 01 00 00 00 -> 01 01 01 00 00 11 00 -> 01 02 11 01 00 11 22 00 33 -> 03 11 22 02 33 00 11 22 33 44 -> 05 11 22 33 44 00 11 00 00 00 -> 02 11 01 01 01 00 01 02 03 ... FC FD FE -> FF 01 02 03 ... FC FD FE 00 00 01 02 ... FC FD FE -> 01 FF 01 02 ... FC FD FE 00 01 02 03 ... FD FE FF -> FF 01 02 03 ... FE 02 FF 00 02 03 04 ... FE FF 00 -> FF 02 03 04 ... FF 01 01 00 03 04 05 ... FF 00 01 -> FE 03 04 05 ... FF 02 01 00
Raku
# 20231102 Raku programming solution
sub encode($data where $data.Bool, $delim = 0x00) {
my ($ins,$code,$addLastCode,@enc) = 0,1,True,-1;
for $data.list -> $byte {
if $byte != 0 { @enc.push($byte) andthen $code++ }
$addLastCode = True;
if $byte == 0 || $code == 255 {
$addLastCode = False if $code == 255;
@enc[$ins] = $code;
$code = 1;
$ins = @enc.elems;
@enc.push(-1);
}
}
if $addLastCode {
@enc[$ins] = $code;
if $delim != 0 { @enc >>^=>> $delim }
@enc.push($delim)
} else {
if $delim != 0 { @enc >>^=>> $delim }
@enc[$ins] = $delim
}
return @enc;
}
sub decode($data where $data.Bool, $delim = 0x00) {
my $length = ( my @enc2 = $data.list[0..*-2] ).elems;
if $delim != 0 { @enc2 >>^=>> $delim }
my ($block,$code,@dec) = 0,255;
for @enc2.kv -> $i,$byte {
if $block != 0 {
@dec.push($byte)
} else {
die "marker pointing beyond the end of the packet." if $i + $byte > $length;
@dec.push(0) if $code != 255;
$block = $code = $byte;
last if $code == 0
}
$block--;
}
return @dec;
}
for ( [0x00], [0x00,0x00], [0x00,0x11,0x00], [0x11,0x22,0x00,0x33],
[0x11,0x22,0x33,0x44], [0x11,0x00,0x00,0x00], # 0x01..0xfe, 0x00..0xfe,
# [0x02..0xff].append(0x00), [0x03..0xff].append(0x00, 0x01),
) { # https://crccalc.com/bytestuffing.php
# say encode( $_ )>>.&{.fmt("0x%x")};
say decode(encode( $_ ))>>.&{.fmt("0x%x")}
}
You may Attempt This Online!
Wren
This supports a non-zero marker using the method suggested by Nigel Galloway in the talk page which is also the method suggested in the original Cheshire & Baker paper.
import "./fmt" for Fmt
class COBS {
static isByte(i) { (i is Num) && i.isInteger && i >= 0 && i < 256 }
static encode(data, delim) {
if (!((data is List) && data.count > 0 && data.all { |i| isByte(i) })) {
Fiber.abort("data must be a non-empty list of bytes.")
}
var enc = [-1]
var ins = 0
var code = 1
var addLastCode = true
for (byte in data) {
if (byte != 0) {
enc.add(byte)
code = code + 1
}
addLastCode = true
if (byte == 0|| code == 255) {
if (code == 255) addLastCode = false
enc[ins] = code
code = 1
ins = enc.count
enc.add(-1)
}
}
if (addLastCode) {
enc[ins] = code
if (delim != 0) for (i in 0...enc.count) enc[i] = enc[i] ^ delim
enc.add(delim)
} else {
if (delim != 0) for (i in 0...enc.count) enc[i] = enc[i] ^ delim
enc[ins] = delim
}
return enc
}
static decode(enc, delim) {
if (!((enc is List) && enc.count > 0 && enc[-1] == delim &&
enc.all { |i| isByte(i) })) {
Fiber.abort("encoded data must be a non-empty list of delimiter-terminated bytes.")
}
var enc2 = enc[0..-2]
var length = enc2.count
if (delim != 0) for (i in 0...length) enc2[i] = enc[i] ^ delim
var dec = []
var code = 255
var block = 0
for (i in 0...length) {
var byte = enc2[i]
if (block != 0) {
dec.add(byte)
} else {
if (i + byte > length) Fiber.abort("marker pointing beyond the end of the packet.")
if (code != 255) dec.add(0)
code = byte
block = code
if (code == 0) break
}
block = block - 1
}
return dec
}
}
var examples = [
[0x00],
[0x00, 0x00],
[0x00, 0x11, 0x00],
[0x11, 0x22, 0x00, 0x33],
[0x11, 0x22, 0x33, 0x44],
[0x11, 0x00, 0x00, 0x00],
(0x01..0xfe).toList,
(0x00..0xfe).toList,
(0x01..0xff).toList,
(0x02..0xff).toList + [0x00],
(0x03..0xff).toList + [0x00, 0x01]
]
for (delim in [0x00, 0x02]) {
var encoded = []
Fmt.print("COBS encoding (hex) with delimiter $#02x:", delim)
for (example in examples) {
var res = COBS.encode(example, delim)
encoded.add(res)
if (example.count < 5) {
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", example), res)
} else {
var e = Fmt.va("Xz", 2, example, 0, " ", "", "", 5, "...")
var r = Fmt.va("Xz", 2, res, 0, " ", "", "", 5, "...")
Fmt.print("$s -> $s", e, r)
}
}
Fmt.print("\nCOBS decoding (hex) with delimiter $#02x:", delim)
for (enc in encoded) {
var res = COBS.decode(enc, delim)
if (enc.count < 7) {
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", enc), res)
} else {
var e = Fmt.va("Xz", 2, enc, 0, " ", "", "", 5, "...")
var r = Fmt.va("Xz", 2, res, 0, " ", "", "", 5, "...")
Fmt.print("$s -> $s", e, r)
}
}
System.print()
}
- Output:
COBS encoding (hex) with delimiter 0x00: 00 -> 01 01 00 00 00 -> 01 01 01 00 00 11 00 -> 01 02 11 01 00 11 22 00 33 -> 03 11 22 02 33 00 11 22 33 44 -> 05 11 22 33 44 00 11 00 00 00 -> 02 11 01 01 01 00 01 02 03 04 05 ... FA FB FC FD FE -> FF 01 02 03 04 ... FB FC FD FE 00 00 01 02 03 04 ... FA FB FC FD FE -> 01 FF 01 02 03 ... FB FC FD FE 00 01 02 03 04 05 ... FB FC FD FE FF -> FF 01 02 03 04 ... FD FE 02 FF 00 02 03 04 05 06 ... FC FD FE FF 00 -> FF 02 03 04 05 ... FE FF 01 01 00 03 04 05 06 07 ... FD FE FF 00 01 -> FE 03 04 05 06 ... FE FF 02 01 00 COBS decoding (hex) with delimiter 0x00: 01 01 00 -> 00 01 01 01 00 -> 00 00 01 02 11 01 00 -> 00 11 00 03 11 22 02 33 00 -> 11 22 00 33 05 11 22 33 44 00 -> 11 22 33 44 02 11 01 01 01 00 -> 11 00 00 00 FF 01 02 03 04 ... FB FC FD FE 00 -> 01 02 03 04 05 ... FA FB FC FD FE 01 FF 01 02 03 ... FB FC FD FE 00 -> 00 01 02 03 04 ... FA FB FC FD FE FF 01 02 03 04 ... FD FE 02 FF 00 -> 01 02 03 04 05 ... FB FC FD FE FF FF 02 03 04 05 ... FE FF 01 01 00 -> 02 03 04 05 06 ... FC FD FE FF 00 FE 03 04 05 06 ... FE FF 02 01 00 -> 03 04 05 06 07 ... FD FE FF 00 01 COBS encoding (hex) with delimiter 0x02: 00 -> 03 03 02 00 00 -> 03 03 03 02 00 11 00 -> 03 00 13 03 02 11 22 00 33 -> 01 13 20 00 31 02 11 22 33 44 -> 07 13 20 31 46 02 11 00 00 00 -> 00 13 03 03 03 02 01 02 03 04 05 ... FA FB FC FD FE -> FD 03 00 01 06 ... F9 FE FF FC 02 00 01 02 03 04 ... FA FB FC FD FE -> 03 FD 03 00 01 ... F9 FE FF FC 02 01 02 03 04 05 ... FB FC FD FE FF -> FD 03 00 01 06 ... FF FC 00 FD 02 02 03 04 05 06 ... FC FD FE FF 00 -> FD 00 01 06 07 ... FC FD 03 03 02 03 04 05 06 07 ... FD FE FF 00 01 -> FC 01 06 07 04 ... FC FD 00 03 02 COBS decoding (hex) with delimiter 0x02: 03 03 02 -> 00 03 03 03 02 -> 00 00 03 00 13 03 02 -> 00 11 00 01 13 20 00 31 02 -> 11 22 00 33 07 13 20 31 46 02 -> 11 22 33 44 00 13 03 03 03 02 -> 11 00 00 00 FD 03 00 01 06 ... F9 FE FF FC 02 -> 01 02 03 04 05 ... FA FB FC FD FE 03 FD 03 00 01 ... F9 FE FF FC 02 -> 00 01 02 03 04 ... FA FB FC FD FE FD 03 00 01 06 ... FF FC 00 FD 02 -> 01 02 03 04 05 ... FB FC FD FE FF FD 00 01 06 07 ... FC FD 03 03 02 -> 02 03 04 05 06 ... FC FD FE FF 00 FC 01 06 07 04 ... FC FD 00 03 02 -> 03 04 05 06 07 ... FD FE FF 00 01