Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Структура данных
Data structure
В компьютерном программировании, строка с нулевым завершением — это последовательность символов, хранящаяся в виде массива, содержащего символы и завершающаяся нулевым символом (символ с внутренним значением нуля, называемый "NUL" в этой статье, не путать с графическим символом нуля). Другие названия — C-строка, отсылающая к языку программирования C, и ASCIIZ (хотя C может использовать кодировки, отличные от ASCII). Длина строки определяется путем поиска (первого) NUL. Это может быть медленным, так как требует O(n) (линейного времени) относительно длины строки. Также это означает, что строка не может содержать NUL (в памяти NUL присутствует, но он располагается после последнего символа, а не внутри строки).
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 (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).
История
Нулевые строки создавались директивой ASCIZ языков ассемблера PDP 11 и директивой ASCIZ макроассемблера MACRO 10 для PDP 10. Они предшествовали разработке языка программирования C, но часто использовались и другие форматы строк. Когда C (и языки, от которых он произошел) разрабатывался, память была крайне ограничена, поэтому использование всего одного байта дополнительных затрат для хранения длины строки было привлекательным решением. Единственной популярной альтернативой в то время, обычно называемой «паскалевской строкой» (более современный термин – «строка с префиксом длины»), был ведущий байт, используемый для хранения длины строки. Это позволяло строке содержать символ NUL и требовало всего одного обращения к памяти для определения длины (O(1) – постоянное время), но ограничивало длину строки до 255 символов. Разработчик C, Деннис Ричи, выбрал соглашение о нулевом завершении, чтобы избежать ограничения длины строки и потому, что, по его опыту, ведение подсчета казалось менее удобным, чем использование терминатора. Это оказало определенное влияние на проектирование наборов инструкций процессоров. Некоторые процессоры 1970-х и 1980-х годов, такие как Zilog Z80 и DEC VAX, имели специализированные инструкции для работы со строками с префиксом длины. Однако, по мере распространения нулевых строк, разработчики процессоров стали учитывать и их, что проявилось, например, в решении IBM добавить инструкции "Logical String Assist" в ES/9000 520 в 1992 году и векторные строковые инструкции в IBM z13 в 2015 году. Разработчик FreeBSD, Пол Хеннинг Камп, в статье для ACM Queue назвал победу нулевых строк над двухбайтовым (а не однобайтовым) префиксом длины «самой дорогой ошибкой в один байт» в истории.
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. 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. 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.
Ограничения
Хотя это представление легко реализовать, оно склонно к ошибкам и проблемам с производительностью. Нуль-терминирование исторически создавало уязвимости в системе безопасности. Символ NUL, вставленный в середину строки, неожиданно обрезает её. Распространенной ошибкой было недостаточное выделение памяти для завершающего нуля, из-за чего он перезаписывал соседние области памяти. Другой ошибкой было полное отсутствие записи завершающего нуля, что часто оставалось незамеченным при тестировании, поскольку блок памяти уже содержал нули. Из-за затрат на определение длины многие программы пренебрегали этим перед копированием строки в буфер фиксированного размера, что приводило к переполнению буфера, если строка была слишком длинной. Невозможность хранения нуля требует раздельного хранения текстовых и бинарных данных и использования для их обработки различных функций (для бинарных данных при этом необходимо указывать и длину). Это может приводить к дублированию кода и ошибкам при использовании неверной функции. Проблемы с производительностью при определении длины обычно можно решить, объединив эту операцию с другой, имеющей сложность O(n), например, как в strlcpy. Однако это не всегда обеспечивает интуитивно понятный API.
While simple to implement, this representation has been prone to errors and performance problems. Null termination has historically created security problems. A NUL 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 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.
Кодировки символов
Строки с нулевым терминатором требуют, чтобы кодировка не использовала нулевой байт (0x00) нигде; следовательно, невозможно сохранить каждую возможную строку ASCII или UTF-8. Однако обычно подмножество ASCII или UTF-8 – все символы, кроме NUL – хранится в строках с нулевым терминатором. Некоторые системы используют "модифицированный UTF-8", который кодирует NUL как два ненулевых байта (0xC0, 0x80) и таким образом позволяет хранить все возможные строки. Это не допускается стандартом UTF-8, поскольку это избыточно длинная кодировка, и это считается угрозой безопасности. Вместо этого в качестве конца строки могут использоваться другие байты, например 0xFE или 0xFF, которые не используются в UTF-8. UTF-16 использует 2-байтовые целые числа, и поскольку любой байт может быть нулевым (фактически, каждый второй байт является нулевым при представлении текста ASCII), его нельзя хранить в строке байтов с нулевым терминатором. Однако некоторые языки реализуют строку из 16-битных символов UTF-16, завершаемую 16-битным NUL (0x0000).
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. 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).
Улучшения
Было предпринято множество попыток сделать обработку строк в C менее подверженной ошибкам. Одна из стратегий заключается в добавлении более безопасных функций, таких как strdup и strlcpy, и одновременном отказе от использования небезопасных функций, например, gets. Другая – добавить объектно-ориентированную оболочку вокруг строк C, чтобы разрешить только безопасные вызовы. Однако, небезопасные функции все равно можно вызывать напрямую. Большинство современных библиотек заменяют строки C структурой, содержащей значение длины размером 32 бита или больше (что значительно превышает размеры, рассматриваемые для строк с префиксом длины), и часто добавляют дополнительный указатель, счетчик ссылок и даже нулевой символ для ускорения преобразования обратно в строку C. Объем памяти сейчас значительно больше, поэтому, если добавление 3 (или 16, или более) байтов к каждой строке действительно является проблемой, программное обеспечение должно будет работать с таким количеством коротких строк, что другой метод хранения позволит сэкономить еще больше памяти (например, если существует большое количество дубликатов, хэш-таблица может использовать меньше памяти). Примеры включают std::string из C++ Standard Template Library, QString из Qt, CString из MFC, а также реализацию CFString на основе C из Core Foundation и ее аналог на Objective-C – NSString из Foundation, обе разработаны Apple. Для хранения строк также могут использоваться более сложные структуры, такие как rope (веревка).
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.