En programación de computadoras , una cadena terminada en nulo es una cadena de caracteres almacenada como una matriz que contiene los caracteres y terminada 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 se refiere al lenguaje de programación C y ASCIIZ [1] (aunque C puede usar codificaciones distintas a ASCII ).
La longitud de una cadena se encuentra buscando el (primer) NUL. Esto puede ser lento ya que toma 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 nulo fueron producidas por la .ASCIZ
directiva de los lenguajes ensambladores PDP-11 y la directiva del lenguaje ensamblador macro MACRO-10 para el PDP-10 . Estos son anteriores al desarrollo del lenguaje de programación C, pero a menudo se usaban otras formas de cadenas.ASCIZ
En el momento en que se desarrolló C (y los lenguajes de los que se deriva), la memoria era extremadamente limitada, por lo que usar solo un 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 " prefijo de longitud "), usaba un byte inicial para almacenar la longitud de la cadena. Esto permite que la cadena contenga NUL y para encontrar la longitud solo se necesita un acceso a la memoria (O(1) (constante) tiempo ), pero la longitud de la cadena se limita a 255 caracteres. El diseñador de C Dennis Ritchie optó por seguir la convención de terminación nula para evitar la limitación de 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 las décadas de 1970 y 1980, como Zilog Z80 y DEC VAX , tenían instrucciones dedicadas para manejar cadenas con prefijo de longitud. Sin embargo, a medida que la cadena terminada en nulo ganó fuerza, los diseñadores de CPU comenzaron a tenerla en cuenta, como se ve, 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 para el 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 caro" 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 espacio adicional para NUL, por lo que se escribía en la memoria adyacente. Otra era no escribir 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 molestaron antes de copiar una cadena a un búfer de tamaño fijo , provocando un desbordamiento del búfer si era demasiado larga.
La incapacidad de almacenar un cero requiere que el texto y los datos binarios se mantengan distintos y manejados por diferentes funciones (estas últimas requieren que también se proporcione la longitud de los datos). Esto puede provocar redundancia de código y errores cuando se utiliza la función incorrecta.
Los problemas de velocidad para encontrar la longitud generalmente se pueden mitigar combinándolos 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 (todos los caracteres 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 para la seguridad. En su lugar, se puede utilizar algún otro byte como final de cadena, como 0xFE o 0xFF, que no se utilizan en UTF-8.
UTF-16 utiliza enteros de 2 bytes y, como cualquiera de los bytes puede ser cero (y de hecho, todos los demás bytes lo son, cuando se representa texto ASCII), no se puede almacenar en una cadena de bytes terminada en nulo. Sin embargo, algunos lenguajes implementan una cadena de caracteres UTF- 16 de 16 bits , terminada en un NUL de 16 bits (0x0000).
Se han realizado muchos intentos para hacer que el manejo de cadenas C sea menos propenso a errores. Una estrategia es agregar funciones más seguras como strdup
y strlcpy
, mientras se desaconseja el uso de funciones inseguras como gets
. Otra es agregar un contenedor orientado a objetos alrededor de las cadenas C para que solo se puedan realizar llamadas seguras. Sin embargo, es posible llamar a funciones inseguras de todos modos.
La mayoría de las bibliotecas modernas reemplazan las cadenas C con una estructura que contiene un valor de longitud de 32 bits o mayor (mucho más de lo que alguna vez se consideró para cadenas con prefijo de longitud) y, a menudo, agregan otro puntero, un recuento de referencias e incluso un NUL para acelerar la conversión. De vuelta a una cuerda C. La memoria es mucho mayor 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á aún más memoria. (por ejemplo, puede haber tantos duplicados que una tabla hash utilizará 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 utilizar estructuras más complejas para almacenar hilos como la cuerda . std::string
QString
CString
CFString
NSString