JPH08508358A - リロケート可能なファイルフォーマットのための装置および方法 - Google Patents

Abstract

(57)【要約】 実行可能なオブジェクトコードファイルのリロケーション表エントリは、特定のそれぞれのリロケート可能な情報に対する個々の仕様としてではなくリロケーション命令として解釈される。抽象マシンが設けられ、リロケーション命令を解釈し、リロケーション命令に応答して、抽象マシンのためのさまざまなリロケーション動作およびさまざまな制御機能を実行する。抽象マシンはいくつかのタイプのリロケーション命令に応答して参照されかつ更新される情報を含むいくつかの変数を維持し、それによってそのような情報を各リロケーション命令の一部として含む必要性をなくす。リロケーション命令タイプのいくつかは、ｎ個の連続リロケート可能な情報項目からなるランに対して行なわれるべき特定のリロケーション動作を指定することも可能であり、ｎはリロケーション命令の一部として指定される。これらのリロケーション命令タイプのいくつかはまた、各情報を実行すべき同一のまたは異なったタイプの２つ以上の個々のリロケーションを含むものとして考慮し、したがって効果的にリロケーションのパターンのｎ回の反復からなるランを指定する。他のタイプのリロケーション命令もまた利用可能にされる。ファイルはまたハッシングされたシンボルエクスポート表およびパターン初期化されたデータ拡張命令を含む。

Description

【発明の詳細な説明】 リロケート可能なファイルフォーマットのための 装置および方法 著作権の一部放棄 この特許書類の開示の一部分は、著作権保護が要求されている資料を含む。著 作権所有者は、特許書類または特許開示であって、米国特許商標庁のファイルま たは記録に表われているとおりのものをいかなる者が複写することに対しても異 議は申し立てないが、他のいかなる権利もすべて留保する。 背景 １．発明の分野 この発明は、コンピュータシステムによる実行のための、ソフトウェアのメモ リへのローディングに関し、より特定的には、それを容易にする技術およびファ イルフォーマットに関する。 ２．関連技術の説明 コンピュータプログラムは典型的には、Ｃもしくはパスカルなどのコンピュー タ言語またはアセンブリ言語のソースコードで最初書かれる。コンピュータシス テム上での実行のためのプログラムを準備するために、１つまたはそれ以上のソ ースコードモジュールが、使用される言語およびプログラムが実行されるコンピ ュータにより特定されるコンパイラ（またはアセンブラ）を通され、このコンパ イラ は、オブジェクトコードファイルをその出力として発生する。独立のプログラム またはコンパイラの一部であるリンカルーチンが、それらを結合して、「実行可 能な」オブジェクトコードファイルとして知られている１つの出力ファイルにす る。１以上の実行可能ファイルが、次にローダプログラムによりメモリにともに ロードされ、制御が、プログラム実行を開始するために先頭アドレスに移される 。 実行可能なオブジェクトコードファイルは典型的には、とりわけ、ファイルの 構成についての情報を含むヘッダセクションと、システムのＣＰＵにより直接実 行可能であるバイナリ命令を含む、１以上のコードセクションと、１以上のデー タセクションと、ローダセクションとを含み、その内容を以下で説明する。 データセクションは典型的には、ソースコードに応答してコンパイラにより初 期化されたデータ、さまざまなプロシジャポインタを記述する記述子、およびい くつかの他のタイプのポインタを含む。データセクションに含まれるさまざまな ポインタは、他のデータオブジェクトまたは特定のコンピュータ命令のメモリ内 のアドレスを参照するものを含み得る。たとえば、ポインタは、プロシジャのエ ントリポイントなどの、コードセクションの特定のオブジェクトを参照し得る。 データセクションの他のポインタは、同じデータセクションの他のオブジェクト のアドレスを含み得る。（ここで用いられるように、アドレスは、用いられ るコンピュータシステムによって、実アドレスまたは仮想アドレスのいずれでも よい。）さらに、プログラムが２以上の実行可能なファイルにコンパイルされ、 その後ともにロードされ得るシステムにおいては、１つのファイルのデータセク ションは、別のファイルのコードまたはデータセクションのオブジェクトへのポ インタを含み得る。 絶対アドレスへのこれらの参照のすべては、「リロケート可能」でなければな らない。なぜならコンパイルおよびリンキング時には、コンパイラ／リンカは、 参照されるさまざまなオブジェクトがロードされるメモリの最終的なアドレスが どうなるかを知る方法がないからである。したがって、実行可能なオブジェクト コードファイルにおけるコードセクションのアドレスへの参照は、単にコードセ クションの先頭と相対的な形式でしばしば表わされ、データセクション内のオブ ジェクトへの参照は、単にデータセクションの先頭アドレスと相対的な形式で表 わされる。その結果、参照されたセクションがメモリにロードされ、そのセクシ ョンの先頭アドレスが知られた後に、その先頭アドレスを、そのセクション内の オブジェクトへの参照のすべてに単に加えることにより、ローダプログラムがこ れらの参照のリロケーションを行なうことができるようになる。 外部シンボルへの参照は、典型的には、実行可能なオブジェクトコードファイ ルにおいては、同じくそのファイルに含まれるシンボルインポート／エクスポー ト表へのイン デックスとして表わされる。インポート／エクスポート表の各インポートエント リは、シンボルの１つの名前と、そのシンボルを含むはずである外部ファイルと の両方を特定する。インデックスはしばしば連続的に番号をつけられ、以下から わかるように、表はエクスポートエントリも含む。ローダプログラムは、外部シ ンボルへの参照に出会うと、外部ファイルをロードし、参照されたシンボルのア ドレスを判定する。次にローダプログラムは、参照されたシンボルのアドレスを 加えることにより、参照をリロケートする。 インポートシンボルのアドレスを判定するために、ローダは、一般に名前で、 外部ファイルのシンボルインポート／エクスポート表のエクスポートの中からシ ンボルをサーチする。所望のエクスポートを含むエントリはまた、そのシンボル を含む外部ファイルのセクション番号およびそのセクション内でのオフセットを 指定することにより、シンボルのアドレスを指定する。 実行可能なオブジェクトコードファイルのローダセクションは典型的には、リ ロケート可能な参照の各々がメモリにロードされる時点でいかにリロケートされ るべきかを特定するエントリを含むリロケーション表を含む。たとえば、コード セクション内のオブジェクトへのリロケート可能な参照については、リロケーシ ョン表は、参照に加えられるべき数が、他のセクションの先頭アドレスではなく てコードセクションの先頭アドレスであるという仕様を含む。同 様に、データセクション内に含まれるオブジェクトへのリロケート可能な参照に ついては、リロケーション表は、リロケート可能な参照に加えられるべき数がコ ードセクションの先頭アドレスではなくデータセクションの先頭アドレスである ことを特定するエントリを含む。外部シンボルへのリロケート可能な参照につい ては、リロケーション表は、シンボルインポート表の所望のエントリへのインデ ックスの、対応する仕様を含む。 ローダプログラムは、オペレーションを開始すると、ディスクなどの大容量記 憶装置から、所望の実行可能なオブジェクトコードファイルを取り出す。コンピ ュータシステムが、複数のタスクがオブジェクトコードセクションを共有して同 時に常駐するのを許可する場合、ロードされたファイルを用いる各タスクに対し て、データセクションの別々のコピーが作成される。メモリ編成の１つの例にお いて、ローダは、所望のファイルが別のタスクのためにメモリ内に既にあるかど うかを最初に検査する。ファイルがなければ、ローダは、ファイルのヘッダ、コ ード、データおよびローダセクションを、メモリの、個々のユーザに対して読出 専用である部分にロードする。いずれの場合も、ローダは次に、新しいタスクの ために読出／書込メモリ内にデータセクションのコピーを作成する。 ローダが呼出され、いくつかのファイルまたはモジュールを同時にメモリにロ ードする場合、これらのファイルも、 最初のファイルと同じ態様でメモリにロードされる。外部シンボルへの参照はす べて、各ファイルのシンボルインポート表に、各シンボルがロードされているア ドレスを挿入することにより、この時に解決される。シンボルインポートは再帰 的に解決され得る。すなわち、１つのモジュール（たとえばアプリケーションプ ログラム）が第２のモジュール（たとえばライブラリ）のシンボルを参照する場 合、ローダは、第１のモジュールのシンボルを解決するために復帰する前に、第 ２のモジュールをロードし、すべてのリロケーションを行なうことができる。同 様に、第２のモジュールが第３のモジュールのシンボルを参照する場合、ローダ は、第２のモジュールに戻る前に、第３のモジュールをロードし、すべてのリロ ケーションを行なうことができ、以下同様である。 ファイルのさまざまなセクションがメモリにロードされ、インポートが解決さ れた後、ローダはリロケーションプロセスを行なう。リロケーションプロセスは 、ローダセクションのリロケーション表全体を調べ、現在のファイル内に含まれ るリロケート可能な参照の各々に対して特定されたリロケーション動作を行なう ことにより、行なわれる。 実行可能なオブジェクトコードファイルのための１つの一般的なフォーマット はＸＣＯＦＦとして知られている。ＸＣＯＦＦは、ＩＢＭにおいて発行された以 下の論文、「Ｒ６０００ ＩｎｆｏＥｘｐｌｏｒｅｒ」（ＣＤ−ＲＯ Ｍ、１９９２年）に記載されている。 「ａ．ｏｕｔファイルフォーマット（a.out File Format）」、 「ａ．ｏｕｔファイルのためのオプショナル補助ヘッダ（Optional Auxiliary Header for the a.out File）」、 「ａ．ｏｕｔファイルのためのセクションヘッダ（Section Headers for the a.out File）」、 「ａ．ｏｕｔファイルのための生データセクション（Raw Data Sections for the a.out File）」、 「ａ．ｏｕｔファイルのための特別データセクション（Special Data Section s for the a.out File）」、 「ａ．ｏｕｔファイルのためのリロケーション情報（Relocation Information for the a.out File）」、 「xcoff.h」 「filehdr.h」 「reloc.h」 「scnhdr.h」 「loader.h」 上のすべてを引用によりここに援用する。ＸＣＯＦＦにおいて、ローダセクショ ンは以下の部分を有する。 ヘッダ部 外部シンボルインポート／エクスポート表 リロケーション表 インポートファイルＩｄ ローダストリング表 ローダセクションのヘッダ部は、バージョン番号、およびローダセクションの 残りをナビゲートするのに十分な情報を含む。 外部シンボルインポート／エクスポート表は、ファイルの外部参照の各々に対 して１つの２４バイトエントリを含む。エントリはソートされておらず、エクス ポートと別にインポートをグループ化していることもなく、１つの外部ファイル からのインポートを別の外部ファイルからのインポートとは別にグループ化して いることもない。外部シンボルインポート／エクスポート表の各エントリは、以 下のフィールドを有する。 リロケーション表は、ＸＣＯＦＦファイルのためのリロケーション情報を含む 。リロケーション表の各エントリは、１２バイト長であり、以下のフィールドを 含む。 リロケーション表エントリの１＿ｓｙｍｎｄｘフィールドは、リロケートされ るべき項目が、外部シンボルへの参照であるか、またはコードもしくはデータセ クションの１つの内のオブジェクトへの参照であるかを特定する。特定的には、 １および２の値は、参照が．ｄａｔａまたは．ｂｓｓセクション（その両方が、 ここで用いられる用語としての「データセクション」とみなされる）のオブジェ クトにそれぞれ対することを示し、０の値は、参照が．ｔｅｘｔセクション（コ ード）のオブジェクトに対することを示す。３またはより高い値は、そのファイ ルの外部シンボルインポート表内のインデックスを構成し、情報項目内のリロケ ート可能な参照が、対応する外部シンボルへの参照であることを示す。この場合 、情報項目内のリロケート可能な参照自体は、０、または外部シンボルのアドレ スが加えられるオフセット値を含み得る。リロケーション表エントリが、コード セクションに含まれる情報項目のリロケーションを制御するための能力を有する が、この能力は、相対 分岐をサポートするコンピュータシステム上でほとんど用いられない。これらの システムについては、コンパイラは、コードセクションに対する分岐命令を発生 するとき、典型的には相対分岐フォーマットを用い、リロケーションの必要をな くす。コンパイラは、データオブジエクトを参照する命令を発生するとき、典型 的には、インデックスされたアドレス指定機構を用いるが、この機構のためには 、最終的に実行されるコードに含まれなければならないのは、データセクション のベースアドレスからのオフセットだけである。ソフトウェアは、所望のデータ セクションの先頭アドレスをレジスタにプリロードし、ベースアドレスとして用 いる。さらに、コードセクションが共有可能である場合、コードセクションにお いてもリロケーションが回避される。なぜなら、１つのタスクに適切なリロケー ションが、同じコードセクションを共有している別のタスクに適切なリロケーシ ョンとは同じでないかもしれないからである。 １＿ｒｔｙｐｅフィールドは、行なわれるべきリロケーションのタイプを示し 、一般に、参照がオブジェクトの仮想アドレスへの絶対３２ビット参照であるこ とを示す値を含む。 １＿ｒｓｅｃｎｍは、リロケートされるべき情報項目を含むセクション番号を 示す。１＿ｓｙｍｎｄｘフィールドの場合と同じく、いくつかの予め定義された 値が、．ｔｅｘｔ、．ｄａｔａおよび．ｂｓｓセクションそれぞれへの 暗示的な参照となっている。 ＸＣＯＦＦファイルのインポートファイルＩｄ部は、可変長ストリングを含み 、各々は、外部シンボルインポート／エクスポート表のインポートエントリの１ ＿ｉｆｉｌｅフィールドで順に参照されるインポートファイルのそれぞれのため のファイルＩｄを保持する。同様に、ファイルのローダストリング表部は、可変 長ストリングを含み、各々は、外部シンボルインポート／エクスポート表のイン ポートまたはエクスポートエントリの１＿ｎａｍｅフィールドで参照されるイン ポートおよびエクスポートシンボルのそれぞれ１つのテキスト名を保持する。 ＸＣＯＦＦファイルフォーマットの１つの問題は、それが、大容量記憶装置に おいて占められる空間という点で、起動時のメモリ使用という点で、およびアプ リケーションを起動するのに必要とされる時間という点で、非常に非効率的であ ることである。大容量記憶装置においてＸＣＯＦＦファイルが占める空間は、大 部分は、ＸＣＯＦＦが、データセクションのリロケーションを必要とする各４バ イトワードに対して１２バイトのリロケーション情報を必要とすることに起因す る。したがって、１．５メガバイトを含む実行可能なオブジェクトコードファイ ルにおいて、３００ｋバイトもがリロケーション表により占められるかもしれな い。リロケーション表空間のオーバヘッドも、起動時のメモリの使用が非効率的 である、大きな要因である。起 動時の動作速度が非効率的であるのは、部分的には、行なわれるべきリロケーシ ョンごとに１２バイトを取り出し、解釈する必要があるからである。 ＸＣＯＦＦファイルフォーマットが非効率的であるのはまた、部分的には、外 部シンボルインポート／エクスポート表が組織化されていないからである。これ は、ローダプログラムが、ＸＣＯＦＦファイルによりエクスポートされたシンボ ルをインポートする必要があれば、それが見出されるまで外部シンボルインポー ト／エクスポート表全体をサーチしなければならないことを意味する。いくつか のプログラムでは何百または何千ものエントリがある結果となり得、（そのファ イルからの各インポートごとに１回ずつで）何百回または何千回もサーチされる 必要が生ずるかもしれない。さらに、各サーチは、表のエクスポートのシンボル 名と所望のシンボルインポート名との、長いストリング比較を伴うかもしれない 。 ＸＣＯＦＦローダプログラムは、比較を行なう前に、インポートされたＸＣＯ ＦＦファイルの外部シンボルインポート／エクスポート表全体を、読出／書込メ モリに読込むことにより、このプロセスの速度を上げようとすることもできるが 、これ自体が時間がかかり、広大な量のメモリを必要とする。さらに、ローダス トリング表全体もメモリにロードされる必要があり、仮想メモリコンピュータシ ステムにおいては、外部シンボルインポート／エクスポート表 エントリおよびロードストリング表を交互の態様で繰り返しアクセスする必要が あることにより、ページフォールトが繰り返され、さらに性能が低下する可能性 が強い。さらに、典型的なインポートファイルは、このようにしてメモリに読込 まれるインポートされたファイルによってエクスポートされたシンボルの１０％ しかインポートする必要がないかもしれない。したがって、インポート解決の速 度を上げるためにメモリ内に読込まれた外部シンボルインポート／エクスポート 表およびローダストリング表のエントリの大多数が、全く使用されないかもしれ ない。 ＸＣＯＦＦに加えて、実行可能なオブジェクトコードファイルのための別の従 来のフォーマットが、アタリ ＳＴコンピュータのためのＧＥＭディスクオペレ ーティングシステムにおいて用いられている。ケイ・ピール（K．Peel）の「ア タリ ＳＴ ６８０００プログラマのコンサイスリファレンスガイド（The Conc ise Atari ST 68000 Programmer'ｓ Reference Guide）」（グレントトップ・パ ブリッシャーズ（Glentop Publishers）：１９８６年）の、特にｐｐ．２−２１ ないし２−２４を参照のこと。ピールのガイド全体を引用によりここに援用する 。 ＧＥＭフォーマットにおいては、実行可能なオブジェクトコードファイルのロ ーダセクションは、一連のバイトからなり、その各々は、多くて１つのリロケー ションを特定する。ローダルーチンは、ロードされているプログラムへ のポインタを管理し、ローダセクションの各バイトに依存してポインタを更新す る。具体的には、ローダセクションのバイトが２以上２５５以下の数を含む場合 、ローダルーチンは、その特定された数のバイトだけポインタを進め、先頭プロ グラムアドレスを、そのときポインタにより示されている３２ビットのリロケー ト可能な参照に加える。ローダセクションのバイトが値１を含む場合、ローダル ーチンは、リロケーションを行なわずにポインタを２５４バイト進める。ローダ セクション内のゼロバイトは、リロケーションの終了を示す。 ＧＥＭ形式の実行可能なオブジェクトコードファイルフォーマットおよびロー ダルーチンは、非常に単純であり、先頭プログラムアドレスを３２ビットのリロ ケート可能な参照に加えること以外には、シンボルインポートおよびエクスポー トに対する、別個のコードおよびデータセクションに対する、または他のいかな る種類にも対する、リロケーションについてのいかなる能力も欠いている。さら に、ＸＣＯＦＦフォーマットと同様に、ＧＥＭフォーマットは依然として、行な われるべき各リロケーションごとにリロケーション表エントリ（バイト）を含む 。 発明の概要 この発明は、実行可能なオブジェクトコードファイルのいくつかの特性を利用 して、リロケーションごとに必要とされるリロケーション情報のバイト数を大き く減少させる。 特に、大まかにいえば、実行可能なオブジェクトコードファイル内のリロケーシ ョン表エントリは、特定のそれぞれのリロケート可能な情報項目に対する個々の 仕様ではなく、リロケーション命令として解釈される。リロケーション命令に応 答する抽象マシンが設けられ、この抽象マシンは、リロケーション命令を解釈し 、抽象マシンのためのさまざまな制御機能およびさまざまなリロケーション動作 を行なう。この抽象マシンは、リロケーション命令のいくつかのタイプに応答し て参照されかつ更新される情報を含むいくつかの変数を管理し、それによりその ような情報を各リロケーション命令の一部として含む必要をなくす。リロケーシ ョン命令タイプのあるものはまた、リロケーション命令の一部として特定される ｎ個の一連の連続的なリロケート可能な情報に対して行なわれるべき特定のリロ ケーション動作も特定できる。他のタイプのリロケーション命令も利用可能にさ れる。 この発明の別の局面において、実行可能なオブジェクトコードファイルは、イ ンポートシンボル表とエクスポートシンボル表とを分け、組合わされたストリン グ表において、インポートシンボル名ストリングをインポートシンボル表のより 近くにロケートし、エクスポートシンボル名ストリングをエクスポートシンボル 表のより近くにロケートする。エクスポートシンボル表はまた、ハッシングアル ゴリズムに従ってソートされる。さらに、パターン初期化されたデ ータセクションが、データ拡張命令としてストアされ、オブジェクトファイルの サイズをさらに減少させる。 図面の簡単な説明 この発明をその特定の実施例に関して説明し、図面を参照する。ここで同様の 素子には同様の参照符号が与えられる。 図１は、この発明を組入れたコンピュータシステムの記号的な、簡単なブロッ ク図である。 図２は、この発明を用いるローダプログラムの幅広い機能を示す簡単なフロー チャートである。 図３は、図１のメモリの情報記憶の記号図である。 図４は、図２のＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳステップを詳細に示すフロー チャートである。 図５は、図２のＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳステップを詳細に示 すフローチャートである。 図６は、典型的なコンパイラにより発生されるデータセクションの構成を示す 。 図７Ａ−７Ｇは、抽象マシンにより再編成されるリロケーション命令のための フィールド定義を示す。 図８は、図４のＦＩＮＤ ＮＥＸＴ ＩＭＰＯＲＴ ＳＹＭＢＯＬ ＮＡＭＥ ステップを詳細に示すフローチャートである。 図９は、この発明に従ってファイルを構成するためのプログラムの幅広い機能 を示す簡単なフローチャートである。 図１０は、図９のＣＯＮＶＥＲＴ ＳＹＭＢＯＬＳステップを詳細に示すフロ ーチャートである。 図１１は、図９のＳＯＲＴ ＰＥＦ ＥＸＰＯＲＴ ＳＹＭＢＯＬＳステップ を詳細に示すフローチャートである。 図１２は、図９のＣＯＮＶＥＲＴ ＲＥＬＯＣＡＴＩＯＮＳ ＴＯ ＰＥＦ ＲＥＬＯＣＡＴＩＯＮ ＩＮＳＴＲＵＣＴＩＯＮＳステップを詳細に示すフロー チャートである。 図１３は、図１２のＤＯ ＳＹＭＲ，ＳＹＭＢ，ＬＳＹＭ ＩＮＳＴＲＵＣＴ ＩＯＮＳステップを詳細に示すフローチャートである。 図１４は、図１２のＤＯ ＤＤＡＴＡ，ＣＯＤＥ，ＤＡＴＡ ＩＮＳＴＲＵＣ ＴＩＯＮＳステップを詳細に示すフローチャートである。 図１５は、図１２のＤＯ ＤＥＳＣ ＩＮＳＴＲＵＣＴＩＯＮＳステップを詳 細に示すフローチャートである。 詳細な説明 図１は、この発明が実現されるコンピュータシステムの記号的なブロック図で ある。それは、バス１０４に結合されるＣＰＵ１０２を含む。バス１０４はまた 、メモリ１０６およびディスクドライブ１０８に結合される。多くのタイプのコ ンピュータシステムが用いられ得るが、この実施例において、コンピュータソフ トウェアは一般に、ディスクドライブ１０８上にストアされ、ＣＰＵ１０２によ りバ ス１０４を介して発行されたコマンドに応答して、バス１０４を介してメモリ１ ０６に読込まれる。ＣＰＵ１０２は、多分専用ハードウェアとともに仮想アドレ ス指定をサポートするオペレーティングシステムを実行する。すなわち、ＣＰＵ １０２上で実行しているコンピュータプログラムは、オペレーティングシステム および／または専用ハードウェアが、必要に応じてメモリ１０６からディスクド ライブ１０８におよびディスクドライブ１０８からメモリ１０６にページをスワ ップすることにより、メモリ１０６の物理空間よりはるかに大きいアドレス空間 のメモリアドレスを参照することができる。オペレーティングシステムはまた、 ２つまたはそれ以上のタスクが、並列に、または時分割によって、同一のまたは 異なるソフトウェアの異なるコピーを実行することができるマルチタスキングを サポートする。 ディスクドライブ１０８上にストアされた実行可能なオブジェクトコードファ イルは、ここではコンテナと呼び、ここで説明している実施例の特徴を組入れた ものは、ＰＥＦコンテナと呼ばれる（すなわち、それらは「ＰＥＦ」フォーマッ トに従う）。そのようなファイルはまた、メモリ１０６の異なる部分からまたは 別のリソース（図示せず）から取り出され得る。ＰＥＦコンテナは、１つのソー スコードモジュールからのコンパイラ出力を含むことができ、コンパイラが２以 上のソースコードモジュールを結合することができる場合には、複数個のソース コードモジュール からの出力を含むことができる。完全なプログラムを形成するのには、いくつか の異なるコンテナ（ＰＥＦまたは他の形式）が必要とされることもある。ＰＥＦコンテナ構成全体 各ＰＥＦコンテナは、以下の部分、すなわちコンテナヘッダ、Ｎ個のセクショ ンヘッダ、ストリング表、およびＮ個のセクションデータ部を含む。コンテナヘ ッダは、固定サイズであり、ＰＥＦコンテナの構成についてのグローバルな情報 を含む。コンテナヘッダの厳密な内容はこの発明を理解するのに重要ではないの で、ここで説明しない。 ＰＥＦコンテナのセクションヘッダ部は、Ｎ個の「セクション」の各々のため のセクションヘッダを含む。すべてのＰＥＦセクションは、それが生データを含 むかどうかに関係なく、対応するセクションヘッダを有する。そのようなセクシ ョンは、たとえば、コード、データおよびパターン初期化されたデータ（ｐｉデ ータ）セクションなどのロード可能なセクションと、「ローダ」セクションなど のロード不能なセクションとを含む。セクションの各々は、対応するセクション 番号を有し、これは、セクション０から始まり、ＰＥＦコンテナのセクションヘ ッダ部内のセクションヘッダの順序から導出される。セクション０は典型的には コードセクションであり、セクション１は典型的にはデータセクションであるが 、これは必要条件ではない。 各セクションヘッダは２８バイト長であり、以下の構成 を有する。 セクションヘッダの要素の各々の厳密な意味は、上の表に含まれるものを除き 、また以下に述べる事項を除き、この発明を理解するのに不必要である。すなわ ち、セクション種別は以下のセクションを含む。 ＰＥＦコンテナフォーマットは、従来のＸＣＯＦＦファ イルの．ｂｓｓセクションと同様の、ゼロ初期化データのための特定の領域の種 別を含まない。そうではなく、ゼロ初期化セクションは、０の初期サイズでデー タセクションを特定するだけで、ＰＥＦにおいては達成される。ローダは、実行 サイズを用いて、メモリ内のどのくらいの空間をセクションに割当てるかを決定 し、実行サイズと初期サイズとの間の差を利用して、どのくらいの空間をゼロ初 期化するかを決定する。したがって、０初期サイズのデータセクションにより、 メモリのデータセクション全体がゼロ初期化されることになる。ゼロ初期化デー タセクションがメモリの他のデータセクションのすぐ後に続く必要がないことに 注目されたい。 ＰＥＦコンテナのセクションデータ部は、（ゼロ初期化セクションを除いて） ＰＥＦコンテナのセクションヘッダ部のヘッダの各々に対応する生のセクション データを含む。セクションデータ部のシーケンスは、それらの対応するセクショ ンヘッダのシーケンスと同じである必要はない。コード、データおよびローダセ クションを含むあるセクション内の生データは、８バイト（倍長語）アラインさ れる必要がある。コードセクションについては、生データは実行可能なオブジェ クトコードを含むだけである。データセクションについては、生データはセクシ ョンのための初期化されたデータを含む。ローダセクションについては、生デー タは、以下でより詳細に述べられるような、ローダによ り必要とされる付加的な情報を含む。ローダセクションフォーマット ローダセクションは以下の部分を含む。 ローダセクションヘッダ インポートコンテナＩＤの表 インポートシンボル表 リロケーションヘッダ リロケーション命令 ローダストリング表 エクスポートスロット表 エクスポートチェーン表 エクスポートシンボル表 ローダセクションヘッダ ローダセクションヘッダは、固定サイズを有し、ロ ーダセクションのさまざまな構成要素の構成および相対的な位置についての情報 を与える。ローダセクションヘッダのエントリのほとんどは、次に述べることを 除きこの発明を理解するのに重要ではない。すなわち、ローダセクションヘッダ は、とりわけ、インポートコンテナＩＤの表にあるエントリの数を特定する１つ のエントリと、ローダセクションの「インポートシンボル表」部のエントリの数 を示す１つのエントリと、リロケーションを必要とするＰＥＦコンテナのセクシ ョンの数を示す１つのエントリと、ローダセクションの先頭からリロケーション 命令（リロケーション表）の先頭へのバイトオフセッ トを示す１つのエントリと、ローダストリング表へのオフセットを示す１つのエ ントリと、エクスポートスロット表へのオフセットを示す１つのエントリと、（ エクスポートスロット表の「スロット」の数を示す）「ハッシュスロットカウン ト」と、（インポートの再エクスポートを含む）このオブジェクトファイルから エクスポートされるシンボルの数を示すエントリとを含む。すべての表はゼロベ ースのインデックスを用いる。 インポートコンテナＩＤの表 インポートコンテナＩＤの表は、現在のＰＥＦ コンテナにインポートされるべきシンボルを含み得る各外部コンテナごとにエン トリを含む。そのような外部コンテナは、ＸＣＯＦＦなどの従来のフォーマット に従うことができるが、好ましくは、ＰＥＦコンテナについてここで説明される ものと同じフォーマットに従う。インポートコンテナＩＤの表の各エントリは、 この発明を理解するのに重要ではない他の情報の他に、以下のフィールドを含む 。すなわち、コンテナの名前を示すローダストリング表内のオフセット、特定の 外部コンテナのためのインポートシンボル表に含まれるシンボルの数のカウント 、および特定の外部コンテナのための（現在のファイル内の）インポートシンボ ル表の最初のエントリのゼロベースのインデックスを含む。 インポートシンボル表 インポートシンボル表は、インポートされるべき各外 部シンボルごとに１つのエントリを 含む。各インポートシンボル表エントリは、シンボルクラス識別子と、シンボル の名前を示す、ローダストリング表内のオフセットとを含む。外部コンテナのう ちの所与のものからインポートされるべきシンボルのすべては、インポートシン ボル表内においてともにグループ化されるが、そのグループ内では、それらはい かなる順序で現れることもできる。インポートされるシンボルは、以下のクラス 、すなわち、コード内のアドレス、データ内のアドレス、（ここでは記述子また はプロシジャポインタとも呼ばれる）遷移ベクトルへのポインタ、ＴＯＣシンボ ル、またはリンカ挿入されたグルーシンボルのいずれのクラスでもよい。 リロケーションヘッダ ＰＥＦコンテナのローダセクションのリロケーション ヘッダ部は、リロケートされるべき１つまたはそれ以上の情報項目を含むＰＥＦ コンテナの各ロード可能なセクションごとに１つのエントリを含む。ここで用い られるように、「情報項目」は、１以上のリロケート可能なアドレスフィールド を含む情報の、語、倍長語、またはいかなる他の単位でもよい。各リロケート可 能な情報項目が厳密に１つのリロケート可能なアドレスフィールドからなる従来 のファイルフォーマットとは異なり、ＰＥＦのリロケート可能な情報は、リロケ ーション命令により定義される、いかなる数のリロケート可能なアドレスフィー ルドをも含むことができる。 コードセクション内に含まれる情報項目のリロケーショ ンがＰＥＦコンテナ定義によりサポートされるが、コードセクションは好ましく はロード時リロケーションを全く含まないことに注目されたい。これにより、コ ードセクションがユーザ書込可能メモリの外部にロケートされるのが可能になり 、またコードセクションを共有可能にする。多数のデータセクションがサポート されるが、典型的には１つのデータセクションだけが存在することにも注目され たい。 ＰＥＦコンテナのローダセクションのリロケーションヘッダ部分の各ヘッダは 、以下のフォーマットを有する。 リロケーションヘッダのセクション番号フィールドは、その情報がリロケート されるべきであるロード可能なセクションのセクション番号を特定する。セクシ ョン番号０は、たとえばコードセクションでもよく、セクション番号１は、たと えばデータセクションでもよい。上で述べたように、セクション番号は、ＰＥＦ コンテナの「セクションヘッダ」部分内のそれらのシーケンスに依存して割当ら れる。 また上で述べたように、リロケーションヘッダは典型的にはコードセクションに は含まれない。なぜなら、コードセクションは好ましくはリロケート可能な情報 を含まないからである。さらに、セクション番号−１および−２は、ここでは関 係のない特殊な意味を有し、これらのセクションはリロケーションを含まない。 セクション番号−３は、インポートの再エクスポートを示し、いかなるリロケー ションも含まない。 リロケーション表 ＰＥＦコンテナのローダセクションのリロケーション表は 、リロケーション命令のアレイからなる。ＰＥＦコンテナの所与のセクション内 の情報項目に関するリロケーション命令のすべては、ともにグループ化される。 リロケーション命令は、２または４バイト長であり、上位ビットにオペコードを 含む。命令の残りのフィールドはオペコードに依存し、これ以降説明する。 ローダストリング表 ローダストリング表は、ローダセクションの他の部分に より参照されるストリングのすべてを含む。ストリングは、すべて可変長であり 、インポートおよびエクスポートシンボル名の両方ならびにインポートされたラ イブラリのファイル名を含む。ローダストリング表は、ローダセクションの中央 に、インポートシンボル表およびリロケーション表の後であるが、ローダセクシ ョンのシンボルエクスポート部の前に、ロケートされる。インポートシンボルの すべては、ともにグループ化され、イン ポートシンボル表の近くにロケートされ、エクスポートシンボルのすべては、と もにグループ化され、エクスポートシンボル表の近くにロケートされる。シンボ ルのグループ化および２つのシンボル表に対するそれらのロケーションの双方が 、仮想メモリコンピュータシステムのローディング時の性能を向上させる傾向が ある。なぜならページヒットの可能性が高いからである。 シンボルエクスポート部 ＰＥＦコンテナ編成は、コンテナ形成時に、コンテ ナのエクスポートシンボルをハッシュデータ構造にハッシュする。これにより、 ロード時に、エクスポートされたシンボルが別のコンテナにインポートされるべ きであるときの、エクスポートされたシンボルをサーチする速度がかなり向上す る。ＰＥＦコンテナのローダセクションのシンボルエクスポート部は、エクスポ ートスロット表、エクスポートチェーン表およびエクスポートシンボル表を含む 。 ハッシュデータ構造において、エクスポートスロット表は、データ構造の各ハ ッシュ「スロット」に対してエントリを含む。各エントリは、エントリのインデ ックスに対応するスロットにおかれているエクスポートシンボルの数を示すチェ ーンカウントと、そのスロットのための最初のエクスポートチェーン表エントリ の、エクスポートチェーン表内のインデックスとを含む。 エクスポートチェーン表は、それらのスロットに従って グループ化された各エクスポートシンボルに対してエントリを含む。各エントリ は、エントリのエクスポートシンボルに対するハッシュ語の値を含む。 エクスポートシンボル表は、別のコンテナによりインポートされ得る現在のＰ ＥＦコンテナの各シンボルごとにエントリを含む。これらのエントリは、現在の コンテナのローダストリング表内の、シンボル名を特定するオフセットと、その シンボルを含む現在のＰＥＦコンテナのセクションの番号と、シンボルが見出さ れ得るそのセクション内のオフセットとを含む。 したがって、その名前を与えられたエクスポートシンボルをロケートするため に、ローダプログラムは最初に、予め定義された名−ハッシュ語関数を用いてシ ンボル名に対するハッシュ語値を計算する。それは次に、予め定義されたハッシ ュ語−ハッシュスロット番号関数と、（ローダセクションヘッダから得られる） 所与のコンテナのエクスポートスロット表のサイズとを用いて、エクスポートシ ンボルに対するスロット番号を計算する。それは、ハッシュスロット番号をエク スポートスロット表へのインデックスとして用い、エクスポートスロット表から 、そのスロットのための最初のエクスポートチェーン表エントリのエクスポート チェーン表インデックスおよびチェーンカウントをフェッチする。カウントが有 効である間、エクスポートチェーン表は、以前にフェッチされたエクスポートチ ェーン表 インデックスから始めてサーチされる。ハッシュ語が所望のエクスポートシンボ ルに対して計算されたものと一致するとき、そのハッシュ語のエクスポートチェ ーン表インデックスが、名前が一致する可能性があるエクスポートインデックス 番号を指定している。名前が実際に一致するかどうかを調べるために、ローダプ ログラムは、エクスポートインデックスを、エクスポート名のテキストへのオフ セットを含むエクスポートシンボル表に与え、このテキストが所望のエクスポー トシンボル名と比較される。それが一致すれば、そのインデックスにより特定さ れるエクスポートについての情報が戻される。それ以外のときは、カウントがな おも有効である限り（有効でなければシンボルは見出されないことになる。）、 次のエクスポートインデックスが検査される。 ＰＥＦローダプログラムもまた、そのエクスポートシンボルインデックスが与 えられればエクスポートシンボルをロケートすることが可能である。（ゼロベー スの）インデックスによってエクスポートシンボルに関する情報を見つけるため に、ＰＥＦローダはそのインデックスをエクスポートチェーン表に与え、そのシ ンボルに対するハッシュ語値をフェッチするか、またはそのインデックスをエク スポートシンボル表に与え、その値に関する情報の残りをフェッチする。エクス ポートシンボル表は実名テキストへのポインタを含む。 現在説明されている実施例のエクスポートスロット表およびエクスポートチェ ーン表を構築するための一般的なプロセスは以下のとおりである。 １．エクスポートスロット表のエレメントの数を計算する。これはエクスポート の数に基づくが、所望されるエクスポートスロット表サイズオーバヘッドに依存 して変化し得る。エクスポートスロット表サイズをローダセクションヘッダに書 込む。 ２．各エクスポートについて、名−ハッシュ語関数を使用してそのハッシュ語値 を計算する。次に、ハッシュ語−ハッシュスロット番号関数を使用して、エクス ポートスロット表サイズに基づいてそのエクスポートハッシュスロット値を計算 する。 ３．そのエクスポートをハッシュスロット番号によってソートする。この命令は 同じスロット番号を有するすべてのエクスポートをまとめ、各エクスポートに対 する（ゼロベースの）シンボルインデックスを生成する。エクスポートチェーン 表の各インデックスで、そのエクスポートに対するハッシュ語を書込む。エクス ポートシンボル表の各インデックスで、シンボル表エントリを書込む。 ４．エクスポートスロット表（ステップ１によって与えられたサイズ）を構築す る。この表の各エントリはエクスポートの数およびそのハッシュスロット値があ のハッシュスロットインデックスと衝突する第１のエクスポートのイン デックスを有する。 以下はハッシングプロセスで使用するためのエクスポートスロット表サイズを 計算するための好ましい方法であるが、代わりに他の方法を使用することも可能 である。ハッシュスロット表サイズ関数は、エクスポートの数が与えられれば、 エクスポートスロット表に適切なサイズを計算する。このサイズは常に２のべき 乗であり、したがってこの関数の出力は２のべき乗の数を与えることである。定 数ｋＡｖｄＣｈａｉｎＳｉｚｅは通常５であるが、サイズｖｓ．速度のトレード オフに対する所望に応じて変化し得る。 注：より短いハッシュスロット表から、より長いハッシュスロットチェーンが生 じるが、このペナルティは非常に小さい。なぜなら、データ構造はハッシュスロ ット衝突を考慮するために最適化されるからである。 ローダセクションのエクスポートシンボルに対するハッシュ語を計算するため に使用される好ましい名−ハッシュ語関数は、識別子の長さを上位１６ビットと して符号化し、下位ビットは各バイトごとに以下の動作、つまり現在のハッシュ 値を１ビットローテートさせ、その名前の次のバイトでｘｏｒするという動作を 蓄積することによって構築さ れる。これは以下のように実現される。 ハッシュ語−ハッシュスロット番号関数は、上で計算されたハッシュ値を適切 に小さいインデックス番号に変換する。好ましいスロット関数はやはり上で計算 されたエクスポートスロット表のサイズに基づく。 ｐｉデータセクションフォーマット ｐｉデータセクションの生データはデータ拡張命令のシーケンスとして編成さ れる。各命令は３ビットオペコードと、それに続く５ビットのカウントとからな る第一バイトから始まる。次に、このオペコードに依存して、付加的なカウント および／または生データバイトが続いてもよい。オペコードは以下のとおりであ る。 オペコード０：Ｚｅｒｏ ♯Count このオペコードは１つのカウントパラメータをとる。こ れは現在のデータロケーションから始まる「カウント」数のバイトをクリアする 。 オペコード１：Ｂｌｏｃｋ ♯Count（Ｃｏｕｎｔ数だけの生データバイト ） このオペコードは１つのカウントパラメータおよび「カウント」数の生データ バイトをとる。これは生データバイトをデータロケーションに置くもので、実質 的にはブロックバイト転送を実行する。 オペコード２：Ｒｅｐｅａｔ ♯Count1，＃RCount（Ｃｏｕｎｔ１の数の生 データバイト） このオペコードは２つのカウントパラメータおよびカウント１の数の生データ バイトをとる。これはＣｏｕｎｔ１の数の生データバイトを「ＲＣｏｕｎｔ２」 回だけ繰返す。 オペコード３：ＲｅｐｅａｔＢｌｏｃｋ ♯Count1，＃DCount2，＃RCount3 （生データバイト） このオペコードは３つのカウントパラメータおよびＣｏｕｎｔ１＋ＤＣｏｕｎ ｔ２＊ＲＣｏｕｎｔ３数だけの生データバイトをとる。生データバイトは以下の ように解釈される。最初のＣｏｕｎｔ１数のバイトは「反復パターン」を構成す る。次のＤＣｏｕｎｔ数のバイトは第１の「非反復パート」を構成する。ＲＣｏ ｕｎｔ３数だけの「非反復パート」がある。このオペコードはまず「反復パター ン」を置き、次に１つの「非反復パート」を置く。これが「ＲＣｏｕｎｔ３」回 だけ実行され、各回は同じ「反復パター ン」および新しい「非反復パート」を使用する。最後に、もう１つの「反復パタ ーン」が置かれる。 オペコード４：Ｒｅｐｅａｔ Ｚｅｒｏ ♯Count1，＃DCount2，＃RCount3（ 生データバイト） このオペコードは３つのカウントパラメータおよび「ＤＣｏｕｎｔ２」＊「Ｒ Ｃｏｕｎｔ３」数だけの生データバイトをとる。生データバイトは以下のように 解釈される。「反復パターン」は生データバイトに表わされていない「Ｃｏｕｎ ｔ１」数のバイトから構成される。最初の「ＤＣｏｕｎｔ」数のバイトが第１の 「非反復パート」を構成する。「ＲＣｏｕｎｔ３」数の「非反復パート」がある 。このオペコードはまず「反復パターン」（ゼロ）を置き、次に１つの「非反復 パート」を置く。これが「ＲＣｏｕｎｔ３」回だけ実行され、各回は同じ「反復 パターン」（ゼロ）および新しい「非反復パート」を使用する。最後に、もう１ つの「反復パターン」（ゼロ）が置かれる。 ローダプログラム 図２は本願発明を使用し得るローダプログラムの広い機能を示す単純化された フローチャートである。図に示されたＬＯＡＤ ＣＯＮＴＡＩＮＥＲルーチン２ ０２は以下に説明されるように再帰的である。 ステップ２０４で、ロードされているＰＥＦコンテナ全体がコンテナの源（デ ィスクドライブ１０８、メモリ１０６の別の部分、またはリソース（図示せず） ）からユーザ プログラムによっては書込可能ではないメモリ１０６の部分に移される。もし所 望のコンテナが別のタスクによって前にロードされていてメモリ１０６に既に存 在していれば、このステップ２０４はスキップされる。 図３は、主要ＰＥＦコンテナがアプリケーションプログラムであり、このアプ リケーションプログラムがここでライブラリコンテナと呼ぶ第２のＰＥＦコンテ ナ内にすべてロケートされる外部シンボルへの呼出を含む状況に対するＬＯＡＤ ＣＯＮＴＡＩＮＥＲルーチンを例示するためのメモリアレイ１０６の模式図で ある。図３に示されるように、このアプリケーションプログラムはステップ２０ ４でメモリ１０６の読出専用部分の領域３０２にロードされる。このアプリケー ションプログラムは、（図示されない他のセクションとともに）、メモリ領域３ ０４にロードされるヘッダセクションと、メモリ領域３０６にロードされるコー ドセクションと、メモリ領域３０８にロードされるデータセクションと、メモリ 領域３１０にロードされるローダセクションとを含む。 再び図２を参照して、コンテナがメモリ１０６にロードされた後、ＬＯＡＤ ＣＯＮＴＡＩＮＥＲルーチンはすべてのデータおよびｐｉデータセクションに対 する読出／書込メモリ領域を割当て、それを満たす（ステップ２０６）。図３の 例示については、このステップはデータセクションをメモリ１０６の領域３０８ からメモリ１０６の読出／書 込部の領域３１２にコピーすることを含む。このステップで割当てられる領域は アプリケーションプログラムのヘッダセクション３０４で特定され、割当てられ たメモリ領域にコピーされるか、または他の方法で書込まれるデータはアプリケ ーションプログラムの対応するセクションデータ部分から導出される。 ステップ２０６ではまた、領域［ｉ］表が生成され、現在のコンテナに対して 生成された各領域ｉに対する仮想先頭アドレスを示す。具体的には、現在のコン テナが１つのコードセクションしか含んでいず、かつそれがコンテナのセクショ ンヘッダ部分でセクション０として特定されていると、領域［０］はコードセク ションが置かれた読出専用メモリの仮想アドレスを持つだろう。図３の例では、 領域［０］はメモリ領域３０６の先頭の仮想アドレスを持つ。同様に、コンテナ のセクション１がデータセクションであれは、表エントリ領域［１］は現在のタ スクが使用するためにコピーされたメモリ１０６のデータセクションの仮想アド レスを持つ。図３の例では、領域［１］に対する表エントリは領域３１２のメモ リ１０６の仮想アドレスを持つ。説明したように、複数のコードおよびデータセ クションがサポートされており、いかなる順序でも発生し得る。各々には番号が 与えられ、領域［ｉ］表は各セクションがメモリ１０６内でロケートされる場所 を示す。 再び図２を参照して、領域［ｉ］表が生成された後、外 部シンボルへのすべての参照はステップ２０８で解決され、以下に説明される態 様で解決される。（なおこの実施例では、本願発明の理解には重要ではないが、 ある外部シンボルインポートは、もしそれらが解決される必要がないことを示す フラグを持っていれば、この時点で解決される必要はない。）ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳステップ２０８の結果は、現在のコンテナで参照されるシンボル ｊの各々の仮想アドレスを持つインポート［ｊ］表である。ＲＥＳＯＬＶＥ Ｉ ＭＰＯＲＴＳステップ２０８については以下により詳細に説明する。 インポートが解決された後、ＰＥＦコンテナのローダセクションのリロケーシ ョンヘッダ部に何らかのリロケーションヘッダが存在するかどうかについての決 定がステップ２１２で行なわれる。もし存在しなければ、ユーザプログラムは今 や完全にメモリ１０６にロードされたことになり、ＬＯＡＤ ＣＯＮＴＡＩＮＥ Ｒルーチン２０２は完了する。このときユーザプログラムが実行されてもよい。 ローダセクションのリロケーションヘッダ部が１つ以上のリロケーションヘッダ を含んでいれば、ローダは次のリロケーションヘッダによって示されたセクショ ンに対してＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳステップ２１０を実行する 。上述のように、セクションがリロケートされるシーケンスはＰＥＦコンテナの セクションのシーケンスと同じでなければならないという要件も、セクションは 数字の順でリロ ケートされなければならないという要件もない。現在のリロケーションヘッダで 識別されたセクション内のすべての情報項目についてリロケーションが実行され た後、ステップ２１６でリロケーションヘッダ内のインデックスがインクリメン トされ、ルーチンは決定ステップ２１２に戻って、現在のＰＥＦコンテナのロー ダセクションのリロケーションヘッダ部にさらなるリロケーションヘッダが残っ ているかどうか決定する。このプロセスはそのようなセクションのすべてが処理 されてしまうまで続けられる。 シンボルインポート解決 図４はＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳステップ２０８（図２）を詳細に示す フローチャートである。一般的に説明すると、ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳ ルーチン２０８は、現在のＰＥＦコンテナのローダセクションヘッダのインポー トコンテナＩＤの表のインポートコンテナＩＤのすべてをループする。そのよう なインポートコンテナＩＤの各々について、ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳル ーチン２０８はＬＯＡＤ ＣＯＮＴＡＩＮＥＲルーチンを再帰的に呼出し、参照 されたコンテナをメモリに移し、かつそこで特定されたインポートを再帰的に解 決する。一旦制御が現在のコンテナ（ここでは「インポートしているコンテナ」 と呼ぶ）に対するＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳルーチンに戻れば、このルー チンはインポートしているコンテナのローダセクションのインポートシンボル表 のエント リのすべてを循環する。そのようなエントリの各々に対して、このルーチンは、 一致が見つかるまで、インポートされたシンボルの名前を、最近ロードされたコ ンテナ（ここでは「インポートされコンテナ」と呼ぶ）のエクスポートシンボル 表で特定されたストリングのさまざまな名前と比較する。このような比較はＰＥ Ｆエクスポートシンボル表のハッシングされた編成によって容易にされる。イン ポートされたシンボルの仮想アドレスは、インポートされたコンテナのエクスポ ートシンボル表の対応のエントリから計算され、インポート［ｊ］表にストアさ れる。 したがって、ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳルーチン２０８はステップ４０ ２で始まり、このステップでは、現在のコンテナに対するインポートコンテナＩ Ｄの表に何らかのエントリが残っているかどうかが決定される。もしなければ、 ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳルーチン２０８は終了し、このルーチンからス テップ４０４で抜ける。インポートコンテナＩＤの表にエントリが残っていれば 、次に参照されたコンテナに対して、ステップ４０６で、ＬＯＡＤ ＣＯＮＴＡ ＩＮＥＲルーチンが再帰的に呼出される。前述のように、コンテナはすべてがＰ ＥＦフォーマットに従う必要があるわけではなく、次に指定されたコンテナがＰ ＥＦフォーマットでなければ、ＬＯＡＤ ＣＯＮＴＡＩＮＥＲの代わりに別の適 切なルーチンが呼出される。 制御が現在のコンテナに対するＲＥＳＯＬＶＥ ＩＭＰ ＯＲＴＳルーチン２０８に戻った後、現在のコンテナのローダセクションのロー ダインポートシンボル表が最近ロードされたコンテナからインポートされるべき シンボルを何かさらに含んでいるかどうかが決定される（ステップ４０８）。も しなければ、制御はステップ４０２に戻り、現在のコンテナが何かさらに外部コ ンテナのロードを必要とするかどうかを決定する。 図３の例示では、ＬＯＡＤ ＣＯＮＴＡＩＮＥＲルーチン２０２の再帰的実行 の結果、ライブラリコンテナをメモリ１０６の読出専用部の領域３１４にロード することになる。ライブラリコンテナのコンテナヘッダは領域３１６に置かれ、 コードセクションは領域３１８に置かれ、データセクションは領域３２０に置か れ、ライブラリコンテナのローダセクションは領域３２２に置かれる。データセ クション３２０はまた現在のタスクのためにメモリ１０６の読出／書込部の領域 ３２４にコピーされる。別の領域［ｉ］表がライブラリコンテナのために生成さ れ、以下に説明されるようにライブラリコンテナのリロケーションを実行するた めに使用され、アプリケーションプログラムのための処理が再開された後は、ラ イブラリコンテナからインポートされたシンボルの仮想アドレスを計算するため に使用される。 図４のフローチャートに戻って、最近ロードされたコンテナからインポートさ れるべき付加的なシンボルが残って いると判断された後、ＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳルーチン２０８は最近ロ ードされたコンテナのエクスポートシンボル表の次のインポートシンボル名を（ 現在のコンテナのインポートシンボル表から）見つける（ステップ４１０）。こ れは図８に示された諸ステップによって達成される。 図８を参照して、ステップ４１０は、予め規定された名−ハッシュ語関数を使 用して、所望されるインポートシンボル名に対するハッシュ語値を計算すること によって始まる（ステップ８０２）。ステップ８０４で、このルーチンは予め規 定されたハッシュ語−ハッシュスロット番号関数とともにエクスポートスロット 表のサイズを使用し、インポートシンボルが見つかるはずのエクスポートスロッ ト番号を計算する。ステップ８０６で、このルーチンはエクスポートスロット表 内でのインデックスとしてハッシュスロット番号を使用し、そこからそのスロッ トに対する第１のエクスポートチェーン表エントリのエクスポートチェーン表イ ンデックスおよびチェーンカウントをフェッチする。ステップ８０８で、ルーチ ンは前にフェッチされたインデックスから始まり、最大チェーンカウントによっ て指定されたエントリの数の間エクスポートチェーン表をループする。エクスポ ートチェーン表の各エントリについて、ルーチンはそのエントリに対するハッシ ュ語が所望されるインポートシンボルに対して計算されたものと一致するかどう か判断する（ステップ８１０）。もし一致しなければ、ループは継続する（８０ ８）。もし一致すれば、そのハッシュ語のエクスポートチェーン表インデックス はエクスポートシンボル表に与えられ、ローダストリング表のエクスポート名の テキストに対するオフセットを取得し（ステップ８１２）、対応のローダストリ ング表エントリが所望されるインポートシンボル名と一致するかどうかが判断さ れる（ステップ８１４）。もし一致しなければ、ループは継続し（ステップ８０ ８）、もし一致すれば、エクスポートシンボル表でインポートが発見されたこと になり、ルーチンは呼出元に戻る（ステップ８１６）。 このように、ステップ４１０の終了の結果、最近ロードされたコンテナのエク スポートシンボル表の参照されたエントリへのインデックスが得られる。ステッ プ４１２では、そのエクスポートシンボル表エントリの情報が、インポートされ るべきシンボルの仮想アドレスを計算するために使用され、この仮想アドレスは インポートしているコンテナに対するインポート［ｊ］表にストアされる。特に 、インポートされたシンボルの仮想アドレスは、インポートされたシンボルを含 むインポートされたコンテナのセクションの仮想アドレスと、シンボルがロケー トされるそのセクション内のオフセットとの和として計算される。インポートさ れたシンボルを含むインポートされたコンテナのセクションの仮想アドレスは、 そのインポートされたコンテナに 対する領域［ｉ］表からとられ、ｉおよびオフセットはどちらもインポートされ るべきシンボルに対して特定されたインポートされたコンテナのエクスポートシ ンボル表エントリからとられる。シンボル番号ｊは現在の、つまりインポートし ているコンテナから見たシンボル番号である。 なお、所望されるシンボルに対するエクスポートシンボル表エントリのセクシ ョン番号が特別のセクション番号−２を含んでいれば、仮想アドレスはそのエン トリのオフセットフィールドから直接とられる。セクション番号が（さらなる第 ３のコンテナからライブラリコンテナにインポートされたシンボルの再エクスポ ートを示す）−３であれば、オフセットはライブラリのインポートシンボル表へ のインデックスとして使用される。 現在のシンボルの仮想アドレスが計算され、インポート［ｊ］にストアされた 後、ｊはステップ４１４でインクリメントされ、制御は決定ステップ４０８に戻 り、何かさらなるシンボルが、最近ロードされたコンテナからインポートされる 必要があるかどうか判断される。 参照のリロケート 図５は図２のＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳステップ２１０を詳細 に示すフローチャートである。説明したように、ＰＥＲＦＯＲＭ ＲＥＬＯＣＡ ＴＩＯＮＳルーチンは現在のＰＥＦコンテナのロード可能なセクションｉの各々 に対して、現在のＰＥＦコンテナの連続的なリロ ケーションヘッダで指定されたシーケンスで呼出される。現在のセクション番号 ｉはパラメータとしてＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳルーチンに送ら れる。ＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳルーチン２１０を含むＣ言語プ ロシジャについては付属書類Ａで説明する。 図５を参照して、このルーチンはまずステップ５０２でエラーがあるかどうか チェックし、もしエラーが検出されればアボートする。そのようなエラーには、 ゼロより小さい、または現在のコンテナのセクションの総数より大きいセクショ ン番号の受領が含まれる。また、呼出ルーチンによって与えられたセクション番 号が定数セクションかまたはローダセクションであり、そのいずれもがリロケー ト可能な項目を何も含まないことが含まれ得る。 始めのエラーチェックステップ５０２の後、いくつかの変数がステップ５０４ で初期化される。理解されるように、リロケーション表の個々のエレメントはこ の実施例では従来のリロケーション表のリロケーション表エントリよりずっと高 いレベルで解釈される。この解釈はこの実施例ではもっぱらソフトウェアで、リ ロケーション表のリロケーション命令のデコードおよび実行をシミュレートする ルーチンによって実行される。このように、解釈ソフトウェアは、リロケーショ ン命令を解釈し実行するための「疑似マシン」または「抽象マシン」を形成する 。 したがって、以下の抽象マシン変数がステップ５０４で 初期化される。 ｒｅｌｏｃ 現在のＰＥＦコンテナのローダセクションのリロケーション表 の次のリロケーション命令へのポインタ。ＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯ ＮＳルーチン２１０に送られた現在のセクション番号に対する第１のリロケーシ ョン命令を指すように初期化される。 ｒｌＥｎｄ ＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳルーチン２１０に送 られた現在のセクション番号に対する最後のリロケーション命令後の第１のバイ トへのポインタ。ｒｅｌｏｃに現在のセクションに対するリロケーションヘッダ で指定されたリロケーション命令のバイトの数を加えることによって、その値に 初期化される。 ｒＡｄｄｒ 現在のセクションに対する生データの次の情報へのポインタ。 現在のセクション番号に対するメモリ領域の始めのメモリアドレスに初期化され る。 ｒＳｙｍＩ インポート［ｉ］表の対応のインポートのアドレスにアクセス するために使用されるシンボルインデックス（カウント値）。各新しいセクショ ンごとに値０に 初期化される。 ｃｏｄｅＡ 現在のＰＥＦコンテナのロード可能なセクションの１つの先頭 メモリアドレスへのポインタ。セクション番号０が存在しかつロード可能であれ ば、セクション番号０の先頭メモリアドレスを指すように初期化され、他の態様 では、値０に初期化される。理解されるように、あるリロケーション命令はｃｏ ｄｅＡの値を変更でき、それによってこの変数を参照するリロケーション命令に よる後続のリロケーションに影響を及ぼす。 ｄａｔａＡ 現在のＰＥＦコンテナのロード可能なセクションの別の１つの メモリアドレスへのポインタ。セクション番号１が存在しかつロード可能であれ ば、セクション番号１の先頭メモリアドレスを指すように初期化され、他の態様 では、値０に初期化される。ｃｏｄｅＡの場合のように、あるリロケーション命 令はｄａｔａＡの値を変更でき、それによってこの変数を参照する命令による後 続のリロケーションに影響を及ぼす。 ｒｐｔ 以下に説明される反復命令で使用される カウンタ変数。値０に初期化される。 抽象マシン変数ｃｏｄｅＡおよびｄａｔａＡは、これらの変数に初期デフォル ト値を供給する以外に、コンテナにおいてどのセクションがコードセクションで あり、どのセクションがデータセクションであるかを規定しようとしない。これ らの変数はコンテナのロード可能なセクションのいずれをも指すことができ、リ ロケーション命令を使用することによって所望されるたびに変更可能である。 なお、ｃｏｄｅＡおよびｄａｔａＡはロードされたセクションのメモリアドレ スを指すものとして上では説明しているが、これらはロードされたセクションの メモリアドレスからそのセクションに対するデフォルトアドレスを引いたものに 等しい値をストアすることによってこの動作を行なう。セクションに対するデフ ォルトアドレスは、そのセクションのセクションヘッダの所望のセクションアド レスフィールドから入手される。しかしながら、さまざまなセクションに対する デフォルトアドレスは典型的には０であり、そのためｃｏｄｅＡおよびｄａｔａ Ａ変数によって含まれる値は典型的にはメモリの所望のセクションの先頭アドレ スに等しい。 抽象マシン変数が初期化された後、現在のセクション内に情報に対応する何か （さらなる）リロケーション命令があるかどうか決定される（ステップ５０６） 。この決定はｒｅｌｏｃがｒｌＥｎｄより小さいかどうかテストするこ とによって行なわれる。もしそうでなければ、現在のセクションに対するリロケ ーションは完了し、ＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳルーチン２１０か ら抜ける（ステップ５０８）。 現在のセクションに対してより多くのリロケーション命令が存在すれば、次の リロケーション命令が取出され、変数ｒにコピーされる（ステップ５１０）。（ なお、別の実施例では、リロケーション命令は、実際にそれを後続の参照に対す る変数にコピーすることなく、たとえばその内容をテストするステップの一部と して取出されてもよい。）変数ｒｅｌｏｃはステップ５１２で２バイトだけイン クリメントされる。理解されるように、リロケーション命令の大半は２バイト長 であるが、いくつかは４バイト長である。ステップ５１０で、最初の２バイトの みがｒにコピーされる。ステップ５１０の後、ｒｅｌｏｃは、現在のリロケーシ ョン命令が２バイト長しかない場合には、次のリロケーション命令を指すか、ま たはそれが４バイト長であれば現在のリロケーション命令の第２の半語を指す。 命令フォーマットのすべては上位ビットのオペコードで始まる。図５を参照し て、このオペコードは「スイッチ」ステップ５１４で使用され、現在変数ｒにあ るリロケーション命令のオペコード部分の内容に依存して、複数のルーチンの１ つに制御を渡す。この実施例では、リロケートされるべきすべての情報項目は、 各々が４バイト仮想アドレ スフィールドの形式である、１つ以上のリロケート可能な参照を含むと仮定され 、リロケーションはある指定されたポインタ（メモリの領域の先頭へのポインタ またはインポートから取られたポインタ）の内容をリロケート可能な参照に加え ることによって達成される。 取出されたリロケーション命令内のオペコードによって呼出された特定のルー チンの完了後、制御は決定ステップ５０６に戻り、何かさらなるリロケーション 命令が現在のセクションに与えられたかどうかを判断する。もしそうであれば、 次のリロケーション命令が取出され、ループは継続する。もしそうでなければ、 制御はＰＥＲＦＯＲＭ ＲＥＬＯＣＡＴＩＯＮＳルーチン２１０から抜ける。 リロケーション命令 この実施例のリロケーション命令はオペコードおよび引数としてパックされた オブジェクトである。リロケーション命令の中には抽象マシン自体に対する指令 として作用するものもあれば、あるリロケーションが実行される必要があると命 令するものもあれば、特定のタイプの多くのリロケーションが実行されるべきで あると命令するものもある。異なったタイプの命令に対するさまざまなフィール ド定義は以下のＣ言語ｔｙｐｅｄｅｆで十分に説明される。 話を進める前に、典型的なコンパイラによって生成されるデータセクション６ ００の構造を理解することが有用であろう。このような構造は図６に示される。 データセクション６００の先頭で部分６０２の初期化されたユーザデータがグル ープ分けされる。初期化されたユーザデータ部分６０２に続いて、コンパイラは 典型的には領域６０４の連続的な遷移ベクトル（プロシジャ記述子としても知ら れている）のグループを置く。遷移ベクトルはそれらの遷移ベクトルによって参 照されるプロシジャに対する外部呼出元によって使用される。このように、遷移 ベクトルは特にライブラリのコンパイル時に生成された実行可能なオブジェクト コードファイルで共通である。コンパイラは典型的にはコンパイルされた各プロ シジャに対する遷移ベクトルを生成するが、リロケーションがローダプログラム によって実行されるときまでには、外部呼出元によって決して呼出されないプロ シジャに対する遷移ベクトルは典型的には取り除かれてしまっているだろう。 遷移ベクトルは通常図６にそれぞれフォーマット６０６ および６０８として示される２つのフォーマットのうちの１つで生成される。所 与のコンパイラは典型的には２つのフォーマット６０６または６０８の１つのみ で遷移ベクトルを生成する。フォーマット６０６では、各遷移ベクトルは３つの ４バイト語を含む。第１の語はコードセクションのプロシジャの先頭へのポイン タ６１０であり、第２の語６１２はデータセクション６００に対するＴＯＣの既 知のロケーションへのポインタである。第３の語６１４はめったに使用されず、 本願発明の理解に重要ではない「環境語」を含む。コンパイラによって生成され る際、ポインタ６１０は所望されるプロシジャに対するコードセクション内のオ フセットを含み、ポインタ６１２は通常ＴＯＣの先頭に対するデータセクション ６００内のオフセットを含む。したがって、各遷移ベクトル６０６の第１の語は 、現在のコンテナのコードセクションの先頭アドレスを加えることによって、ロ ーダプログラムによってリロケートされなければならない。これを「コードタイ プのリロケーション」と呼ぶ。同様に、各遷移ベクトル６０６の第２の語は、デ ータセクション、典型的には遷移ベクトル６０６を含む同一のデータセクション ６００の先頭アドレスを加えることによって、ローダプログラムによってリロケ ートされなければならない。これは「データタイプのリロケーション」として知 られている。遷移ベクトル６０６の各々の環境語６１４はリロケートされる必要 はない。 第２のタイプ６０８の遷移ベクトルは、各遷移ベクトルの第３の語が省略され ることを除いては、第１のタイプ６０６の遷移ベクトルと同じである。 遷移ベクトル６０４に続いて、コンパイラは典型的には目次（ＴＯＣ）として も知られているポインタの表をデータセクション６００の部分６１６に置く。Ｔ ＯＣはコードセクションへのポインタ６１８、データセクション６００へのポイ ンタ６２０、およびインポートされることが可能な外部シンボルへのポインタ６ ２２を含む。これらのポインタは典型的には混在されるが、しばしば１つのタイ プのいくつかがまとめられる。コンパイラによって生成される際、コードセクシ ョン内へのポインタはコードセクション内へのオフセットのみを伴い、データセ クションへのポインタはデータセクション内へのオフセットのみを伴う。これら のタイプのポインタ６１８および６２０はしたがってコードタイプのリロケーシ ョンおよびデータタイプのリロケーションをそれぞれ必要とする。外部シンボル へのポインタ６２２は典型的にはコンパイルの完了時に０を含むが、所望される シンボルのアドレスが加えられるようなオフセットを含むことも許される。後者 のアドレスはＲＥＳＯＬＶＥ ＩＭＰＯＲＴＳルーチン２０８によって生成され たインポート［ｉ］表の適切なエントリからとられる（図４）。このタイプのリ ロケーションをここでは「シンボルタイプのリロケーション」と呼ぶ。 まずコードタイプのリロケーションを考えると、従来の実行可能なオブジェク トコードフォーマットでそのようなリロケーションを達成するためのリロケーシ ョン表エントリは、リロケートされるべき各４バイト情報に対して１２バイトの リロケーション情報を必要とすることが理解される。これは部分的には従来のフ ォーマットが以下の情報のすべてが各１２バイトのリロケーション表エントリに 現れることを必要とするという事実のためである。その情報とは、リロケートさ れるべき情報項目を含むセクション番号、リロケートされるべき情報項目のセク ション内のオフセット、その先頭アドレスが情報に加えられなければならないセ クション番号、および情報項目が３２ビット語であることの表示を含む。一方、 この実施例では、この情報の大半は抽象マシン変数の１つに維持されるか、また はリロケーション命令オペコードに当然含まれるかのいずれかである。特に、リ ロケートされるべき情報項目の現在のセクションのオフセットは、リロケートさ れるべき情報項目を含むセクション番号とともに、抽象マシン変数ｒＡｄｄｒに 維持される。同様に、リロケートされるべき情報項目の異なるリロケート可能な アドレスフィールドの数、および各々が３２ビットポインタとして処理されるべ きであるという事実は、リロケーション命令オペコードに当然含まれる。なぜな ら、各リロケーション命令オペコードによって指定されたリロケーションを実行 するために、別々のルーチンが 与えられ得るからである。加えて、メモリ内のその先頭アドレスがリロケート可 能なアドレスフィールドのオフセット値に加えられるべきセクション番号もまた 、リロケーション命令オペコードの多くによって当然に指定される。 さらに、従来の実行可能なオブジェクトコードファイルフォーマットはリロケ ートされるべき各アドレスフィールドに対して１つのリロケーションエントリを 必要とするが、この実施例のローダプログラムは、上述のように、同じタイプの いくつかのリロケーションがしばしばまとめられる（ＴＯＣにおけるように）と いう事実を利用する。つまり、コンパイラはコードセクション内への５つのポイ ンタ６１８を順次発生し、その後データセクション内への４つのポインタ６２０ を発生し、その後外部シンボルへの７つのポインタ６２２を発生し、その後デー タセクションへのさらなるポインタ６２０を発生し、などである。この実施例の ローダプログラムは、リロケーションのタイプ（たとえばコード、データ、シン ボル）、および連続して（つまり１つの「ラン」で）実行するそのようなリロケ ーションの数のカウントを指定するリロケーション命令のクラスを与えることに よってこの特性を利用する。 類似のタイプのリロケーションのランを与えるリロケーション命令の多くは、 図７Ａに示された「ラン」命令フォーマットに従う。このフォーマットでは、上 位３ビットは０１０のオペコードを持ち、次の４ビットは実行するリロ ケーションのタイプを示すサブオペコードを持ち、下位の９ビットはサブオペコ ードによって指定された態様でリロケートされるべき連続する情報項目の数を示 すカウントＣＮＴ９を持つ。 そのようなリロケーション命令タイプの１つはＣＯＤＥであり、これは、ステ ップ５１６（図５）で、抽象マシン変数ｃｏｄｅＡの値を「ＣＮＴ９」個の連続 した情報項目に対するマシン変数ｒＡｄｄｒによって指定された情報項目に加え る。ｒＡｄｄｒはラン中の次の情報項目を指すように、それらのリロケーション の各個々のリロケーションの後４だけインクリメントされる。別のそのようなリ ロケーション命令タイプはＤＡＴＡであり、これは、ステップ５１８で、抽象マ シン変数ｄａｔａＡの値を「ＣＮＴ９」個の連続した４バイト情報項目に対する 抽象マシン変数ｒＡｄｄｒによって指定された情報項目に加える。 別のリロケーション命令タイプ、ＳＹＭＲはシンボルタイプの一連のリロケー ションを行なう。ラン中のシンボルタイプのリロケーションの各々に対して、ｒ Ａｄｄｒによって指定された情報項目は、ラン中のそのようなリロケーション動 作の各々の後、インポート［ｒＳｙｍＩ］からの値を加えることによってリロケ ートされ、ｒＳｙｍＩおよびｒＡｄｄｒはどちらもそれぞれ１および４だけイン クリメントされる。説明したように、ｒＳｙｍＩはセクションを処理する初めに ゼロに初期化される。ＳＹＭＢまたはＬ ＳＹＭ命令（以下に説明する）によって特にリセットされない限り、ｒＳｙｍＩ はセクションが処理されるにつれて単調に増加する。 これらの３つのリロケーションタイプの命令（ＣＯＤＥ、ＤＡＴＡおよびＳＹ ＭＲ）を利用できること自体により、ＴＯＣ内に含まれた情報項目に対して要求 されるリロケーションを実行するために必要とされるリロケーション表情報のバ イトの数を大幅に減らすことが可能である。ＤＥＳＣおよびＤＳＣ２リロケーシ ョン命令タイプはさらに大幅な減少を与えることができる。前述のように、典型 的な実行可能なオブジェクトコードファイルでは、遷移ベクトルのすべては部分 ６０４内にまとめられる（図６）。タイプ６０６の遷移ベクトルについては、各 遷移ベクトルはコードタイプのリロケーションを必要とし、その後データタイプ のリロケーションを必要とし、その後は何もリロケーションは必要ではない。タ イプ６０８の遷移ベクトルについては、各遷移ベクトルはコードタイプのリロケ ーションの後データタイプのリロケーションを必要とする。どちらの場合にも、 従来の実行可能なオブジェクトコードフォーマットは、遷移ベクトルリロケーシ ョンを指定するために２４バイト（２つの１２バイトのリロケーション表エント リ）を必要とした。一方、この実施例では、ここでＤＥＳＣと呼ぶランタイプの リロケーション命令が、タイプ６０６の一連の遷移ベクトルをリロケートするた めに与えられ る。このルーチンはＤＥＳＣステップ５２２（図５）で実施され、このステップ では、、ラン中の各３倍長語情報項目６０６に対して、抽象マシン変数ｃｏｄｅ Ａの値がｒＡｄｄｒによって指し示された語に加えられ、ｒＡｄｄｒは４だけポ ストインクリメントされる。抽象マシン変数ｄａｔａＡの値はその後ｒＡｄｄｒ によって指し示された語に加えられ、ｒＡｄｄｒは再び４だけポストインクリメ ントされる。ｒＡｄｄｒはその後三たび４だけインクリメントされ、環境語６１ ４をスキップする。このプロシジャは指定されたラン中の各情報項目に対して繰 返される。 ＤＳＣ２リロケーション命令タイプは、タイプ６０８の遷移ベクトル上での使 用に適合されることを除いては、ＤＥＳＣリロケーション命令タイプと類似して いる。ＤＳＣ２命令は、ｒＡｄｄｒの３回目のインクリメントの省略を除いては 、ＤＥＳＣルーチン５２２と同一のルーチンによってステップ５２４で処理され る。 したがって、遷移ベクトルの全領域６０４のリロケーションが、単一の２バイ トリロケーション命令に応答して、この実施例のローダプログラムを使用して実 行され得ることが理解される。これは従来のローダプログラムに比べて著しい節 約を与える。 上述のフレームワーク内で、リロケーション命令の数多くのタイプが他のよく 発生するリロケート可能な情報フォーマットが認識されたとき、それらに対する リロケーショ ンを単純にするために開発され得る。たとえば、Ｃ＋＋コンパイラによって初期 化されたユーザデータエリア６０２でしばしば生成される１つのリロケート可能 な情報フォーマットは、１語のリロケートできないデータが続く、データセクシ ョンのオブジェクトへの１語のポインタの形式である。このように、この実施例 では、ＶＴＢＬリロケーション命令タイプが与えられステップ５２６で処理され 、このステップでは抽象マシン変数ｄａｔａＡの値がラン中の各情報項目の第１ の語に加えられ、ラン中の各情報の第２の語は変化しないままにされる。多くの 他の情報フォーマットが他のリロケーション命令タイプによって与えられ得る。 いくつかのリロケーション命令タイプは実際のリロケーション動作を何ら実行 することなく、抽象マシン変数を変更する。たとえば、ＤＥＬＴＡタイプのリロ ケーション命令は単に指定された値をｒＡｄｄｒに加えるだけであり、それによ ってリロケートされるべきでない多くの情報を効果的にスキップする。ＤＥＬＴ Ａ命令のフォーマットは図７Ｂに示され、特に、１０００の４ビット上位オペコ ードを含み、その後１２ビットのＤＥＬＴＡ値Ｂ１２を含む。ＤＥＬＴＡ命令は ステップ５２８（図５）で処理され、このステップでは、抽象マシン変数ｒＡｄ ｄｒの値に単にＢ１２＋１を加えるだけである。 ＣＤＩＳ命令もまた何らリロケーションを実行すること なく、抽象マシン変数の値を変更する。特に、この命令はｃｏｄｅＡ変数に現在 のＰＥＦコンテナのロード可能なセクションのうちの指定された１つの先頭メモ リアドレスをロードする。ＣＤＩＳ命令は図７Ｃのフォーマットに従い、０１１ の上位３ビットオペコードを含み、その後にＣＤＩＳ命令を示す４ビットサブオ ペコードを含み、その後にその先頭アドレスがｃｏｄｅＡにロードされるべきセ クション番号を指定するための９ビットのＩＤＸ９フィールドを含む。ＣＤＩＳ 命令はステップ５３０（図５）で処理され、このステップでは、抽象マシン変数 ｃｏｄｅＡに領域［ＩＤＸ９］のポインタを単にコピーするだけである。 ＣＤＩＳと同じオペコードフォーマットに従う類似の命令は命令ＤＴＩＳであ り、これはステップ５３２（図５）で処理される。ステップ５３２は領域［ＩＤ Ｘ９］の値を単に抽象マシン変数ｄａｔａＡにコピーするだけである。ＣＤＩＳ およびＤＴＩＳ命令は複数のコードおよび／またはデータセクションがコンパイ ルシステムによって生成される場合には非常に有用である。 現在の実施例でサポートされるリロケーション命令タイプのいくつかは、リロ ケーション動作を実行するとともに、さらに抽象マシン変数の１つを変更する。 たとえば、ＤＤＡＴ命令はまずｒＡｄｄｒを指定された数の語（ＤＥＬＴＡに類 似）だけインクリメントし、次に指定された数の連続するデータタイプのリロケ ーション（ＤＡＴＡに類似） を実行する。ＤＤＡＴ命令は図７Ｄに示される、フォーマットに従い、そのフォ ーマットは００の２ビットの上位オペコードを規定し、その後スキップすべき情 報の語の数を示す８ビットのＷ８フィールドを規定し、その後続いて実行すべき データタイプのリロケーションの数を示すＮ６フィールドを規定する。ＤＤＡＴ 命令はステップ５３４（図５）で処理され、まずｒＡｄｄｒをＷ８の値の４倍だ けインクリメントし、その後ｄａｔａＡの値を後続する「Ｎ６」個の情報項目の 各々に加えるルーチンで処理される。ｒＡｄｄｒはそのようなリロケーション動 作の各々の後インクリメントされ、命令が完了したときには、ｒＡｄｄｒはラン の後の次の情報を指し示すようにする。 ＳＹＭＢは抽象マシン変数を変更し、その後リロケーション動作を実行する別 の命令である。ＳＹＭＢ命令は図７Ｃのフォーマットに従い、この命令により抽 象マシンはまずｒＳｙｍＩにＩＤＸ９によって指定された新しいシンボル番号を ロードし、次に（１のランカウントに対するＳＹＭＲ命令と同じように）、イン ポート［ｒＳｙｍＩ］の値をｒＡｄｄｒによって示されたリロケート可能な情報 に加える。ｒＳｙｍＩおよびｒＡｄｄｒはどちらもその後インクリメントされる 。ＳＹＭＢ命令はステップ５３６（図５）で処理される。 ＳＥＣＮ命令は、これも図７Ｃのフォーマットに従うが、その番号がＩＤＸ９ で指定されるセクションへの単一のリ ロケーションを実行する。ステップ５３８（図５）で、ＳＥＣＮ命令を処理する ためのルーチンは単に領域［ＩＤＸ９］の値をｒＡｄｄｒによって示された情報 に加え、ｒＡｄｄｒをインクリメントするだけである。 ＲＰＴ命令は指定された数の連続する情報項目のグループに対して一連のリロ ケーション命令を反復する手段を与えることによって、リロケーション表をさら に簡素化することを可能にする。ＲＰＴ命令は図７Ｅのフォーマットに従い、１ ００１の上位４ビットのオペコードを含み、その後に４ビットの番号１４を含み 、その後に８ビットのＣＮＴ８フィールドを含む。呼出されると、抽象マシンは 最近の「Ｉ４」個のリロケーション命令を「ＣＮＴ８」回繰返す。ＲＰＴ命令は ステップ５４０（図５）で処理され、このステップでは、まず抽象マシン変数ｒ ｐｔをデクリメントし、その値をテストする。ｒｐｔが今回０より小さければ、 ＲＰＴ命令に遭遇したのは今回が初めてであり、ｒｐｔはＣＮＴ８＋１に初期化 される。その後、ｒｐｔの値にかかわらず、抽象マシン変数ｒｅｌｏｃはＩ４に よって指定された半語の数だけデクリメントされ、ルーチンを抜ける。これは抽 象マシンにリロケーション命令の「Ｉ４」個の半語だけ逆戻りさせ、それらを反 復させるという効果を有する。なお、ｒＡｄｄｒはデクリメントされないので、 反復されたリロケーション命令は、（反復された情報項目のグループではなく） リロケートされていない次の情報項 目のグループに対して作用する。もし最初のｒｐｔのデクリメントが上記した抽 象マシン変数を０にすれば、ＲＰＴ命令は完了したと判断され、、ルーチン５４ ０を終了する。 Ｉ４で指定された番号はリロケーション命令の数ではなく半語の数である。し たがって、反復が１つ以上の４バイトリロケーション命令を含むのであれば、Ｉ ４の値はそのような４バイトリロケーション命令の各々に対する追加のカウント を含まなければならない。また、Ｉ４の値は反復すべき半語の数より１だけ小さ い値である（つまり、Ｉ４＝０は１つの半語の反復を指定し、Ｉ４＝１は２つの 半語の反復を指定するなどである）。 ＬＡＢＳ命令は図７Ｆのフォーマットに従う４バイトリロケーション命令であ る。具体的には、上位４ビットは１０１０のオペコードを含み、次の２ビットは ００のサブオペコードを含み、下位２６ビットは値ＯＦＦＳＥＴ２６を有する。 ＬＡＢＳ命令はステップ５２４で処理され、このステップでは、値ＯＦＦＳＥＴ ２６をその情報項目が現在リロケートされているセクションの先頭アドレスに加 え、その結果を抽象マシン変数ｒＡｄｄｒにロードする。このように、ＬＡＢＳ は現在のセクション内の特定の情報項目に対する「ジャンプ」を実行する。ＬＡ ＢＳ命令は４バイト命令であるので、ルーチン５４２はｒｅｌｏｃをさらに２バ イトだけインクリメントすることによって終了する。 ＬＳＹＭ命令もまた０１のサブオペコードを有する図７ Ｆのフォーマットに従う。この命令は新しいシンボル番号をｒＳｙｍＩにセット し、その後ｒＡｄｄｒによって示された情報項目に対してシンボルタイプのリロ ケーションを実行するという機能を果たす。ｒＳｙｍＩおよびｒＡｄｄｒはどち らもその後ポストインクリメントされる。新しいシンボル番号はフィールドＯＦ ＦＳＥＴ２６のＬＳＹＭ命令で指定される。ＬＳＹＭ命令はステップ５４４で処 理される。 ＬＲＰＴ命令は図７Ｇのフォーマットに従い、このフォーマットでは、上位４ ビットは１０１１のオペコードを持ち、次の２ビットは００のサブオペコードを 持ち、次の４ビットはＣＮＴ４値を持ち、最後の２２ビットはＣＮＴ２２値を持 つ。ＬＲＰＴはＲＰＴに類似しているが、より多くの反復カウントを可能にする 。具体的には、ＬＲＰＴステップ５４６が呼出されると、最後の「ＣＮＴ４」個 の２バイトリロケーション命令がＣＮＴ２２で指定された回数繰返される。再び 、ＬＲＰＴは４バイト命令であるので、ステップ５４６は、最後の反復後、ｒｅ ｌｏｃをさらに２バイトだけインクリメントすることによって終了する。 図７Ｇの命令フォーマットもまた、３つの他の４バイトのリロケーション命令 のために使用され、この場合サブオペコードが０１であり、ＣＮＴ４が３つの命 令のうちのいずれが呼出されるべきかを指定する。これら３つの命令は、すべて ＬＳＥＣのステップ５４８（図５）で処理され、Ｌ ＳＥＣＮ（ＳＥＣＮと同じであるが、非常に大きなセクション番号を有する）、 ＬＣＤＩＳ（ＣＤＩＳと同じであるが、非常に大きなセクション番号を有する） 、およびＬＤＴＩＳ（ＤＴＩＳと同じであるが、非常に大きなセクション番号を 有する）である。再び、これらの命令は４バイト命令であるので、ＬＳＥＣのス テップ５４８はｒｅｌｏｃをさらに２バイトだけインクリメントすることによっ て終了する。 ｒｅｌｏｃによって示された現在のリロケーション命令のオペコードが認識さ れなければ、デフォルトステップ５５０がエラーを示し、中断する。ＰＥＦファイルの構成 前述のフォーマットのＰＥＦファイルはコンパイラから直接生成可能である。 その代わりとして、従来のコンパイラを用いて従来のフォーマットの実行可能な ファイルを生成し、変換ツールを用いて従来のフォーマットの実行可能なファイ ルをＰＥＦフォーマットのファイルに変換することができる。ＰＥＦフォーマッ トのファイルを生成するのに用いられ得るプロシジャを示す例として、付属書類 Ｂは、ＸＣＯＦＦフォーマットのファイルから始めてそれを行なう、Ｃ言語プロ グラムである。以降このプログラムについて図９−１５のフローチャートを参照 して概略的に述べるが、付属書類Ｂを参照すればこのプロシジャがより正確に理 解できる。 図９はこのプログラムの全体の流れを示す。初期化ステップ９０２では、ＸＣ ＯＦＦファイルがオープンされ、メモリに読込まれる。さまざまなＸＣＯＦＦセ クションがメモリにロケートされており、それらのアドレスは変数にストアされ ている。 ステップ９０４で、インポートシンボル、エクスポートシンボルおよびインポ ートファイルＩｄがＸＣＯＦＦファイルから抽出され（メモリ内コピー）、ＰＥ Ｆファイルフォーマットで使用される編成に変換される。図１０はシンボル変換 ステップ９０４をより詳細に示すフローチャートである。 図１０を参照すれば、インポートファイルＩｄすべてが最初にＸＣＯＦＦファ イルから抽出される。特定的には、インポートファイルＩｄはすべて、ＸＣＯＦ ＦファイルのローダセクションのインポートファイルＩｄ部における可変長のス トリングとして記載されていることが想起されるだろう。これらストリングの順 序はインポートファイル番号を表わし、ＸＣＯＦＦ外部シンボルインポート／エ クスポート表で参照される。ステップ１００２はしたがって、インポートファイ ルＩｄストリングの各々を新しく生成されたＰＥＦローダストリング表にコピー し、各ストリングのオフセットをＰＥＦローダセクションのインポートコンテナ Ｉｄ部における対応するエントリに書込むことを含む。 ステップ１００４において、ＸＣＯＦＦインポートがＸ ＣＯＦＦ外部シンボルインポート／エクスポート表およびローダストリング表か ら抽出される。これはインポートシンボルを求めてＸＣＯＦＦ外部シンボルイン ポート／エクスポート表全体を検査し、インポートシンボル名をＰＥＦローダス トリング表に書込み、付随するストリングへのオフセットをＰＥＦインポートシ ンボル表に書込むことにより達成される。この検査は各インポートファイル番号 に対し別々に行なわれるため、結果として生じるインポートシンボルはインポー トファイル番号によりグループ化される。 ステップ１００６で、エクスポートシンボルがＸＣＯＦＦファイルから抽出さ れる。特定的には、ＸＣＯＦＦ外部シンボルインポート／エクスポート表および ローダストリング表がエクスポートシンボルを求めて検査され、このようなエク スポートシンボル各々に対し、シンボル名がＰＥＦローダストリング表に書込ま れ、付随するオフセットがＰＥＦエクスポートシンボル表に書込まれる。この時 点でこのルーチンはまたエクスポートシンボルに対してハッシュ値を計算し、そ れをエクスポートチェーン表の対応するエントリに書込む。この検査は異なるＰ ＥＦセクション番号に対し別々にかつシーケンシャルに行なわれ、したがってエ クスポートシンボルのリストはＰＥＦセクション番号によりグループ化される。 ステップ１００８で、シンボル変換ルーチン９０４は呼出元に戻る。 図９に戻れば、ステップ９０６において、このプログラムは図１１でより詳細 に説明するようにＰＥＦエクスポートシンボルをソートする。図１１で示される ように、ステップ１１０２において、このルーチンは最初に、ＸＣＯＦＦ外部シ ンボルインポート／エクスポート表に含まれるエクスポートの数を与えられて、 エクスポートスロット表の大きさを計算する。ステップ１１０４で、このプロシ ジャはエクスポートシンボルすべてをループする。各エクスポートシンボルに対 し、このプロシジャはエクスポートスロット表の大きさを与えられてそのハッシ ュスロット値を計算する。このシンボルはそのハッシュスロット値に対するリン クトリストに加えられる。エクスポートスロット表は、そのスロットに対するリ ンクトリストを一時的に示す各エントリのチェーンインデックスフィールドを伴 い、このプロセスにおいて生成される。 ステップ１１０６で、予め定められた数ｍよりも多くのスロットが、予め定め られた数ｎよりも多くのエクスポートシンボルを含むかどうかが判断される。も しそうであれば、エクスポートスロット表は小さすぎる。ステップ１１０８でエ クスポートスロット表の大きさを倍にし、ステップ１１０４が繰返される。エク スポートスロット表が小さすぎなければ、エクスポートチェーン表およびエクス ポートシンボル表がリンクトリストから生成される。特定的には、エクスポート スロット表の各スロットに対し、そのス ロットに対するリンクトリストが調べられこれら２つの表を生成する。エクスポ ートスロット表におけるスロットに対するチェーンインデックスフィールドは、 エクスポートチェーン表への正しいインデックスを用いて上書きされる。このプ ロシジャは次に呼出元に戻る（ステップ１１１２）。 ＰＥＦエクスポートシンボルがソートされた後（図９）、ＸＣＯＦＦファイル におけるリロケーションはＰＥＦフォーマットに変換される（ステップ９０８） 。図１２は、このタスクを達成するプロシジャを示す。 図１２を参照すれば、ステップ１２０２で、ＰＥＦファイルのコードおよびデ ータセクションがデフォルト番号を有するかどうかが判断される。そうでなけれ ば、ＣｏｄｅＡおよび／またはＤａｔａＡ抽象マシン変数をセットするために、 ＣＤＩＳおよび／またはＤＴＩＳ命令が「吐出される」。「吐出す」ステップを 以下に説明する。 ステップ１２０４で、このルーチンはＸＣＯＦＦリロケーション表エントリす べてをループすること開始する。ステップ１２０６で、リロケーション表の現在 のエントリがインポートシンボルリロケーションであるかどうかが判断される。 もしそうであれは、適切なＳＹＭＲ、ＳＹＭＢまたはＬＳＹＭ命令が吐出され（ ステップ１２０８）、制御はルーピングステップ１２０４に戻る。ステップ１２ １０で、このルーチンはデータセクションにおける連続する長語に対し同じリロ ケーションタイプ（コードまたはデー タ）を指示する、リロケーション表における連続するエントリの数をカウントす る。もしこのカウントが１よりも大きければ、ＤＤＡＴ、ＣＯＤＥまたはＤＡＴ Ａ命令が必要なものとして叶出され（ステップ１２１２）、制御はルーピングス テップ１２０４に戻る。 もしステップ１２１０からのランカウントが≦１であれば、ステップ１２１４ で、データセクションにおける３つの連続する長語に対し、コードタイプリロケ ーション、データタイプリロケーション、次にリロケーションなしを指示する、 リロケーション表におけるエントリの連続する対についてのランカウントが新し く作られる。もしこのランカウントが≧１であれば、ＤＥＳＣ命令が吐出され（ ステップ１２１６）、制御はルーピングステップ１２０４に戻る。 もしステップ１２１４からのランカウントが１よりも小さければ、データセク ションにおける２つの連続する長語に対し、データタイプリロケーションが後に 続くコードタイプリロケーションを指示する、リロケーション表におけるエント リの連続する対についてランカウントが新しく作られる（ステップ１２１８）。 もしこのランカウントが≧１であれば、ＤＳＣ２ ＰＥＦ命令が吐出され、（ス テップ１２２０）制御はルーピングステップ１２０４に戻る。 もしステップ１２１８のランカウントが１よりも小さければ、ステップ１２２ ２で、データセクションにおける２ つの連続する長語に対し、後にリロケーションが続かないデータタイプリロケー ションを指示する、連続するリロケーション表エントリについての、ランカウン トが新たに作られる。もしこのランカウントが≧１であれば、ＶＴＢＬ命令が適 切なものとして吐出され（ステップ１２２４）、制御はルーピングステップ１２ ０４に戻る。 もし上記のテストがうまくいかなければ、リロケーション表のエントリはデー タタイプリロケーションだけまたはコードタイプリロケーションだけを特定する 。ステップ１２２６で、このルーチンはしたがってＤＤＡＴ、ＣＯＤＥまたはＤ ＡＴＡ命令を適切なものとして吐出し、制御はルーピングステップ１２０４に戻 る。 リロケーション表のエントリすべてが検査されＰＥＦリロケーション命令に変 換されると、このルーチン９０８は呼出元に戻る（ステップ１２２８）。 図１３は、ＳＹＭＲ、ＳＹＭＢおよびＬＳＹＭ命令を行なうルーチン１２０８ を示す。ステップ１３０２で、連続するＰＥＦインポートシンボル番号に対する 、リロケーション表における連続するインポートシンボルリロケーションについ てのランカウントが作られる。ＰＥＦ ＳＹＭＲ／ＳＹＭＢ／ＬＳＹＭリロケー ション命令を利用するためには、これらインポートシンボルリロケーションは、 ＰＥＦフォーマットへの変換（ステップ９０４）の前ではなく変換後に番号が付 けられた、連続するインポートシンボル に対するものでなければならないことに注目されたい。 ステップ１３０４で、このランに対しリロケートされる最初の長語と、先行す るＰＥＦ命令に対しリロケートされる最後の長語との間のデルタが決定される。 もしこのデルタが０よりも大きければ、ＤＥＬＴＡ命令が、またはもし必要であ ればＬＡＢＳ命令が吐出される（ステップ１３０６）。次に、もしランカウント が１よりも大きければ（ステップ１３０８）、１つまたはそれ以上のＳＹＭＲ命 令が吐出され（ステップ１３１０）、このルーチンは呼出元に戻る（ステップ１ ３１２）。もしランカウントが、ＳＹＭＲ命令のランカウントフィールドにおい て表わすことが可能な最大ランカウントよりも大きければ、２つ以上のＳＹＭＲ 命令を発行することができる。 ランカウントが１に等しければ（ステップ１３０８）、好ましい順で、ＳＹＭ Ｒ、ＳＹＭＢまたはＬＳＹＭ命令のいずれかが発行され（ステップ１３１４）。 このルーチンは呼出元に戻る（ステップ１３１２）。 図１４は、ＤＤＡＴ、ＣＯＤＥ、およびＤＡＴＡ命令を行なうプロシジャにつ いて説明する（１２１２、図１２）。このプロシジャはステップ１２２６（図１ ２）で再び用いられる。図１４を参照すれば、エントリのランがデータタイプリ ロケーションのランであるかどうかについて最初に判断される（ステップ１４０ ２）。もしそうであれは、多分ＤＥＬＴＡ命令に続くＤＤＡＴ命令が、うまくラ ンを表 わすことができるかどうかが判断される（ステップ１４０４）。ＤＤＡＴ命令に おいて表わすことが可能な最大ランカウントがデータアラインメント要求として ここで考慮される。もしこのような命令が適切であればこれらの命令が吐出され （ステップ１４０６）、このプロシジャは呼出元に戻る（ステップ１４０８）。 もしＤＥＬＴＡ／ＤＤＡＴ命令が正確にランを表さなければ（ステップ１４０ ４）、またはこのランがコードタイプリロケーションのランであれば（ステップ １４０２）、ステップ１４１０で、ＣＯＤＥまたはＤＡＴＡ命令が必要なものと して吐出される。ステップ１４１０の前に、ＤＥＬＴＡまたはＬＡＢＳ命令の吐 出が必要なものとして行なわれる（ステップ１４１２）かもしれない。このルー チンは次に呼出元に戻る（ステップ１４０８）。 ＤＥＳＣ命令を行なうステップ１２１６（図１２）は、図１５で述べるプロシ ジャに従って達成される。図１５を参照すれば、ＤＥＳＣ命令に先行してＤＥＬ ＴＡまたはＬＡＢＳ命令が必要であれば、ステップ１５０２でそれが吐出される 。次にＤＥＳＣ命令がステップ１５０４で吐出され、このルーチンはステップ１ ５０６で呼出元に戻る。図１２においてＤＳＣ２命令（ステップ１２２０）およ びＶＴＢＬ命令（ステップ１２２４）を行なうルーチンは、ＤＥＳＣ命令の代わ りにステップ１５０４（図１５）においてＤＳＣ２命令またはＶＴＢＬ命令が吐 出されることを除 き、図１５で述べるものと同一である。 ＸＣＯＦＦエントリからのリロケーションをＰＥＦリロケーション命令に変換 するルーチン（図１２）についての説明では、ＰＥＦリロケーション命令が「吐 出される」と表明されたときは常に、吐出されたリロケーション命令は１時バッ ファに置くことが可能である。後に、反復パターンおよびそれに対して生成され たＲＰＴまたはＬＲＰＴを捜して、その１時バッファをスキャンすることが可能 である。 ＲＰＴおよびＬＲＰＴ命令を生成するための別の技術は、これらが生成されて いるときにパターンを識別することである。この技術においては、リロケーショ ン変換ルーチン９０８により「吐出された」ＰＥＦ命令は、先入れ先出し（ＦＩ ＦＯ）バッファに、このバッファが満杯になるまでまたはパターンが検出される まで保持される。もしこのバッファが満杯であれば、バッファ内の最初のＰＥＦ 命令が出力され、新しく吐出された命令が末端に加えられ、このルーチンは復帰 する。新しく吐出された命令がバッファにおける部分的一致を開始させ、または 継続している場合、一致サイズ変数が単にインクリメントする。もし新しく吐出 された命令が一致を完了させれば、一致サイズ変数は０に戻り、繰返しカウント 変数がインクリメントする。もし新しく吐出された命令が一致を破れば、パター ンに共通の命令が最初に出力され、バッファから削除され、次に適切 なＲＰＴまたはＬＲＰＴ命令が出力される。新しく吐出された命令が次にバッフ ァに加えられる。このパターン一致プロセスにより出力された命令が、最終的な ＰＥＦファイルにはまだ出力されておらず、これらは単にＰＥＦリロケーション バッファの最終的なメモリ内バージョンにシーケンシャルにストアされているだ けであることに注意されたい。 図９に戻って、ＸＣＯＦＦリロケーション表におけるすべてのエントリがＰＥ Ｆリロケーション命令に変換された後（ステップ９０８）、データセクション自 体が、前述のパターン初期化データ（ｐｉデータ）フォーマットを用いてパック される（ステップ９１０）。ステップ９１２では、ＰＥＦセクションの大きさが すべて確立されているため、オフセットが計算され、すべてのヘッダはさまざま なセクションを示す必要な情報で満たされる（ステップ９１２）。ステップ９１ ４で、ＰＥＦファイルの各ブロックが、データアラインメント要求を満たすため に必要に応じて挿入されるパディングバイトとともに書出される。 本発明は特定的な実施例について述べられており、その範囲から逸脱すること なく数多くの修正を行なうことが可能であることが理解されるだろう。たとえば 、本発明は、リンキングに先行してコンパイラにより生成されるリロケート可能 なオブジェクトコードファイルフォーマットにも応用され得る。ただし、実行さ れるべきリロケーションの 繰返しのパターンが比較的乏しいため、本発明はそのコンテキストにおいてはあ まり有用でない。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ， ＣＡ，ＣＨ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，Ｇ Ｂ，ＨＵ，ＪＰ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，ＬＵ，ＬＶ ，ＭＧ，ＭＮ，ＭＷ，ＮＬ，ＮＯ，ＮＺ，ＰＬ，ＰＴ， ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＫ，ＵＡ，ＵＺ，ＶＮ (72)発明者 リリック，アラン・ダブリュ アメリカ合衆国、95032 カリフォルニア 州、ロス・ガトス、ユークリッド・アベニ ュ、３ 【要約の続き】 定する。他のタイプのリロケーション命令もまた利用可 能にされる。ファイルはまたハッシングされたシンボル エクスポート表およびパターン初期化されたデータ拡張 命令を含む。

Claims (1)

1. 【特許請求の範囲】 １．リロケート可能なファイルを実行のためにコンピュータシステムメモリにロ ードするための方法であって、前記ファイルは前記メモリにロードされる複数の 情報項目を有し、前記情報項目のいくつかは、リロケート可能なアドレスを含む それぞれの第１のアドレスフィールドを有し、前記ファイルはさらに複数のリロ ケーション命令を有し、 前記リロケーション命令のうち１つを取り出すステップと、 前記リロケーション命令のうちの前記１つに応答して、ｎ個の連続する前記情 報項目のアドレスフィールドを更新するステップとを含み、ｎは前記リロケーシ ョン命令のうちの前記１つ内において特定される、リロケート可能なファイルを 実行のためにコンピュータシステムメモリにロードするための方法。 ２．前記複数のリロケーション命令の異なるものに対し、前記取り出し更新する ステップを繰返すステップをさらに含む、請求項１に記載の方法。 ３．前記リロケーション命令は種々のタイプのものであり、前記更新するステッ プは、前記リロケーション命令のそれぞれのタイプに依存する複数のステップを 含む、請求項２に記載の方法。 ４．前記リロケーション命令の各々はそれぞれのアドレスにロケートされ、前記 リロケーション命令のアドレスは、 前記取り出すステップの各繰返しに対して第１のポインタ（ｒｅｌｏｃ）から判 定され、前記取り出すステップの各繰返しと関連して、前記第１のポインタ（ｒ ｅｌｏｃ）を前記検索されたリロケーション命令の長さに依存するある値に更新 するステップをさらに含む、請求項２に記載の方法。 ５．前記第１のポインタ（ｒｅｌｏｃ）を更新する前記ステップは、前記第１の ポインタ（ｒｅｌｏｃ）を更新し、前記リロケーション命令のうち、前記取出さ れたリロケーション命令のすぐ後に続く１つを指示するようにするステップを含 む、請求項４に記載の方法。 ６．前記第１のポインタ（ｒｅｌｏｃ）を更新する前記ステップは、前記取出さ れたリロケーション命令内のバイト数を前記第１のポインタ（ｒｅｌｏｃ）に加 えるステップを含む、請求項４に記載の方法。 ７．前記ｎ個の連続する情報項目のうち第１の情報項目の前記メモリ内における アドレスは、前記更新するステップの各繰返しに対して第２のポインタ（ｒＡｄ ｄｒ）から判定され、前記更新するステップの各繰返しと関連して、ｎに依存す るある値に前記第２のポインタ（ｒＡｄｄｒ）を更新するステップをさらに含む 、請求項２に記載の方法。 ８．前記第２のポインタ（ｒＡｄｄｒ）を更新する前記ステップは、前記第２の ポインタ（ｒＡｄｄｒ）を更新して、前記ｎ個の連続する情報項目に続く、前記 メモリ内におけ る第１のアドレスを指示するようにするステップを含む、請求項７に記載の方法 。 ９．前記第２のポインタ（ｒＡｄｄｒ）を更新する前記ステップは、１つの情報 項目当たり予め定められたバイト数のｎ倍を前記第２のポインタ（ｒＡｄｄｒ） に加えるステップを含む、請求項７に記載の方法。 １０．第１のアドレスフィールドを更新する前記ステップは、前記ｎ個の連続す る情報項目における各所与の情報項目の第１のアドレスフィールドを、表（イン ポート）のそれぞれの所与の要素に依存するある値に更新するステップを含む、 請求項１に記載の方法。 １１．各所与の情報項目の第１のアドレスフィールドを更新する前記ステップは 、 前記ｎ個の連続する情報項目のｉ番目のものの第１のアドレスフィールドを、 前記表のｉ番目の要素に依存するある値に更新するステップを含み、ｉはカウン ト値（ｒＳｙｍＩ）から判断され、さらに、 前記ｎ個の連続する情報項目のｉ番目のものの第１のアドレスフィールドを更 新する前記ステップの各繰返しに関連して前記カウント値（ｒＳｙｍＩ）をイン クリメントするステップと、 前記ｎ個の連続する情報項目の各々に対し、前記ｎ個の連続する情報項目のｉ 番目のものの第１のアドレスフィールドを更新する前記ステップおよび前記カウ ント値（ｒＳ ｙｍＩ）をインクリメントする前記ステップを繰返すステップとを含む、請求項 １０に記載の方法。 １２．前記ｎ個の連続する情報項目のｉ番目のものの第１のアドレスフィールド を更新する前記ステップは、前記表の前記ｉ番目の要素の内容を、前記ｎ個の連 続する情報項目の前記ｉ番目のものの前記第１のアドレスフィールドに加えるス テップを含む、請求項１１に記載の方法。 １３．第１のアドレスフィールドを更新する前記ステップは、前記ｎ個の連続す る情報項目内の各所与の情報項目の第１のアドレスフィールドを、第３のポイン タ（ｃｏｄｅＡ、ｄａｔａＡ）に依存するある値に更新するステップを含み、前 記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）内の値はｎ個の連続する前記情報 項目の第１のアドレスフィールドを更新する前記ステップ全体に対して一定であ る、請求項１に記載の方法。 １４．各所与の情報項目の第１のアドレスフィールドを更新する前記ステップは 、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）の内容を前記所与の情報項目 の前記第１のアドレスフィールドに加えるステップを含む、請求項１３に記載の 方法。 １５．前記リロケーション命令（たとえばＣＯＤＥ、ＤＡＴＡ）に依存して前記 第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）を選択するステップをさらに含む、 請求項１３に記載の方法。 １６．リロケート可能なファイルを実行のためにコンピュータシステムメモリに ロードするための方法であって、前記ファイルは前記メモリにロードされる複数 の情報項目を有し、前記情報項目のいくつかはリロケート可能なアドレスを含む それぞれの第１のアドレスフィールドを有し、前記ファイルはさらに複数のリロ ケーション命令を有し、前記リロケーション命令は種々のタイプであり、 第１のポインタ（ｒｅｌｏｃ）に依存するあるロケーションから前記リロケー ション命令のうち１つを取り出すステップと、 前記取り出すステップの各繰返しに関連して前記第１のポインタ（ｒｅｌｏｃ ）を更新するステップと、 前記取出されたリロケーション命令がリロケーション命令の第１のクラスにあ れば（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、ＤＳＣ２、ＶＴＢＬ 、ＳＹＭＲ、ＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）、前記情報項目の少なくとも１ つについてリロケーション動作を実行するステップとを含み、前記情報項目の前 記少なくとも１つの第１のものは第２のポインタ（ｒＡｄｄｒ）により指示され 、前記リロケーション動作は前記取出されたリロケーション命令のタイプに依存 する複数のステップを含み、さらに、 前記第２のポインタ（ｒＡｄｄｒ）を前記情報項目の前記少なくとも１つにつ いての前記リロケーション動作のうち１つの各実行に関連して更新するステップ と、 前記取出すステップ、前記第１のポインタ（ｒｅｌｏｃ）を更新するステップ 、前記実行するステップ、および前記第２のポインタ（ｒＡｄｄｒ）を更新する ステップを繰返すステップとを含む、リロケート可能なファイルを実行のために コンピュータシステムメモリにロードするための方法。 １７．前記取出されたリロケーション命令は、前記第１のクラス内にある、リロ ケーション命令の第２のクラス（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥ ＳＣ、ＤＳＣ２、ＶＴＢＬ、ＳＹＭＲ）にあり、前記リロケーション動作の前記 ステップは、ｎ個の連続する前記情報項目の第１のアドレスフィールドを更新す るステップを含み、前記ｎ個の連続する前記情報項目の始めは、前記第２のポイ ンタ（ｒＡｄｄｒ）により指示され、ｎは前記取出されたリロケーション命令内 で特定される、請求項１６に記載の方法。 １８．前記取出されたリロケーション命令は、前記第２のクラス内にある、リロ ケーション命令の第３のクラス（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥ ＳＣ、ＤＳＣ２、ＶＴＢＬ）にあり、第１のアドレスフィールドを更新する前記 ステップは、前記ｎ個の連続する前記情報項目における各所与の情報項目の第１ のアドレスフィールドを、当該第１のアドレスフィールドの従前の内容および第 ３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）に依存するある値に更新するステップ を含み、前記第３のポインタ（ｃｏｄｅ Ａ、ｄａｔａＡ）内の値は、ｎ個の連続する情報項目の第１のアドレスフィール ドを更新する前記ステップ全体に対して一定である、請求項１７に記載の方法。 １９．前記取出されたリロケーション命令は、前記第３のクラス内の、命令の第 ４のクラス（たとえばＤＤＡＴ）内にあり、第１のアドレスフィールドを更新す る前記ステップは第３のポインタ（ｄａｔａＡ）の内容を前記ｎ個の連続する情 報項目の各々の前記第１のアドレスフィールドに加えるステップを含み、 前記取出されたリロケーション命令が命令の前記第４のクラス（たとえばＤＤ ＡＴ）内にあれば、リロケーション動作を実行する前記ステップに先行して、前 記取出されたリロケーション命令において特定された値により前記第２のポイン タ（ｒＡｄｄｒ）をインクリメントするステップをさらに含む、請求項１７に記 載の方法。 ２０．前記取出されたリロケーション命令は、前記第２のクラス内の、リロケー ション命令の第５のクラス（たとえばＣＯＤＥ、ＤＡＴＡ）内にあり、前記第５ のクラスはリロケーション命令の第６のクラス（たとえばＣＯＤＥ）およびリロ ケーション命令の第７のクラス（たとえばＤＡＴＡ）を含み、第１のアドレスフ ィールドを更新する前記ステップは、 もし前記取出されたリロケーション命令が命令の前記第６のクラス（たとえば ＣＯＤＥ）内にあれば、前記ｎ個の 連続する情報項目の各々の前記第１のアドレスフィールドに第３のポインタ（ｃ ｏｄｅＡ）の内容を加えるステップと、 もし前記取出されたリロケーション命令が命令の前記第７のクラス（たとえば ＤＡＴＡ）内にあれば、前記ｎ個の連続する情報項目の各々の前記アドレスフィ ールドに第４のポインタ（ｄａｔａＡ）の内容を加えるステップとを含む、請求 項１７に記載の方法。 ２１．前記取出されたリロケーション命令は前記第２のクラス内の、命令の第８ のクラス（たとえばＶＴＢＬ）内にあり、 第１のアドレスフィールドを更新する前記ステップは、第４のポインタ（ｄａ ｔａＡ）の内容を前記ｎ個の連続する情報項目の各々の第１の語に加えるステッ プを含み、前記ｎ個の連続する情報項目は２語の長さを有し、 前記第２のポインタ（ｒＡｄｄｒ）を更新する前記ステップは前記第２のポイ ンタを２ｎ個の語でインクリメントするステップを含む、請求項１７に記載の方 法。 ２２．前記取出されたされたリロケーション命令は前記第２のクラス内の、リロ ケーション命令の第９のクラス（たとえばＤＥＳＣ、ＤＳＣ２）内にあり、 第１のアドレスフィールドを更新する前記ステップは、第３のポインタ（ｃｏ ｄｅＡ）の内容を前記ｎ個の連続する情報項目各々の前記第１のアドレスフィー ルドに加える ステップを含み、 前記ｎ個の連続する情報項目の各々はさらに第２のアドレスフィールドを有し 、 前記リロケーション動作の前記ステップはさらに、第４のポインタ（ｄａｔａ Ａ）の内容を前記ｎ個の連続する情報項目各々の前記第２のアドレスフィールド に加えるステップを含む、請求項１７に記載の方法。 ２３．前記取り出されたリロケーション命令は命令の第１０のクラス（たとえば ＳＹＭＲ）内にあり、第１のアドレスフィールドを更新する前記ステップは、 前記ｎ個の連続する情報項目の各ｉ番目のものの第１のアドレスフィールドに 、表（インポート）のｎ個の連続する要素のそれぞれのｉ番目の要素の内容を加 えるステップを含み、前記表における前記ｎ個の連続する要素の始めはカウント 値（ｒＳｙｍＩ）から判定され、さらに、 前記カウント値（ｒＳｙｍＩ）にｎを加えるステップを含む、請求項１７に記 載の方法。 ２４．前記取り出されたリロケーション命令は前記第１のクラス内の、リロケー ション命令の第１１のクラス（たとえばＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）内に あり、前記リロケーション動作の前記ステップは、前記第２のポインタ（ｒＡｄ ｄｒ）により指示された情報項目の第１のアドレスフィールドを更新するステッ プを含む、請求項１６に記載の方法。 ２５．第１のアドレスフィールドを更新する前記ステップは、前記取り出された リロケーション命令により特定されたポインタの内容（インポート［ＩＤＸ９］ 、領域［ＩＤＸ９］、領域［ＣＮＴ２２］）を前記第１のアドレスフィールドに 加えるステップを含む、請求項２４に記載の方法。 ２６．前記取り出されたリロケーション命令は前記第１１のクラス内の、第１２ のクラスの命令（たとえばＳＹＭＢ）内にあり、前記取り出されたリロケーショ ン命令により特定された前記ポインタは、表（インポート）のｉ番目の要素とし て与えられ、ｉは前記取り出されたリロケーション命令内で特定され、前記表（ インポート）の次に使用する要素を示すカウント値（ｒＳｙｍＩ）を維持するス テップをさらに含み、前記リロケーション動作の前記ステップはさらに、次に使 用するために、前記カウント値（ｒＳｙｍＩ）としてｉ＋１をストアするステッ プを含む、請求項２５に記載の方法。 ２７．もし前記取り出されたリロケーション命令が第１３のクラスの命令（たと えばＣＤＩＳ、ＤＴＩＳ、ＬＣＤＩＳ、ＬＤＴＩＳ）内にあれば、前記第３のポ インタ（ｃｏｄｅＡ、ｄａｔａＡ）の内容を前記取り出されたリロケーション命 令に依存するある値に更新するステップをさらに含む、請求項１６に記載の方法 。 ２８．前記複数の情報項目は前記メモリの複数の領域にロードされ、前記領域の 各々は、前記複数の情報項目の少な くとも１つのそれぞれのグループを連続して含み、前記領域の各々はそれぞれの 指定名およびそれぞれの先頭アドレスを有し、 前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）の内容を更新する前記ステッ プは、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）として、その指定名が前 記取り出されたリロケーション命令内で特定される前記領域の１つの先頭アドレ スをストアするステップを含む、請求項２７に記載の方法。 ２９．もし前記取り出されたリロケーション命令が第１４のクラスの命令（たと えばＤＥＬＴＡ）内にあれば、前記第２のポインタ（ｒＡｄｄｒ）に、前記取り 出されたリロケーション命令内で特定される値を加えるステップをさらに含む、 請求項１６に記載の方法。 ３０．もし前記取り出されたリロケーション命令が第１５のクラスの命令（たと えばＬＡＢＳ）内にあれば、前記第２のポインタ（ｒＡｄｄｒ）として、前記取 り出されたリロケーション命令内で特定された値をストアするステップをさらに 含む、請求項１６に記載の方法。 ３１．もし前記取り出されたリロケーション命令が第１６のクラスの命令（たと えばＲＰＴ、ＬＲＰＴ）内にあれば、前記第１のポインタ（ｒｅｌｏｃ）の内容 を、前記取り出されたリロケーション命令に依存するある値に更新するステップ をさらに含む、請求項１６に記載の方法。 ３２．前記第１のポインタ（ｒｅｌｏｃ）の内容を更新する前記ステップは、前 記第１のポインタ（ｒｅｌｏｃ）の前記内容から値ｊを減算するステップを含み 、ｊは前記取り出されたリロケーション命令内で特定される、請求項３１に記載 の方法。 ３３．減算する前記ステップの繰返しの数のカウントを保持するステップと、 ｍ個のそのような繰返しの後減算する前記ステップを禁止するステップとをさ らに含み、ｍは前記取り出されたリロケーション命令内で特定される、請求項３ ２に記載の方法。 ３４．もし前記取り出されたリロケーション命令が第１７のクラスの命令（たと えばＬＳＹＭ）内にあれば、前記カウント値（ｒＳｙｍＩ）を前記取り出された リロケーション命令に依存するある値に更新するステップをさらに含む、請求項 ２３に記載の方法。 ３５．もし前記取り出されたリロケーション命令が第１７のクラスの命令（たと えばＬＳＹＭ）内にあれば、前記カウント値（ｒＳｙｍＩ）を前記取り出された リロケーション命令に依存するある値に更新するステップをさらに含む、請求項 ２６に記載の方法。 ３６．コンピュータシステムメモリにロードするためのリロケート可能なファイ ルを有する情報記憶媒体であって、前記ファイルは前記メモリにロードされる複 数の情報項目 を有し、前記情報項目のいくつかはリロケート可能なアドレスを含むそれぞれの 第１のアドレスフィールドを有し、前記ファイルはさらに、ｎ個の連続する前記 情報項目の第１のアドレスフィールドの更新を特定する第１の命令を含む複数の リロケーション命令を有し、ｎは前記第１のリロケーション命令内で特定される 、情報記憶媒体。 ３７．前記リロケーション命令はさらに、前記リロケーション命令の第２のもの を含み、前記第２のリロケーション命令はｍ個の連続する前記情報項目のアトル スフィールドの更新を特定し、ｍは前記第２のリロケーション命令内で特定され る、請求項３６に記載の媒体。 ３８．前記第１および第２のリロケーション命令は、それぞれ異なる第１および 第２のタイプであり、前記第１のタイプのリロケーション命令により特定される 更新は、前記第２のタイプのリロケーション命令により特定される更新と異なる 、請求項３７に記載の媒体。 ３９．前記第１および第２のリロケーション命令のバイト長は異なる、請求項３ ７に記載の媒体。 ４０．前記第１のリロケーション命令は、ｎ個の連続する情報項目のうちいずれ が更新されるアドレスフィールドを有するかを特定しない、請求項３６に記載の 媒体。 ４１．前記第１のリロケーション命令により特定される、前記ｎ個の連続する情 報項目の第１のアドレスフィールドの前記更新は、前記ｎ個の連続する情報項目 における各所 与の情報項目の第１のアドレスフィールドの、表（インポート）のそれぞれの所 与の要素に依存する値への更新を含む、請求項３６に記載の媒体。 ４２．前記第１のリロケーション命令により特定される、所与の情報項目の第１ のアドレスフィールドの前記更新は、前記表の前記それぞれの所与の要素の内容 を前記所与の情報項目の前記第１のアドレスフィールドに加えることを含む、請 求項４１に記載の媒体。 ４３．前記第１のリロケーション命令により特定される、第１のアドレスフィー ルドの前記更新は、前記ｎ個の連続する情報項目における各所与の情報項目の第 １のアドレスフィールドを、第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）に依存 する値に更新することを含み、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ） における値は、ｎ個の連続する前記情報項目の第１のアドレスフィールドの前記 更新全体に対して一定である、請求項３６に記載の媒体。 ４４．前記第１のリロケーション命令により特定される、各所与の情報項目の第 １のアドレスフィールドの前記更新は、前記第３のポインタ（ｃｏｄｅＡ、ｄａ ｔａＡ）の内容を前記所与の情報項目の前記第１のアドレスフィールドに加える ことを含む、請求項４３に記載の媒体。 ４５．前記第１のリロケーション命令により特定される、第１のアドレスフィー ルドの前記更新はさらに、予め定められた複数のポインタのうちいずれが前記第 ３のポインタ を構成するかについての特定を含む、請求項４３に記載の媒体。 ４６．コンピュータシステムメモリにロードするためのリロケート可能なファイ ルを有する情報記憶媒体であって、前記ファイルは前記メモリにロードされる複 数の情報項目を有し、前記情報項目のいくつかはリロケート可能なアドレスを含 むそれぞれの第１のアドレスフィールドを有し、前記ファイルはさらに複数のリ ロケーション命令を有し、前記リロケーション命令は種々のタイプであり、前記 リロケーション命令の第１のクラス（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、 ＤＥＳＣ、ＤＳＣ２、ＶＴＢＬ、ＳＹＭＲ、ＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ） は、前記情報項目の少なくとも１つについてのリロケーション動作を特定し、前 記少なくとも１つの前記情報項目は、リロケーション命令の前記第１のクラスに おける前記リロケーション命令においては指示されず、前記リロケーション命令 のタイプが前記情報項目の前記少なくとも１つについて実行されるリロケーショ ン動作を特定する、情報記憶媒体。 ４７．前記第１のクラス内の第２のクラス内のリロケーション命令（たとえばＤ ＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、ＤＳＣ２、ＶＴＢＬ、ＳＹＭＲ）にお ける各所与のリロケーション命令により特定されるリロケーション動作は、ｎ個 の連続する前記情報項目の第１のアドレスフィールドの更新を含み、前記ｎ個の 連続する前記情報項目は前 記所与のリロケーション命令内で指示されず、ｎは前記所与のリロケーション命 令内で特定される、請求項４６に記載の媒体。 ４８．もし前記所与のリロケーション命令が前記第２のクラス内の第３のクラス のリロケーション命令（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、Ｄ ＳＣ２、ＶＴＢＬ）内にあれば実行される更新は、前記ｎ個の連続する前記情報 項目における各所与の情報項目の第１のアドレスフィールドを、そのような第１ のアドレスフィールドの従前の内容および第３のポインタ（ｃｏｄｅＡ、ｄａｔ ａＡ）に依存するある値に更新することを含み、前記第３のポインタ（ｃｏｄｅ Ａ、ｄａｔａＡ）内の値は、ｎ個の連続する情報項目の第１のアドレスフィール ドの前記更新全体に対して一定である、請求項４７に記載の媒体。 ４９．もし前記所与のリロケーション命令が前記第３のクラス内の第４のクラス の命令（たとえばＤＤＡＴ）内にあれば実行される更新は、第３のポインタ（ｄ ａｔａＡ）の内容を前記ｎ個の連続する情報項目の各々の前記第１のアドレスフ ィールドに加えることを含み、 前記所与のリロケーション命令はさらに、前記情報項目を示す第２のポインタ （ｒＡｄｄｒ）が前記更新に先行してインクリメントされる値を特定する、請求 項４７に記載の媒体。 ５０．当該実行される更新は、もし前記所与のリロケーシ ョン命令が第２のクラス内の第６のクラスのリロケーション命令（たとえばＣＯ ＤＥ）内にあれば第３のポインタ（ｃｏｄｅＡ）の内容を前記ｎ個の連続する情 報項目の各々の前記第１のアドレスフィールドに加えることおよびもし前記所与 のリロケーション命令が前記第２のクラス内の第７のクラスの命令（たとえばＤ ＡＴＡ）内にあれば、第４のポインタ（ｄａｔａＡ）の内容を前記ｎ個の連続す る情報項目の各々の前記第１のアドレスフィールドに加えることを含む、請求項 ４７に記載の媒体。 ５１．前記ｎ個の連続する情報項目の各々は第１の語および第２の語を含み、も し前記所与のリロケーション命令が前記第２のクラス内の第８のクラスの命令（ たとえばＶＴＢＬ）内にあれば実行される前記更新は、第４のポインタ（ｄａｔ ａＡ）の内容を前記ｎ個の連続する情報項目の各々の第１の語に加えることを含 み、前記第８のクラスの命令におけるリロケーション命令により特定されるリロ ケーション動作は、前記ｎ個の連続する情報項目の各々の第２の語のいかなる更 新も含まない、請求項４７に記載の媒体。 ５２．前記ｎ個の連続する情報項目の各々はさらに、リロケート可能なアドレス を含むそれぞれの第２のアドレスフィールドを含み、前記第２のクラス内の第９ のクラスのリロケーション命令（たとえばＤＥＳＣ、ＤＳＣ２）における各所与 のリロケーション命令により特定されるリロケーション動作は、第３のポインタ （ｃｏｄｅＡ）の内容を前 記ｎ個の連続する情報項目の各々の前記第１のアドレスフィールドに加えること および第４のポインタ（ｄａｔａＡ）の内容を前記ｎ個の連続する情報項目の各 々の前記第２のアドレスフィールドに加えることを含む、請求項４７に記載の媒 体。 ５３．もし前記所与のリロケーション命令が第１０のクラスの命令（たとえばＳ ＹＭＲ）内にあれば実行される更新は、前記ｎ個の連続する情報項目の各ｉ番目 のものの第１のアドレスフィールドに、表（インポート）におけるｎ個の連続す る要素のそれぞれのｉ番目の要素の内容を加えることを含む、請求項４７に記載 の媒体。 ５４．前記第１のクラス内の第１１のクラスのリロケーション命令（たとえばＳ ＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）内にある各所与のリロケーション命令により特 定される前記リロケーション動作は、その内容が前記リロケーション命令内で特 定されていない第２のポインタ（ｒＡｄｄｒ）により指示される情報項目の第１ のアドレスフィールドの更新を含む、請求項４６に記載の媒体。 ５５．第１のアドレスフィールドの前記更新は、前記第１のアドレスフィールド に、前記所与のリロケーション命令により特定されるポインタの内容（インポー ト［ＩＤＸ９］、領域［ＩＤＸ９］、領域［ＣＮＴ２２］）を加えることを含む 、請求項５４に記載の媒体。 ５６．前記複数のリロケーション命令はさらに、第１３の クラスの命令（たとえばＤＣＩＳ、ＤＴＩＳ、ＬＣＤＩＳ、ＬＤＴＩＳ）におけ るリロケーション命令を含み、前記第１３のクラスの命令における各リロケーシ ョン命令は、予め定められた複数のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）の第３ のポインタが更新されることを特定し、前記第１３のクラスの命令における各リ ロケーション命令のタイプが、前記予め定められた複数のポインタ（ｃｏｄｅＡ 、ｄａｔａＡ）のいずれが前記第３のポインタになるかどうかを決定する、請求 項４６に記載の媒体。 ５７．前記複数の情報項目は前記メモリの複数の領域にロードされ、前記領域の 各々は前記複数の情報項目の少なくとも１つのそれぞれのグループを連続して含 み、前記領域の各々はそれぞれの指定名およびそれぞれの先頭アドレスを有し、 前記第１３のクラスの命令における各所与のリロケーション命令により特定さ れる更新は、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）として、前記所与 のリロケーション命令において指定名が特定される前記領域の１つの先頭アドレ スをストアすることを含む、請求項５６に記載の媒体。 ５８．前記リロケーション命令はさらに、第１４のクラスの命令（たとえばＤＥ ＬＴＡ）を含み、前記第１４のクラスの命令における各リロケーション命令は、 前記情報項目への第２のポインタ（ｒＡｄｄｒ）に加えられる値を特定 する、請求項４６に記載の媒体。 ５９．前記リロケーション命令はさらに、第１５のクラスの命令（たとえばＬＡ ＢＳ）を含み、前記第１５のクラスの命令における各リロケーション命令は、前 記情報項目への第２のポインタ（ｒＡｄｄｒ）としてストアされる値を特定する 、請求項４６に記載の媒体。 ６０．前記リロケーション命令はさらに、第１６のクラスの命令（たとえばＲＰ Ｔ、ＬＲＰＴ）を含み、前記第１６のクラスの命令における各命令は、ｍ個の前 記リロケーション命令の直前のグループが何回繰返されるかを特定する、請求項 ４６に記載の媒体。 ６１．前記第１６のクラスの命令における各命令はさらにｍを特定する、請求項 ６０に記載の媒体。 ６２．コンピュータシステムメモリにロードするためのファイルを有する情報記 憶媒体であって、前記ファイルは、 複数のインポートシンボル名をそれぞれのインポートシンボル番号に関連づけ るインポート部分と、 複数のエクスポートシンボル名をそれぞれのエクスポートシンボルのロケーシ ョンの値に関連づけるエクスポート部分とを含み、前記エクスポート部分は前記 インポート部分とは異なる、情報記憶媒体。 ６３．前記インポート部分は、前記インポートシンボル名の各々に対応するイン ポート表エントリを有するインポートシンボル表を含み、前記インポート表エン トリの各々は、 前記表においてそれぞれのロケーションを有し、それが対応するインポートシン ボル名を特定し、前記インポートシンボル名の各々に関連するインポートシンボ ル番号は、前記インポートシンボル表におけるインポートシンボル名に対応する インポート表エントリのロケーションから導出可能である、請求項６２に記載の 媒体。 ６４．前記ファイルはさらに、前記インポートシンボル名を含むストリング表を 含み、前記インポートシンボル表における前記エントリの各々は、そのエントリ が対応するインポートシンボル名を特定する、前記ストリング表内のオフセット を含む請求項６３に記載の媒体。 ６５．前記インポートシンボル名すべてに対するインポートシンボル番号は全体 として一連の連続する整数を構成する、請求項６３に記載の媒体。 ６６．前記エクスポートシンボルのロケーションの値の各々は、（ａ）前記ファ イルにおけるロケーションへのポインタおよび（ｂ）インポートシンボル番号か らなる群より選択される、請求項６２に記載の媒体。 ６７．前記エクスポート部分は、前記エクスポートシンボル名の各々に対応する エクスポート表エントリを有するエクスポートシンボル表を含み、前記エクスポ ート表エントリの各々は、対応するエクスポートシンボル名および対応するエク スポートシンボル名と関連するエクスポートシンボルのロケーションの値を特定 する、請求項６２に記載の 媒体。 ６８．前記ファイルはさらに少なくとも１つのロード可能なセクションを含み、 前記エクスポートシンボルのロケーションの値の第１のものは前記ロード可能な セクションのうち第１のものにおけるロケーションへのポインタを含む、請求項 ６２に記載の媒体。 ６９．前記第１のエクスポートシンボルのロケーションの値はさらに、前記少な くとも１つのロード可能なセクションのいずれが前記第１のロード可能なセクシ ョンであるかを選択する、請求項６８に記載の媒体。 ７０．前記インポート部分は前記インポートシンボル名の各々に対応するインポ ート表エントリを有するインポートシンボル表を含み、前記インポート表エント リの各々は前記表におけるそれぞれのロケーションを有し、対応するインポート シンボル名を特定し、前記インポートシンボル名の各々に関連するインポートシ ンボル番号は、前記インポートシンボル表におけるインポートシンボル名に対応 するインポート表エントリのロケーションから導出可能であり、前記インポート シンボル表は前記エクスポートシンボル表とは異なる、請求項６２に記載の媒体 。 ７１．前記ファイルはさらに、前記ファイルのインポートシンボル名ストリング 部分に位置する複数のインポートシンボルストリングおよび前記ファイルのエク スポートシンボル名ストリング部分に位置する複数のエクスポートシン ボルストリングを含み、 前記インポート表エントリの各々は前記インポートシンボル名ストリングのう ち１つを指示し、インポート表エントリが対応するインポートシンボル名を特定 し、 前記エクスポート表エントリの各々は前記エクスポートシンボル名ストリング のうち１つを指示し、エクスポート表エントリが対応するエクスポートシンボル 名を特定し、 前記ファイルの前記インポートおよびエクスポートシンボル名ストリング部分 は異なる、請求項７０に記載の媒体。 ７２．前記インポートおよびエクスポートシンボル名ストリング部分は各々、前 記エクスポートシンボル表と異なり、前記ファイルの前記エクスポートシンボル 名ストリング部分は、前記ファイルにおいて前記ファイルの前記インポートシン ボル名ストリング部分よりも前記エクスポートシンボル表に近接して位置してい る、請求項７１に記載の媒体。 ７３．前記インポートおよびエクスポートシンボル名ストリング部分は各々前記 インポートシンボル表と異なり、前記ファイルの前記インポートシンボル名スト リング部分は、前記ファイルにおいて、前記ファイルの前記エクスポートシンボ ル名ストリング部分よりも前記インポートシンボル表に近接して位置している、 請求項７２に記載の媒体。 ７４．前記エクスポートシンボル表はハッシュされる、請求項６７に記載の媒体 。 ７５．前記ファイルはさらに、前記エクスポートシンボル 名の各々を前記エクスポート表エントリの予め定められたサブセットと関連づけ るエクスポートスロット表を含む、請求項６７に記載の媒体。 ７６．前記ファイルは、前記エクスポートシンボル名の各々に対応するチェーン エントリを含み、前記チェーンエントリの各々は、チェーンエントリに対応する エクスポートシンボル名の予め規定された第１の関数であるハッシュ語を含み、 前記チェーンエントリはスロットにグループ化され、前記スロットの少なくとも １つは２つ以上のチェーンエントリを有し、各スロットは複数のハッシュスロッ ト値のうちそれぞれ１つに対応し、ハッシュスロット値は、前記所与のスロット におけるチェーンエントリに対応するエクスポートシンボル名の各々の予め規定 された第２の関数である各所与のスロットに対応する、請求項６７に記載の媒体 。 ７７．前記ファイルはさらに、前記ハッシュスロット値のうち各所与の１つを、 前記所与のハッシュスロット値に対応するスロットにおけるチェーンエントリに 関連づける、請求項７６に記載の媒体。 ７８．前記ファイルはさらに、複数のインポートライブラリ名を前記インポート シンボル番号のそれぞれの集合に関連づけるライブラリ部分を含み、前記ライブ ラリ部分は前記インポート部分および前記エクスポート部分とは異なる、請求項 ６２に記載の媒体。 ７９．前記ファイルは前記メモリにロードされる複数の情報項目を有し、前記情 報項目のいくつかはリロケート可能なアドレスを含むそれぞれの第１のアドレス フィールドを有し、前記ファイルはさらに、ｎ個の連続する前記情報項目の第１ のアドレスフィールドの更新を特定する第１の命令を含む複数のリロケーション 命令を有し、ｎは前記第１のリロケーション命令内で特定される、請求項６２に 記載の媒体。 ８０．前記ファイルは前記メモリにロードされる複数の情報項目を有し、前記情 報項目のいくつかはリロケート可能なアドレスを含むそれぞれの第１のアドレス フィールドを有し、前記ファイルはさらに複数のリロケーション命令を有し、前 記リロケーション命令は種々のタイプからなり、第１のクラスの前記リロケーシ ョン命令（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、ＤＳＣ２、ＶＴ ＢＬ、ＳＹＭＲ、ＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）は前記情報項目の少なくと も１つについてリロケーション動作を特定し、前記情報項目の前記少なくとも１ つは前記第１のクラスのリロケーション命令における前記リロケーション命令に おいては指示されず、前記リロケーション命令のタイプが前記情報項目の前記少 なくとも１つについて実行されるリロケーション動作を特定する、請求項６２に 記載の媒体。 ８１．コンピュータシステムメモリにロードするためのファイルを有する情報記 憶媒体であって、前記ファイルは複 数のエクスポートシンボル名をそれぞれのエクスポートシンボルロケーションの 値に関連づけるエクスポートシンボル表を有し、前記エクスポートシンボル表は ハッシュされる、情報記憶媒体。 ８２．コンピュータシステムメモリにロードするためのファイルを有する情報記 憶媒体であって、前記ファイルは複数のエクスポートシンボル名をそれぞれのエ クスポートシンボルのロケーションの値に関連づけるエクスポートシンボル表お よび前記エクスポートシンボル名の各々を前記エクスポート表エントリの予め定 められたサブセットと関連づけるエクスポートスロット表を有する、情報記憶媒 体。 ８３．コンピュータシステムメモリにロードするためのファイルを有する情報記 憶媒体であって、前記ファイルは複数のエクスポートシンボル名をそれぞれのエ クスポートシンボルのロケーションの値と関連づけるエクスポートシンボル表を 有し、前記ファイルはさらに前記エクスポートシンボル名の各々に対応するチェ ーンエントリを含み、前記チェーンエントリの各々はチェーンエントリに対応す るエクスポートシンボル名の予め規定された第１の関数であるハッシュ語を含み 、前記スロットの少なくとも１つは２つ以上のチェーンエントリを有し、各スロ ットは複数のハッシュスロット値のうちそれぞれ１つに対応し、各所与のスロッ トに対応するハッシュスロット値は前記所与のスロットにおけるチェーンエント リに対応するエクスポートシン ボル名の各々の予め規定された第２の関数である、情報記憶媒体。 ８４．前記ファイルはさらに、前記ハッシュスロット値の所与の各々を、前記所 与のハッシュスロット値に対応する、スロット内のチェーンエントリと関連づけ るエクスポートスロット表を含む、請求項８３に記載の媒体。 ８５．リロケート可能なファイルを実行のためにコンピュータシステムメモリに ロードするための方法であって、前記ファイルは前記メモリにロードされる複数 の情報項目を有し、前記情報項目の第１のものはアドレスフィールドおよび前記 アドレスフィールドの更新において使用するための第１のインポートシンボル名 の表示を有し、 インポートファイルを前記メモリにロードするステップを含み、前記インポー トファイルは各々がスロット値を有する複数のエクスポートシンボルを含むエク スポートシンボルの表を有し、エクスポートシンボルの前記表における前記スロ ットの各々はエクスポートシンボル名をそれぞれのロケーションの値に関連づけ る少なくとも１つの関連づけを含み、エクスポートシンボルの前記表における少 なくとも１つの前記スロットは２つ以上のそのような関連づけを含み、前記スロ ットの各所与の１つにおいて関連づけられるエクスポートシンボル名すべては、 予め規定されたハッシュ−スロット値のアルゴリズムに従う同じハッシュスロッ ト値を有し、 前記予め規定されたハッシュ−スロット値のアルゴリズムに従い、前記第１の インポートシンボル名に対する第１のハッシュスロット値を決定するステップと 、 前記インポートファイル中のエクスポートシンボルの前記表における前記第１ のハッシュスロット値に対応する、スロット内の第１のエクスポートシンボル名 を探索するステップとをさらに含み、そのエクスポートシンボル名は前記第１の インポートシンボル名に一致し、 エクスポートシンボルの前記表により前記第１のエクスポートシンボル名に関 連づけられたロケーションの値に応答して、前記第１の情報の前記アドレスフィ ールドを更新するステップをさらに含む、リロケート可能なファイルを実行のた めにコンピュータシステムメモリにロードするための方法。 ８６．前記インポートファイル中のエクスポートシンボルの前記表における前記 関連づけの各々はさらに、予め規定されたハッシュ−語−値アルゴリズムに従い 関連づけのエクスポートシンボル名から計算されたハッシュ語の値を関連づけ、 前記ハッシュ語値アルゴリズムに従い前記第１のインポートシンボル名に対する 第１のインポートハッシュ語の値を決定するステップをさらに含み、探索する前 記ステップは、 エクスポートシンボルの前記表内の前記第１のハッシュスロット値に対応する 前記スロット内の前記関連づけの、 連続する現在のものに対し、前記現在の関連づけのエクスポートシンボル名が前 記第１のインポートシンボル名に一致するまで、前記現在の関連づけのエクスポ ートハッシュ語の値が前記第１のインポートハッシュ語の値に一致するかどうか を最初に決定し、もしそうである場合のみ、前記現在の関連づけのエクスポート シンボル名が前記第１のインポートシンボル名に一致するかどうかを決定するス テップを含む、請求項８５に記載の方法。 ８７．前記インポートファイルはさらに、エクスポートシンボルの前記表におけ る各所与のスロットを前記所与のスロットのスロット値と関連づけるエクスポー トスロット表を有し、前記エクスポートスロット表を調べて前記第１のハッシュ スロット値に対応する前記スロットを決定するステップをさらに含む、請求項８ ６に記載の方法。 ８８．前記インポートファイルはさらに、エクスポートシンボルの前記表におけ る各所与のスロットを前記所与のスロットのスロット値に関連づけるエクスポー トスロット表を有し、前記エクスポートスロット表を調べて前記第１のハッシュ スロット値に対応する前記スロットを決定するステップをさらに含む、請求項８ ５に記載の方法。 ８９．コンピュータシステムメモリにロードするためのリロケート可能なファイ ルを構成するための方法であって、前記ファイルは前記メモリにロードされる複 数の情報項目を有し、前記情報項目のいくつかはリロケート可能なアド レスを含むそれぞれの第１のアドレスフィールドを有し、 ｎ個の連続する前記いくつかの情報項目を特定するステップと、 前記ファイルに前記ｎ個の連続する情報項目の第１のアドレスフィールドの更 新を特定する第１のリロケーション命令を書込むステップとを含み、ｎは前記第 １のリロケーション命令内で特定される、コンピュータシステムメモリにロード するためのリロケート可能なファイルを構成するための方法。 ９０．ｍ個の連続する前記いくつかの情報項目を特定するステップと、 前記ファイルに前記ｍ個の連続する情報項目のアドレスフィールドの更新を特 定する第２のリロケーション命令を書込むステップとを含み、ｍは前記第２のリ ロケーション命令において特定される、請求項８９に記載の方法。 ９１．前記第１および第２のリロケーション命令のタイプはそれぞれ異なる第１ および第２のタイプであり、前記第１のタイプのリロケーション命令により特定 される更新は、前記第２のタイプのリロケーション命令により特定される更新と 異なる、請求項９０に記載の方法。 ９２．前記第１および第２のリロケーション命令のバイトの長さは異なる、請求 項９０に記載の方法。 ９３．前記第１のリロケーション命令は、前記ｎ個の連続する情報項目のいずれ が更新されるアドレスフィールドを 有するかを特定しない、請求項８９に記載の方法。 ９４．前記第１のリロケーション命令により特定される、前記ｎ個の連続する情 報項目の第１のアドレスフィールドの前記更新は、前記ｎ個の連続する情報項目 における各所与の情報項目の第１のアドレスフィールドを、表（インポート）の それぞれの所与の要素に依存するある値に更新することを含む、請求項８９に記 載の方法。 ９５．前記第１のリロケーション命令により特定される、所与の情報項目の第１ のアドレスフィールドの前記更新は、前記表の前記それぞれの所与の要素の内容 を前記所与の情報項目の前記第１のアドレスフィールドに加えることを含む、請 求項９４に記載の方法。 ９６．前記第１のリロケーション命令により特定される、第１のアドレスフィー ルドの前記更新は、前記ｎ個の連続する情報項目における各所与の情報項目の第 １のアドレスフィールドを、第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）に依存 するある値に更新することを含み、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａ Ａ）における値は、ｎ個の連続する前記情報項目の第１のアドレスフィールドの 前記更新全体に対して一定である、請求項８９に記載の方法。 ９７．前記第１のリロケーション命令により特定される、所与の情報項目の各々 の第１のアドレスフィールドの前記更新は、前記第３のポインタ（ｃｏｄｅＡ、 ｄａｔａＡ）の内容を前記所与の情報項目の前記第１のアドレスフィー ルドに加えることを含む、請求項９６に記載の方法。 ９８．前記第１のリロケーション命令により特定される、第１のアドレスフィー ルドの前記更新はさらに、予め定められた複数のポインタのうちいずれが前記第 ３のポインタを構成するかについての特定を含む、請求項９６に記載の方法。 ９９．コンピュータシステムメモリにロードするためのリロケート可能なファイ ルを構成するための方法であって、前記ファイルは前記メモリにロードされる複 数の情報項目を有し、前記情報項目のいくつかはリロケート可能なアドレスを含 むそれぞれの第１のアドレスフィールドを有し、 第１の複数の前記いくつかの情報項目を特定するステップと、 前記ファイルに複数のリロケーション命令を書込むステップとを含み、前記リ ロケーション命令は種々のタイプからなり、第１のクラスの前記リロケーション 命令（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、ＤＳＣ２、ＶＴＢＬ 、ＳＹＭＲ、ＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）は、前記第１の複数における前 記情報項目の少なくとも１つに対するリロケーション動作を特定し、前記第１の 複数における前記情報項目の前記少なくとも１つは前記第１のクラスのリロケー ション命令中の前記リロケーション命令において指示されず、前記リロケーショ ン命令のタイプが前記第１の複数における前記情報項目の前記少なくとも１ つに対して実行されるリロケーション動作を特定する、コンピュータシステムメ モリにロードするためのリロケート可能なファイルを構成するための方法。 １００．前記第１のクラス内にある第２のクラスのリロケーション命令（たとえ ばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、ＤＳＣ２、ＶＴＢＬ、ＳＹＭＲ） における各所与のリロケーション命令により特定されたリロケーション動作は、 前記第１の複数内のｎ個の連続する前記情報項目の第１のアドレスフィールドの 更新を含み、前記ｎ個の連続する前記情報項目は前記所与のリロケーション命令 内では指示されず、ｎは前記所与のリロケーション命令内で特定される、請求項 ９９に記載の方法。 １０１．もし前記所与のリロケーション命令が前記第２のクラス内の第３のクラ スのリロケーション命令（たとえばＤＤＡＴ、ＣＯＤＥ、ＤＡＴＡ、ＤＥＳＣ、 ＤＳＣ２、ＶＴＢＬ）内にあれば実行される更新は、前記ｎ個の連続する前記情 報項目における各所与の情報項目の第１のアドレスフィールドを、そのような第 １のアドレスフィールドの従前の内容および第３のポインタ（ｃｏｄｅＡ、ｄａ ｔａＡ）に依存するある値に更新することを含み、前記第３のポインタ（ｃｏｄ ｅＡ、ｄａｔａＡ）内の値は、ｎ個の連続する情報項目の第１のアドレスフィー ルドの前記更新全体に対して一定である、請求項１００に記載の方法。 １０２．もし前記所与のリロケーション命令が前記第３の クラス内の第４のクラスの命令（たとえばＤＤＡＴ）内にあれば実行される更新 は、第３のポインタ（ｄａｔａＡ）の内容を前記ｎ個の連続する情報項目の各々 の前記第１のアドレスフィールドに加えることを含み、 前記所与のリロケーション命令はさらに、前記情報項目を示す第２のポインタ （ｒＡｄｄｒ）が前記更新に先行してインクリメントされる値を特定する、請求 項１００に記載の方法。 １０３．実行される更新は、もし前記所与のリロケーション命令が前記第２のク ラス内の第６のクラスのリロケーション命令（たとえばＣＯＤＥ）内にあれば第 ３のポインタ（ｃｏｄｅＡ）の内容を前記ｎ個の連続する情報項目の各々の前記 第１のアドレスフィールドに加えることおよび、もし前記所与のリロケーション 命令が前記第２のクラス内の第７のクラスの命令（たとえばＤＡＴＡ）内にあれ ば第４のポインタ（ｄａｔａＡ）の内容を前記ｎ個の連続する情報項目の各々の 前記第１のアドレスフィールドに加えることを含む、請求項１００に記載の方法 。 １０４．前記ｎ個の連続する情報項目の各々は第１の語および第２の語を含み、 もし前記所与のリロケーション命令が前記第２のクラス内の第８のクラスの命令 （たとえばＶＴＢＬ）内にあれば実行される更新は、第４のポインタ（ｄａｔａ Ａ）の内容を前記ｎ個の連続する情報項目の各々の第１の語に加えることを含み 、前記第８のクラスの命 令におけるリロケーション命令により特定されるリロケーション動作は前記ｎ個 の連続する情報項目の各々の第２の語のいかなる更新も含まない、請求項１００ に記載の方法。 １０５．前記ｎ個の連続する情報項目の各々はさらに、リロケート可能なアドレ スを含むそれぞれの第２のアドレスフィールドを含み、前記第２のクラス内の第 ９のクラスのリロケーション命令（たとえばＤＥＳＣ、ＤＳＣ２）内の各所与の リロケーション命令により特定されるリロケーション動作は、第３のポインタ（ ｃｏｄｅＡ）の内容を前記ｎ個の連続する情報項目の各々の前記第１のアドレス フィールドに加えることおよび第４のポインタ（ｄａｔａＡ）の内容を前記ｎ個 の連続する情報項目の各々の前記第２のアドレスフィールドに加えることを含む 、請求項１００に記載の方法。 １０６．もし前記所与のリロケーション命令が第１０のクラスの命令（たとえば ＳＹＭＲ）内にあれば実行される更新は、前記ｎ個の連続する情報項目の各ｉ番 目のものの第１のアドレスフィールドに、表（インポート）におけるｎ個の連続 する要素のそれぞれのｉ番目の要素の内容を加えることを含む、請求項１００に 記載の方法。 １０７．前記第１のクラス内の第１１のクラスのリロケーション命令（たとえば ＳＹＭＢ、ＳＥＣＮ、ＬＳＥＣＮ）内にある各所与のリロケーション命令により 特定される前記リロケーション動作は、その内容が前記リロケーション 命令において特定されない第２のポインタ（ｒＡｄｄｒ）により指定される情報 項目の第１のアドレスフィールドの更新を含む、請求項９９に記載の方法。 １０８．第１のアドレスフィールドの前記更新は、前記第１のアドレスフィール ドに、前記所与のリロケーション命令により特定されるポインタの内容（インポ ート［ＩＤＸ９］、領域［ＩＤＸ９］、領域［ＣＮＴ２２］）を加えることを含 む、請求項１０７に記載の方法。 １０９．前記複数のリロケーション命令はさらに第１３のクラスの命令（たとえ ばＤＣＩＳ、ＤＴＩＳ、ＬＣＤＩＳ、ＬＤＴＩＳ）のリロケーション命令を含み 、前記第１３のクラスの命令の各リロケーション命令は予め定められた複数のポ インタ（ｃｏｄｅＡ、ｄａｔａＡ）の第３のポインタが更新されるべきであるこ とを指定し、前記第１３のクラスの命令の各リロケーション命令の当該タイプは 、前記予め定められた複数のポインタ（ｃｏｄｅＡ、ｄａｔａＡ）のいずれが前 記第３のポインタであるべきかを判定する、請求項９９に記載の方法。 １１０．前記複数の情報項目は前記メモリの複数の領域にロードされることが可 能であり、前記領域の各々は前記複数の情報項目の少なくとも１つのそれぞれの グループを連続して含み、前記領域の各々はそれぞれの指定名およびそれぞれの 先頭アドレスを有し、 前記第１３の命令のクラスの各所与のリロケーション命 令によって指定された更新は、前記第３のポインタ（ｃｏｄｅＡ、ｄａｔａＡ） としてその指定名が前記所与のリロケーション命令で指定される前記領域の１つ の先頭アドレスをストアすることを含む、請求項１０９に記載の方法。 １１１．前記リロケーション命令はさらに第１４のクラスの命令（たとえばＤＥ ＬＴＡ）を含み、前記第１４のクラスの命令の各リロケーション命令は前記情報 項目への第２のポインタ（ｒＡｄｄｒ）に加えられるべき値を指定する、請求項 ９９に記載の方法。 １１２．前記リロケーション命令はさらに第１５のクラスの命令（たとえばＬＡ ＢＳ）を含み、前記第１５のクラスの命令の各リロケーション命令は前記情報項 目への第２のポインタ（ｒＡｄｄｒ）としてストアされるべき値を指定する、請 求項９９に記載の方法。 １１３．前記リロケーション命令はさらに第１６のクラスの命令（たとえばＲＰ Ｔ、ＬＲＰＴ）を含み、前記第１６のクラスの命令の各命令は直前のｍ個の前記 リロケーション命令からなるグループが反復されるべき回数を指定する、請求項 ９９に記載の方法。 １１４．前記第１６のクラスの命令の各命令はさらにｍを指定する、請求項１１ ３に記載の方法。 １１５．コンピュータシステムメモリにロードされるべきインポートしているフ ァイルにインポートされることが可能な複数のエクスポートを含むオブジェクト コードファイ ルを構築するための方法であって、前記エクスポートの各々はエクスポートシン ボル名およびそれぞれのエクスポートシンボルロケーション値を有し、 前記エクスポートを前記オブジェクトコードファイルに書込むステップと、 前記オブジェクトコードファイルに前記エクスポートシンボル名を前記エクス ポートシンボルロケーション値と関連づけるエクスポートシンボル表を書込むス テップとを含み、前記エクスポートシンボル表はハッシングされる、オブジェク トコードファイルを構築するための方法。 １１６．コンピュータシステムメモリにロードされるべきインポートしているフ ァイルにインポートされることが可能な複数のエクスポートを含むオブジェクト コードファイルを構築するための方法であって、前記エクスポートの各々はエク スポートシンボル名とそれぞれのエクスポートシンボルロケーション値とを有し 、 前記オブジェクトコードファイルに各々が前記エクスポートシンボル名のそれ ぞれの１つをそのそれぞれのエクスポートシンボルロケーション値と関連づける 複数のエントリを有するエクスポートシンボル表を書込むステップと、 前記オブジェクトコードファイルに前記エクスポートシンボル名の各々を前記 エクスポート表エントリの予め定められたサブセットに関連づけるエクスポート スロット表を書込むステップとを含む、オブジェクトコードファイルを 構築するための方法。 １１７．コンピュータシステムメモリにロードされるべきインポートしているフ ァイルにインポートされることが可能な複数のエクスポートを含むオブジェクト コードファイルを構築するための方法であって、前記エクスポートの各々はエク スポートシンボル名とそれぞれのエクスポートシンボルロケーション値とを有し 、 前記オブジェクトコードファイルに前記エクスポートシンボル名の各々をその それぞれのエクスポートシンボルロケーション値と関連づけるエクスポートシン ボル表を書込むステップと、 前記オブジェクトコードファイルに前記エクスポートシンボル名の各々に対応 するチェーンエントリを書込むステップとを含み、前記チェーンエントリの各々 はチェーンエントリに対応するエクスポートシンボル名の第１の予め規定された 関数であるハッシュ語を含み、前記チェーンエントリはスロットにグループ分け され、前記スロットの少なくとも１つは１つより多いチェーンエントリを有し、 各スロットは複数のハッシュスロット値のそれぞれの１つに対応し、各所与のス ロットに対応するハッシュスロット値は前記所与のスロットのチェーンエントリ に対応するエクスポートシンボル名の各々の第２の予め規定された関数である、 オブジェクトコードファイルを構築するための方法。 １１８．前記オブジェクトコードファイルに、前記ハッシ ュスロット値の各所与の１つを前記所与のハッシュスロット値に対応するスロッ トのチェーンエントリと関連づけるエクスポートスロット表を書込むステップを さらに含む、請求項１１７に記載の方法。 １１９．コンピュータシステムメモリにロードされるべきファイルを構築するた めの方法であって、 前記ファイルにおいて、第１のサブパターンの「Ｒカウント３」回の繰返しの 後に長さが「カウント１」バイトである第２のサブパターンが続くデータパター ンを識別するステップを含み、前記第１のパターンの前記反復の各々は前記第２ のパターンと、その後に続く「Ｄカウント２」の付加的なバイトのデータからな り、 前記ファイルに、カウント１、Ｄカウント２、Ｒカウント３、前記第１のサブ パターン、および前記付加的なバイトのデータの各々を含むデータ拡張命令を書 込むステップを含む、ファイルを構築するための方法。 １２０．コンピュータシステムメモリにロードするためのファイルを伴う情報記 憶手段であって、前記ファイルは複数のデータ拡張命令を有し、第１のサブパタ ーンの「Ｒカウント３」回の繰返しの後に長さ「カウント１」バイトの第２のサ ブパターンが続くことからなるデータパターンの生成を指定する第１の命令を含 み、前記第１のサブパターンの前記反復の各々は、前記第２のサブパターンと、 それに続く「Ｄカウント２」の付加的なバイトのデータからな り、前記第１の命令はカウント１、Ｄカウント２、Ｒカウント３、前記第１のサ ブパターン、および前記付加的なバイトのデータの各々を特定する、コンピュー タシステムメモリにロードするためのファイルを伴う情報記憶手段。 １２１．コンピュータシステムメモリにファイルをロードするための方法であっ て、前記ファイルは複数のデータ拡張命令を有し、 前記データ拡張命令のうちの第１の命令を取出すステップと、 第１のサブパターンの「Ｒカウント３」回の繰返しの後に長さが「カウント１ 」バイトの第２のサブパターンが続くことからなるデータパターンを生成するス テップとを含み、前記第１のサブパターンの前記反復の各々は前記第２のサブパ ターンと、その後に続く「Ｄカウント２」の付加的なバイトのデータとからなり 、前記第１の命令はカウント１、Ｄカウント２、Ｒカウント３、前記第１のサブ パターン、および前記付加的なバイトのデータの各々を特定する、コンピュータ システムメモリにファイルをロードするための方法。