Cadena terminada en nulo

En programación informática , una cadena terminada en nulo es una cadena de caracteres almacenada como una matriz que contiene los caracteres y termina con un carácter nulo (un carácter con un valor interno de cero, llamado "NUL" en este artículo, no es lo mismo que el glifo cero). Los nombres alternativos son cadena C , que hace referencia al lenguaje de programación C y ASCIIZ ^[1] (aunque C puede usar codificaciones distintas a ASCII ).

La longitud de una cadena se obtiene buscando el (primer) NUL. Esto puede ser lento, ya que lleva O( n ) ( tiempo lineal ) con respecto a la longitud de la cadena. También significa que una cadena no puede contener un NUL (hay un NUL en la memoria, pero está después del último carácter, no en la cadena).

Las cadenas terminadas en cero se produjeron mediante la .ASCIZdirectiva de los lenguajes ensambladores PDP-11 y la directiva del lenguaje ensamblador de macros MACRO-10 para PDP-10 . Estas son anteriores al desarrollo del lenguaje de programación C, pero se usaban con frecuencia otras formas de cadenas.ASCIZ

En la época en que se desarrolló C (y los lenguajes de los que se derivaba), la memoria era extremadamente limitada, por lo que utilizar un solo byte de sobrecarga para almacenar la longitud de una cadena era atractivo. La única alternativa popular en ese momento, generalmente llamada "cadena Pascal" (un término más moderno es " con prefijo de longitud "), utilizaba un byte inicial para almacenar la longitud de la cadena. Esto permite que la cadena contenga NUL y hace que encontrar la longitud requiera solo un acceso a memoria ( tiempo O(1) (constante) ), pero limita la longitud de la cadena a 255 caracteres. El diseñador de C Dennis Ritchie eligió seguir la convención de terminación nula para evitar la limitación en la longitud de una cadena y porque mantener el conteo parecía, en su experiencia, menos conveniente que usar un terminador. ^{[2] [3]}

Esto tuvo cierta influencia en el diseño del conjunto de instrucciones de la CPU . Algunas CPU de los años 1970 y 1980, como la Zilog Z80 y la DEC VAX , tenían instrucciones dedicadas para manejar cadenas con prefijo de longitud. Sin embargo, a medida que la cadena terminada en cero ganó fuerza, los diseñadores de CPU comenzaron a tenerla en cuenta, como se vio, por ejemplo, en la decisión de IBM de agregar las instrucciones "Logical String Assist" al ES/9000 520 en 1992 y las instrucciones de cadena vectorial al IBM z13 en 2015. ^[4]

El desarrollador de FreeBSD Poul-Henning Kamp , escribiendo en ACM Queue , se refirió a la victoria de las cadenas terminadas en nulo sobre una longitud de 2 bytes (no de un byte) como "el error de un byte más costoso" de la historia. ^[5]

Si bien es fácil de implementar, esta representación ha sido propensa a errores y problemas de rendimiento.

Históricamente, la terminación nula ha creado problemas de seguridad . ^[6] Un NUL insertado en el medio de una cadena la truncará inesperadamente. ^[7] Un error común era no asignar el espacio adicional para el NUL, por lo que se escribía sobre la memoria adyacente. Otro era no escribir el NUL en absoluto, lo que a menudo no se detectaba durante las pruebas porque el bloque de memoria ya contenía ceros. Debido al costo de encontrar la longitud, muchos programas no se molestaban antes de copiar una cadena a un búfer de tamaño fijo , lo que causaba un desbordamiento del búfer si era demasiado largo.

La imposibilidad de almacenar un cero requiere que los datos de texto y binarios se mantengan separados y sean manejados por funciones diferentes (y estos últimos requieren que también se proporcione la longitud de los datos). Esto puede generar redundancia de código y errores cuando se utiliza la función incorrecta.

Los problemas de velocidad para encontrar la longitud se pueden mitigar generalmente al combinarla con otra operación que sea O( n ) de todos modos, como en strlcpy. Sin embargo, esto no siempre da como resultado una API intuitiva .

Las cadenas terminadas en nulo requieren que la codificación no utilice un byte cero (0x00) en ninguna parte; por lo tanto, no es posible almacenar todas las cadenas ASCII o UTF-8 posibles . ^{[8] [9] [10]} Sin embargo, es común almacenar el subconjunto de ASCII o UTF-8 (cada carácter excepto NUL) en cadenas terminadas en nulo. Algunos sistemas utilizan " UTF-8 modificado " que codifica NUL como dos bytes distintos de cero (0xC0, 0x80) y, por lo tanto, permite almacenar todas las cadenas posibles. Esto no está permitido por el estándar UTF-8, porque es una codificación demasiado larga y se considera un riesgo de seguridad. Se puede utilizar algún otro byte como final de cadena en su lugar, como 0xFE o 0xFF, que no se utilizan en UTF-8.

UTF-16 utiliza números enteros de 2 bytes y, como cada byte puede ser cero (y, de hecho, cada byte lo es, cuando se representa texto ASCII), no se puede almacenar en una cadena de bytes terminada en cero. Sin embargo, algunos lenguajes implementan una cadena de caracteres UTF-16 de 16 bits , terminada en un NUL de 16 bits (0x0000).

Se han hecho muchos intentos para que el manejo de cadenas de C sea menos propenso a errores. Una estrategia es agregar funciones más seguras como strdupy strlcpy, y desaprobar el uso de funciones inseguras como gets. Otra es agregar un contenedor orientado a objetos alrededor de las cadenas de C para que solo se puedan realizar llamadas seguras. Sin embargo, es posible llamar a las funciones inseguras de todos modos.

La mayoría de las bibliotecas modernas reemplazan las cadenas de C con una estructura que contiene un valor de longitud de 32 bits o mayor (mucho más de lo que se consideró alguna vez para cadenas con prefijo de longitud) y a menudo agregan otro puntero, un conteo de referencia e incluso un NUL para acelerar la conversión de regreso a una cadena de C. La memoria es mucho más grande ahora, de modo que si la adición de 3 (o 16, o más) bytes a cada cadena es un problema real, el software tendrá que lidiar con tantas cadenas pequeñas que algún otro método de almacenamiento ahorrará incluso más memoria (por ejemplo, puede haber tantos duplicados que una tabla hash usará menos memoria). Los ejemplos incluyen la Biblioteca de plantillas estándar de C++ , Qt , MFC y la implementación basada en C de Core Foundation, así como su hermano Objective-C de Foundation , ambos de Apple. También se pueden usar estructuras más complejas para almacenar cadenas, como rope . std::string QString CStringCFStringNSString

• Cadena vacía
• Valor centinela