Каковы проблемы строки с нулевым завершением, которую префиксные строки превзойдут?

Ответ 1

Одна из проблем заключается в том, что при нулевых концах вам нужно постоянно находить конец строки. Классический пример, когда это неэффективно, заключается в конкатенации в буфер:

char buf[1024] = "first";
strcat(buf, "second");
strcat(buf, "third");
strcat(buf, "fourth");

При каждом вызове strcat программа должна начинаться с начала строки и находить терминатор, чтобы узнать, с чего начать добавление. Это означает, что функция тратит все больше времени на поиск места для добавления, поскольку строка увеличивается дольше.

С строкой с префиксом длины эквивалент функции strcat будет знать, где заканчивается сразу, и просто обновит длину после добавления к ней.

Есть плюсы и минусы для каждого способа представления строк и зависят ли они от проблем, зависящих от того, что вы делаете со строками, и какие операции должны быть эффективными. Описанную выше проблему можно преодолеть, вручную отслеживая конец строки по мере ее роста, поэтому, изменяя код, вы можете избежать затрат на производительность.

Ответ 2

Одна из проблем заключается в том, что нельзя хранить нулевые символы (нулевое значение) в строке с нулевым завершением. Это делает невозможным сохранение некоторых кодировок символов, а также зашифрованных данных.

Строки с префиксом длины не претерпевают этого ограничения.

Ответ 3

Сначала уточнение: строки С++ (т.е. std::string) не не должны были заканчиваться нулем до С++ 11. Однако они всегда предоставляли доступ к строкам C с нулевым завершением.

Строки в стиле C заканчиваются символом 0 по историческим причинам.

Проблемы, о которых вы говорите, связаны главным образом с проблемами безопасности: нулевые строки нуждаются, чтобы иметь нулевой терминатор. Если им не хватает (по какой-либо причине), длина строки становится ненадежной, и они могут привести к проблемам переполнения буфера (которые злоумышленник может использовать, записывая произвольные данные в местах, где это не должно быть. DEP помогает смягчить эти проблемы, но это не по теме).

Ответ 4

Лучше всего резюмировать в Самая дорогая однобайтная ошибка от Poul-Henning Kamp.

• Эксплуатационные затраты: дешевле манипулировать памятью в кусках, что невозможно, если вам всегда нужно искать символ NULL. Другими словами, если вы знаете, что у вас есть строка с 129 символами, скорее всего, будет более эффективно манипулировать ею в разделах 64, 64 и 1 байт вместо символа по символу.

• Безопасность: Марко А. уже сильно ударил. Перегруженные и запущенные буферы строк по-прежнему являются основным маршрутом для атак хакеров.

• Расходы на разработку компилятора: большие затраты связаны с оптимизацией компиляторов для нулевых завершающих строк, которые были бы проще с использованием формата адреса и длины.

• Затраты на разработку оборудования: затраты на разработку оборудования также велики для строковых инструкций, связанных с нулевыми завершающими строками.

Ответ 5

Несколько дополнительных функций, которые могут быть реализованы с помощью строк с префиксом длины:

• Возможно иметь несколько стилей префикса длины, идентифицируемых через один или несколько битов первого байта, идентифицированных указателем/ссылкой строки. В обмен на небольшое дополнительное время, определяющее длину строки, можно, например, используйте однобайтовый префикс для коротких строк и более длинных префиксов для более длинных строк. Если вы используете много 1-3 байтовых строк, которые могли бы сэкономить более 50% общего потребления памяти для таких строк по сравнению с использованием фиксированного четырехбайтового префикса; такой формат может также содержать строки, длина которых превышала диапазон 32-битных целых чисел.

• Можно хранить строки переменной длины в проверенных границах буферах по цене только одного или двух битов в префиксе длины. Число N, объединенное с другими битами, будет указывать на одну из трех вещей:

  • Строка в N-байте

  • (Необязательно) N-байтовый буфер, содержащий строку с нулевой длиной

  • N-байтовый буфер, который, если последний бит B меньше 248, содержит строку длины N-B-1; если 248 или более, предыдущие байты B-247 сохраняют разницу между размером буфера и длиной строки. Обратите внимание, что если длина строки точно равна N-1, за строкой будет следовать NUL-байт, и если она меньше, чем байт, следующий за строкой, будет неиспользован и может быть установлен в NUL.

  Используя такой подход, нужно будет инициализировать сильные буферы перед использованием (указать их длину), но тогда больше не нужно будет передавать длину строкового буфера подпрограмму, которая собиралась хранить там данные.

• Можно использовать определенные значения префикса для обозначения различных особых вещей. Например, может быть префикс, который указывает, что за ним не следует строка, а скорее указателем строки и двумя целыми числами, задающими размер буфера и текущую длину. Если методы, которые работают с строками, вызывают метод для получения указателя данных, размера и длины буфера, можно передать такой метод ссылку на часть строки дешево при условии, что сама строка переведет вызов метода.

• Можно расширить описанную выше функцию бит, чтобы указать, что строковые данные находятся в области, которая была сгенерирована с помощью malloc и при необходимости может быть изменена; кроме того, можно смело иметь методы, которые иногда возвращают динамически сгенерированную строку, выделенную в куче, и иногда возвращают неизменяемую статическую строку, и получатель выполняет "освободить эту строку, если она не является статикой".

Я не знаю, реализуют ли какие-либо префиксные реализации все эти бонусные функции, но все они могут быть размещены за очень небольшую стоимость в пространстве для хранения, относительно небольшую стоимость кода и меньше затрат во времени, чем требуется для используйте строки с NUL-концами, длина которых не была ни известной, ни короткой.

Ответ 6

Каковы проблемы строки с нулевым концом, прерванные префиксными строками?

Ничего. Это просто глазная конфета.

Строки с префиксом длины имеют, как часть своей структуры, информацию о том, как долго длится строка. Если вы хотите сделать то же самое с нулевыми строками, вы можете использовать вспомогательную переменную;

lpstring = "foobar"; // saves '6' somewhere "inside" lpstring

ztstring = "foobar";
ztlength = 6;        // saves '6' in a helper variable

_{Множество функций библиотеки C работают с нулевыми строками и не могут использовать ничего, кроме байта '\0'. Это проблема с самими функциями, а не с строковой структурой. Если вам нужны функции, связанные с нулевыми строками со встроенными нулями, напишите свой собственный.}