8 ms·

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

55 points by mayankkaizen 9y ago

PopsiclePete 9y ago
>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, the upper bound for a string is effectively the amount of memory the OS is willing to give you, and code can keep working without modification for decades. Am I missing something here?
- mnarayan01 9y ago
  Two bytes extra for the length, but one byte saved from the marker character.
- tbirdz 9y ago
  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.
  - jerf 9y ago
    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.
    - PopsiclePete 9y ago
      So then....they chose correctly?
      - jerf 9y ago
        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.
    - pjmlp 9y ago
      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.
  - jandrese 9y ago
    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.
- deleted 9y ago
  [deleted]
- IshKebab 9y ago
  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).
  - rzzzt 9y ago
    Length itself could also be stored with variable length encoding.
  - PopsiclePete 9y ago
    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?
    - jandrese 9y ago
      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.
    - IshKebab 9y ago
      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).
- kbenson 9y ago
  There are various schemes to address this. A simple one is to make the legtth prefix variable, nad use the high order bit use the highorder bit of each byte to indicate there is another length byte following the current one. This gives you 128 possible values for each length byte. The max string size for a single byte prefix would be 127 (2^(8-1), the max size for two bytes would be 16384 (2^16-2), etc. It's not necessarily a good solution, there are likely ones that are much more performant, but many solutions exist, and a few have even been implemented in widely used languages.
chrisaycock 9y ago
Many prior comments over the years: https://news.ycombinator.com/item?id=2837571 https://news.ycombinator.com/item?id=2837571 https://news.ycombinator.com/item?id=7572711 https://news.ycombinator.com/item?id=7572711 https://news.ycombinator.com/item?id=3892410 https://news.ycombinator.com/item?id=3892410 https://news.ycombinator.com/item?id=8385306 https://news.ycombinator.com/item?id=8385306
JustSomeNobody 9y ago
Did they choose "wrong"? No. Did they make a choice and move on? Yes.
- pjmlp 9y ago
  Yes, because there were already safer systems programming languages being used by the time C got invented. OS safety was already a concern in 1961.
aknoob 9y ago
A null-terminated representation is as close to a fundamental datatype for a string as possible. It is same in spirit as other fundamental data types in C like array. People have built abstractions over these fundamental datatypes over the years.
- IshKebab 9y ago
  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.
  - saint_fiasco 9y ago
    Why would you want to represent a null byte in a string? Is there a character encoding where the null value has a meaning?
    - jandrese 9y ago
      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.
      - JoachimSchipper 9y ago
tptacek 9y ago
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.
- korethr 9y ago
  > ...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?
  - tptacek 9y ago
    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]).
    - zerokernel 9y ago
      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.
  - dllthomas 9y ago
    Overflow of a signed integer - even in intermediate values - is technically undefined behavior, with the concomitant nasal demons, etc.
csours 9y ago
Maybe - but the people who followed definitely chose poorly by continuing to use null terminated strings.
bobsc123 9y ago
Null terminated strings are just application level logic. "strings" are just bytes in memory. There are no strings.
- roywiggins 9y ago
  > Should the C language represent strings as an address + length tuple or just as the address with a magic character (NUL) marking the end? This explicitly is a different kind of representation in memory.
- callesgg 9y ago
  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
  - _kst_ 9y ago
    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.)
moonbug22 9y ago
Hell yes.
dblotsky 9y ago
The title should have "Dennis" instead of "Ritchie".
Sir_Cmpwn 9y ago
>The CPUs that offered string manipulation instructions—for example, Z-80 and DEC VAX—did so in terms of the far more widespread adr+len model. Hold up, the z80 offered string maniuplation instructions? Using adr+len, no less? You miiiight call LDIR a string manipulation function using adr+len but in practice almost all z80 machines I've seen use NUL terminated strings and something like CPIR to find it.
aplorbust 9y ago
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 every purpose. Whenever I write programs in C from scratch, I use byte.h, buffer.h, etc., from the above mentioned author. I do not use memcpy. In doing this, I am not a professional programmer and I am not writing internet-facing programs for other users. I am a student of C learning how to use C, the language. If I know how the language works, then it stands to reason I should be able to use a variety of libraries, including alternatives to the "standard libraries". Otherwise it is arguable I would be just learning how to use a standard library, not a language. The C language has utility on its own, as form of a notation, and it is that utility which I seek to learn about. Historical records indicate there was C language in productive use for some time before there was a "standard library".
- korethr 9y ago
  Who is this author, and where is his code? I'd like to study it -- I might learn something.
  - eesmith 9y ago
    Almost certainly D. J. Bernstein's string API from daemontools , http://cr.yp.to/daemontools.html http://cr.yp.to/daemontools.html and his other bits of code. Some commentary at http://www.and.org/vstr/comparison http://www.and.org/vstr/comparison . Probably more commentary elsewhere.

55 points by mayankkaizen 9y ago

>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, the upper bound for a string is effectively the amount of memory the OS is willing to give you, and code can keep working without modification for decades. Am I missing something here?

mnarayan01 9y ago
Two bytes extra for the length, but one byte saved from the marker character.
tbirdz 9y ago
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.
- jerf 9y ago
  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.
  - PopsiclePete 9y ago
    So then....they chose correctly?
    - jerf 9y ago
      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.
  - pjmlp 9y ago
    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.
- jandrese 9y ago
  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.
deleted 9y ago
[deleted]
IshKebab 9y ago
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).
- rzzzt 9y ago
  Length itself could also be stored with variable length encoding.
- PopsiclePete 9y ago
  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?
  - jandrese 9y ago
    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.
  - IshKebab 9y ago
    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).
kbenson 9y ago
There are various schemes to address this. A simple one is to make the legtth prefix variable, nad use the high order bit use the highorder bit of each byte to indicate there is another length byte following the current one. This gives you 128 possible values for each length byte. The max string size for a single byte prefix would be 127 (2^(8-1), the max size for two bytes would be 16384 (2^16-2), etc. It's not necessarily a good solution, there are likely ones that are much more performant, but many solutions exist, and a few have even been implemented in widely used languages.

chrisaycock 9y ago

Many prior comments over the years: https://news.ycombinator.com/item?id=2837571 https://news.ycombinator.com/item?id=2837571 https://news.ycombinator.com/item?id=7572711 https://news.ycombinator.com/item?id=7572711 https://news.ycombinator.com/item?id=3892410 https://news.ycombinator.com/item?id=3892410 https://news.ycombinator.com/item?id=8385306 https://news.ycombinator.com/item?id=8385306

JustSomeNobody 9y ago

Did they choose "wrong"? No. Did they make a choice and move on? Yes.

pjmlp 9y ago
Yes, because there were already safer systems programming languages being used by the time C got invented. OS safety was already a concern in 1961.

aknoob 9y ago

A null-terminated representation is as close to a fundamental datatype for a string as possible. It is same in spirit as other fundamental data types in C like array. People have built abstractions over these fundamental datatypes over the years.

IshKebab 9y ago
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.
- saint_fiasco 9y ago
  Why would you want to represent a null byte in a string? Is there a character encoding where the null value has a meaning?
  - jandrese 9y ago
    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.
    - JoachimSchipper 9y ago

tptacek 9y ago

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.

korethr 9y ago
> ...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?
- tptacek 9y ago
  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]).
  - zerokernel 9y ago
    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.
- dllthomas 9y ago
  Overflow of a signed integer - even in intermediate values - is technically undefined behavior, with the concomitant nasal demons, etc.

csours 9y ago

Maybe - but the people who followed definitely chose poorly by continuing to use null terminated strings.

bobsc123 9y ago

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

roywiggins 9y ago
> Should the C language represent strings as an address + length tuple or just as the address with a magic character (NUL) marking the end? This explicitly is a different kind of representation in memory.
callesgg 9y ago
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
- _kst_ 9y ago
  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.)

moonbug22 9y ago

Hell yes.

dblotsky 9y ago

The title should have "Dennis" instead of "Ritchie".

Sir_Cmpwn 9y ago

>The CPUs that offered string manipulation instructions—for example, Z-80 and DEC VAX—did so in terms of the far more widespread adr+len model. Hold up, the z80 offered string maniuplation instructions? Using adr+len, no less? You miiiight call LDIR a string manipulation function using adr+len but in practice almost all z80 machines I've seen use NUL terminated strings and something like CPIR to find it.

aplorbust 9y ago

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 every purpose. Whenever I write programs in C from scratch, I use byte.h, buffer.h, etc., from the above mentioned author. I do not use memcpy. In doing this, I am not a professional programmer and I am not writing internet-facing programs for other users. I am a student of C learning how to use C, the language. If I know how the language works, then it stands to reason I should be able to use a variety of libraries, including alternatives to the "standard libraries". Otherwise it is arguable I would be just learning how to use a standard library, not a language. The C language has utility on its own, as form of a notation, and it is that utility which I seek to learn about. Historical records indicate there was C language in productive use for some time before there was a "standard library".

korethr 9y ago
Who is this author, and where is his code? I'd like to study it -- I might learn something.
- eesmith 9y ago
  Almost certainly D. J. Bernstein's string API from daemontools , http://cr.yp.to/daemontools.html http://cr.yp.to/daemontools.html and his other bits of code. Some commentary at http://www.and.org/vstr/comparison http://www.and.org/vstr/comparison . Probably more commentary elsewhere.