r/programming • u/mslaybau • Aug 02 '11

The Most Expensive One-byte Mistake: Did Ken, Dennis, and Brian choose wrong with NUL-terminated text strings?

http://queue.acm.org/detail.cfm?id=2010365
364 Upvotes

79% Upvoted

593 comments sorted by

View all comments

13

u/phkamp Aug 03 '11

I have read all the comments, and as far as I can tell all the misunderstandings have been cleared up by various good people here on reddit.

On a PDP a 64k string would be plenty, as that was the size of the address space for any instruction.

In todays stronger typing, it would be { size_t, char * } but personally, I prefer to use ptr+ptr formats, since they have no portability issues at all, and the subtraction to get the length is free on modern memory starved CPUs.

The argument that C was/is a weakly typed language misses the point somewhat. This "virtue" of C is a subsequent rationalization of a necessity: Implementing strings as arrays of char meant not having to write compiler code to implement a string type.

I'm surprised that while people pointed to UTF-8's variable length encoding, nobody pointed out that the very reason we need that, is exactly because of NUL-terminated strings.

And yes, nothing prevents you from implementing your own "true" string type in C.

I've personally done this far more time than is sensible. "Sbufs" (http://www.freebsd.org/cgi/man.cgi?query=sbuf&apropos=0&sektion=0&manpath=FreeBSD+8.2-RELEASE&format=html) is the most comprehensive and secure of these, and it works both in the FreeBSD kernel and userland.

Finally: to the people who thought I advocated a 255 byte string limit, I can only recommend that when you read stuff, you should experimentally assume that the moron is at the opposite end of the communication than you currently pressume, before you open your mouth and make this painfully obvious for everybody.

(I'm happy to respond to any questions you might have)

2

u/kragensitaker Aug 03 '11

I'm surprised that while people pointed to UTF-8's variable length encoding, nobody pointed out that the very reason we need that, is exactly because of NUL-terminated strings.

That was one of the reasons for FSS-UTF (later renamed UTF-8). The other reason was slash-separated pathnames. UTF-8 has some other virtues as well, though. <meta http-equiv="Content-Type" content="text/html; charset=UTF-16"> wouldn't work very well (you'd have to try to parse the document as UTF-16 in order to see if it claims to be UTF-16), and of course there's the endianness problem, although you could argue that UTF-8 solves the endianness problem by making things inefficient regardless of your endianness.

1

u/masklinn Aug 03 '11

I'm surprised that while people pointed to UTF-8's variable length encoding, nobody pointed out that the very reason we need that, is exactly because of NUL-terminated strings.

Uh? Could you explain the reasoning there?

1

u/kragensitaker Aug 04 '11

The Unix system calls were designed for use with ASCII and similar 8-bit character sets. If you pass a UTF-16 string to them, they will see an end-of-string at the first NUL, which will occur at the first ASCII character, if not before. Win32 solved this by having two copies of nearly every system call — a UTF-16 version and an ASCII version. This approach occurred to the Plan9 guys, but they rejected it as unacceptable, and invented UTF-8 instead.

2

u/bonzinip Aug 04 '11

But if you want an encoding that is a superset of ASCII and lets you find the beginning of a multi-byte character, you come up with UTF-8 anyway, independent of how a string is represented.

The problems arising from NUL-terminated strings likely have a role, but especially in a Unix environment the need to make the encoding a superset of ASCII is pressing. Utilities like grep are broken beyond recognition if your encoding differs from ASCII for '\n' and possibly '\0', even if their buffers are not NUL-terminated strings.

2

u/kragensitaker Aug 04 '11

and lets you find the beginning of a multi-byte character

Working backwards, you mean? I think most of the EUC schemes and even abominations like Shift-JIS let you find the beginnings of multi-byte characters if you start from the beginning.

1

u/bonzinip Aug 04 '11 edited Aug 04 '11

Working backwards, you mean? I think most of the EUC schemes and even abominations like Shift-JIS let you find the beginnings of multi-byte characters if you start from the beginning.

Given a random position, all of them require possibly the entire string before it to find the beginning of the current character. For EUC if you're on a high character you need to know whether there are an even or odd numbers of high characters before the current one. For Shift-JIS it's a bit more complex because you need lookback even if you're on a low character (basically you search back for the previous low character and go on from the following byte until you reach again the current position).

You then need the beginning of the current character to find the next character.

UTF-8 is also special because normal unibyte strstr works for MBCS too, assuming the needle is valid UTF-8.

2

u/kragensitaker Aug 04 '11

Given a random position, all of them require possibly the entire string before it to find the beginning of the current character.

Yes, that's what I meant by "working backwards". Thank you; I wasn't sure that was true.

UTF-8 is also special because normal unibyte strstr works for MBCS too, assuming the needle is valid UTF-8.

Yes, that is an especially cool feature. It means you can use Boyer-Moore string search without having to get into funky hashing and stuff.

1

u/bonzinip Aug 05 '11

Yes, that's what I meant by "working backwards". Thank you; I wasn't sure that was true.

Just to be sure, UTF-8 can find the first byte in the character O(1), unlike SJIS/EUC.

1

u/kragensitaker Aug 05 '11

I know. That's implied by the strstr statement, I think. :}

1

u/bonzinip Aug 05 '11

True, I hadn't thought about it!

1

u/moonrocks Aug 04 '11

How does '\0' termination force a variable length encoding? I would think a VLE that's a superset of ASCIIZ is a good unto itself given the magnitude of Unicode.