(57)【要約】【課題】元および新ファイル・バージョン間の際ファイル発生の一部、例えば、バイト・レベルのファイル差別化として、元および新バージョンのファイルを前処理および後処理するシステムおよび方法を提供する。【解決手段】ファイル・バージョン間のソフトウェア／エクゼキュータブルの変更は、ソース・コード変更であると定義する、主変更／論理変更と、二次的変更とを含む。二次的変更は、一般に主変更から生じ、ソフトウェア・コンパイラ／リンカ・ユーティリティが発生する。二次的変更は、アドレス変更、ポインタ目標アドレス変更、およびアドレス・オフセットの変更を含む。提供する前処理および／または後処理システムならびに方法は、ファイル・バージョン間において近似規則を用いて二次的変更を除去／削減し、これらの変更の除去に関する情報を、対応する差異ファイル内にエンコードする。【選択図】図１
2009509272.tif 000002
【特許請求の範囲】
【請求項１】
電子ファイルの更新システムであって、
電子ファイルの元バージョンと新バージョンとの間の符号化差異を含む差異ファイルを発生する発生コンポーネントであって、該発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、
前記元バージョンと前記新バージョンとの間で共通である第１および第２テキスト・セクションを識別し、前記元バージョンにおける第１テキスト・セクションは、第１開始アドレスおよび第１目標アドレスを有する第１計算可能命令を含み、前記新バージョンにおける第２テキスト・セクションは、第２開始アドレスおよび第２目標アドレスを有する第２計算可能命令を含み、
前記第１および第２計算可能命令の特性に基づいて、既知のテキスト・セクションを拡張するか、または前記元バージョンと前記新バージョンとの間で共通である新しいテキスト・セクションを作成するかの内少なくとも一方を決定し、
前記元バージョンおよび前記新バージョンに共通であるテキスト・セクションにおいて識別した差異を除去する、発生コンポーネントと、
新バージョンを発生するときに用いるために、前記差異ファイルを転送する転送コンポーネントと、
を備えている、電子ファイルの更新システム。
【請求項２】
請求項１記載のシステムにおいて、前記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、前記第１および第２計算可能命令の第１および第２目標アドレスが１つ以上の既知の共通テキスト・セクションの中にない場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含むように、前記元バージョンと前記新バージョンとの間で共通である既知のテキスト・セクションを拡張する、システム。
【請求項３】
請求項２記載のシステムにおいて、前記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、前記第１および第２計算可能命令の第１および第２開始アドレスが、前記元バージョンおよび前記新バージョン間で共通である第１および第２テキスト・セクションの開始アドレスから等しい量だけずれている場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含むように、前記元バージョンと前記新バージョンとの間で共通である既知のテキスト・セクションを拡張する、システム。
【請求項４】
請求項２記載のシステムにおいて、記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、前記第１および第２計算可能命令の第１および第２開始アドレスが、前記元バージョンおよび前記新バージョン間で共通である第１および第２テキスト・セクション内において計算可能な量だけ対応する基準からずれている場合、前記第１および第２計算可能命令の第１および第２目標アドレスを内包するように、前記元バージョンと前記新バージョンとの間で共通である既知のテキスト・セクションを拡張する、システム。
【請求項５】
請求項１記載のシステムにおいて、記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、前記第１および第２計算可能命令の第１および第２目標アドレスが、前記元バージョンと前記新バージョンとの間で共通である１つ以上の既知のテキスト・セクションの中にない場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含む、前記元バージョンと前記新バージョンとの間で共通である１つ以上のテキスト・セクションを作成する、システム。
【請求項６】
請求項５記載のシステムにおいて、記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、１つ以上の計算可能な命令の数、頻度、および間隔の内少なくとも１つに基づいて、前記第１および第２計算可能命令の第１および第２目標アドレスを含む、前記元および新バージョン間で共通である１つ以上の新テキスト・セクションを作成する、システム。
【請求項７】
請求項５記載のシステムにおいて、記発生コンポーネントは、前記差異ファイルのサイズを縮小する際に、前記第１および第２計算可能命令の第１および第２開始アドレスが、前記元バージョンおよび前記新バージョン間で共通である第１および第２テキスト・セクション内において計算可能な量だけ対応する基準からずれている場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含む、前記元バージョンと新バージョンとの間で共通である１つ以上の新テキスト・セクションを作成する、システム。
【請求項８】
請求項１記載のシステムにおいて、前記既知のテキスト・セクションを拡張するか、または前記元バージョンと前記新バージョンとの間で共通である新しいテキスト・セクションを作成するかの内少なくとも一方の決定は、少なくとも部分的に、正しく処理前処理された計算可能命令の数に基づく、システム。
【請求項９】
請求項１記載のシステムにおいて、前記転送コンポーネントは、第２デバイス上において前記新ファイルの１バージョンを発生する際に用いるために、前記差違ファイルを転送し、前記第２デバイスは、パーソナル・コンピュータ、携帯用計算デバイス、セルラ電話機、携帯用通信デバイス、およびパーソナル・ディジタル・アシスタントの中から選択した、少なくとも１つのプロセッサに基づくデバイスである、システム。
【請求項１０】
差異ファイルを発生する際に用いる装置であって、
電子ファイルの元バージョンおよび新バージョンを受信する手段と、
前記元および新バージョンに共通するコードのユニットを識別する手段と、
前記コードのユニットに交通である命令を識別する手段であって、前記識別する命令は、第１開始アドレスおよび第１目標アドレスを有する前記元バージョンにおける第１命令と、第２開始アドレスおよび第２目標アドレスを有する前記新バージョンにおける第２命令とを含む、手段と、
コードのユニットを拡張するか、または前記元および新バージョンに共通である新しいコードのユニットを作成する手段と、
を備えている、装置。
【請求項１１】
請求項１０記載の装置において、前記コードのユニットを拡張するか、または新しいコードのユニットを作成する手段は、コードのユニットを拡張するか、または前記元および新バージョンに共通である新しいコードのユニットを作成する際に、前記識別した命令を評価する、装置。
【請求項１２】
請求項１１記載の装置において、前記コードのユニットを拡張するか、または新しいコードのユニットを作成する手段は、コードのユニットを拡張するか、または前記元および新バージョンに共通である新しいコードのユニットを作成する際に、前記識別した第１および第２命令の第１および第２目標アドレスが、前記元および新バージョンに共通である１つ以上の既知の共通ユニットの中にないか否か評価する、装置。
【請求項１３】
請求項１２記載の装置において、記コードのユニットを拡張するか、または新しいコードのユニットを作成する手段は、コードのユニットを拡張するか、または前記元および新バージョンに共通である新しいコードのユニットを作成する際に、前記識別した第１および第２命令の第１および第２開始アドレスの特性を評価する、装置。
【請求項１４】
ファイル差別化を行う方法であって、
電子ファイルの元バージョンおよび新バージョンを受信するステップと、
前記元および新バージョンに共通であるコードのユニットを識別するステップであって、前記元および新バージョンに共通するコードのユニットは共通機能ユニットを含む、ステップと、
前記元バージョンと前記新バージョンとの間に１つ以上の共通機能ブロックを形成するために、前記コードのユニットの共通機能ユニットを併合するステップと、
前記１つ以上の機能ブロックに共通する命令を識別するステップであって、前記識別した命令は、第１開始アドレスおよび第１目標アドレスを有する前記元バージョンにおける第１命令と、第２開始アドレスおよび第２目標アドレスを有する前記新バージョンにおける第２命令とを含む、ステップと、
前記識別した第１および第２命令の評価に基づいて、前記１つ以上の共通機能ブロックの少なくとも１つを拡張するか、または１つ以上の新しい共通機能ブロックを作成するステップと、
を備えている、方法。
【請求項１５】
請求項１４記載の方法であって、更に、前記第１および第２命令の第１および第２目標アドレスが１つ以上の共通機能ブロックの中にない場合、前記１つ以上の共通機能ブロックの少なくとも１つを拡張するか、または前記１つ以上の新しい共通機能ブロックを作成するステップを備えている、方法。
【請求項１６】
請求項１５記載の方法であって、更に、前記第１および第２計算可能命令の第１および第２開始アドレスが、前記元バージョンおよび前記新バージョン間で共通である第１および第２テキスト・セクションの開始アドレスから等しい量だけずれている場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含むように、前記１つ以上の共通機能ブロックを拡張するステップを備えている、方法。
【請求項１７】
請求項１５記載の方法であって、更に、前記電子ファイルの元および新バージョン間で共通である１つ以上の命令の数、頻度、および間隔の内少なくとも１つに基づいて、前記第１および第２命令の第１および第２目標アドレスを含む１つ以上の新しい共通機能ブロックを作成するステップを備えている、方法。
【請求項１８】
請求項１５記載の方法であって、更に、前記第１および第２計算可能命令の第１および第２開始アドレスが、前記第１および第２共通機能ブロックの対応する基準から等しい量だけずれている場合、前記第１および第２計算可能命令の第１および第２目標アドレスを含む１つ以上の新しい共通機能ブロックを作成するステップを備えている、方法。
【請求項１９】
請求項１４記載の方法であって、更に、正しく前処理された命令の数に部分的に基づいて、前記１つ以上の共通機能ブロックの少なくとも１つを拡張するか、または１つ以上の新しい共通機能ブロックを作成するステップを備えている、方法。
【請求項２０】
請求項１４記載の方法であって、更に、
差異ファイルを発生するステップと、
前記差異ファイルを携帯用処理システムに転送するステップと、
前記差異ファイルを用いて、前記携帯用処理システムにおいて前記新ファイルの１バージョンを発生するステップと、
を備えている、方法。
【請求項２１】
実行可能な命令を含むコンピュータ読み取り可能媒体であって、前記命令を処理システムにおいて実行すると、電子ファイルの元バージョンと新バージョンとの間において符号化した差異を含む差異ファイルの合図を縮小し、その際に、
電子ファイルの元バージョンおよび新バージョンを受信し、
前記元および新バージョンに共通であるコードのユニットを識別し、前記元および新バージョンに共通するコードのユニットは共通機能ユニットを含み、
前記元バージョンと前記新バージョンとの間に１つ以上の共通機能ブロックを形成するために、前記コードのユニットの共通機能ユニットを併合し、
前記１つ以上の機能ブロックに共通する命令を識別し、前記識別した命令は、第１開始アドレスおよび第１目標アドレスを有する前記元バージョンにおける第１命令と、第２開始アドレスおよび第２目標アドレスを有する前記新バージョンにおける第２命令とを含み、
前記識別した第１および第２命令の評価に基づいて、共通機能ブロックを拡張するか、または新しい共通機能ブロックを作成する、
コンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本願は、２００５年９月２３日に出願した米国仮特許出願第６０／７２０，２６４号の優先権を主張する。
【０００２】
本願は、２００３年７月２０日に出願した米国特許出願第１０／６００，９７８号の一部継続出願である。
【背景技術】
【０００３】
プロセッサ、マイクロプロセッサ、および／または演算装置上で実行し、一定の機能性を提供するソフトウェアは、時と共に変化することが多い。この変化は、 ソフトウェア・ファイルにおけるバグ、即ち、誤りを訂正する必要性、発展する技術に合わせる必要性、または新たな特徴を追加する必要性等、様々な必要性の 結果生じる可能性がある。即ち、移動処理デバイス、例えば、移動ワイヤレス・デバイス上で動作する埋め込みソフトウェア・コンポーネントは、多数のソフト ウェア・バグを含むことが多く、訂正が必要である。ソフトウェアは、人が読むことができる情報相互交換用アメリカ標準コード（ＡＳＣＩＩ： American Standard Code for Information Interchange）の平文ファイルまたは二進コードの形態の１つ以上のファイルを含む。ソフトウェア・ファイルは、更に小さな単位に分割することが でき、これらは多くの場合モジュールまたはコンポーネントと呼ばれている。
【０００４】
移動処理デバイスのような、プロセッサを用いた携帯用デバイスは、リアル・タイムのオペレーティング・システム（ＲＴＯＳ）を含むのが通例であり、このデ バイスのソフトウェア・コンポーネントは全て、単一の大型ファイルとしてリンクされている。更に、これらの移動ワイヤレス・デバイスには、ファイル・シス テム支援が設けられていないのが通例である。加えて、単一の大型ファイルは、無線、赤外線、またはシリアル・リンクのような低速通信リンクを用いて、デバ イス内に予めロードするか、埋め込む必要がある。
【０００５】
低速通信リンクを通じて移動ワイヤレス・デバイスの大きなファイルを更新する場合の障害には、更新したファイルをデバイスに配信する際に伴う時間、帯域 幅、およびコストが含まれる。大型ファイルを移動処理デバイスに配信する問題に対する既存の解決策の１つに、圧縮の使用が含まれる。一般に既存の圧縮アル ゴリズムが数多く用いられているが、しかしながら、多くの場合、圧縮したファイルでさえも、低速でコストがかかる狭帯域通信リンクを通じてデバイスにダウ ンロードするには大き過ぎる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ファイルを更新するための別の典型的な解決策では、差異プログラムを用いて、改訂したファイルが元のファイルとどれくらい異なるかについての記述を生成する。このような差異データを生成する差異プログラムが入手可能である。しかしながら、圧縮と同様、これらの差異プログラムを用いて生成した差異ファイル は、関連する通信プロトコルによる転送には大き過ぎる場合もあり得る。
【発明を実施するための最良の形態】
【０００７】
（引用による本願への加入）
本明細書において述べられる各刊行物、特許、および／または特許出願は、引用することにより、個々の各刊行物および／または特許出願が特定して個々に引用により本願に含まれることを示すのと同様に、その全体が本願にも含まれるものとする。
【０００８】
元ファイルおよび新ファイル間の差異ファイル発生の一部として、元ファイルおよび新ファイルを前処理するシステムおよび方法を提供する。この前処理は、差 異ファイルのサイズの一層の縮小に対応する。ファイル・バージョン間のソフトウェア／実行可能な変更は、ソース・コード変更と定める主変更／論理変更、お よび二次的変更を含む。二次的変更は、一般に、主変更から生じ、ソフトウェア・コンパイラ／リンカ・ユーティリティによって発生する。二次的変更は、アド レス変更、ポインタ目標アドレス変更、ならびに主変更から生じソフトウェア・コンパイラ／リンカ・ユーティリティによって発生したアドレス・オフセットの 変更を含む。提供する前処理システムおよび方法は、ファイル・バージョン間において近似規則を用いて、二次的変更を除去／削減し、これらの変更の除去に関 する情報を、対応する差異ファイルの情報にエンコードする。
【０００９】
電子ファイルの２バージョン間の差異ファイルを生成するシステムおよび方法について、これより詳細に説明する。このファイル生成を、ここでは、ファイル差別化(file differencing)と呼ぶことにする。図１は、 一実施形態の下において行われるファイル差別化および更新を示すブロック図である。ファイル差別化および更新は、差別化コンポーネントおよび更新コンポー ネントを含む。差別化コンポーネントは、ここではファイル差異発生部と呼び、第１のプロセッサを用いたシステムまたはコンピュータ・システムにおいて、電 子ファイルの元バージョンおよび新バージョンから、差異ファイルを発生する。更新コンポーネントは、ここでは更新発生部と呼び、第２のプロセッサを用いた システムまたはコンピュータ・システム上で、差異ファイルと、元ファイルのホストされたコピー(hosted copy)とを用いて、新ファイルのコピーを発生する。
【００１０】
以下の説明では、本発明の実施形態の完全な理解が得られ、それを実施可能な説明を行うために、多数の具体的な詳細を導入する。しかしながら、本発明は、これら具体的な詳細の１つ以上が無くとも、または他のコンポーネント、システム等を用いても実施可能であることを、当業者は認めよう。その他の場合では、周知の構造または動作については、本発明の特徴を曖昧にするのを避けるために、示さないか、または詳細には説明しない。
【００１１】
図１を参照すると、第１コンピュータ・システム１０２および第２コンピュータ・システム１０４が通信経路１０６を通じて通信する。これらのコンピュータ・システ ム１０２および１０４は、当技術分野では周知のように、共に動作する計算コンポーネントおよびデバイスのいずれかの集合体を含む。コンピュータ・システム １０２および１０４は、更に大きなコンピュータ・システムまたはネットワーク内部におけるコンポーネントまたはサブシステムであることも可能である。
【００１２】
通信経路１０６は、コンピュータ・システム１０２および１０４間でファイルを伝達または転送する何らかの媒体を含む。したがって、この経路１０６は、ワイヤレス接続、有線接続、および混合ワイヤレス／有線接続を含む。また、通信経路１０６は、ローカル・エリア・ネットワーク（ＬＡＮ）、市内エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、特定企業のネットワーク、オフィス間またはバックエンド(backend)ネットワーク、およびインターネットを含むネットワークへの結合部または接続部も含む。更に、通信経路１０６は、フロッピ・ディスク、ハード・ディスク・ドライブ、およびＣＤ−ＲＯＭのような、着脱可能な固定媒体、ならびに電話回線、バス、および電子メール・メッセージを含む。
【００１３】
第１通信システム１０２は、電子ファイルの元のバージョン即ち旧バージョンおよび新バージョン１１２を受信する。新ファイル１１２は、一般に、元ファイル１１０の更新または改訂バージョンであるが、そのように限定される訳ではない。電子ファイル１１０および１１２は、ソフトウェア・ファイルを含み、ダイナミック・リンク・ライブラリ・ファイル、共有オブジェクト・ファイル、埋め込みソフトウェア・コンポーネント（ＥＢＳＣ）、ファームウェア・ファイル、実行可能ファイル、１６進データ・ファイルを含むデータ・ファイル、システム・コンフィギュレーション・ファイル、ならびに個人使用データを含むファイルを含むが、これらに限定されるのではない。いずれの形式のファイルもバイト・ストリームと見なすことができるので、以後、文脈に応じて、ファイルをバイト・ストリームと記述できることとする。
【００１４】
ファイル差異発生部１１４のコンポーネントは、新ファイル１１２を受信し、これを元ファイル１１０と比較し、以下に説明するように、比較したファイル間の差異を計算する。これらの差異は、比較したファイル間のバイト・レベルでの差異を含むが、そのように限定されるのではない。ファイル差異発生部１１４は、比較の間に、差異ファイル１１６を発生する。ここでは、差異ファイル１１６をデルタ・ファイル１１６と呼ぶ。
【００１５】
一実施形態のファイル差異発生部１１４は、ホスト・コンピュータ・システム１０２のコンポーネント間で結合を行い、ここで、コンポーネントは、プロセッサ、少なくとも１つのコントローラ、少なくとも１つのメモリ・デバイス、および少なくとも１つのバスのうち少なくとも１つを含むが、そのように限定されるのではない。一実施形態のファイル差発生部１１４のコンポーネントは、少なくとも１つの前処理サブシステム１２４と、少なくとも１つの差別化サブシステム１３４とを含む。前処理サブシステム１２４のことをプリプロセッサ１２４も呼び、少なくとも１つの前処理アルゴリズム、プログラム、またはルーチンの制御の下で実行する少なくとも１つのプロセッサを含む。同様に、差別化サブシステム１３４は、少なくとも１つの差別化アルゴリズム、プログラム、またはルーチンの制御の下で実行する少なくとも１つのプロセッサを含む。
【００１６】
デルタ・ファイル１１６の内容は、新ファイル１１２と元ファイル１１０との間の差異の効率的な表現を備えている。デルタ・ファイル１１６は、２００２年５月１３日に出願され、"Byte-Level File Differencing and Updating Algorithms"（バイト・レベルにおけるファイル差別化および更新アルゴリズム）と題する米国特許出願、出願番号第１０／１４６，５４５号に記載されているように、関連するファイルの新または現バージョンと当該ファイルの以前のバージョンとの間の差異を表す、交換および／または挿入動作の実際のデータと共に、メタ・データを含む。ファイル差異発生部１１４は、最小数のバイトおよび予め規定したフォーマットまたはプロトコルを用いて、元１１０および新１１２ファイル間のいずれの差異をも、デルタ・ファイル１１６内に供給することによって、空間について最適化したデルタ・ファイルが得られる。
【００１７】
デルタ・ファイル１１６は、通信経路１０６を通じて、別の処理システム１０４に転送または送信される。転送の前に、当技術分野では周知の圧縮技法を用いて、デルタ・ファイル１１６を圧縮すると良いが、そのように限定されるのではない。受信システム１０４上にホストされた更新発生部１１８は、デルタ・ファイル１１６を、ホストされた元ファイル１１０Ｈと共に用いて、新ファイル１１２Ｃのコピーを発生即ち作成する。次いで、新ファイル１１２のこのコピーを用いて、改訂または更新の目標とするクライアント・デバイス上にホストされた元ファイル１１０Ｈを更新する。この更新プロセスの完了時には、第２コンピュータ・システム上に格納されている新ファイルは、第１コンピュータ・システム１０２において受信した新ファイル１１２と同一となっている。
【００１８】
元ファイルと新ファイルとの間の差異は、新ファイルよりも小さいのが通例であり、新ファイル全体の代わりに差異を送信し格納すれば、格納および送信の大きな節約に至る。これは、プログラムを記憶しており、通例低速で費用がかかる可能性がある接続、例えば、ワイヤレスまたはセルラ接続を介してプログラムを更新する移動電子デバイス（クライアント・デバイス）には特に重要である。デルタ・ファイルのサイズが縮小されることにより、多数の改良が得られ、その１つには、デルタ・ファイルをクライアント・デバイスに送信するために必要な帯域幅の縮小が含まれる。ファイルの小型化は、転送に必要な帯域幅が少なくて済むことを意味する。また、ファイルの小型化により、送信に必要な時間も短縮され、したがって、ファイル転送が中断される虞れが低下し、同時に、受信したファイルにおける送信エラーも低減する。加えて、安全でない接続を介して送信する場合、新たなソフトウェア画像よりも、デルタ・ファイルの方が安全である。これらの改良は全て、顧客の満足度を高めることになる。
【００１９】
図２は、図１の実施形態の下における、デルタ・ファイル発生のフロー図である。動作が開始するのは、ブロック２０４において、第１処理システムまたはコンピュータ・システムにおいて、新ファイルおよび元ファイルを受信したときである。新ファイルおよび元ファイルに対応するマップ・ファイルも受信する。マップ・ファイルは、上位テキスト・ファイルであり、ソフトウェア画像の各シンボルの開始アドレスおよびサイズを含み、シンボルの例には、関数およびグローバル変数が含まれる。マップ・ファイルは、コンパイラ／リンカ・ユーティリティによって出力され、ログ・ファイル、シンボル・ファイル、および／またはリスト・ファイルとしても知られている。
【００２０】
ブロック２０６において、新ファイルと元ファイルの内容間において前処理動作が行われ、２つのファイルの内容間で、共通セグメントおよび単純なパターンを識別する。一般に、前処理は、識別した共通セグメントおよびパターンを用いて、新ファイルおよび元ファイル間における二次変更を削減／除去する。一実施形態の前処理は、論理的な変更に伴うアドレスのずれによって生ずる元ファイルおよび新ファイル間の変更を削減および／または除去することを含む。これについては以下で説明するが、そのように限定されるのではない。つまり、この前処理は、二次的な変更を含む、ファイルの共通セグメント間の差異を削減することにより、差異計算の効率を高めるのである。
【００２１】
前処理に続いて、ブロック２０８において、新ファイルと修正した元ファイルとの間で、バイト・レベルの差異を計算する。ブロック２１０において、計算した差異をコード化し併合し、既定のエンコーディング・フォーマットにしたがってデルタ・ファイルを発生する。次いで、ブロック２１２において、当技術分野では周知のように、デルタ・ファイルを最適化して、可能であれば、更にファイル・サイズを縮小し、ブロック２１４において、最適化したデルタ・ファイルを供給する。
【００２２】
前述のように、前処理動作は、新ファイルおよび元ファイルの内容間で行われ、２つのファイルの内容間における共通セグメントおよび単純パターンを識別する。この共通セグメントおよび単純パターンの知識を用いて、二次的な変更を削減／除去することにより、全体的な性能向上(gain)が得られる。
【００２３】
前述のように、システムとクライアント・デバイスとの間における電子ファイルまたはソフトウェア・アップグレードの送信は、特に、低帯域幅チャネルを通じて行われる場合、大量の時間がかかる可能性がある。一例に、セルラ電話機のソフトウェア・アップグレードがある。セルラ・ワイヤレス結合を通じて新および元ソフトウェア・バージョン間のバイト・レベルのファイル差異即ち変更部を送ることが、典型的な慣例になっている。実行可能ファイルの新バージョンおよび元バージョン間の差異は、それらの対応するソース・ファイル間の差異よりも複雑であるので、多大な転送時間が生ずる。
【００２４】
新および元ファイル・バージョン間におけるこれら複雑な差異が生ずるのは、部分的に、ソース・ファイルにおける小さな変更によって、実行可能ファイル全体を通じて主要な変更が導入される場合が多いからである。一例として、実行可能ファイルに導入される変更には、２つの主な種類の変更、即ち、主変更および二次的変更を含み。主変更は、論理的変更とも呼ばれ、元ファイルからのソース・コード・ラインの削除、新ファイルへのソース・コード・ラインの加入、およびソース・コード・ラインの修正によって生ずるソース・コードの変更である。二次的変更は、主変更によって生ずる、およびソフトウェア・コンパイラ／リンカ・ユーティリティが発生するアドレスの変更、ポインタ・目標・アドレスの変更、およびアドレス・オフセットの変更を含むと定めるが、これらに限定されるのではない。以下で説明する前処理ルーチンは、二次的変更を除去／削減し、これらの変更の除去に関連する情報を、対応するデルタ・ファイルの情報にエンコードする。
【００２５】
実行可能ファイルはコード（テキスト）セクションおよびデータ・セクションを含むと想定して、実行可能ファイルに導入される二次的変更の分析が開始する。図３は、実行可能ファイルの元Ｖ１および新Ｖ２バージョンを示すブロック図３００である。元Ｖ１および新Ｖ２バージョンは、双方とも、コード（テキスト）セクション３１０および３２０、ならびにデータ・セクション３１２および３２２を含む。新バージョンＶ２が元バージョンＶ１と相違するのは、新バージョンＶ２は、サイズ０ｘ５００の新コード３０２の追加ブロックを含むことである。新コード３０２のブロックの存在により、２種類の二次的変更が導入される。
【００２６】
第１の種類の二次的変更は、新バージョンＶ２のコード（テキスト）セクション３２０に生じ、その結果、分岐命令ＢＲＡＮＣＨが異なる分岐変位を有することになる。これは、相対アドレスまたは分岐オフセットとも呼ばれ、分岐命令ＢＲＡＮＣＨのアドレスと目標命令アドレスＴＡＲＧＥＴとの間に新コード３０２のブロックを追加したことの結果である。この例では、目標命令アドレスは０ｘ１０００であり、分岐命令アドレスは０ｘ３０００であるので、元バージョンに０ｘ２０００（０ｘ３０００−０ｘ１０００）の分岐変位が生ずる。分岐命令アドレスと目標命令アドレスとの間に新コードのブロック（サイズは０ｘ５００）を追加することによって、分岐命令アドレスが０ｘ３５００（０ｘ３０００＋０ｘ５００）に変化する。したがって、新バージョンＶ２における分岐変位は、０ｘ２５００（０ｘ３５００−０ｘ１０００）に変化する。
【００２７】
第２の種類の二次的変更は、新バージョンＶ２のデータ・セクション３２２に生じ、対応するデータ・エリアの絶対アドレスを格納する、データ・ポインタＰＯＩＮＴＥＲ、即ち、データ・ポインタ値に変更が生ずる。このデータ・ポインタ値の変更は、新コード３０２をコード（テキスト）セクションに追加した結果である。新コード３０２は、データ・セクション３２２の前にある、元バージョン内のポイントに挿入される。したがって、元バージョンでは０ｘ８０００であるデータ・ポイント値は、新バージョンでは０ｘ８５００（０ｘ８０００＋０ｘ５００）に変化する。
【００２８】
ソフトウェアの開発が増々複雑になるに連れて、二次的変更が実行可能ファイル全体に広がり、バイト・レベルでのファイルの差別化の関連で考えると、二次的変更が主変更よりも数において勝る可能性があるところまで来ている。以下に説明する前処理ルーチンは、ファイルの元バージョンおよび新バージョン間の関係を用いて、二次的変更に関連する差異に関してデルタ・ファイルにエンコードする情報量を削減する。情報を最小限に抑えれば、バイト・レベルで差別化および再生を行う際に、縦続計算(cascading computation)の効果が得られ、デルタ・ファイルのサイズを縮小することができる。
【００２９】
概略的に、一実施形態の前処理ルーチンは、少なくとも１つの近似ルーチンと、デルタ・ファイル・サイズを最小化する際に用いる少なくとも１つの併合ルーチンとを含む。近似ルーチンは、テキスト（コード）およびデータ・モデルの想定にしたがって、二次的変更を削減／除去するように機能する。併合ルーチンは、ヒント併合ルーチン(hint merging routine)とも呼ばれ、新バージョンを受信するデバイスへの転送には、最小コスト・レベルでモデル情報をエンコードする。モデル情報は、前述のように、デバイスにおいて新バージョンを復元する際に用いられるが、そのように限定されるのではない。
【００３０】
図４は、図１および図２の実施形態の下において、電子ファイルの異なるバージョンを前処理するためのフロー図２０６である。ファイルの新および元バージョンを受信すると、ブロック４０２において、共通関数ユニットおよび共通データ・ユニットを、関連するマップ・ファイルから抽出する。ブロック４０４において、共通関数ユニットを併合して、共通関数ブロックを形成する。これについては、図１１を参照して以下で詳しく説明する。同様に、ブロック４０６において、共通データ・ユニットを併合して共通データ・ブロックを形成する。これについては図１２を参照して以下で詳しく説明する。次いで、前処理システムの前処理ルーチンは、ブロック４０８において、新および元ファイルのコード（テキスト）セクションを前処理する。これについては、図５、図６、および図７を参照しながら以下で説明する。続いて、または同時に、前処理ルーチンは、ブロック４１０において、新および元ファイルのデータ・セクションを前処理する。これについては、図８、図９、および図１０を参照しながら以下で説明する。ブロック４１２において、共通関数ブロックおよび共通データ・ブロックをエンコードし、元ファイルの修正バージョンを出力し、バイト・レベルのファイル差別化を実行する際に用いる。
【００３１】
図５は、図４の実施形態の下において、電子ファイルの異なるバージョンのコード（テキスト）セクションを前処理するためのフロー図４０８である。一般に、ファイルのコード（テキスト）セクションは、１つ以上の関数ユニットまたはブロックで構成されている。一実施形態のコード（テキスト）セクションの前処理は、ブロック５０２において、元および新ファイルの各関数ユニットの開始および終了アドレスの特定から開始する。元ファイルの関数ユニットをここでは「元関数ユニット」と呼び、新ファイルの関数ユニットをここでは「新関数ユニット」と呼ぶ。機能ユニットの開始および終了アドレスを特定するには、マップ・ファイルを用いるが、そのように限定されるのではない。
【００３２】
次に、ブロック５０４において、プリプロセッサは一意のインデックスまたはインデックス値を各一意の関数ユニットに割り当てる。このインデックス値の一意の関数ユニットへの割り当ては、元および新ファイル・バージョン双方に共通な関数ユニットの識別を支援する。その結果、ファイルの元および新バージョン双方に同じ関数ユニットが見つかった場合、その関数には共通のインデックス値を割り当てるが、実施形態はそのように限定されるのではない。
【００３３】
一例として、元関数ユニットＦ１、Ｆ２、Ｆ３、およびＦ４を含む元ファイル・バージョンと、新関数ユニットＦ１、Ｆ２、Ｆ３、およびＦ５を含む新ファイル・バージョンについて考える。プリプロセッサがインデックス値１、２、３、４、および５を用いて関数ユニットＦ１、Ｆ２、Ｆ３、Ｆ４、およびＦ５をそれぞれインデックス化（index）する場合、元ファイル・バージョンには以下の表が作成される。
【００３４】
【表１】
2009509272.tif 000003
【００３５】
同様に、新ファイル・バージョンには以下の表が作成される。
【００３６】
【表２】
2009509272.tif 000004
【００３７】
これらの表双方において、開始アドレス（startAddress）は、一般に、対応する関数ユニットの開始アドレスと定められ、したがって、「開始アドレスＶ１」は、元ファイルの関数ユニットの開始アドレスであり、「開始アドレスＶ２」は、新ファイルの関数ユニットの開始アドレスである。更に、終了アドレス（endAddress）は、関数ユニットのサイズ（function unit size）に、関数ユニットの開始アドレスを加算することによって発生するので、
【００３８】
【数１】
2009509272.tif 000005
【００３９】
となるが、実施形態はそのように限定されるのではない。その結果、終了アドレスＶ１は、元ファイルの関数ユニットの終了アドレスと定められ、一方終了アドレスＶ２は新ファイルの関数ユニットの終了アドレスと定められる。この終了アドレスの定めは、ここではデータ・ユニットにも適用されるが、そのように限定されるのではない。
【００４０】
続いて、プリプロセッサは、ブロック５０６において、前述の表からのインデックス値、開始アドレス、および終了アドレスの情報を用いて、共通関数ユニットのHintTableを発生する。HintTableは、１つの表に組み入れた共通関数ユニットの情報を含み、元ファイル・バージョン（Ｖ１）の元関数ユニットのインデックス値、開始および終了アドレス、ならびに新ファイル・バージョン（Ｖ２）の新関数ユニットの開始および終了アドレスを含む。HintTableの情報を配列するには、当技術分野では周知の技術がいくつでも用いられる。
【００４１】
【表３】
2009509272.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を含む。
【００４６】
図６を参照すると、新目標アドレス値の発生は、ブロック６０２において元ファイル・バージョンの元関数ユニットｊから、前処理が済んでいない計算可能命令を呼び出すことから開始し、ｊは、カウンタ値であり、１の値に初期化され、以後ｊ＝ｎになるまで１回毎に１ずつ増分し、ｎは、元バージョンと新バージョンとの間の共通関数ユニットの総数である。
【００４７】
次に、ブロック６０４において、以下のようにして、計算可能命令の現目標アドレスを発生または計算する。例えば、プログラム・カウンタに関連するジャンプ命令や、ロード／格納命令のような、目標アドレスを含むいずれの命令についても、目標アドレスを計算するには、現命令アドレスおよび対応する命令のデコーディング(decode(instruction))を用いる。先に引用した表記を用いると、現目標アドレスの計算は、次のようになる。
【００４８】
【数２】
2009509272.tif 000007
【００４９】
あるいは、
【００５０】
【数３】
2009509272.tif 000008
【００５１】
値[targetAddrV1-addrV1]がわかっていれば、以下のように、対応するエンコーディング方式に基づいて命令（(instruction）も計算することができる。
【００５２】
【数４】
2009509272.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の命令値と置換する。一実施形態のプリプロセッサは、少なくとも２つの仮定の下で動作するが、そのように限定されるのではない。第１の仮定は、元バージョンおよび新バージョン双方において同じサイズを有する共通関数ユニットは、元および新バージョン双方を通じて同じ命令構造を有し、命令構造は、命令型および命令順序を含むことを仮定する。第２の仮定は、第１の仮定を満たす共通関数ユニットにおけるいずれの計算可能命令についても、当該計算可能命令が関数コールであるとき、または計算可能命令の目標アドレスが、同様に第１の仮定を満たす共通関数ユニットに入るときには、通常以下のように２つの不変式が元および新バージョン双方を通じて成り立つことを仮定する。
【００５６】
【数５】
2009509272.tif 000010
【００５７】
および
【００５８】
【数６】
2009509272.tif 000011
【００５９】
このように、２つの仮定にしたがって、プリプロセッサはブロック６１０において、cal_insAに対して以下のように新命令値(targetAddrV2-addrV2)を発生する。
【００６０】
【数７】
2009509272.tif 000012
【００６１】
これを、ここでは式１と呼ぶ。
ブロック６１２において、cal_insAの新命令値を用いて、プリプロセッサは、以下のようにcal_insAを修正する。
【００６２】
【数８】
2009509272.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）を発生する。一実施形態のプリプロセッサは、データ・ユニットに関する少なくとも２つの追加の仮定の下で動作するが、そのように限定されるのではない。ここでは、これらの仮定を第３および第４の仮定と呼ぶ。第３の仮定は、元バージョンおよび新バージョン双方において同じサイズを有する共通データ・ユニットは、元および新バージョン双方を通じて同じデータ構造を有すると仮定し、データ構造には、型、サイズ、およびデータ変数の順序が含まれる。第４の仮定は、第３の仮定を満たす共通データ・ユニットにおけるいずれのデータ・ポインタについても、以下のように、不変式が全体的に元および新バージョン双方を通じて成り立つことを仮定する。
【００７５】
【数９】
2009509272.tif 000014
【００７６】
このように、第３および第４の仮定に応じて、プリプロセッサは、ブロック９０８において、次のように新データ・ユニットに新データ・ポインタ値（dataPointerV2）を発生する。
【００７７】
【数１０】
2009509272.tif 000015
【００７８】
これをここでは式２と呼ぶ。
ブロック９１０において、データ・ポインタ値dataPointerV2を用いて、プリプロセッサは、元バージョンにおける対応するアドレスにおいて、dataPointerV1をdataPointerV2と置換する。続いて、ブロック９１２において、プリプロセッサは、前処理が済んでいないデータ・ポインタが未だ元データ・ユニットに残っているか否か判定を行う。
【００７９】
前処理が済んでいないまま残っている元データ・ユニットのデータ・ポインタがある場合、プリプロセッサはブロック９０２に戻って、元データ・ユニットから別の、あるいは次の未処理のデータ・ポインタを読み出し、前述のように前処理が続けられる。元データ・ユニットのデータ・ポインタ全てを前処理したとブロック９１２において判定した場合、プリプロセッサは、ブロック９１４において、新ファイルの近似バージョンを含む元ファイルの修正バージョンを出力する。
【００８０】
先にHintTableにおいて用いた、共通関数ユニットおよび共通データ・ユニットの開始および終了アドレスは、異なるファイル・バージョン間において共通ユニットの相対的な位置付けを決定する際にそれらを使用したので、「アルゴリズム・ヒント」または「ヒント」と呼ぶことにする。したがって、ヒントはクライアント・デバイスに転送される。クライアント・デバイスは、前述のように、差異即ちデルタ・ファイルを受信し、デルタ・ファイルおよび元ファイルから新ファイル・バージョンを復元する際にこのファイルを用いる。ヒントの転送は、デルタ・ファイルおよびその他の情報をクライアント・デバイスに転送する際に用いられるのと同じ低帯域幅チャネルを通じて行われるので、一実施形態のプリプロセッサは、ヒントの併合を行い、HintTableの共通関数ユニットおよび共通データ・ユニットを併合するが、前処理アルゴリズムやルーチンの遂行に影響はない。この併合により、ヒントを含むファイルのサイズが縮小し、結果的に、クライアント・デバイスに転送する情報量が減少する。
【００８１】
前述のコード（テキスト）セクションの前処理から得られる共通関数ユニットを用いて、そして図４に戻って、プリプロセッサは、ブロック４０４において、ヒント併合ルーチンまたはアルゴリズムの制御の下で、共通関数ユニットを併合し、共通関数ブロックを形成する。図１１は、図４の実施形態の下における、共通関数ユニットのヒント併合４０４のフロー図である。
【００８２】
同様に、プリプロセッサは、ブロック４０６において、前述のデータ・セクションの前処理から得られた共通データ・ユニットを用いて、共通データ・ユニットを併合し、共通データ・ブロックを形成する。図１２は、図４の実施形態の下における、共通データ・ファイルのヒント併合４０６のフロー図である。共通関数ユニットおよび共通データ・ユニットのヒント併合について順に以下で説明する。
【００８３】
ここでは明確化のために、共通関数ユニットおよび共通データ・ユニットのヒント併合を別個に説明するが、実施形態は、併合に伴う動作をいずれの順序またはいずれの組み合わせでも実行することができる。表記に関して、関数またはデータ・ユニットの開始アドレスを、全体的に、ここでは前述のように表記「startAddress」を用いて示すこととする。したがって、「startAddressV1」は、元関数またはデータ・ユニットの開始アドレスを示し、一方「startAddressV2」は、新関数またはデータ・ユニットにおける対応する開始アドレスを示す。同様に、関数またはデータ・ユニットの終了アドレスを、全体的に、ここでは表記「endAddress」を用いて示すこととする。したがって、「endAddressV1」は、元関数またはデータ・ユニットの終了アドレスを示し、一方「endAddressV2」は新関数またはデータ・ユニットにおける対応する終了アドレスを示す。
【００８４】
図５を参照して先に説明したように、共通関数ユニットのHintTableを発生する。これは、１つの表に組み込まれた共通関数ユニットの情報を含み、元ファイル・バージョンＶ１の元関数ユニットの開始および終了アドレス、ならびに新ファイル・バージョンＶ２の新関数ユニットの開始および終了アドレスを含む。先に提示したHintTableは、共通関数ユニットのヒント併合を説明する際に一例として用いられたが、実施形態はそのように限定されるのではない。
【００８５】
【表４】
2009509272.tif 000016
【００８６】
図４および図１１ならびにHintTableを参照すると、共通関数ユニットのヒント併合４０４の動作は、ブロック１１０２において、プリプロセッサがHintTableのｎ個のエントリ全てを使用可能と印し、カウンタをｊ＝１と設定し、関連するHintTableから関数ユニットｊおよびユニット（ｊ＋１）の元および新バージョンを読み出すことから開始する。この例では、ユニットｊおよびユニット（ｊ＋１）の値は、HintTableのインデックス値に対応し、ｊ＝１、２、．．．（ｎ＋１）であるが、そのように限定されるのではない。更に、ｊの値を初期状態において１に等しく設定し、ヒント併合４０４が進展するに連れて、そして共通ユニットを処理するに連れて、当技術分野では周知の方法を用いて、以後増分させていく。したがって、インデックス値１および２（ｊ＋１＝１＋１＝２）と関連付けられている共通関数ユニットの情報を、ブロック１１０２において、呼び出す。
【００８７】
ブロック１１０４において、プリプロセッサは、共通関数ユニットｊの元バージョンＶ１および新バージョンＶ２はサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【００８８】
【数１１】
2009509272.tif 000017
【００８９】
しかし、そのように限定されているのではない。元Ｖ１および新Ｖ２バージョンが異なるサイズのファイルを有する場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９０】
元バージョンＶ１および新バージョンＶ２のサイズが等しい場合、プリプロセッサは、ブロック１１０６において、以下のように、共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【００９１】
【数１２】
2009509272.tif 000018
【００９２】
しかし、そのように限定されているのではない。共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスとは異なる場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９３】
共通関数ユニットｊの元バージョンＶ１の終了アドレスが、共通関数ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一である場合、プリプロセッサは、ブロック１１０８において、共通関数ユニットｊの新バージョンＶ２の終了アドレスが、以下のように、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一か否か判定を行う。
【００９４】
【数１３】
2009509272.tif 000019
【００９５】
しかし、そのように限定されているのではない。共通関数ユニットｊの新バージョンＶ２の終了アドレスが、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスとは異なる場合、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９６】
共通関数ユニットｊの新バージョンＶ２の終了アドレスが、共通関数ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一である場合、プリプロセッサは、ブロック１１１０において、共通関数ユニットｊおよび共通関数ユニット（ｊ＋１）の情報を併合して共通関数ブロックを形成し、ユニット（ｊ＋１）のエントリを置換し、ついでユニットｊのエントリに使用不可能と印する。次いで、動作は、ブロック１１１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【００９７】
プリプロセッサは、ブロック１１１２において、ｊの値が量（ｎ−１）未満か否か判定を行う。ｊの値が量（ｎ−１）に等しく、全ての関数ユニットを前処理し終えたことを示す場合、動作は、ブロック１１１６に進み、全ての使用可能なエントリを共通関数ブロックとして出力し、そして動作は戻る。ｊの値が量（ｎ−１）未満であり、前処理が済んでいない関数ユニットが残っていることを示す場合、ブロック１１１４において、ｊの値を増分し、動作は、ブロック１１０２に進み、ｊの新しい値に対応する共通関数ユニットの情報を読み出す。次いで、前処理は前述のように続けられる。
【００９８】
以下に、図１１およびHintTableを参照して、共通関数ユニットのヒント併合を伴う例について説明する。動作は、プリプロセッサが３つのエントリ全てを使用可能と印し、HintTableから関数ユニット１および２の元および新バージョンを読み出すことから開始する。次いで、プリプロセッサは、共通関数ユニット１の元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【００９９】
【数１４】
2009509272.tif 000020
【０１００】
HintTableからの実際の値を代入すると、以下のようになる。
【０１０１】
【数１５】
2009509272.tif 000021
【０１０２】
元バージョンＶ１および新バージョンＶ２はサイズが等しいので、プリプロセッサは次に、共通関数ユニット１の元バージョンＶ１の終了アドレスが、次のように、共通関数ユニット２の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１０３】
【数１６】
2009509272.tif 000022
【０１０４】
HintTableからの実際の値を代入すると、以下のように、共通関数ユニット１の元バージョンＶ１の終了アドレスが、共通関数ユニット２の元バージョンの開始アドレスと同一であるという判定が得られる。
【０１０５】
【数１７】
2009509272.tif 000023
【０１０６】
共通関数ユニット１の元バージョンＶ１の終了アドレスは、共通関数ユニット２の元バージョンＶ１の開始アドレスと同一であるので、次に、共通関数ユニット１の新バージョンＶ２の終了アドレスが、以下のように、共通関数ユニット２の新バージョンＶ２の開始アドレスと同一か否かについて判定を行う。
【０１０７】
【数１８】
2009509272.tif 000024
【０１０８】
HintTableからの実際の値を代入すると、以下のように、共通関数ユニット１の新バージョンＶ２の終了アドレスが、共通関数ユニット２の新バージョンＶ２の開始アドレスと同一であるという判定が得られる。
【０１０９】
【数１９】
2009509272.tif 000025
【０１１０】
共通関数ユニット１の新バージョンＶ２の終了アドレスが共通関数ユニット２の新バージョンＶ２の開始アドレスと同一であるという判定に応答して、プリプロセッサは、共通関数ユニット１および共通関数ユニット２の情報を併合し、以下のような共通関数ブロックを形成する。
【０１１１】
【表５】
2009509272.tif 000026
【０１１２】
例を続けると、プリプロセッサは、次に、HintTableから関数ユニット２および３の元および新バージョンを読み出す。プリプロセッサは、共通関数ユニット２の元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始アドレスと終了アドレスとの間の差を取る。
【０１１３】
【数２０】
2009509272.tif 000027
【０１１４】
HintTableからの実際の値を代入すると、次の結果が得られる。
【０１１５】
【数２１】
2009509272.tif 000028
【０１１６】
これは、元バージョンＶ１および新バージョンＶ２のサイズが等しいことを示す。
次に、プリプロセッサは、共通関数ユニット２の元バージョンＶ１の終了アドレスが、以下のように、共通関数ユニット３の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１１７】
【数２２】
2009509272.tif 000029
【０１１８】
HintTableからの実際の値を代入すると、共通関数ユニット２の元バージョンＶ１の終了アドレスは、以下のように、共通関数ユニット３の元バージョンＶ１の開始アドレスとは異なるという判定が得られる。
【０１１９】
【数２３】
2009509272.tif 000030
【０１２０】
共通関数ユニット２の元バージョンＶ１の終了アドレスが、共通関数ユニット３の元バージョンＶ１の開始アドレスと同一ではないので、動作は戻り、共通関数ユニット２および３を併合して共通関数ブロックを形成することは行わない。
【０１２１】
共通関数ユニットを併合した後、前述の例のHintTableの使用可能なエントリは、出力に対して次のようになる。
【０１２２】
【表６】
2009509272.tif 000031
【０１２３】
一実施形態のプリプロセッサは、共通関数ユニットに関して先に説明したのと同様にして、共通データ・ユニットのヒント併合を実行する。図４および図１２を参照すると、共通データ・ユニットのヒント併合４０６の動作は、ブロック１２０２において、プリプロセッサがHintTableのｎ個のエントリ全てに印を付け、カウンタをｊ＝１に設定し、関連するHintTableからデータ・ユニットｊおよび（ｊ＋１）の元および新バージョンを読み出すことから開始する。ユニットｊおよびユニット（ｊ＋１）の値は、HintTableのインデックス値に対応し、ここで、ｊ＝１，２，．．．（ｎ−１）であるが、そのように限定されるのではない。
【０１２４】
ブロック１２０４において、プリプロセッサは、共通データ・ユニットｊの元バージョンＶ１および新バージョンＶ２のサイズが等しいか否か判定を行う。この判定を行うには、以下のように、元Ｖ１および新Ｖ２バージョンの開始および終了アドレス間の差を取る。
【０１２５】
【数２４】
2009509272.tif 000032
【０１２６】
しかし、そのように限定されるのではない。元Ｖ１および新Ｖ２バージョンが異なるサイズのファイルを有する場合、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１２７】
元バージョンＶ１および新バージョンＶ２のサイズが等しい場合、プリプロセッサは、ブロック１２０６において、以下のように、共通データ・ユニットｊの元バージョンＶ１の終了アドレスが、共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一か否か判定を行う。
【０１２８】
【数２５】
2009509272.tif 000033
【０１２９】
しかし、そのように限定されるのではない。共通データ・ユニットｊの元バージョンＶ１の終了アドレスが共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと異なる場合、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３０】
共通データ・ユニットｊの元バージョンＶ１の終了アドレスが共通データ・ユニット（ｊ＋１）の元バージョンＶ１の開始アドレスと同一である場合、プリプロセッサは、ブロック１２０８において、共通データ・ユニットｊの新バージョンＶ２の終了アドレスが、以下のように、共通データ・ユニット（ｊ＋１）の新バージョンの開始アドレスと同一か否か判定を行う。
【０１３１】
【数２６】
2009509272.tif 000034
【０１３２】
しかし、そのように限定されるのではない。共通データ・ユニットｊの新バージョンＶ２の終了アドレスが共通データ・ユニット（ｊ＋１）の新バージョンの開始アドレスとは異なる場合、動作はブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３３】
共通データ・ユニットｊの新バージョンＶ２の終了アドレスが共通データ・ユニット（ｊ＋１）の新バージョンＶ２の開始アドレスと同一である場合、プリプロセッサは、ブロック１２１０において、共通データ・ユニットｊおよび共通データ・ユニット（ｊ＋１）の情報を併合して共通データ・ブロックを形成し、ユニット（ｊ＋１）のエントリを置換し、次いで、ユニットｊのエントリに使用不可と印する。次いで、動作は、ブロック１２１２に進み、ｊの値が量（ｎ−１）未満か否か判定を行う。
【０１３４】
プリプロセッサは、ブロック１２１２において、ｊの値が量（ｎ−１）未満か否か判定を行う。ｊの値が量（ｎ−１）と等しく、全ての関数ユニットを前処理し終えたことを示す場合、動作は、ブロック１２１６に進み、HintTable内にある使用可能なエントリを共通データ・ブロックとして出力し、動作は戻る。ｊの値が量（ｎ−１）未満であり、前処理が済んでいない関数ユニットが残っていることを示す場合、ブロック１２１４においてｊの値を増分し、動作はブロック１２０２に進み、ｊの新しい値に対応する共通データ・ユニットの情報を読み出す。次いで、前述のように前処理が継続する。
【０１３５】
電子ファイルの異なるバージョンを前処理するために説明したシステムおよび方法は、いずれの数の命令アーキテクチャを用いたいずれの数の処理および／またはプロセッサに基づくシステムのソフトウェアおよび実行可能ファイルにも適用することができる。例えば、この中におけるシステムおよび方法は、"ARM Architecture Reference Manual" 2nd Edition, by D.Jagger and D. Seal（Ｄ．ジェガーおよびＤ．シールによる「ＡＲＭアーキテクチャ参考書」第２版）に記載されているように、ＡＲＭ(R)アーキテクチャにおいても用いることができる。ＡＲＭ（登録商標）アーキテクチャは、１６／３２ビット埋め込み減少命令セット・コンピュータ（ＲＩＳＣ）コアに基づき、Ｔｈｕｍｂ１６−ビット命令セットを組み込んだマイクロプロセッサ・アーキテクチャである。ＡＲＭ(R)アーキテクチャにおいて用いる場合、例えば、先に引用した計算可能命令は、ＡＲＭ／Ｔｈｕｍｂ命令セットの"branch with link (BL)"および"branch with link and change mode to ARM/Thumb(BLX)"命令を含む。更に、先に引用したデータ・ポインタは、ＡＲＭ／Ｔｈｕｍｂ命令セットのＤＣＤ命令を含む。
【０１３６】
ここに記載する一実施形態の処理は、コンパイラ／リンカ・ユーティリティが発生するマップ・ファイル、シンボル・ファイル、あるいはログ・ファイルからのシンボル情報を使用せずに、１対のソフトウェア・エクゼキュータブル(software executable)から直接共通コード／データ表を発生する前処理に加えて、後処理も含む。前処理したデータの後処理は、前述のような共通コード・ブロックのアレイの後処理を含む。
【０１３７】
図１３は、一実施形態の下において１つ以上の新コード・ブロックを発生する後処理を示す。図１４は、一実施形態の下において、１つ以上の既に特定した共通コード・ブロックのサイズを増大させつつ、少なくとも１つの新コード・ブロックを発生するデータの前処理の後処理を示す。ここに記載するように、元ファイル・バージョンおよび新ファイル・バージョン間の差異ファイル発生の一部として、ファイルの元バージョンおよび新バージョンを前処理するシステムおよび方法を提供する。種々の実施形態は、前処理の一部として、ファイル・バージョン間において近似規則を用いて、二次的変更を除去／削減し、これらの変更の除去に関する情報を、対応する差異ファイル内にエンコードする。差異ファイルは「無線によって」(over-the-air)送り、異なるコンピュータ・システム上において新ファイル・バージョンのコピーを発生するために用いることができる。
【０１３８】
図１３および図１４を参照すると、左側の縦軸は、「旧画像Ｖ１」と称され、電子ファイルの元バージョンを表す。右側の縦軸は、「新画像Ｖ２」と称され、電子ファイルの新バージョンを表す。各縦軸は、バイト・シーケンスのような、コードの単位を表す。旧画像Ｖ１および新画像Ｖ２は、前処理した命令の性能を向上させる後処理システムおよび方法の実施形態について説明する際に用いる。
【０１３９】
一実施形態では、後処理は、命令特性を試験して、以下に記載する、指定された関係を有する命令対を判定する。例えば、後処理処理(post-processing processing)は、命令特性を試験して、整合命令(aligned instructions)の対を判定する。整合命令の対毎に、後処理は１対の目標アドレスを発生する。目標アドレスの対を収集した後、後処理アルゴリズムを用いて、既存の（既知の）共通コード・ブロックの一部を拡張する、および／または新しい共通コード・ブロックを作成することができる。後処理アルゴリズムは、前処理成功率の上昇と前処理データの全体量の抑制との間におけるいかなるトレードオフをも考慮する。これは重要な考慮点である。何故なら、大量の新しい前処理データを導入することによって、前処理成功率を容易に高めることはできるが、これは望ましくないからである。後処理アルゴリズムの１つ以上が共通コード・ブロックを改良した後、次に、いずれのデータ・ブロックも計算し直すことにより、データ・ポインタを有する命令の前処理性能を改善する。このような命令は、馴染みのあるＡＲＭ  ＬＤＲ命令を含むが、これに限定されるのではない。
【０１４０】
ここに記載する前処理済みデータの後処理は、前処理済みデータを共通コード・ブロックのアレイとして受け取る。例えば、ＴｈｕｍｂＢＬ命令のような計算可能な命令を１つ以上の共通コード・ブロックにおいて分析し、共通コード・ブロックを拡張および／または追加するか否か決定するために用いることができる、命令特性を識別することができる。例えば、計算可能命令を分析して、画像には目標アドレスを有するが既知の共通コード・ブロックにはそれを有さない命令を識別することができる。旧画像および新画像は双方ともこの時点において入手可能であるので、コード・ブロックの中に、整合命令のような、指定された関係を有する命令があるか否か判定を行うことができる。次に、この関係および／または命令の開始アドレスおよび／または目標アドレスに部分的に基づいて、追加および／または拡張するか否かについての評価を行うことができる。開始および目標アドレスを含む、この種のデータの集合体に基づいて、既知の共通コード・ブロックを拡張することができ、および／または共通コード・ブロックを発生することができる。
【０１４１】
一実施形態の後処理では、旧画像におけるバイト数に等しいサイズの２つの整数アレイを作成することによって、データを収集する。整数の全てを０に初期化し、更に、
【０１４２】
【数２７】
2009509272.tif 000035
【０１４３】
アドレス「ｉ」が旧画像内にあり、そして既知のコード・ブロックにはない場合、後方[i]は、直前のコード・ブロックを前方に拡張してアドレス「ｉ」を含ませる場合に、正しく前処理されるＢＬ命令のような命令の数をカウントする。前方[i]は、続くコード・ブロックを後方に拡張してアドレス「ｉ」を含ませる場合、正しく前処理される命令の数をカウントする。また、後処理は、addr_pair構造のリストも作成する。この構造には、命令に考慮するには十分であるはずの旧画像におけるバイト数の約半分に等しいサイズが割り当てられている。例えば、関連するビットはＴｈｕｍｂＢＬ命令の第１部および第２部では異なるので、画像におけるＢＬ命令は、当該画像におけるバイト数の約１／４よりも多くなければならない。リストに格納されているaddr_pairの数を追跡する変数があり、初期状態において０に設定されている。
【０１４４】
一実施形態のaddr_pair構造は、
【０１４５】
【数２８】
2009509272.tif 000036
【０１４６】
のような１対の値を含む。
これらの値は、球画像における目標アドレス、および新画像における目標アドレスを表すが、実施形態はそのように限定されるのではない。１対の目標アドレスが含む特性により、直前または直後のコード・ブロックのいずれを用いても命令が正しく前処理されなかった場合、この対をこのリストに追加する。一般に、「後方」および「前方」アレイは、既知のコード・ブロックを拡張しようとするときに用いることができ、addr_pairリストは、新しいコード・ブロックを作成しようとするときに用いることができる。
【０１４７】
図１３に示すように、旧画像Ｖ１および新画像Ｖ２は、ある数の既知の共通コード・ブロック１３００、１３０２、１３０４と、１つの新しい共通コード・ブロック１３０７とを含む。例えば、既知の共通コード・ブロック１３００は、ＪＰＥＧまたはＭＰＥＧファイルを表すことができる。既知の共通コード・ブロック１３０２は、ＷＡＶファイルを表すことができる。既知の共通コード・ブロック１３０４は、アドレス・ブックを表すことができる。共通コード・ブロック１３０７は、一実施形態の後処理によって発生した「新しい」共通コード・ブロックである（共通コード・ブロック１３０７）の「破線」の境界は、それを新しい共通コード・ブロックとして表す）。ある数の共通コード・ブロックを描画したが、共通コード・ブロックの数はこれよりも多くてもまたは少なくてもよい。
【０１４８】
一実施形態の後処理は、相対アドレシングの概念を用いる命令の前処理の性能を改善する。このような命令は、「ビーコン」または「一般化ビーコン」と呼ぶこともできる。これらは、馴染みのあるARM BL命令のような、計算可能命令を含むが、これに限定されるのではない。旧画像および新画像双方は、前処理データを作成するときに利用可能であるので、共通コード・ブロックにおける整合場所(aligned locations)に命令があるか否か検査することが可能となる。また、関連する開始および／または目標アドレスを試験することも可能である。開始および／または目標アドレスを含む、命令に関するこの種のデータの集合体に基づいて、既存の共通コード・ブロックを拡張すること、および／または新しい共通コード・ブロックを作成することが可能となる。
【０１４９】
一実施形態によれば、新しいコード・ブロックを作成することを試みるために、addr_pairリストを用いる関数／アルゴリズムがある。
例えば、この起用は、以下のように新しいコード・ブロックを作成しようとするために、addr_pairリストを用いる。
【０１５０】
【表７】
2009509272.tif 000037
【０１５１】
図１３は、新しい共通コード・ブロック１３０７の追加に至る後処理を描画する。共通コード・ブロック１３０７のような、新しい共通コード・ブロックを追加するか否か判断するときに、後処理は、画像内には目標アドレスを有するが既知のコード・ブロックには有さない命令を識別する。例えば、後処理は、命令１３０８、１３１０、１３１２、および１３１４を、１つ以上の新しい共通コード・ブロックの発生に通じる可能性がある特性を含む命令として識別している。各命令は、関連する開始アドレスおよび目標アドレス（１３０８ａ〜ｂ、１３１０ａ〜ｂ、および１３１４ａ〜ｂ）。命令１３０８、１３１０、１３１２、および１３１４の後処理の結果、新しい共通コード・ブロック１３０７が追加されることになる。
【０１５２】
前述のように、後処理は、命令１３０８、１３１０、１３１２、および１３１４を、新しい共通コード・ブロック１３０７の作成を促す特性を有すると識別する。例えば、後処理は、命令１３０８、１３１０、１３１２、および１３１４の目標アドレス１３０８ｂ、１３１０ｂ、１３１２ｂ、および１３１４ｂが、既知のコード・ブロックには存在せず、定義された最少空間にしたがって離間されていることを識別する。加えて、命令１３０８、１３１０、１３１２、および１３１４の開始アドレス１３０８ａ、１３１０ａ、１３１２ａ、および１３１４ａは、既知の共通コード・ブロック１３０６のような、１つ以上の既知の共通コード・ブロックの中に存在する。
【０１５３】
目標アドレス１３０８ｂ、１３１０ｂ、１３１２ｂ、および１３１４ｂ間の間隔は、新しい共通コード・ブロックを作成するか否かの判断に用いることができる１つの要因に過ぎない。共通エリアを指し示す目標アドレスを含む命令の数は、新しい共通コード・ブロックを作成するか否かの判断に用いることができる更に別の要因である。加えて、共通エリアを指し示す目標アドレスを含む命令の頻度も、新しい共通コード・ブロックを作成するか否かの判断に用いることができる別の要因である。一実施形態によれば、命令数、命令の頻度、旧および新画像における１つ以上の共通コード・エリアを指し示す命令間の間隔の内少なくとも１つに基づいて、１つ以上の新しいコード・ブロックを作成する。
【０１５４】
これより図１４を参照して、一実施形態の下において、後処理を用いて、１つ以上の以前に識別した共通コード・ブロックのサイズを増大する、即ち、拡張しつつ、当たらし共通コード・ブロックも発生する。コード・ブロックを後処理するアルゴリズムに関して、この関数／アルゴリズムがコード・ブロックを拡張するために、以下のように「後方」および「前方」アレイを用いることができる。
【０１５５】
【表８】
2009509272.tif 000038
【０１５６】
図１４に示すように、旧画像Ｖ１および新画像Ｖ２は、多数の既知の共通コード・ブロック１４００、１４０２、１４０４、１４０６と、新しい共通コード・ブロック１４０８とを含む。先に論じたように、後処理は、既知の共通コード・ブロック１４００〜１４０６の内１つ以上というような、１つ以上の以前に識別した共通コード・ブロックのサイズを増大する、即ち、拡張することができる。共通コード・ブロック１４０２のような、既知の共通コード・ブロックを拡張または拡大するか否か判断するときに、後処理は、画像内には目標アドレスを有するが既知のコード・ブロック内には有さない命令を識別する。また、後処理は、命令および／または既知の共通コード・ブロックに関して計算可能な関係を有する開始アドレスを有する命令も識別する。
【０１５７】
例えば、後処理は、命令１４１０および１４１２を、既知の共通コード・ブロック１４０２のような１つ以上の共通コード・ブロックの拡大に通ずる可能性がある特性を含む命令として識別している。即ち、識別された命令１４１０および１４１２は、既知の共通コード・ブロック内にはない、対応する目標アドレス１４１０ｂおよび１４１２ｂを有する。目標アドレス１４１０ｂおよび１４１２ｂは、既知の共通コード・ブロックにはないので、この場合、後処理は、命令１４１０および１４１２の１つ以上の特性を評価して、既知の共通コード・ブロック１４０２を拡大するか否か判断することができる。
【０１５８】
目標アドレス１４１０ｂおよび１４１２ｂが既知の共通コード・ブロックにはないと判断した後、後処理は、命令１４１０および１４１２の各開始アドレス１４１０ａおよび１４１２ａを試験して、目標アドレス１４１０ｂおよび１４１２ｂを含むように既知の共通コード・ブロック１４０２を拡大するか否か判断することができる。一実施形態によれば、開始アドレス１４１０ａは既知の共通コード・ブロック１４００の中にあるので、後処理は命令１４１０の開始アドレス１４１０ａと既知の共通コード・ブロック１４００の開始アドレス１４００ａとの間のオフセット即ち差異を試験する。この差異を図１４では「デルタ−ａ」で表している。同様に、後処理は、命令１４１２の開始アドレス１４１２ａと既知の共通コード・ブロック１４００の開始アドレス１４００ｂとの間のオフセット即ち差異を試験する。この差異を「デルタ−ｂ」で表す。
【０１５９】
デルタ−ａがデルタ−ｂに等しい場合、開始アドレス１４１０ａおよび１４１２ａは整合されており、後処理は、目標アドレス１４１０ｂおよび１４１２ｂを含むように、既知の共通コード・ブロック１４０２を拡大する。言い換えると、命令１４１０および１４１２の１つ以上の特性に基づいて、後処理は、共通コード・ブロック１４０２のサイズを増大し、その結果目標アドレス１４１０ｂおよび１４１２ｂが拡大した共通コード・ブロック１４０２によって内包されるようにすることができる。しがって、拡張共通コード・ブロック１４０２は、共通コード・ブロック１４０２のサイズ増大に対応する新しい境界を含む。後処理は、後方および／または前方アレイを用いることによってHintTableにおける２つの数値を変更することにより、共通コード・ブロックのサイズを拡張することができる。（StartADDRV1(i)およびStartADDV2(i)を修正することにより）境界を移動させると、前述のSIZE変数も変化する場合がある。
【０１６０】
更に別の例として、後処理は、命令１４１４および１４１６を、既知の共通コード・ブロック１４０６のような１つ以上の既知の共通コード・ブロックの拡大に至る可能性がある特性を含む命令として識別している。即ち、識別された命令１４１４および１４１６は、既知の共通コード・ブロックの中にはない、対応する目標アドレス１４１４ｂおよび１４１６ｂを有する。目標アドレス１４１４ｂおよび１４１６ｂは既知の共通コード・ブロックの中にはないので、この場合、後処理は１つ以上の命令１４１４および１４１６の１つ以上の特性を評価して、既知の共通コード・ブロック１４０６を拡大するか否か判断することができる。
【０１６１】
目標アドレス１４１４ｂおよび１４１６ｂは既知の共通コード・ブロックの中にはないので、後処理は、命令１４１４および１４１６の各開始アドレス１４１４ａおよび１４１６ａを試験して、目標アドレス１４１４ｂおよび１４１６ｂを含むように、既知の共通コード・ブロック１４０６を拡大するか否か判断する。前述のように、一実施形態によれば、後処理は、命令１４１４の開始アドレス１４１４ａと既知の共通コード・ブロック１４０４の開始アドレス１４０４ａとの間のオフセット即ち差異を試験する。この差異を図１４では「デルタ−ｃ」で表す。同様に、後処理は、命令１４１６の開始アドレス１４１６ａと既知の共通コード・ブロック１４０４の開始アドレス１４０４ａとの間のオフセット即ち差異を検査する。この差異を「デルタ−ｄ」で表す。
【０１６２】
デルタ−ｃがデルタ−ｄに等しい場合、開始アドレス１４１４ａおよび１４１６ａは整合されており、後処理は、目標アドレス１４１４ｂおよび１４１６ｂを含むように、既知の共通コード・ブロック１４０４を拡大する。別の言い方をすると、命令１４１４および１４１６の１つ以上の特性に基づいて、後処理は、共通コード・ブロック１４０６のサイズを増大し、その後では目標アドレス１４１４ｂおよび１４１６ｂが、拡大した共通コード・ブロック１４０６によって内包されるようにすることができる。その結果、拡張共通コード・ブロック１４０６は、共通コード・ブロック１４０６のサイズ増大に対応する、新しい境界１４２０を含むことになる。この例では、共通コード・ブロック１４０６は後方に拡張するのに対して、最初の例では、共通コード・ブロック１４０２は前方に拡張する。後方または前方のどちらに拡張するかについての判断は、前述のように、現在燃え処理する命令の数に少なくとも部分的に基づく。
【０１６３】
既知の共通コード・ブロック１４０２および１４０６を拡張することに加えて、後処理は新しい共通コード・ブロック１４０８を追加している。共通コード・ブロック１４０８は、「新しい」共通コード・ブロックであり、一実施形態の後処理によって発生した（共通コード・ブロック１４０８の「破線」の境界は、これが新しい共通コード・ブロックであることを表す）。共通コード・ブロック１４０８のような新しい共通コード・ブロックを追加するか否か判断するときに、後処理は、画像内には目標アドレスを有するが既知のコード・ブロック内には有さない命令を識別する。例えば、後処理は、命令１４２２、１４２４、１４２６、および１４２８を、１つ以上の新しい共通コード・ブロックの発生に至る可能性がある特性を含む命令として識別している。命令１４２２、１４２４、１４２６、および１４２８の後処理の結果、新しい共通コード・ブロック１４０８が追加されることになった。
【０１６４】
前述のように、後処理は、命令１４２２、１４２４、１４２６、および１４２８を、新しい共通コード・ブロック１４０８の作成を促す特性を有すると識別している。例えば、後処理は、目標アドレス１４２２ｂ、１４２４ｂ、１４２６ｂ、および１４２８ｂが既知のコード・ブロックの中には存在せず、定義された最少間隔にしたがって離間されていることを識別している。加えて、開始アドレス１４２２ａ、１４２４ａ、１４２６ａ、および１４２８ａは、既知の共通コード・ブロック１４０２および１４０４の中に存在する。目標アドレス１４２２ｂ、１４２４ｂ、１４２６ｂ、および１４２８ｂの間の間隔は、新コマンド・コード・ブロック１４０８のような新しい共通コード・ブロックを作成するか否かの判断に用いることができる１つの要因に過ぎない。
【０１６５】
共通エリアを差し示す目標アドレスを含む命令の数は、新コマンド・コード・ブロックを作成するか否かの判断に用いることができる別の要因である。加えて、共通エリアを指し示す目標アドレスを含む命令の頻度も、新しい共通コード・ブロックを作成するか否かの判断に用いることができる別の要因である。一実施形態によれば、命令数、命令の頻度、旧バージョンおよび新バージョンにおける１つ以上の共通コード・エリアを指し示す命令間の間隔の内少なくとも１つに基づいて、１つ以上の新しいコード・ブロックを作成する。
【０１６６】
変更することができるパラメータは、以下を含むが、これらに限定されるのではない。
【０１６７】
【表９】
2009509272.tif 000039
【０１６８】
場合によっては、後処理技法を用いて実現される改良全体が劇的なこともある。これは、部分的に、実施形態が発見することができる共通コード・ブロックは、サイズが小さいが、画像内部の命令のグラフ全体に関しては非常に重要であるからである。このような例の１つをあげるとすれば、ＡＲＭコードにおいて共通であるベニヤ(veneer)であろう。ベニヤは、数バイトに過ぎないことが多く、したがって従来の技法を用いて検出するのは困難である。
【０１６９】
一実施形態の「データ・アレイ」は、以下を含むが、これに限定されるのではない。
【０１７０】
【表１０】
2009509272.tif 000040
【０１７１】
一実施形態によれば、コード・ブロック・アレイの所与の入力に対して、２つの異なる後処理手順を実行することができ、正しく前処理された命令の数に基づいて手順を選択する。２つの異なる手順は、以下に記載する第１手順および第２手順を含む。第１手順は、データ・アレイをクリアすること、入力コード・ブロックに基づいてデータ・アレイを計算すること、modify_tryToAddArray()、データ・アレイをクリアすること、修正したコード・ブロックに基づいて、データ・アレイを計算すること、modify_tryToExtend()、そして修正したコード・ブロックに基づいて、正しく前処理された命令の数を計算することを含むが、これらに限定されるのではない。
【０１７２】
第２手順は、データ・アレイをクリアすること、入力コード・ブロックに基づいて、データ・アレイを計算すること、modify_tryToExtend()、データ・アレイをクリアすること、修正したコード・ブロックに基づいて、データ・アレイを計算すること、正しく前処理された命令の数を計算することを含むがこれらに限定されるのではない。第１手順および第２手順は、これらが逆のシーケンスでアルゴリズム（modify_tryToAddArray()およびmodify_tryToExtend()）を用いるという点で相違する。第１または第２手順の選択は、少なくとも部分的に、正しく前処理された命令の数に基づいて行われる。
【０１７３】
図１５Ａから図１５Ｆは、先に論じた前処理および後処理方法論の結果例を提示するグラフ表現である。サンプル・データは、「旧画像」を表す「v1.bin」、および「新画像」を表す「v2.bin」を含む。２つの画像は、近似的に同数のＢＬ命令を有する。v1.binには２５９，６５３個のＢＬ命令があり、v2.binには２６１，２８３個のＢＬ命令がある。
【０１７４】
図１５Ａは、前処理後の結果を描画する。図１５Ａに示すように、共通コード・ブロックの数が、可変幅を有する垂直方向の帯のように見える。例えば、１５００、１５０２、１５０４、１５０６、１５０８、１５１０、および１５１２は、共通コード・ブロックの例である。共通コード・ブロック１５００〜１５１２に加えて、図１５Ａは他の共通コード・ブロックも含む。図１５Ａの下にある横軸は、いずれかの充填領域(padding region)の除去後における旧画像（v1.bin)のアドレス空間である。図の中間にある横軸は、いずれかの充填領域の除去後における新画像（v2.bin)のアドレス空間である。本例では、図の右側付近に位置する１つの充填領域しかない。充填領域のサイズは、２４５，０７６バイトである。９，５８５，３２４よりも少ないアドレスは、充填による影響を受けず、図におけるアドレスは、画像における実際のアドレスに等しい。
【０１７５】
前述のように、各垂直帯は、１つの共通コード・ブロックを表し、第１部分は旧画像における領域を識別し（これは図の下位軸と接触する帯の範囲である）、第２部分は新画像における領域を識別する（これは、図における中間軸と接触する帯の範囲である）。図における帯の殆どがほぼ垂直に見えるのは、図の横目盛が９メガバイトよりも大きく、このような大きな目盛ではコード・ブロックにおける小さなずれは見難いからである。
【０１７６】
v1.binにおける２５８，８２２個のＢＬ命令は、共通コード・ブロックの中にある。これらの内、１８７，１６２個は、目標アドレスも共通コード・ブロックの中にある。一般に、正しい予測は、関連する共通コード・ブロックのずれと一致するように、目標アドレス間の間隔が旧および新画像間で異なることを意味する。先に説明したように、後処理方法論は、ＢＬ命令のような、共通コード・ブロックの中に目標アドレスを有していない命令を分析する。命令が共通コード・ブロックの中に目標アドレスを有していない場合、後処理は、既知の共通コード・ブロックの拡張、および／または新しい共通コード・ブロックの追加によって、共通コード・ブロックを改良しようとするが、これに限定されるのではない。
【０１７７】
前述のように、一実施形態によれば、後処理は次の手順を試みる。
１．modify_tryToAddArray
２．modify_tryToExtend
後処理の結果、正しい予測を有するＢＬ命令は、２４２，１９８個が数えられることになる。
【０１７８】
次に、後処理は次の手順を試みる。
１．modify_tryToExtend
２．modify_tryToAddArray
この後処理の結果、正しい予測を有するＢＬ命令は、２５７，２１７個が数えられることになる。第２手順の結果の方が、正しい予測を有する命令の数が多いので、この例では、第２手順を用いる。尚、第２手順からのカウントは、v1.binにおけるＢＬ命令の総数、即ち、２５８，８２２に非常に近いことを記しておく。また、予測が正しいＢＬ命令のカウントは、後処理の後では、１８６，０５８であったことも思い出されたい。つまり、後処理方法論の結果、デルタ・ファイルは大幅に小さくなる。後処理を行わない場合のデルタ・ファイルのサイズは、２７４，２５９バイトである。後処理を行った場合のデルタ・ファイルのサイズは、１３１，７９９バイトである。このように、この例では、後処理の結果、デルタ・ファイルは、後処理を用いないデルタ・ファイルのサイズの半分未満となる。
【０１７９】
図１５Ｂは、後処理の結果を描画する。図１５Ｂに示すように、共通コード・ブロックの数は、可変幅を有する垂直帯のように見える。例えば、１５１４、１５１６、１５１８、１５２０、１５２２、１５２４、および１５２６は、共通コード・ブロックの例である。共通コード・ブロック１５１４〜１５２６に加えて、図１５Ｂは、他の共通コード・ブロックも含む。上側のプロットは、後処理による影響を受けるバイトの密度である。ここで、この曲線は図１における対応する曲線よりも高くなる傾向があることを記しておく。これは、左側のアドレス範囲が０から約２，０００，０００までにおいて特に顕著である（アドレスは、図の下にある横軸を参照する）。この結果を理解するために、図１５Ｃを見ると、画像内に目標アドレスを有するv2.binにおけるＢＬ命令が示されている。同様のグラフをv1.binについても作ることができる。各ドットには菱形が印されて、見やすくしている。１つのドットは１つのＢＬ命令を表す。横軸上の値は、命令のアドレスであり、縦軸飢上の値は、目標アドレスである。図の左下部分に注目すると、０から２，０００，０００の範囲のアドレスを有するＢＬ命令の多数が、１，０００，０００付近に目標アドレスを有することがわかる。これは、左下におけるドット（点線で囲まれている）の横方向の集合に対応する。
【０１８０】
図１５Ｄおよび図１５Ｅは、それぞれ、図１５Ａおよび図１５Ｂの関連する領域を拡大した結果である。横軸のみを拡大している（縦軸は不変である）。図１５Ｄは、図１５Ａ上におけるズーム・イン(zoom in)であり、９００，０００から１，１００，０００までの範囲を示すために、横軸を拡大している。これは、共通コード・ブロック１５００、１５０２、および１５０４を強調する。図１５Ｅは、図１５Ｂ上におけるズーム・インであり、範囲９００，０００から１，１００，０００までの範囲を示すために横軸を拡大し、共通コード・ブロック１５１４、１５１６、１５１８、および１５２０を強調する。図１５Ｄは、後処理方法論を用いない計算についてであるが、いくつかのギャップが見える。しかしながら、図１５Ｅに示すように、後処理は、隣接する共通コード・ブロック（例えば、１５１４、１５１６、および１５２０）を拡張することにより（例えば、modify-tryToExtendを用いる）、および／または新しい共通コード・ブロック（例えば、１５１８）を導入することにより（例えば、modify-tryToAddArryを用いる）、ギャップを殆ど埋めている。
【０１８１】
以下の表は、更に詳細な情報を提示する。この表は、先に論じた試験領域における共通コード・ブロックの内数個についての後処理の効果を強調する。
【０１８２】
【表１１】
2009509272.tif 000041
【０１８３】
上の表において、各コード・ブロックは３つの数値、ａ、ｂ、およびｃによって記述されている。接頭辞「ａ」は、v1.binにおけるブロックの開始アドレスを表す。接頭辞「ｂ」は、v2.binにおけるブロックの開始アドレスを表す。接頭辞「ｃ」はブロック（v1.binおよびv2.binの双方における）の長さを表す。
【０１８４】
表の数は、最初のブロックをその終端まで延長したことを示す。何故なら、ａおよびｂ値が同一であり、ｃ値が増大しているからである。この延長は、modify_tryToExtendアルゴリズムを用いることによって遂行した。２番目のブロックは、左側および右側双方に延長し、ここでもmodify_tryToAddArrayアルゴリズムを用いた（これは、図１５Ｅの３つめの狭いブロックである）。尚、表における最後のブロックは無変化であることを記しておく。変化は、図１５Ｄおよび図１５Ｅでは明白である。図１５Ｆは、図１５Ｃの領域の拡大であり、後処理によって追加されたブロックの効果を示す。追加したブロックの中に入っているドットは、ここでは前処理されたＢＬ命令を表す。
【０１８５】
前述の前処理および／または後処理を用いたデバイスおよび／またはシステムの一例として、デルタ・ファイルを受信し用いる計算デバイスは、対応のソフトウェア・アプリケーションを記憶しておりその更新を必要とするクライアント・デバイス、例えば、セルラ電話機、移動電子デバイス、移動通信デバイス、パーソナル・ディジタル・アシスタント、およびその他のプロセッサに基づくデバイスとすることができる。この支援は、通信業者およびデバイス製造業者に効率的に電子ファイル・コンテンツおよびアプリケーションを彼らのワイヤレス・インフラストラクチャを通じて配布できるようにすることによって、ファームウェアから埋め込みアプリケーションまでの範囲に入るあらゆる移動デバイス・ソフトウェアに提供する。
【０１８６】
前述の前処理の効果が得られるシステムの別の例は、有線シリアル接続を用いてデルタ・ファイルを、ファイル差異発生部を実装したデバイスからそして更新発生部を実装したデバイスに転送するシステムを含む。これらのシステムは、通例、転送レートが遅く、転送レートが遅いために、デルタ・ファイルのサイズ縮小は、転送時間短縮を実現する１つの方法となる。
【０１８７】
前処理の使用による効果が得られるシステムの更に別の例は、無線通信を用いてデルタ・ファイルを、ファイル差異発生部を実装したデバイスから、ファイル更新発生部を実装したデバイスに転送するワイヤレス・システムを含む。ワイヤレス接続に伴う低信頼性が問題になりつつも、これらのシステムも転送レートが遅い。より小さなデルタ・ファイルをこれらのシステムにおいて用いることにより、様々な利点が得られる。例えば、ファイル・サイズが小さい程、デルタ・ファイルの転送時間は短くなる。転送時間が短い程、デバイス・ユーザの時間を節約しつつ、デルタ・ファイルに誤りが混入する機会を減らし、これによってシステムの信頼性が向上する。また、セルラ通信では、転送時間の短縮により、通例サービス料金を分単位で支払う顧客にとって、コストの節約となる。
【０１８８】
別の利点として、デルタ・ファイルが小さい程、デルタ・ファイルをクライアント・デバイスに転送するために必要な帯域幅が狭くて済む。帯域幅の縮小により、割り当てられたチャネルを通じてより多くのクライアント・デバイスに対応することが可能となる。転送時間の短縮と同様、これもワイヤレス・サービス・プロバイダにとって運営コストの削減につながる。
【０１８９】
本発明の形態は、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、プログラマブル・アレイ・ロジック（ＰＡＬ）デバイス、特に、電気的プログラム可能ロジックおよびメモリ・デバイスのようなプログラマブル・ロジック・デバイス（ＰＤＬ）、標準的なセルに基づくデバイス、ならびに特定用途集積回路（ＡＳＩＣ）を含む種々の回路のいずれにもプログラムされる機能性として実現することができる。本発明の形態を実施するための他の可能性の一部には、（電子的消去可能プログラマブル・リード・オンリ・メモリ（ＥＥＰＲＯＭ）のような）メモリを有するマイクロコントローラ、埋め込みプロセッサ、ファームウェア、ソフトウェア等が含まれる。更に、本発明の形態は、ソフトウェアに基づく回路エミュレーション、ディスクリート・ロジック（連続および組み合わせ）、カスタム・デバイス、ファジイ（ニューラル）デバイス、量子デバイス、および上述のデバイスの種類のいずれのハイブリッドを有するマイクロプロセッサにおいても具体化することができる。勿論、基盤となるデバイス技術は、種々のコンポーネントの種類、例えば、相補金属酸化物半導体（ＣＭＯＳ）のような金属酸化物半導体電界効果トランジスタ（ＭＯＳＦＥＴ）技術、エミッタ結合ロジック（ＥＣＬ）のようなバイポーラ技術、ポリマ技術（例えば、シリコン共役ポリマおよび金属共役ポリマ−金属構造）、混合アナログおよびディジタルなどにおいて提供することができる。
【０１９０】
ここに発明として記載した機能は、プログラムまたはプログラム・コード集合によって実行することができ、ソフトウェア、ファームウェア、実行可能コード、あるいは１つ以上の汎用コンピュータまたはプロセッサに基づくシステム上で走るまたはそうでなければこれらによって実行する命令を含む。コンピュータまたはその他のプロセッサに基づくシステムは、プログラム・コードを実行する１つ以上の中央演算装置、プログラムの実行中にデータおよびデータ構造を一時的に格納するＲＡＭのような揮発性メモリ、データベースおよびその他のデータ・ストアを含む、プログラムおよびデータを格納するハード・ディスク・ドライブまたは光ドライブのような不揮発性メモリ、ならびにイントラネットおよび／またはインターネットにアクセスするネットワーク・インターフェースを含むことができる。しかしながら、ここに記載した機能は、特殊目的コンピュータ、ワイヤレス・コンピュータ、状態機械、および／またはハードワイヤ型電子回路を用いても実施することができる。
【０１９１】
尚、ここに開示した種々のシステムおよび方法のコンポーネントは、コンピュータ補助設計ツールを用いて記述し、その挙動、レジスタ転送、論理コンポーネント、トランジスタ、レイアウト外形、および／またはその他の特性に関して、種々のコンピュータ読み取り可能媒体において具体化するデータおよび／または命令として表現（表す）ことができる。このような回路表現を実施することができるファイルまたはその他のオブジェクトのフォーマットは、Ｃ、Verilog、およびＨＬＤＬのような挙動言語を支援するフォーマット、ＲＴＬのようなレジスタ・レベル記述言語を支援するフォーマット、ならびにＧＤＳＩＩ、ＧＤＳＩＩＩ、ＧＤＳＩＶ、ＣＩＦ、ＭＥＢＥＳおよびその他のあらゆる適したフォーマットおよび言語のような幾何学記述言語(geometry description language)を支援するフォーマットを含むが、これらに限定されるのではない。
【０１９２】
このようなフォーマット化したデータおよび／または命令を具体化することができるコンピュータ読み取り可能媒体は、種々の形態の不揮発性記憶媒体（例えば、光学、磁気、または半導体記憶媒体）、ならびにワイヤレス、光学、または有線シグナリング媒体あるいはそのいずれの組み合わせを通じてでもこのようなフォーマット化データおよび／または命令を転送するために用いることができる搬送波を含むが、これらに限定されるのではない。搬送波によるこのようなフォーマット化データおよび／または命令の転送の例には、限定ではなく、１つ以上のデータ転送プロトコル（例えば、ＨＴＴＰ、ＦＴＰ、ＳＭＴＰ等）によるインターネットおよび／またはその他のコンピュータ・ネットワークを通じた転送（アップロード、ダウンロード、電子メール等）が含まれる。１つ以上のコンピュータ読み取り可能媒体を通じてコンピュータ・システム内部で受信する場合、前述のシステムおよび方法のこのようなデータおよび／または命令に基づく表現は、コンピュータ・システム内部にある処理実体（例えば、１つ以上のプロセッサ）によって、１つ以上のその他のコンピュータ・プログラムの実行と合わせて処理することができる。
【０１９３】
文脈上特に必要であることが明らかでない限り、明細書および特許請求の範囲を通じて、「備える」、「備えている」等の言葉は、排他的または網羅的意味ではなく、包含的意味で解釈するものとする。即ち、「含むが、限定されない」という意味である。単数または複数を用いる単語も、それぞれ、複数および単数を含むものとする。加えて、「ここでは」、「以下で」、「先に」、「以下で」という単語、および同様な意義の単語は、本願において用いられる場合、本願全体を指すのであり、本願のいずれの特定部分を指すのではないとする。「または」という単語が２つ以上の項目のリストに関して用いられている場合、その単語は、当該単語の以下の解釈全て、即ち、リストにおける項目のいずれか、リストにおける項目の全て、およびリストにおける項目のあらゆる組み合わせを包含するものとする。
【０１９４】
本発明の例示した実施例についてのこれまでの説明は、それで全てであることも、開示した正確な形態に本発明を限定することも意図していない。本発明の具体的な実施形態および例を例示の目的のためにここで記載したが、種々の等価な変更も本発明の範囲内で可能であることは、当業者は認めよう。ここに提示した本発明の教示は、他の処理システムや通信システムにも適用することができ、前述のファイル差別化システムのみに適用できるのではない。
【０１９５】
前述した種々の実施形態のエレメントおよび作用を組み合わせれば、更に別の実施形態も得ることができる。これらおよびその他の変更は、前述の詳細な説明に鑑みれば、容易に行うことができる。必要であれば、本発明の形態を変更して前述の種々の特許および出願のシステム、機能および概念を採用すれば、本発明の更に別の実施形態を得ることができる。
【０１９６】
一般に、特許請求の範囲においては、用いられる用語は、明細書に開示される具体的な実施形態および特許請求の範囲に本発明を限定するように解釈するのではなく、特許請求の範囲の下で動作してファイル差別化および更新方法を実施するあらゆる処理システムを含むように解釈するのが当然である。したがって、本発明は、本開示に限定されるのではなく、むしろ発明の範囲は特許請求の範囲によって全体的に決定されるものとする。
【０１９７】
本発明のある種の形態をある請求項の形式で提示するが、本願の発明者は、本発明の種々の形態をいかなる数の請求項形式でも想定している。例えば、本発明の一形態のみを、コンピュータ読み取り可能媒体に具体化するものとして明記するが、他の形態も同様にコンピュータ読み取り可能媒体に具体化することができる。したがって、本発明は、本願を出願した後でも、更に別の請求項を追加し、本発明の別の形態に対する、このような更に別の請求項を追求する権利を保有するものとする。
【図面の簡単な説明】
【０１９８】
【図１】図１は、一実施形態の下における、ファイル差別化および更新を示すブロック図である。
【図２】図２は、図１の実施形態の下における、デルタ・ファイルの発生のフロー図である。
【図３】図３は、実行可能ファイルの元バージョンおよび新バージョンを示すブロック図である。
【図４】図４は、図１および図２の実施形態の下において、電子ファイルの異なるバージョンを前処理するためのフロー図である。
【図５】図５は、図４の実施形態の下において、電子ファイルの異なるバージョンのコード（テキスト）セクションを前処理するためのフロー図である。
【図６】図６は、図５の実施形態の下において、電子ファイルの元のバージョンのコード（テキスト）セクションに新たな目標アドレス値を発生するためのフロー図である。
【図７】図７は、一実施形態の下における、ファイルの元バージョンおよび新バージョンのブロック図であり、電子ファイルの元バージョンのコード（テキスト）セクションに対する新たな目標アドレス値の発生を参照して記述した異なるアドレス（よび対応する標記）を示す。
【図８】図８は、図４の実施形態の下において、電子ファイルの元および新バージョンのデータ・セクションを前処理するためのフロー図である。
【図９】図９は、図８の実施形態の下において、電子ファイルの元バージョンのデータ・セクションに新データ・ポインタ値を発生するためのフロー図である。
【図１０】図１０は、一実施形態の下における、ファイルの元バージョンおよび新バージョンのブロック図であり、電子ファイルの元バージョンに新データ・ポインタ値を発生する際に用いる、異なるアドレス（および対応する標記）を示す。
【図１１】図１１は、図４の実施形態の下における、共通ファイル・ユニットのヒント融合(hint merging)のフロー図である。
【図１２】図１２は、図４の実施形態の下における、共通ファイル・ユニットのヒント融合のフロー図である。
【図１３】図１３は、一実施形態の下における、１つ以上の新コード・ブロックを発生するデータの前処理の後処理を示す。
【図１４】図１４は、一実施形態の下において、１つ以上の既に特定した共通コード・ブロックのサイズを増大させつつ、少なくとも１つの新コード・ブロックを発生するデータの前処理の後処理を示す。
【図１５Ａ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１５Ｂ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１５Ｃ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１５Ｄ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１５Ｅ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１５Ｆ】図１５Ａ〜図１５Ｆは、前述の前処理および後処理方法論の結果例を提示する図式表現を示す。
【図１】
2009509272.tif 000042
【図２】
2009509272.tif 000043
【図３】
2009509272.tif 000044
【図４】
2009509272.tif 000045
【図５】
2009509272.tif 000046
【図６】
2009509272.tif 000047
【図７】
2009509272.tif 000048
【図８】
2009509272.tif 000049
【図９】
2009509272.tif 000050
【図１０】
2009509272.tif 000051
【図１１】
2009509272.tif 000052
【図１２】
2009509272.tif 000053
【図１３】
2009509272.tif 000054
【図１４】
2009509272.tif 000055
【図１５Ａ】
2009509272.tif 000056
【図１５Ｂ】
2009509272.tif 000057
【図１５Ｃ】
2009509272.tif 000058
【図１５Ｄ】
2009509272.tif 000059
【図１５Ｅ】
2009509272.tif 000060
【図１５Ｆ】
2009509272.tif 000061
【国際調査報告】
2009509272.tif 000062
2009509272.tif 000063
2009509272.tif 000064