(57)【要約】  命令ストリームなどの入力された交錯するシーケンスは、該シーケンスに混合されたサブシーケンスの間の及び内部の相関を同時に取得及び利用するため、シーケンスを複数のマルコフチェーンにモデル化することにより圧縮される。複数のマルコフチェーンは、エントロピー符号化手段を起動するため合成されるかもしれない。
2009516474.tif 000002
【特許請求の範囲】
【請求項１】
入力された交錯したシンボルシーケンスを複数のマルコフチェーンにモデル化するステップと、
シンボルに対応する前記マルコフチェーンによるコンテクストモデルによって前記シンボルを符号化するステップと、
を有する方法。
【請求項２】
前記入力された交錯したシーケンスは、複数のサブシーケンスにより絡み合っている、請求項１記載の方法。
【請求項３】
前記モデル化するステップは、前記入力された交錯したシーケンスの各サブシーケンスの間と内部の各相関を利用して前記複数のマルコフチェーンを構成することを含む、請求項２記載の方法。
【請求項４】
前記符号化するステップは、シンボルに対応する前記マルコフチェーンによるコンテクストモデルから前記シンボルの条件付確率を推定することを含む、請求項１記載の方法。
【請求項５】
前記複数のマルコフチェーンの１つは、確率推定値に基づく各サブシーケンスの間の又は内部の各相関を提供する、請求項１記載の方法。
【請求項６】
前記入力された交錯したシーケンスは、命令ストリームである、請求項１記載の方法。
【請求項７】
入力された交錯したシンボルシーケンスを複数のマルコフチェーンにモデル化可能であって、
シンボルに対応するマルコフチェーンによるコンテクストモデルによって前記シンボルを符号化可能であるモデルを有する装置。
【請求項８】
前記入力された交錯したシーケンスは、複数のサブシーケンスにより絡み合っている、請求項７記載の装置。
【請求項９】
前記モデルは、前記入力された交錯したシーケンスの各サブシーケンスの間と内部の各相関を利用して前記複数のマルコフチェーンを構成することが可能である、請求項８記載の装置。
【請求項１０】
前記モデルは、シンボルに対応する前記マルコフチェーンによるコンテクストモデルから前記シンボルの条件付確率を推定することが可能である、請求項７記載の装置。
【請求項１１】
前記複数のマルコフチェーンの１つは、確率推定値に基づく各サブシーケンスの間の又は内部の各相関を提供する、請求項７記載の装置。
【請求項１２】
前記入力された交錯したシーケンスは、命令ストリームである、請求項７記載の装置。
【請求項１３】
関連する情報を有するマシーンアクセス可能な媒体を含む物であって、
前記情報は、アクセスされるとマシーンに、
入力された交錯したシンボルシーケンスを複数のマルコフチェーンにモデル化するステップと、
シンボルに対応する前記マルコフチェーンによるコンテクストモデルによって前記シンボルを符号化するステップと、
を実行させる物。
【請求項１４】
前記モデル化するステップは、前記入力された交錯したシーケンスの各サブシーケンスの間と内部の各相関を利用して前記複数のマルコフチェーンを構成することを含む、請求項１３記載の物。
【請求項１５】
前記符号化するステップは、シンボルに対応する前記マルコフチェーンによるコンテクストモデルから前記シンボルの条件付確率を推定することを含む、請求項１３記載の物。
【請求項１６】
前記複数のマルコフチェーンの１つは、確率推定値に基づく各サブシーケンスの間の又は内部の各相関を提供する、請求項１３記載の物。
【請求項１７】
圧縮されたシーケンスを格納可能な不揮発性メモリと、
前記不揮発性メモリに接続され、前記圧縮されたシーケンスを提供するため、入力された交錯したシンボルシーケンスを複数のマルコフチェーンにモデル化可能であって、シンボルに対応するマルコフチェーンによるコンテクストモデルによって前記シンボルを符号化可能であるモデルと、
を有するシステム。
【請求項１８】
前記モデルは、前記入力された交錯したシーケンスの各サブシーケンスの間と内部の各相関を利用して前記複数のマルコフチェーンを構成することが可能である、請求項１７記載のシステム。
【請求項１９】
前記モデルは、シンボルに対応する前記マルコフチェーンによるコンテクストモデルから前記シンボルの条件付確率を推定することが可能である、請求項１７記載のシステム。
【請求項２０】
前記複数のマルコフチェーンの１つは、確率推定値に基づく各サブシーケンスの間の又は内部の各相関を提供する、請求項１７記載のシステム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の分野］
本開示は、実行可能コードの圧縮に関し、特に実行可能コードの圧縮のため複数のマルコフチェーンに命令内（ｉｎｔｒａ−ｉｎｓｔｒｕｃｔｉｏｎ）及び命令間（ｉｎｔｅｒ−ｉｎｓｔｒｕｃｔｉｏｎ）相関をモデル化することに関する。
【０００２】
［背景］
圧縮は、データセットのサイズを他の形式によるそれと等価な表現により低減する。データ圧縮は、情報を表すのに必要とされるデータ量を低減する処理を表す。データ圧縮技術は、シンプルなファイルサイズの低減から音声及び映像符号化に至る多くのアプリケーションにおいて使用される情報格納及び送信のためのコストを減少させる。
【０００３】
通常使用される大部分の圧縮方法は、辞書ベース又は統計的なものである。統計的な方法は、エントリピー符号化とモデリング技術とを組み合わせる。典型的には、統計的方法は、実行可能コードを圧縮するのに利用される。入力シンボルのシーケンスの各入力シンボルは、入力シンボルのシーケンスより少ないビットしか有しない入力シンボルを表すコードストリームを生成するため、可変長コードにより表される。各入力シンボルは、入力シンボルのシーケンスにおけるそれの出現頻度に係る特定の確率値を有する。ビット数を減少させるため、大部分の統計的な圧縮方法は、最も少ないビット数を有するコードによって最も高い出現確率を有するシンボルを符号化する。
【０００４】
典型的には、統計的な圧縮方法は、モデルと符号化手段とを有する。モデルは、入力シンボルのシーケンスから取得される統計情報を含む。マルコフモデルなどの最もシンプルなケースでは、モデルは、入力シンボルのシーケンスにおける各自の出現頻度に基づき、入力シンボルの確率値を提供する。符号化手段は、入力シンボルのシーケンスとモデルにより提供される確率値から符号化されたコードシーケンスを生成する。
【０００５】
実行可能コードは、リニアな命令シーケンスである。所与のマシーン構成に対して、命令は特定のフォーマットを有し、一般にはオペコードと、アドレッシングモードとオペランドとの３つのフィールドを有している。実行可能コードの統計的圧縮は、実行可能コードの構造に固有の統計的依存性のため、通常のデータの統計的圧縮とは異なっている。命令内相関（ｉｎｔｒａ−ｉｎｓｔｒｕｃｔｉｏｎ  ｃｏｒｒｅｌａｔｉｏｎ）と呼ばれる命令の各フィールド間に依存性が存在する。さらに、機械語はそれのシンタックス、セマンティック及びモジュラリティにより特徴付けされているため、命令間相関（ｉｎｔｅｒ−ｉｎｓｔｒｕｃｔｉｏｎ  ｃｏｒｒｅｌａｔｉｏｎ）と呼ばれる各命令間の強力な統計的依存性が存在する。命令内及び命令間相関は、複雑に互いに絡み合っている。
【０００６】
典型的には、各命令間の統計的依存性を利用して高い圧縮レートを実現するため、実行可能プログラムのオペコードと残りとの厳密にメカニカルな分離がなされる。しかしながら、この分離方法は、一部の命令内相関の利用を禁止させるため、次善的なものである。他方、オペコードを抽出し、１つのシーケンスとして実行可能プログラムを圧縮することは、命令間相関を不明確にし、圧縮パフォーマンスを低下させる。
【０００７】
命令内及び命令間相関は共に、命令のオペコードとアドレッシングモードとを組み合わせ、それらを拡張オペコードとして扱い、その後に命令に対する拡張オペコードのシーケンスを分離及び圧縮することにより利用されるかもしれない。しかしながら、この方法は、２つのエンティティが大変弱い相関しか有していなくても、現在の命令のオペコードと前の命令のアドレッシングモードとの間の逐次的な結合を人工的に生成するため、問題になる。この結果、拡張オペコードの逐次的な圧縮は、高い圧縮レートを実現しない。
【０００８】
［詳細な説明］
以下の説明では、多数の具体的詳細が与えられる。しかしながら、本発明の実施例は、これら具体的詳細なしに実現可能である。他の例では、本説明の理解を不明りょうにしないため、周知の回路、構成及び技術は詳細には示されていない。
【０００９】
一実施例では、マルコフモデルとも呼ばれる有限コンテクストモデルは、命令内相関と命令間相関（実行可能コードに混合されている統計的な冗長性）の両方を同時に取得及び利用する。このマルコフモデリング方法は、従来のモデルより高い圧縮パフォーマンスを提供する。
【００１０】
図１は、本発明の原理による実行可能コード（実行可能コード又はファイルにおけるプログラム命令のストリーム）を圧縮するための圧縮手段１００の実施例のブロック図である。圧縮手段１００は、符号化手段１０２とモデル１０４とを有する。圧縮対象となる実行可能コードは、シンボルシーケンス１０６の形式により符号化手段１０２とモデル１０４の両方に入力される。シンボルは、異なる命令セットでは異なる意味を有する汎用的な用語である。モデルは、各シンボルの確率推定値（確率）１１０を符号化手段１０２に提供する。これにより、符号化手段１０２は、入力シンボルシーケンス１０６より短い圧縮されたコードシーケンス１０８を提供するため、最大の圧縮によりシンボルを符号化することができる。
【００１１】
圧縮手段１１０は、入力シンボルシーケンス１０６の各シンボルを一つずつ可変長出力コードに符号化することによって、データ圧縮の統計的方法を利用する。出力コードの長さは、シンボルの確率（頻度）に応じて変えられ、低い確率のシンボルは高い確率のシンボルより多数のビットで符号化される。
【００１２】
モデル１０４は、シンボルシーケンス１０６に基づき複数のマルコフチェーンを構成する。すなわち、モデル１０４は、シンボルが強く関連してるシンボルのサブシーケンスを検出し、そのサブシーケンスにおけるシンボルの確率を推定する。
【００１３】
符号化手段１０２は、シンボルサブシーケンス１０６を、モデル１０４により提供される確率に応じた単一の浮動小数（０以上１未満）と置換する算術符号化手段などのエントロピー符号化手段であってもよい。エントロピー符号化手段は、当業者に周知であり、本発明の範囲外である。
【００１４】
入力シンボルを符号化するのに使用されるビット数は、モデル１０４により与えられ理予測された確率に依存する。各シンボルが８ビットである実施例では、当該シンボルについて２８個の可能な値が存在し、各値はＰ（１／２５６）の予測確率により出現する。コードシーケンスのシンボルを符号化するのに使用されるビット数は、モデル１０４から受け取られた予測確率について−ｌｏｇ２（予測確率）を計算することにより求められる。各シンボルに等しい確率が与えられているとき、予測確率は、入力シンボルを符号化するのに８ビットコードを必要とする１／２５６となる。シンボルの１つが時間の２５％で出現する場合、当該シンボルは２ビット（−ｌｏｇ２（．２５））により表すことができ、これにより、８ビットシンボルが、それを２ビットコードにより表すことにより圧縮される。このため、モデルにより計算される予測確率は、圧縮手段１００により与えられる圧縮レートを決定する。実行可能プログラムでは、オペコードシーケンスは、マルコフ過程としてモデル化されるかもしれない。
【００１５】
図２は、命令の実施例のフォーマットを示すブロック図である。図示された実施例は、ＩＡ−３２命令セットのＩｎｔｅｌ（登録商標）Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＡ）−３２命令２００である。ＩＡ−３２  Ｉｎｔｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｓｏｆｔｗａｒｅ  Ｄｅｖｅｌｏｐｅｒのマニュアルに記載されたＩＡ−３２命令符号化は、図２に示されるフォーマットのサブセットである。各命令は、１以上のタイプのシンボルを含む。ＩＡ−３２命令セットでは、シンボルのタイプは、任意的な命令プリフィックス２０２（任意の順序による）、プライマリオペコードバイト２０４（３バイトまで）、ＭｏｄＲ／Ｍバイト２０６とときにはＳＩＢ（Ｓｃａｌｅ−Ｉｎｄｅｘ−Ｂａｓｅ）バイト２０８とを含むアドレッシング形式指定子（必要に応じて）、ディスプレースメント２１０（必要に応じて）、及び中間データフィールド２１２（必要に応じて）を含む。各シンボルの長さは、命令セットに依存する。例えば、ＩＡ−３２命令セットでは、シンボル長は８ビット（１バイト）である。他の命令セットでは、シンボル長は８ビットより長いか又は短いかもしれない。命令の上記異なるパーツへの分離のための情報は、命令セットに固有のものであり、圧縮と伸張の両方の処理に提供されるかもしれない。
【００１６】
ＩＡ−３２命令セットの実施例が説明される。しかしながら、本発明は、ＩＡ−３２命令セットに限定されるものでない。本発明は、何れかの命令セットに適用可能である。本発明はまた、命令セットに限定されず、命令内及び命令間相関を有する同様の相関を有した何れかの入力ストリームに適用可能である。
【００１７】
メモリにおいてオペランドを参照する多数の命令は、プライマリオペコードに続くアドレッシング形式指定子（ＭｏｄＲ／Ｍ）バイト２０６を有する。ＭｏｄＲ／Ｍバイトは、ｍｏｄフィールド２１４、レジスタ／オペコードフィールド２１６及びレジスタ／モード（ｒ／ｍ）フィールド２１８を含む。ｍｏｄフィールド２１４は、典型的には、レジスタ及びアドレッシングモードを指定するため、ｒ／ｍフィールド２１８と合成される。レジスタ／オペコードフィールド２１６は、レジスタナンバー又はオペコード情報を指定する。ｒ／ｍフィールド２１８は、オペランドとしてレジスタを指定するか、又はアドレッシングモードを符号化するためｍｏｄフィールド２１４と合成することが可能である。
【００１８】
ＳＩＢバイト２０８は、スケールフィールド２２０、インデックスフィールド２２２及びベースフィールド２２４を含む第２のアドレッシング形式指定子バイトである。スケールフィールド２２８は、スケール係数を指定する。インデックスフィールド２２２は、インデックスナンバーのレジスタナンバーを指定し、ベースフィールド２２４は、ベースレジスタのレジスタナンバーを指定する。このため、命令セットの命令は、構造体、すなわち、要素の集合体とみなすことができる。一実施例では、特定の命令の長さは固定され、異なる命令は異なる個数の要素を有してもよい。すなわち、命令セットの各命令の長さは可変であってもよい。他の実施例では、命令セットの各命令の長さは固定されてもよい。
【００１９】
実行可能コードにはいくつかの典型的なシーケンスが存在する。このため、実行可能コードには強い命令間相関が存在する。例えば、ＩＡ−３２による実行可能プログラムでは、ファンクションの最初の２つのアセンブリ命令は、通常は、ｅｂｐにより指定される現在のローカルスタックフレームを保存するためのｐｕｓｈ命令（ＰＵＳＨ  ｅｂｐ）と、その後の新しいスタックフレームへのポインタをｅｂｐに移動させるためのｍｏｖ命令（ＭＯＶ  ｅｂｐ，ｅｓｐ）である。ＰＵＳＨ  ｅｂｐ命令に割り当てられたベース１６（プリフィックス‘０ｘ’により示される１６進数）により表されるバイナリコードは、“０ｘ５５”であり、ＭＯＶ  ｅｂｐ，ｅｓｐ命令に割り当てられるバイナリコードは、“０ｘ８Ｂ  ０ｘＥＣ”である。このため、シンボルシーケンスは、“０ｘ５５  ０ｘ８Ｂ  ０ｘＥＣ”である。また、比較命令“ＣＭＰ＊＊＊＊”に続く命令は、通常は、ｊｕｍｐ  ｏｎ  ｅｑｕａｌｉｔｙ（ＪＥ）やｊｕｍｐ  ｏｎ  ｎｏｎ−ｅｑｕａｌｉｔｙ（ＪＮ）などの“ＪＭＰ”命令クラスのものである。
【００２０】
図３は、各セットの第１命令がオペコード０ｘ８Ｂを有するＭＯＶ命令である２つの連続する命令の３つのセットの具体例を示す。アセンブリ言語命令と各命令に対応するベース１６により表されるバイナリコードの両方が示されている。汎用的なアセンブリ言語によるｍｏｖ命令は、“ｍｏｖ  ｄｅｓｔｉｎａｔｉｏｎ，ｓｏｕｒｃｅ”の形式をとり、ソースのコピーを生成し、この値をデスティネーションに格納することによって、ソースからデスティネーションに値を移動する。ソースのコンテンツは影響を受けず、デスティネーションの前のコンテンツが上書きされる。
【００２１】
ソースは、即値、汎用レジスタ、セグメントレジスタ又はメモリ位置でありうる。デスティネーションは、汎用レジスタ、セグメントレジスタ又はメモリ位置でありうる。ソースとデスティネーションは共に、典型的には、バイト（８ビット）、ワード（１６ビット）又はダブルワード（３２ビット）など同じサイズである。すべてのｍｏｖ命令は、同一のニーモニック（ｍｏｖ）、すなわち、同様の機能を有する命令オペコードクラスについて確保されている名称を有する。図２に示される例では、異なるオペコード０ｘ８Ｂと０ｘ８９を有するニーモニック“ｍｏｖ”による２つのムーブ命令がある。オペコード０ｘ８Ｂによるｍｏｖ命令（‘１’にセットされたオペコードのビット１を有する（ただし、ビット１は転送指示を示す））はデータをメモリに移動し、オペコード０ｘ８９（‘０’にセットされたオペコードのビット１を有する）はデータをレジスタに移動する。
【００２２】
２つの連続する命令３００の第１セットでは、０ｘ８Ｂのオペコードによりｍｏｖ命令が与えられ、その後にオペコード０ｘｅ８によるコール命令が続く。２つの連続する命令の第２セット３０２と第３セット３０４では、０ｘ８Ｂのオペコードによるｍｏｖ命令が与えられ、その後にオペコード０ｘ８９による他のｍｏｖ命令が続く。
【００２３】
実行可能コード“ａｃｒｏｒｄ３２．ｅｘｅ”は、典型的には、圧縮アルゴリズムを比較するのに使用される。図４は、実行可能ファイル“ａｃｒｏｒｄ３２．ｅｘｅ”におけるオペコード０ｘ８Ｂを有する命令に直接続く命令におけるオペコードの値（０−２５５）の分布を示すヒストグラムである。ｎ次条件付エントリピーは、先行する（ｎ−１）個のオペコードを知ってオペコードを送信するための平均ビット数である。大きくバイアスされたヒストグラムは、オペコードシーケンスの低い条件付エントリピー、すなわち、オペコード０ｘ８Ｂに続くオペコードを送信するのに必要とされる平均ビット数を明確に示す。例えば、ａｃｒｏｒｄ３２．ｅｘｅの１次条件付エントロピーは、３．４９８ビットと同程度の低さである。
【００２４】
正確には、強い命令間相関に関する上記の観察のため、実行可能コードを圧縮する従来の技術は、オペコード（コマンド）を実行可能コードストリームの残りから分離し、それらを独立に圧縮する。
【００２５】
しかしながら、このアプローチは、強い命令内相関を損なわせる。メモリのオペランドを参照する多くの命令は、オペコードに続くアドレッシング形式指定子（ＭｏｄＲ／Ｍバイト）を有する。図５は、オペコード０ｘ８Ｂの後にＭｏｄＲ／Ｍバイトが続くｍｏｖ命令の具体例を示す。アセンブリ言語命令と各命令に対応するベース１６により表されるバイナリコードの両方が、示されている。
【００２６】
図５に示された例では、命令５００のＭｏｄＲ／Ｍは“０ｘＥＣ”であり、すなわち、ｍｏｄフィールド２１４は‘１１ｂ’であり、Ｒ／Ｍフィールド２１８は“０００ｂ”であり、ｒｅｇフィールド２１６は‘００１ｂ’である。命令５０２、５０４のＭｏｄＲ／Ｍは“０ｘ３５”であり、すなわち、ｍｏｄフィールド２１４は‘００ｂ’であり、Ｒ／Ｍフィールド２１８は“１１０ｂ”であり、ｒｅｇフィールド２１４は‘１０１ｂ’である。
【００２７】
図６は、実行可能ファイル（プログラム）“ａｃｒｏｒｄ３２．ｅｘｅ”におけるオペコード０ｘ８Ｂに続くＭｏｄＲ／Ｍバイトの値（０−２５５）の分布を示すヒストグラムである。ＭｏｄＲ／Ｍ値の分布は、大きく尖っていることが観察できる。これは、アドレッシングモードとオペコードとの間の強い相関を明示している。この例では、オペコード０ｘ８Ｂに続くＭｏｄＲ／Ｍの条件付エントリピーは、たったの３．９０６ビットである。従って、実行可能プログラムの残りから独立してオペコードを圧縮することは、アドレッシングモードの関連するオペコードへの依存性に隠されている統計的な冗長さを取り除くものでない。圧縮パフォーマンスにおける大きな向上は、アドレッシングモードの関連するオペコードに対するエントロピー符号化を条件付けることにより取得されるかもしれない。
【００２８】
以下の説明では、Ｘ１Ｘ２・・・ＸＮは、圧縮対象となる実行可能プログラムの命令シーケンスであり、Ｙ１Ｙ２・・・ＹＪは、命令シーケンスＸ１Ｘ２・・・ＸＮのオペコードサブシーケンスであり（ただし、Ｙｊ＝Ｘｎ，ｎ＝１＋Σ１≦ｉ＜ｊＬｉである。）、Ｌｉはｉ番目の命令の長さである。長さの単位は、ＩＡ−３２命令セットについてはバイトである。
【００２９】
図７は、実行可能プログラムにおける命令シーケンスのオペコードサブシーケンスを示す。命令シーケンスは、バイトＸ１からスタートし、第ｎ命令の最後のバイト、すなわち、バイトＸｉ｛Ｎ｝で終了する。命令シーケンスの４つの命令が示される。第１及び第２命令は、連続した命令である。第３及び第４命令は、不連続な命令であり、第３命令は命令シーケンスの第ｋ命令であり、第４命令は第ｎ命令である。オペコードサブシーケンスは、各命令からのオペコード、すなわち、Ｘ１，Ｘｉ＋１，・・・，Ｘｉ｛ｋ｝＋１，・・・，Ｘｉ｛ｎ｝＋１からのオペコードを有する。
【００３０】
当業者に知られているように、マルコフチェーンは、通常は離散的な確率過程である。確率過程は、統計的に解析可能であるが、正確には予測できないランダムな確率分布又はパターンを有する過程である。例えば、１次マルコフチェーンでは、様々な以降の状態の出現確率は、システムの現在の状態と直前の状態のみに依存し、現在の状態が実現されたパスには依存しない。実行可能コードについて、マルコフチェーンのオーダは、１より大きく、何れかのオーダのマルコフモデルが利用可能である。例えば、一実施例では、３次までのモデルが利用可能であり、すなわち、Ｘｉは、Ｘ｛ｉ−１｝，Ｘ｛ｉ−２｝，Ｘ｛ｉ−３｝に依存する。
【００３１】
本発明の実施例では、命令間相関を提供するため、１つのマルコフチェーンが利用され、命令内相関を提供するため、もう１つのマルコフチェーンが利用されるかもしれない。例えば、確率推定値Ｐ（Ｘｉ｜Ｓ（Ｘｉ−１Ｘｉ−２・・・Ｘｉ−ｔ））により導出される命令シーケンスＸｉのエントロピー符号化では、条件状態Ｓ（Ｘｉ−１Ｘｉ−２・・・Ｘｉ−ｔ）はＸｉ−１Ｘｉ−２・・・Ｘｉ−ｔの適切なサブシーケンスである。このサブシーケンスは、命令間相関のオペコードサブシーケンス又は命令内相関のオペコードサブシーケンス以外のサブシーケンスであるかもしれない。このため、条件状態は、コンテクストモデルからのＸｉのプリフィックスにおける１以上の統計的に無関係なシンボルの排除を可能にし、これにより、コンテクスト希釈が回避される。このため、確率推定値は、モデルから統計的に無関係なシンボルを排除するかもしれない。
【００３２】
図８は、統計的に無関係なシンボルを含む実行可能コード（プログラム）における命令シーケンスの一例を示す。オペコードＹｊのプリフィックスにおける無関係なシンボルは、大部分は前の命令のオペランドである。図８に示されるように、例えば、第３命令“０ｘ８９  ０ｘ４５  ０ｘ０８”におけるオペランド０ｘ０８は、最後の命令“０ｘ８５  ０ｘＣ０”におけるオペコード０ｘ８５と関係を有さない。このため、最後の命令におけるアドレスモードシンボル０ｘＣ０のコンテクストは、‘０ｘ８Ｄ  ０ｘ４Ｄ  ０ｘ５０，０ｘ８９  ０ｘ４５  ０ｘ８５’となる。シンボル“０ｘ８Ｄ  ０ｘ４Ｄ”は、命令シーケンスの第１命令からのものである。シンボル‘０ｘ８９  ０ｘ４５’は第３命令からのものであり、シンボル‘０ｘ８５’は最後の命令におけるオペコードである。第１命令からのシンボル０ｘ１０と第３命令からの０ｘ０８は、シンボル０ｘＣ０と統計的に無関係であり、確率推定値から排除される。
【００３３】
上記サブシーケンスの例は、命令間及び命令内相関の両方によるマルコフチェーンである。このため、エントロピー符号化に使用される複数のマルコフチェーンが存在するかもしれない。
【００３４】
一実施例では、入力命令ストリームにおけるシンボルの長さは１バイトであり、命令ストリームはバイト毎に符号化される。与えられたバイト（シンボル）がある命令のオペコードＹｊである場合、エントロピー符号化手段は、前の命令（すなわち、Ｙｊ−１Ｙｊ−２・・・Ｙｊ−ｔ）のオペコードのコンテクストの下での条件付確率により駆動される。このとき、当該条件付確率Ｐ（Ｙｊ｜Ｙｊ−１Ｙｊ−２・・・Ｙｊ−ｔ）は、Ｙｊの値を使用して更新される。与えられたバイトがオペコードでない場合、すなわち、Ｘｉでない場合、エントロピー符号化手段は、条件付確率Ｐ（Ｘｉ｜Ｓ（Ｘｉ−１Ｘｉ−２・・・Ｘｉ−ｔ））により駆動される。マルコフチェーン（シーケンス）Ｓ（Ｘｉ−１Ｘｉ−２・・・Ｘｉ−ｔ）は、異なる命令セットについては異なるものとすることができる。命令間相関の前の解析から、アドレッシングモードバイトが与えられると、一実施例では、マルコフチェーン（シーケンス）は、先行するオペコードＹｊ、前のアドレッシングモード
【００３５】
【数１】
2009516474.tif 000003
及び前のオペコードＹｊ−１を含むかもしれない。Ｘｉの符号化後、コンテクストモデルＰ（Ｘｉ｜Ｓ（Ｘｉ−１Ｘｉ−２・・・Ｘｉ−ｔ））はＸｉの値に基づき更新される。例えば、図８に示される命令シーケンスにおける最後の命令に対するマルコフチェーンは、前の命令（４つの命令のシーケンスにおける第３命令）の先行するオペコード０ｘ８９、前のアドレッシングモード０ｘ４５（第３命令の）及び前のオペコード０ｘ５０（第２命令の）を含むかもしれない。マルコフチェーンの一例が図８に示される。
【００３６】
図９は、本発明の原理による圧縮アルゴリズムの実施例のフロー図である。シンボルシーケンスにおけるシンボルの確率を推定する方法は、図１に示されるモデル１０４により実現可能である。モデル１０４により提供された推定確率は、シンボルシーケンスを符号化するためのエントロピー符号化手段であるかもしれない符号化手段１０２により利用可能である。
【００３７】
説明を簡単化するため、２トラックマルコフチェーンによる実施例が説明される。このマルコフチェーンは、フロー図において２つの分離したブランチにより表される。しかしながら、本発明は、２つのマルコフチェーンに限定されるものでなく、異なるマルコフチェーンに対応する各ブランチを有する２より多くのブランチが存在してもよい。
【００３８】
図９を参照するに、ブロック９００において、実行可能コードの各命令に対応するＮバイトの入力ストリームが、バイトストリームにより受信される。各バイトは、バイトストリームのシンボルに対応する。
【００３９】
ブロック９０２において、入力バイトストリームにおいて処理されるバイト数（ｉ）がインクリメントされ、最後のバイトに到達したか判断するため、バイトストリームの合計バイト数（Ｎ）と比較される。そうである場合、入力バイトストリームの処理は完了する。そうでない場合、処理はブロック９０４に続く。
【００４０】
ブロック９０４において、バイト（シンボル）が命令のオペコードである場合、処理はブロック９０６に続く。そうでない場合、処理はブロック９１０に続く。シンボルのタイプを決定するための情報が、命令セットにおいて非明示的に指定される。ＩＡ３２命令セットでは、この情報は、圧縮伸張アルゴリズムの一実施例により利用される複数の命令ルックアップマップから構成される。
【００４１】
ブロック９０６において、バイト（シンボル）は、モデルに基づく前の命令のオペコードのコンテクストの下でのモデル１０４（図１）により与えられる条件付確率を利用して、符号化手段１０２（図１）により符号化される。モデル１０４は、マルコフチェーンによりシンボルの条件付確率を計算し、この確率を符号化手段１０２にわたす。その後、符号化手段は、符号化されたストリームにおいて出力される出力ビットを生成する。上述されるように、符号化手段はエントロピー符号化手段であるかもしれない。処理はブロック９０８に続く。
【００４２】
ブロック９０８において、コンテクストモデルは、現在のオペコードを使用して更新される。符号化されたオペコードは、符号化されたストリーム９１４に配設され、入力ストリームを圧縮する処理を継続するため、処理はブロック９０２に続く。ブロック９１０において、非オペコードバイトは、モデルに基づく命令間相関のオペコードサブシーケンス以外のサブシーケンスの条件付確率を利用して符号化される。ブロック９１２において、非オペコードサブシーケンスのコンテクストモデルは、現在のバイト（シンボル）に基づき更新される。符号化されたバイトは、符号化されたストリーム９１４に配設され、入力ストリームを圧縮する処理を継続するため、処理はブロック９０２に続く。
【００４３】
図１０は、本発明の実施例により推定された確率に基づきプログラム命令ストリームを圧縮するシステム１０００のブロック図である。システム１０００は、プロセッサ（ＣＰＵ）１００２、ストレージコントローラ１００６、フラッシュメモリなどの不揮発性メモリ１００４及び揮発性メモリ１００８を有する。ストレージコントローラ１００６は、ディスクドライブであるかもしれないストレージ装置１０１０へのアクセスを制御する。メモリ１００８又はストレージ装置１０１０に格納されている実行可能コードは、図１０に関して説明された圧縮処理を利用して圧縮されるかもしれない。圧縮された実行可能コードは、不揮発性メモリ１００４又はストレージ装置１０１０に格納されてもよい。図９に関して説明された方法を利用して符号化されたストリームを復号化する復号化手段が、不揮発性メモリ１００４又はストレージ装置１０１０に格納されてもよい。
【００４４】
一実施例では、実行可能コードは、マルチトラックマルコフモデルを利用してエントロピー符号化手段を起動して、１つのコードストリームに順次符号化される。圧縮された実行可能プログラムを伸張する処理は、図９に関して説明された圧縮処理と同様の処理である。シンボルに対応するコードのみが、復号化手段に送信される。復号化手段は、命令セットの機械語のシンタックスを利用して、命令シーケンスを構文解析することによって、オペコードＹｊとオペランドＸｉを区別する。例えば、ＩＡ−３２命令セットのシンタックスは、インテルコーポレイションから入手可能なＩｎｔｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｓｏｆｔｗａｒｅ  Ｄｅｖｅｌｏｐｅｒ‘ｓ  Ｍａｎｕａｌに記載されている。ここに記載された実施例はＩＡ−３２命令セットを使用しているが、命令間相関と命令内相関の両方を結合的にモデル化する方法は、ＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）の命令セットを含む他の命令セットに適用可能である。
【００４５】
図１１は、図９に関して説明された方法を利用して符号化されたストリームを復号化するための伸張アルゴリズムの実施例のフロー図である。
【００４６】
ブロック１１００において、実行可能コードにＮ個のシンボルの命令に対応する符号化ストリーム（確率値）が受付される。処理はブロック１１０２に続く。
【００４７】
ブロック１１０２において、符号化ストリームから復号化されたシンボルの個数（ｉ）がインクリメントされ、最後のシンボルが復号化されたか判断するため、符号化されたストリームから復号化対象となる合計シンボル数と比較される。そうである場合、符号化されたストリームの処理は完了する。そうでない場合、処理はブロック１１０４に続く。
【００４８】
ブロック１１０４において、復号化対象となる次のシンボルのタイプが、前に復号化されたシンボルと命令セットに固有のルックアップ情報とに基づき決定される。処理はブロック１１０６に続く。
【００４９】
ブロック１１０６において、次のシンボルがオペコードである場合、処理はブロック１１０８に続く。そうでない場合、処理はブロック１１１２に続く。
【００５０】
ブロック１１０８において、バイト（シンボル）が、条件付確率と入力確率値とを使用して復号化手段により復号化される。処理は、ブロック１１１０に続く。
【００５１】
ブロック１１１０では、コンテクストモデルは、復号化されたオペコードを使用して更新される。復号化されたオペコードは、復号化されたバイトストリームに配設され、符号化されたストリームを伸張するための処理を継続するため、処理はブロック１１０２に続く。
【００５２】
ブロック１１１２において、復号化対象となる次のシンボルはオペコードでなく、入力確率と命令内相関のオペコードサブシーケンス以外のサブシーケンスの条件付確率とを利用して復号化される。処理はブロック１１１４に続く。
【００５３】
ブロック１１１４において、非オペコードサブシーケンスのコンテクストモデルが、復号化されたバイト（シンボル）に基づき更新される。復号化されたバイトは、復号化されたバイトストリームに配設され、符号化されたストリームを伸張するための処理を継続するため、処理はブロック１１０２に続く。
【００５４】
実行可能プログラムを圧縮する方法が、実行可能プログラムを圧縮するのに利用可能であり、これにより、それは限られたメモリ及び／又は通信帯域幅を有する装置に格納され、リアルタイムな圧縮／伸張が要求される。例えば、ＥＦＩ（Ｅｘｔｅｎｓｉｂｌｅ  Ｆｉｒｍｗａｒｅ  Ｉｎｔｅｒｆａｃｅ）ドライバは、限定的なサイズのフラッシュメモリに格納可能となるように、圧縮することができる。一実施例では、２メガバイトの実行可能プログラムが約３１６キロバイト（Ｋ）に圧縮され、これにより、この圧縮された実行可能プログラムを３２０Ｋのフラッシュメモリに格納することが可能となる。圧縮されたファイルは、ＬＺＭＡ（Ｌｅｍｐｅｌ−Ｚｉｖ−Ｍａｒｋｏｖ  ｃｈａｉｎ  Ａｌｇｏｒｉｔｈｍ）により実現される３６６Ｋより小さなものとなる。
【００５５】
この圧縮方法は、ａｃｒｏａｄ３２．ｅｘｅのファイルを圧縮するとき、６９．５３％の圧縮レートをもたらす。この圧縮レートは、同じファイルを圧縮するためＷｉｎＺｉｐにより実現される５５．０７％の圧縮レートより良好なものとなる。ＷｉｎＺｉｐは、ＷｉｎＺｉｐ  Ｃｏｍｐｕｔｉｎｇにより開発された市販のファイルアーカイバである。
【００５６】
また、実行可能プログラムの圧縮は、ネットワークトラフィックと伝送コストを低減するため、無線環境において利用可能であり、ネットワークサービスプロバイダによるより多くのエンドユーザのサポートを可能にする。
【００５７】
他の実施例では、実行可能プログラムを圧縮する方法が、実行前にリアルタイムに伸張されるインターネットを介したダウンロードのためのＭｉｃｒｏｓｏｆｔのＡｃｔｉｖｅＸなどのウェブアプリケーションを圧縮するのに利用可能である。他の実施例では、この圧縮方法は、例えば、圧縮ファイルにおけるウイルスのリアルタイムなスキャニングなどのリアルタイムなスキャニングに利用可能である。
【００５８】
本発明の実施例はまた、命令内及び命令間相関と同様の相関を有する何れかの入力ストリームを圧縮するのに適用可能である。入力命令ストリームは、オペコードサブシーケンス、命令サブシーケンス、アドレッシングモードサブシーケンスなどの各種サブシーケンスを含む交錯したシーケンスである。命令内及び命令間相関はまた、これらのサブシーケンスの間の又は内部の相関である。交錯したシーケンスに相関が混じり合う命令シーケンスに類似した他のシーケンスが存在する。本発明は、交錯したシーケンスをこれらの相関による複数のマルコフチェーンにモデル化することによって、これら交錯したシーケンスに適用可能である。入力された交錯したシーケンスにおける各シンボルの確率は、シンボルが属するマルコフチェーンのコンテクストに従って推定される。シンボルに対応するマルコフチェーンの決定は、アプリケーションに固有のものである。命令ストリームの圧縮の実施例では、この決定は命令内のシンボルのタイプに基づく。
【００５９】
明細書における“一実施例”又は“実施例”という表現は、当該実施例に関して説明された特定の機能、構成又は特徴が本発明の少なくとも１つの実施例に含まれることを意味する。明細書の各箇所における“一実施例では”というフレーズの出現は、必ずしも同一の実施例を参照するとは限らない。
【００６０】
本発明の各実施例に関する方法は、コンピュータにより使用可能な媒体を含むコンピュータプログラムプロダクトにより実現可能であるということは、当業者に明らかであろう。例えば、このようなコンピュータ利用可能媒体は、ＣＤ  ＲＯＭディスクや従来のＲＯＭ装置などの読み出し専用記憶装置、又はコンピュータ可読プログラムを格納したコンピュータディスケットから構成されるかもしれない。
【００６１】
本発明が複数の実施例に関して説明されたが、本発明が記載された実施例に限定されるものでなく、添付した請求項の趣旨及び範囲内の変更及び改良により実現可能であることは、当業者に認識されるであろう。このため、本記載は限定するものでなく例示的なものとみなされるべきである。
【図面の簡単な説明】
【００６２】
【図１】図１は、本発明の原理による実行可能コード（実行可能プログラム又はファイルにおけるプログラム命令ストリーム）を圧縮するための圧縮手段の実施例のブロック図である。
【図２】図２は、命令の実施例のフォーマットを示すブロック図である。
【図３】図３は、各セットの第１命令がオペコード０ｘ８Ｂを有するｍｏｖ命令である２つの連続する命令の３つのセットの例を示す。
【図４】図４は、実行可能ファイル“ａｃｒｏｒｄ３２．ｅｘｅ”においてオペコード０ｘ８Ｂに直接続く各命令のオペコードの分布を示すヒストグラムである。
【図５】図５は、オペコード０ｘ８Ｂの後にＭｏｄＲ／Ｍバイトが続くｍｏｖ命令の例を示す。
【図６】図６は、実行可能ファイル“ａｃｒｏｒｄ３２．ｅｘｅ”におけるＭｏｄＲ／Ｍバイトの後に続くオペコード０ｘ８Ｂの分布を示すヒストグラムである。
【図７】図７は、実行可能プログラムにおける命令シーケンスのオペコードサブシーケンスを示す。
【図８】図８は、統計的に無関係なシンボルを含む実行可能コード（プログラム）における命令シーケンスの例を示す。
【図９】図９は、本発明の原理による実行可能コードを圧縮する方法の実施例のフロー図である。
【図１０】図１０は、本発明の原理による実行可能コードを圧縮するシステムの実施例である。
【図１１】図１１は、図９に関して説明された方法を利用して符号化されたストリームを復号化する伸張アルゴリズムの実施例のフロー図である。
【図１】
2009516474.tif 000004
【図２】
2009516474.tif 000005
【図３】
2009516474.tif 000006
【図４】
2009516474.tif 000007
【図５】
2009516474.tif 000008
【図６】
2009516474.tif 000009
【図７】
2009516474.tif 000010
【図８】
2009516474.tif 000011
【図９】
2009516474.tif 000012
【図１０】
2009516474.tif 000013
【図１１】
2009516474.tif 000014
【国際調査報告】
2009516474.tif 000015
2009516474.tif 000016
2009516474.tif 000017