Where Does It Start?

You want to send Mira a sentence. Not HI this time but an actual sentence, something like meet at 7, and you want her to be able to read it even if she was not staring at the wire the instant you began. That last condition is the whole problem, and it is worth watching it fail properly before trying to fix it.

You type meet at 7. That is nine characters, seventy-two bits, and your card puts them on the wire. Mira’s machine, meanwhile, was doing something else, and it starts listening a few bits in. It has no way of knowing this. From its point of view the wire was quiet, then bits started arriving, and it began grouping them into eights the way the two of you agreed. These are your seventy-two bits, together with what she gets if she happens to start reading at each of the first few positions.

Start at bit 0:  m e e t   a t   7      ← what you sent
Start at bit 1:  Ú Ê Ê è @ Â è @        ← eight valid characters, none of them yours

Start two bits late and you get a different set, mostly invisible control codes this time. Three bits late, different again. Every one of those readings is made of legitimate entries from the table, and not one of them is meet at 7. The part that ought to trouble you is that her machine has no way to tell which reading it is in. It grouped bits into eights. It looked them up. The lookups succeeded. From where it stands, Ú Ê Ê è @ Â è @ is as valid a message as meet at 7. This is the worst kind of failure a system can have. It is not a crash and it is not an error. It is a perfectly confident wrong answer, with nothing anywhere to suggest that it is wrong.

Nor is the trouble confined to the beginning. When your sentence is over, your card leaves the wire at zero. Mira’s card keeps reading zeros and grouping them into eights, and every group of eight zeros is a valid character too, since the table has an entry for it. Is she receiving a message made of nothing-characters, or is the wire idle? She cannot know. The message has no end, any more than it had a beginning.

The wire has done nothing wrong. It carried your bits in order. It has no concept of your message, of where it starts, where it stops, or that there was a message at all. It carries a stream, and the message is a thing that exists only in your head and, if you are lucky, in Mira’s. You are going to need an agreement that puts the boundaries into the stream itself.

Consider how you would solve this if you were shouting across the courtyard instead of using a wire. You would not launch into “meet at seven” and hope she was listening. You would call her name first, and then, once she had looked up, deliver the message. The name does two things. It gets her attention, and it tells her that whatever comes next is the beginning.

You can do the same thing with bits. Agree on a special pattern, a sequence that you will always send before a message and that she will always wait for before she starts grouping. Something like this:

10101010 10101010 10101011

Two bytes of alternating ones and zeros, and then a third that ends differently. Her card, when it is idle, does not group anything. It watches the stream for that pattern. The alternating bytes are easy to spot even from the middle, since nothing else looks like them, and the final 11 says that this is the last one and the message starts on the next bit. Now it does not matter when she starts listening. If she joins in the middle of the pattern, she still catches the tail of it and knows where the message begins. If she joins in the middle of the message, she sees garbage, ignores it, because she is only looking for the pattern, and picks up cleanly at the next one. The pattern is a place to stand.

Call it a start marker for now. It has solved half of the problem at no extra charge, because once the start marker exists silence stops being ambiguous. When the wire is idle, her card is waiting for a marker. It is not reading zeros as characters, because it is not reading characters at all until it is told to start.

The other half is harder than it looks. The obvious answer is to do the same thing again: agree on a special byte that means the message is over, and send it last. Say you pick a byte that is not a printable character, something like 01111110, which we will write in hexadecimal as 7E because it is shorter. You send the start marker, then meet at 7, then 7E. Mira’s card sees the marker, starts grouping, reads characters, sees 7E, and stops. Call it an end marker. It works, for a while, and then a few weeks later you want to send Mira a picture.

A picture is not text. It is a long string of bytes that stand for brightnesses and colours, and those bytes can be anything at all. Every value from 00 to FF shows up somewhere in a typical image, and that includes, inevitably, 7E. So you send a picture. The start marker goes out, and the picture’s bytes follow it. Somewhere around the four-thousandth byte the picture happens to contain a 7E. Mira’s card sees it and does what you agreed: it stops. It hands her machine a picture that ends abruptly at byte four thousand, and then, which is worse, it goes back to waiting for a start marker while the rest of the picture streams past, ignored. Eventually some pair of bytes in the remaining image happens to resemble the start pattern, and her card starts grouping again from the middle of nowhere.

You have built a system in which the content of a message can break the boundaries of the message. That is not a rare edge case. It is a guarantee. The moment you send anything other than carefully chosen text, it will happen.

You have two ways out of this, and they lead to different places. The first is to stop the content from containing the marker. You cannot control what is in a picture, but you can control what you send. Agree on a second special byte, which we will call the escape, say 7D, and agree on a rule: whenever the real content contains a 7E, do not send 7E. Send 7D followed by a modified version of it. Mira’s card, when it sees 7D, knows that the next byte is content and not a marker, and puts it back the way it was.

Now 7D is special too, so if the content contains a 7D you have to escape that as well, sending 7D followed by a modified 7D. It is a little fiddly, but it is finite. Two special bytes, one rule each, and every possible sequence of content bytes can now be sent without ever producing a bare marker. The message gets slightly longer, by one byte for every 7E or 7D in the content, which for most content is almost nothing. This is called byte stuffing, or escaping, and once you have seen it here you will find it everywhere. It is the same idea as writing \" to put a quotation mark inside a quoted string. The string’s boundary is ", the content wants to contain ", and so you escape it. The problem and the fix are the same, at a completely different layer.

The second way out is to have no end marker at all. Instead of marking where the message stops, say up front how long it is. Right after the start marker, send a number, two bytes say, which allows lengths up to 65,535, and then send that many bytes of content. Mira’s card reads the length, counts that many bytes, and stops. It never needs to look at what the bytes are, so it does not matter whether they contain 7E or 7D or anything else. The content is opaque, and the boundary is arithmetic.

Put the pieces together and every message you send now looks like this on the wire.

┌──────────────┬────────┬──────────────────────┐
│ start marker │ length │ content              │
│  3 bytes     │ 2 bytes│ as many as length says│
└──────────────┴────────┴──────────────────────┘

Mira’s card waits for the marker. It reads the length. It collects that many bytes, hands them to her machine as a unit, and goes back to waiting. If it joins in the middle of something, it sees noise, ignores it, and resynchronises at the next marker. The content can be anything at all.

This unit, a marker, some bookkeeping, and then a bounded chunk of content, has a name. It is called a frame, and the bookkeeping that comes before the content is called a header. You will be adding to that header for most of the rest of Part I. At the moment it holds a length. Soon it will hold a good deal more.

The thing to carry forward from this chapter is not the marker or the length. It is the problem. The wire gave you a stream, and a stream has no edges. Your messages have edges. Something had to put them there, and that something is an agreement, about a pattern or about a count. Every time in this book that you take a stream and try to pull messages out of it, this problem will come back. It will not be a wire next time. It will be a stream of bytes handed to you by a piece of software that has already done all of this framing for you and undone it again, leaving you with a smooth, edgeless stream of your own. You will need to find the edges in it again, and you will reach for a marker or a length.