Řetězec zakončený nulovým znakem
Řetězec zakončený nulovým znakem je v programování způsob reprezentace textového (znakového) řetězce v podobě pole znaků zakončeného nulovým znakem – znakem s hodnotou nula, nazývaným v tomto článku „NUL“, což není totéž jako číslice (glyf) nula. Tato reprezentace řetězců se také nazývá céčkové řetězce podle programovacího jazyka C nebo ASCIIZ[1] (i když mohou používat jiné kódování než ASCII).
Pro zjištění délky řetězce je třeba najít první výskyt znaku NUL. To může být pomalé, protože vyžaduje O(n) porovnání (lineární čas) v závislosti na délce řetězce. Dalším omezením je, že řetězec nemůže obsahovat znaky NUL, který by nebyl chápán jako součást řetězce, ale jako značka jeho konce.
Historie
[editovat | editovat zdroj]Řetězce zakončené nulovým znakem vytvářela direktiva .ASCIZ v jazyce symbolických adres na PDP-11 a direktiva ASCIZ makrojazyka symbolických adres MAKRO-10 pro PDP-10. Ty předcházely vývoji programovacího jazyka C, ale v té době byly často používány i jiné tvary řetězců.
V době, kdy vznikal jazyk C (a jazyky z něho odvozené), byla paměť počítačů velmi omezená, takže použití jediného bajtu pro reprezentaci řetězců s proměnnou délkou bylo atraktivní. Jedinou alternativou v té době byly řetězce, které používaly první bajt pro uložení délky řetězce, později nazývané „Pascalské řetězce“ (podle typu String v jazyce Turbo Pascal), případně „řetězce prefixované délkou“. Tyto řetězce mohou obsahovat všechny znaky včetně znaku NUL a jejich délku lze získat v konstantním čase jediným přístupem k paměti (asymptotická složitost O(1)), ale jejich maximální délka je omezena na 255 znaků. Autor jazyka C Dennis Ritchie zvolil řetězce zakončené nulovým znakem, aby se vyhnul omezení délky řetězce a protože udržování délky se mu zdálo komplikovanější než použití ukončovacího znaku.[2][3]
To mělo určitý vliv na návrh instrukční sady procesorů. Některé procesory v 70. a 80. letech 20. století, např. Z80 a DEC VAX, měly instrukce určené pro zpracovávání řetězců prefixovaných délkou. Protože však řetězce zakončené nulovým znakem dostaly přednost, začali je návrháři procesorů zohledňovat, jak je vidět například na rozhodnutí společnosti IBM přidat v roce 1992 instrukci „Logical String Assist“ do počítačů IBM ES/9000 520 a v roce 2015 přidání vektorových řetězcových instrukcí do procesorů IBM z13.[4]
Vývojář FreeBSD Poul-Henning Kamp v článku v ACM Queue označil volbu řetězců zakončených nulovým znakem místo řetězců s dvoubajtovou délkou za „nejdražší jednobajtovou chybu“ vůbec.[5]
Omezení
[editovat | editovat zdroj]Řetězce zakončené nulovým znakem lze sice jednoduše implementovat, ale tato reprezentace je náchylná k chybám a výkonnostním problémům.
Nulové zakončení v minulosti způsobovalo bezpečnostní problémy.[6] Vložení znaku NUL do řetězce jej neočekávaně zkrátí.[7] Běžnou chybou je opomenutí místa pro znak NUL, které může způsobit, že při uložení řetězce maximální délky se znakem NUL přepíše jiná proměnná. Jinou chybou je nezapsání znaku NUL, což při testování nemusí být vždy odhaleno, pokud blok paměti původně obsahoval nuly. Často chybou je opomenutí kontroly délky před kopírováním řetězce do bufferu pevné velikosti, což může způsobit přetečení bufferu, pokud je řetězec příliš dlouhý.
Nemožnost používat nulové bajty v řetězci vedla k vytvoření zvláštních funkcí pro binární data (které používají informace o délce). To může vést k redundanci kódu a chybám kvůli použití nesprávné funkce.
Problémy s rychlostí při zjišťování délky mohou být obvykle zmírněny jeho zkombinováním s jinými operacemi, které mají složitost O(n), např. v strlcpy. Ne vždy to však vede k intuitivnímu API.
Kódování znaků
[editovat | editovat zdroj]Řetězce zakončené nulovým znakem vyžadují, aby se při kódování řetězců nikde nepoužívaly nulové bajty (0x00); proto není možné v řetězci ukládat všechny možné ASCII nebo UTF-8 znaky.[8][9][10] Je však běžné ukládat podmnožinu ASCII nebo UTF-8 znaků – všechny znaky kromě znaku NUL – v řetězcích zakončených nulovým znakem. Některé systémy používají „modifikované UTF-8“ které kóduje znak NUL v řetězci jako dva nenulové bajty (0xC0, 0x80) a umožňuje tak používat i řetězce obsahující nulové znaky. UTF-8 standard to však zakazuje, a tato reprezentace je považována za bezpečnostní riziko. Alternativou je používat pro ukončení řetězce jiné bajty, které nejsou používány v UTF-8, např. 0xFE nebo 0xFF.
UTF-16 používá dvoubajtová celá čísla, a protože libovolný z bajtů může být nulový (a při reprezentaci ASCII textu je každý druhý bajt nulový), nemůže být uložený v bajtových řetězcích zakončených nulovým znakem. Některé jazyky však implementují řetězce 16bitových UTF-16 znaků ukončené 16bitovým znakem NUL (0x0000).
Vylepšení
[editovat | editovat zdroj]Pro snížení náchylnosti k chybám při práci s řetězci v jazyce C bylo učiněno mnoho pokusů. Jednou z možností je přidání bezpečnějších funkcí, jako jsou strdup a strlcpy, a zároveň znemožnění používání nebezpečných funkcí, jako je gets. Další možností je přidání objektově orientovaného obalu kolem řetězců zakončených nulovým znakem, aby bylo možné volat pouze bezpečné funkce. Nebezpečné funkce je však možné volat stejně.
Většina moderních knihoven nahrazuje řetězce zakončené nulovým znakem strukturou obsahující 32bitový nebo větší údaj o délce řetězce (mnohem větší, než se kdy uvažovalo u řetězců s délkovým prefixem), a často přidává další ukazatel, počet odkazů, a dokonce NUL, aby se zrychlil převod zpátky na řetězce zakončené nulovým znakem. V současnosti není třeba tak šetřit pamětí, ale pokud by přidání 3 (16 nebo více) bajtů ke každému řetězci představovalo opravdu problém, a software musel pracovat s tolika krátkými řetězci, že by jiná metoda ukládání ušetřila ještě více paměti (kdyby například bylo tolik duplicit, že hašovací tabulka budete zabírat méně paměti). Jako příklad lze uvést Standard Template Library pro C++ std::string, Qt QString, MFC CString a CFString vycházející z implementace CFString z Core Foundation stejně jako její protějšek NSString pro Objective-C z Foundation, oba od Applu. Pro ukládání řetězců se mohou také používat složitější struktury např. rope.
Odkazy
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku Null-terminated string na anglické Wikipedii.
- ↑ Chapter 15 - MIPS Assembly Language [online]. Carleton University [cit. 2023-10-09]. Dostupné online.
- ↑ RITCHIE, Dennis M., 1993. The development of the C language. In: Second History of Programming Languages conference. Cambridge, MA: [s.n.], duben 1993. Dostupné online.
- ↑ RITCHIE, Dennis M., 1996. History of Programming Languages. 2. vyd. New York: ACM Press. Dostupné online. ISBN 0-201-89502-1. Kapitola The development of the C language.
- ↑ IBM z/Architecture Principles of Operation
- ↑ KAMP, Poul-Henning. The Most Expensive One-byte Mistake. ACM Queue. 2011-07-25, roč. 9, čís. 7, s. 40–43. Dostupné online. ISSN 1542-7730. DOI 10.1145/2001562.2010365. S2CID 30282393.
- ↑ Rain Forest Puppy. Perl CGI problems. Phrack Magazine. artofhacking.com, 1999-09-09, roč. 9, čís. 55, s. 7. Dostupné online [cit. 2016-01-03].
- ↑ Null byte injection on PHP? [online]. Dostupné online.
- ↑ UTF-8, a transformation format of ISO 10646 [online]. [cit. 2013-09-19]. Dostupné online.
- ↑ Unicode/UTF-8-character table [online]. [cit. 2013-09-13]. Dostupné online.
- ↑ KUHN, Markus. UTF-8 and Unicode FAQ [online]. [cit. 2013-09-13]. Dostupné online.