ヌル終端文字列
プログラミングにおいて、ヌル終端文字列（ヌルしゅうたんもじれつ、英語: null-terminated string）とは、文字を配列に格納し、ヌル文字（'\0'、ASCIIコードではNUL）でその終端（番兵）を表した文字列である。C言語等で用いられることからC文字列 (C string) とも言い、ASCIIコードの後にゼロ (zero) があることからASCIIZとも呼ばれる[1]。
ヌル終端文字列の長さは、文字列の先頭から見て最初のヌル文字を発見することでしかわからない。その計算量は文字列長に比列する（O(n)）。また、ヌル文字そのものは文字列に含めることはできず、ヌル文字は終端に1つだけ存在する。
歴史
[編集]ヌル終端文字列は、PDP-11のアセンブリ言語の.ASCIZディレクティブ、および、PDP-10のマクロアセンブリ言語であるMACRO-10のASCIZディレクティブとして導入された。これらはC言語の開発に先行するものであるが、その後は他の形が文字列がよく使われた。
C言語（およびそれから派生した言語）の開発において、メモリは非常に限られたものだったため、文字列長を保存するのにオーバーヘッドが1バイトだけで済むのは魅力的であった。その当時よく使われていたのは「Pascal文字列」[2]で、これは、文字列長を先頭に数値で格納していた。この方式ならばヌル文字を文字列に含めることが可能であり、また、文字列長を求めるのが1回のメモリアクセスだけで済む（計算量が O(1) の定数時間になる）。しかし、C言語の開発者であるデニス・リッチーは、既にBCPLで確立していたヌル終端を選択した。これは、文字列のカウントを8ビットまたは9ビットのスロットに格納することで文字列長が制限されるのを避けるためと、カウントを維持する方法は終端を用いる方法よりも、彼の経験上使いやすくなかったためである[3]。
このC言語の設計は、CPUの命令セットの設計に影響を与えた。1970年代から1980年代にかけてのいくつかのCPU（例えばザイログのZ80やDECのVAX）は、文字列長が前に置かれた文字列を取り扱うための命令が存在した。しかし、ヌル終端文字列が主流となったことにより、"Logical String Assist"命令をIBM ES/9000 520に加えるという1992年のIBMの決定に見られるように、CPU設計者はヌル終端文字列を考慮に入れるようになった。
FreeBSDの開発者ポール＝ヘニング・カンプは『ACM Queue』の中で、2バイト（1バイトではない）の文字列長の使用に対するC文字列の勝利を「最も高価な1バイトの間違い(the most expensive one-byte mistake)」と言及している[4]。
実装
[編集]![[icon]](/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wiki_letter_w_cropped.svg){kind=small} | この節の加筆が望まれています。 |
C言語はヌル終端文字列を基本の文字列型として実装している[5]。標準Cライブラリには、ヌル終端文字列を扱うための以下のような多くの関数がある。
- 文字列の長さを求める
- 文字列を他の文字列にコピーする
- 文字列を他の文字列に加える（結合する）
- 指定の文字が文字列中で最初（または最後）に登場する箇所を見付ける
- 文字列中で指定の文字群を含む（または含まない）最初の箇所を見付ける
- 指定の文字列が文字列中で最初に登場する箇所を見付ける
- 2つの文字列を辞書順で比較する
- 文字列を分割する
- 数値や文字列を出力可能な形式に変換する
- 文字列を数値に変換する
- 1バイト文字やマルチバイト文字の文字列とワイド文字の文字列を相互に変換する (C95以降)
制限
[編集]実装が単純であるために、この表現にはエラーとパフォーマンス問題の傾向がある。
ヌル終端文字列は歴史的にコンピュータセキュリティ上の問題を作ってきた[6]。文字列を宣言するときにヌル文字のための領域を割り当て忘れると、最大の長さの文字列を格納したときにヌル文字が隣接したメモリ領域に書かれてしまう。ヌル文字を格納し忘れるのもバグの原因となる。プログラムのテスト時に、以前そのメモリ領域を使った時のヌル文字が偶然残っていると、そのバグを見つけられないことがある。文字列を固定サイズのバッファへコピーする際に、多くのプログラムではバッファのサイズを気にしていない。そして、コピーする文字列がバッファサイズより長いとバッファオーバーランを引き起こす。
文字列にヌル文字 ('\0') を格納できないので、文字列データとバイナリデータは明確に分けておき、それぞれ異なる関数で取り扱う必要がある。
文字列長を求める際の速度の問題は、他の計算量 O(n) の操作と組み合わせて使用することで軽減される。strlcpyの実装はそのようになっている。
文字のエンコード
[編集]ヌル終端文字列では、文字配列中において値が0の要素が番兵として使われるため、値が0となる文字を含まないエンコード方式が必要である。1バイト単位でエンコードする場合は、値が0となるバイトを含んではいけない。
ASCIIでは0x00を、UnicodeではU+0000をヌル文字NULとして定義している[7]ため、ヌル終端文字列にヌル文字をそのまま含むことはできない[8][9][10]。そこで、ヌル文字を含まない、あるいはヌル文字を別の文字または文字シーケンスで代替した、ASCIIやUnicodeのサブセットを使用することがある。いくつかのシステムではUTF-8の代わりに「修正UTF-8」(Modified UTF-8) を使用している。これは、ヌル文字を2つの0でないバイト (0xC0, 0x80) で表現し、ヌル終端文字列に格納できるようにしたものである。これはセキュリティ上のリスクがあるため[要説明]標準のUTF-8の規格外である。C0 80 NUL はセキュリティ確認[要説明]では文字列終端として、実際の使用時[要説明]は文字としてみなされるかもしれない。Javaの文字列クラスStringはヌル終端でなく、長さ情報を別途保持しているため、内部シーケンス中にヌル文字を直接含むことができるが、エンコードを指定してバイト配列からJava文字列を生成する場合[11]や、Java Native InterfaceでJava文字列をC言語のchar型ヌル終端文字列に変換する場合[12]など、修正UTF-8がエンコードとして使用される。
UTF-16はエンコーディングの単位に2バイト（16ビット）の整数値を使用し、上位バイト／下位バイトの両方あるいはいずれかの値が0になり得るので、1バイト（8ビット）単位のヌル終端文字列に格納することができない。しかし、いくつかの言語あるいはライブラリでは、2バイト整数型を要素とする配列を用いて、16ビットのヌル文字で終端することでUTF-16のヌル終端文字列を実装している。この場合、シングルバイト（8ビット）のヌル文字を想定している従来の文字列操作関数は使用することができず、16ビットのヌル終端文字列専用の関数が必要となる。Microsoft Windowsではワイド文字が2バイト文字型として定義され、ワイド文字の配列をUTF-16のヌル終端文字列として扱う。
発展
[編集]C文字列の処理における誤りを減らすために、多くの試みがなされた。その一つの方法が、標準Cライブラリでgetsやstrcpyのような危険な関数を廃止するために導入された、より安全で使いやすいgets_sやstrlcpy/strcpy_s、strdupなどの関数の追加である。他に、安全な呼び出ししか行われないように、C文字列にオブジェクト指向のラッパーを追加する方法もある。
最新のシステムではメモリの使用は懸念がより少ないので、多バイトの文字列長も許容された。文字列長の保持のために使用される領域によるメモリオーバーヘッドが懸念されるような、多くの小さな文字列が多数ある場合でも、ハッシュテーブルを使用することでより少ないメモリで管理できるようになっている。C文字列の後継は、文字列長を格納するための32ビットあるいはそれ以上のサイズの値フィールドを持っている。例えばC++のStandard Template Library (STL) のstd::string[13]、QtのQString、Active Template Library/Microsoft Foundation Class (ATL/MFC) のCString、Core FoundationのCFString、Foundation KitのNSStringなどである。このような、文字列を格納するためのより複雑な構造を、string（ひも）に対してrope（ロープ）と言う。
出典
[編集]- ^ 文字はASCIIだけに限らないことに注意。
- ^ Pascal言語における文字列形式に由来するが、初期のMicrosoft BASICでも使われていた。
- ^ Dennis M. Ritchie (1993). [The development of the C language]. Proc. 2nd History of Programming Languages Conf.
- ^ Kamp, Poul-Henning (25 July 2011), “The Most Expensive One-byte Mistake”, ACM Queue 9 (7), ISSN 1542-7730 2 August 2011閲覧。
- ^ Richie, Dennis (2003年). “The Development of the C Language”. 9 November 2011閲覧。
- ^ Rain Forest Puppy (9 September 1999). “Perl CGI problems”. Phrack Magazine (artofhacking.com) 9 (55): 7 6 January 2012閲覧。.
- ^ U+0000 <Null> (NUL) Unicode Character
- ^ “UTF-8, a transformation format of ISO 10646”. 19 September 2013閲覧。
- ^ “Unicode/UTF-8-character table”. 13 September 2013閲覧。
- ^ Kuhn, Markus. “UTF-8 and Unicode FAQ”. 13 September 2013閲覧。
- ^
java.io.DataInput - ^ Java Native Interface Specification: 4 - JNI Functions
- ^ std::basic_string::length()の計算量オーダーは定数時間と規定されている。basic_string::length - cpprefjp C++日本語リファレンス
