Amanda Majorowicz: This is Self-Directed Research.
James and Amos, our hosts, get really excited about different
topics and each week they take turns presenting their ideas to each other.
Like the most recent episodes, you can check out the website, YouTube, or Spotify
to see the video presentation in action and visit sdr-podcast.com/episodes for
previous episodes, more presentations and videos, show notes, and transcripts.
New episodes are published every Wednesday.
This week, James presents "Frame Synchronization: Just simple
enough to cause problems."
But first, a quick word from him.
James Munns: The Self-Directed Research Podcast is looking for sponsors.
If you would like to promote your company, project, conference, or open
job positions, stay tuned to the end of the episode and send us an email to
contact@sdr-podcast.com for more info.
This is one of those things that like- that valley of it seems simple
enough that everyone does it and everyone gets all the little subtle
things wrong and sometimes don't even know the right name of terms, so...
today I'm talking about frame synchronization.
Which is a big fancy word that is step one of make computers talk to computers.
And it actually is a fairly straightforward thing, but the
problem really boils down to:
How do we decide where one message ends and the next message starts?
Which if you live in a world of TCP or UDP sometimes you feel like this
is very simple, but even in TCP and when I'm talking about embedded
stuff, usually things like serial ports, it gets a little trickier.
Amos Wenger: I already have a story.
I'm sorry to interrupt.
But I remember I did some work regarding diffing and patching when I worked at
itch.io, the game marketplace for indies.
And it's so fun because if you read papers from people working on
string sorting algorithms, which are mostly used in biocomputer science-
James Munns: Like DNA sequencing patterns and stuff?
Amos Wenger: So what they do is they're like, "Well, you see, you have an
alphabet and then you just make up, like, maybe your alphabet is like 256
values and then you make up a 257th symbol and that's your, your stopper.
That's the end value.
If you encounter 257th symbol, then you know the sequence is over.
And you're like, "But that's...
that's not how bytes work.
That works in the paper, but not in my code!"
James Munns: This is exactly what we're gonna get into.
So, we're talking about usually a sender and a receiver.
And a lot of times it ends up being bidirectional, but we can
look at just one of those first.
And the metaphor, which is totally...
I wanted to make it equally out of date for everyone.
So we're gonna be talking about telegrams.
Or telegraphs, actually.
So you have, you know, an office in one city, and then a wire that
goes to another city, and you've got someone with Morse code on that.
But these are people who don't have cell phones, and they don't have a
landline that they can call each other.
They literally only have the wire that goes from the one office
in Austin to the other office in Chicago, or whatever cities you
would like to use for the metaphor.
But they only have the one wire in between them, and they've got
Morse code or something so they can decode symbols from each other.
But they want to act like, sort of like a post office.
People want to walk in off the street and say, "I want to send
a message to my buddy in Chicago.
Here it is on a piece of paper.
Please get it there."
And we have to figure out how these two people operate with each other
and negotiate with each other.
And when something goes wrong, if one of them gets up for coffee and
they come back and they sit down and they missed the first half of the
message, how do they figure out how to get unconfused with hopefully the
least collateral damage possible?
Like, okay, at least I only lost one message with my unplanned coffee break.
And when we're trying to come up with this, like you're saying,
like in those papers, how do we decide which of these solutions are
good and which ones aren't good?
Like which ones sound good, but in the real world are practically- like in your
example, where I have a 257th value.
Okay.
Now, well, every symbol has to be two bytes now, which means we've just
reduced our total efficiency by half.
Is that good?
Or is that maybe not so good?
So when we talk about good, there's efficiency- so like, how
efficient are we at using all the values we can send over the wire?
There's our robustness, so what happens if a message gets lost?
Like we walk out of the room or someone cuts the wire or the connection 's bad.
What if the data is corrupted?
So like, what if we get some weird radio noise and it makes it sound
like a message is something else.
Or desynchronization.
This is sort of that, like: you walk out of the room and you walk
back in halfway through and you go, "Wait, I don't know if...
how many did I lose?
Am I halfway through a message?
When's the end of this one?"
How do I get back on track?
And simplicity.
Like the least complexity we can get away with is usually great because there's
less places for things to go wrong.
You can have like a very complex setup but it means that now you have
to think about all this failure modes and this tree of failures that I could
possibly have, and deal with that.
So we're back on our telegraph.
We have one sender and one receiver.
And most importantly, they don't control the content of
the messages that they send.
People are going to walk in off the street and want to send
whatever they want to send.
And you can't really trust the people walking in off the street
aren't trying to mess with you just because that's what they find fun.
Because people do that for...
fun.
The only thing we can control is how we as telegraph operators have
agreed to send these messages back and forth- the framing, how do we
package these messages and encode them and decode them over the wire.
You and I can decide on that because we went to a convention somewhere at
some point and decided and wrote down these rules on a piece of paper but we
can't make changes to people's messages to just fit how we're feeling today.
So, normally there's two main ways that you can do this.
You can either do what's called "in band" signaling or "out of band" signaling.
Out of band signaling could be something like: we have two wires, and only you and
I are allowed to use that second wire.
We use that wire to just beep every single time we're done.
Or, we do something that's illegal.
Like, we hold down the button for way longer than we should.
Like, someone can't walk in and tell me to hold down the button for ten seconds.
But I could decide to hold down the button in a way that people off
the street aren't allowed to do.
And these go back to those efficiencies of like: well, now I have to run
two wires or now I have to spend a bunch of time holding that down.
And that gets into our trade offs.
But these are things that are illegal for the message to have
in them, but are legal for you and I, as the operators, to decide on.
This is like the ethernet frame does something that you're not allowed to
have in the payload of the ethernet value or something like that.
So these are like, common solutions that I see and how
they're actually not very good.
But if you haven't thought of how all of the ways that they can fail,
how you might think they are good, but they are perhaps not so good.
So one of them is just line silence or holding down the button
for a certain amount of time.
You say, "Look, between every message, we're going to sit
quietly for five seconds.
And I promise that while I'm tapping out that message to you in Morse code, I'm
good enough at Morse code that I'm never gonna pause for more than five seconds."
And if you hear a silence of five seconds, you go, "Rip off that piece of paper,
that message is done, get the next piece of paper, I am ready for the next one."
And this is really great because it's simple.
You don't have to think that much.
You go: if it's quiet for five seconds, I have a little stopwatch or something.
If it's quiet for five seconds, we know it's done.
And it's not something that someone can affect.
You can't write in your message, "Please pause for five seconds."
Cause I go, "No, you can't ask me that.
You can give me the data that I'm going to send.
You can't tell me how to send it."
Now it's, you know, somewhat efficient?
You know, it's not that long, depending on how long you need it to be, it could
be less efficient, but it's fairly robust.
Like it's something that we don't have to worry about: as long as you promise
that the sender can never get distracted.
If someone walks in and talks to me while I'm typing out this message, can I ever
be distracted for more than five seconds?
Because if I can, then we have to increase that time for it to be suitable.
This sounds weird for a telegraph operator, but if we're talking about a
microcontroller or an embedded system: if we have hardware interrupts or someone
presses a button or it's time to draw the screen, how do I guarantee that I'm
never distracted from receiving messages for more than the amount of time?
And do I actually have a stopwatch that I can accurately measure that time so
that if I'm counting to five and I only count to 4.9 because I got a little
distracted and you think you've ended a message and I don't think you've ended
a message, we can get out of sync.
So we do need maybe a longer amount of time than you might think, just so that if
something does go wrong or weird, or I get distracted, it's not too little of time.
So this one's maybe okay, but also sometimes it requires some hardware
capability that is more challenging than you might think to do accurately.
Amos Wenger: Right.
And to make it more reliable, you have to sacrifice efficiency.
James Munns: You make it longer so that you go, "Well, I promise
I will never be distracted for more than 200 milliseconds."
Amos Wenger: Yeah.
Yeah.
It's
James Munns: easier to imagine
Amos Wenger: with smaller values 'cause like yeah.
The telegraph example shows its limits here.
But if you're thinking of like, it's, I dunno, it's four
milliseconds or something.
Yeah.
I can see them getting stuck for that long.
James Munns: Yeah.
So the other one, and this is the one that I see most common when people roll
their own is they use a length header.
So I might say, "Look, I'm going to count the number of words in this message.
And before I send the message, I'm going to send the number of words,"
and that way you can count how many words you receive and you go: cool!
He said 200, and then I count my messages, and when I get to the 200th
word I rip the piece of paper off the sheet and I know that I am done and
now I start listening for the next one.
But let's say I went to the bathroom and I come back and we're in the
middle of receiving a message.
You are sending me a message about how many horses are being sent on the
train to Chicago today or whatever.
And I go "Shoot, shoot, shoot, shoot.
Uh, cool.
I need to get back.
I need to get back...
uh, let me just listen for a number.
I'm- I'm back I was distracted, but i'm listening for a number," and you're
talking about sending 200 horses.
And it's the last sentence of the message and I go, "Oo!
Oh, they said 200!"
So I write down 200 and I start counting 200.
There's four words left in the message.
So now, I've started counting 200, we get to the four words in your message.
Then there's some silence while we're waiting for you to send the next
message, you start counting the next one.
And I get to the end of the 200, and you're still talking about someone
else's message, and I've totally lost this one, I've become desynchronized,
and everything is terrible.
So this is one of those things that I see people do when they have TCP
with TLS, where you can guarantee that all the messages will be there.
You've got an operating system, buffering messages for you and things like that.
And if you have TCP and TLS, it's probably fair.
If you lost some messages, your TCP connection is just going to fail.
And TLS is going to go, "Oops, we're out of sync."
And you'll either recover with TCP or you won't.
And the connection will be reset or whatever.
But even with TCP with no TLS...
there's not that much- like TCP is a reliable protocol.
But TCP itself only has a 16 bit CRC on it.
The chances of something going wrong is not impossible.
And if that 200 becomes 201 because you have a bit error, all of the sudden
now you are totally desynchronized.
And I am listening into your next message and all of a sudden it's
not a number and I am very confused.
Or I could lose a byte or- you know, all these ways that things could go
wrong, if you don't have a really rock solid medium like TCP and TLS.
On a serial port, if you get a little glitch and all of a sudden
you lose a byte: what do you do?
How do you recover?
So this length header is very efficient because it only takes, you know, us
putting the length that we're going to put at the front of the message.
But once we get out of sync, we're done.
And trying to figure out what is a data number, and what is a header number
is tremendously hard to figure out if you only have a length header prefix.
Amos Wenger: Which is why you always add a four byte magic number in your header.
James Munns: It's true!
And you can reduce the false positives...
but there's always a chance that someone could come in and go, "Okay, I'm going
to send a message with just a number followed by the magic word over and over
and over and over and over and over again, and see how much I can ruin your day."
Amos Wenger: Some people do that on purpose for fun.
I think it's called a queen, a quine.
What, how's it pronounced?
Like a-
James Munns: Oh, well, quines are when you make a program that encodes a different
program that eventually wraps itself.
I was thinking of phreaking, like, P H phreaking, like phone phreaking.
The people who had you know, they found a whistle...
This is in band signaling, like when you have a phone and you play a certain
tone that signals the end of the call, or 'stop billing,' and you can just
play that little tone in there and all of a sudden the hardware in the
central office goes, "Oh, stop billing.
Okay!"
That's in band signaling, which we don't love.
Amos Wenger: Some people could do it by hand, like with no
hardware, no, physical whistle.
I was thinking of the files that are like valid PDF, but also a valid PNG
and also a Linux executable and also something like, that's very fun.
You can- yeah, you could just accidentally, sort of on
purpose, use other people's magic numbers because it's fun.
James Munns: Trusting- trusting user-provided data
is always spicy and fun.
Amos Wenger: Yes, Amanda, please, please edit in the honk sound
from, uh, Untitled Goose Game here.
James Munns: Exactly.
So, the other one that I see people use, and this is like common back to
the dial up days, is using a flag word.
So we decide a certain word means 'end of message,' but like in your
DNA example, if we're sending bytes, we only have 256 different values.
And someone might want to include that value.
Like, if we're sending ASCII, there's probably some ASCII control
character we can go: Okay, well, there's literally a character
called ETX for end of transmission.
Which, if you're just sending ASCII characters and you agree on the rules
that someone walking in off the street can only send ASCII characters: cool,
you've got all 128 reserved bytes that you're allowed to use- or, excuse
me- 128 characters or whatever that you're allowed to use and then half
that you're not allowed to use because they have special semantical meaning.
It does mean that our efficiency takes a hit because we're very rarely sending
something in that back half, you know, we lose a bit of efficiency, maybe it's fine.
But this all breaks down when we leave the world of plain text and we want to
send a photo or a video where the color values that we're actually sending across
the network here can be the full range.
Like it can be any value of a byte.
And so you might accidentally send a picture that's all brat green, and it
turns out that brat green has exactly the same value as ETX or something like that,
and you're sending a bitmap across the network that is "Oops, all ETX values."
Amos Wenger: I'm sorry.
Is this, is this a technical term?
Like brat??
Okay.
James Munns: I don't know!
Amos Wenger: I'm sorry.
I didn't keep myself up to date.
I just, I'm sorry.
James Munns: Do I look like Pantone to you?
But yeah, so, I mean, the normal way that you say it is you go: Okay, well,
ETX is our end of transmission word.
And if it happens to show up in your message, tell you what, you're
going to escape that message.
You're going to send the character DLE.
Or data something escape before that.
And this is kind of like putting backslashes before new lines in
a text or something like that.
You say like, "Ignore the next thing that I'm going to send.
It's a normal data byte, not a special meta character," or something like that.
But then the problem becomes: well, okay, well, if you're sending that
message that's all that escape character, you now have half efficiency because
every time you send it you have to send the escape character behind it.
And then what do I do if the two data bytes are "Ignore escape
character, end of message."
And then you have to put more- it's like that problem where you just keep
adding more backslashes until it works.
And if you have a malicious attacker, they can blow up, "Okay.
Well, you said that I can send a hundred data characters for a
dollar," or something like that.
"Cool.
The hundred that I pick are the worst nightmare ones for you."
And all of a sudden you're sending five, 600 bytes of transfer for 100
bytes of actual data across the wire.
Amos Wenger: Mm hmm.
James Munns: And so this generally works as long as you have, you know,
scrambled data or whatever, if it's encrypted or whatever, and you're
unlikely to get a run of exactly the same characters all over the place.
Sure, you can maybe make it work, but it's either unbounded or an incredibly high
bound of potential worst case going on.
And again, if you're on an embedded system and you need enough room to buffer all of
the bytes that you're going to receive, you got to think about that because either
you have to decode everything one byte at a time so you can do the decoding,
or you need to DMA a huge chunk of data.
But if your worst case is eight times bigger than your potential data transfer,
then that's a lot of wasted space for something that almost never happens.
So these are all the ones that I see people commonly use.
These are the, "Ah!
I know a trick to solve this."
And then you end up with people where you go: well, what happens if you reboot
one device cause you did a firmware update halfway through a conversation?
Now they're out of sync and these two devices can never get to each
other or they get accidental buffer overflows because: oops, my decoding
used eight times more of the space that I thought I could use.
Amos Wenger: One problem I didn't, I thought about, but I forgot to
bring up with the length header is that you don't always know the
length of the message you're sending.
I imagine in the embedded world, most of the time you do, but
I, I'm, I am now thinking about HTTP cause you forced me to.
Also, cause I've been working on this implementation and we have,
you know, we have chunked transfer encoding and you don't know,
you're just sending bits at a time.
So, you know, the length of the chunk, we don't know the
length of the total message.
And then you have to do something even fancier.
James Munns: Yeah.
And these frames are chunks, but it's still a problem of like, you
can't opportunistically send things sometimes, if you don't know the
size of the chunk, which might be variable and things like that.
So it also goes back to efficiency of like: you have to be able to buffer
up some amount so that you can count how much you buffered so that you can
send it versus a totally asynchronous, like, stream of bytes, for example.
So we have enough time to get into my favorite one, which is still from the
days of dial up, but more recent dial up, like early 90s or something like that.
And it's called COBS, or consistent Overhead Byte Stuffing.
Which is actually a funny combination of most of the previous ones, but it
allows you to do things in a fairly- like it's a little more complex
than any of them, but has almost no totally awful, pessimal case.
So I'm just going to run down some of these rules and we'll
get to the point where we have a total rule between the two of us.
And now we're back to talking about real world 8 bit bytes instead
of, you know, telegraph words.
Amos Wenger: Do I get a guess as to how it works?
Knowing that I've never- the, acronym is is familiar.
I'm pretty sure I read about this before, but I've already forgotten all about it.
Do they just change- like, does the- is there an escape character, but it
depends on the position in the stream?
So that you can't, like, the pessimal case is never really hit?
Cause it changes around?
James Munns: Sort of...
but okay, let me explain it.
So, first rule: a null byte always means end of message.
If you send a zero on the wire, that's the end.
That's the, you know, perforated edges, we are now done, tear off the
old message, go with the new one.
So then you say, well, what if I want to send a lot of zero data bytes?
So the first rule is a zero always means the end of message.
And whenever you give me a user message, I'm going to stick a
zero at the end of your message.
I'm going to append a zero to the end so that I know that
that is the end of the message.
But now I need to figure out: what do I do with all these zeros inside
of the message or the potentially the zeros inside of the message?
Well, what I'm going to do is I'm going to take my zero at the end
and I'm going to work backwards.
And anytime I run into a zero, I'm going to count how many bytes it's been
since the zero, like working backwards, and I'm going to replace the zero with
how many bytes until the next zero.
And then when I go back to the next user zero, I'm going to be counting
again from that new position and I'm going to count how many bytes it would
be to the next zero that got replaced.
So essentially what I'm doing is I'm making a linked list of
all the zeros in my message.
And I work all the way until I get to the front of the message
and I put the number there.
So let's say I put 14 there.
So I will start with 14.
I know that's a header byte I'm going to take the next 13
bytes as normal data bytes.
And when I get to that 14th byte, it's going to be a number that's not zero.
Let's say it's eight.
That's where a zero should have been.
So the data I'm going to replace there with a zero, and I'm going to start
counting again until I get to eight.
And if you ever are counting down like this and you hit a zero,
you know that you've reached the real end of the message.
Amos Wenger: And it also means you, you can tell the boundaries of the
messages without knowing any of this, just by looking for zeros.
Yeah.
James Munns: Yep, before you actually start decoding this, you
can just keep buffering until you get a zero and then you go, "Ah,
now it is time to do something."
And so you go look at the first byte, you walk forward, and essentially this is
also a little bit of an integrity check.
If you hit the zero when you were counting but that's not where you expected,
you know that you've lost something.
And it means that you go, "Welp, nope, that was a poorly framed piece of data."
And the nice thing is, is in this case, you have at least two bytes of overhead.
You've got the zero you're sticking at the end, and you've got that number
that you're sticking at the front.
If you sent all zeros, if you were trying to be an ass and sent all zeros here,
that's actually perfect for me because then every data by just becomes a one.
It just goes link, link, link, link, link, link, link, link, link, link.
The worst case is actually you send no zeros.
And this is the sort of final rule.
If you ever get to- I forget the number, it's like 254, you don't go all the way
to 255- but if you get a 254 and there hasn't been a data zero, you insert
one more header byte there that you know that you're going to throw away.
It's basically kind of like sticking an extra header byte
in the middle of the message.
Amos Wenger: Right, yeah.
James Munns: So, you know, that if you ever see a 254, you go: ah, I'm
going to be counting towards the next one, but there's no actual zero
data byte that I'm replacing there.
It's just a placeholder.
Which means your worst case is bounded in the worst case to be two bytes
plus one for every 254 data bytes.
Amos Wenger: Right, yeah.
James Munns: Which means effectively for it, like if your max message
size is like a kilobyte, your worst case overhead is something like
six bytes or something like that.
You can see it scales really proportionally to the length.
And most of the time you do just randomly have zeros in there.
So you don't even hit the worst case very often.
Amos Wenger: Yeah, Yeah, that's...
that's so- I like that because it's a trick.
It's just someone figured out a nice design and it's it's as old
as the world itself almost...
like the 70s probably?
James Munns: And it's one of those things where this is something that
is used in telecoms, like when you're streaming data between telecoms and
things like that, and you're trying to do message framing of where does one
message end and when does one start.
This is something that's fairly simple, which means you could do
it in electrical logic or whatever.
And there's been a lot of papers on this, of like: how do we do message framing?
Where people come up with these incredibly complex encoding schemes
and things like that and the baseline usually is COBS because you go "Well,
it's not perfect," but to be honest, it's dumb as hell and it's really easy
to do in either hardware or software.
And you get some of these robustness checks for free.
Like, you know, I can tell if I have a properly terminated message,
I have a very clear way to say if I get a zero we're done here
Amos Wenger: Yeah, yeah.
I was thinking like, I now better understand the slide where you
said, "How do we get unconfused?"
Because this is a nice way in COBS is like, if you don't know what the
heck is going on, just wait for a zero and try again with the next frame.
James Munns: Exactly!
Yeah, and if you ever get confused if you're halfway through a message, and
you go, "... That didn't line up," like something just went wrong or I had an
error locally, or I walked in from the bathroom, you go, "That message is gone.
Sorry.
Sucks.
But now I know my job is to sit here and wait for the zero."
And then we can at least move on from there.
Amos Wenger: Exactly.
But you don't have to like, tell the peer: hey, can you...
I don't know, like something went wrong.
You just need to keep listening and ignore until you reach another, another zero.
James Munns: And that's your resynchronization point.
It means that you have this perfect resynchronization point,
which is a zero on the data.
This is in fact so useful, I use it in Postcard and Postcard
has a built in flavor for this.
So as you're serializing, you can do the COBS encoding at the same time,
or as you're deserializing you can do the COBS decoding at the same time.
Where essentially as you're pulling bytes from the wire or pushing bytes to
the wire, you can just do this encoding or decoding because it requires like...
a couple of lines of logic and like one or two bytes of
intermediate context to store.
But it's basically stupid simple and you can do it for almost free as you're going.
Amos Wenger: God, I like this trick so much.
James Munns: So if people are building it themselves and you've got a serial
port from here to there and you have to do it and you don't have a reliable
line, like TCP and TLS: probably use COBS with something like Postcard so that you
can just get the encoding and decoding of frames for free and try and think
of what your hardware can support to figure out how to hardware accelerate it.
And we have talked about DMA.
And so this is one of those fun things where you can just say:
hardware, give me messages until the line goes quiet for a little bit.
Okay.
Now I'm going to look through that, see if I got a zero.
Pull that out, save the remainder off, and then wait until the next time my hardware
pings me for something to be ready.
So, it is one of those things that it's very easy to automate at this point.
Which is why it's one of my favorite.
And I have to say thanks to Whitequark, who showed me, because
I was trying to come up with something dumb and complicated, and
Whitequark went, "Have you heard of this thing from the dial up days?"
and I, I went, "No..."
and it became my new favorite thing, and it's, it's just
become one of my go-to tools now.
The Self-Directed Research podcast is made possible by our sponsors.
We offer 30 second host-read ads- like this one- at the end of every episode.
Not sure how to get your message out, or what to say?
Let us help!
If you'd like to promote your company, project, conference, or open job positions
to an audience interested in programming and technical deep dives, send us an
email to contact@sdr-podcast.com for more information about sponsorship.
Thanks to all of our sponsors for their support.