Here's a fun Sunday puzzle for data minded people out there: * COBS is a bit-stuffing technique, it changes the bitstream when encoding * CRC is designed to defend against corruptions of the EXACT bit pattern on the wire If I want to frame my messages with COBS, how do I also CRC them? - ThreadSky

jamesmunns.com • 45 days ago

Here's a fun Sunday puzzle for data minded people out there:

* COBS is a bit-stuffing technique, it changes the bitstream when encoding
* CRC is designed to defend against corruptions of the EXACT bit pattern on the wire

If I want to frame my messages with COBS, how do I also CRC them?

Comments

jamesmunns.com•45 days ago

If you CRC the payload then COBS encode it, you actually WEAKEN the CRC properties. See also CAN and USB bit-stuffing issues that have been found (https://users.ece.cmu.edu/~koopman/pubs/koopman14_crc_faa_conference_presentation.pdf)

If you COBS then append CRC, the CRC could include a zero byte, confusing the COBS framing

sneakyness.com•45 days ago

It's been a bit over a decade, but I think we used to use a counter, figure out the absolute worst case and send n+1 duplicate packets. Idk if that counts as cheating or not. Was for telematics going over cellular

jamesmunns.com•45 days ago

So, I could

* YOLO it, use a CRC16/32 then COBS encode, accept the weakened CRC properties
* Do something complicated like cobs+ that is smart enough to handle crc zeros, maybe looking for two termination `0x00` bytes that are 2 (crc16) or 4 (crc32) bytes apart
* Use a non-crc message integrity sig

dcoles.net•45 days ago

Could you COBS encode, calculate the CRC checksum and then COBS encode the checksum; with the end result that each message turning into a pair of COBS frames?

To re-sync, just find the next COBS frame that contains a valid CRC for the previous raw COBS frame bytes.

djc.ochtman.nl•45 days ago

Do your own length-delimited framing?

jamesmunns.com•45 days ago

I did a whole podcast episode on this :)

Length-delimited framing works well over transports that guarantee no data loss (and no data corruption), but aren't reliable over mediums that may lose or corrupt data, which can cause an irreversible loss of synchronization

https://www.youtube.com/watch?v=KTrVpgw82Gg

jamesmunns.com•45 days ago

So: this works very well over TLS-secured streams, is uuuuuusually okay over TCP (which has some checksums, but there are still chances of data loss/corruption), but I wouldn't trust for UART or other similar "lossy" mediums.

djc.ochtman.nl•45 days ago

Ahh, fair, sorry — have not caught up on all of SDR!

just-some-ghost.bsky.social•45 days ago

having some kind of CRC-8 value that never evaluated to 0 might be useful for this? I feel like you'd have to be doing some weird COBS shenanigans to make that work tho. Like, what if you have a multibyte CRC and you have to stuff something in the middle of them to get the COBS framing right?

just-some-ghost.bsky.social•45 days ago

ig you could pick a 14-bit CRC, encode it into 2 bytes and just fix one of the bits in each to be ones. That avoids the problem of zeros at least. Then if there's any bytes stuffed in the checksum you'll know before you compute the CRC because you know the length of the CRC, so those can be included

jamesmunns.com•45 days ago

Maybe on this one! Though the CRC is calculated "as if" it is directly appended to the calculated payload, so inserting bits in between the CRC itself is also modifying the stream! I wonder if it's reasonable to do something like put the ones at the top of the first byte and bottom of the second

jamesmunns.com•45 days ago

you'd have to deal with the bitstream actually being len bytes + 1 bit (the top of the CRC) but maybe that's possible to do?

thejpster.org.uk•45 days ago

Surely a crc being weaker doesn’t matter as long as it is still sufficiently strong for your failure modes.

If you’re running over a UART then that’s random bit flips or dropped bytes. If you’re running over Ethernet or USB then these kinds of errors are very unlikely (modulo off by one errors)

jamesmunns.com•45 days ago

Sure, but the impact can be pretty big! CAN bit stuffing takes the effective HD from 6 to 2:

It's still probably "good enough", but you're losing a lot of the main value of choosing CRC over a much simpler integrity check

elfprince13.mumak.app•45 days ago

“Compress, then error correct” got imprinted into my head at some point in a grad school theory seminar discussion

thejpster.org.uk•45 days ago

But that’s CAN bit stuffing, not COBS. It would be interesting to see the same analysis done.

jamesmunns.com•45 days ago

Yep, I definitely need to just set up a brute force simulator on my computer and let it run for a week. I do have a mac mini m4 that is sitting mostly idle...

daveofthings.bsky.social•45 days ago

Could you COBS then CRC then interleave the bits of the CRC with the data in such a way that COBS is not confused? (Sorry I'm not familiar with COBS so this may be nonsense.)

jamesmunns.com•45 days ago

The general issue: if you modify the content of the message AFTER taking the CRC, including reordering, insertions, or deletions, then that's potentially an issue.

crcs are designed to protect "bits on the wire in that order", if you change the bits, then you're breaking the contract

daveofthings.bsky.social•45 days ago

Ok, COBS is really interesting and this is indeed a fun puzzle. My instinct now would be to calculate the CRC32 as usual then encode it in 5 bytes instead of 4. Each 4-bit block of the CRC could be mapped to 5 bits in a way that no input generated all zero output. So COBS first, then encoded CRC.

daveofthings.bsky.social•45 days ago

A more efficient way of encoding the CRC32 in 5 bytes would be to simply XOR the four bytes with a non-zero mask then append that mask as byte 5. The mask could be chosen from one of 5 fixed values such that it didn't match any of the input bytes. So no 0 outputs would result.

jamesmunns.com•45 days ago

yep, but like I said here: https://bsky.app/profile/jamesmunns.com/post/3lgnuccet722x

Once you're moving or modifying the raw bits on the wire, you're having an effect on the preconditions assumed by the math behind the CRC.

daveofthings.bsky.social•45 days ago

This wouldn't change any bits that were covered by the CRC. I'm thinking do the CRC on COBS encoded stream. Then instead of appending the CRC (violating COBS) Do this 4 to 5 byte encoding and feed that to COBS.

addypb0.bsky.social•44 days ago

encode the crc in a different way that avoids framing bytes but preserves the HD. 8-14 modulation as used on CDs to avoid runs? increased message length only applies to the CRC, so reasonably low overhead

tjallingt.com•8 days ago

I'm curious what you ended up doing? Did you find a solution or best practice?

cr1901.bsky.social•45 days ago

Interesting question that I simply do not have the spare cycles to think hard about :(...

crespum.eu•43 days ago

This was new to me, but today I was having a look at the just-released sources for the Pebble watches and I came into this: https://github.com/google/pebble/blob/main/platform/robert/boot/src/drivers/dbgserial.c#L131

jamesmunns.com•43 days ago

Hah, if it's good enough for pebble, maybe it's good enough for me :)

macegr.bsky.social•45 days ago

It’s all about reducing probabilities. I’ve been happy with COBS packet framing of CRCed packets. You will detect the overwhelming majority of bit errors in the payload and in the CRC.

jamesmunns.com•45 days ago

Sure! But if we're settling for HD=2 (or less), does it make sense to use something as relatively expensive as a CRC?

To be clear, it'll never be worse than 1/2^n, so crc32 is still a 1/4B chance to hit, even with "degraded" performance! But CRCs *should* be much stronger than that.

jamesmunns.com•45 days ago

And don't get me wrong, "just yolo" isn't THAT bad of a choice! I'm just itching for something better, if it's possible.

macegr.bsky.social•45 days ago

Perhaps you can dynamically sacrifice overhead for reliability depending on the type of message. A less critical sensor reading gets a 16 bit CRC and yolo. Missile launch command you have long checksums or even repeating the same packet several times.

jamesmunns.com•45 days ago

Downside of writing a comms library, you have no idea what your users are going to do with it :)

macegr.bsky.social•45 days ago

Right. This is Pandora’s Box you’re opening. I wonder how exactly many dev teams have death spiraled due to an eternal damnation of trying to abstract away every hard decision and baby proof every sharp edge. It’s admirable to get near 100% coverage but too many 9’s are certain doom.

lonjil.xyz•45 days ago

A silly solution that came to mind but that doubt would be acceptable, is to include a counter in the message, and increment it until the CRC value doesn't include any zeroes.

jamesmunns.com•45 days ago

This isn't silly at all! In fact it's more or less EXACTLY what Koopman himself suggested when I asked. It's a bit unfortunate because it means you need to perform multiple attempts whenever a zero byte is found, and is theoretically not very well bounded.

But you're definitely not off-base here.

lonjil.xyz•45 days ago

The unboundedness is why I felt a bit silly suggesting it, though, sometimes such try again solutions really are the best so I suppose I shouldn't think like that.

I don't recall the math of CRC nearly well enough to know whether this is plausible, but I wonder if it would be possible ...

lonjil.xyz•45 days ago

... to directly calculate an additional byte to add to make the CRC value not have any zero bytes without too much computation.

aviva.gay•45 days ago

this + maybe a bound where you give up if the pathological case poses issues (does one even exist)

Comments

Posting Rules

Reply