Řetězec zakončený nulou - Null-terminated string

V programování počítače , je nulový ukončovací řetězec je řetězec znaků uložena jako pole obsahující znaky a zakončeny znakem null (charakter s hodnotou nula, tzv NUL v tomto článku). Alternativní názvy jsou řetězec C , který odkazuje na programovací jazyk C a ASCIIZ (i když C může používat jiné kódování než ASCII).

Délka řetězce se zjistí vyhledáním (první) NUL. To může být pomalé, protože to trvá O ( n ) ( lineární čas ) s ohledem na délku řetězce. Znamená to také, že řetězec nemůže obsahovat NUL (v paměti je NUL, ale je za posledním znakem, nikoli „v“ řetězci).

Dějiny

Řetězce zakončené nulou byly vytvořeny .ASCIZsměrnicí sestavovacích jazyků PDP-11 a směrnicí sestavovacího jazyka makra MACRO-10 pro PDP-10 . Ty předcházejí vývoji programovacího jazyka C, ale často byly používány i jiné formy řetězců. ASCIZ

V době, kdy byl vyvinut C (a jazyky, ze kterých byl odvozen), byla paměť extrémně omezená, takže použití pouze jednoho bajtu režie k uložení délky řetězce bylo atraktivní. Jediná populární alternativa v té době, obvykle nazývaná „Pascalův řetězec“ (modernější termín je „ s předponou délky “), používala k uložení délky řetězce úvodní bajt . To umožňuje, aby řetězec obsahoval NUL, a zjistil délku již uloženého řetězce, potřebuje pouze jeden přístup do paměti (O (1) (konstantní) čas ), ale omezenou délku řetězce na 255 znaků (na počítači využívajícím 8bitové bajty) ). Návrhář C Dennis Ritchie se rozhodl dodržovat konvenci nulového ukončení, aby se vyhnul omezení délky řetězce, a protože udržování počtu se podle jeho zkušeností zdálo méně pohodlné než používání terminátoru.

To mělo určitý vliv na návrh sady instrukcí CPU . Některé procesory v sedmdesátých a osmdesátých letech, jako například Zilog Z80 a DEC VAX , měly vyhrazené pokyny pro zpracování řetězců s předponou s délkou. Když však řetězec zakončený nulou získal trakci, návrháři CPU jej začali brát v úvahu, jak je vidět například v rozhodnutí IBM přidat pokyny k „Logical String Assist“ do ES/9000 520 v roce 1992 a pokyny pro vektorové řetězce na IBM Z13 v roce 2015.

Vývojář FreeBSD Poul-Henning Kamp , píšící v ACM Queue , označil vítězství řetězců s nulovým zakončením nad 2bajtovou (nikoli jednobajtovou) délkou za „nejdražší jednobajtovou chybu“ vůbec.

Omezení

I když je tato implementace jednoduchá, byla náchylná k chybám a problémům s výkonem.

Nulové ukončení historicky způsobilo problémy se zabezpečením . NUL vložený do středu řetězce jej neočekávaně zkrátí. Běžnou chybou bylo nepřidělení dalšího místa pro NUL, takže se zapisovalo do sousední paměti. Dalším důvodem bylo nenapsat NUL vůbec, což často nebylo během testování detekováno, protože blok paměti již obsahoval nuly. Kvůli nákladům na hledání délky se mnoho programů neobtěžovalo před kopírováním řetězce do vyrovnávací paměti pevné velikosti , což způsobilo přetečení vyrovnávací paměti, pokud byla příliš dlouhá.

Neschopnost uložit nulu vyžaduje, aby textová a binární data byla odlišná a zpracovávala je různé funkce (přičemž druhá vyžaduje, aby byla zadána také délka dat). To může vést k redundanci kódu a chybám při použití nesprávné funkce.

Problémy s rychlostí při hledání délky lze obvykle zmírnit jejich kombinací s jinou operací, která je stejně O ( n ), jako například v strlcpy. Ne vždy to však má za následek intuitivní API .

Kódování znaků

Řetězce zakončené nulou vyžadují, aby kódování nikde nepoužívalo nulový bajt (0x00), proto není možné uložit všechny možné řetězce ASCII nebo UTF-8 . Je však běžné ukládat podmnožinu ASCII nebo UTF-8-každý znak kromě NUL-do řetězců ukončených nulou. Některé systémy používají " upravený UTF-8 ", který kóduje NUL jako dva nenulové bajty (0xC0, 0x80) a umožňují tak uložení všech možných řetězců. To standard UTF-8 nepovoluje, protože jde o prodloužené kódování a je to považováno za bezpečnostní riziko. Místo toho může být jako konec řetězce použit jiný bajt, například 0xFE nebo 0xFF, které se v UTF-8 nepoužívají.

UTF-16 používá 2bajtová celá čísla a protože každý bajt může být nula (a ve skutečnosti každý druhý bajt je, když reprezentuje text ASCII), nemůže být uložen v bajtovém řetězci s nulovým zakončením. Některé jazyky však implementují řetězec 16bitových znaků UTF-16 ukončených 16bitovou NUL

Vylepšení

Bylo provedeno mnoho pokusů, aby bylo zpracování řetězců C méně náchylné k chybám. Jednou ze strategií je přidat bezpečnější funkce jako strdupa strlcpy, zatímco zastaralé používání nebezpečných funkcí jako je gets. Další možností je přidat objektově orientovaný obal kolem řetězců C, aby bylo možné provádět pouze bezpečná volání. Je však možné volat nebezpečné funkce tak jako tak.

Většina moderních knihoven nahrazuje řetězce C strukturou obsahující hodnotu 32bitové nebo větší délky (mnohem více, než se kdy uvažovalo u řetězců s předponou s délkou) a často přidává další ukazatel, počet odkazů a dokonce NUL, aby se převod zrychlil. zpět na řetězec C. Paměť je nyní mnohem větší, takže pokud je přidání 3 (nebo 16 nebo více) bajtů do každého řetězce skutečným problémem, software bude muset řešit tolik malých řetězců, že nějaký jiný způsob ukládání ušetří ještě více paměti (například může existovat tolik duplikátů, že hashovací tabulka zabere méně paměti). Mezi příklady patří standardní knihovna šablon C ++ , Qt , MFC a implementace založená na C od Core Foundation , stejně jako její sourozenec Objective-C od Foundation , oba od společnosti Apple. Složitější struktury mohou být také použity pro uložení strun, jako je lano . std::string QString CStringCFStringNSString

Viz také

Reference