Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

queue.acm.org

Post reply on HN
Print view View original

21–30 of 58 posts

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#21

Post by PopsiclePete »

IshKebab wrote: post #11
PopsiclePete wrote: post #2

>Using an address + length format would cost one more byte of overhead than an address + magic_marker format, and their PDP computer had limited core memory. I find this interesting - why only one more byte of overhead? That would've limited string lengths to 256. So 2 bytes would seem the minimum, and even then, how do you go to 4 bytes once memory becomes cheap without breaking everything? Using NUL-termination, th…

I presume the machine at the time was 16-bit, and thus you could never have a string longer than 65536 bytes in memory. On a modern machine you'd need at least 4 bytes. `std::string` uses `size_t` (64-bits on 64-bit machines).

That's what I mean though - if you standardize, as part of the language, that you can have 2 bytes for the string length because at the time no machine could handle anything larger, how do you move forward once 4 or 8 bytes is not a big deal without breaking everything?

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#22

Post by function_seven »

jerf wrote: post #18
function_seven wrote: post #16

Earlier quoted context omitted.

A string contains characters. NUL is not a character; it's nothing. "Fundamental" in this case means "matches reality". Having a number at the beginning doesn't match reality as closely as having the string of characters in sequential memory addresses with something to terminate them. The quick fox made the jump\N or 27The quick fox made the jump The second one requires more work to store (a character-counting routin…

"A string contains characters. NUL is not a character; it's nothing." You already couldn't make this argument stick in the ASCII era, where a string can't contain NUL but can contain SOH (Start of Heading), STX (Start of Text), ETX (End of Text), EOT (End of Transmission), ENQ (Enquiry), ACK (Acknowledge), BEL, BS, HT (horizontal tab), LF, VT (vertical tab), FF (form feed), CR, SO (shift out), SI (shift in), DLE (dat…

Good point. And I would agree that the error lies in choosing to use strings for inappropriate places.

Also, ETX might have been a good terminator :) I assume NUL was chosen for easier checking (if (char) ...) vs (if (char == 0x03) ...)

But my argument was against length prefixing somehow being "more fundamental" than having just a sequence of characters "raw" in memory addresses.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#23

Post by PopsiclePete »

jerf wrote: post #19
tbirdz wrote: post #5

Earlier quoted context omitted.

1 additional byte of overhead would give you 2 bytes for the length, since you wouldn't have to have the NUL byte at the end of the string. You could do some kind of variable int encoding scheme, where longer strings would require more bytes for length, with some overhead to indicate how many length bytes are required for each string.

In the PDP era, they would have noticed the overhead of having a variable-length int at the beginning they would have to decode. In the modern era, it's probably cheap to the point of being free, because in the vast majority of cases I would expect branch prediction to largely eliminate the checks as being very predictable.

So then....they chose correctly?

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#24

Post by korethr »

tptacek wrote: post #9

Worth keeping in mind that the security cost here is illusory: the track record of length-delimited data structures isn't much better than that of ASCIIZ, especially since integer handling in C is so treacherous.

> ...especially since integer handling in C is so treacherous.

I'm still learning C, having not had much reason to do so until recently, so I'm not quite sure I understand this statement. How is integer handling in C treacherous (any more so than any other language, especially other languages that operate as close to the metal as C)? Is it something to do with signed vs unsigned, and beware of over/under-flow when doing math? Or is it a more insidious subtlety I'm ignorant of because it has been biding its time for a more perfect opportunity to bite me in the ass?

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#25

Post by function_seven »

andrewstuart2 wrote: post #20
function_seven wrote: post #16

Earlier quoted context omitted.

A string contains characters. NUL is not a character; it's nothing. "Fundamental" in this case means "matches reality". Having a number at the beginning doesn't match reality as closely as having the string of characters in sequential memory addresses with something to terminate them. The quick fox made the jump\N or 27The quick fox made the jump The second one requires more work to store (a character-counting routin…

None of it really "matches reality." It's all binary numbers, and on a deeper level, voltages or magnetized particles. 0 is not a letter of the alphabet, but nor is 01000001 (ascii 'a'). So either the first number is special, or you look for a special number to indicate the end. Neither represents reality, because the "end" of a single group of characters is visually identical to a million white-space characters that…

I was going more toward "closer to reality". But I take your point. Somewhere we're going to need extra info about the string itself, whether that extra info is a magic terminator or a magic prefix. The magic prefix gives great benefit, but also is more complex to implement if you want to store an arbitrary-length string.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#26

Post by jandrese »

saint_fiasco wrote: post #13
IshKebab wrote: post #10

Earlier quoted context omitted.

It's not fundamental at all. You can't even represent null bytes in a null-terminated string. A length prefix is pretty clearly superior.

Why would you want to represent a null byte in a string? Is there a character encoding where the null value has a meaning?

Interesting some Unix command line utilities will send null separated records if you pass a flag (often -0) because it's the least likely character to show up as part of the string.

find and xargs are examples of programs with this feature.

It depends a bit on what you call a "string". If you're thinking "something a human will want to read", then yeah, there's no much need to encode null. If however you take a looser view of "an 8 bit vector" then encoding null becomes important. Otherwise your system can't be 8 bit clean.

Overall I think the null terminator has caused more problems than it has solved, but prefixing the string length isn't a panacea either. You end up with systems with 256, 65536, or even 4294967296 byte limits on their strings. It's also more difficult to pass around an index into the string so you end up having to make lots of copies and then possibly merge them later or your language is cluttered with index values everywhere strings are used.

It's quite possible that if K&R had gone with length prefix strings that we would have a different class of errors where the string index gets offset or malicious values are inserted in the length field.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#28

Post by tptacek »

korethr wrote: post #24
tptacek wrote: post #9

Worth keeping in mind that the security cost here is illusory: the track record of length-delimited data structures isn't much better than that of ASCIIZ, especially since integer handling in C is so treacherous.

> ...especially since integer handling in C is so treacherous. I'm still learning C, having not had much reason to do so until recently, so I'm not quite sure I understand this statement. How is integer handling in C treacherous (any more so than any other language, especially other languages that operate as close to the metal as C)? Is it something to do with signed vs unsigned, and beware of over/under-flow when do…

Two bottles of beer on the wall, two bottles of beer.

Take one down, pass it around, one bottle of beer on the wall.

One bottle of beer on the wall, one bottle of beer.

Take it down, pass it around, zero bottles of beer on the wall.

Zero bottles of beer on the wall, zero bottles of beer.

Take one down, pass it around, four billion, two hundred ninety-four million, nine hundred sixty-seven thousand, two hundred ninety-five bottles of beer on the wall.

(Yes, you pretty much have it in your question; the Google search you want to make to learn more is [integer overflow]).

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#29

Post by dllthomas »

korethr wrote: post #24
tptacek wrote: post #9

Worth keeping in mind that the security cost here is illusory: the track record of length-delimited data structures isn't much better than that of ASCIIZ, especially since integer handling in C is so treacherous.

> ...especially since integer handling in C is so treacherous. I'm still learning C, having not had much reason to do so until recently, so I'm not quite sure I understand this statement. How is integer handling in C treacherous (any more so than any other language, especially other languages that operate as close to the metal as C)? Is it something to do with signed vs unsigned, and beware of over/under-flow when do…

Overflow of a signed integer - even in intermediate values - is technically undefined behavior, with the concomitant nasal demons, etc.

Re: Did Ken, Ritchie and Brian choose wrong with NUL-terminated text strings? (2011)

#30

Post by zerokernel »

tptacek wrote: post #9

Worth keeping in mind that the security cost here is illusory: the track record of length-delimited data structures isn't much better than that of ASCIIZ, especially since integer handling in C is so treacherous.

I would claim that there is still a difference between P-strings and, say, ASN.1 DER (which, at heart, is still TLV).
Post reply on HN