● [Thoughts][Publish] Magic number 1440 (FAT8 編)

頓挫していた "Magic number 1440 シリーズ" を再開する前に、一言皆様にお詫びしておかなければならないことがあります。2006/11/3 のメモ において、私は古川享氏の記事を引用し、「Microsoft が NEC N88-DISK BAISC で採用されていた FAT を真似た」との表記を行っておりましたが、その後調べ直したところ、この記述は全くの誤りであることが判明しました。

ちなみに、古川氏の表現は「NEC N88-DISC BASIC 用のファイルシステムとして開発されたFATをMS-DOSにも使う」であり、私がこの文章を誤って解釈したことが原因のようです。

どこが誤りであったのか、いくつかの資料からご説明したいと思います。

NEC PC-8000 シリーズ

残念ながら、日本にはパソコン黎明期の歴史を正確に記した書籍が見あたりません。インターネット上に出回っている情報についても、20年以上前の資料はほとんど公開されておらず、調査を進めることはかなり難しい状況にあります。

幸い、我が家の屋根裏部屋に25年以上前の資料が眠っていましたので、先日発掘してみました。右は、発掘品のひとつ。懐かしの、NEC PC-8000 シリーズ ユーザーズ・マニュアル４部作です。左から、PC-8001 (本体)、PC-8821/8822 (ドットインパクトプリンター)、PC-8012 (拡張I/Oユニット)、PC-8031-2W (5.25インチ・ミニディスクユニット)。なぜこれらのマニュアルが、当時貧乏浪人生であった私の手元に残っているのか、定かではありません(１冊千数百円程度で販売されていたような気もしますし、それとも時を経てゴミ箱行きになっていたものを回収したの？＞我)。当時は気づかなかったのですが、今の目で見ると、カバーに登場する男性が左から右に進むにつれ、老けています。身なりや表情もすべてことなり、なかなか芸が細かいですね。

その内容ですが、すべて100ページにも満たない小冊子(A5版)であり、ハードウェア仕様や、サンプルプログラム(もちろんすべてBASIC)、文字コード、制御コード、DISK BASIC 内部仕様などが、それぞれごちゃ混ぜ状態で記載されています。内容的には「分かる人が読めば分かるデータシート」であり、ユーザーズマニュアルと呼ぶには程遠い代物。しかし、当時パソコンの書籍は皆無でしたから、初心者はこの暗号にも等しいマニュアルを片手にBASICプログラムを打ち込み、その結果に一喜一憂したのでした。

ちなみに、PC-8001 の発売は 1979年9月28日 (後の "パソコンの日")のことでした。PC-8001 に関する資料も、やはりネット上には少なく、現在の NEC エレクトロニクスですら「半導体のあゆみ」の中で、寂しく一行で紹介する程度。PC-8001 よりも TK-80 が大きく取り上げられ、さらには μPD765 が "世界初のFDC" として一面トップの写真入りで紹介されているあたりが、社内事情を反映しているのか、なかなか意味深です。PC-8001 で育った世代としては、せめても情報処理学会並みの扱いを御願いしたいものです。

ここで、マイコン・ノスタルジーに浸りたい方は、株式会社イトイが提供されている Time Machine のページがお勧めです。PC-8001 だけでなく、MZ-80をはじめとする数々の名機に再会できます。思わず涙＆合掌。

ところで、MZ-80 とくれば、同機の開発者(中西氏)による「MZ-80 パソコン開発秘話」を忘れてはなりません。コメント欄も含め、とても "熱い" です。PC-8001 版も登場すると嬉しいですが、個人的には本体よりも「PC-8031 開発秘話 ＆ μPD765 IBM-PC採用への道」に、とても興味があります。

NEC PC-8000 システム DISK BASIC

それでは、ようやく本題です。PC-8031-2W のユーザーズ・マニュアルを開いてみましょう。

PC-8001 発売当時のマイコンの外部記憶装置は、まだカセットテープが一般的でしたが、この PC-8031 を接続することで、夢の5.25インチ・フロッピィディスクドライブを利用することが可能になりました。PC-8031 は、当時の値段で30万円を超えていましたので、一般ユーザには高嶺の花。フロッピィディスクですら、緑白ツートンカラーの紙箱入りで万単位の値段。当時浪人生だった私は、ショップで１枚だけバラ売りしてもらい、後生大事に使ったことを覚えています。

PC-8031 本体には、緑のジャケットに包まれた "PC-8000 システム DISK BASIC" のシステムディスクが添付されており、同ディスクをディスクドライブに装着し、PC-8001 を起動すると右のようなメッセージが表示されました(ドライブのヘッドロード音がまるでヤカンを叩くが如く、うるさいのです)。

このメッセージを見て、思わず涙腺が緩んでしまう方もいらっしゃるかと思いますが、知ってる人は知っている、懐かしの "How many files (0-15) ?" です。注目すべきは、Copyright notice であり Microsoft と記されています。古川氏が言及されていた N88-DISK BASIC よりも前から、Microsoft 社は NEC に DISK BASIC を提供していたことが分かります。

DISK BAISC トラック・マップ

PC-8031-2W のユーザーズマニュアルには、６ページにおよぶ DISK BASIC のファイル構造が記されています。

PC-8031-2W には両面倍密度ミニフロッピィディスク２台が搭載されており、その物理フォーマットは両面・40 トラック/面・16 セクター/トラック・256 バイト/セクターとなっています。すなわち、フォーマット後の総容量は 320 KiB (256x16x40x2=327680)となります。

注目すべきは、裏面(Surface 1)の第18トラックであり、ここにディレクトリ情報と後述のFAT (File Allocation Table)情報が格納されています。18 トラックの根拠ですが、これはファイル情報へのアクセス頻度を考慮し、ヘッドの移動が最小で済むように中心付近に設定されたのです。

ちなみに、表面のトラック０〜２に位置している DISK code に注目してください。DISK BASIC 拡張部分のコードサイズは全部で 47 セクター、すなわち 12032 バイト。昔は何もかもが "小さかった" のです。

DISK BASIC ディレクトリエントリ

次に、DISK BASIC ディレクトリ・エントリの構造を見てみましょう。右図に示すとおり、1 エントリはわずか 16 バイトから構成されています。ファイル名は６文字、拡張子として３文字、ファイル属性として１バイト、ファイルを格納する "先頭クラスタ番号" に１バイトが割り当てられています(クラスタについては後述)。タイムスタンプやファイルサイズさえ存在しない、極めて原始的なファイルシステムであったことが分かります。

属性には、ASCII形式, 非ASCII形式, 書き込み禁止, Read after write のフラグがあるのみで、ディレクトリファイルは用意されていません。つまり、DISK BASIC のディレクトリ構造はサブディレクトリが存在しない、"フラット" なものでした。先ほどのトラックマップにおいて、ディレクトリデータは合計 12 セクターの領域に格納される決まりになっていましたから、ディスケット1枚には最大で 192 種類のファイルをセーブすることができました(12x256/16)。今となっては子供だましのようなスペックですが、カセットテープ上でのシーケンシャルデータを取り扱うことを考えれば、十二分に先進的であり、DISK BASIC はオフィス業務で大活躍したのです。

参考までに、C言語の構造体でディレクトリ・エントリを記述すると、次のようになります(バイト割り当てのために、GNU C compiler の拡張機能を使用)。

 struct dir_entry {
   char filename[ 6 ];
   char extension[ 3 ];
   unsigned char attr;
   unsigned char cluster;
   char _free_[ 5 ];
  } __attribute__((packed));

FAT8 on DISK BASIC

それでは、いよいよ本題の FAT (File Allocation Table)に踏み込みましょう。

フロッピィディスクの物理フォーマットは大きく、サーフェス・トラック・セクターの３つのパラメータから成り立っています。ディスケット上のデータにアクセスするためには、ヘッド番号・トラック番号・セクター番号の３つを指定する必要がありますが、これはプログラマーにとってなかなか煩雑な作業であるため、サーフェス０・トラック０・セクター１(セクターだけは1から開始)から、サーフェス１・トラック０、サーフェス０・トラック１、サーフェス１・トラック１という順番で、全セクターを一連のインデックス番号で順序づけることが考えられました。

しかしながら、320 KiB という当時の低容量ディスケットであっても、全セクター数は 1280 個(16x40x2)に及ぶため、もしも各セクターに１バイトを割り当てたセクターマップを用意すると、これだけで 1280 バイトの RAM、ディスク上では５セクターも消費することになってしまいます。標準搭載 RAM が 16 KiB であった時代に、このような贅沢は許されませんでした。

そこで、ファイル管理情報の圧縮を目的として、クラスター(cluster)と呼ばれる工夫が導入されたのです。と言っても、難しいことではありません。ファイルの管理単位を１セクターではなく、"８セクター単位" としたのです。これによって、ファイル管理情報は 1/8 で済むようになりました。１クラスターを１バイトで管理するクラスターマップを用意すると、そのサイズは 1280/8 = 160 バイト。丁度１セクターに収まる手頃なサイズです。

この１バイト版クラスターマップが、25年以上経た現在も脈々と受け継がれている FAT のご先祖様です。右図から分かる通り、DISK BASIC はファイルの格納情報をクラスター番号の "一方向性リンク構造" で管理していました。FAT を格納するセクターの先頭 160 バイト (0x00-0x9F)は、対応する 160 個のクラスターのステータス情報を表しています。ディレクトリエントリには、ファイルを格納する先頭クラスター番号が記されていますから、ファイル名が与えられると一意にこの先頭クラスター番号を得ることができます。次に、FAT 内の該当クラスターのステータス情報を参照。この値が 0xC1 から 0xC8 までの範囲にあれば、ファイルデータは当該クラスタ内で終了しており、実際のデータに割り当てられているセクター数は下位４ビットとなります(0xC3 であれば、３セクター使用中)。ファイルシステム上でのファイルサイズはセクター単位であり、バイト単位ではない点に注意してください。今では考えられないような "丼勘定" でした。

該当クラスターのステータス情報が 0x00 から 0x9F の範囲にあれば、ファイルはさらに後続クラスターへと続くことを意味しています。文章では分かりづらいため、仮想コードでまとめておきましょう。read_file は、指定された先頭クラスターからリンク構造を辿りながら、ファイル内の全セクターを読み込むための関数。read_data は、与えられたクラスター番号の先頭セクターから指定セクター数分を読み込むための補助関数です。

 unsigned char fat[ 160 ];
 
 void read_file(int first_cluster) {
   int cluster = first_cluster, stat, sectors;
 
   while (1) {
     stat = (int) fat[ cluster ];
     switch (stat) {
       case 0xC1..0xC8:
         sectors = (int) (fat[ idx ] & 15);
         read_data(cluster, sectors);
         return;
 
       case 0x00..0x9F:
         sectors = 8;
         read_data(cluster, sectors);
         cluster = fat[ cluster ];
         continue;
      }
    }
  }

後で述べるように、その後 MS-DOS に採用された FAT は 12 ビットに拡張され (FAT12)、時代と共に FAT16, FAT32 へと進化していきました。ここに示した１バイト版クラスターマップを持つ DISK BASIC の FAT は、バイトテーブルから構成される、最も原始的なものであり FAT8 と呼んでも良いでしょう。FAT8 の内部仕様は、ネット上ではほとんど見つけることができないため、PC-8031-2W ユーザーズマニュアルに記されたこれらの情報は、ファイルシステムの黎明期を知る上で、とても貴重なものだと思います。

FAT の開発者は誰？

今回ご紹介した PC-8000 DISK BASIC は、私が内部仕様を把握できた資料の中では最古の FAT システムにあたりますが、一体誰が開発したのでしょうか？DISK BASIC のバナーメッセージから、Microsoft 社によることは間違いありませんが、出来れば開発者が誰であったのかを知りたいところです。

Google 様によると、程なくその人は Marc McDonald 氏であることが分かりました。Microsoft Press での著者略歴において、氏が最初の社員であり FAT を設計したことが紹介されていますので、間違いないようです。それでは、最初に誕生した FAT はどのプラットフォームに搭載され、どのような仕様であったのか？

ここからの検索作業は、なかなか大変でした。最近流行りの Wikipedia も、少し踏み込んだ検索では、ほとんど役に立ちません。FAT8 の記述はもちろんありませんし、FAT の歴史に関しては最初に次の一文があるのみです。

 The FAT filesystem was created by Bill Gates and Marc McDonald in 1977
 for managing disks in Microsoft Disk BASIC.

他の検索結果は、この Wikipedia を引用しているものがほとんどであり、金太郎飴状態。ここから先には進めません。検索対象を変え、次に目についたのは Evil-Microsoft timeline に記述された次の一行でした。

 1977: autumn: Gates and Marc McDonald design File Allocation Table (FAT) for NCR Basic

残念ながら一次リンクはつながりませんでしたが、FAT が最初に搭載された歴史的プラットフォームは National Cash Register (NCR) 社のコンピュータだったようです。「う〜〜ん、これよこれ！」と検索をさらに続けます。

しばらくして、超弩級の資料を発見。Roy A. Allan 氏による "A History of the Personal Computer: The People and the Technology" と題する書籍が、ネット上で全文公開されています。著者・出版社による許諾が明示されていない点が心配ですが、この第６章に 1970 年代における Microsoft 社の歴史が克明に刻まれています。サブタイトルにあるように、誰がどのような仕事を成したのかに重点が置かれており、極めて貴重な資料に仕上がっています。Marc McDonald 氏は、この文章中において 1976年、以下の一文で登場します。

 In Apirl 1976, the company hired its first permanent employee, Marc McDonald.
 He began work on what become known as Stand-alone Disk BASIC for the NCR.

確かに、FAT が最初に産声を上げた環境は NCR のコンピュータで間違いないようです。同章を読み進めると、後半で次のような段落が登場します。

 Another important contract from NCR required development of a disk version
 of BASIC for their 8200 terminal. The company assigned Marc McDonald to
 the project who developed a new disk formatting concept that used a File
 Allocation Table (FAT). The FAT controlled the sequence of data stored on
 a disk and improved the performance of disk operations. The company used
 the concept of a file allocation table in Microsoft Stand-alone Disk Basic.
 Also in a Microsoft Operating System project called MIDAS and later in QDOS
 by Time Paterson of Seattle Computer Products.

FAT システムは、NCR 8200 ターミナル (NCR 8250 の資料はこちら)向けの Stand-alone BASIC (PC-8001 のようにスイッチONで起動する BASIC。OS の介在を必要としない)で初めて採用されました。その実績を評価された FAT は、Microsoft 社の Stand-alone DISK BASIC に採用されると共に(PC-8000 DISK BASIC もこの流れを踏むと思われます)、社内で開発中であったOSプロジェクト MIDAS にも取り入れられます。FAT は、当時 QDOS (Quick and Dirty OS: その後 Microsoft 社に買い取られ、MS-DOS に発展)を開発していた Tim Paterson の目にも止まることになり、FAT12 として PC-DOS に組み込まれました。

右上の写真は、1978年当時の Microsoft 社の集合写真。左隅は若き日の Gates 氏、中段右から２番目が FAT の開発者 McDonald 氏です。McDonald 氏は一旦 Microsoft 社を退社した後、現在は復職しています。

終わりに

以上が、現時点で私が把握できている FAT 誕生の状況です。誤りもあるかもしれませんが、お気づきの点がありましたら、私までご連絡頂けましたら幸いです。今後、PC-8000 DISK BASIC が、NCR BASIC や Microsoft Stand-alone Disk BASIC と、海を越えてどのような系譜でつながっているのかが明らかになれば、再度加筆したいと思います。

最後に、右は PC-8031-2W ユーザーズマニュアルの最終ページに登場する標語です。ディスク上には、FAT のコピーが３セクターに渡り記録されています。ディスケット挿入後に、MOUNT コマンドを実行すると、これらの FAT 情報がメモリー上に読み込まれ、ファイル操作は同メモリ内容を修正しながら行われます。このため、作業終了時には REMOVE コマンドを実行し、ディスク上の FAT 情報をメモリ上の内容で上書きする必要があるのですが、私も含め多くのユーザーは度々 REMOVE を忘れ、涙涙の状況に陥ったものでした(誤って他のディスクに入れ替えた後に、REMOVE を実行すると最悪の状況に・・)。

今となっては笑い話のような世界ですが、システムは単純であり、誰もが内部に踏み込み、探検を行うことが出来た時代です。ソースリストはありませんでしたし、GNU 開発環境もありませんでしたが、少年達は逆アセンブルとハンドアセンブルで楽しく青春を費やしたのでした。

FAT8 は仕組みも単純であり、ちょっとした知識さえあれば誰もが簡単に実装できるファイルシステムです。教材としては最適でしょう。Computer Architecture Series では、今後の続刊で FAT が登場する予定です。お楽しみに。