Stringa null-terminata
In programmazione, una stringa null-terminata è una stringa di caratteri memorizzata come un vettore contenente i caratteri e terminata con un carattere null (un carattere con valore zero, chiamato NUL in questo articolo). I nomi alternativi sono stringa C, che si riferisce al linguaggio di programmazione C e ASCIIZ (sebbene C possa usare codifiche diverse da ASCII).
La lunghezza di una stringa si trova cercando il (primo) NUL. Questo può essere lento in quanto richiede un tempo lineare O(n) rispetto alla lunghezza della stringa. Significa anche che una stringa non può contenere un NUL (c'è un NUL in memoria, ma è dopo l'ultimo carattere, non "nella" stringa).
Storia
[modifica | modifica wikitesto]Le stringhe null-terminate sono state introdotte dalla direttiva . ASCIZ dei linguaggi assembly PDP-11 e dalla direttiva ASCIZ del linguaggio assembly macro MACRO-10 per il PDP-10. Questi precedono lo sviluppo del linguaggio di programmazione C, ma sono state spesso utilizzate altre forme di stringhe.
Al momento dello sviluppo del C (e dei linguaggi da cui deriva), la memoria era estremamente limitata, quindi l'utilizzo di un solo byte di sovraccarico per memorizzare la lunghezza di una stringa era interessante. L'unica alternativa popolare a quel tempo, solitamente chiamata "stringa Pascal" (un termine più moderno è "lunghezza prefissata"), utilizzava un byte iniziale per memorizzare la lunghezza della stringa. Ciò consente alla stringa di contenere NUL e la ricerca della lunghezza di una stringa già memorizzata richiede solo un accesso alla memoria in tempo costante O(1), ma la lunghezza della stringa è limitata a 255 caratteri (su una macchina che utilizza byte a 8 bit). Il progettista del linguaggio C Dennis Ritchie ha scelto di seguire la convenzione della terminazione con carattere nullo per evitare la limitazione della lunghezza di una stringa e perché mantenere il conteggio sembrava, nella sua esperienza, meno conveniente rispetto all'utilizzo di un terminatore.[1][2]
Ciò ha avuto una certa influenza sulla progettazione del set di istruzioni della CPU. Alcune CPU negli anni '70 e '80, come Zilog Z80 e DEC VAX, avevano istruzioni dedicate per la gestione delle stringhe con prefisso di lunghezza. Tuttavia, quando la stringhe null-terminate hanno guadagnato trazione, i progettisti delle CPU hanno iniziato a tenerne conto, come si è visto ad esempio nella decisione di IBM di aggiungere le istruzioni "Logical String Assist" all'ES/9000 520 nel 1992.
Lo sviluppatore FreeBSD Poul-Henning Kamp, scrivendo in ACM Queue, ha definito la vittoria delle stringhe null-terminate su una lunghezza di 2 byte (non un byte) come "l'errore di un byte più costoso" di sempre.[3]
Limitazioni
[modifica | modifica wikitesto]Sebbene semplice da implementare, questa rappresentazione è stata soggetta a errori e problemi di prestazione.
La terminazione nulla ha storicamente creato problemi di sicurezza.[4] Un NUL inserito nel mezzo di una stringa la troncherà inaspettatamente.[5] Un bug comune era quello di non allocare lo spazio aggiuntivo per il NUL, che quindi veniva scritto sulla memoria adiacente. Un altro era di non scrivere affatto il NUL, che spesso non veniva rilevato durante il test perché il blocco di memoria conteneva già degli zeri. A causa delle spese per trovare la lunghezza, molti programmi non si sono preoccupati di copiare una stringa in un buffer di dimensioni fisse, causando un overflow del buffer se era troppo lungo.
L'impossibilità di memorizzare uno zero richiede che testo e dati binari siano mantenuti distinti e gestiti da funzioni diverse (quest'ultima richiede che venga fornita anche la lunghezza dei dati). Ciò può portare a ridondanza del codice ed errori quando viene utilizzata la funzione sbagliata.
I problemi di velocità nel trovare la lunghezza di solito possono essere mitigati combinandola con un'altra operazione che è comunque O(n), come la funzionestrlcpy. Tuttavia, questo non si traduce sempre in un'API intuitiva.
Codifiche dei caratteri
[modifica | modifica wikitesto]Le stringhe null-terminate richiedono che la codifica non utilizzi un byte zero (0x00) da nessuna parte, quindi non è possibile memorizzare tutte le possibili stringhe ASCII o UTF-8.[6][7][8] Tuttavia, è comune memorizzare il sottoinsieme di ASCII o UTF-8 – ogni carattere tranne NUL – in stringhe null-terminate. Alcuni sistemi usano "UTF-8 modificato" che codifica NUL come due byte diversi da zero (0xC0, 0x80) e quindi consente di memorizzare tutte le stringhe possibili. Questo non è consentito dallo standard UTF-8, perché è una codifica troppo lunga ed è vista come un rischio per la sicurezza. Alcuni altri byte possono essere invece utilizzati come fine della stringa, come 0xFE o 0xFF, che non vengono utilizzati in UTF-8.
UTF-16 utilizza numeri interi a 2 byte e poiché entrambi i byte possono essere zero (e infatti ogni altro byte lo è, quando si rappresenta testo ASCII), non può essere archiviato in una stringa di byte con terminazione null. Tuttavia, alcuni linguaggi implementano una stringa di caratteri UTF-16 a 16 bit, terminata da un NUL a 16 bit.
Miglioramenti
[modifica | modifica wikitesto]Sono stati fatti molti tentativi per rendere la gestione delle stringhe C meno soggetta a errori. Una strategia consiste nell'aggiungere funzioni più sicure come strdup e strlcpy, deprecando al contempo l'uso di funzioni non sicure come gets. Un altro è aggiungere un wrapper orientato agli oggetti attorno alle stringhe C in modo che possano essere eseguite solo chiamate sicure. Tuttavia anche così facendo risulta comunque possibile chiamare le funzioni non sicure.
La maggior parte delle librerie moderne sostituisce le stringhe C con una struttura contenente un valore di lunghezza pari o superiore a 32 bit (molto più di quanto non sia mai stato considerato per le stringhe di lunghezza prefissata) e spesso aggiunge un altro puntatore, un conteggio dei riferimenti e persino un NUL per accelerare la conversione inversa ad una stringa C. La memoria ora è molto più grande, in modo tale che se l'aggiunta di 3 (o 16 o più) byte a ciascuna stringa è un problema reale, il software dovrà gestire così tante piccole stringhe che qualche altro metodo di archiviazione farà risparmiare ancora più memoria (ad esempio potrebbero esserci così tanti duplicati che una tabella hash utilizzerà meno memoria). Gli esempi includono la Standard Template Library del C++std::string, Qt QString, MFC CString e l'implementazione basata sul linguaggio C CFString di Core Foundation, nonché il fratello Objective-C NSString di Foundation, entrambi di Apple. Strutture più complesse possono essere utilizzate anche per riporre le stringhe come le corde.
Note
[modifica | modifica wikitesto]- ^ (EN) Dennis M. Ritchie, The development of the C language, Second History of Programming Languages conference, Cambridge (MA), Aprile 1993.
- ^ (EN) Dennis M. Ritchie, The development of the C language, in Thomas J. Bergin, Jr. , Richard G. Gibson, Jr. (a cura di), History of Programming Languages, Addison-Wesley (Reading, Mass), 2ª ed., New York, ACM Press, 1996, ISBN 0-201-89502-1.
- ^ (EN) Poul-Henning Kamp, The Most Expensive One-byte Mistake, in ACM Queue, vol. 9, n. 7, 25 luglio 2011, ISSN 1542-7730. URL consultato il 2 agosto 2011.
- ^ Rain Forest Puppy, Perl CGI problems (TXT), in Phrack Magazine, vol. 9, n. 55, artofhacking.com, 9 settembre 1999, p. 7. URL consultato il 3 gennaio 2016.
- ^ Null byte injection on PHP?, su Information Security Stack Exchange. URL consultato il 1º luglio 2021.
- ^ UTF-8, a transformation format of ISO 10646, su tools.ietf.org. URL consultato il 19 settembre 2013.
- ^ Unicode/UTF-8-character table, su utf8-chartable.de. URL consultato il 13 settembre 2013.
- ^ Markus Kuhn, UTF-8 and Unicode FAQ, su cl.cam.ac.uk. URL consultato il 13 settembre 2013.
