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

31–40 of 58 posts

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

#31

Post by jandrese »

tbirdz wrote: post #5
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…

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.

You don't even need that length prefix if you use something like SDNV. Ironically this would have introduced a case where you have something like a null terminator that can overflow.

It would have also been a fair bit of overhead on those old single-Mhz machines. Still, almost everything you do with strings is slow so it probably would have been manageable. As an added bonus, it is zero space overhead for short strings (up to 127 characters) which are the majority of strings.

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

#32

Post by zerokernel »

tptacek wrote: post #28
korethr wrote: post #24

Earlier quoted context omitted.

> ...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…

And various undefined behaviours (signed overflow etc.) colluding against the programmer to the effect that compilers sometimes delete range-checking code.

Integer promotion rules are not simple, either. Integer width rules, far from simple.

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

#33

Post by jandrese »

PopsiclePete wrote: post #21
IshKebab wrote: post #11

Earlier quoted context omitted.

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?

Best solution would be something like SDNV. Short strings (up to 127 characters) have no length penalty and you can handle strings of any length.

I don't think these were invented back when K&R were designing C, but it feels like something any smart computer language designer could invent if the need arose.

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

#34

Post by zerokernel »

function_seven wrote: post #16
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.

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…

> NUL is not a character

Somehow NUL is still an assigned character in the ASCII code table. Strange, hmmm?

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

#35

Post by pishpash »

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…

NUL is a character in the ASCII character set. That is a problem because you cannot create all the strings composed of ASCII characters in C.

But C never claimed to support all ASCII strings. C doesn't even have strings. C just has char arrays, which are byte arrays. When strings were formalized by convention in the stdlibs, clearly the supported strings are 1-255 strings, NUL excluded. That's the character set available for strings in the stdlibs. If you insist on using stdlib strings for some other kind of strings, that's your own problem.

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

#36

Post by SAI_Peregrinus »

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…

Most CPUs have a flags register, and typically have a "zero" flag which is set when the result of the last operation was zero. Zero is special in the vast majority of hardware designs. Checking for null (zero) instead of another specific value often saves a few cycles. That's where the optimization of having all FOR loops count down towards zero comes from, the check saves a cycle or two each iteration on some CPUs. The same thing happens when reading from a buffer, the load instruction will set the Zero flag when the terminating null is read.

The difference doesn't matter much on modern (non-embedded) processors, but it did make sense at the time C was designed. It matches the most common hardware design pattern better than the alternatives.

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

#37

Post by JoachimSchipper »

jandrese wrote: post #26
saint_fiasco wrote: post #13

Earlier quoted context omitted.

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 loose…

Elaborating on the NUL bytes on the command-line, e.g. find -print0 | xargs -0:

Using find -print0 etc. is a good idea not so much because NUL is an uncommon character (the various record separators / vertical tab / ... are no more common), but because UNIX - being a C system through and through - allows any character to appear in a file name except '/' (path separator) and NUL. Thus, NUL makes a perfect separator between filenames.

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

#38

Post by Jtsummers »

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…

A bug in an early XCom game led to character's becoming so fast that they couldn't leave the landing zone.

Stats were stored in an 8-bit field and were incremented at some (variable, depended on other factors) rate as the character leveled up. Once they hit 255 in a stat, the next time they leveled up their stat would be back to single digits.

This sort of behavior is silent in C so you have to have bounds checking yourself to make sure you don't cause underflow/overflow.

Also, be careful with enumerations. Any integer can be stored into the enumerated type and, at best, the compiler will warn you (an error if you use the right compiler flags) that you haven't cast it to the enumerated type. But nothing guarantees that it's actually in the range of the enumeration.

Post reply on HN