Consistent overhead byte stuffing: Difference between revisions

From Rosetta Code
Content added Content deleted
(Realize in F#)
(→‎{{header|Wren}}: Now supports using a non-zero marker.)
Line 427: Line 427:
=={{header|Wren}}==
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-fmt}}
This only supports using a zero marker (see talk page).
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.
<syntaxhighlight lang="ecmascript">import "./fmt" for Fmt
<syntaxhighlight lang="ecmascript">import "./fmt" for Fmt


Line 433: Line 433:
static isByte(i) { (i is Num) && i.isInteger && i >= 0 && i < 256 }
static isByte(i) { (i is Num) && i.isInteger && i >= 0 && i < 256 }


static encode(data) {
static encode(data, delim) {
if (!((data is List) && data.count > 0 && data.all { |i| isByte(i) })) {
if (!((data is List) && data.count > 0 && data.all { |i| isByte(i) })) {
Fiber.abort("data must be a non-empty list of bytes.")
Fiber.abort("data must be a non-empty list of bytes.")
Line 457: Line 457:
if (addLastCode) {
if (addLastCode) {
enc[ins] = code
enc[ins] = code
if (delim != 0) for (i in 0...enc.count) enc[i] = enc[i] ^ delim
enc.add(0)
enc.add(delim)
} else {
} else {
enc[ins] = 0
if (delim != 0) for (i in 0...enc.count) enc[i] = enc[i] ^ delim
enc[ins] = delim
}
}
return enc
return enc
}
}


static decode(enc) {
static decode(enc, delim) {
if (!((enc is List) && enc.count > 0 && enc[-1] == 0 &&
if (!((enc is List) && enc.count > 0 && enc[-1] == delim &&
enc.all { |i| isByte(i) })) {
enc.all { |i| isByte(i) })) {
Fiber.abort("encoded data must be a non-empty list of zero-terminated bytes.")
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 dec = []
var code = 255
var code = 255
var block = 0
var block = 0
for (byte in enc[0..-2]) {
for (i in 0...length) {
var byte = enc2[i]
if (block != 0) {
if (block != 0) {
dec.add(byte)
dec.add(byte)
} else {
} else {
if (i + byte > length) Fiber.abort("marker pointing beyond the end of the packet.")
if (code != 255) dec.add(0)
if (code != 255) dec.add(0)
code = byte
code = byte
Line 501: Line 508:
]
]


⚫
for (delim in [0x00, 0x02]) {
var encoded = []
var encoded = []
System.print("COBS encoding (hex):")
Fmt.print("COBS encoding (hex) with delimiter $#02x:", delim)
for (example in examples) {
var res = COBS.encode(example)
for (example in examples) {
var res = COBS.encode(example, delim)
encoded.add(res)
encoded.add(res)
if (example.count < 5) {
if (example.count < 5) {
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", example), res)
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", example), res)
} else {
} else {
⚫
var e = Fmt.va("Xz", 2, example, 0, " ", "", "", 5, "...")
var r = Fmt.va("Xz", 2, res, 0, " ", "", "", 5, "...")
var e = Fmt.va("Xz", 2, example, 0, " ", "", "", 5, "...")
Fmt.print("$s -> $s", e, r)
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) {
⚫
System.print("\nCOBS decoding (hex):")
var res = COBS.decode(enc, delim)
⚫
for (enc in encoded) {
var res = COBS.decode(enc)
if (enc.count < 7) {
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", enc), res)
⚫
if (enc.count < 7) {
} else {
⚫
Fmt.print("$-33s -> $02X", Fmt.swrite("$02X", enc), res)
⚫
var e = Fmt.va("Xz", 2, enc, 0, " ", "", "", 5, "...")
⚫
} else {
var e = Fmt.va("Xz", 2, enc, 0, " ", "", "", 5, "...")
var r = Fmt.va("Xz", 2, res, 0, " ", "", "", 5, "...")
var r = Fmt.va("Xz", 2, res, 0, " ", "", "", 5, "...")
Fmt.print("$s -> $s", e, r)
Fmt.print("$s -> $s", e, r)
}
}
}
System.print()
}</syntaxhighlight>
}</syntaxhighlight>


{{out}}
{{out}}
<pre>
<pre>
COBS encoding (hex):
COBS encoding (hex) with delimiter 0x00:
00 -> 01 01 00
00 -> 01 01 00
00 00 -> 01 01 01 00
00 00 -> 01 01 01 00
Line 541: Line 551:
03 04 05 06 07 ... FD FE FF 00 01 -> FE 03 04 05 06 ... FE FF 02 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):
COBS decoding (hex) with delimiter 0x00:
01 01 00 -> 00
01 01 00 -> 00
01 01 01 00 -> 00 00
01 01 01 00 -> 00 00
Line 553: Line 563:
FF 02 03 04 05 ... FE FF 01 01 00 -> 02 03 04 05 06 ... FC FD FE FF 00
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
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
</pre>
</pre>

Revision as of 19:45, 28 September 2023

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 stream
  •   Check for errors during decoding - an unexpected instance of the chosen marker
  •   Support a non-zero marker

C

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>254 || g=0uy)
                                                  seq{match n with 255->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 rec fT g=seq{match Seq.head g with 0uy->() |n->yield 0uy; yield! g|>Seq.take(int n)|>Seq.skip 1; yield! fT(g|>Seq.skip(int n))}
let decode g=seq{let n=int(Seq.head g) in yield! g|>Seq.take n|>Seq.skip 1; yield! fT(g|>Seq.skip n)}

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   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   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   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

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

Insitux

(function COBS unencoded
  (let chunk   (take-until [0] unencoded)
       length  (len chunk)
       encoded (append (first 254 chunk) (or %1 []))
       more?   (< length (len unencoded)))
  (if (or (and (= length 254) more?) (> length 254))
    (recur (skip 254 unencoded) encoded)
    (if more?
      (recur (skip (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 COBSencode, COBSdecode

"""
    COBSencode(data)

Return result of encoding `inputdata` into COBS packet format.
"""
function COBSencode(inputdata, marker = 0x00)
    output = [0xff]
    codeindex, code = 1, 1
    addlastcode = true
    for byte in inputdata
        if byte != marker
            push!(output, byte)
            code += 1
        end
        addlastcode = true
        if byte == marker || code == 255
            code == 255 && (addlastcode = false)
            output[codeindex] = code
            code = 1
            push!(output, 0xff)
            codeindex = length(output)
        end
    end
    if addlastcode
        output[codeindex] = code
        push!(output, marker)
    else
        output[codeindex] = marker
    end
    return output
end

"""
    COBSdecode(buffer)

    Return result of decoding `buffer` from COBS encoded format.
"""
function COBSdecode(buffer::AbstractVector, marker = 0x00)
    decoded = UInt8[]
    bdx, len = 1, length(buffer)
    while bdx < len
        code = buffer[bdx]
        bdx += 1
        for i in 1:code-1
            push!(decoded, buffer[bdx])
            bdx += 1
            bdx >= len && break
        end
        code < 0xff && bdx < len && push!(decoded, marker)
    end
    return decoded
end

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(COBSencode(t, 3)), " -> ", ab(COBSdecode(COBSencode(t, 3), 3)))
end
Output:
00 -> 01 01 00 -> 00
00 00 -> 01 01 01 00 -> 00 00
00 11 00 -> 01 02 11 01 00 -> 00 11 00
11 22 00 33 -> 03 11 22 02 33 00 -> 11 22 00 33
11 22 33 44 -> 05 11 22 33 44 00 -> 11 22 33 44
11 00 00 00 -> 02 11 01 01 01 00 -> 11 00 00 00
01 02 03 04 ... fb fc fd fe -> ff 01 02 03 ... fc fd fe 00 -> 01 02 03 04 ... fb fc fd fe
00 01 02 03 ... fb fc fd fe -> 01 ff 01 02 ... fc fd fe 00 -> 00 01 02 03 ... fb fc fd fe
01 02 03 04 ... fc fd fe ff -> ff 01 02 03 ... fe 02 ff 00 -> 01 02 03 04 ... fc fd fe ff
02 03 04 05 ... fd fe ff 00 -> ff 02 03 04 ... ff 01 01 00 -> 02 03 04 05 ... fd fe ff 00
03 04 05 06 ... fe ff 00 01 -> fe 03 04 05 ... ff 02 01 00 -> 03 04 05 06 ... fe ff 00 01

Phix

with javascript_semantics
function cobs_encode(sequence data)
    sequence buffer = {-1}
    integer cdx = 1, code = 1, addlast = true
    for b in data do
        if b then
            buffer &= b
            code += 1
        end if
        addlast = true
        if b=0 or code=0xFF then
            addlast = code!=0xFF
            buffer[cdx] = code
            code = 1
            buffer &= -1
            cdx = length(buffer)
        end if
    end for
    buffer[cdx] = iff(addlast?code:0)
    if addlast then buffer &= 0 end if
    return buffer
end function

function cobs_decode(sequence buffer)
    sequence data = {}
    integer bdx = 1, l = length(buffer)
    while bdx<l do
        integer code = buffer[bdx]
        bdx += 1
        for i=1 to code-1 do
            data &= buffer[bdx]
            bdx += 1
        end for
        if code<0xFF and bdx<l then
            data &= 0
        end if
    end while
    return data
end function

constant tests = {{{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}},
                  {tagset(0xFE,0x01), 0xFF & tagset(0xFE,0x01) & 0x00},
                  {tagset(0xFE,0x00), {0x01, 0xFF} & tagset(0xFE,0x01) & 0x00},
                  {tagset(0xFF,0x01), 0xFF & tagset(0xFE,0x01) & {0x02, 0xFF, 0x00}},
                  {tagset(0xFF,0x02) & {0x00}, 0xFF & tagset(0xFF,0x02) & {0x01, 0x01, 0x00}},
                  {tagset(0xFF,0x03) & {0x00, 0x01}, 0xFE & tagset(0xFF,0x03) & {0x02, 0x01, 0x00}}}

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 t in tests do
    sequence {orig,expected} = t,
             actual = cobs_encode(orig),
             decoded = cobs_decode(actual)
    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
Output:
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

Wren

Library: Wren-fmt

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
Retrieved from "https://rosettacode.org/wiki/Consistent_overhead_byte_stuffing?oldid=360195"