(57)【要約】      （修正有）【課題】バイト・レベルでファイルの差別化を行うシステムおよび方法を提供する。【解決手段】ファイル・バージョン間のソフトウェア／実行可能変更は、ソース・コード変更であると定める、主変更／論理変更と、二次的変更とを含む。二次的変更は、一般に主変更から生じ、ソフトウェア・コンパイラ／リンカ・ユーティリティが発生する。二次的変更は、アドレス変更、ポインタ目標アドレス変更、およびアドレス・オフセットの変更を含む。提供する前処理システムおよび方法は、ファイル・バージョン間において近似規則を用いて二次的変更を除去／削減し、これらの変更の除去に関する情報を、対応する差異ファイル内にエンコードする。【選択図】図１
2010176699.tif 000002
【特許請求の範囲】
【請求項１】
電子ファイルを更新するためのシステムであって、
電子ファイルの元バージョンと新バージョンとの間のコード化した差異を含む差異ファイルを発生する第１デバイスであって、
コード・ラインの削除、コード・ラインの追加、およびコード・ラインの修正のうちの少なくとも１つによって生じたアドレスのずれに対応する前記元および新バージョン間の差異を特定し、
前記元バージョンのテキスト・セクションおよび前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通のテキスト・セクションにおいて前記特定した差異を除去し、
修正した目標アドレスを有する命令を含む前記元ファイルの修正バージョンを発生する、
ことによって前記差異ファイルのサイズを縮小する少なくとも１つのコンポーネントを含む、第１デバイスと、
第２デバイスであって、前記差異ファイルを受信し、該差異ファイルを用いて、該第２デバイスにおいて新ファイルの一バージョンを発生する第２デバイスと、
を備えている、システム。
【請求項２】
請求項１記載のシステムにおいて、除去することは、更に、
前記元および新バージョン間に共通の第１および第２テキスト・セクションを特定し、前記元バージョンにおける第１テキスト・セクションは第１計算可能命令を含み、前記新バージョンにおける第２テキスト・セクションは第２計算可能命令を含み、
前記元および新バージョン間に共通の第３および第４テキスト・セクションを特定し、前記元バージョンにおける第３テキスト・セクションは、前記第１計算可能命令に対応する第１目標アドレスを含み、前記新バージョンにおける第４テキスト・セクションは、前記第２計算可能命令に対応する第２目標アドレスを含み、
前記第３および第４の関数ユニットの開始アドレス間の第１の差異を用い、更に前記第１および第２の関数ユニットの開始アドレス間の第２の差異を用いて、前記第１命令値を修正することによって、前記第２計算可能命令から第２命令値を発生し、
前記第１計算可能命令の第１命令値を、前記第２命令値と置換する、
ことを含む、システム。
【請求項３】
請求項１記載のシステムであって、更に、前記元バージョンにおけるデータ・ポインタ値を修正することによって、前記元および新バージョンに共通のデータ・セクションを指し示すデータ・ポインタを含む命令において前記特定した差異を除去することを含み、データ・ポインタ値を修正することは、現データ・ポインタが指し示す前記元バージョンにおけるデータ・セクションの開始アドレスと、前記新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を用いる、システム。
【請求項４】
請求項３記載のシステムにおいて、データ・ポインタを含む命令において特定した差異を除去することは、更に、
前記元および新バージョン間に共通の第１および第２のコード・セグメントを特定し、前記元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、前記新バージョンにおける第２コード・セグメントは第２データ・ポインタを含み、
前記元および新バージョン間で共通な第１および第２のデータ・ユニットを特定し、前記元バージョンにおける第１データ・ユニットは、前記第１データ・ポインタに対応する第１目標アドレスを含み、前記新バージョンにおける第２データ・ユニットは、前記第２データ・ポインタに対応する第２目標アドレスを含み、
前記第１および第２データ・ユニットの開始アドレス間の差異を用いて、第１データ・ポインタ値を修正することによって、前記第２データ・ポインタから第２データ・ポインタ値を発生し、
前記第１データ・ポインタの第１データ・ポインタ値を前記第２データ・ポインタ値と置換する、
ことを含む、システム。
【請求項５】
請求項１記載のシステムにおいて、前記第２デバイスは、パーソナル・コンピュータ、携帯計算デバイス、セルラ電話機、携帯通信デバイス、およびパーソナル・ディジタル・アシスタントの中から選択した、少なくとも１つのプロセッサに基づくデバイスである、システム。
【請求項６】
請求項１記載のシステムにおいて、前記第１デバイスは、少なくとも１つの結合部を用いて、前記差異ファイルを前記第２デバイスに転送し、前記少なくとも１つの結合部は、ワイヤレス結合部、有線結合部、混成ワイヤレス／有線結合部のうち少なくとも１つである、システム。
【請求項７】
差異ファイルの発生において用いる装置であって、
電子ファイルの元バージョンおよび新バージョンを受信する手段と、
前記元および新バージョンに共通のコードのユニットを特定する手段と、
前記コードのユニットに共通の命令を特定する手段であって、前記命令が、前記対応するファイルの別の部分に対する処理を指令する命令値を含む、手段と、
前記元バージョンの第１命令から第１命令値を発生する手段と、
前記新バージョンの第２命令から第２命令値を発生する手段であって、前記第２命令が前記第１命令に対応する、手段と、
前記第１命令の第１命令値を前記第２命令値と置換する手段と、
前記第２命令値をもつ前記第１命令を含む前記元ファイルの修正バージョンを発生する手段と、
を備えている、装置。
【請求項８】
電子ファイルの元バージョンと新バージョンとの間のコード化した差異を含む差異ファイルのサイズを縮小する方法であって、
コード・ライン削除、コード・ライン追加、およびコード・ライン修正のうち少なくとも１つから生じたアドレスのずれに対応する前記元および新バージョン間の差異を特定するステップと、
前記元バージョンのテキスト・セクションと前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、前記元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通なテキスト・セクションにおいて前記特定した差異を除去するステップと、
修正した目標アドレスを有する命令を含む前記元ファイルの修正バージョンを発生するステップと、
を備えている、方法。
【請求項９】
請求項８記載の方法において、除去するステップは、更に、
前記元および新バージョン間で共通の第１および第２テキスト・セクションを特定するステップであって、前記元バージョンにおける第１テキスト・セクションは第１計算可能命令を含み、前記新バージョンにおける第２テキスト・セクションは第２計算可能命令を含む、ステップと、
前記元および新バージョン間で共通の第３および第４テキスト・セクションを特定するステップであって、前記元バージョンにおける第３テキスト・セクションは前記第１計算可能命令に対応する第１目標アドレスを含み、前記新バージョンにおける第４テキスト・セクションは前記第２計算可能命令に対応する第２目標アドレスを含む、ステップと、
前記第３および第４関数ユニットの開始アドレス間の第１の差異、ならびに前記第１および第２関数ユニットの開始アドレス間における第２の差異を用いて前記第１命令値を修正することによって、前記第２計算可能命令から第２命令値を発生するステップと、
前記第１計算可能命令の第１命令値を前記第２命令値と置換するステップと、
を備えている、方法。
【請求項１０】
請求項８記載の方法であって、更に、前記元バージョンにおけるデータ・ポインタを修正することによって、前記元および新バージョンに共通なデータ・セクションを指し示すデータ・ポインタを含む命令において特定した差異を除去するステップを備えており、データ・ポインタ値の修正には、現データ・ポインタが指し示す前記元バージョンにおけるデータ・セクションの開始アドレスと、前記新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を用いる、方法。
【請求項１１】
請求項１０記載の方法において、データ・ポインタを含む命令において特定した差異を除去するステップは、更に、
前記元および新バージョン間に共通の第１および第２コード・セグメントを特定するステップであって、前記元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、前記新バージョンにおける第２コード・セグメントは第２データ・ポインタを含む、ステップと、
前記元および新バージョン間で共通の第１および第２データ・ユニットを特定するステップであって、前記元バージョンにおける第１データ・ユニットは、前記第１データ・ポインタに対応する第１目標アドレスを含み、前記新バージョンにおける第２データ・ユニットは、前記第２データ・ポインタに対応する第２目標アドレスを含み、ステップと、
前記第２データ・ポインタから第２データ・ポインタ値を発生するステップと、
前記第１データ・ポインタの第１データ・ポインタ値を前記第２データ・ポインタ値と置換するステップと、
を備えている、方法。
【請求項１２】
請求項１１記載の方法において、前記第２データ・ポインタ値を発生するステップは、前記第１および第２データ・ユニットの開始アドレス間の差異を用いて、第１データ・ポインタ値を修正するステップを含む、方法。
【請求項１３】
請求項１０記載の方法であって、更に、修正データ・ポインタを有する前記命令を含む前記元ファイルの修正バージョンを発生するステップを備えている、方法。
【請求項１４】
請求項１０記載の方法であって、更に、共通データ・ブロックを形成するために共通データ・ユニットを併合するステップを含む、方法。
【請求項１５】
請求項１４記載の方法において、併合するステップは、
前記元バージョンの第１データ・ユニットが前記新バージョンの第１データ・ユニットに等しいサイズを有し、前記元バージョンの第１データ・ユニットの終了アドレスが前記元バージョンの第２データ・ユニットの開始アドレスに等しく、かつ前記新バージョンの第１データ・ユニットの終了アドレスが前記新バージョンの第２データ・ユニットの開始アドレスに等しい場合、共通データ・ブロックを形成するために、前記元バージョンの第１および第２データ・ユニットを結合し、前記新バージョンの対応する第１および第２データ・ユニットを結合するステップと、
追加の併合可能データ・ユニットについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項１６】
請求項１５記載の方法であって、更に、共通関数ブロックを形成するために、共通テキスト・セクションを併合するステップを含む、方法。
【請求項１７】
請求項１６記載の方法において、併合するステップは、
前記元バージョンの第１テキスト・セクションが前記新バージョンの第１テキスト・セクションに等しいサイズを有し、前記元バージョンの第１テキスト・セクションの終了アドレスが、前記元バージョンの第２テキスト・セクションの開始アドレスに等しく、かつ前記新バージョンの第１テキスト・セクションの終了アドレスが前記新バージョンの第２テキスト・セクションの開始アドレスに等しい場合、共通関数ブロックを形成するために、前記元バージョンの第１および第２テキスト・セクションを結合し、前記新バージョンの対応する第１および第２テキスト・セクションを結合するステップと、
追加の併合可能データ・ユニットについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項１８】
ファイルの差別化を実行するための方法であって、
電子ファイルの元バージョンおよび新バージョンを受信するステップと、
前記元および新バージョンに共通のコードのユニットを特定するステップと、
前記コードのユニットに共通の命令を特定するステップであって、前記命令が前記対応するファイルの別の部分に関係する命令値を含む、ステップと、
前記元バージョンの第１命令から第１命令値をデコードするステップと、
前記新バージョンの第２命令から第２命令値を発生するステップであって、前記第２命令が前記第１命令に対応する、ステップと、
前記第１命令の第１命令値を前記第２命令値と置換するステップと、
前記第２命令値をもつ前記第１命令を含む元ファイルの修正バージョンを発生するステップと、
を備えている、方法。
【請求項１９】
請求項１８記載の方法であって、更に、関連するマップ・ファイルから共通するコードのユニットを抽出するステップを備えており、前記共通するコードのユニットは、共通関数ユニットおよび共通データ・ユニットを含む、方法。
【請求項２０】
請求項１８記載の方法であって、更に、共通関数ブロックを形成するために、前記コードのユニットの共通関数ユニットを併合するステップを含む、方法。
【請求項２１】
請求項２０記載の方法において、併合するステップは、
前記元バージョンの第１関数ユニットが前記新バージョンの第１関数ユニットに等しいサイズを有し、前記元バージョンの第１関数ユニットの終了アドレスが前記元バージョンの第２関数ユニットの開始アドレスに等しく、かつ前記新バージョンの第１関数ユニットの終了アドレスが前記新バージョンの第２関数ユニットの開始アドレスに等しい場合、共通関数ブロックを形成するために、前記元バージョンの第１および第２関数ユニットを結合し、前記新バージョンの対応する第１および第２関数ユニットを結合するステップと、
追加の併合可能な関数ユニットについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項２２】
請求項２０記載の方法であって、更に、前記共通関数ブロックをエンコードするステップを含む、方法。
【請求項２３】
請求項１８記載の方法であって、更に、共通データ・ブロックを形成するために、前記コードのユニットの共通データ・ユニットを併合するステップを含む、方法。
【請求項２４】
請求項２３記載の方法において、併合するステップは、
前記元バージョンの第１データ・ユニットが前記新バージョンの第１データ・ユニットに等しいサイズを有し、前記元バージョンの第１データ・ユニットの終了アドレスが前記元バージョンの第２データ・ユニットの開始アドレスに等しく、かつ前記新バージョンの第１データ・ユニットの終了アドレスが、前記新バージョンの第２データ・ユニットの開始アドレスに等しい場合、共通データ・ブロックを形成するために、前記元バージョンの第１および第２データ・ユニットを結合し、前記新バージョンの対応する第１および第２データ・ユニットを結合するステップと、
追加の併合可能なデータ・ユニットについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項２５】
請求項２３記載の方法であって、更に、前記共通データ・ブロックを併合するステップを含む、方法。
【請求項２６】
請求項１８記載の方法において、前記元および新バージョンに共通の前記コードのユニットは共通関数ユニットであり、前記第１命令は第１計算可能命令を含み、前記第２命令は第２計算可能命令を含み、前記第２命令値をの発生は、目標アドレスを含む前記元および新バージョンの共通関数ユニットの開始アドレス間の第１の差異を用い、更に第１および第２計算可能命令を含む前記共通関数ユニットの開始アドレス間の第２の差異を用いて、前記第１命令値を修正することを含む、方法。
【請求項２７】
請求項１８記載の方法において、前記コードのユニットは、関数ユニットを含む、方法。
【請求項２８】
請求項２７記載の方法において、前記第１命令値を発生するステップは、前記第１計算可能命令の現命令アドレスと、前記第１計算可能命令の目標アドレスとの間の差異を発生するステップを含む、方法。
【請求項２９】
請求項２７記載の方法において、前記第２命令値を発生するステップは、
前記第１計算可能命令の現命令アドレスと、前記第１計算可能命令の目標アドレスとの間の差異を発生するステップと、
前記新バージョンの第１共通関数ユニットの開始アドレスと、前記元バージョンの対応する第１共通関数ユニットの開始アドレスとの間の差異を発生するステップと、
前記新バージョンの第２共通関数ユニットの開始アドレスと、前記元バージョンの対応する第２共通関数ユニットの開始アドレスとの間の差異を発生するステップと、
を含む、方法。
【請求項３０】
請求項１８記載の方法において、前記コードのユニットは、データ・ユニットを含み、前記命令はデータ・ポインタを含む、方法。
【請求項３１】
請求項１８記載の方法において、前記元および新バージョンに共通の前記コードのユニットは共通データ・ユニットであり、前記第１命令は第１データ・ポインタを含み、前記第２命令は第２データ・ポインタを含み、前記第１命令値は第１データ・ポインタ値を含み、前記第２命令値は第２データ・ポインタ値を含み、前記第２命令値の発生は、前記第１および第２データ・ユニットの開始アドレス間の差異を用いて前記第１データ・ポインタ値を修正することにより、第２データ・ポインタ値を発生することを含む、方法。
【請求項３２】
請求項１８記載の方法であって、更に、前記元ファイルおよび前記新ファイルの修正バージョン間でファイルの差別化を行い、差異ファイルを発生するステップを含む、方法。
【請求項３３】
請求項３２記載の方法であって、更に、
前記差異ファイルを携帯処理システムに転送するステップと、
前記携帯処理システムにおいて、前記差異ファイルを用いて前記新ファイルの一バージョンを発生するステップと、
を備えている、方法。
【請求項３４】
請求項３３記載の方法であって、更に、
共通関数ブロックを形成するために、前記コードのユニットの共通関数ユニットを併合するステップと、
共通データ・ブロックを形成するために、前記コードのユニットの共通データ・ユニットを併合するステップと、
前記携帯処理システムにおいて前記新ファイルのバージョンの発生に用いるために、前記共通関数ブロックおよび前記共通データ・ブロックをエンコードするステップと、
を備えている、方法。
【請求項３５】
電子ファイル間の差異を判定するための方法であって、
電子ファイルの元バージョンおよび新バージョンを受信するステップと、
前記元および新バージョン間で共通の第１および第２の関数ユニットを特定するステップであって、前記元バージョンにおける第１関数ユニットは第１計算可能命令を含み、前記新バージョンにおける第２関数ユニットは第２計算可能命令を含む、ステップと、
前記元および新バージョン間で共通の第３および第４の関数ユニットを特定するステップであって、前記元バージョンにおける第３関数ユニットは前記第１計算可能命令に対応する第１目標アドレスを含み、前記新バージョンにおける第４関数ユニットは、前記第２計算可能命令に対応する第２目標アドレスを含む、ステップと、
前記第２計算可能命令から、第２命令値を発生するステップと、
前記第１計算可能命令の第１命令値を前記第２命令値と置換するステップと、
前記第２命令値をもつ前記第１命令を含む前記元ファイルの修正バージョンを発生するステップと、
を備えている、方法。
【請求項３６】
請求項３５記載の方法において、前記第２命令値を発生するステップは、前記第３および第４関数ユニットの開始アドレス間の第１の差異を用い、更に前記第１および第２関数ユニットの開始アドレス間の第２の差異を用いて、前記第１命令値を修正するステップを含む、方法。
【請求項３７】
請求項３５記載の方法であって、更に、
前記元および新バージョン間で共通の第１および第２コード・セグメントを特定するステップであって、前記元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、前記新バージョンにおける第２コード・セグメントは第２データ・ポインタを含む、ステップと、
前記元および新バージョン間で共通の第１および第２データ・ユニットを特定するステップであって、前記元バージョンにおける第１データ・ユニットは、前記第１データ・ポインタに対応する第１目標アドレスを含み、前記新バージョンにおける第２データ・ユニットは、前記第２データ・ポインタに対応する第２目標アドレスを含む、ステップと、
前記第２データ・ポインタから第２データ・ポインタ値を発生するステップと、
前記第１データ・ポインタの第１データ・ポインタ値を前記第２データ・ポインタ値と置換するステップと、
前記第２データ・ポインタ値をもつ前記第１データ・ポインタを含む前記元ファイルの修正バージョンを発生するステップと、
を備えている、方法。
【請求項３８】
請求項３７記載の方法において、前記第２データ・ポインタ値を発生するステップは、現データ・ポインタが指し示す前記元バージョンにおけるデータ・セクションの開始アドレスと、前記新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を発生するステップを備えている、方法。
【請求項３９】
請求項３５記載の方法であって、更に、共通関数ブロックを形成するために共通関数ユニットを併合するステップを備えている、方法。
【請求項４０】
請求項３５記載の方法であって、更に、共通データ・ブロックを形成するために共通データ・ユニットを併合するステップを備えている、方法。
【請求項４１】
請求項３５記載の方法であって、更に、前記元ファイルおよび前記新ファイルの更新バージョンを用いて差異ファイルを発生するステップを備えている、方法。
【請求項４２】
請求項４１記載の方法であって、更に、
前記差異ファイルを携帯処理システムに転送するステップと、
前記携帯処理システムにおいて、前記差異ファイルを用いて前記新ファイルの一バージョンを発生するステップと、
を備えている、方法。
【請求項４３】
実行可能命令を含むコンピュータ読み取り可能媒体であって、処理システムにおいて実行すると、
コード・ライン削除、コード・ライン追加、およびコード・ライン修正のうち少なくとも１つから生じたアドレスのずれに対応する前記元および新バージョン間の差異を特定し、
前記元バージョンのテキスト・セクションと前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、前記元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通なテキスト・セクションにおいて前記特定した差異を除去し、
修正した目標アドレスを有する命令を含む前記元ファイルの修正バージョンを発生する、
ことによって、電子ファイルの元バージョンと新バージョンとの間のコード化差異を含む差異ファイルのサイズを縮小する、コンピュータ読み取り媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
開示する実施形態は、差異ファイルを用いた電子ファイルの更新に関する。
【背景技術】
【０００２】
本願は、２００２年５月１３日に出願した米国特許出願第１０／１４６，５４５号に関係がある。
プロセッサ、マイクロプロセッサ、および／または演算装置上で実行し、一定の機能を提供するソフトウェアは、時と共に変化することが多い。この変化は、ソフトウェア・ファイルにおけるバグ、即ち、誤りを訂正する必要性、発展する技術に合わせる必要性、または新たな特徴を追加する必要性等、様々な必要性の結果生じる可能性がある。即ち、移動処理デバイス、例えば、移動ワイヤレス・デバイス上で動作する埋め込みソフトウェア・コンポーネントは、多数のソフトウェア・バグを含むことが多く、訂正が必要である。ソフトウェアは、人が読むことができる情報相互交換用アメリカ標準コード（ＡＳＣＩＩ：American Standard Code for Information Interchange）の平文ファイルまたは二進コードの形態の１つ以上のファイルを含む。ソフトウェア・ファイルは、更に小さな単位に分割することができ、これらは多くの場合モジュールまたはコンポーネントと呼ばれている。
【０００３】
移動処理デバイスのような、プロセッサを用いた携帯用デバイスは、リアル・タイムのオペレーティング・システム（ＲＴＯＳ）を含むのが通例であり、このデバイスのソフトウェア・コンポーネントは全て、単一の大型ファイルとしてリンクされている。更に、これらの移動ワイヤレス・デバイスには、ファイル・システム支援が設けられていないのが通例である。加えて、単一の大型ファイルは、無線、赤外線、またはシリアル・リンクのような低速通信リンクを用いて、デバイス内に予めロードするか、埋め込む必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
低速通信リンクを通じて移動ワイヤレス・デバイスの大きなファイルを更新する場合の障害には、更新したファイルをデバイスに配信する際に伴う時間、帯域幅、およびコストが含まれる。大型ファイルを移動処理デバイスに配信する問題に対する既存の解決策の１つに、圧縮の使用が含まれる。一般に既存の圧縮アルゴリズムが数多く用いられているが、しかしながら、多くの場合、圧縮したファイルでさえも、低速でコストがかかる狭帯域通信リンクを通じてデバイスにダウンロードするには大き過ぎる。
【０００５】
ファイルを更新するための別の典型的な解決策では、差異プログラムを用いて、改訂したファイルが元のファイルとどれくらい異なるかについての記述を生成する。このような差異データを生成する差異プログラムが入手可能である。しかしながら、圧縮と同様、これらの差異プログラムを用いて生成した差異ファイルは、関連する通信プロトコルによる転送には大き過ぎる場合もあり得る。
【図面の簡単な説明】
【０００６】
【図１】図１は、一実施形態の下における、ファイル差別化および更新を示すブロック図である。
【図２】図２は、図１の実施形態の下における、デルタ・ファイルの発生のフロー図である。
【図３】図３は、実行可能ファイルの元バージョンおよび新バージョンを示すブロック図である。
【図４】図４は、図１および図２の実施形態の下において、電子ファイルの異なるバージョンを前処理するためのフロー図である。
【図５】図５は、図４の実施形態の下において、電子ファイルの異なるバージョンのコード（テキスト）セクションを前処理するためのフロー図である。
【図６】図６は、図５の実施形態の下において、電子ファイルの元のバージョンのコード（テキスト）セクションに新たな目標アドレス値を発生するためのフロー図である。
【図７】図７は、一実施形態の下における、ファイルの元バージョンおよび新バージョンのブロック図であり、電子ファイルの元バージョンのコード（テキスト）セクションに対する新たな目標アドレス値の発生を参照して記述した異なるアドレス（よび対応する標記）を示す。
【図８】図８は、図４の実施形態の下において、電子ファイルの元および新バージョンのデータ・セクションを前処理するためのフロー図である。
【図９】図９は、図８の実施形態の下において、電子ファイルの元バージョンのデータ・セクションに新データ・ポインタ値を発生するためのフロー図である。
【図１０】図１０は、一実施形態の下における、ファイルの元バージョンおよび新バージョンのブロック図であり、電子ファイルの元バージョンに新データ・ポインタ値を発生する際に用いる、異なるアドレス（および対応する標記）を示す。
【図１１】図１１は、図４の実施形態の下における、共通ファイル・ユニットのヒント融合(hint merging)のフロー図である。
【図１２】図１２は、図４の実施形態の下における、共通データ・ユニットのヒント融合のフロー図である。
【発明を実施するための形態】
【０００７】
図面においては、同一の参照番号は、同一または実質的に同様の要素またはアクトを特定するものとする。いずれの特定の要素またはアクトであってもその論述を容易に特定するために、参照番号における最上位桁は、当該要素が最初に紹介される図番を示すこととする（例えば、要素１２４は、図１において初めて紹介され、図１に関して論じられるものとする）。
【０００８】
元ファイルおよび新ファイル間の差異ファイル発生の一部として、元ファイルおよび新ファイルを前処理するシステムおよび方法を提供する。この前処理は、差異ファイルのサイズの一層の縮小に対応する。ファイル・バージョン間のソフトウェア／実行可能な変更は、ソース・コード変更と定める主変更／論理変更、および二次的変更を含む。二次的変更は、一般に、主変更から生じ、ソフトウェア・コンパイラ／リンカ・ユーティリティによって発生する。二次的変更は、アドレス変更、ポインタ目標アドレス変更、ならびに主変更から生じソフトウェア・コンパイラ／リンカ・ユーティリティによって発生したアドレス・オフセットの変更を含む。提供する前処理システムおよび方法は、ファイル・バージョン間において近似規則を用いて、二次的変更を除去／削減し、これらの変更の除去に関する情報を、対応する差異ファイルの上方にエンコードする。
【０００９】
電子ファイルの２バージョン間の差異ファイルを生成するシステムおよび方法について、これより詳細に説明する。このファイル生成を、ここでは、ファイル差別化(file differencing)と呼ぶことにする。図１は、一実施形態の下において行われるファイル差別化および更新を示すブロック図である。ファイル差別化および更新は、差別化コンポーネントおよび更新コンポーネントを含む。差別化コンポーネントは、ここではファイル差異発生部と呼び、第１のプロセッサを用いたシステムまたはコンピュータ・システムにおいて、電子ファイルの元バージョンおよび新バージョンから、差異ファイルを発生する。更新コンポーネントは、ここでは更新発生部と呼び、第２のプロセッサを用いたシステムまたはコンピュータ・システム上で、差異ファイルと、元ファイルのホストされたコピー(hosted copy)とを用いて、新ファイルのコピーを発生する。
【００１０】
以下の説明では、本発明の実施形態の完全な理解が得られ、それを実施可能な説明を行うために、多数の具体的な詳細を導入する。しかしながら、本発明は、これら具体的な詳細の１つ以上が無くとも、または他のコンポーネント、システム等を用いても実施可能であることを、当業者は認めよう。その他の場合では、周知の構造または動作については、本発明の特徴を曖昧にするのを避けるために、示さないか、または詳細には説明しない。
【００１１】
図１を参照すると、第１コンピュータ・システム１０２および第２コンピュータ・システム１０４が通信経路１０６を通じて通信する。これらのコンピュータ・システム１０２および１０４は、当技術分野では周知のように、共に動作する計算コンポーネントおよびデバイスのいずれかの集合体を含む。コンピュータ・システム１０２および１０４は、更に大きなコンピュータ・システムまたはネットワーク内部におけるコンポーネントまたはサブシステムであることも可能である。
【００１２】
通信経路１０６は、コンピュータ・システム１０２および１０４間でファイルを伝達または転送する何らかの媒体を含む。したがって、この経路１０６は、ワイヤレス接続、有線接続、および混合ワイヤレス／有線接続を含む。また、通信経路１０６は、ローカル・エリア・ネットワーク（ＬＡＮ）、市内エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、特定企業のネットワーク、オフィス間またはバックエンド(backend)ネットワーク、およびインターネットを含むネットワークへの結合部または接続部も含む。更に、通信経路１０６は、フロッピ・ディスク、ハード・ディスク・ドライブ、およびＣＤ−ＲＯＭのような、着脱可能な固定媒体、ならびに電話回線、バス、および電子メール・メッセージを含む。
【００１３】
第１通信システム１０２は、電子ファイルの元のバージョン即ち旧バージョンおよび新バージョン１１２を受信する。新ファイル１１２は、一般に、元ファイル１１０の更新または改訂バージョンであるが、そのように限定される訳ではない。電子ファイル１１０および１１２は、ソフトウェア・ファイルを含み、ダイナミック・リンク・ライブラリ・ファイル、共有オブジェクト・ファイル、埋め込みソフトウェア・コンポーネント（ＥＢＳＣ）、ファームウェア・ファイル、実行可能ファイル、１６進データ・ファイルを含むデータ・ファイル、システム・コンフィギュレーション・ファイル、ならびに個人使用データを含むファイルを含むが、これらに限定されるのではない。いずれの形式のファイルもバイト・ストリームと見なすことができるので、以後、文脈に応じて、ファイルをバイト・ストリームと記述できることとする。
【００１４】
ファイル差異発生部１１４のコンポーネントは、新ファイル１１２を受信し、これを元ファイル１１０と比較し、以下に説明するように、比較したファイル間の差異を計算する。これらの差異は、比較したファイル間のバイト・レベルでの差異を含むが、そのように限定されるのではない。ファイル差異発生部１１４は、比較の間に、差異ファイル１１６を発生する。ここでは、差異ファイル１１６をデルタ・ファイル１１６と呼ぶ。
【００１５】
一実施形態のファイル差異発生部１１４は、ホスト・コンピュータ・システム１０２のコンポーネント間で結合を行い、ここで、コンポーネントは、プロセッサ、少なくとも１つのコントローラ、少なくとも１つのメモリ・デバイス、および少なくとも１つのバスのうち少なくとも１つを含むが、そのように限定されるのではない。一実施形態のファイル差発生部１１４のコンポーネントは、少なくとも１つの前処理サブシステム１２４と、少なくとも１つの差別化サブシステム１３４とを含む。前処理サブシステム１２４のことをプリプロセッサ１２４も呼び、少なくとも１つの前処理アルゴリズム、プログラム、またはルーチンの制御の下で実行する少なくとも１つのプロセッサを含む。同様に、差別化サブシステム１３４は、少なくとも１つの差別化アルゴリズム、プログラム、またはルーチンの制御の下で実行する少なくとも１つのプロセッサを含む。
【００１６】
デルタ・ファイル１１６の内容は、新ファイル１１２と元ファイル１１０との間の差異の効率的な表現を備えている。デルタ・ファイル１１６は、２００２年５月１３日に出願され、"Byte-Level File Differencing and Updating Algorithms"（バイト・レベルにおけるファイル差別化および更新アルゴリズム）と題する米国特許出願、出願番号第１０／１４６，５４５号に記載されているように、関連するファイルの新または現バージョンと当該ファイルの以前のバージョンとの間の差異を表す、交換および／または挿入動作の実際のデータと共に、メタ・データを含む。ファイル差異発生部１１４は、最小数のバイトおよび予め規定したフォーマットまたはプロトコルを用いて、元１１０および新１１２ファイル間のいずれの差異をも、デルタ・ファイル１１６内に供給することによって、空間について最適化したデルタ・ファイルが得られる。
【００１７】
デルタ・ファイル１１６は、通信経路１０６を通じて、別の処理システム１０４に転送または送信される。転送の前に、当技術分野では周知の圧縮技法を用いて、デルタ・ファイル１１６を圧縮すると良いが、そのように限定されるのではない。受信システム１０４上にホストされた更新発生部１１８は、デルタ・ファイル１１６を、ホストされた元ファイル１１０Ｈと共に用いて、新ファイル１１２Ｃのコピーを発生即ち作成する。次いで、新ファイル１１２のこのコピーを用いて、改訂または更新の目標とするクライアント・デバイス上にホストされた元ファイル１１０Ｈを更新する。この更新プロセスの完了時には、第２コンピュータ・システム上に格納されている新ファイルは、第１コンピュータ・システム１０２において受信した新ファイル１１２と同一となっている。
【００１８】
元ファイルと新ファイルとの間の差異は、新ファイルよりも小さいのが通例であり、新ファイル全体の代わりに差異を送信し格納すれば、格納および送信の大きな節約に至る。これは、プログラムを記憶しており、通例低速で費用がかかる可能性がある接続、例えば、ワイヤレスまたはセルラ接続を介してプログラムを更新する移動電子デバイス（クライアント・デバイス）には特に重要である。デルタ・ファイルのサイズが縮小されることにより、多数の改良が得られ、その１つには、デルタ・ファイルをクライアント・デバイスに送信するために必要な帯域幅の縮小が含まれる。ファイルの小型化は、転送に必要な帯域幅が少なくて済むことを意味する。また、ファイルの小型化により、送信に必要な時間も短縮され、したがって、ファイル転送が中断される虞れが低下し、同時に、受信したファイルにおける送信エラーも低減する。加えて、安全でない接続を介して送信する場合、新たなソフトウェア画像よりも、デルタ・ファイルの方が安全である。これらの改良は全て、顧客の満足度を高めることになる。
【００１９】
図２は、図１の実施形態の下における、デルタ・ファイル発生のフロー図である。動作が開始するのは、ブロック２０４において、第１処理システムまたはコンピュータ・システムにおいて、新ファイルおよび元ファイルを受信したときである。新ファイルおよび元ファイルに対応するマップ・ファイルも受信する。マップ・ファイルは、上位テキスト・ファイルであり、ソフトウェア画像の各シンボルの開始アドレスおよびサイズを含み、シンボルの例には、関数およびグローバル変数が含まれる。マップ・ファイルは、コンパイラ／リンカ・ユーティリティによって出力され、ログ・ファイル、シンボル・ファイル、および／またはリスト・ファイルとしても知られている。
【００２０】
ブロック２０６において、新ファイルと元ファイルの内容間において前処理動作が行われ、２つのファイルの内容間で、共通セグメントおよび単純なパターンを識別する。一般に、前処理は、識別した共通セグメントおよびパターンを用いて、新ファイルおよび元ファイル間における二次変更を削減／除去する。一実施形態の前処理は、論理的な変更に伴うアドレスのずれによって生ずる元ファイルおよび新ファイル間の変更を削減および／または除去することを含む。これについては以下で説明するが、そのように限定されるのではない。つまり、この前処理は、二次的な変更を含む、ファイルの共通セグメント間の差異を削減することにより、差異計算の効率を高めるのである。
【００２１】
前処理に続いて、ブロック２０８において、新ファイルと修正した元ファイルとの間で、バイト・レベルの差異を計算する。ブロック２１０において、計算した差異をコード化し併合し、既定のエンコーディング・フォーマットにしたがってデルタ・ファイルを発生する。次いで、ブロック２１２において、当技術分野では周知のように、デルタ・ファイルを最適化して、可能であれば、更にファイル・サイズを縮小し、ブロック２１４において、最適化したデルタ・ファイルを供給する。
【００２２】
前述のように、前処理動作は、新ファイルおよび元ファイルの内容間で行われ、２つのファイルの内容間における共通セグメントおよび単純パターンを識別する。この共通セグメントおよび単純パターンの知識を用いて、二次的な変更を削減／除去することにより、全体的な性能向上(gain)が得られる。
【００２３】
前述のように、システムとクライアント・デバイスとの間における電子ファイルまたはソフトウェア・アップグレードの送信は、特に、低帯域幅チャネルを通じて行われる場合、大量の時間がかかる可能性がある。一例に、セルラ電話機のソフトウェア・アップグレードがある。セルラ・ワイヤレス結合を通じて新および元ソフトウェア・バージョン間のバイト・レベルのファイル差異即ち変更部を送ることが、典型的な慣例になっている。実行可能ファイルの新バージョンおよび元バージョン間の差異は、それらの対応するソース・ファイル間の差異よりも複雑であるので、多大な転送時間が生ずる。
【００２４】
新および元ファイル・バージョン間におけるこれら複雑な差異が生ずるのは、部分的に、ソース・ファイルにおける小さな変更によって、実行可能ファイル全体を通じて主要な変更が導入される場合が多いからである。一例として、実行可能ファイルに導入される変更には、２つの主な種類の変更、即ち、主変更および二次的変更を含み。主変更は、論理的変更とも呼ばれ、元ファイルからのソース・コード・ラインの削除、新ファイルへのソース・コード・ラインの加入、およびソース・コード・ラインの修正によって生ずるソース・コードの変更である。二次的変更は、主変更によって生ずる、およびソフトウェア・コンパイラ／リンカ・ユーティリティが発生するアドレスの変更、ポインタ・目標・アドレスの変更、およびアドレス・オフセットの変更を含むと定めるが、これらに限定されるのではない。以下で説明する前処理ルーチンは、二次的変更を除去／削減し、これらの変更の除去に関連する情報を、対応するデルタ・ファイルの情報にエンコードする。
【００２５】
実行可能ファイルはコード（テキスト）セクションおよびデータ・セクションを含むと想定して、実行可能ファイルに導入される二次的変更の分析が開始する。図３は、実行可能ファイルの元Ｖ１および新Ｖ２バージョンを示すブロック図３００である。元Ｖ１および新Ｖ２バージョンは、双方とも、コード（テキスト）セクション３１０および３２０、ならびにデータ・セクション３１２および３２２を含む。新バージョンＶ２が元バージョンＶ１と相違するのは、新バージョンＶ２は、サイズ０ｘ５００の新コード３０２の追加ブロックを含むことである。新コード３０２のブロックの存在により、２種類の二次的変更が導入される。
【００２６】
第１の種類の二次的変更は、新バージョンＶ２のコード（テキスト）セクション３２０に生じ、その結果、分岐命令ＢＲＡＮＣＨが異なる分岐変位を有することになる。これは、相対アドレスまたは分岐オフセットとも呼ばれ、分岐命令ＢＲＡＮＣＨのアドレスと目標命令アドレスＴＡＲＧＥＴとの間に新コード３０２のブロックを追加したことの結果である。この例では、目標命令アドレスは０ｘ１０００であり、分岐命令アドレスは０ｘ３０００であるので、元バージョンに０ｘ２０００（０ｘ３０００−０ｘ１０００）の分岐変位が生ずる。分岐命令アドレスと目標命令アドレスとの間に新コードのブロック（サイズは０ｘ５００）を追加することによって、分岐命令アドレスが０ｘ３５００（０ｘ３０００＋０ｘ５００）に変化する。したがって、新バージョンＶ２における分岐変位は、０ｘ２５００（０ｘ３５００−０ｘ１０００）に変化する。
【００２７】
第２の種類の二次的変更は、新バージョンＶ２のデータ・セクション３２２に生じ、対応するデータ・エリアの絶対アドレスを格納する、データ・ポインタＰＯＩＮＴＥＲ、即ち、データ・ポインタ値に変更が生ずる。このデータ・ポインタ値の変更は、新コード３０２をコード（テキスト）セクションに追加した結果である。新コード３０２は、データ・セクション３２２の前にある、元バージョン内のポイントに挿入される。したがって、元バージョンでは０ｘ８０００であるデータ・ポイント値は、新バージョンでは０ｘ８５００（０ｘ８０００＋０ｘ５００）に変化する。
【００２８】
ソフトウェアの開発が増々複雑になるに連れて、二次的変更が実行可能ファイル全体に広がり、バイト・レベルでのファイルの差別化の関連で考えると、二次的変更が主変更よりも数において勝る可能性があるところまで来ている。以下に説明する前処理ルーチンは、ファイルの元バージョンおよび新バージョン間の関係を用いて、二次的変更に関連する差異に関してデルタ・ファイルにエンコードする情報量を削減する。情報を最小限に抑えれば、バイト・レベルで差別化および再生を行う際に、カスケーディング計算(cascading computation)の効果が得られ、デルタ・ファイルのサイズを縮小することができる。
【００２９】
概略的に、一実施形態の前処理ルーチンは、少なくとも１つの近似ルーチンと、デルタ・ファイル・サイズを最小化する際に用いる少なくとも１つの併合ルーチンとを含む。近似ルーチンは、テキスト（コード）およびデータ・モデルの想定にしたがって、二次的変更を削減／除去するように機能する。併合ルーチンは、ヒント併合ルーチン(hint merging routine)とも呼ばれ、新バージョンを受信するデバイスへの転送には、最小コスト・レベルでモデル情報をエンコードする。モデル情報は、前述のように、デバイスにおいて新バージョンを復元する際に用いられるが、そのように限定されるのではない。
【００３０】
図４は、図１および図２の実施形態の下において、電子ファイルの異なるバージョンを前処理するためのフロー図２０６である。ファイルの新および元バージョンを受信すると、ブロック４０２において、共通関数ユニットおよび共通データ・ユニットを、関連するマップ・ファイルから抽出する。ブロック４０４において、共通関数ユニットを併合して、共通関数ブロックを形成する。これについては、図１１を参照して以下で詳しく説明する。同様に、ブロック４０６において、共通データ・ユニットを併合して共通データ・ブロックを形成する。これについては図１２を参照して以下で詳しく説明する。次いで、前処理システムの前処理ルーチンは、ブロック４０８において、新および元ファイルのコード（テキスト）セクションを前処理する。これについては、図５、図６、および図７を参照しながら以下で説明する。続いて、または同時に、前処理ルーチンは、ブロック４１０において、新および元ファイルのデータ・セクションを前処理する。これについては、図８、図９、および図１０を参照しながら以下で説明する。ブロック４１２において、共通関数ブロックおよび共通データ・ブロックをエンコードし、元ファイルの修正バージョンを出力し、バイト・レベルのファイル差別化を実行する際に用いる。
【００３１】
図５は、図４の実施形態の下において、電子ファイルの異なるバージョンのコード（テキスト）セクションを前処理するためのフロー図４０８である。一般に、ファイルのコード（テキスト）セクションは、１つ以上の関数ユニットまたはブロックで構成されている。一実施形態のコード（テキスト）セクションの前処理は、ブロック５０２において、元および新ファイルの各関数ユニットの開始および終了アドレスの特定から開始する。元ファイルの関数ユニットをここでは「元関数ユニット」と呼び、新ファイルの関数ユニットをここでは「新関数ユニット」と呼ぶ。機能ユニットの開始および終了アドレスを特定するには、マップ・ファイルを用いるが、そのように限定されるのではない。
【００３２】
次に、ブロック５０４において、プリプロセッサは一意のインデックスまたはインデックス値を各一意の関数ユニットに割り当てる。このインデックス値の一意の関数ユニットへの割り当ては、元および新ファイル・バージョン双方に共通な関数ユニットの識別を支援する。その結果、ファイルの元および新バージョン双方に同じ関数ユニットが見つかった場合、その関数には共通のインデックス値を割り当てるが、実施形態はそのように限定されるのではない。
【００３３】
一例として、元関数ユニットＦ１、Ｆ２、Ｆ３、およびＦ４を含む元ファイル・バージョンと、新関数ユニットＦ１、Ｆ２、Ｆ３、およびＦ５を含む新ファイル・バージョンについて考える。プリプロセッサがインデックス値１、２、３、４、および５を用いて関数ユニットＦ１、Ｆ２、Ｆ３、Ｆ４、およびＦ５をそれぞれインデックス化（index）する場合、元ファイル・バージョンには以下の表が作成される。
【００３４】
【表１】
2010176699.tif 000003
【００３５】
同様に、新ファイル・バージョンには以下の表が作成される。
【００３６】
【表２】
2010176699.tif 000004
【００３７】
これらの表双方において、開始アドレス（startAddress）は、一般に、対応する関数ユニットの開始アドレスと定められ、したがって、「開始アドレスＶ１」は、元ファイルの関数ユニットの開始アドレスであり、「開始アドレスＶ２」は、新ファイルの関数ユニットの開始アドレスである。更に、終了アドレス（endAddress）は、関数ユニットのサイズに、関数ユニットの開始アドレスを加算することによって発生するので、
【００３８】
【数１】
2010176699.tif 000005
【００３９】
となるが、実施形態はそのように限定されるのではない。その結果、終了アドレスＶ１は、元ファイルの関数ユニットの終了アドレスと定められ、一方終了アドレスＶ２は新ファイルの関数ユニットの終了アドレスと定められる。この終了アドレスの定めは、ここではデータ・ユニットにも適用されるが、そのように限定されるのではない。
【００４０】
続いて、プリプロセッサは、ブロック５０６において、前述の表からのインデックス値、開始アドレス、および終了アドレスの情報を用いて、共通関数ユニットのHintTableを発生する。HintTableは、１つのテーブルに組み入れた共通関数ユニットの情報を含み、元ファイル・バージョン（Ｖ１）の元関数ユニットのインデックス値、開始および終了アドレス、ならびに新ファイル・バージョン（Ｖ２）の新関数ユニットの開始および終了アドレスを含む。HintTableの情報を配列するには、当技術分野では周知の技術がいくつでも用いられる。
【００４１】
【表３】
2010176699.tif 000006
【００４２】
続いて、プリプロセッサは、ブロック５０８において、目標アドレスを含む元関数ユニットの命令に対する新目標アドレス値の発生に進む。図６は、図５の実施形態の下において、電子ファイルの元バージョンのコード（テキスト）セクションに新目標アドレス値を発生するためのフロー図５０８である。
【００４３】
新目標アドレス値の発生について説明するにあたり、以下のような特定の標記を用いて、関数ユニットに伴う種々のアドレスについて説明する。全般的に、命令アドレスは、ここでは「addr」という標記を用いて示す。したがって、「addrV1」は、元関数ユニットにおける命令アドレスを示し、一方「addrV2」は、新関数ユニットにおける命令アドレスを示す。全般的に、目標アドレスは、ここでは、「targetAddr」という標記を用いて示す。したがって、「targetAddrV1」は、元関数ユニットにおける目標アドレスを示し、一方「targetAddrV2」は、新関数ユニットにおける対応の目標アドレスを示す。更に、targetAddrV1を含む元関数ユニットの開始アドレスは、ここでは、「targetStartAddrV1」という標記を用いて参照し、targetAddrV1を含む元関数ユニットの開始アドレスであり、TargetAddrV2を含む新関数ユニットの開始アドレスは、ここでは、「targetStartAddrV2」という標記を用いて参照する。
【００４４】
図７は、一実施形態の下における、ファイルの元バージョンＶ１および新バージョンＶ２のブロック図であり、電子ファイルの元バージョンのコード（テキスト）セクションに対する新目標アドレス値の発生を参照して説明する異なるアドレス（および対応する標記）を示す。第１の共通関数ユニットＣＦＵ  Ａおよび第２の共通関数ユニットＣＦＵ  Ｂは、元Ｖ１および新Ｖ２バージョン双方に共通である。元バージョンＶ１の共通関数ユニットＣＦＵ  Ｂは、開始アドレスstartAddrV1を有し、命令アドレスaddV1に位置する、計算可能命令cal＿insAを含む。計算可能命令については、以下で説明する。元バージョンＶ１の共通関数ユニットＣＦＵ  Ａは、開始アドレスtargetStartAddrV1を有し、計算可能命令cal＿insAの目標アドレスtargetAddrV1を含む。
【００４５】
同様に、新バージョンＶ２の共通関数ユニットＣＦＵ  Ｂは、開始アドレスstartAddrV2を有し、命令アドレスaddrV2に位置する計算可能命令cal＿insBを含む。新バージョンＶ２の共通関数ユニットＣＦＵ  Ａは、開始アドレスtargetStartAddrV2を有し、計算可能命令cal＿insBの目標アドレスtargetAddrV2を含む。
【００４６】
図６を参照すると、新目標アドレス値の発生は、ブロック６０２において元ファイル・バージョンの元関数ユニットｊから、前処理が済んでいない計算可能命令を呼び出すことから開始し、ｊは、カウンタ値であり、１の値に初期化され、以後ｊ＝ｎになるまで１回毎に１ずつ増分し、ｎは、元バージョンと新バージョンとの間の共通関数ユニットの総数である。
【００４７】
次に、ブロック６０４において、以下のようにして、計算可能命令の現目標アドレスを発生または計算する。例えば、プログラム・カウンタに関連するジャンプ命令や、ロード／格納命令のような、目標アドレスを含むいずれの命令についても、目標アドレスを計算するには、現命令アドレスおよび対応する命令のデコーディングを用いる。先に引用した表記を用いると、現目標アドレスの計算は、次のようになる。
【００４８】
【数２】
2010176699.tif 000007
【００４９】
あるいは、
【００５０】
【数３】
2010176699.tif 000008
【００５１】
値[targetAddrV1-addrV1]がわかっていれば、以下のように、対応するエンコーディング方式に基づいて命令も計算することができる。
【００５２】
【数４】
2010176699.tif 000009
【００５３】
この種の命令を計算可能命令と呼び、ここでは、「cal＿ins」で示し、値(targetAddrV1-addrV1)を計算可能命令の値、または「命令値」と呼ぶ。
共通関数ユニットにおける計算可能命令に対して、一実施形態のプリプロセッサは、元バージョンにおける命令値を元関数ユニットの開始アドレスおよび新関数ユニットの開始アドレスと共に用いて、共通関数ユニットの新バージョンにおける命令値を発生する。したがって、先に引用した表記を用いると、元バージョンにおける命令値(targetAddrV1-addrV1)、startAddrV1、targetStartAddrV1、startAddrV2、およびTargetStartAddrV2を用いて、新バージョン(targetAddrV2-addrV2)における命令値を発生または計算する。
【００５４】
したがって、元ファイルの目標アドレス(targetAddrV1)の発生時に、ブロック６０６において、プリプロセッサはHintTableにアクセスして、ｋ、目標アドレスtargetAddrV1を含む元ファイル・バージョンの関数ユニットを特定する。元関数ユニットｊおよびその目標とした関数ユニットｋのアイデンティティを用いて、プリプロセッサは、ブロック６０８において、HintTableからstartAddrV1、startAddrV2、targetStartAddrV1、およびtargetStartAddrV2を読み出す。
【００５５】
続いて、ブロック６１０において、プリプロセッサは、ここで、以下のようにしてcal＿insBに対する命令値(targetAddrV2-addrV2)を発生し、cal＿insAの命令値と置換する。一実施形態のプリプロセッサは、少なくとも２つの仮定の下で動作するが、そのように限定されるのではない。第１の仮定は、元バージョンおよび新バージョン双方において同じサイズを有する共通関数ユニットは、元および新バージョン双方を通じて同じ命令構造を有し、命令構造は、命令型および命令順序を含むことを仮定する。第２の仮定は、第１の仮定を満たす共通関数ユニットにおけるいずれの計算可能命令についても、当該計算可能命令が関数コールであるとき、または計算可能命令の目標アドレスが、同様に第１の仮定を満たす共通関数ユニットに入るときには、通常以下のように２つの不変式が元および新バージョン双方を通じて成り立つことを仮定する。
【００５６】
【数５】
2010176699.tif 000010
【００５７】
および
【００５８】
【数６】
2010176699.tif 000011
【００５９】
このように、２つの仮定にしたがって、プリプロセッサはブロック６１０において、cal＿insAに対して以下のように新命令値(targetAddrV2-addrV2)を発生する。
【００６０】
【数７】
2010176699.tif 000012
【００６１】
これを、ここでは式１と呼ぶ。
ブロック６１２において、cal＿insAの新命令値を用いて、プリプロセッサは、以下のようにcal＿insAを修正する。
【００６２】
【数８】
2010176699.tif 000013
【００６３】
次いで、元バージョンのアドレスaddrVV1における元命令、cal＿insAを新命令と置換する。
続いて、ブロック６１４において、プリプロセッサは、元関数ユニットｊの計算可能命令の中でまだ前処理が済んでいないものが残っているか否か判定を行う。前処理が未だ済んでいない計算可能命令が残っている場合、プリプロセッサは、ブロック６０２に戻り、別の、あるいは次の未処理の計算可能命令を元関数ユニットｊから読み出し、先に説明したように前処理を続ける。
【００６４】
元関数ユニットｊの計算可能命令全てを処理し終えたとブロック６１４で判定したとき、プリプロセッサは、ブロック６１６において、カウンタｊにおける値が値ｎよりも大きいか否か判定を行う。ｊがｎよりも大きくないという判定は、未だ前処理されていない共通関数ユニットがあることを示すので、ブロック６１８においてカウンタ内の値ｊを１増分し、先に説明したように前処理を続ける。
【００６５】
ｊがｎよりも大きいという判定は、元ファイル・バージョンの関数ユニット全てを前処理し終えたことを示す。したがって、ブロック６２０において、プリプロセッサは、新ファイルの近似バージョンを含む、元ファイルの修正バージョンを出力する。
【００６６】
図４を参照しながら先に説明したように、プリプロセッサおよび近似ルーチンは、テキスト（コード）モデルの仮定にしたがって二次的変更を除去することに加えて、ブロック４１０において、データ・モデルの仮定にしたがって二次的変更を除去するようにも機能する。図８は、図４の実施形態の下において、電子ファイルの元および新バージョンのデータ・セクションを前処理するためのフロー図４１０である。一般に、ファイルのデータ・セクションは、１つ以上のグローバル変数ユニットまたはブロックで構成されており、ここでは「データ・ユニット」と呼ぶ。
【００６７】
一実施形態のデータ・セクションの前処理は、ブロック８０２において、元および新ファイルの各データ・ユニットの開始および終了アドレスの特定から開始する。ここで、元ファイルのデータ・ユニットを「元データ・ユニット」と呼び、新ファイルのデータ・ユニットを「新データ・ユニット」と呼ぶことにする。データ・ユニットの開始および終了アドレスを特定するには、マップ・ファイルを用いるが、そのように限定されるのではない。
【００６８】
次に、ブロック８０４において、前処理は一意のインデックスまたはインデックス値を一意の各データ・ユニットに割り当てる。このインデックス値の一意のデータ・ユニットへの割り当ては、元および新ファイル・バージョン双方に共通のデータ・ユニットの識別を支援する。したがって、ファイルの元および新バージョン双方において同じデータ・ユニットが発見された場合、そのデータ・ユニットには共通のインデックス値を割り当てるが、実施形態はそのように限定されるのではない。インデックス値の一意のデータ・ユニットへの割り当ては、前述したインデックス値の一意の関数ユニットへの割り当てと同じであるが、そのように限定されるのではない。同様に、インデックス値にしたがって編成され、各データ・ユニット毎に開始アドレスおよび終了アドレスを含むテーブルの発生も、前述した元および新ファイル・バージョンの関数ユニットのためのテーブルの発生と同じである。しかしながら、代替実施形態では、当技術分野では周知の技術をいくつでも用いて、インデックス値を割り当て、テーブルを発生することもできる。
【００６９】
続いて、プリプロセッサは、ブロック８０６において、先のテーブルからのインデックス値、開始アドレス、および終了アドレスの情報を用いて、共通データ・ユニットのHintTableを発生する。HintTableは、１つのテーブルに組み立てた共通データ・ユニットの情報を含み、元ファイル・バージョン（Ｖ１）の元データ・ユニットの開始および終了アドレス、ならびに新ファイル・バージョン（Ｖ２）の新データ・ユニットの開始および終了アドレスを含む。HintTableの発生は、共通関数ユニットのHintTableを参照して先に説明した通りであるが、代替実施形態では、当技術分野において周知の技術をいくつでも用いてHintTableを発生することができる。
【００７０】
ブロック８０８において、プリプロセッサは、続いて、元バージョンのデータ・ポインタに対して新データ・ポインタ値を発生する。図９は、図８の実施形態の下において、電子ファイルの元バージョンにおけるデータ・ポインタに、新データ・ポインタ値を発生するためのフロー図８０８である。
【００７１】
データ・ポインタは、データ・ユニットにおけるあるデータを指し示す命令である。新データ・ポインタ値の発生について説明する際にここで用いる表記を、次に示す。データ・ポインタを含む命令のアドレスは、ここでは通常「dataPointer」という表記を用いて示す。したがって、「dataPointerV1」は、元バージョンにおけるdataPointerを示し、一方、「dataPointerV2」は、新バージョンにおけるdataPointerを示す。データ・ポインタによって指し示されているデータを含むデータ・ユニットの開始アドレスを、ここでは、「dataStartAddr」という表記を用いて示す。したがって、「dataStartAddrV1」は、元バージョンにおけるdataStartAddrを示し、一方「dataStartAddrV2」は、新バージョンにおけるdataStartAddrを示す。
【００７２】
図１０は、一実施形態の下におけるファイルの元バージョンＶ１および新バージョンＶ２のブロック図であり、電子ファイルの元バージョンに新データ・ポインタ値を発生する際に用いられる、異なるアドレス（および対応する表記）示す。元Ｖ１および新Ｖ２バージョンは双方とも、コード（テキスト）セグメントおよびデータ・セグメントを含む。データ・セグメントは、元Ｖ１および新Ｖ２ファイル・バージョン双方に共通である、共通データ・ユニットＣＤＵ  Ａを含む。元バージョンＶ１は、コード（テキスト）セグメント内にデータ・ポインタdataPointerV1を含み、これは元バージョンの共通データ・ユニットＣＤＵ  Ａ内のあるデータを指し示す。元バージョンＶ１におけるＣＤＵ  Ａの開始アドレスは、dataStartAddrV1である。同様に、新バージョンＶ２は、コード（テキスト）セグメント内にデータ・ポインタdataPointerV2を含み、これは新バージョンＶ２の共通データ・ユニットＣＤＵ  Ａ内のあるデータを指し示す。新バージョンＶ２におけるＣＤＵ  Ａの開始アドレスは、dataStartAddrV2である。dataStartAddrアドレスは、ファイルの元Ｖ１および新Ｖ２バージョンのソフトウェア画像に関連するマップ・ファイルからのものである。
【００７３】
図９に戻って、新データ・ポインタ値の発生は、ブロック９０２において、元バージョンにおいて前処理が済んでいないデータ・ポインタを特定することから開始する。一実施形態のプリプロセッサは、元バージョンにおけるポインタ値（dataPointerV1)を、dataPointerV1が指し示すデータを含むデータ・ユニットの開始アドレス（dataStartAddrV1)、および新バージョンにおける対応するデータ・ユニットの開始アドレス（dataStartAddrV2)と共に用いて、新バージョンのデータ・ポインタ値（dataPointerV2)を発生する。これについては、以下で述べる。これを行うには、ブロック９０４において、HintTableにアクセスして、ｋ、即ち、dataPointerVV1が指し示すデータを含む元バージョンにおけるデータ・ユニットを特定する。データ・ユニットｋのアイデンティティを用いて、プリプロセッサは、ブロック９０６において、HintTableからdataStartAddrV1およびdataStartAddrV2を読み出す。
【００７４】
続いて、プリプロセッサは、ブロック９０８において、以下のようにして、dataPointerV1を置換するためにデータ・ポインタ値（dataPointerV2）を発生する。一実施形態のプリプロセッサは、データ・ユニットに関する少なくとも２つの追加の仮定の下で動作するが、そのように限定されるのではない。ここでは、これらの仮定を第３および第４の仮定と呼ぶ。第３の仮定は、元バージョンおよび新バージョン双方において同じサイズを有する共通データ・ユニットは、元および新バージョン双方を通じて同じデータ構造を有すると仮定し、データ構造には、型、サイズ、およびデータ変数の順序が含まれる。第４の仮定は、第３の仮定を満たす共通データ・ユニットにおけるいずれのデータ・ポインタについても、以下のように、不変式が全体的に元および新バージョン双方を通じて成り立つことを仮定する。
【００７５】
【数９】
2010176699.tif 000014
【００７６】
このように、第３および第４の仮定に応じて、プリプロセッサは、ブロック９０８において、次のように新データ・ユニットに新データ・ポインタ値（dataPointerV2）を発生する。
【００７７】
【数１０】
2010176699.tif 000015
【００７８】
これをここでは式２と呼ぶ。
ブロック９１０において、データ・ポインタ値dataPointerV2を用いて、プリプロセッサは、元バージョンにおける対応するアドレスにおいて、dataPointerV1をdataPointerV2と置換する。続いて、ブロック９１２において、プリプロセッサは、前処理が済んでいないデータ・ポインタが未だ元データ・ユニットに残っているか否か判定を行う。
【００７９】
前処理が済んでいないまま残っている元データ・ユニットのデータ・ポインタがある場合、プリプロセッサはブロック９０２に戻って、元データ・ユニットから別の、あるいは次の未処理のデータ・ポインタを読み出し、前述のように前処理が続けられる。元データ・ユニットのデータ・ポインタ全てを前処理したとブロック９１２において判定した場合、プリプロセッサは、ブロック９１４において、新ファイルの近似バージョンを含む元ファイルの修正バージョンを出力する。
【００８０】
先にHintTableにおいて用いた、共通関数ユニットおよび共通データ・ユニットの開始および終了アドレスは、異なるファイル・バージョン間において共通ユニットの相対的な位置付けを決定する際にそれらを使用したので、「アルゴリズム・ヒント」または「ヒント」と呼ぶことにする。したがって、ヒントはクライアント・デバイスに転送される。クライアント・デバイスは、前述のように、差異即ちデルタ・ファイルを受信し、デルタ・ファイルおよび元ファイルから新ファイル・バージョンを復元する際にこのファイルを用いる。ヒントの転送は、デルタ・ファイルおよびその他の情報をクライアント・デバイスに転送する際に用いられるのと同じ低帯域幅チャネルを通じて行われるので、一実施形態のプリプロセッサは、ヒントの併合を行い、HintTableの共通関数ユニットおよび共通データ・ユニットを併合するが、前処理アルゴリズムやルーチンの遂行に影響はない。この併合により、ヒントを含むファイルのサイズが縮小し、結果的に、クライアント・デバイスに転送する情報量が減少する。
【００８１】
前述のコード（テキスト）セクションの前処理から得られる共通関数ユニットを用いて、そして図４に戻って、プリプロセッサは、ブロック４０４において、ヒント併合ルーチンまたはアルゴリズムの制御の下で、共通関数ユニットを併合し、共通関数ブロックを形成する。図１１は、図４の実施形態の下における、共通関数ユニットのヒント併合４０４のフロー図である。
【００８２】
同様に、プリプロセッサは、ブロック４０６において、前述のデータ・セクションの前処理から得られた共通データ・ユニットを用いて、共通データ・ユニットを併合し、共通データ・ブロックを形成する。図１２は、図４の実施形態の下における、共通データ・ファイルのヒント併合４０６のフロー図である。共通関数ユニットおよび共通データ・ユニットのヒント併合について順に以下で説明する。
【００８３】
ここでは明確化のために、共通関数ユニットおよび共通データ・ユニットのヒント併合を別個に説明するが、実施形態は、併合に伴う動作をいずれの順序またはいずれの組み合わせでも実行することができる。表記に関して、関数またはデータ・ユニットの開始アドレスを、全体的に、ここでは前述のように表記「startAddress」を用いて示すこととする。したがって、「startAddressV1」は、元関数またはデータ・ユニットの開始アドレスを示し、一方「startAddressV2」は、新関数またはデータ・ユニットにおける対応する開始アドレスを示す。同様に、関数またはデータ・ユニットの終了アドレスを、全体的に、ここでは表記「endAddress」を用いて示すこととする。したがって、「endAddressV1」は、元関数またはデータ・ユニットの終了アドレスを示し、一方「endAddressV2」は新関数またはデータ・ユニットにおける対応する終了アドレスを示す。
【００８４】
図５を参照して先に説明したように、共通関数ユニットのHintTableを発生する。これは、１つのテーブルに組み込まれた共通関数ユニットの情報を含み、元ファイル・バージョンＶ１の元関数ユニットの開始および終了アドレス、ならびに新ファイル・バージョンＶ２の新関数ユニットの開始および終了アドレスを含む。先に提示したHintTableは、共通関数ユニットのヒント併合を説明する際に一例として用いられたが、実施形態はそのように限定されるのではない。
【００８５】
【表４】
2010176699.tif 000016
【００８６】
図４および図１１ならびにHintTableを参照すると、共通関数ユニットのヒント併合４０４の動作は、ブロック１１０２において、プリプロセッサがHintTableのｎ個のエントリ全てを使用可能と印し、カウンタをｊ＝１と設定し、関連するHintTableから関数ユニットｊおよびユニット（ｊ＋１）の元および新バージョンを読み出すことから開始する。この例では、ユニットｊおよびユニット（ｊ＋１）の値は、ヒント・テーブルのインデックス値に対応し、ｊ＝１、２、．．．（ｎ＋１）であるが、そのように限定されるのではない。更に、ｊの値を初期状態において１に等しく設定し、ヒント併合４０４が進展するに連れて、そして共通ユニットを処理するに連れて、当技術分野では周知の方法を用いて、以後増分させていく。したがって、インデックス値１および２（ｊ＋１＝１＋１＝２）と関連付けられている共通関数ユニットの情報を、ブロック１１０２において、呼び出す。
【００８７】
ブロック１１０４において、プリプロセッサは、共通関数ユニットｊの元バージョンＶ１および新バージョンＶ２はサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【００８８】
【数１１】
2010176699.tif 000017
【００８９】
しかし、そのように限定されているのではない。元Ｖ１および新Ｖ２バージョンが異なるサイズのファイルを有する場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９０】
元バージョンＶ１および新バージョンＶ２のサイズが等しい場合、プリプロセッサは、ブロック１１０６において、以下のように、共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【００９１】
【数１２】
2010176699.tif 000018
【００９２】
しかし、そのように限定されているのではない。共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスとは異なる場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９３】
共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一である場合、プリプロセッサは、ブロック１１０８において、共通関数ユニットｊの新バージョンＶ２の終了アドレスが、以下のように、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一か否か判定を行う。
【００９４】
【数１３】
2010176699.tif 000019
【００９５】
しかし、そのように限定されているのではない。共通関数ユニットｊの新バージョンＶ２の終了アドレスが、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスとは異なる場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９６】
共通関数ユニットｊの新バージョンＶ２の終了アドレスが、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一である場合、プリプロセッサは、ブロック１１１０において、共通関数ユニットｊおよび共通関数ユニット（ｊ＋１）の情報を併合して共通関数ブロックを形成し、ユニット（ｊ＋１）のエントリを置換し、ついでユニットｊのエントリに使用不可能と印する。次いで、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９７】
プリプロセッサは、ブロック１１１２において、ｊの値が量（ｎ−１）未満か否か判定を行う。ｊの値が量（ｎ−１）に等しく、全ての関数ユニットを前処理し終えたことを示す場合、動作は、ブロック１１１６に進み、全ての使用可能なエントリを共通関数ブロックとして出力し、そして動作は戻る。ｊの値が量（ｎ−１）未満であり、前処理が済んでいない関数ユニットが残っていることを示す場合、ブロック１１１４において、ｊの値を増分し、動作は、ブロック１１０２に進み、ｊの新しい値に対応する共通関数ユニットの情報を読み出す。次いで、前処理は前述のように続けられる。
【００９８】
以下に、図１１およびHintTableを参照して、共通関数ユニットのヒント併合を伴う例について説明する。動作は、プリプロセッサが３つのエントリ全てを使用可能と印し、HintTableから関数ユニット１および２の元および新バージョンを読み出すことから開始する。次いで、プリプロセッサは、共通関数ユニット１の元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【００９９】
【数１４】
2010176699.tif 000020
【０１００】
HintTableからの実際の値を代入すると、以下のようになる。
【０１０１】
【数１５】
2010176699.tif 000021
【０１０２】
元バージョンＶ１および新バージョンＶ２はサイズが等しいので、プリプロセッサは次に、共通関数ユニット１の元バージョンＶ１の終了アドレスが、次のように、共通関数ユニット２の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１０３】
【数１６】
2010176699.tif 000022
【０１０４】
HintTableからの実際の値を代入すると、以下のように、共通関数ユニット１の元バージョンＶ１の終了アドレスが、共通関数ユニット２の元バージョンの開始アドレスと同一であるという判定が得られる。
【０１０５】
【数１７】
2010176699.tif 000023
【０１０６】
共通関数ユニット１の元バージョンＶ１の終了アドレスは、共通関数ユニット２の元バージョンＶ１の開始アドレスと同一であるので、次に、共通関数ユニット１の新バージョンＶ２の終了アドレスが、以下のように、共通関数ユニット２の新バージョンＶ２の開始アドレスと同一か否かについて判定を行う。
【０１０７】
【数１８】
2010176699.tif 000024
【０１０８】
HintTableからの実際の値を代入すると、以下のように、共通関数ユニット１の新バージョンＶ２の終了アドレスが、共通関数ユニット２の新バージョンＶ２の開始アドレスと同一であるという判定が得られる。
【０１０９】
【数１９】
2010176699.tif 000025
【０１１０】
共通関数ユニット１の新バージョンＶ２の終了アドレスが共通関数ユニット２の新バージョンＶ２の開始アドレスと同一であるという判定に応答して、プリプロセッサは、共通関数ユニット１および共通関数ユニット２の情報を併合し、以下のような共通関数ブロックを形成する。
【０１１１】
【表５】
2010176699.tif 000026
【０１１２】
例を続けると、プリプロセッサは、次に、HintTableから関数ユニット２および３の元および新バージョンを読み出す。プリプロセッサは、共通関数ユニット２の元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始アドレスと終了アドレスとの間の差を取る。
【０１１３】
【数２０】
2010176699.tif 000027
【０１１４】
HintTableからの実際の値を代入すると、次の結果が得られる。
【０１１５】
【数２１】
2010176699.tif 000028
【０１１６】
これは、元バージョンＶ１および新バージョンＶ２のサイズが等しいことを示す。
次に、プリプロセッサは、共通関数ユニット２の元バージョンＶ１の終了アドレスが、以下のように、共通関数ユニット３の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１１７】
【数２２】
2010176699.tif 000029
【０１１８】
HintTableからの実際の値を代入すると、共通関数ユニット２の元バージョンＶ１の終了アドレスは、以下のように、共通関数ユニット３の元バージョンＶ１の開始アドレスとは異なるという判定が得られる。
【０１１９】
【数２３】
2010176699.tif 000030
【０１２０】
共通関数ユニット２の元バージョンＶ１の終了アドレスが、共通関数ユニット３の元バージョンＶ１の開始アドレスと同一ではないので、動作は戻り、共通関数ユニット２および３を併合して共通関数ブロックを形成することは行わない。
【０１２１】
共通関数ユニットを併合した後、前述の例のHintTableの使用可能なエントリは、出力に対して次のようになる。
【０１２２】
【表６】
2010176699.tif 000031
【０１２３】
一実施形態のプリプロセッサは、共通関数ユニットに関して先に説明したのと同様にして、共通データ・ユニットのヒント併合を実行する。図４および図１２を参照すると、共通データ・ユニットのヒント併合４０６の動作は、ブロック１２０２において、プリプロセッサがHintTableのｎ個のエントリ全てに印を付け、カウンタをｊ＝１に設定し、関連するHintTableからデータ・ユニットｊおよび（ｊ＋１）の元および新バージョンを読み出すことから開始する。ユニットｊおよびユニット（ｊ＋１）の値は、ヒント・テーブルのインデックス値に対応し、ここで、ｊ＝１，２，．．．（ｎ−１）であるが、そのように限定されるのではない。
【０１２４】
ブロック１２０４において、プリプロセッサは、共通データ・ユニットｊの元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【０１２５】
【数２４】
2010176699.tif 000032
【０１２６】
しかし、そのように限定されるのではない。元Ｖ１および新Ｖ２バージョンが異なるサイズのファイルを有する場合、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１２７】
元バージョンＶ１および新バージョンＶ２のサイズが等しい場合、プリプロセッサは、ブロック１２０６において、以下のように、共通データ・ユニットｊの元バージョンＶ１の終了アドレスが、共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１２８】
【数２５】
2010176699.tif 000033
【０１２９】
しかし、そのように限定されるのではない。共通データ・ユニットｊの元バージョンＶ１の終了アドレスが共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと異なる場合、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３０】
共通データ・ユニットｊの元バージョンＶ１の終了アドレスが共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一である場合、プリプロセッサは、ブロック１２０８において、共通データ・ユニットｊの新バージョンＶ２の終了アドレスが、以下のように、共通データ・ユニット（ｊ＋１）の新バージョンの開始アドレスと同一か否か判定を行う。
【０１３１】
【数２６】
2010176699.tif 000034
【０１３２】
しかし、そのように限定されるのではない。共通データ・ユニットｊの新バージョンＶ２の終了アドレスが共通データ・ユニット（ｊ＋１）の新バージョンの開始アドレスとは異なる場合、動作はブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３３】
共通データ・ユニットｊの新バージョンＶ２の終了アドレスが共通データ・ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一である場合、プリプロセッサは、ブロック１２１０において、共通データ・ユニットｊおよび共通データ・ユニット（ｊ＋１）の情報を併合して共通データ・ブロックを形成し、ユニット（ｊ＋１）のエントリを置換し、次いで、ユニットｊのエントリに使用不可と印する。次いで、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３４】
プリプロセッサは、ブロック１２１２において、ｊの値が量（ｎ−１）未満か否か判定を行う。ｊの値が量（ｎ−１）と等しく、全ての関数ユニットを前処理し終えたことを示す場合、動作は、ブロック１２１６に進み、HintTable内にある使用可能なエントリを共通データ・ブロックとして出力し、動作は戻る。ｊの値が量（ｎ−１）未満であり、前処理が済んでいない関数ユニットが残っていることを示す場合、ブロック１２１４においてｊの値を増分し、動作はブロック１２０２に進み、ｊの新しい値に対応する共通データ・ユニットの情報を読み出す。次いで、前述のように前処理が継続する。
【０１３５】
電子ファイルの異なるバージョンを前処理するために説明したシステムおよび方法は、いずれの数の命令アーキテクチャを用いたいずれの数の処理および／またはプロセッサに基づくシステムのソフトウェアおよび実行可能ファイルにも適用することができる。例えば、この中におけるシステムおよび方法は、"ARM Architecture Reference Manual" 2nd Edition, by D.Jagger and D. Seal（Ｄ．ジェイガーおよびＤ．シールによる「ＡＲＭアーキテクチャ参考書」第２版）に記載されているように、ＡＲＭ(R)アーキテクチャにおいても用いることができる。ＡＲＭ(R)アーキテクチャは、１６／３２ビット埋め込み減少命令セット・コンピュータ（ＲＩＳＣ）コアに基づき、Ｔｈｕｍｂ１６−ビット命令セットを組み込んだマイクロプロセッサ・アーキテクチャである。ＡＲＭ(R)アーキテクチャにおいて用いる場合、例えば、先に引用した計算可能命令は、ＡＲＭ／Ｔｈｕｍｂ命令セットの"branch with link (BL)"および"branch with link and change mode to ARM/Thumb(BLX)"命令を含む。更に、先に引用したデータ・ポインタは、ＡＲＭ／Ｔｈｕｍｂ命令セットのＤＣＤ命令を含む。
【０１３６】
前述の前処理を用いるデバイスおよび／またはシステムの一例として、デルタ・ファイルを受信し用いる計算デバイスは、対応のソフトウェア・アプリケーションを記憶しておりその更新を必要とするクライアント・デバイス、例えば、セルラ電話機、移動電子デバイス、移動通信デバイス、パーソナル・ディジタル・アシスタント、およびその他のプロセッサに基づくデバイスとすることができる。この支援は、通信業者およびデバイス製造業者に効率的に電子ファイル・コンテンツおよびアプリケーションを彼らのワイヤレス・インフラストラクチャを通じて配布できるようにすることによって、ファームウェアから埋め込みアプリケーションまでの範囲に入るあらゆる移動デバイス・ソフトウェアに提供する。
【０１３７】
前述の前処理の効果が得られるシステムの別の例は、有線シリアル接続を用いてデルタ・ファイルを、ファイル差異発生部を実装したデバイスからそして更新発生部を実装したデバイスに転送するシステムを含む。これらのシステムは、通例、転送レートが遅く、転送レートが遅いために、デルタ・ファイルのサイズ縮小は、転送時間短縮を実現する１つの方法となる。
【０１３８】
前処理の使用による効果が得られるシステムの更に別の例は、無線通信を用いてデルタ・ファイルを、ファイル差異発生部を実装したデバイスから、ファイル更新発生部を実装したデバイスに転送するワイヤレス・システムを含む。ワイヤレス接続に伴う低信頼性が問題になりつつも、これらのシステムも転送レートが遅い。より小さなデルタ・ファイルをこれらのシステムにおいて用いることにより、様々な利点が得られる。例えば、ファイル・サイズが小さい程、デルタ・ファイルの転送時間は短くなる。転送時間が短い程、デバイス・ユーザの時間を節約しつつ、デルタ・ファイルに誤りが混入する機会を減らし、これによってシステムの信頼性が向上する。また、セルラ通信では、転送時間の短縮により、通例サービス料金を分単位で支払う顧客にとって、コストの節約となる。
【０１３９】
別の利点として、デルタ・ファイルが小さい程、デルタ・ファイルをクライアント・デバイスに転送するために必要な帯域幅が狭くて済む。帯域幅の縮小により、割り当てられたチャネルを通じてより多くのクライアント・デバイスに対応することが可能となる。転送時間の短縮と同様、これもワイヤレス・サービス・プロバイダにとって運営コストの削減につながる。
【０１４０】
前述のファイルの元および新バージョンを、元および新ファイル間の差異ファイル発生の一部として前処理するシステムは、差異ファイルを発生する第１デバイスと、差異ファイルを受信し、この差異ファイルを用いて内部で新ファイルの一バージョンを発生する第２デバイスとを含む。第１デバイスは、差異ファイルのサイズを縮小する少なくとも１つのコンポーネントを含み、縮小する際に、コード・ライン削除、コード・ライン追加、およびコード・ライン修正の少なくとも１つから生じるアドレスのずれに対応する元および新バージョン間の差異を特定し、元バージョンのテキスト・セクションと新バージョンの対応するテキスト・セクションとのアドレス間の少なくとも１つの関係を用いて、元バージョンの命令の目標アドレスを修正することによって、元および新バージョンに共通のテキスト・セクションにおいて特定した差異を除去し、修正した目標アドレスを有する命令を含む元ファイルの修正バージョンを発生する。
【０１４１】
一実施形態では、元および新バージョンに共通なテキスト・セクションにおいて特定した差異を除去する際、元および新バージョン間で共通の第１および第２テキスト・セクションを特定し、元バージョンにおける第１テキスト・セクションは、第１計算可能命令を含み、新バージョンにおける第２テキスト・セクションは、第２計算可能命令を含み、元および新バージョン間で共通の第３および第４テキスト・セクションを特定し、元バージョンにおける第３テキスト・セクションは、第１計算可能命令に対応する第１目標アドレスを含み、新バージョンにおける第４テキスト・セクションは、第２計算可能命令に対応する第２目標アドレスを含み、第３および第４関数ユニットの開始アドレス間の第１の差異を用い、更に第１および第２関数ユニットの開始アドレス間の第２の差異を用いて第１命令値を修正することにより、第２計算可能命令から第２命令値を発生し、第１計算可能命令の第１命令値を第２命令値と置換する。
【０１４２】
一実施形態の差異ファイル発生の一部としてのファイルの前処理は、更に、元バージョンにおけるデータ・ポインタ値を修正することにより、元および新バージョンに共通なデータ・セクションを指し示すデータ・ポインタを含む命令において特定した差異を除去することを含み、データ・ポインタ値を修正する際に、現データ・ポインタが指し示す元バージョンにおけるデータ・セクションの開始アドレスと、新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を用いる。データ・ポインタを含む命令において特定した差異を除去するには、更に、元および新バージョン間で共通である第１および第２コード・セグメントを特定し、ここで元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、新バージョンにおける第２コード・セグメントは第２データ・ポインタを含み、元および新バージョン間で共通である第１および第２データ・ユニットを特定し、ここで元バージョンにおける第１データ・ユニットは、第１データ・ポインタに対応する第１目標アドレスを含み、新バージョンにおける第２データ・ユニットは、第２データ・ポインタに対応する第２目標アドレスを含み、第１および第２データ・ユニットの開始アドレス間の差異を用いて第１データ・ポインタ値を修正することにより、第２データ・ポインタから第２データ・ポインタ値を発生し、第１データ・ポインタの第１データ・ポインタ値を第２データ・ポインタ値と置換することを含む。
【０１４３】
一実施形態のシステムにおける第１デバイスは、少なくとも１つの結合部を用いて差異ファイルを第２デバイスに転送し、少なくとも１つの結合部は、ワイヤレス結合部、有線結合部、および混成ワイヤレス／有線結合部のうち少なくとも１つである。
【０１４４】
一実施形態のシステムにおける第２デバイスは、パーソナル・コンピュータ、携帯計算デバイス、セルラ電話機、携帯通信デバイス、およびパーソナル・ディジタル・アシスタントのような、少なくとも１つのプロセッサに基づくデバイスを含む。
【０１４５】
元および新ファイル間の差異ファイル発生の一部としてファイルの元および新バージョンを前処理する前述のシステムは、差異ファイルを発生する際に用いる装置を含む。この装置は、電子ファイルの元バージョンおよび新バージョンを受信する手段と、元および新バージョンに共通なコードのユニットを特定する手段と、コード・ユニットに共通な命令を特定する手段であって、この命令は、対応するファイルの別の部分に対して処理を指令する命令値を含む、手段と、元バージョンの第１命令から第１命令値を発生する手段と、新バージョンの第２命令から第２命令値を発生する手段であって、第２命令が第１命令に対応する、手段と、第１命令の第１命令値を第２命令値と置換する手段と、第１命令を備える元ファイルの第２命令値による修正バージョンを発生する手段とを含む。
【０１４６】
元および新ファイル間での差異ファイルの発生の一部としてファイルの元および新バージョンを前処理するための前述のシステムは、関連する方法を含む。これらの方法の中には、電子ファイルの元バージョンと新バージョンとの間のコード化差異を含む差異ファイルのサイズを縮小する方法がある。一実施形態のこの方法は、コード・ライン削除、コード・ライン追加、およびコード・ライン修正のうち少なくとも１つによって生じたアドレスのずれに対応する元および新バージョン間の差異を特定するステップと、元バージョンのテキスト・セクションと新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、元バージョンの命令の目標アドレスを修正することによって、元および新バージョンに共通なテキスト・セクションにおいて特定した差異を除去するステップと、修正した目標アドレスを有する命令を含む元ファイルの修正バージョンを発生するステップとを含む。
【０１４７】
共通テキスト・セクションにおいて特定した差異を除去する方法は、更に、元および新バージョン間で共通の第１および第２テキスト・セクションを特定するステップであって、元バージョンにおける第１テキスト・セクションは第１計算可能命令を含み、新バージョンにおける第２テキスト・セクションは第２計算可能命令を含む、ステップと、元および新バージョン間で共通の第３および第４テキスト・セクションを特定するステップであって、元バージョンにおける第３テキスト・セクションは、第１計算可能命令に対応する第１目標アドレスを含み、新バージョンにおける第４テキスト・セクションは、第２計算可能命令に対応する第２目標アドレスを含む、ステップと、第３および第４関数ユニットの開始アドレス間の第の１差異を用い、更に第１および第２関数ユニットの開始アドレス間の第２の差異を用いて第１命令値を修正することにより、第２計算可能命令から第２命令値を発生するステップと、第１計算可能命令の第１命令値を第２命令値と置換するステップとを含む。
【０１４８】
一実施形態の前述の方法は、更に、元バージョンにおけるデータ・ポインタを修正することにより、元および新バージョンに共通のデータ・セクションを指し示すデータ・ポインタを含む命令において特定した差異を除去するステップを含み、データ・ポインタ値を修正するには、元バージョンにおいて現データ・ポインタが指し示すデータ・セクションの開始アドレスと、新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を用いる。
【０１４９】
データ・ポインタを含む命令において特定した差異を除去するステップは、元および新バージョン間で共通の第１および第２コード・セグメントを特定するステップであって、元バージョンにおける第１コード・セグメントは第２データ・ポインタを含み、新バージョンにおける第２コード・セグメントは第２データ・ポインタを含む、ステップと、元および新バージョン間で共通な第１および第２データ・ユニットを特定するステップであって、元バージョンにおける第１データ・ユニットは、第１データ・ポイントに対応する第１目標アドレスを含み、新バージョンにおける第２データ・ユニットは、第２データ・ポインタに対応する第２目標アドレスを含む、ステップと、第２データ・ポインタから第２データ・ポインタ値を発生するステップと、第１データ・ポインタの第１データ・ポインタ値を第２データ・ポインタ値と置換するステップとを備えている。一実施形態の第２データ・ポインタ値の発生は、第１および第２データ・ユニットの開始アドレス間の差異を用いて、第１データ・ポインタ値を修正することを含む。
【０１５０】
更に、一実施形態の前述の方法は、修正したデータ・ポインタを有する命令を含む元ファイルの修正バージョンを発生するステップを含む。
また、一実施形態の前述の方法は、更に、共通データ・ブロックを形成するために共通データ・ユニットを併合するステップを含む。一実施形態の併合は、元バージョンの第１データ・ユニットのサイズが新バージョンの第１データ・ユニットと等しく、元バージョンの第１データ・ユニットの終了アドレスが元バージョンの第２データ・ユニットの開始アドレスと等しく、更に新バージョンの第１データ・ユニットの終了アドレスが新バージョンの第２データ・ユニットの開始アドレスに等しい場合、共通データ・ブロックを形成するために、元バージョンの第１および第２データ・ユニットを結合し、新バージョンの対応する第１および第２データ・ユニットを結合するステップと、別の併合可能なデータ・ユニットについて結合動作を繰り返すステップとを備えている。更に、併合は、共通関数ブロックを形成するために共通テキスト・セクションを併合するステップを備えている。また、併合は、元バージョンの第１テキスト・セクションのサイズが新バージョンの第１テキスト・セクションに等しく、元バージョンの第１テキスト・セクションの終了アドレスが元バージョンの第２テキスト・セクションの開始アドレスに等しく、更に新バージョンの第１テキスト・セクションの終了アドレスが新バージョンの第２テキスト・セクションの開始アドレスに等しい場合、共通関数ブロックを形成するために、元バージョンの第１および第２テキスト・セクションを結合し、新バージョンの対応する第１および第２テキスト・セクションを結合するステップと、別の併合可能テキスト・セクションについて結合動作を繰り返すステップとを備えている。
【０１５１】
元ファイルおよび新ファイル間の差異ファイルの発生の一部として、ファイルの元および新バージョンを前処理する前述のシステムは、関連する方法を含む。これらの方法の中には、ファイル差別化を実行する方法がある。この方法は、電子ファイルの元バージョンおよび新バージョンを受信するステップと、元および新バージョンに共通するコードのユニットを特定するステップと、コードのユニットに共通する命令を特定するステップであって、命令が、対応するファイルの別の部分に関係する命令値を含む、ステップと、元バージョンの第１命令から第１命令値をデコードするステップと、新バージョンの第２命令から第２命令値を発生するステップであって、第２命令が第１命令に対応するステップと、第１命令の第１命令値を第２命令値と置換するステップと、第２命令値をもつ第２命令を備える元ファイルの修正バージョンを発生するステップとを備えている。
【０１５２】
更に、一実施形態の前述の方法は、関連するマップ・ファイルからコードの共通ユニットを抽出するステップを備えており、このコードの共通ユニットは、共通関数ユニットおよび共通データ・ユニットを含む。
【０１５３】
一実施形態の前述の方法は、更に、共通関数ブロックを形成するために、コードのユニットの共通関数ユニットを併合するステップを含む。一実施形態の併合するステップは、元バージョンの第１関数ユニットのサイズが、新バージョンの第１関数ユニットに等しく、元バージョンの第１関数ユニットの終了アドレスが元バージョンの第２関数ユニットの開始アドレスに等しく、新バージョンの第１関数ユニットの終了アドレスが新バージョンの第２関数の開始アドレスに等しい場合、共通関数ブロックを形成するために、元バージョンの第１および第２関数ユニットを結合し、新バージョンの対応する第１および第２関数ユニットを結合するステップと、別の併合可能な関数ユニットについて、結合動作を繰り返すステップとを含む。一実施形態の前述の方法は、更に、共通関数ブロックをエンコードするステップも含む。
【０１５４】
更に、一実施形態の前述の方法は、共通データ・ブロックを形成するためにユニットの共通データ・ユニットを併合するステップも含む。一実施形態の併合するステップは、元バージョンの第１データ・ユニットのサイズが新バージョンの第１ユニットに等しく、元バージョンの第１データ・ユニットの終了アドレスが元バージョンの第２データ・ユニットの開始アドレスに等しく、新バージョンの第１データ・ユニットの終了アドレスが新バージョンの第２データ・ユニットの開始アドレスに等しい場合、共通データ・ブロックを形成するために、元バージョンの第１および第２データ・ユニットを結合し、新バージョンの対応する第１および第２データ・ユニットを結合するステップと、別の併合可能データ・ユニットについて結合動作を繰り返すステップとを含む。この方法は、更に、共通データ・ブロックをエンコードするステップも含む。
【０１５５】
一実施形態の方法の下では、元および新バージョンに共通するコードのユニットは共通関数ユニットであり、第１命令は第１計算可能命令を含み、第２命令は第２計算可能命令を含み、第２命令値を発生するステップは、目標アドレスを含む元および新バージョンの共通関数ユニットの開始アドレス間の第１の差異を用い、更に第１および第２計算可能命令を含む共通関数ユニットの開始アドレス間の第２の差異を用いて、第１関数値を修正するステップを含む。
【０１５６】
一実施形態の方法のコードのユニットは、関数ユニットを含む。これらの方法の下では、第１命令値を発生するステップは、第１計算可能命令の現命令アドレスと、第１計算可能命令の目標アドレスとの間の差異を発生するステップを含む。第２命令値を発生するステップは、第１計算可能命令の現命令アドレスと第１計算可能命令の目標アドレスとの間の差異を発生するステップと、新バージョンの第１共通関数ユニットの開始アドレスと、元バージョンの対応する第１共通関数ユニットの開始アドレスとの差異を発生するステップと、新バージョンの第２共通関数ユニットの開始アドレスと、元バージョンの対応する第２共通関数ユニットの開始アドレスとの間の差異を発生するステップとを含む。
【０１５７】
一実施形態の方法の中には、コードのユニットは、データ・ユニットを含み、命令は、データ・ポインタを含むものがある。
一実施形態の方法の下では、元および新バージョンに共通のコードのユニットは、共通データ・ユニットであり、第１命令は第１データ・ポイントを含み、第２命令は第２データ・ポインタを含み、第１命令値は第１データ・ポイント値を含み、第２命令値は第２データ・ポインタ値を含み、第２命令値を発生するステップは、第１および第２データ・ユニットの開始アドレス間の差異を用いて第１データ・ポインタ値を修正することによって、第２データ・ポインタ値を発生するステップを含む。
【０１５８】
一実施形態の前述の方法は、更に、元ファイルおよび新ファイルの修正バージョン間でファイル差別化を行うステップと、差異ファイルを発生するステップとを含む。また、これらの方法は、差異ファイルを携帯処理システムに転送するステップと、携帯処理システムにおいて差異ファイルを用いて新ファイルの一バージョンを発生するステップも備えている。また、一実施形態の前述の方法は、更に、共通関数ブロックを形成するためにコードのユニットの共通関数ユニットを併合するステップと、共通関数ブロックを形成するためにコードのユニットの共通データ・ユニットを併合するステップと、共通データ・ブロックを形成するためにコードのユニットの共通データ・ユニットを併合するステップと、携帯処理システムにおいて新ファイルのバージョンを発生する際に用いるために、共通関数ブロックおよび共通データ・ブロックをエンコードするステップを備えている。
【０１５９】
元および新ファイル間における差異ファイル発生の一部としてファイルの元および新バージョンを前処理する前述のシステムは、更に別の関連する方法を含む。これらの方法の中には、電子ファイル間の差異を判定する方法があり、電子ファイルの元バージョンおよび新バージョンを受信するステップと、元および新バージョン間で共通の第１および第２関数ユニットを特定するステップであって、元バージョンにおける第１関数ユニットは第１計算可能命令を含み、新バージョンにおける第２関数ユニットは第２計算可能命令を含む、ステップと、元および新バージョン間で共通の第３および第４関数ユニットを特定するステップであって、元バージョンにおける第３関数ユニットは、第１計算可能命令に対応する第１目標アドレスを含み、新バージョンにおける第４関数ユニットは、第２計算可能命令に対応する第２目標アドレスを含む、ステップと、第２計算可能命令から第２命令値を発生するステップと、第１計算可能命令の第１命令値を第２命令値と置換するステップと、第２命令値をもつ第１命令を備える元ファイルの修正バージョンを発生するステップとを備えている。
【０１６０】
前述の方法の下において第２命令値を発生するステップは、第３および第４関数ユニットの開始アドレス間の第１の差異を用い、更に第１および第２関数ユニットの開始アドレス間の第２の差異を用いて、第１命令値を修正するステップを含む。
【０１６１】
更に、一実施形態の前述の方法は、元および新バージョン間で共通の第１および第２コード・セグメントを特定するステップであって、元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、新バージョンにおける第２コード・セグメントは第２データ・ポインタを含む、ステップと、元および新バージョン間で共通の第１および第２データ・ユニットを特定するステップであって、元バージョンにおける第１データ・ユニットは、第１データ・ポインタに対応する第１目標アドレスを含み、新バージョンにおける第２データ・ユニットは、第２データ・ポインタに対応する第２目標アドレスを含む、ステップと、第２データ・ポインタから第２データ・ポインタ値を発生するステップと、第１データ・ポインタの第１データ・ポインタ値を第２データ・ポインタ値と置換するステップと、第２データ・ポインタ値をもつ第１データ・ポインタを備える元ファイルの修正バージョンを発生するステップとを備えている。一実施形態の下において第２データ・ポインタを発生するステップは、現データ・ポインタが指し示す元バージョンにおけるデータ・セクションの開始アドレスと、新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差異を発生するステップを含む。
【０１６２】
更に、一実施形態の前述の方法は、共通関数ブロックを形成するために共通関数ユニットを併合するステップを含む。
更に、一実施形態の前述の方法は、共通データ・ブロックを形成するために共通データ・ユニットを併合するステップを含む。
【０１６３】
一実施形態の前述の方法は、更に、元ファイルおよび新ファイルの修正バージョンを用いて、差異ファイルを発生するステップを含む。これらの方法は、更に、差異ファイルを携帯処理システムに転送するステップと、差異ファイルを用いて、携帯処理システムにおいて新ファイルの一バージョンを発生するステップとを含む。
【０１６４】
元および新ファイル間における差異ファイル発生の一部としてファイルの元および新バージョンを前処理するための前述のシステムは、コンピュータ読み取り可能媒体を含む。一実施形態のコンピュータ読み取り可能媒体は、処理システムにおいて実行すると、コード・ライン削除、コード・ライン追加、およびコード・ライン修正の少なくとも１つによって生じたアドレスのずれに対応する元および新バージョン間の差異を特定し、元バージョンのテキスト・セクションのアドレスと新バージョンの対応するテキスト・セクションのアドレスの間の少なくとも１つの関係を用いて、元バージョンの命令の目標アドレスを修正することにより、元および新バージョンに共通のテキスト・セクションにおいて特定した差異を除去し、修正した目標アドレスを有する命令を含む元ファイルの修正バージョンを発生することによって、電子ファイルの元バージョンおよび新バージョンの間でコード化した差異を含む差異ファイルのサイズを縮小する実行可能命令を含む。
【０１６５】
本発明の形態は、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、プログラマブル・アレイ・ロジック（ＰＡＬ）デバイス、電気的プログラム可能ロジックおよびメモリ・デバイスのようなプログラマブル・ロジック・デバイス（ＰＤＬ）、標準的なセルに基づくデバイス、ならびに特定用途集積回路（ＡＳＩＣ）を含む種々の回路のいずれにもプログラムされる機能として実現することができる。更に、本発明の形態は、ソフトウェアに基づく回路エミュレーション、ディスクリート・ロジック（連続および組み合わせ）、カスタム・デバイス、ファジイ（ニューラル）デバイス、量子デバイス、および上述のデバイスの種類のいずれのハイブリッドを有するマイクロプロセッサにおいても具体化することができる。勿論、基盤となるデバイス技術は、種々のコンポーネントの種類、例えば、相補金属酸化物半導体（ＣＭＯＳ）のような金属酸化物半導体電界効果トランジスタ（ＭＯＳＦＥＴ）技術、エミッタ結合ロジック（ＥＣＬ）のようなバイポーラ技術、ポリマ技術（例えば、シリコン共役ポリマおよび金属共役ポリマ−金属構造）、混合アナログおよびディジタルなどにおいて提供することができる。
【０１６６】
文脈上特に必要であることが明らかでない限り、明細書および特許請求の範囲を通じて、「備える」、「備えている」等の言葉は、排他的または網羅的意味ではなく、包含的意味で解釈するものとする。即ち、「含むが、限定されない」という意味である。単数または複数を用いる単語も、それぞれ、複数および単数を含むものとする。加えて、「ここでは」、「以下で」、「先に」、「以下で」という単語、および同様な意義の単語は、本願において用いられる場合、本願全体を指すのであり、本願のいずれの特定部分を指すのではないとする。「または」という単語が２つ以上の項目のリストに関して用いられている場合、その単語は、当該単語の以下の解釈全て、即ち、リストにおける項目のいずれか、リストにおける項目の全て、およびリストにおける項目のあらゆる組み合わせを包含するものとする。
【０１６７】
本発明の例示した実施例についてのこれまでの説明は、それで全てであることも、開示した正確な形態に本発明を限定することも意図していない。本発明の具体的な実施形態および例を例示の目的のためにここで記載したが、種々の等価な変更も本発明の範囲内で可能であることは、当業者は認めよう。ここに提示した本発明の教示は、他の処理システムや通信システムにも適用することができ、前述のファイル差別化システムのみに適用できるのではない。
【０１６８】
前述した種々の実施形態のエレメントおよび作用を組み合わせれば、更に別の実施形態も得ることができる。これらおよびその他の変更は、前述の詳細な説明に鑑みれば、容易に行うことができる。
【０１６９】
先の引例ならびに米国特許および特許出願は全て、ここで引用したことにより、本願にも含まれるものとする。必要であれば、本発明の形態を変更して前述の種々の特許および出願のシステム、機能および概念を採用すれば、本発明の更に別の実施形態を得ることができる。
【０１７０】
一般に、特許請求の範囲においては、用いられる用語は、明細書に開示される具体的な実施形態および特許請求の範囲に本発明を限定するように解釈するのではなく、特許請求の範囲の下で動作してファイル差別化および更新方法を実施するあらゆる処理システムを含むように解釈するのが当然である。したがって、本発明は、本開示に限定されるのではなく、むしろ発明の範囲は特許請求の範囲によって全体的に決定されるものとする。
【０１７１】
本発明のある種の形態をある請求項の形式で提示するが、本願の発明者は、本発明の種々の形態をいかなる数の請求項形式でも想定している。例えば、本発明の一形態のみを、コンピュータ読み取り可能媒体に具体化するものとして明記するが、他の形態も同様にコンピュータ読み取り可能媒体に具体化することができる。したがって、本発明は、本願を出願した後でも、更に別の請求項を追加し、本発明の別の形態に対する、このような更に別の請求項を追求する権利を保有するものとする。
【図１】
2010176699.tif 000035
【図２】
2010176699.tif 000036
【図３】
2010176699.tif 000037
【図４】
2010176699.tif 000038
【図５】
2010176699.tif 000039
【図６】
2010176699.tif 000040
【図７】
2010176699.tif 000041
【図８】
2010176699.tif 000042
【図９】
2010176699.tif 000043
【図１０】
2010176699.tif 000044
【図１１】
2010176699.tif 000045
【図１２】
2010176699.tif 000046
【手続補正書】
【提出日】平成22年4月30日(2010.4.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
電子ファイルを更新するためのシステムであって、
電子ファイルの元バージョンと新バージョンとの間のコード化された差異を含む差異ファイルを発生する第１デバイスであって、
コード・ラインの削除、コード・ラインの追加、およびコード・ラインの修正のうちの少なくとも１つによって生じたアドレスのずれに対応する前記元および新バージョン間の差異を特定し、
前記元バージョンのテキスト・セクションおよび前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通のテキスト・セクションにおいて前記特定した差異を除去し、
修正した目標アドレスを有する命令を含む前記元バージョンの修正バージョンを発生し、
前記新バージョンと前記元バージョンの前記修正バージョンとを使用して前記差異ファイルを生成する、
ように構成された少なくとも１つのコンポーネントを含む、第１デバイスと、
第２デバイスであって、前記差異ファイルを受け、該差異ファイルを用いて、該第２デバイスにおいて前記新バージョンを発生する第２デバイスと、
を備えている、システム。
【請求項２】
請求項１記載のシステムにおいて、除去することは、更に、
前記元および新バージョン間に共通の第１および第２テキスト・セクションを特定し、前記元バージョンにおける第１テキスト・セクションは第１計算可能命令を含み、前記新バージョンにおける第２テキスト・セクションは第２計算可能命令を含み、
前記元および新バージョン間に共通の第３および第４テキスト・セクションを特定し、前記元バージョンにおける第３テキスト・セクションは、前記第１計算可能命令に対応する第１目標アドレスを含み、前記新バージョンにおける第４テキスト・セクションは、前記第２計算可能命令に対応する第２目標アドレスを含み、
前記第３および第４の関数ユニットの開始アドレス間の第１の差を用い、更に前記第１および第２の関数ユニットの開始アドレス間の第２の差を用いて、前記第１命令値を修正することによって、前記第２計算可能命令から第２命令値を発生し、
前記第１計算可能命令の第１命令値を、前記第２命令値と置換する、
ことを含む、システム。
【請求項３】
請求項１記載のシステムであって、更に、前記元バージョンにおけるデータ・ポインタ値を修正することによって、前記元および新バージョンに共通のデータ・セクションを指し示すデータ・ポインタを含む命令において前記特定した差異を除去することを含み、データ・ポインタ値を修正することは、現データ・ポインタが指し示す前記元バージョンにおけるデータ・セクションの開始アドレスと、前記新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差を用いる、システム。
【請求項４】
請求項３記載のシステムにおいて、データ・ポインタを含む命令において特定した差異を除去することは、更に、
前記元および新バージョン間に共通の第１および第２のコード・セグメントを特定し、前記元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、前記新バージョンにおける第２コード・セグメントは第２データ・ポインタを含み、
前記元および新バージョン間で共通な第１および第２のデータ・ユニットを特定し、前記元バージョンにおける第１データ・ユニットは、前記第１データ・ポインタに対応する第１目標アドレスを含み、前記新バージョンにおける第２データ・ユニットは、前記第２データ・ポインタに対応する第２目標アドレスを含み、
前記第１および第２データ・ユニットの開始アドレス間の差を用いて、第１データ・ポインタ値を修正することによって、前記第２データ・ポインタから第２データ・ポインタ値を発生し、
前記第１データ・ポインタの第１データ・ポインタ値を前記第２データ・ポインタ値と置換する、
ことを含む、システム。
【請求項５】
請求項１記載のシステムにおいて、前記第２デバイスは、パーソナル・コンピュータ、携帯計算デバイス、セルラ電話機、携帯通信デバイス、およびパーソナル・ディジタル・アシスタントの中から選択した、少なくとも１つのプロセッサ・ベースのデバイスである、システム。
【請求項６】
請求項１記載のシステムにおいて、前記第１デバイスは、少なくとも１つの結合を用いて、前記差異ファイルを前記第２デバイスに転送し、前記少なくとも１つの結合は、ワイヤレス結合、有線結合、混成ワイヤレス／有線結合のうち少なくとも１つである、システム。
【請求項７】
電子ファイルの元バージョンと新バージョンとの間のコード化された差異を含む差異ファイルのサイズを縮小する方法であって、
コード・ライン削除、コード・ライン追加、およびコード・ライン修正のうち少なくとも１つから生じたアドレスのずれに対応する前記元および新バージョン間の差異を特定するステップと、
前記元バージョンのテキスト・セクションと前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、前記元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通なテキスト・セクションにおいて前記特定した差異を除去するステップと、
修正した目標アドレスを有する命令を含む前記元バージョンの修正バージョンを発生するステップと、
前記新バージョンと前記元バージョンの前記修正バージョンとを使用して前記差異ファイルを発生するステップと、
を備えた、方法。
【請求項８】
請求項７記載の方法において、除去するステップは、更に、
前記元および新バージョン間で共通の第１および第２テキスト・セクションを特定するステップであって、前記元バージョンにおける第１テキスト・セクションは第１計算可能命令を含み、前記新バージョンにおける第２テキスト・セクションは第２計算可能命令を含む、ステップと、
前記元および新バージョン間で共通の第３および第４テキスト・セクションを特定するステップであって、前記元バージョンにおける第３テキスト・セクションは前記第１計算可能命令に対応する第１目標アドレスを含み、前記新バージョンにおける第４テキスト・セクションは前記第２計算可能命令に対応する第２目標アドレスを含む、ステップと、
前記第３および第４関数ユニットの開始アドレス間の第１の差、ならびに前記第１および第２関数ユニットの開始アドレス間における第２の差を用いて前記第１命令値を修正することによって、前記第２計算可能命令から第２命令値を発生するステップと、
前記第１計算可能命令の第１命令値を前記第２命令値と置換するステップと、
を備えている、方法。
【請求項９】
請求項７記載の方法であって、更に、前記元バージョンにおけるデータ・ポインタ値を修正することによって、前記元および新バージョンに共通なデータ・セクションを指し示すデータ・ポインタを含む命令において前記特定した差異を除去するステップを備えており、データ・ポインタ値の修正には、現データ・ポインタが指し示す前記元バージョンにおけるデータ・セクションの開始アドレスと、前記新バージョンにおける対応するデータ・セクションの開始アドレスとの間の差を用いる、方法。
【請求項１０】
請求項９記載の方法において、データ・ポインタを含む命令において特定した差異を除去するステップは、更に、
前記元および新バージョン間に共通の第１および第２コード・セグメントを特定するステップであって、前記元バージョンにおける第１コード・セグメントは第１データ・ポインタを含み、前記新バージョンにおける第２コード・セグメントは第２データ・ポインタを含む、ステップと、
前記元および新バージョン間で共通の第１および第２データ・ユニットを特定するステップであって、前記元バージョンにおける第１データ・ユニットは、前記第１データ・ポインタに対応する第１目標アドレスを含み、前記新バージョンにおける第２データ・ユニットは、前記第２データ・ポインタに対応する第２目標アドレスを含み、ステップと、
前記第２データ・ポインタから第２データ・ポインタ値を発生するステップと、
前記第１データ・ポインタの第１データ・ポインタ値を前記第２データ・ポインタ値と置換するステップと、
を備えている、方法。
【請求項１１】
請求項１０記載の方法において、前記第２データ・ポインタ値を発生するステップは、前記第１および第２データ・ユニットの開始アドレス間の差を用いて、第１データ・ポインタ値を修正するステップを含む、方法。
【請求項１２】
請求項９記載の方法であって、更に、修正データ・ポインタを有する前記命令を含む前記元ファイルの修正バージョンを発生するステップを備えている、方法。
【請求項１３】
請求項９記載の方法であって、更に、共通データ・ブロックを形成するために共通データ・ユニットを併合するステップを含む、方法。
【請求項１４】
請求項１３記載の方法において、併合するステップは、
前記元バージョンの第１データ・ユニットが前記新バージョンの第１データ・ユニットに等しいサイズを有し、前記元バージョンの第１データ・ユニットの終了アドレスが前記元バージョンの第２データ・ユニットの開始アドレスに等しく、かつ前記新バージョンの第１データ・ユニットの終了アドレスが前記新バージョンの第２データ・ユニットの開始アドレスに等しい場合、共通データ・ブロックを形成するために、前記元バージョンの第１および第２データ・ユニットを結合し、前記新バージョンの対応する第１および第２データ・ユニットを結合するステップと、
追加の併合可能データ・ユニットについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項１５】
請求項１４記載の方法であって、更に、共通関数ブロックを形成するために、共通テキスト・セクションを併合するステップを含む、方法。
【請求項１６】
請求項１５記載の方法において、併合するステップは、
前記元バージョンの第１テキスト・セクションが前記新バージョンの第１テキスト・セクションに等しいサイズを有し、前記元バージョンの第１テキスト・セクションの終了アドレスが、前記元バージョンの第２テキスト・セクションの開始アドレスに等しく、かつ前記新バージョンの第１テキスト・セクションの終了アドレスが前記新バージョンの第２テキスト・セクションの開始アドレスに等しい場合、共通関数ブロックを形成するために、前記元バージョンの第１および第２テキスト・セクションを結合し、前記新バージョンの対応する第１および第２テキスト・セクションを結合するステップと、
追加の併合可能テキスト・セクションについて前記結合動作を繰り返すステップと、
を備えている、方法。
【請求項１７】
実行可能命令を含むコンピュータ読み取り可能媒体であって、処理システムにおいて実行されると、
コード・ライン削除、コード・ライン追加、およびコード・ライン修正のうち少なくとも１つから生じたアドレスのずれに対応する元および新バージョン間の差異を特定し、
前記元バージョンのテキスト・セクションと前記新バージョンの対応するテキスト・セクションのアドレス間の少なくとも１つの関係を用いて、前記元バージョンの命令の目標アドレスを修正することによって、前記元および新バージョンに共通なテキスト・セクションにおいて前記特定した差異を除去し、
修正した目標アドレスを有する命令を含む前記元バージョンの修正バージョンを発生し、
前記新バージョンと前記元バージョンの前記修正バージョンとを使用して前記差異ファイルを発生する、
ことによって、電子ファイルの前記元バージョンと前記新バージョンとの間のコード化された差異を含む差異ファイルのサイズを縮小する、コンピュータ読み取り媒体。
【外国語明細書】
2010176699000001.pdf