Cadena terminada en nulo - Null-terminated string

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 de cero, llamado NUL en este artículo). Los nombres alternativos son cadena C , que se refiere al lenguaje de programación C y ASCIIZ (aunque C puede usar codificaciones distintas de 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 cuerda. 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).

Historia

Las cadenas terminadas en nulo fueron producidas por la .ASCIZdirectiva 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 derivó), 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 que, para encontrar la longitud de una cadena ya almacenada, solo necesite un acceso a la memoria (tiempo O (1) (constante) ), pero una longitud de cadena limitada a 255 caracteres (en una máquina que usa bytes de 8 bits ). 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, según su experiencia, mantener el conteo parecía menos conveniente que usar un terminador.

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 prefijos 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 vio, por ejemplo, en la decisión de IBM de agregar las instrucciones de "Asistencia de cadena lógica" al ES / 9000 520 en 1992 y las instrucciones de cadena vectorial para el IBM z13 en 2015.

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 un byte) como "el error de un byte más caro" de todos los tiempos.

Limitaciones

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

La terminación nula ha creado históricamente problemas de seguridad . Un NUL insertado en el medio de una cadena la truncará inesperadamente. Un error común era no asignar espacio adicional para el NUL, por lo que se escribía en la memoria adyacente. Otro fue 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 molestaron antes de copiar una cadena en un búfer de tamaño fijo , lo que provocó un desbordamiento del búfer si era demasiado largo.

La incapacidad de almacenar un cero requiere que el texto y los datos binarios se mantengan distintos y manejados por diferentes funciones (y esta última requiere 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ándola con otra operación que sea O ( n ) de todos modos, como in strlcpy. Sin embargo, esto no siempre resulta en una API intuitiva .

Codificaciones de caracteres

Las cadenas terminadas en nulo requieren que la codificación no utilice un byte cero (0x00) en ningún lugar, por lo que no es posible almacenar todas las cadenas ASCII o UTF-8 posibles . 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, permiten 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 usar algún otro byte como final de cadena, como 0xFE o 0xFF, que no se usan en UTF-8.

UTF-16 utiliza números enteros de 2 bytes y, dado que cualquiera de los bytes puede ser cero (y de hecho, todos los demás bytes, cuando representan texto ASCII), no se pueden almacenar en una cadena de bytes terminada en nulo. Sin embargo, algunos lenguajes implementan una cadena de caracteres UTF-16 de 16 bits , terminada por un NUL de 16 bits.

Mejoras

Se han realizado muchos intentos para hacer que el manejo de cadenas de C sea menos propenso a errores. Una estrategia es agregar funciones más seguras como strdupy strlcpy, mientras se desaprueba el uso de funciones inseguras como gets. Otra es agregar una envoltura orientada a objetos alrededor de cadenas 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 C con una estructura que contiene un valor de longitud de 32 bits o mayor (mucho más de lo que se consideró para cadenas con prefijos de longitud) y, a menudo, agregan otro puntero, un recuento de referencias e incluso un NUL para acelerar la conversión. de nuevo a una cuerda 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á aún más memoria. (por ejemplo, puede haber tantos duplicados que una tabla hash utilice menos memoria). Los ejemplos incluyen la biblioteca de plantillas estándar C ++std::string , Qt QString , MFC CString y la implementación basada en C CFStringde Core Foundation , así como su hermano Objective-CNSString de Foundation , ambos de Apple. También se pueden utilizar estructuras más complejas para almacenar cuerdas como la cuerda .

Ver también

Referencias