Строка с нулевым завершением
В компьютерном программировании строка с нулевым завершением — это символьная строка, хранящаяся в виде массива , содержащего символы и заканчивающаяся нулевым символом (символ с внутренним значением, равным нулю, в этой статье называемый «NUL», а не то же самое, что глиф нулевой ). ). Альтернативные названия — строка C , которая относится к языку программирования C , и ASCIIZ. [1] (хотя C может использовать кодировки, отличные от ASCII ).
Длина строки определяется путем поиска (первого) NUL. Это может быть медленным, поскольку для этого требуется O( n ) ( линейное время ) относительно длины строки. Это также означает, что строка не может содержать NUL (в памяти есть NUL, но он находится после последнего символа, а не в строке).
История
[ редактировать ]Строки с нулевым завершением были созданы .ASCIZ директива PDP-11 языков ассемблера и ASCIZ директива MACRO-10 макроассемблерного языка для PDP-10 . Они появились еще до разработки языка программирования C, но часто использовались и другие формы строк.
В то время, когда разрабатывался C (и языки, на которых он произошел), память была чрезвычайно ограничена, поэтому использование всего лишь одного байта служебных данных для хранения длины строки было привлекательным. Единственная популярная в то время альтернатива, обычно называемая «строкой Паскаля» (более современный термин — « с префиксом длины »), использовала ведущий байт для хранения длины строки. Это позволяет строке содержать NUL, а для определения длины требуется только один доступ к памяти ( время O(1) (постоянное) ), но длина строки ограничена 255 символами. Дизайнер C Деннис Ритчи решил следовать соглашению о нулевом завершении, чтобы избежать ограничения на длину строки и потому, что, по его опыту, поддержание счетчика казалось менее удобным, чем использование терминатора. [2] [3]
Это оказало некоторое влияние на дизайн набора команд ЦП . Некоторые процессоры 1970-х и 1980-х годов, такие как Zilog Z80 и DEC VAX , имели специальные инструкции для обработки строк с префиксом длины. Однако по мере того, как строка с нулевым завершением получила распространение, разработчики процессоров начали принимать ее во внимание, как видно, например, из решения IBM добавить инструкции «Logical String Assist» в ES/9000 520 в 1992 году и инструкции для векторных строк в IBM z13 в 2015 году. [4]
FreeBSD Разработчик Пол-Хеннинг Камп , пишущий в ACM Queue , назвал победу строк с нулевым завершением над двухбайтовой (а не однобайтовой) длиной «самой дорогой однобайтовой ошибкой» за всю историю. [5]
Ограничения
[ редактировать ]Несмотря на простоту реализации, такое представление подвержено ошибкам и проблемам с производительностью.
Нулевое завершение исторически создавало проблемы безопасности . [6] NUL, вставленный в середину строки, неожиданно обрезает ее. [7] Распространенной ошибкой было то, что дополнительное пространство для NUL не выделялось, поэтому оно записывалось в соседнюю память. Другой вариант заключался в том, чтобы вообще не записывать NUL, что часто не обнаруживалось во время тестирования, поскольку блок памяти уже содержал нули. Из-за затрат на определение длины многие программы не утруждали себя копированием строки в буфер фиксированного размера , вызывая переполнение буфера, если она была слишком длинной.
Невозможность хранить ноль требует, чтобы текстовые и двоичные данные хранились отдельно и обрабатывались разными функциями (причем последняя также требует указания длины данных). Это может привести к избыточности кода и ошибкам при использовании неправильной функции.
Проблемы скорости с поиском длины обычно можно уменьшить, объединив ее с другой операцией, которая в любом случае имеет O( n ), например, в strlcpy. Однако это не всегда приводит к созданию интуитивно понятного API .
Кодировки символов
[ редактировать ]Строки с нулевым завершением требуют, чтобы в кодировке нигде не использовался нулевой байт (0x00); поэтому невозможно хранить все возможные строки ASCII или UTF-8 . [8] [9] [10] Однако подмножество 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).
Улучшения
[ редактировать ]Было предпринято множество попыток сделать обработку строк C менее подверженной ошибкам. Одна из стратегий — добавить более безопасные функции, такие как strdup и strlcpy, при этом осуждая использование небезопасных функций, таких как gets. Другой вариант — добавить объектно-ориентированную оболочку вокруг строк C, чтобы можно было выполнять только безопасные вызовы. Однако в любом случае можно вызвать небезопасные функции.
Большинство современных библиотек заменяют строки C структурой, содержащей 32-битное или большее значение длины (намного больше, чем когда-либо считалось для строк с префиксом длины), и часто добавляют еще один указатель, счетчик ссылок и даже NUL для ускорения преобразования. вернемся к строке C. Память теперь намного больше, так что, если добавление 3 (или 16 или более) байтов к каждой строке является реальной проблемой, программному обеспечению придется иметь дело с таким количеством маленьких строк, что какой-либо другой метод хранения сэкономит еще больше памяти. (например, дубликатов может быть так много, что хэш-таблица будет использовать меньше памяти). Примеры включают C++. стандартную библиотеку шаблонов std::string, Qt QString, МФЦ CStringи реализация на основе C CFString от Core Foundation, а также от его Objective-C брата NSString от Foundation , оба от Apple. , также могут использоваться более сложные конструкции Для хранения веревок, таких как веревка .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Глава 15 — Язык ассемблера MIPS» (PDF) . Карлтонский университет . Проверено 9 октября 2023 г.
- ^ Ричи, Деннис М. (апрель 1993 г.). Разработка языка Си . Вторая конференция по истории языков программирования. Кембридж, Массачусетс.
- ^ Ричи, Деннис М. (1996). «Развитие языка Си». В Бергине-младшем, Томасе Дж.; Гибсон-младший, Ричард Г. (ред.). История языков программирования (2-е изд.). Нью-Йорк: ACM Press. ISBN 0-201-89502-1 – через Аддисон-Уэсли (Ридинг, Массачусетс).
- ^ Принципы работы IBM z/Architecture
- ^ Камп, Пол-Хеннинг (25 июля 2011 г.), «Самая дорогая однобайтовая ошибка» , ACM Queue , 9 (7): 40–43, doi : 10.1145/2001562.2010365 , ISSN 1542-7730 , S2CID 30282393
- ^ Щенок тропического леса (9 сентября 1999 г.). «Проблемы Perl CGI» . Журнал Фрак . 9 (55). artofhacking.com: 7 . Проверено 3 января 2016 г.
- ^ «Внедрение нулевых байтов в PHP?» .
- ^ «UTF-8, формат преобразования ISO 10646» . Проверено 19 сентября 2013 г.
- ^ «Таблица символов Unicode/UTF-8» . Проверено 13 сентября 2013 г.
- ^ Кун, Маркус. «Часто задаваемые вопросы по UTF-8 и Unicode» . Проверено 13 сентября 2013 г.
