词条 | 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 ( The length of a C string is found by searching for the (first) NUL byte. 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 character (there is a NUL in memory, but it is after the last character, not "in" the string). HistoryNull-terminated strings were produced by the 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 (on a machine using 8-bit bytes). C designer Dennis Ritchie chose to follow the convention of NUL-termination, already established in BCPL, 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.[1] 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 NUL-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. FreeBSD developer Poul-Henning Kamp, writing in ACM Queue, would later refer to the victory of null-terminated strings over a 2-byte (not one-byte) length as "the most expensive one-byte mistake" ever.[2]Implementations{{expand section|date=November 2011}}{{Main|C string handling#Functions}}C programming language supports null-terminated strings as the primary string type.[3] There are many functions for string handling in the C standard library. Operations supported include:
LimitationsWhile simple to implement, this representation has been prone to errors and performance problems. The NUL termination has historically created security problems.[4] A NUL byte inserted into the middle of a string will truncate it unexpectedly. 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 a NUL was already there by chance from previous use of the same block of memory. 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 NUL requires that string data 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 Character encodingsNull-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.[5][6][7] However, it is common to store the subset of ASCII or UTF-8 – every character except the NUL character – in null-terminated strings. Some systems use "modified UTF-8" which encodes the NUL character 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 as it is a security risk. A 0xC0, 0x80 NUL might be seen as a string terminator in security validation and as a character when used. 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 character. (Again the NUL character, which encodes as a single zero code unit, is the only character that cannot be stored. UTF-16 does not have any alternative encoding of zero). ImprovementsMany attempts to make C string handling less error prone have been made. One strategy is to add safer functions such as 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 See also
References1. ^Dennis M. Ritchie (1993). [The development of the C language]. Proc. 2nd History of Programming Languages Conf. {{CProLang}}{{Data types}}{{Use dmy dates|date=January 2011}}C string2. ^{{citation |last=Kamp |first=Poul-Henning |date=25 July 2011 |title=The Most Expensive One-byte Mistake |journal=ACM Queue |volume=9 |number=7 |issn=1542-7730 |accessdate=2 August 2011 |url=http://queue.acm.org/detail.cfm?id=2010365 }} 3. ^{{cite web |title=The Development of the C Language |url=http://cm.bell-labs.com/cm/cs/who/dmr/chist.html |accessdate=9 November 2011 |first=Dennis |last=Richie |year=2003 }} 4. ^{{cite journal|url= http://insecure.org/news/P55-07.txt |author=Rain Forest Puppy |title=Perl CGI problems |work=Phrack Magazine |publisher=artofhacking.com |date=9 September 1999 |volume=9 |issue=55 |page=7 |accessdate=3 January 2016}} 5. ^{{cite web|title=UTF-8, a transformation format of ISO 10646|url=http://tools.ietf.org/html/rfc3629#section-3|accessdate=19 September 2013}} 6. ^{{cite web|title=Unicode/UTF-8-character table|url=http://www.utf8-chartable.de/|accessdate=13 September 2013}} 7. ^{{cite web|last=Kuhn|first=Markus|title=UTF-8 and Unicode FAQ|url=http://www.cl.cam.ac.uk/~mgk25/unicode.html#utf-8|accessdate=13 September 2013}} 1 : String data structures |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。