Null-terminated string
In computer programming, a null-terminated string is a character string stored as an array
containing the characters and terminated with a null character (a character with an internal value of
zero, called "NUL" in this article, not same as the glyph zero). Alternative names are C string, which
refers to the C programming language and ASCIIZ[1] (although C can use encodings other than
ASCII).
The length of a string is found by searching for the (first) NUL. This can be slow as it takes O(n)
(linear time) with respect to the string length. It also means that a string cannot contain a NUL (there
is a NUL in memory, but it is after the last character, not in the string).
History
Null-terminated strings were produced by the .ASCIZ directive of the PDP-11 assembly languages
and the ASCIZ directive of the MACRO-10 macro assembly language for the PDP-10. These predate
the development of the C programming language, but other forms of strings were often used.
At the time C (and the languages that it was derived from) was developed, memory was extremely
limited, so using only one byte of overhead to store the length of a string was attractive. The only
popular alternative at that time, usually called a "Pascal string" (a more modern term is "length-
prefixed"), used a leading byte to store the length of the string. This allows the string to contain NUL
and made finding the length need only one memory access (O(1) (constant) time), but limited string
length to 255 characters. C designer Dennis Ritchie chose to follow the convention of null-termination
to avoid the limitation on the length of a string and because maintaining the count seemed, in his
experience, less convenient than using a terminator.[2][3]
This had some influence on CPU instruction set design. Some CPUs in the 1970s and 1980s, such as
the Zilog Z80 and the DEC VAX, had dedicated instructions for handling length-prefixed strings.
However, as the null-terminated string gained traction, CPU designers began to take it into account,
as seen for example in IBM's decision to add the "Logical String Assist" instructions to the ES/9000
520 in 1992 and the vector string instructions to the IBM z13 in 2015.[4]
FreeBSD developer Poul-Henning Kamp, writing in ACM Queue, referred to the victory of null-
terminated strings over a 2-byte (not one-byte) length as "the most expensive one-byte mistake"
ever.[5]
Limitations
While simple to implement, this representation has been prone to errors and performance problems.
Null-termination has historically created security problems.[6] A NUL inserted into the middle of a
string will truncate it unexpectedly.[7] A common bug was to not allocate the additional space for the
NUL, so it was written over adjacent memory. Another was to not write the NUL at all, which was
often not detected during testing because the block of memory already contained zeros. Due to the
expense of finding the length, many programs did not bother before copying a string to a fixed-size
buffer, causing a buffer overflow if it was too long.
The inability to store a zero requires that text and binary data be kept distinct and handled by
different functions (with the latter requiring the length of the data to also be supplied). This can lead
to code redundancy and errors when the wrong function is used.
The speed problems with finding the length can usually be mitigated by combining it with another
operation that is O(n) anyway, such as in strlcpy. However, this does not always result in an
intuitive API.
Character encodings
Null-terminated strings require that the encoding does not use a zero byte (0x00) anywhere; therefore
it is not possible to store every possible ASCII or UTF-8 string.[8][9][10] However, it is common to
store the subset of ASCII or UTF-8 – every character except NUL – in null-terminated strings. Some
systems use "modified UTF-8" which encodes NUL as two non-zero bytes (0xC0, 0x80) and thus
allow all possible strings to be stored. This is not allowed by the UTF-8 standard, because it is an
overlong encoding, and it is seen as a security risk. Some other byte may be used as end of string
instead, like 0xFE or 0xFF, which are not used in UTF-8.
UTF-16 uses 2-byte integers and as either byte may be zero (and in fact every other byte is, when
representing ASCII text), cannot be stored in a null-terminated byte string. However, some languages
implement a string of 16-bit UTF-16 characters, terminated by a 16-bit NUL (0x0000).
Improvements
Many attempts to make C string handling less error prone have been made. One strategy is to add
safer functions such as strdup and strlcpy, whilst deprecating the use of unsafe functions such as
gets. Another is to add an object-oriented wrapper around C strings so that only safe calls can be
done. However, it is possible to call the unsafe functions anyway.
Most modern libraries replace C strings with a structure containing a 32-bit or larger length value (far
more than were ever considered for length-prefixed strings), and often add another pointer, a
reference count, and even a NUL to speed up conversion back to a C string. Memory is far larger now,
such that if the addition of 3 (or 16, or more) bytes to each string is a real problem the software will
have to be dealing with so many small strings that some other storage method will save even more
memory (for instance there may be so many duplicates that a hash table will use less memory).
Examples include the C++ Standard Template Library std::string, the Qt QString, the MFC
CString, and the C-based implementation CFString from Core Foundation as well as its Objective-
C sibling NSString from Foundation, both by Apple. More complex structures may also be used to
store strings such as the rope.
See also
Empty string
Sentinel value
References
1. "Chapter 15 - MIPS Assembly Language" (https://people.scs.carleton.ca/~sivarama/org_book/org_
book_web/solution_manual/org_soln_one/arch_book_solution_ch15.pdf) (PDF). Carleton
University. Retrieved 9 October 2023.
2. Ritchie, Dennis M. (April 1993). The development of the C language (https://www.bell-labs.com/us
r/dmr/www/chist.html). Second History of Programming Languages conference. Cambridge, MA.
3. Ritchie, Dennis M. (1996). "The development of the C language". In Bergin, Jr., Thomas J.;
Gibson, Jr., Richard G. (eds.). History of Programming Languages (2 ed.). New York: ACM Press.
ISBN 0-201-89502-1 – via Addison-Wesley (Reading, Mass).
4. IBM z/Architecture Principles of Operation (http://publibfp.dhe.ibm.com/epubs/pdf/a227832c.pdf)
5. Kamp, Poul-Henning (25 July 2011), "The Most Expensive One-byte Mistake" (http://queue.acm.or
g/detail.cfm?id=2010365), ACM Queue, 9 (7): 40–43, doi:10.1145/2001562.2010365 (https://doi.or
g/10.1145%2F2001562.2010365), ISSN 1542-7730 (https://search.worldcat.org/issn/1542-7730),
S2CID 30282393 (https://api.semanticscholar.org/CorpusID:30282393)
6. Rain Forest Puppy (9 September 1999). "Perl CGI problems" (http://insecure.org/news/P55-07.tx
t). Phrack Magazine. 9 (55). artofhacking.com: 7. Retrieved 3 January 2016.
7. "Null byte injection on PHP?" (https://security.stackexchange.com/questions/48187/null-byte-injecti
on-on-php).
8. "UTF-8, a transformation format of ISO 10646" (http://tools.ietf.org/html/rfc3629#section-3).
Retrieved 19 September 2013.
9. "Unicode/UTF-8-character table" (http://www.utf8-chartable.de/). Retrieved 13 September 2013.
10. Kuhn, Markus. "UTF-8 and Unicode FAQ" (http://www.cl.cam.ac.uk/~mgk25/unicode.html#utf-8).
Retrieved 13 September 2013.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Null-terminated_string&oldid=1184745718"
