The format of strings in early (pre-C) Unix

https://utcc.utoronto.ca/~cks/space/blog/unix/UnixEarlyStrings

by fcambus • 11 years ago

102 64 11 years ago

utcc.utoronto.ca

jamesfmilne• 11 years ago

That was anti-climatic.

bitwize2• 11 years ago

One of the worst programming ideas ever dates bavk even earlier than we thought.

If only Dennis had had the foresight to nip that one in the bud...

marvy• 11 years ago

what's your better idea? (hint: this has to work in assembly language.)

xenadu02• 11 years ago

Strings and arrays begin with one pointer-sized word that indicates the size of the string/array, thus making all the various mutant versions of functions that work with them unnecessary. And eliminate the requirement to specify length separately when passing as a function argument. And make bounds-checking trivial. And almost entirely eliminate buffer overflows.

This would naturally want malloc to know the type and count, eg: char[] x = malloc(char[], 100). That means no opportunity to screw it up (let the compiler turn that into the sizeof math to pass to the actual allocator).

If bounds checking is a performance bottleneck you could turn it off with compiler flags; that's not a valid argument against it.

But hey... all the various buffer overflows, RCEs, and various exploits are totally worth the minor performance gains /sarcasm.

crpatino3• 11 years ago

make str_t an opaque type. First char is always length.

1. If string is 0-15 chars long, str_t is a small string, aka char[16]. First byte is length, payload starts in 2nd byte, tail is always zeroed. Empty string is all zeros always.

2. If string is 16-248, str_t is a half string. The whole payload exist in a single contiguous buffer. First bytes is length. A pointer to the rest of the payload exist within the remaining 15 bytes, starting at the first alligned address. This way you can cast half string as small string when passing as value without knowing the size at compile time (and stil recover the rest of the payload). Gap between the length and the pointer is reserved and always zeroed.

3. For lengths 249 and higher. Each value 249-255 is not the lenght, but an encoded way to represent one or more styles of bigger strings. Not need to hold the payload in a single contiguous buffer. Remaining 15 bytes will hold a pointer to the data structure in the same fashion as half string. Reserved bytes are used to represent length if possible. If not, length is required to exist at a fixed position in the first buffer accesible when dereferencing the pointer.

oso2k• 11 years ago

ken had written most of the original asm kernel.

bitwize2• 11 years ago

But Dennis could have reversed it by giving C -- and thus later Unix -- a better default, you know, like Pascal had.

coupdejarnac• 11 years ago

I was hoping to read something juicy like null termination was created by a summer intern.

tomrod• 11 years ago

Nope! Only time-wasting and mind-engaging software like solitaire.

ghrifter• 11 years ago

So am I overachieving by trying to learn React+Flux and Angular.js + typescript and also trying to learn ASP.NET 5 MVC 6 while working my internship?

Maybe I should just make HTML 5 games instead...

noselasd• 11 years ago

This is the origination of null terminated strings in C:

"In BCPL, the first packed byte contains the number of characters in the string; in B, there is no count and strings are terminated by a special character, which B spelled ‘*e’. This change was made partially to avoid the limitation on the length of a string caused by holding the count in an 8- or 9-bit slot, and partly because maintaining the count seemed, in our experience, less convenient than using a terminator.

From https://www.bell-labs.com/usr/dmr/www/chist.pdf

holmak• 11 years ago

I have seen it claimed that null-terminated strings were encouraged by the instruction sets of the time -- that some instruction sets make null-terminated sequences easier to handle than length-prefixed ones. The article's error-message-printing code snippet is a good example. Does anyone think there is any truth to this?

HillRat• 11 years ago

The ASCIZ directive on the PDP-11 assembler took a string literal and blitted it to memory with a trailing NULL, so there was a convenience factor there. BCPL and B used null-terminated strings, so it made sense for C to inherit the practice.

Pascal strings were significantly size-limited due to memory constraints (an implementation detail), so there was a reason to prefer null termination, but in essence we're still slaves to an obsolete instruction set.

coliveira4• 11 years ago

Maybe that's not the whole picture, but I think a big reason for null terminated strings is that C has pointers. A char pointer makes it practical to move through strings and a NULL terminator is easier to handle than a size test. In the end, sized strings make C code more complicated, unlike other languages such as Pascal.

pjmlp6• 11 years ago

Which also has pointers, yet makes use of safe strings.

jamesbowman• 11 years ago

Yes, the PDP-11 instruction set makes null-terminated strings especially efficient. Strcpy() is 3 instructions per character, for example.

The PDP-11 features that make this possible are (1) post increment addressing and (2) MOVE instructions set the condition codes.

toast02• 11 years ago

Null terminated is going to be nice in most instruction sets, you don't need to keep track of a count, so you save a register, and you have one less thing to increment (or decrement). Loop condition is basically free too, loading the next byte into a register is going to set the status register, so you don't need a compare, you can just branch if the zero flag is set.

As long as you are handling good data, it's clearly more efficient.

rasz_pl2• 11 years ago

loading the next byte into a register is going to set the status register

not in x86

Zardoz843• 11 years ago

Also, null-terminated arrays are used for other stuff that not are strings. For example : https://developer.gnome.org/glib/stable/glib-String-Utility-... returns an null terminated array of strings.

ksherlock2• 11 years ago

Aside from the Zero flag, there was also a Negative/Signed flag. Setting the high-bit in the last character (or clearing it if the rest had the high bit set) was also a way to terminate strings and save a byte over null-terminated strings.

People who go ape-shit over 0-terminated strings would probably be even more upset if we still did that.

SCHiM2• 11 years ago

Yes, the architecture on which you're most likely reading this (x86 or x64) also has semi-dedicated string handling instructions, akin to higher level string functions.

For example, a string copy 'instruction' that copies a 0 terminated string from one location to another looks like this:

  lea esi, source_string
  lea edi, dest_string
  repnz movsb           ; copies esi -> edi until *esi = 0

rasz_pl2• 11 years ago

are you sure about that? http://docs.huihoo.com/help-pc/asm-repne.html http://faydoc.tripod.com/cpu/repnz.htm

repnz movsb is undocumented and undefined, MOVS doesnt modify flags, not sure how would that work

kazinator• 11 years ago

After skimming through this, I navigated around this Chris Siebelmann's site with the forward and back links, discovering something way more interesting than Unix strings and refreshingly relevant:

"How I do per-address blocklists with Exim"

https://utcc.utoronto.ca/~cks/space/blog/sysadmin/EximPerUse...

I run Exim, and I'm also a huge believer in blocking spam at the SMTP level, and also do some things globally that should perhaps be per-user. I'm eagerly interested in everything this fellow has to say.

username223• 11 years ago

I've followed his site for awhile, and he seems like a thoughtful person who likes to document his reasoning. I'm not a sysadmin, so I don't care about a lot of what he writes, but he's worth reading for stuff I care about. For example, he's pretty astute about the "how" and "why" of spam.

Thomas_Lord2• 11 years ago

Slightly off topic. The article doesn't call it out but there's a lovely assembly hack here. In:

bec 1f / branch if no error

   jsr r5,error / error in file name

       <Input not found\n\0>; .even

   sys exit

jsr calls a subroutine passing the return address in register 5. The routine error interprets the return address as a pointer to the string.

r5 is incremented in a loop, outputing one character at a time. When the null is found, it's time to return.

The instructions used to return from "error:" aren't shown but there is a subtlety here, I think.

".even" after the string constant assures that the next instruction, "sys exit", to which "error:" is supposed to return, is aligned on an even address.

By implication, the return sequence in "error:" just be sure to increment r5, if r5 is odd. I am guessing something like the pseudo-code:

inc r5

and r5, fffe

ret r5

ksherlock2• 11 years ago

Yep!

http://minnie.tuhs.org/cgi-bin/utree.pl?file=V1/sh.s

    error:
        ...
	inc	r5 / inc r5 to point to return
	bic	$1,r5 / make it even

Thomas_Lord2• 11 years ago

Thanks! Nifty!

castell• 11 years ago

The predecessor of Unix, Multics was written in PL/1 and was very innovative (modern OS still borrow "new ideas"): https://en.wikipedia.org/wiki/Multics

emmelaich• 11 years ago

How else would you implement them, seriously.

You have two choices, counted or terminated.

Counted places a complexity burden at the lowest level of coding.

With terminated you still have the option of implementing strings with structs or arrays with counts or anything.

And people did of course. Many many different implementations of safe strings exist in C; the fact that none have won out vindicates the decision to use sentinel termination.

derefr• 11 years ago

I always felt like NUL-termination, newline-separation, and (eventually) UTF-8 were all sort of complementary ideas: they all take as an axiom that strings are fundamentally streams, not random-access buffers; and they all separate the space of single-byte coding units, by simple one-bitwise-instruction-differentiable means, into multiple lexical token types.

Taking all three together, you end up with the conception of a "string" as a serialized bitstring encoding a sequence of four lexical types: a NUL type (like the EOF "character" in a STL stream), an ASCII control-code type (or a set of individual control codes as types, if you like), a set of UTF-8 "beginning of rune" types for each possible rune length, a "byte continuing rune" type, and an ASCII-printable type. (You then feed this stream into another lexer to put the rune-segment-tokens together into rune-tokens.)

In the end, it's not a surprise that all of these components were effectively from a single coherent design, thought up by Ken Thompson. It's a bit annoying that each part ended up introduced as part of a separate project, though: NULs with Unix, gets() with C, and runes with Plan 9.

One of the pleasant things about Go's string support, I think, it that was an opportunity for Ken to express the entirety of his string semantics as a single ADT type. That part of the compiler is quite lovely.

The format of strings in early (pre-C) Unix

Related Stories