В компьютерном программировании , А строка завершается нулем является строка символов хранятся в виде массива , содержащего символы , и прекращается с нулевым символом (символ с нулевым значением, называется NUL в этой статье). Альтернативные имена - строка C , которая относится к языку программирования C и ASCIIZ (хотя C может использовать кодировки, отличные от ASCII).
Длина строки определяется поиском (первого) NUL. Это может быть медленным, поскольку занимает O ( n ) ( линейное время ) по отношению к длине строки. Это также означает, что строка не может содержать NUL (в памяти есть NUL, но он стоит после последнего символа, а не "в" строке).
История
Строки с завершающим нулем были созданы .ASCIZ
директивой языков ассемблера PDP-11 и директивой языка ассемблера макросов MACRO-10 для PDP-10 . Они предшествовали развитию языка программирования C, но часто использовались другие формы строк.ASCIZ
Во время разработки C (и языков, на которых он был основан) память была чрезвычайно ограничена, поэтому использование только одного байта служебных данных для хранения длины строки было привлекательным. Единственная популярная альтернатива в то время, обычно называемая «строка Паскаля» (более современный термин - «с префиксом длины »), использовала ведущий байт для хранения длины строки. Это позволяет строке содержать NUL, и для определения длины требуется только один доступ к памяти (время O (1) (постоянное) ), но ограниченная длина строки до 255 символов (на машине, использующей 8-битные байты). Разработчик C Деннис Ричи решил следовать соглашению о нулевом завершении, уже установленному в BCPL , чтобы избежать ограничения на длину строки и потому, что, по его опыту, поддержание счетчика казалось менее удобным, чем использование терминатора. [1] [2]
Это оказало некоторое влияние на дизайн набора команд ЦП . Некоторые процессоры 1970-х и 1980-х годов, такие как Zilog Z80 и DEC VAX , имели специальные инструкции для обработки строк с префиксом длины. Однако по мере того, как строка с завершающим нулем набирала обороты, разработчики ЦП начали принимать ее во внимание, как, например, было видно в решении IBM добавить инструкции «Logical String Assist» в ES / 9000 520 в 1992 году.
Разработчик FreeBSD Пол-Хеннинг Камп , писавший в ACM Queue , позже назовет победу строк с завершающим нулем над 2-байтовой (а не однобайтовой) длиной как «самой дорогой однобайтовой ошибкой». [3]
Ограничения
Несмотря на простоту реализации, это представление было подвержено ошибкам и проблемам с производительностью.
Нулевое завершение исторически создавало проблемы с безопасностью . [4] NUL, вставленный в середину строки, неожиданно обрезает ее. [5] Распространенной ошибкой было то, что для NUL не выделялось дополнительное пространство, поэтому он был записан поверх смежной памяти. Другой заключался в том, чтобы вообще не записывать NUL, что часто не обнаруживалось во время тестирования, потому что блок памяти уже содержал нули. Из-за затрат на определение длины многие программы не беспокоились перед копированием строки в буфер фиксированного размера , что приводило к переполнению буфера, если оно было слишком длинным.
Неспособность хранить ноль требует, чтобы текст и двоичные данные были разделены и обрабатывались разными функциями (причем последние требуют, чтобы длина данных также была предоставлена). Это может привести к избыточности кода и ошибкам при использовании неправильной функции.
Проблемы со скоростью при нахождении длины обычно можно уменьшить, комбинируя ее с другой операцией, которая в любом случае равна O ( n ), например in strlcpy
. Однако это не всегда приводит к интуитивно понятному API .
Кодировки символов
Строки с завершающим нулем требуют, чтобы кодировка нигде не использовала нулевой байт (0x00), поэтому невозможно сохранить все возможные строки ASCII или UTF-8 . [6] [7] [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.
Улучшения
Было сделано много попыток сделать обработку строк C менее подверженной ошибкам. Одна из стратегий заключается в добавлении более безопасных функций, таких как strdup
и strlcpy
, при одновременном отказе от использования небезопасных функций, таких как gets
. Другой - добавить объектно-ориентированную оболочку вокруг строк C, чтобы можно было выполнять только безопасные вызовы. Однако в любом случае можно вызывать небезопасные функции.
Большинство современных библиотек заменяют строки C структурой, содержащей 32-битное или большее значение длины (гораздо больше, чем когда-либо считалось для строк с префиксом длины), и часто добавляют еще один указатель, счетчик ссылок и даже NUL для ускорения преобразования. вернуться к строке C. Память теперь намного больше, так что если добавление 3 (или 16 или более) байтов к каждой строке является реальной проблемой, программное обеспечение должно будет иметь дело с таким количеством маленьких строк, что какой-то другой метод хранения сэкономит еще больше памяти. (например, может быть так много дубликатов, что хеш-таблица будет использовать меньше памяти). Примеры включают стандартную библиотеку шаблонов C ++ , Qt , MFC и реализацию на основе C от Core Foundation, а также ее родственную версию Objective-C от Foundation , обе от Apple. Более сложные конструкции также могут использоваться для хранения струн, таких как веревка . std::string
QString
CString
CFString
NSString
Смотрите также
- Пустая строка
- Сторожевое значение
Рекомендации
- ^ Ричи, Деннис М. (апрель 1993). Развитие языка Си . Вторая конференция по истории языков программирования. Кембридж, Массачусетс.
- ^ Ричи, Деннис М. (1996). «Развитие языка Си». In Bergin, Jr., Thomas J .; Гибсон-младший, Ричард Г. (ред.). История языков программирования (2-е изд.). Нью-Йорк: ACM Press. ISBN 0-201-89502-1 - через Аддисон-Уэсли (Ридинг, Массачусетс).
- ^ Камп, Поул-Хеннинг (25 июля 2011 г.), «Самая дорогая однобайтовая ошибка» , ACM Queue , 9 (7), ISSN 1542-7730 , получено 2 августа 2011 г.
- ^ Щенок дождевого леса (9 сентября 1999 г.). «Проблемы Perl CGI» . Журнал Phrack . artofhacking.com. 9 (55): 7 . Проверено 3 января +2016 .
- ^ https://security.stackexchange.com/questions/48187/null-byte-injection-on-php
- ^ «UTF-8, формат преобразования ISO 10646» . Проверено 19 сентября 2013 года .
- ^ «Таблица Unicode / UTF-8 символов» . Проверено 13 сентября 2013 года .
- ^ Кун, Маркус. «Часто задаваемые вопросы по UTF-8 и Unicode» . Проверено 13 сентября 2013 года .