SCCS has been introduced in 1972 by by Marc J. Rochkind at Bell Labs.
Marc J. Rochkinds home page is here  and here is the story how he
invented SCCS, written by him Tue Nov 10 09:49:32 AEST 2015 on the mailing list:

Since you asked, here's the true story of how I came up with the delta
encoding, a story never before told.

I was living in a garden apartment in Sayreville, NJ, and at night would
walk my girlfriend's dog along a hillside just outside our front door. It
was usually cold, I didn't like the dog (still don't like dogs), and hated
dodging the piles of dog shit while he tugged on the leash. So, as a coping
mechanism, I used to let my mind wander, and one evening it was wandering
and wondering about a problem I was struggling with, which was how to store
the source and the deltas all in the same file. (It was a "data set," on
the IBM OS/360 system we were using--we weren't on UNIX yet.)

Anyway, no doubt simultaneously with this unpleasant animal taking a shit,
I came up with idea of surrounding pieces of text with markers. (The
algorithm itself is documented in my original 1975 paper, which you can
read about here:

(Wouldn't this be an even better story if I said that the little piles of
dog poop on the hillside looked like markers in the soft glow of a full
moon? It's not true, but perhaps I'll tell it that way if the occasion
arises in the future.)

When I got inside, I started to sketch out how the markers might work, and
came up with interesting observation that insertion start/end markers
obviously nested, but deletion start/end markers did not nest with insert
start/end markers. This is obvious if you think about it the right way:
When you delete, the text you're deleting could have been added at various
times, but when you insert, the inserted text is always added at the same

I didn't have replacement markers; insert and delete were enough, I thought.

I kept fooling around with the idea until I had an algorithm that I thought
would work to retrieve any version with a single pass. (It's in the paper,
referenced above.)

To prove the algorithm to be correct, I enumerated all possible cases of
insertions mixed in with deletions. I don't recall how many cases I had,
but I think it was around 20 or 30. Then I painstakingly went though every
case, making sure the algorithm produced the right answer. This was a rare
example of me doing actual work.

Coding it up, as I remember, was very easy, as the scheme is pretty simple.
I'm sure I had it running in SNOBOL4 in a day or two. Redesigning SCCS in C
for UNIX came maybe a year or so later, but the algorithm remained the same.

Larry [McVoy] very kindly says: "SCCS has interleaved deltas. It's a brilliant
design that has far far better performance than anything else out there."

Maybe it was brilliant, but I can tell you that I was just trying to pass
the time while that stupid dog did his business.


Last change 2016/02/23