More than 5 years have passed since last update.

JustSystemsAdvent Calendar 2017

@hironiwasm(廣庭雅一)in

株式会社ジャストシステム

「文字列の終端はなぜヌルなのか」を考察する

Last updated at 2017-12-24Posted at 2017-12-24

Advent Calendarの最終日に寄せて（?）、終端文字の話をします。

文字列の終端文字について

終端がヌルの文字列、いわゆる ヌル終端文字列 ですが、終端文字がヌル文字（'\0'）なのは何故でしょうか。
他の文字でも良かったんじゃないの？と考えたことはありませんか。

文字列の持ち方

そもそも、文字列の持ち方には、初期のコンピュータでは主に2種類の方式がありました（今はもっといろいろあると思いますが）。

'\0'で終わる文字列、すなわちヌル終端文字列で、 **ASCIIZ** あるいは『 **C文字列** 』と呼ばれる
先頭に文字列長を1バイトで配置する文字列で、『 **Pascal文字列** 』とよばれる

です。

"Hello,"というリテラルを例にとると、
C文字列では


H	e	l	l	o	,	\0

Pascal文字列では


6	H	e	l	l	o	,
となります。

それぞれの方式には、一長一短があります。

文字列長の取得

C文字列は、先頭から1文字ずつ見ていく必要があり計算量は文字列の長さに比例してO(n)だが、文字列長には制限がない。
Pascal文字列では、先頭1バイトだけ見れば良いので計算量はO(1)で済むが、文字列長は1バイトで表現可能な255文字までに制限される。

文字列の連結

"Hello,"+"World."を例に取ると、
（連結した文字列を格納するメモリ領域の確保は同じ手間がかかるとして）
C文字列は文字列を続けて書き込むだけで済む。


H	e	l	l	o	,	\0
と


W	o	r	l	d	.	\0
から

|||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|H|e|l|l|o|,|W|o|r|l|d|.|\n|

Pascal文字列では文字列を続けて書き込んだ上で先頭の文字列長を書き換える必要がある。


6	H	e	l	l	o	,
と


6	W	o	r	l	d	.
から

||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|12|H|e|l|l|o|,|W|o|r|l|d|.|

C文字列とPascal文字列のどちらが優れているかを断言することは難しいと思いますが、UNIXという優れたOSと一心同体であることとハードウェアの性能をフルに引き出しやすいC言語が普及し、結果としてC文字列の方がより広い範囲で使われるようになったのは事実だと思います。

終端文字になぜヌル文字を選んだか

ヌル終端文字列の起源は、 PDP-11 （DECが1970年に販売開始した"ミニ"コンピュータ。ミニというのは汎用の大型コンピュータに対する相対サイズのことで、今となっては十分デカい）のマクロアセンブリ言語であるMACRO-10の仕様に .ASCIZディレクティブとして導入されたこととされているようです（ヌル終端文字列）。

では、なぜ MACRO-10 の設計者は .ASCIZディレクティブを定義する際に終端文字に'\0'を選択したのでしょうか。これは、PDP-11の命令セットアーキテクチャから見ると、ごく合理的な選択であったことを明らかにしたいと思います。

PDP-11のアセンブリソースを読む

PDP-11の命令セットアーキテクチャを見るには、PDP-11のアセンブリ言語で書かれたソースを読むのが一番ということで、さっそく見てみましょう。

PDP-11よりソースコードを引用させていただきました。

        .TITLE  HELLO WORLD
        .MCALL  .TTYOUT,.EXIT
HELLO:: MOV     #MSG,R1 ;STARTING ADDRESS OF STRING
1$:     MOVB    (R1)+,R0 ;FETCH NEXT CHARACTER
        BEQ     DONE    ;IF ZERO, EXIT LOOP
        .TTYOUT         ;OTHERWISE PRINT IT
        BR      1$      ;REPEAT LOOP
DONE:   .EXIT

MSG:    .ASCIZ /Hello, world!/
        .END    HELLO

この当時のコンピュータとしては、驚くほど読みやすい、きれいなアセンブリ言語仕様です。行きがかり上、PDP-11の前身の PDP-8 （1965年製造開始）のアセンブリ言語仕様も見てみたのですが、命令の種類とメモリアクセス方法がまだ整理されておらず、読んでいてつらいです。アポロ誘導コンピュータ（アポロ11号）のアセンブリ言語も同様です。1960年代半ばまでは、こんなものだったのでしょう。
それがPDP-11では大きく改善されており、その直交性の高い命令セットにより、ほとんど現在のCPUのアセンブリ言語と同じ感覚で読むことができます。

MOV #MSG,R1　により"MSG"というラベル付けしたアドレスをR1レジスタに代入する
（ループ開始）
MOVB (R1)+,R0　によりR1レジスタが指すアドレスから1バイト読み込んでR0レジスタに代入する　（同時にR1はインクリメンされる）　MOV(B)インストラクションの仕様として、読み込んだ値が0なら演算の結果としてZフラグが立つ
BEQ DONE　により、Zフラグが立っていたら"DONE"ラベルまでジャンプ（条件分岐）して終了する（ループから抜ける）
.TTYOUTディレクティブ　によりR0レジスタの文字が出力される
BR 1\$　により1$ラベルまでジャンプする（ループの先頭に戻る）

上のループで使われている

演算の結果を ステータスレジスタ に出力する（ここでは、ゼロなら汎用レジスタの中のZフラグを立てる）
ステータスレジスタの状態により条件分岐する（ここでは、Zフラグの状態によりジャンプする）
という動作は、CPU共通の基本設計であり、インテル系（ x86 ）やモトローラ系、日本製の H-8 （ルネサスエレクトロニクス）、今をときめく ARM 系のCPUでも同様です。

ここで大事なのは、初期のコンピュータの貧弱な処理能力では、少しでも処理を軽くする必要性に迫られていたと言うことです。
PDP-11の MOV(B) では、所定アドレスの値をレジスタに読み込むだけで値がゼロかそれ以外かを判別できています（ PDP-11命令一覧表）。つまり、0という値を特別な値とすることにより 「特定の数値と比較する」というステップ（処理）を省略できているところがポイント です。

CPUの命令とサイクル

初期の貧弱なコンピュータでプログラムを書いていたアセンブラプログラマは、命令を実行するのに必要なサイクル数を数えながらプログラミングをしていました。
例えば、条件分岐を行うには、

アキュムレータ というCPUの中でも特別なレジスタに値を読み込んでから、
数値との比較なり論理演算を行ってステータスレジスタを更新し、
条件分岐命令を実行します。
この単純な流れであっても、サイクル数を削るのに心を砕くのです。

私は、アセンブラに関しては、NECの PC-6001 （1981年発売）に採用されている Z-80 （ザイログ社開発の8bit CPU）が母語ですので、この事情をZ-80アセンブラで説明します。
Z-80は、8bitレジスタはA,B,C,D,E,H,Lの7本です（正確には、補助レジスタ（裏レジスタとも言う）があります）。このうち、論理演算や数値演算に使えるアキュムレータは、Aレジスタです。
『高級』言語によるプログラミングしか経験がないプログラマは、レジスタが変数に相当すると思ってください（そのうち式に書けるのは1個だけ）。想像を絶する窮屈さですね。

さて、ある領域の値をシーケンシャルにAレジスタに読ませて処理を実行して行くには、

16ビットレジスタにアドレスを設定してAレジスタに読ませ、
なにがしかの処理を実行し、
16ビットレジスタをインクリメント
していくことになります。
Aレジスタに16ビットレジスタの値を読み込ませるには、次の命令があります。
それぞれの命令には、サイクル数も添えます。
参照資料 8ビット CPU Z80命令セット

LD A,(HL)    ;サイクル数 7　（BC,DEも同様）
LD A,(IX+d)  ;サイクル数 19　（IYも同様）

CPUが命令を実行する時間は、CPUのクロック数とこのサイクル数で決まります（厳密には、割り込みなども発生するのでそう単純ではありませんが）。ざっくり言うと、サイクル数が2倍なら命令を実行する時間も2倍になります。
サイクル数が大きいIXやIYでオフセット値dを利用するのは、各種変数のプール領域とでも言うべきワーク領域を参照する場合に限られます。

次に、Aレジスタの値を判定する方法には、次の命令があります。

LD r,n   ;サイクル数 7　rは任意のレジスタ、nは任意の1バイトの値
CP r     ;サイクル数 4　rは任意のレジスタ
         ;合計サイクル数 11

CP n     ;サイクル数 7　nは任意の1バイトの値

1つめの方法は、上述したようにZ-80には8bitレジスタは7本しかないのでrの土地代は高く、rにn（ここでは0）を読み込む時間も余分にかかるので採用はしないでしょう。
従って、CP n とするしか方法がないように思えます。
しかし、判定したいバイト値が0である場合に限定して、

OR A     ;サイクル数 4

という、アキュムレータ自身で論理演算を行ってステータスレジスタを更新するというテクニックが使えるのです。
余分なレジスタを使う必要はなく、CP n よりも速く判定ができる、合理的な方法と言えます。
Z-80以外のCPUも、同じようなテクニックがあるのではないでしょうか。
私が現役Z80プログラマのときは、ヌル文字に限らず0判定の常套句として書いていました。
「値がゼロであることの判定」は、「値が特定の数値であることの判定」よりも軽い。
CPUの命令セットアーキテクチャにとって ゼロは特別な値 なのです。

さて、上のPDP-11のサンプルソースを、Z-80アセンブラで書くと、次のようになると思います。

;TTYOUTというサブルーチンが事前に定義されている前提

HELLO:  LD HL,MSG   ;文字列の開始位置をセット
LOOP:   LD A,(HL)   ;バイト値をAレジスタに読み込む
        INC HL      ;1バイト次へ
        OR A        ;0であることを判定
        JR Z,DONE   ;0ならループを抜ける
        CALL TTYOUT ;Aレジスタの内容を出力
        JR LOOP     ;ループ
DONE:   RET         ;HELLOの呼び出し元に返る

MSG:    DB 'Hello, world!',00H

C言語とPDP-11

ここまで、PDP-11が終端文字にヌルを採用したことの合理性を書いてきました。
「そして、PDP-11の.ASCIZは、C言語のC文字列として継承されたのでした（めでたしめでたし）」と言いたいところですが・・実はそうではないようなのです。
別途、会社の同僚が調べてくれたのですが、Cの前身のB言語の時点で、PDP-11とは関係ないところで終端文字にヌルを採用したようなのです（Bのさらに前身のBCPLでは文字列長を保持していた）。

興味がある人は、
The Development of the C Language
The Most Expensive One-byte Mistake
を読んでみてください。

いろいろ言われているようですが、C文字列の終端文字にヌルを採用したことは、実行速度という観点では悪くない選択だったと思います。

PDP-11だけでなく他のCPU上のアセンブラプログラマが高級言語に移行する際にC言語を支持したのは、システムレイヤーに近いC言語の設計思想に依るところが大きかったと思います（80年代前半までは、C言語は「高級アセンブラ」と呼ばれていた）。
C文字列は、結果的にはC言語のそんな思想にマッチしているのではないでしょうか。