530: : Overhead byte (Start of frame) 3+ -------------->| : Points to relative location of first zero symbol 2+-------->| : Is a zero data byte, pointing to next zero symbol : Location of end-of-packet zero symbol. 0 1 2 3 4 5 : Byte Position 03 11 22 02 33 00 : COBS Data Frame 11 22 00 33 : Extracted Data OHB = Overhead Byte (Points to next zero symbol) EOP = End Of Packet
137:
123:
COBS transforms an arbitrary string of bytes in the range into bytes in the range . Having eliminated all zero bytes from the data, a zero byte can now be used to unambiguously mark the end of the transformed data. This is done by appending a zero byte to the transformed data, thus forming a packet
119:
is required to demarcate packet boundaries. This is done by using a framing marker, a special bit-sequence or character value that indicates where the boundaries between packets fall. Data stuffing is the process that transforms the packet data before transmission to eliminate all occurrences of the
195:
indicates a zero data byte that was altered by encoding. All zero data bytes are replaced during encoding by the offset to the following zero byte (i.e. one plus the number of non-zero bytes that follow). It is effectively a pointer to the next packet byte that requires interpretation: if the
83:
data bytes (one byte in 254, rounded up). Consequently, the time to transmit the encoded byte sequence is highly predictable, which makes COBS useful for real-time applications in which jitter may be problematic. The algorithm is computationally inexpensive, and in addition to its desirable
47:
is a process that transforms a sequence of data bytes that may contain 'illegal' or 'reserved' values (such as packet delimiter) into a potentially longer sequence that contains no occurrences of those values. The extra length of the transformed sequence is typically referred to as the
41:(a special value that indicates the boundary between packets). When zero is used as a delimiter, the algorithm replaces each zero data byte with a non-zero value so that no zero data bytes will appear in the packet and thus be misinterpreted as packet boundaries.
155:
Encode each group by deleting the trailing zero byte (if any) and prepending the number of non-zero bytes, plus one. Thus, each encoded group is the same size as the original, except that 254 non-zero bytes are encoded into 255 bytes by prepending a byte of
165:
First, insert a zero byte at the beginning of the packet, and after every run of 254 non-zero bytes. This encoding is obviously reversible. It is not necessary to insert a zero byte at the end of the packet if it happens to end with exactly 254 non-zero
210:
is an overhead byte which is also a group header byte containing an offset to a following group, but does not correspond to a data byte. These appear in two places: at the beginning of every encoded packet, and after every group of 254 non-zero
218:
zero byte appears at the end of every packet to indicate end-of-packet to the data receiver. This packet delimiter byte is not part of COBS proper; it is an additional framing byte that is appended to the encoded
151:
To encode some bytes, first append a zero byte, then break them into groups of either 254 non-zero bytes, or 0–253 non-zero bytes followed by a zero byte. Because of the appended zero byte, this is always
169:
Second, replace each zero byte with the offset to the next zero byte, or the end of the packet. Because of the extra zeros added in the first step, each offset is guaranteed to be at most 255.
34:
regardless of packet content, thus making it easy for receiving applications to recover from malformed packets. It employs a particular byte value, typically zero, to serve as a
527:
Below is a diagram using example 4 from above table, to illustrate how each modified data byte is located, and how it is identified as a data byte or an end of frame byte.
159:
As a special exception, if a packet ends with a group of 254 non-zero bytes, it is not necessary to add the trailing zero byte. This saves one byte in some situations.
136:
1552:
72:-case overhead of 100%; for inputs that consist entirely of bytes that require escaping, HDLC byte stuffing will double the size of the input.
75:
The COBS algorithm, on the other hand, tightly bounds the worst-case overhead. COBS requires a minimum of 1 byte overhead, and a maximum of ⌈
1490:
1425:
120:
framing marker, so that when the receiver detects a marker, it can be certain that the marker indicates a boundary between packets.
178:
These examples show how various data sequences would be encoded by the COBS algorithm. In the examples, all bytes are expressed as
96:. Before transmitting its first byte, it needs to know the position of the first zero byte (if any) in the following 254 bytes.
92:
overhead is also low compared to other unambiguous framing algorithms like HDLC. COBS does, however, require up to 254 bytes of
31:
1393:
533:
Examples 7 through 10 show how the overhead varies depending on the data being encoded for packet lengths of 255 or more.
53:
116:
104:
57:
133:(Any other byte value may be reserved as the packet delimiter, but using zero simplifies the description.)
1434:
189:
indicates a data byte which has not been altered by encoding. All non-zero data bytes remain unaltered.
1523:
49:
1439:
200:
that points to the next byte requiring interpretation; if the addressed byte is zero then it is the
126:
1577:
1452:
1481:
1444:
61:
1519:
1477:
1413:
541:
The following code implements a COBS encoder and decoder in the C programming language:
182:
values, and encoded data is shown with text formatting to illustrate various features:
100:
1417:
1571:
1456:
1388:
1557:
1562:
179:
1563:
A patent describing a scheme with a similar result but using a different method
37:
27:
30:
for encoding data bytes that results in efficient, reliable, unambiguous
1493:
1448:
135:
107:, due to the aforementioned poor worst-case overhead of HDLC framing.
1547:
1497:
144:
There are two equivalent ways to describe the COBS encoding process:
1542:
103:
proposed to standardize COBS as an alternative for HDLC framing in
115:
When packetized data is sent over any serial medium, some
64:). Although HDLC framing has an overhead of <1% in the
140:
Consistent
Overhead Byte Stuffing (COBS) encoding process
1278:// Encoded zero, write it unless it's delimiter.
196:
addressed byte is non-zero then it is the following
1558:Consistent Overhead Byte Stuffing—Reduced (COBS/R)
993:@note Stops decoding if delimiter byte is found
130:) to unambiguously mark the end of the packet.
573:@param buffer Pointer to encoded output buffer
56:is a well-known example, used particularly in
8:
1525:PPP Consistent Overhead Byte Stuffing (COBS)
990:@return Number of bytes successfully decoded
981:@param buffer Pointer to encoded input bytes
852:// Input is zero or block completed, restart
567:@param data Pointer to input data to encode
987:@param data Pointer to decoded output data
1438:
124:consisting of the COBS-encoded data (the
222:
1405:
984:@param length Number of bytes to decode
570:@param length Number of bytes to encode
576:@return Encoded buffer length in bytes
7:
1528:. I-D draft-ietf-pppext-cobs-00.txt.
579:@note Does not output delimiter byte
1426:IEEE/ACM Transactions on Networking
1418:"Consistent Overhead Byte Stuffing"
1480:; Baker, Mary (17 November 1997).
68:case, it suffers from a very poor
14:
1483:Consistent Overhead Byte Stuffing
20:Consistent Overhead Byte Stuffing
16:Algorithm for encoding data bytes
978:/** COBS decode data from buffer
198:group header byte zero data byte
1522:; Baker, Mary (November 1997).
1248:// Fetch the next block length
1119:// Decoded output byte pointer
564:/** COBS encode data to buffer
1:
1394:Serial Line Internet Protocol
1086:// Encoded input byte pointer
1416:; Baker, Mary (April 1999).
1553:Another implementation in C
111:Packet framing and stuffing
1594:
1548:Alternate C implementation
792:// Byte not zero, write it
148:Prefixed block description
948:// Write final code value
543:
232:Encoded with COBS (hex)
1326:// Delimiter code found
669:// Encoded byte pointer
162:Linked list description
693:// Output code pointer
141:
1543:Python implementation
501:03 04 05 ... FF 00 01
472:02 03 04 ... FE FF 00
443:01 02 03 ... FD FE FF
417:00 01 02 ... FC FD FE
139:
1197:// Decode block byte
229:Unencoded data (hex)
88:-case overhead, its
481:02 03 04 ... FE FF
452:01 02 03 ... FD FE
429:01 02 ... FC FD FE
403:01 02 03 ... FD FE
394:01 02 03 ... FD FE
142:
52:of the algorithm.
1449:10.1109/90.769765
525:
524:
174:Encoding examples
1585:
1530:
1529:
1520:Cheshire, Stuart
1518:Carlson, James;
1515:
1509:
1508:
1506:
1504:
1488:
1478:Cheshire, Stuart
1474:
1468:
1467:
1465:
1463:
1442:
1422:
1414:Cheshire, Stuart
1410:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
561:<assert.h>
559:
556:
555:<stdint.h>
553:
550:
549:<stddef.h>
547:
521:
520:
514:
508:
502:
492:
491:
488:
485:
479:
473:
463:
462:
456:
450:
444:
434:
433:
427:
424:
418:
408:
407:
401:
395:
385:
384:
381:
375:
369:
359:
358:
352:
346:
336:
335:
329:
323:
317:
307:
306:
303:
297:
294:
288:
278:
277:
274:
271:
265:
255:
254:
251:
248:
242:
223:
217:
209:
203:
199:
194:
79:/254⌉ bytes for
1593:
1592:
1588:
1587:
1586:
1584:
1583:
1582:
1568:
1567:
1539:
1534:
1533:
1517:
1516:
1512:
1502:
1500:
1486:
1476:
1475:
1471:
1461:
1459:
1440:10.1.1.108.3143
1420:
1412:
1411:
1407:
1402:
1385:
1380:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
539:
531:
518:
512:
510:03 04 05 ... FF
506:
505:
500:
489:
486:
483:
477:
476:
471:
460:
454:
448:
447:
442:
431:
425:
422:
421:
416:
405:
399:
398:
393:
382:
379:
373:
372:
367:
356:
350:
349:
344:
333:
327:
321:
320:
315:
304:
301:
295:
292:
291:
286:
275:
272:
269:
268:
263:
252:
249:
246:
245:
240:
215:
207:
201:
197:
192:
176:
113:
17:
12:
11:
5:
1591:
1589:
1581:
1580:
1570:
1569:
1566:
1565:
1560:
1555:
1550:
1545:
1538:
1537:External links
1535:
1532:
1531:
1510:
1469:
1433:(2): 159–172.
1404:
1403:
1401:
1398:
1397:
1396:
1391:
1384:
1381:
544:
538:
537:Implementation
535:
529:
523:
522:
503:
498:
494:
493:
474:
469:
465:
464:
445:
440:
436:
435:
419:
414:
410:
409:
396:
391:
387:
386:
370:
365:
361:
360:
347:
342:
338:
337:
318:
313:
309:
308:
289:
284:
280:
279:
266:
261:
257:
256:
243:
238:
234:
233:
230:
227:
221:
220:
212:
205:
190:
175:
172:
171:
170:
167:
163:
160:
157:
153:
149:
112:
109:
101:Internet Draft
62:RFC 1662 § 4.2
32:packet framing
15:
13:
10:
9:
6:
4:
3:
2:
1590:
1579:
1576:
1575:
1573:
1564:
1561:
1559:
1556:
1554:
1551:
1549:
1546:
1544:
1541:
1540:
1536:
1527:
1526:
1521:
1514:
1511:
1499:
1495:
1492:
1485:
1484:
1479:
1473:
1470:
1458:
1454:
1450:
1446:
1441:
1436:
1432:
1428:
1427:
1419:
1415:
1409:
1406:
1399:
1395:
1392:
1390:
1387:
1386:
1382:
711:// Code value
542:
536:
534:
528:
517:
511:
504:
499:
496:
495:
482:
475:
470:
467:
466:
459:
453:
446:
441:
438:
437:
430:
420:
415:
412:
411:
404:
397:
392:
389:
388:
378:
371:
366:
363:
362:
355:
348:
343:
340:
339:
332:
326:
319:
314:
311:
310:
300:
290:
285:
282:
281:
267:
262:
259:
258:
244:
239:
236:
235:
231:
228:
225:
224:
213:
206:
202:end of packet
191:
188:
185:
184:
183:
181:
173:
168:
164:
161:
158:
154:
150:
147:
146:
145:
138:
134:
131:
129:
128:
121:
118:
110:
108:
106:
102:
97:
95:
91:
87:
82:
78:
73:
71:
67:
63:
59:
55:
51:
46:
45:Byte stuffing
42:
40:
39:
33:
29:
25:
21:
1524:
1513:
1503:November 23,
1501:. Retrieved
1482:
1472:
1462:November 30,
1460:. Retrieved
1430:
1424:
1408:
1389:Bit stuffing
540:
532:
526:
515:
509:
480:
457:
451:
428:
402:
376:
353:
330:
324:
298:
186:
177:
143:
132:
125:
122:
114:
98:
93:
89:
85:
80:
76:
74:
69:
65:
54:HDLC framing
44:
43:
35:
23:
19:
18:
368:11 00 00 00
354:11 22 33 44
345:11 22 33 44
316:11 22 00 33
180:hexadecimal
1400:References
1260:&&
1056:&&
1002:cobsDecode
642:&&
588:cobsEncode
1578:Encodings
1435:CiteSeerX
152:possible.
94:lookahead
38:delimiter
28:algorithm
1572:Category
1457:47267776
1383:See also
558:#include
552:#include
546:#include
380:01 01 01
287:00 11 00
117:protocol
50:overhead
26:) is an
1494:SIGCOMM
1362:uint8_t
1128:uint8_t
1104:uint8_t
1089:uint8_t
1068:uint8_t
1011:uint8_t
741:uint8_t
723:uint8_t
696:uint8_t
672:uint8_t
651:uint8_t
618:uint8_t
226:Example
219:output.
127:payload
99:A 1999
90:average
66:average
36:packet
1498:Cannes
1455:
1437:
1353:decode
1347:size_t
1341:return
1284:decode
1203:decode
1167:length
1161:buffer
1095:decode
1080:buffer
1053:buffer
1047:assert
1026:length
1023:size_t
1017:buffer
999:size_t
969:buffer
963:encode
957:size_t
951:return
921:encode
912:length
891:encode
798:encode
756:length
684:encode
663:buffer
657:encode
645:buffer
633:assert
624:buffer
612:length
609:size_t
585:size_t
211:bytes.
166:bytes.
1496:'97.
1487:(PDF)
1453:S2CID
1421:(PDF)
1329:break
1305:block
1257:block
1230:block
1191:block
1176:block
1143:block
1065:const
1008:const
936:codep
885:codep
861:codep
738:const
720:const
678:codep
594:const
325:11 22
273:01 01
264:00 00
193:Green
86:worst
70:worst
60:(see
1505:2010
1464:2015
1371:data
1320:code
1299:code
1272:0xff
1266:code
1239:byte
1224:else
1215:byte
1158:<
1155:byte
1137:0xff
1131:code
1113:data
1074:byte
1059:data
1038:data
1032:void
942:code
906:byte
873:code
867:code
846:0xff
840:code
834:byte
819:code
810:byte
786:byte
768:byte
750:data
729:byte
699:code
639:data
603:data
597:void
216:blue
187:Bold
156:255.
24:COBS
1491:ACM
1445:doi
1122:for
714:for
302:01
296:02
208:Red
105:PPP
58:PPP
1574::
1489:.
1451:.
1443:.
1429:.
1423:.
1374:);
1350:)(
1311:if
1287:++
1275:))
1269:!=
1251:if
1242:++
1218:++
1206:++
1185:if
1173:--
1062:);
996:*/
972:);
960:)(
918:++
909:||
903:!*
897:if
843:==
837:||
831:!*
825:if
816:++
801:++
777:if
765:++
759:--
687:++
648:);
582:*/
519:00
516:01
513:02
507:FE
497:11
490:00
487:01
484:01
478:FF
468:10
461:00
458:FF
455:02
449:FF
432:00
426:FF
423:01
406:00
400:FF
383:00
377:11
374:02
357:00
351:05
334:00
331:33
328:02
322:03
305:00
299:11
293:01
276:00
270:01
253:00
250:01
247:01
241:00
214:A
1507:.
1466:.
1447::
1431:7
1377:}
1368:)
1365:*
1359:(
1356:-
1344:(
1338:}
1335:}
1332:;
1323:)
1317:!
1314:(
1308:;
1302:=
1296:;
1293:0
1290:=
1281:*
1263:(
1254:(
1245:;
1236:*
1233:=
1227:{
1221:;
1212:*
1209:=
1200:*
1194:)
1188:(
1182:{
1179:)
1170:;
1164:+
1152:;
1149:0
1146:=
1140:,
1134:=
1125:(
1116:;
1110:)
1107:*
1101:(
1098:=
1092:*
1083:;
1077:=
1071:*
1050:(
1044:{
1041:)
1035:*
1029:,
1020:,
1014:*
1005:(
975:}
966:-
954:(
945:;
939:=
933:*
930:}
927:}
924:;
915:)
900:(
894:;
888:=
882:,
879:1
876:=
870:,
864:=
858:*
855:{
849:)
828:(
822:;
813:,
807:*
804:=
795:*
789:)
783:*
780:(
774:{
771:)
762:;
753:;
747:)
744:*
735:(
732:=
726:*
717:(
708:;
705:1
702:=
690:;
681:=
675:*
666:;
660:=
654:*
636:(
630:{
627:)
621:*
615:,
606:,
600:*
591:(
439:9
413:8
390:7
364:6
341:5
312:4
283:3
260:2
237:1
204:.
81:n
77:n
22:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
