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

51–58 of 58 posts

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

#51

Post by _kst_ »

callesgg wrote: post #43
bobsc123 wrote: post #17

Null terminated strings are just application level logic. "strings" are just bytes in memory. There are no strings.

No, If you quote a string in c "string data here" you get a piece of data with null termination. Null termination is part of the C language. Example: char str[]= "1234"; printf ("%s: %lu", str, sizeof(str)); Prints: 1234: 5

Use "%zu" to print a value of type size_t.

A couple of ugly corner cases:

    const char str[] = "abcd\0efgh";
    printf("length = %zu, size = %zu, value = \"%s\"\n",
           strlen(str), sizeof str, str);
output:

    length = 4, size = 10, value = "abcd"
And:

    const char str[4] = "abcd";
    printf("length = %zu, size = %zu, value = \"%s\"\n",
           strlen(str), sizeof str, str);
This has undefined behavior. (Which is a good reason to let the compiler figure out how big the array has to be. Computers are better at counting things than you are. Let them.)

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

#52

Post by korethr »

aplorbust wrote: post #49

There is one author who does not use memcpy, strcpy, etc. He wrote his own "standard" C library routines. Others have used these routines; they are public domain. The security track record on the authors internet-facing programs is better than most. In fact, I cannot think of any author writing similar software with a better track record. Sometimes the most popular solutions are not necessarily the best ones for ever…

Who is this author, and where is his code? I'd like to study it -- I might learn something.

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

#53

Post by jerf »

PopsiclePete wrote: post #23
jerf wrote: post #19

Earlier quoted context omitted.

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?

Despite being vigorously opposed to NUL-termination in the modern era, yes, I would not criticize the people who actually made the decision for the PDP. They had no real reason to believe we'd still be discussing that decision 60 years later.

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

#54

Post by jerf »

pishpash wrote: post #35
jerf wrote: post #18

Earlier quoted context omitted.

"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 avail…

"But C never claimed to support all ASCII strings."

That is precisely my point... there is no well-supported solution in core C for arbitrary binary strings, despite C's extremely frequent use in domains that require them. If you insist on using stdlib strings for other kinds of strings, you do have a problem... but you also have no other choice. Which brings it back to being a language/library problem.

As I already alluded to, C itself doesn't have a problem with length-delimited strings, and there are plenty of libraries you can get for them. But the core library for C does force this problem in your face by leaving you no other choice, and it is a valid criticism of C.

(C is such a disaster that the only thing to do is to leave it behind as quickly as possible. However, if we were somehow stuck with the language itself, there's a lot of ways we could improve the libraries it comes with, as again demonstrated by the many such improved libraries you can get. However, one of the things I've learned from learning a ton of languages over the past couple of decades is that a language almost never manages to escape from its own standard library, and the few that manage it (like D) pay a stiff adoption price in the process. C's standard library has a real problem here, that has caused real bugs, and no amount of wordplay is going to fix those decades of bugs.)

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

#55

Post by eesmith »

korethr wrote: post #52
aplorbust wrote: post #49

There is one author who does not use memcpy, strcpy, etc. He wrote his own "standard" C library routines. Others have used these routines; they are public domain. The security track record on the authors internet-facing programs is better than most. In fact, I cannot think of any author writing similar software with a better track record. Sometimes the most popular solutions are not necessarily the best ones for ever…

Who is this author, and where is his code? I'd like to study it -- I might learn something.

Almost certainly D. J. Bernstein's string API from daemontools , http://cr.yp.to/daemontools.html and his other bits of code. Some commentary at http://www.and.org/vstr/comparison . Probably more commentary elsewhere.

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

#56

Post by function_seven »

zerokernel wrote: post #34
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…

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

Ha, the fact that I spelled it "NUL" instead of using the word "null" should have made me pause. :)

Ok, it's an ASCII character code point. One that's used to terminate strings. I meant it's not a character you'd find in the middle of a string, though I realize that's kinda tautological. Back when ASCII was developed, punch cards were used. Any row in the card that wasn't punched was a NUL. It wouldn't have made sense to have it in the middle of a string. It would be like missing a character altogether.

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

#57

Post by pjmlp »

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.

Even in the PDP era I am not so sure, given the architectures and OSes being developed outside AT&T, some of them in production.

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

#58

Post by IshKebab »

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?

N-bit machines can use N-bit lengths for strings in memory. If you're storing strings your storage format has to specify a way to decide the prefix length (or you can use some other system).

For example `std::string` uses `std::size_t` as a length which is 32-bit on 32-bit machines and 64-bit on 64-bit machines. When you serialise a string to protobuf (for example) it uses a variable-length prefix. Other formats could have fixed 4-byte prefixes or whatever they want (even null-terminated).

Post reply on HN