(57)【特許請求の範囲】
【請求項１】
データ処理システムにおいて、可変長符号化データ・ストリームを復号するための方法であって、
前記データ処理システムの復号器により、前記可変長符号化データ・ストリームの一部である入力ライン・データを受け取るステップと、
前記復号器により、次の入力ライン・データへの前記入力ライン・データのビット・スピル・オーバの量を決定するステップと、
前記復号器により、前記決定されたビット・スピル・オーバの量に基づき、符号化されたシンボル境界で開始するように前記次の入力ライン・データを整列し、整列された次の入力ライン・データを生成するステップと、
前記復号器により、前記整列された次の入力ライン・データをトークン化し、それぞれのトークンが前記整列された次の入力ライン・データにおけるシンボルに対応する１組のトークンを生成するステップと、
前記復号器により、前記１組のトークンに基づき、オリジナルの１組のデータにおける１ワードのデータに対応する出力ワード・データを生成するステップとを含み、
前記入力ライン・データのビット・スピル・オーバの量を決定するステップは、
前記入力ライン・データの複数の推論的復号動作を実行するステップであって、それぞれの推論的復号動作が複数の異なる可能なビット・スピル・オーバの量のうちの１つに対応する、前記実行するステップと、
複数の可能なビット・スピル・オーバの量のそれぞれに対する前記入力ライン・データに関する前記複数の推論的復号動作の結果に基づき、前記入力ライン・データのビット・スピル・オーバの量を決定するステップと、を含む方法。
【請求項２】
ビット・スピル・オーバの量が、Ｈｍａｘを前記入力ライン・データにおける可変長シンボルの最大の長さとして、０ビットからＨｍａｘ−１ビットまでの範囲にあり、推論的復号動作が、０からＨｍａｘ−１までの範囲におけるスピル・オーバのビットのそれぞれの可能な数に対して実行される、請求項１に記載の方法。
【請求項３】
前記複数の推論的復号動作が並列で実行され、前記入力ライン・データのビット・スピル・オーバの量を決定するステップが、前記可変長符号化データ・ストリームにおける直前のライン・データに対して決定されたビット・スピル・オーバの量に基づいて、前記複数の推論的復号動作のうちの１つの結果を選択するステップを含む、請求項１に記載の方法。
【請求項４】
ビット・スピル・オーバの量を決定するステップが、前記複数の推論的復号動作の前記結果と直前のライン・データの復号結果とに基づいてビット・スピル・オーバの前記量を決定するステップを含む、請求項１に記載の方法。
【請求項５】
前記復号器により前記整列された次の入力ライン・データをトークン化し１組のトークンを生成するステップが、複数の段を有するトークナイザ・パイプラインを経由して前記整列された次の入力ラインを処理するステップを含んでおり、それぞれの段が計算ロジックを含み、前記計算ロジックは、前記整列された次の入力ラインにおける次の符号化されたシンボルのためにシンボル・データを抽出し、前記抽出されたシンボル・データと関連するインフレート・バイトの数を決定して、前記整列された次の入力ラインに対するインフレート・バイトの直前の合計と前記抽出されたシンボル・データのサイズとに基づき、前記整列された次の入力ラインに対するインフレート・バイトの総数を蓄積する、請求項１に記載の方法。
【請求項６】
前記トークナイザ・パイプラインの最終段が、前記整列された次の入力ラインから抽出されたシンボル・データに対するエントリを用いて、トークン・テーブルのデータ構造を更新する、請求項５に記載の方法。
【請求項７】
前記１組のトークンに基づき出力ワード・データを生成するステップが、少なくとも２つの入力ラインからのトークンを実質的に同時に処理するステップを含む、請求項６に記載の方法。
【請求項８】
次の符号化されたシンボルに対するシンボル・データを抽出するステップが、対応する抽出されたシンボルのタイプをリテラル・シンボル・タイプまたはリテラル・シンボル・タイプへの参照のどちらか一方であるとして示すデータと、前記タイプがリテラル・シンボル・タイプを示すことに応答してリテラル値を示すデータと、前記タイプが参照タイプを示すことに応答して逆距離ポインタを示すデータと、を抽出するステップを含み、エントリを用いてトークン・テーブルのデータ構造を更新するステップが、前記トークン・テーブル・エントリと関連する抽出されたシンボルに対応する抽出されたシンボル・データを用いて前記エントリをポピュレートするステップを含む、請求項６記載の方法。
【請求項９】
前記可変長符号化データ・ストリームが、ハフマン符号化アルゴリズムを用いて符号化されたオリジナルのデータを含む、請求項１に記載の方法。
【請求項１０】
前記可変長符号化データ・ストリームからの入力ライン・データをクロック・サイクルごとに処理するようにパイプライン化して実行される、請求項１に記載の方法。
【請求項１１】
前記１組のトークンに基づいて出力ワード・データを生成するステップが、
Ｎを、それぞれのプロセッサ・サイクルごとに前記出力ワードに出力される復号されたデータのバイト数であるとして、前記可変長符号化データ・ストリームからの復号されたデータの同じ部分を、出力生成器ロジックの複数であるＮ個のメモリのそれぞれに格納し、かつ
前記出力ワード・データにおけるＮバイトのそれぞれに対し、前記複数であるＮ個のメモリにおける対応するメモリから読み出された１バイトのデータ、または、前記シンボル・タイプに応じてトークン・テーブル・エントリからのリテラル値のいずれか一方を出力するステップと、あるいは、
前記出力生成器ロジックの、プロセッサ・サイクルごとに前記出力ワード・データに出力される復号されたデータのそれぞれのバイトに対して１つであるＮ個の読み出しポートを有する単一の共有メモリに、復号されたデータの一部を格納し、かつ、
前記出力ワード・データにおけるＮバイトのそれぞれに対し、前記複数であるＮ個の読み出しポートおける対応する読み出しポートから読み出された１バイトのデータ、または、前記シンボル・タイプに応じてトークン・テーブル・エントリからのリテラル値のいずれか一方を出力するステップと、
の少なくとも一方を含む、請求項１に記載の方法。
【請求項１２】
データ処理システムにおいて、可変長符号化データ・ストリームを復号するためのコンピュータ・プログラムであって、
可変長符号化データ・ストリームの一部である入力ライン・データを受け取るステップと、
次の入力ライン・データへの前記入力ライン・データのビット・スピル・オーバの量を決定するステップと、
前記決定されたビット・スピル・オーバの量に基づき、符号化されたシンボル境界で開始するように前記次の入力ライン・データを整列するステップと、
前記整列された次の入力ライン・データをトークン化し、それぞれのトークンが前記整列された次の入力ライン・データにおけるシンボルに対応する１組のトークンを生成するステップと、
前記１組のトークンに基づき、オリジナルの１組のデータにおける１ワードのデータに対応する出力ワード・データを生成するステップと、
前記入力ライン・データの複数の推論的復号動作を実行するステップであって、それぞれの推論的復号動作が複数の異なる可能なビット・スピル・オーバの量のうちの１つに対応する、前記実行するステップと、
複数の可能なビット・スピル・オーバの量のそれぞれに対する前記入力ライン・データに関する前記複数の推論的復号動作の結果に基づき、前記入力ライン・データのビット・スピル・オーバの量を決定するステップと、
により、前記データ処理システムに、次の入力ライン・データへの前記入力ライン・データのビット・スピル・オーバの量を決定させるステップと、
をデータ処理システムに実行させる、コンピュータ・プログラム。
【請求項１３】
データ処理システムに実行させるステップは更に、複数の段を有するトークナイザ・パイプラインを経由して前記整列された次の入力ラインを処理することにより、前記データ処理システムに前記整列された次の入力ライン・データをトークン化させて１組のトークンを生成させ、それぞれの段が計算ロジックを含み、前記計算ロジックは、前記整列された次の入力ラインにおける次の符号化されたシンボルのためにシンボル・データを抽出し、前記抽出されたシンボル・データと関連するインフレート・バイトの数を決定して、前記整列された次の入力ラインに対するインフレート・バイトの直前の合計と前記抽出されたシンボル・データのサイズとに基づき、前記整列された次の入力ラインに対するインフレート・バイトの総数を蓄積するステップを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
前記可変長符号化データ・ストリームが、ハフマン符号化アルゴリズムを用いて符号化されたオリジナルのデータを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１５】
前記データ処理システムにパイプライン化して前記可変長符号化データ・ストリームからのライン・データに対して作用させ、前記可変長符号化データ・ストリームからの入力ライン・データをクロック・サイクルごとに処理する、請求項１２に記載のコンピュータ・プログラム。
【請求項１６】
更に、
Ｎを、それぞれのプロセッサ・サイクルごとに前記出力ワードに出力される復号されたデータのバイト数であるとして、前記可変長符号化データ・ストリームからの復号されたデータの同じ部分を、出力生成器ロジックの複数であるＮ個のメモリのそれぞれに格納し、かつ
前記出力ワード・データにおけるＮバイトのそれぞれに対し、前記複数であるＮ個のメモリにおける対応するメモリから読み出された１バイトのデータ、または、前記シンボル・タイプに応じてトークン・テーブル・エントリからのリテラル値のいずれか一方を出力するステップと、あるいは、
前記出力生成器ロジックの、プロセッサ・サイクルごとに前記出力ワード・データに出力される復号されたデータのそれぞれのバイトに対して１つであるＮ個の読み出しポートを有する単一の共有メモリに、復号されたデータの一部を格納し、かつ、
前記出力ワード・データにおけるＮバイトのそれぞれに対し、前記複数であるＮ個の読み出しポートおける対応する読み出しポートから読み出された１バイトのデータ、または、前記シンボル・タイプに応じてトークン・テーブル・エントリからのリテラル値のいずれか一方を出力するステップと、
の少なくとも一方により、前記データ処理システムに前記１組のトークンに基づいて出力ワード・データを生成させる、請求項１２に記載のコンピュータ・プログラム。
【請求項１７】
プロセッサと、
前記プロセッサに結合されたインターフェースと、を備えており、
前記インターフェースを経由して可変長符号化データ・ストリームが受け取られ、前記プロセッサは、
前記可変長符号化データ・ストリームの一部である入力ライン・データを受け取り、
次の入力ライン・データへの前記入力ライン・データのビット・スピル・オーバの量を決定し、
前記決定されたビット・スピル・オーバの量に基づき、符号化されたシンボル境界で開始するように前記次の入力ライン・データを整列し、
前記整列された次の入力ライン・データをトークン化し、それぞれのトークンが前記整列された次の入力ライン・データにおけるシンボルに対応する１組のトークンを生成し、
前記１組のトークンに基づき、オリジナルの１組のデータにおける１ワードのデータに対応する出力ワード・データを生成すし、
前記入力ライン・データの複数の推論的復号動作を実行するステップであって、それぞれの推論的復号動作が複数の異なる可能なビット・スピル・オーバの量のうちの１つに対応する、前記実行し、
複数の可能なビット・スピル・オーバの量のそれぞれに対する前記入力ライン・データに関する前記複数の推論的復号動作の結果に基づき、前記入力ライン・データのビット・スピル・オーバの量を決定し、
により、前記データ処理システムに、次の入力ライン・データへの前記入力ライン・データのビット・スピル・オーバの量を決定する、ロジックを備えている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、改善されたデータ処理装置および方法に関し、より詳細には、可変長符号化データ・ストリームの高帯域幅圧縮解除（high bandwidth decompression）を提供するメカニズムに関する。
【背景技術】
【０００２】
可逆データ圧縮（lossless data compression）とは、圧縮されたデータから厳密にオリジナルのデータを再構築することを可能にするデータ圧縮アルゴリズムのクラスである。「可逆（lossless）」という用語は、より良好な圧縮率と引き替えにしてオリジナルのデータの近似だけの再構築が可能である非可逆データ圧縮技術と、対照的である。可逆データ圧縮は、ＺＩＰ圧縮フォーマットや、Ｕｎｉｘオペレーティング・システムに基づくコンピューティング・システムにおけるＧＺＩＰ圧縮などを含む多くの異なるタイプのアプリケーションにおいて用いられる。
【０００３】
可逆データ圧縮の１つのタイプとして、米国特許第５，０５１，７４５号に記載されているＤＥＦＬＡＴＥデータ圧縮アルゴリズムがある。ＤＥＦＬＡＴＥデータ圧縮アルゴリズムは、Ｌｅｍｐｅｌ−Ｚｉｖ  ＬＺ７７圧縮アルゴリズムとハフマン符号化との組み合わせを利用している。ＬＺ７７圧縮は、スライディング・ウィンドウ圧縮技術であり、この技術では、ある範囲（すなわち、ウィンドウ）のデータに対して、複製されたことがまだ検出されていないストリングのリテラル・バイトが格納され、その範囲（すなわち、ウィンドウ）の中で複製ストリングが検出されると、以前に格納されたリテラル・バイトへのポインタが、代わりに格納される。このポインタは、その範囲（すなわち、ウィンドウ）の中に、長さと逆距離（backward distance）とを含む。次に、ＬＺ７７アルゴリズムでは、ハフマン符号化が、リテラル・バイトとポインタとに適用される。ハフマン符号化は、可変長符号化を用いてリテラル・バイトとポインタとを符号化する能力を提供する。ＤＥＦＬＡＴＥデータ圧縮アルゴリズムに関する更なる情報は、Deutsch, "DEFLATE Compressed Data Format Specification,"version 1.3, Network Working Group RFC 1951, May 1996において見いだすことができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第５，０５１，７４５号
【非特許文献】
【０００５】
【非特許文献１】Deutsch, "DEFLATE CompressedData Format Specification," version 1.3, Network Working Group RFC 1951,May 1996
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、データ処理システムにおいて可変長符号化データ・ストリームの高帯域幅圧縮解除により復号する方法およびプログラムを提供する。
【課題を解決するための手段】
【０００７】
ある例示的な実施形態では、データ処理システムにおいて、可変長符号化データ・ストリームを復号するための方法が提供される。この方法は、データ処理システムの復号器により、可変長符号化データ・ストリームの一部である入力ライン・データを受け取るステップを含む。この方法は、更に、復号器により、シンボル整列のために次の入力ライン・データへの入力ライン・データのビット・スピル・オーバの量を決定するステップを含む。更に、この方法は、復号器により、直前の入力ライン・データからのビット・スピル・オーバの決定された量に基づき、シンボル境界で開始するように入力ライン・データを整列するステップを含む。更に、この方法は、復号器により、整列された入力ライン・データをトークン化して、それぞれのトークンが整列された次の入力ラインにおける可変長符号化シンボルに対応する１組のトークンを生成するステップを含む。加えて、この方法は、復号器により、１組のトークンに基づき、オリジナルの１組のデータにおける１ワードのデータに対応する出力ワード・データを生成するステップを含む。
【０００８】
他の例示的な実施形態では、コンピュータ可読プログラムを有するコンピュータ使用可能または可読媒体を備えたコンピュータ・プログラム製品が提供される。このコンピュータ可読プログラムは、コンピューティング・デバイス上で実行されたとき、コンピューティング・デバイスに、方法の例示的実施形態との関係において上で概略を述べた動作のうちの様々なものとそれらの組み合わせとを、実行させる。
【０００９】
更に別の例示的な実施形態では、システム／装置が提供される。このシステム／装置は、１つまたは複数のプロセッサと、その１つまたは複数のプロセッサに結合されたメモリとを含みうる。このメモリは命令を含んでおり、この命令は、１つまたは複数のプロセッサによって実行されたとき、１つまたは複数のプロセッサに、方法の例示的実施形態との関係において上で概略を述べた動作のうちの様々なものとそれらの組み合わせとを、実行させる。
【００１０】
本発明のこれらのおよびそれ以外の特徴および効果は、本発明の実施形態の例に関する以下の詳細な説明において説明され、または、本発明の実施形態の例に関する以下の詳細な説明により当業者に明らかになるはずである。
【図面の簡単な説明】
【００１１】
本発明は、その使用の好適な態様ならびに更なる目的および効果と共に、添付の図面と共に読まれる例示的な実施形態に関する以下の詳細な説明を参照することにより、最もよく理解されるであろう。添付の図面は、次の通りである。
【図１】例示的な実施形態の態様が実装されうる分散型データ処理システムの一例の図解的な表現である。
【図２】例示的な実施形態の態様が実装されうるデータ処理システムの一例のブロック図である。
【図３】ある例示的な実施形態による復号器／圧縮解除器のアーキテクチャのブロック図の例である。
【図４】ある入力ラインから別の入力ラインへのデータの一部のビットのスピル・オーバを図解する複数の入力ラインを図解する図の一例である。
【図５】ある例示的な実施形態により入力ラインの整列を決定するときの復号器／圧縮解除器の整列ロジックの動作を図解しているブロック図の一例である。
【図６】ある例示的な実施形態によるトークナイザ・ロジック・パイプラインのブロック図の一例である。
【図７】ある例示的な実施形態による出力生成器ロジックのブロック図の一例である。
【図８】ある例示的な実施形態により可変長符号化データ・ストリームを処理するための動作の一例の概略を述べる流れ図である。
【発明を実施するための形態】
【００１２】
例示的な実施形態は、可変長符号化データ・ストリームの高帯域幅圧縮解除を提供するメカニズムを提供する。例示的実施形態のメカニズムは、用いられた圧縮技術によって導入された圧縮されたデータ・ストリームにおける可変長の符号化されたシンボルを補償する。ここで、用いられた圧縮技術とは、例えば、可変長ハフマン符号化またはそれ以外の可変長符号化技術である。符号化されたデータ・ストリームにおけるこの可変長の符号化されたシンボルを補償する例示的実施形態のメカニズムを用いると、データ・ストリームにおけるデータのブロックに対する並列的な圧縮解除を実行することができ、これは、圧縮解除動作のスループットと速度とを向上させる。結果的に、可変長符号化データ・ストリームに対して作用することのできる高帯域幅の高速圧縮解除メカニズムが、提供される。
【００１３】
当業者であれば理解するように、本発明の態様は、システム、方法、またはコンピュータ・プログラム製品として具体化することができる。したがって、本発明の態様は、すべてがハードウェアである実施形態、すべてがソフトウェアである実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、または、ソフトウェアおよびハードウェアの態様を組み合わせた実施形態という形式を取ることができ、本明細書では、これらすべてを、一般的に、「回路」、「モジュール」、または「システム」と呼ぶことがある。更に、本発明の態様は、コンピュータ使用可能なプログラム・コードが組み込まれた１つまたは複数のコンピュータ可読媒体として具体化されるコンピュータ・プログラム製品という形式を取ることがある。
【００１４】
１つまたは複数のコンピュータ可読媒体の任意の組み合わせを、用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体でありうる。コンピュータ可読記憶媒体は、例えば、これらには限定されないが、電子、磁気、光、電磁気、赤外線、もしくは半導体のシステム、装置、デバイス、または上記のいずれかの適切な組み合わせとすることができる。コンピュータ可読記憶媒体のより具体的な例（網羅的ではないリスト）として、１つまたは複数の導線を有する電気接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリ・メモリ（ＲＯＭ）、消去可能プログラム可能なリード・オンリ・メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク・リード・オンリ・メモリ（ＣＤＲＯＭ）、光ストレージ・デバイス、磁気ストレージ・デバイス、または上記の任意の適切な組み合わせが含まれうる。本明細書のコンテキストでは、コンピュータ可読記憶媒体は、命令実行システム、装置、もしくはデバイスによって、またはこれらと共に、用いられるプログラムを含むかまたは格納することができる任意の有形の媒体でありうる。
【００１５】
コンピュータ可読信号媒体は、例えば、ベースバンドにおいてまたは搬送波の一部として、コンピュータ可読なプログラム・コードがその中で具体化されている伝播されるデータ信号を含みうる。そのような伝播される信号は、これらに限定されることはないが、電磁気、光、またはそれらの任意の適切な組み合わせを含む様々な形式のうちの任意のものをとりうる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、装置、もしくはデバイスによって用いられるために、またはそれらと共に用いるために、プログラムを通信、伝播、または運ぶことができる任意のコンピュータ可読媒体でありうる。
【００１６】
コンピュータ可読媒体上に具体化されたコンピュータ・コードは、無線、有線、光ファイバ・ケーブル、無線周波数（ＲＦ）など、または上記の任意の好適な組み合わせを含むが、これらに限定されない任意の適切な媒体を用いて、伝送することができる。
【００１７】
本発明の態様の動作を実行するためのコンピュータ・プログラム・コードは、１つまたは複数のプログラミング言語の任意の組み合わせで書くことができる。ここで、プログラミング言語には、Ｊａｖａ（ＴＭ）、ＳｍａｌｌＴａｌｋ（ＴＭ）、Ｃ＋＋などのようなオブジェクト指向プログラミング言語と、「Ｃ」プログラミング言語または同様のプログラミング言語など従来の手続型プログラミング言語とが含まれる。プログラム・コードは、完全にユーザのコンピュータ上で実行するか、スタンドアロンのソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行するか、部分的にユーザのコンピュータ上で実行し、部分的にリモート・コンピュータ上で実行するか、または、完全にリモート・コンピュータもしくはサーバ上で実行することができる。最後の場合には、リモート・コンピュータを、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通じてユーザのコンピュータに接続することができ、または、（例えば、インターネット・サービス・プロバイダを用いてインターネットを経由することにより）外部コンピュータに接続することもできる。
【００１８】
本発明の態様は、本発明の例示的な実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の流れ図による図解もしくはブロック図またはその両方を参照して、以下で説明される。流れ図による図解もしくはブロック図またはその両方のそれぞれのブロックと、流れ図による図解もしくはブロック図またはその両方における複数のブロックの組み合わせをコンピュータ・プログラム命令によって実装できることが、理解されるであろう。これらのコンピュータ・プログラム命令を、汎用コンピュータ、専用コンピュータ、または他のプログラム可能なデータ処理装置のプロセッサに提供してマシンを生成することにより、コンピュータまたは他のプログラム可能データ処理装置のプロセッサによって実行される命令が、流れ図もしくはブロック図またはその両方の１つまたは複数のブロックに指定されている機能／作用を実装するための手段を、生成するようにできる。
【００１９】
また、このコンピュータ・プログラム命令は、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスに、特定の形で機能するように命じることができるコンピュータ可読媒体に格納することができる。それにより、コンピュータ可読媒体に格納された命令は、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックに指定されている機能／作用を実装する命令を含む製品を製造する。
【００２０】
また、コンピュータ・プログラム命令は、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードすることで、そのコンピュータ、他のプログラム可能装置、または他のデバイス上で、一連の動作ステップを実行させ、コンピュータ実装プロセスを生じさせることができる。それにより、コンピュータや他のプログラム可能装置上で実行される命令は、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックに特定されている機能／作用を実装するためのプロセスを提供することができる。
【００２１】
図における流れ図およびブロック図は、本発明の様々な実施形態に従ったシステム、方法、およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能、および動作を図解している。この点で、流れ図またはブロック図におけるそれぞれのブロックは、特定された論理的機能を実装するための１つまたは複数の実行可能な命令を含む、モジュール、セグメント、またはコードの一部を表すことができる。また、いくつかの代替的な実装では、ブロック内に示された機能が図面に示されている順序とは異なる順序で生じる場合もあることに留意されたい。例えば、連続して示されている２つのブロックは、実際には、実質的に同時に実行されることがあり、または、これらのブロックが、関連する機能に応じて、時には逆の順序で実行されることもある。ブロック図もしくは流れ図の図解またはその両方のそれぞれのブロックと、ブロック図もしくは流れ図の図解またはその両方における複数のブロックの組み合わせとは、指定された機能もしくは作用を実行する特定用途向けハードウェアに基づくシステム、または、特定用途向けハードウェアとコンピュータ命令との組み合わせによって実装可能であることにも注意すべきである。
【００２２】
このように、例示的な実施形態は、多くの異なるタイプのデータ処理環境において、用いることができる。例示的実施形態の特定の要素と機能とに関する説明のためのコンテキストを提供するために、以下では、図１および図２を、例示的実施形態の諸態様が実装されうる例示的な環境として、提供される。図１および図２は、単なる例に過ぎないのであって、本発明の実施形態の諸態様または実施形態が実装されうる環境に関していかなる限定を主張または含意することも意図されていないことを理解すべきである。示されている環境に対する多くの変更を、本発明の精神および範囲から逸脱することなく、行うことが可能である。
【００２３】
図１は、例示的実施形態の態様が実装されうる例示的な分散データ処理システムの絵画的な表現を示している。分散データ処理システム１００は、例示的実施形態の態様が実装されうるコンピュータのネットワークを含むことがある。分散データ処理システム１００は、少なくとも１つのネットワーク１０２を含むが、このネットワーク１０２は、分散データ処理システム１００の内部で相互に接続された様々なデバイスおよびコンピュータの間に通信リンクを提供するのに用いられる媒体である。ネットワーク１０２は、有線、無線通信リンク、または光ファイバ・ケーブルなどの接続を含みうる。
【００２４】
示されている例では、サーバ１０４およびサーバ１０６が、ストレージ・ユニット１０８と共に、ネットワーク１０２に接続されている。更に、クライアント１１０、１１２、および１１４もまた、ネットワーク１０２に接続されている。これらのクライアント１１０、１１２、および１１４は、例えば、パーソナル・コンピュータ、ネットワーク・コンピュータ、または同様のものでありうる。示されている例では、サーバ１０４は、クライアント１１０、１１２、および１１４に、起動ファイル、オペレーティング・システム・イメージ、およびアプリケーションなどのデータを提供する。示されている例では、クライアント１１０、１１２、および１１４は、サーバ１０４に対するクライアントである。分散データ処理システム１００には、図示されていない追加的なサーバ、クライアント、および他のデバイスが含まれることがありうる。
【００２５】
示されている例では、分散データ処理システム１００はインターネットである。この場合、ネットワーク１０２は、相互に通信を行うために、伝送制御プロトコル／インターネット・プロトコル（ＴＣＰ／ＩＰ）と称される一連のプロトコルを用いる、ネットワークおよびゲートウェイの世界規模の集合体を表している。インターネットの核心には、データおよびメッセージのルーティングを行う、数千の商業的、政府による、教育用の、およびその他のコンピュータ・システムから構成される主要なノードまたはホスト・コンピュータの間の高速データ通信回線のバックボーンが存在する。当然ながら、分散データ処理システム１００は、例えば、イントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）など、多数の異なったタイプのネットワークを含むように、実装することも可能である。上述したように、図１は、例として意図されており、本発明の異なる複数の実施形態に対するアーキテクチャに関する限定を意図したものではない。したがって、図１に示されている特定の要素は、本発明の例示的実施形態を実装することが可能な環境に関し、限定的であると考えるべきではない。
【００２６】
図２は、例示的な実施形態の態様を実装することができる例示的なデータ処理システムのブロック図である。データ処理システム２００は、図１におけるクライアント１１０などのコンピュータの例であり、本発明の例示的な実施形態のためのプロセスを実装するコンピュータ使用可能なコードまたは命令を置くことができる。
【００２７】
示されている例において、データ処理システム２００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２とサウス・ブリッジおよび入力／出力（Ｉ／Ｏ）コントローラ・ハブ（ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを用いている。処理ユニット２０６と、メイン・メモリ２０８と、グラフィクス・プロセッサ２１０とは、ＮＢ／ＭＣＨ２０２に接続されている。グラフィクス・プロセッサ２１０は、アクセラレイティド・グラフィクス・ポート（ＡＧＰ）を経由して、ＮＢ／ＭＣＨ２０２に接続されうる。
【００２８】
示されている例において、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２は、ＳＢ／ＩＣＨ２０４に接続している。オーディオ・アダプタ２１６、キーボードおよびマウス・アダプタ２２０、モデム２２２、リード・オンリ・メモリ（ＲＯＭ）２２４、ハード・ディスク・ドライブ（ＨＤＤ）２２６、ＣＤ−ＲＯＭドライブ２３０、ユニバーサル・シリアル・バス（ＵＳＢ）ポートおよびその他の通信ポート２３２、ならびにＰＣＩ／ＰＣＩｅデバイス２３４は、バス２３８とバス２４０とを経由して、ＳＢ／ＩＣＨ２０４に接続している。ＰＣＩ／ＰＣＩｅデバイスは、例えば、イーサネット（Ｒ）・アダプタ、アドイン・カード、およびノートブック・コンピュータのためのＰＣカードを含むことがある。ＰＣＩはカード・バス・コントローラを用いるが、ＰＣＩｅはこれを用いない。ＲＯＭ２２４は、例えば、フラッシュ基本入出力システム（ＢＩＯＳ）とすることができる。
【００２９】
ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、バス２４０を経由して、ＳＢ／ＩＣＨ２０４に接続している。ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、例えば、インテグレーテッド・ドライブ・エレクトロニクス（ＩＤＥ）またはシリアル・アドバンスト・テクノロジ・アタッチメント（ＳＡＴＡ）インターフェースを用いることができる。スーパーＩ／Ｏ（ＳＩＯ）デバイス２３６は、ＳＢ／ＩＣＨ２０４に接続されうる。
【００３０】
オペレーティング・システムは、処理ユニット２０６上で動作する。オペレーティング・システムは、図２のデータ処理システム２００の内部の様々なコンポーネントを調整し、その制御を提供する。クライアントとしては、オペレーティング・システムは、Ｍｉｃｒｏｓｏｆｔ（Ｒ）Ｗｉｎｄｏｗｓ７（Ｒ）など、市販のオペレーティング・システムでありうる。Ｊａｖａ（ＴＭ）プログラミング・システムなどのオブジェクト志向プログラミング・システムが、オペレーティング・システムと共に動作することがあり、データ処理システム２００上で実行されるＪａｖａ（ＴＭ）プログラムまたはアプリケーションから、オペレーティング・システムにコールを提供する。
【００３１】
サーバとしては、データ処理システム２００は、例えば、アドバンスト・インタラクティブ・エグゼキュティブ（ＡＩＸ（Ｒ））オペレーティング・システムまたはＬＩＮＵＸ（Ｒ）オペレーティング・システムを動作させるＩＢＭ（Ｒ）のｅＳｅｒｖｅｒ（ＴＭ）Ｓｙｓｔｅｍ  ｐ（Ｒ）コンピュータ・システムでありうる。データ処理システム２００は、処理ユニット２０６の中に複数のプロセッサを含む対称型マルチプロセッサ（ＳＭＰ）システムでありうる。あるいは、シングル・プロセッサ・システムを用いることも可能である。
【００３２】
オペレーティング・システム、オブジェクト志向プログラミング・システム、およびアプリケーションまたはプログラムのための命令は、ＨＤＤ２２６などのストレージ・デバイス上に置かれ、処理ユニット２０６による実行のために、メイン・メモリ２０８にロードすることができる。本発明の例示的実施形態のためのプロセスは、コンピュータ使用可能なプログラム・コードを用いて処理ユニット２０６によって実行されうる。なお、コンピュータ使用可能なプログラム・コードは、例えばメイン・メモリ２０８やＲＯＭ２２４などのメモリに、または、例えば１つまたは複数の周辺機器２２６および２３０に、置かれうる。
【００３３】
図２に示されているようなバス２３８またはバス２４０などのバス・システムは、１つまたは複数のバスで構成されていることがありうる。もちろん、このバス・システムは、そのファブリックまたはアーキテクチャに付属する異なるコンポーネントまたはデバイスの間においてデータの転送を提供する任意のタイプの通信ファブリックまたはアーキテクチャを用いて、実装することが可能である。図２のモデム２２２またはネットワーク・アダプタ２１２などの通信ユニットは、データを送信および受信するのに用いられる１つまたは複数のデバイスを含みうる。メモリは、例えば、図２におけるＮＢ／ＭＣＨ２０２において見られるような、メイン・メモリ２０８、ＲＯＭ２２４、またはキャッシュでありうる。
【００３４】
図１および図２におけるハードウェアが実装形態に応じて変わりうることは、当業者であれば理解するであろう。図１および図２に示されているハードウェアに加えて、またはこれらの代わりに、フラッシュメモリ、同等な不揮発性メモリ、もしくは光ディスクドライブなど、他の内部的なハードウェアまたは周辺機器を用いることができる。また、例示的実施形態のプロセスは、本発明の精神および範囲から逸脱することなく、上述したＳＭＰシステムの他に、マルチプロセッサ・データ処理システムにも適用できる。
【００３５】
更に、データ処理システム２００は、クライアント・コンピューティング・デバイス、サーバ・コンピューティング・デバイス、タブレット・コンピュータ、ラップトップ・コンピュータ、電話機もしくはそれ以外の通信デバイス、パーソナル・デジタル・アシスタント（ＰＤＡ）、または同様のものを含む、多数の異なるデータ処理システムのうちの任意のものの形式をとりうる。いくつかの実施例では、データ処理システム２００は、ポータブル・コンピューティング・デバイスでありうる。このポータブル・コンピューティング・デバイスは、例えば、オペレーティング・システムのファイルまたはユーザ生成データあるいはその両方を格納するための不揮発性メモリを提供するフラッシュ・メモリを用いて構成される。本質的に、データ処理システム２００は、任意の既知のまたはこれ以後に開発されるデータ処理システムでかまわないのであって、アーキテクチャに関する制限は存在しない。
【００３６】
再び図１および図２を参照すると、例えば図２のデータ処理システムとして実装可能である図１のサーバ１０６などのデータ処理もしくはコンピューティング・デバイス／システムが、または、要素の異なる構成および組成を有しているが本明細書で以下に説明される例示的実施形態のメカニズムを実装することができる別のタイプのデータ処理システムが、データ処理／コンピューティング・システムがオリジナル・データを処理することができるように、符号化されたデータ・ストリームのオリジナル・データに復号される必要がある圧縮されたデータの可変長部分を有する符号化されたデータ・ストリームを受け取る。符号化されたデータ・ストリームは、例えばサーバ１０４、クライアント１１０、１１２、および／または１１４などのこの例におけるサーバ１０６に結合された他のデータ処理システム／コンピューティング・デバイスの１つまたは複数によって送信されうる。符号化されたデータ・ストリームは、１つまたは複数のネットワーク１０２を経由して送信されうる。もちろん、可変長符号化データ・ストリームが例示的実施形態のメカニズムを実装するデータ処理システム／コンピューティング・デバイスによって受け取られうるという任意の他のシナリオを、例示的実施形態のメカニズムと共に、同様に用いることができる。すなわち、データ処理システム／コンピューティング・デバイスまで、可変長符号化データ・ストリームがどのように送信されるのかは重要でないし、または、可変長符号化データ・ストリームが送信される状況も重要でない。可変長符号化データ・ストリームがデータ処理システム／コンピューティング・デバイスにおいて受け取られ、それ以後に、本明細書で以下説明されるように、例示的実施形態のメカニズムによって作用を受けるというだけのことである。
【００３７】
可変長符号化データ・ストリームは、可変長のシンボルを生成してオリジナルの符号化されていないデータを符号化する任意の既知のまたは以後に開発される符号化アルゴリズムを用いて、符号化することができる。ここでの説明のため、以後では、可変長符号化データ・ストリームはＤＥＦＬＡＴＥアルゴリズムを用いて符号化されたこと、したがって、可変長符号化データ・ストリームはＤＥＦＬＡＴＥフォーマットを有していると仮定する。しかし、本発明はＤＥＦＬＡＴＥフォーマットを有するデータ・ストリームと共に用いることに限定されないことを、理解すべきである。また、例示的な実施形態の精神および範囲から逸脱することなく、可変長符号化を有する他のデータ・ストリームを例示的実施形態のメカニズムと共に用いることができることも、理解すべきである。
【００３８】
典型的には、可変長符号化データ・ストリームは、それ自身を、並列的な復号動作にゆだねることはない。すなわち、データ処理システムのプロセッサは、データ・ストリームの複数の部分を並列で復号することはできない。これは、データ・ストリームにはバイト整列マーカが存在せず、したがって、データのある部分がどこで始まりどこで終わるか、そして、データの別の部分がどこで始まりどこで終わるかを、そのデータ・ストリームから判断できないからである。例えば、データのある部分が７ビットの長さで、別の部分が９ビットの長さで、更に別の部分が１６ビットの長さである、ということがありうるが、これらの境界がどこに存在しているのかを、データ・ストリームから判断することはできないからである。結果的に、データ・ストリームを、その後で並列処理される塊に単純に分割することはできない。その理由は、その分割がある１つのシンボルの内部でなされ、そのために不正確な圧縮解除の結果が生じるおそれがあるからである。結果的に、可変長符号化データ・ストリームの処理は、一般的に、シーケンシャルな復号動作を用いて実行される。しかし、シーケンシャルな復号動作は、可変長符号化データ・ストリームの復号が達成されうるスループットおよび速度を制約する。
【００３９】
例示的実施形態は、復号または圧縮解除動作を符号化データ・ストリームに対して実行するときに、その符号化された（または圧縮された）データ・ストリームにおける可変長シンボルを考慮するためのメカニズムを提供する。すなわち、例示的実施形態は、可変長符号化データ・ストリームに対して並列で作用する復号器または圧縮解除器メカニズムを提供する。図３は、ある例示的実施形態による１つのそのような復号器／圧縮解除器アーキテクチャのブロック図の例である。図３に示されている要素は、ハードウェア、１つまたは複数のハードウェア・デバイスによって実行されるソフトウェア、あるいはハードウェアもしくはソフトウェアまたはその両方の任意の組み合わせとして実装することができる。ある例示的実施形態では、図３の要素は、回路ロジックにおいて実装され、したがって、ハードウェアのみによる例示的実施形態を表す。他の例示的実施形態では、図３に示されている要素の１つまたは複数は、例えばハードウェア実装されたプロセッサであるハードウェア・デバイスによって実行されてその機能を実現するソフトウェア、ファームウェア、または同様のものとして、実装することができる。更に他の例示的実施形態では、図３の要素の一部はハードウェアのみの回路として実装が可能であるのに対し、他方、１つまたは複数のハードウェア・デバイス上で実行されるソフトウェア、ファームウェア、または同様のものとして実装される要素も存在する。
【００４０】
図３に示されているように、復号器／圧縮解除器３００は、整列ロジック３１０と、トークナイザ・ロジック３２０と、トークン・テーブルのデータ構造３２５と、出力生成器ロジック３３０と、データ・ストリーム入力ライン・ストレージ３４０とを含む。復号器／圧縮解除器３００は、可変長符号化データ・ストリーム３５０を、入力として受け取る。それぞれのプロセッサ・サイクルの間に、復号器／圧縮解除器３００は、可変長符号化データ・ストリーム３５０の「入力ライン」を受け取る。この入力ラインは、１回のプロセッサ・サイクルの間に受け取られた入力データ・ストリームのデータのバイト数として定義される。入力ラインは、固定されたサイズすなわちバイト数Ｍを有する。１以上である可変長符号化データ・ストリーム３５０の圧縮比に対して、入力ラインにおけるバイト数Ｍは、プロセッサ・サイクルごとに生成されることが求められる圧縮解除された出力のバイト数であるＮ未満である。可変長符号化データ・ストリーム３５０の内部では、オリジナル・データにおける固定長のキャラクタが、可変長のシンボルとして符号化されている。例えば、静的ハフマン符号化を備えたＤＥＦＬＡＴＥ圧縮アルゴリズムを用いて可変長符号化データ・ストリーム３５０が生成される特定の場合のように、ハフマン符号化が用いられるときには、符号化されたシンボルのそれぞれは、最小ハフマン符号の長さであるＨｍｉｎ（例えば、７ビット）から最長のハフマン符号の長さであるＨｍａｘ（例えば、３１ビット）までの間の可変長を有することができる。
【００４１】
復号器／圧縮解除器３００の整列ロジック３１０は、符号化されたシンボル境界で開始するように入力ラインにおける入力データを整列させるように、動作する。ここで、符号化データ・ストリームにおけるシンボルは、可変のビット数を用いて表現され、符号化／圧縮の前のオリジナル・データの１または複数バイトに対応する。例えば、ハフマン符号化を用いると、圧縮されたデータにおけるシンボルは、可変長ハフマン符号化を用いて符号化され、符号化されたシンボルは、オリジナル・データのリテラル・バイトか、または、以前に検出されたオリジナル・データのいくつかの連続的なバイトへのポインタかのいずれか一方を表す。固定サイズの入力ラインにおける符号化されたシンボルの長さが可変であることにより、入力ラインは、シンボル境界で開始するように整列されていない可能性があり、符号化されたシンボルの一部は、例えばある入力ラインから次の入力ラインへ、複数の入力ラインに及ぶことがありうる。
【００４２】
上述したように、現在の説明のコンテキストでは、入力ラインとは、固定されたバイト数を有する符号化されたデータを意味する。プロセッサ・サイクルごとに、入力ラインが受け取られ、処理される。本明細書で符号化データ・ストリームに関係して用いられている「シンボル」という用語は、符号化データ・ストリームにおける可変長符号化表現を意味する。ここで、それぞれのシンボルは、復号／圧縮解除されることにより１または複数バイトのオリジナル・データが得られる。例えば、８バイト（６４ビット）を含み長さが１７、８、９、２１および１１ビット（全体では６６）である５つのシンボルを含みうる入力ラインが、受け取られることがある。この例では、１７ビットのシンボル１は１３バイトのオリジナル・データに復号することができ、シンボル２は１バイトのオリジナル・データに復号することができる、等である。更に、シンボル１−５における総ビット数は６６ビットであるから、２ビットのビット・スピル・オーバが存在する。したがって、次のラインは、新しいシンボル境界でそれを整列して開始するために２ビットだけシフトしなければならない。
【００４３】
図４は、複数の入力ラインを図解している例示的な図であり、ある入力ラインから別の入力ラインへの符号化されたシンボルのビットのスピル・オーバを図解している。図４には、圧縮されたデータにおける符号化されたまたは圧縮されたシンボルに対応するシンボル４１０−４２４が示されている。第１の入力ライン４３０は、やはり１回のプロセッサ・サイクル内で受け取られる圧縮されたデータのバイト数であって、シンボル４１０−４１４とシンボル４１６の第１の部分とを含む。シンボル４１６は、次の入力ライン４４０の中にスピル・オーバを生じていることにより、シンボル４１６のビットは、入力ライン４３０と入力ライン４４０との両方に存在している。これは、「ビット・スピル・オーバ」と称される。したがって、シンボル４１８の開始を識別する入力ライン４４０におけるオフセットは、入力ライン４３０からのスピル・オーバのビット数に左右される。スピル・オーバを生じる最小のビット数は０であり、他方、最大のスピル・オーバはＨｍａｘ−１である。その理由は、符号化されたシンボルのサイズは、高々、符号Ｈｍａｘの最大サイズであり、スピル・オーバが存在するためには、入力ライン４３０に少なくとも１ビットは存在していなければならないからである。
【００４４】
したがって、入力ライン４４０を整列するためには、直前の入力ライン４３０からのスピル・オーバの量をまず決定しなければならないし、このスピル・オーバを補償しなければならない。これは、図３における復号器／圧縮解除器３００の整列ロジック３１０によって提供される機能である。これらの入力ラインの並列処理を実行するために、入力ラインは、ビット・スピル・オーバを補償することによって、シンボル境界の始点で整列される必要がある。そのようなビット・スピル・オーバを補償することによって、いったん整列がなされると、例示的実施形態のメカニズムが、整列された入力ラインに対して並列で作用することができる。
【００４５】
入力ライン４３０および４４０という特定のペアに対するビット・スピル・オーバがどれだけあるかは先験的に知られているわけではないために、例示的実施形態の整列ロジック３１０は、すべてのスピル・オーバのオプションとそれに続く遅れた選択動作と共に、推論的復号のためのパイプライン・アーキテクチャを用いる。推論的復号は、０からＨｍａｘ−１までのすべての可能性があるオフセットに対して、それぞれのラインのＨｍａｘ通りの推論的処理を含む。すなわち、ラインを復号するときには、すべての可能性があるオフセットが並列で考慮され、その復号の結果と直前のラインの復号結果とに基づいて、可能性のあるオフセットのうちの１つに対する復号結果の１つが選択される。推論的復号は、入力ラインにおけるそれぞれのオフセットに対して、並列的で、パイプライン化して実行される。
【００４６】
正しいビット・スピル・オーバが識別され対応するオフセットが決定される態様を更に説明するため、次の単純化された例示的場合を考察しよう。ｘビットのオフセットとｙビットのオフセットとに対応する可能性のあるオフセットは、２つだけしか存在しないと仮定する。ここで、入力ラインは最大でｎ個のシンボルを含んでいて、コンピューティング・デバイスはプロセッサ・サイクルごとに高々１つのシンボルを処理することができるので、その入力ラインを処理するには複数のサイクルが必要になる、と仮定する。サイクル１では、入力ライン１が受け取られ、入力ライン１における第１のシンボルは、２つのオフセットの場合に対する入力ラインの第１のシンボルの長さを見つけるために、ｘビットのオフセットとｙビットのオフセットとを考慮して、処理される。次のプロセッサ・サイクルでは、入力ライン２が受け取られ、同様に、ライン２における第１のシンボルは、ｘビットのオフセットとｙビットのオフセットとを考慮して、処理される。同じプロセッサ・サイクルにおいて、入力ライン１の第２のシンボルが、２つの推論的なシナリオのために処理される。このプロセスが継続し、ｎ回のサイクルの後では、入力ライン１の可能性があるすべてのｎ個のシンボルが処理され、コンピューティング・デバイスは、そのラインにおける可能性があるｎ個すべてのシンボルの長さを知ることになる。すべてのシンボルの全体の長さから入力ラインの長さを減算すると、次のラインへの可能性があるビット・スピル・オーバの値が示される。例えば、２つの推論的な場合に対するすべてのシンボルの全体の長さが６９ビットと７１ビットであって、入力ラインの長さが６４ビットである場合には、ビット・スピルの可能性のある推論的な値は２つ存在する（５ビットと７ビット）。選択メカニズムが提供されて、これらの推論的ビット・スピル・オーバまたはオフセットのどちらが正しいビット・スピル・オーバまたはオフセットであるかを、直前の入力ライン・データの復号からの決定されたビット・スピル・オーバまたはオフセットに基づいて、選択する。
【００４７】
２つの可能性のあるオフセットまたはビット・スピル・オーバを考慮するだけではなく、上述の例におけるように、例示的実施形態のメカニズムを用いると、可能性がある任意の数のビット・スピル・オーバまたはオフセットを、並列で考慮することができる。例えば、ある例示的実施形態では、０からＨｍａｘ−１ビットまでの可能性のあるビット・スピル・オーバまたはオフセットが、それぞれの入力ラインを処理するときに、考慮される。
【００４８】
図５は、ある例示的な実施形態に従って入力ラインの整列を決定するときの、復号器／圧縮解除器３００の整列ロジック３１０の動作を図解する例示的なブロック図である。図５に示されているように、整列ロジック３１０は、Ｍバイトの符号化／圧縮されたデータを含む入力ライン５１０を受け取る。整列ロジック３１０のパディング・ロジック５２０が、直前の入力ラインからの最大のスピル・オーバのビット数を用いて、入力ライン５１０をパディングする。このように、例えば、第１のプロセッサ・サイクルでは、第１の入力ラインが受け取られて格納されうる。そして、次のプロセッサ・サイクルでは、第２の入力ラインが受け取られて、最大のスピル・オーバのビット数まで、直前のプロセッサ・サイクルの間に受け取られた第１の入力ラインと組み合わされうる。このパディングされた入力ラインは、並列パイプライン５３０−５５０に入力される。並列パイプライン５３０−５５０のそれぞれは、可能性のあるオフセット（ビット・スピル・オーバ）の量のうちの１つの分だけ、パディングされた入力ラインのシフトを実行する。例えば、第１のパイプライン５３０は０ビットのシフトを実行し、第２のパイプライン（図示せず）は１ビットのシフトを実行する可能性があり、第３のパイプライン（図示せず）は２ビットのシフトを実行する可能性があり、以下同様である。このようにして、パイプライン５４０は、ｉビットのシフトを実行し、最後のパイプライン５５０は、（Ｈｍａｘ−１）ビットすなわち最大のオフセット（ビット・スピル・オーバ）のシフトを実行する。
【００４９】
それぞれのパイプライン５３０−５５０において、そのパイプラインのそれぞれの段５３２−５３６、５４２−５４６、および５５２−５５６は、シフトされパディングのなされた入力ラインを格納し、シフトされパディングのなされた入力ラインの次のシンボルを復号する。パイプライン５３０−５５０は、８＊Ｍ／Ｈｍｉｎのパイプラインの深さを有しており、ここで、Ｈｍｉｎは最小の符号化されたシンボルの長さであり、これは、静的ハフマン符号化のこの特定の例では７ビットである。シンボルのサイズは、シンボル・タイプに基づいていて、符号化アルゴリズムにおいて特定され整列ロジック３１０に知られている幅ｗ（または、長さ）を有する。例えば、ＤＥＦＬＡＴＥのアルゴリズムとデータ・フォーマットを用いると、シフトされパディングされた入力ラインにおけるシンボルの中の特定のコードに対する長さ（幅）は、符号化アルゴリズムと関連する符号化テーブルから読み出すことによって、知られる。例えば、符号化テーブルは、特定のパターンのビットに対して、次の符号化されたシンボルの長さが何であるかということを定義するエントリを有する。例えば、符号化テーブルは、次のｎバイトが１０１０１１１．．．である場合には次のシンボルの長さはｘであり、次のｎバイトが１１１０００．．．である場合には次のシンボルの長さはｙであり、などと、定義することができる。いったん次のシンボルの長さが知られると、入力ラインは、そのビット数だけシフトされ、次のｎビットが、次のシンボルの長さを見つけるために、再び調べられることがある、などである。
【００５０】
それぞれの段５３２−５３６、５４２−５４６、および５５２−５５６は、１つまたは複数のレジスタと、計算ロジック（ＣＬ）と称され、シフトされパディングされた入力ライン５１０の次のシンボルの復号／圧縮解除を行い蓄積されたシフト量を更新する復号／圧縮解除ロジックとを含む。すなわち、段５３２−５３６、５４２−５４６、および５５２−５５６に対する蓄積されたシフト量は、直前の段からの蓄積されたシフト量と、現在の段である５３２−５３６、５４２−５４６、および５５２−５５６によって処理される次のシンボルの幅とを加算した値に等しい。このシフト量が、オリジナルのＭバイトの入力ラインの最後に至るまで、蓄積される。すなわち、復号は、累積的シフトがパディングされていない入力ラインの長さ以上になるところまで、実行される。これは、シフトの量とシンボルの幅とに応じて、パイプライン５３０−５５０の段５３２−５３６、５４２−５４６、および５５２−５５６の任意の段において生じうる。いったんこの修正されたシフト量が入力ラインのサイズと一致するかまたはそのサイズを超えると（示されている例では、入力ラインは、Ｍを入力ラインにおける圧縮されたバイト数であり、８は１バイト当たりのビット数を表すとして、８＊Ｍビットである）、シフトの量の蓄積を継続するのではなく、入力ラインと現時点の蓄積されたシフト量とが、更新はなされない状態で、段から段へ送られる。例えば、オリジナルの入力ラインの長さが６４ビットであり、それが９４ビットまでパディングされる場合には、符号化は、累積的シフトが６４ビット以上になるところまで、実行される。この場合には、入力ラインの９４ビットまでのパディングが必要なのであり、その理由は、例えば６３ビットで開始して６４ビットまで延長するシンボルが存在する可能性があり、このシンボルは、すべての９４ビットが既知になるまで復号することだけが可能であるからである。６４ビットのオリジナルのパディングされていない入力ラインの長さは、次の入力ラインへのスピル・オーバまたはオフセットである。
【００５１】
パイプライン５３０−５５０の終点では、入力ラインのサイズ（８＊Ｍ）が、蓄積されたシフト量の「シフト」から減算されて、次の入力ラインへの推論的なビット・スピル・オーバが得られる。このように、マルチプレクサ５６０に入力されるそれぞれのパイプライン５３０−５５０に対する推論的なビット・スピル・オーバの値が存在する。マルチプレクサ５６０への推論的なビット・スピル・オーバの値の入力のうちの１つが、次の入力ラインに対するシフト動作（例えば、左シフト動作）を実行するのに用いられる実際のビット・スピル・オーバとして選択されることにより、次の入力ラインがシンボル境界に整列され、したがって、整列された入力ライン５７０が生成される。
【００５２】
可能性のある２つのビット・スピル・オーバ値であるｘまたはｙが存在する先の例を再び参照すると、マルチプレクサ５６０が、次の入力ラインを整列するためのスピル・オーバとしてこれらの２つの値から１つを選択するために、用いられる。マルチプレクサ５６０は、圧縮されたデータ・ストリームにおけるまさに第１の入力ラインのオフセット（または、ビット・スピル・オーバ）を知っており、したがってそのまさに第１の入力ラインすなわち入力ライン１の既知のオフセットに基づいて、２つのビット・スピル・オーバまたはオフセット値の１つを選択することが可能である（そのまさに第１の入力線に対しては、直前の入力線からのスピル・オーバは存在しないが、いくらかの既知のヘッダ・ビットが含まれる場合がありうる）。いったんこの選択がなされると、入力ライン１から入力ライン２への実際のビット・スピル・オーバが何であるのか分かる。次のプロセッサ・サイクルでは、入力ライン１から入力ライン２へのこの実際のビット・スピル・オーバを、ライン２からライン３への実際のビット・スピル・オーバを選択するのに用いることができる。入力ライン２からライン３への実際のビット・スピル・オーバは、次に、ライン３からライン４への実際のビット・スピル・オーバを選択するのに用いることができ、それ以下も同様である。
【００５３】
図３に戻ると、整列された入力ライン５７０が、トークナイザ・ロジック３２０への入力として、提供される。トークナイザ・ロジック３２０は整列ロジック３１０とは分離した状態で図解されているが、例示的実施形態の精神と範囲とから逸脱することなく、トークナイザ・ロジック３２０のパイプライン段は整列ロジック３１０におけるパイプライン段と一体化することができることを理解すべきである。トークナイザ・ロジック３２０は、図６に示されているように、整列された入力ラインにおける圧縮されたシンボルから、パイプライン化して、シンボル・データを抽出する。図６に示されているように、トークナイザ・ロジック３２０は複数の段６１０−６４０を備えており、それぞれの段は、計算ロジック（ＣＬ）と、計算ロジックの結果を格納する１つまたは複数のレジスタとを有する。パイプラインの深さは、入力ラインごとの有効なトークンの最大数（ｔ）に等しく、これは、８＊Ｍ／Ｈｍｉｎビットのシーリングを有する。
【００５４】
それぞれの段６１０−６４０における計算ロジックは、整列された入力ラインにおいて、次の符号化されたシンボルに対するシンボル・データを抽出するが、これは、オリジナル・データにおける１または複数バイトに対応する。このシンボル・データは、有効ビット、タイプ・ビット（例えば、リテラルか、または、先に格納されている一連のバイトへのポインタ／参照のいずれか一方）、リテラル値（タイプ・ビットがリテラルを示している場合）、逆距離（タイプ・ビットがポインタ／参照を示している場合）、および同様のものを含みうる。計算ロジックは、更に、つまりが整列された入力ラインにおけるシンボルから生成された復号／圧縮解除されたデータのバイト数である、シンボルと関連するインフレート・バイト数（ＩＢ）を決定し、トークナイザ・ロジック３２０のパイプラインにおける段６１０から段６４０までの入力ラインに対するインフレート・バイトの総数（ＩＢｔ）を維持する。
【００５５】
トークナイザ・ロジック３２０のパイプラインの最終段６４０では、トークン・テーブル６５０が、シンボルからの抽出された情報を用いて更新されることにより、トークン・テーブル６５０におけるトークン・エントリが生成される。図６に示されているように、トークン・テーブル６５０は、それぞれのエントリが入力ラインにおけるシンボルに対応する１つまたは複数のエントリを含む。トークン・テーブル６５０におけるそれぞれのエントリは、対応するトークンに対して、抽出された有効ビット、タイプ（例えば、リテラルまたはポインタ／参照）、書き込みポインタ（wr_ptr）、および逆距離またはシンボル（トークン）のタイプに応じた実際の復号／圧縮解除されたリテラル・シンボルを格納する。トークンに対する書き込みポインタ（wr_ptr）は、圧縮されていないデータ・ストリームにおいて、トークンを復号することによって生じたバイトを挿入すべき位置を指し示す。シンボル／トークンｉに対する書き込みポインタは、最後の書き込みポインタwr_lastに基づいて、最終段６４０において更新される。この最後の書き込みポインタwr_lastは、直前の入力ラインの最後までのすべてのシンボルによって生じたインフレート・バイトの総数に対応するのであるが、これは、現在の整列されたラインにおける直前のシンボル／トークンｉ−１までの累積的なインフレート・バイト数と加算される。すなわち、wr_last＋ＩＢｉ−１である。整列された入力ラインにおける第１のトークンは、直前の入力ラインに対するwr_lastの値に設定された書き込みポインタwr_ptrを有する。その理由は、これが、整列された入力ラインにおける最初のシンボル／トークンであるからである。最後の書き込みポインタwr_lastは、また、最終段６４０において更新されることにより、この値は、次の整列された入力ラインを処理するときに用いるために格納される。トークン・テーブル６５０に格納されているトークンは、図３における出力生成器ロジック３３０に出力されうる。
【００５６】
出力生成器ロジック３３０は、トークナイザ・ロジック３２０によって生成されたトークンを取り、復号／圧縮解除されたＮバイトのデータをプロセッサ・サイクルごとに生成する。ある例証的な実施形態では、このＮバイトは、出力生成器ロジック３３０によって出力されたデータ・ワードを含んでおり、このデータ・ワードは、符号化された入力ラインのソースであったオリジナルのデータからの復号／圧縮解除されたバイトを含む。出力生成器ロジック３３０は、トークナイザ・ロジック３２０によって生成されたトークンを構文解析（パージング）しその情報をトークン・テーブル６５０のエントリに格納するステート・マシンを含み、プロセッサ・サイクルごとにＮバイトを生成する。出力生成器ロジック３３０は、復号／圧縮解除された出力ストリーム（out_ctr）の内部の現在のワード位置を維持し、Ｎバイトの現在の出力ワードのそれぞれに対するソース・トークン（src token [0:N-1]）を識別する。例えば、wr_ptr(tokenX)<= (out_ctr+i) < wr_ptr(tokenX+1)である場合、すなわち、トークンＸの始点を指している書き込みポインタが現在のワード位置とバイト・インデックスとの和以下であり、かつ、現在のワード位置とバイト・インデックスとの和が次のトークンＸ＋１の書き込みポインタよりも小さい場合には、トークンＸはバイトｉに対するソースである。
【００５７】
出力生成器ロジック３３０は、例えば少なくとも２つの入力ラインからのトークンを同時に処理するというように、複数の入力ラインからのトークンを同時に処理する。１組のトークンが現在の出力ワードによって完全に消費される（その組の中のすべてのトークンが用いられて、Ｎバイトである現在の出力ワードが生じる）ことがない場合、すなわち、[wr_last(token set 1) > (out_ctr+N)である場合には、整列ロジック３１０もしくはトークナイザ・ロジック３２０またはその両方のパイプラインが機能停止される。出力ワードを生成するときには、出力生成器ロジック３３０は、出力バイトがリテラルであるかどうかを判断し、そうである場合には、そのリテラル値が出力バイトにコピーされる。他方、出力バイトがポインタ、または既に識別された一連のバイトにおけるあるバイトへの参照である場合には、トークン・テーブル６５０に格納されている逆距離情報を用いてメモリ・ルックアップ動作が実行され、メモリからそのバイト・データを読み出し、それを出力ワードにコピーする。出力ワードを生成するために利用可能なトークンが十分に存在する場合には、すなわち、[wr_last(token set 2) < (out_crt+N)である場合には、一部の出力ワードが格納され、out_crtが保持され、新たな１組のトークンがフェッチされる。そうでない場合には、out_crtがＮだけインクリメントされて、動作が反復する。
【００５８】
図７は、ある例証的な実施形態による出力生成器ロジックのブロック図の例である。図７に示されているように、例えば２つの異なる入力ラインのそれぞれから１組ずつであるトークンの２つの組７１０および７１２が、Ｎ個のマルチプレクサ７２０−７２４への入力として受け取られる。ここで、Ｎは、特定のアーキテクチャのために望まれる出力のプロセッサ・サイクルごとのバイト数である。トークンの組７１０−７１２は、トークナイザ・ロジック３２０によって生成されたトークン・テーブル６５０から得られるため、このトークン・テーブル６５０からのトークン・エントリとそれらのエントリに格納されているすべての情報とを含む。
【００５９】
それぞれのマルチプレクサ７２０−７２４は、そのバイトに対する対応するソース・トークン選択信号src_token[i]と関連する。ここでｉは０からＮ−１の範囲にある。したがって、それぞれのマルチプレクサは、出力ワードにおけるその特定のバイトに対するソース・トークンを識別するソース・トークン選択信号src_token[i]に対応するトークンの組から、トークンを選択する。マルチプレクサ７２０−７２４は、追加的なロジックを含む。この追加的なロジックは、別のマルチプレクサ７３０−７３４への選択信号としての対応するトークン・タイプ（リテラルまたはポインタ／参照）と、トークン・タイプがリテラルである場合には、マルチプレクサ７３０−７３４への入力としてのトークン・テーブル・エントリからのリテラル・データと、トークン・タイプがポインタ／参照である場合には、トークン・テーブル・エントリの逆距離フィールドに基づいて決定された、別のマルチプレクサ７４０−７４４への更にはＲＡＭ７５０−７５４への入力でもある読み出しイネーブル／読み出しアドレスとを、選択されたトークンに対応するトークンの組におけるトークン・エントリに基づいて、出力する。
【００６０】
別個の専用メモリ７５０−７５４が、または、Ｎ個の読み出しポートを備えた共有メモリの一部が、プロセッサ・サイクルごとに生成される出力バイトのそれぞれに対して、提供される。これらのメモリ７５０−７５４のそれぞれは、同じ圧縮解除された／復号されたデータを格納する。すなわち、メモリ７５０−７５４のそれぞれは相互の複写である。出力ワード７６０におけるＮバイトに対応するＮ個のメモリ７５０−７５４は、それぞれが、Ｎバイト・ワードとして編成されている。あるいは、Ｎバイト・ワードとして編成され、それぞれの読み出しポートが出力ワード７６０におけるＮバイトのうちの１バイトとして機能するＮ個の読み出しポートを有する共有メモリを用いることもできる。メモリ７５０−７５４は、１つの共通の書き込みポートを共有することができる。全体のメモリ容量は、ポインタ／参照トークンによって参照されることが可能な直前の履歴によって決定される。例えば、ＤＥＦＬＡＴＥ仕様のための履歴は３２ＫＢである。Ｎ＝１６であると想定される場合は、この３２ＫＢは、それぞれが１６バイトである２Ｋメモリ・ワードとして編成される。読み出しイネーブルおよび読み出しアドレス信号に応じて、１６バイトのメモリ・ワードが読み出される。読み出しアドレス信号の上位側のビットはメモリ（３２ＫＢメモリの場合には１１ビット）からワードを読み出すために用いられ、下位側のビット（１６バイト・ワードの場合には４）はメモリ（マルチプレクサ７４０−７４４）から読み出されるＮバイトのうちの１バイトを選択するのに用いられる。
【００６１】
メモリ７５０−７５４からの選択されたバイトは、マルチプレクサ７２０−７２４からのリテラル出力と共に、入力としてマルチプレクサ７３０−７３４に与えられる。トークン・タイプ、すなわち、リテラルであるかまたはポインタ／参照であるかに基づいて、これらの入力のうちの１つが、出力ワードにおける対応する位置１−Ｎにおける出力ワード７６０のための出力バイトとして、選択される。例えば、トークン・タイプがリテラル・タイプである場合には、マルチプレクサ７３０−７３４へのリテラル・データ入力が選択される。トークン・タイプがポインタ／参照である場合には、マルチプレクサ７４０−７４４からのバイト出力が、マルチプレクサ７３０−７３４による出力のために選択される。したがって、マルチプレクサ７３０−７３４のそれぞれは、出力ワード７６０に、その出力ワードの中の正しい位置において含まれるデータのうちの１バイトを出力する。この出力ワード７６０は、次に、コンピューティング・デバイスにおける他のロジックに、処理のために提供されうる。ここで、コンピューティング・デバイスにおける他のロジックとは、例えば、そのコンピューティング・デバイス上で動作しているソフトウェアやファームウェアなどに基づいて出力ワード７６０に対して作用しうる、コンピューティング・デバイスにおける中央プロセッサまたは他の機能ユニットである。復号された出力ワードは、また、復号／圧縮解除された出力ストリームの中の現在のワード位置によって決定されるメモリ位置において、Ｎ個のメモリのそれぞれに、Ｎバイト・ワードとして格納される。
【００６２】
このようにして、例示的な実施形態のメカニズムを用いて、可変長符号化データ・ストリームの高帯域幅並列処理が可能になる。これらのメカニズムを用いると、単一のデータ・ストリームを、その単一のデータ・ストリームが可変長のシンボルを含むときであっても、並列で処理することが可能である。例示的な実施形態のメカニズムは、ある入力ラインから別の入力ラインへのビット・スピル・オーバを決定し、入力ラインがシンボル境界において開始するように入力ラインを再整列し、更に、ラインとその対応するシンボル／トークンとをそれに従って並列パイプラインのように処理することによって、可変長のシンボルを補償する。これにより、そのデータ・ストリームのシリアル化された処理のための要件を除去することによって可変長符号化データ・ストリームが処理されうるスループットと速度とが、著しく向上される。
【００６３】
図８は、ある例示的な実施形態によって可変長符号化データ・ストリームを処理するための例示的動作の概略を示す流れ図である。図８に概略が示されている動作は、データ処理システム／コンピューティング・デバイスの復号器／圧縮解除器において実装されうる。この復号器／圧縮解除器は、データ処理システム／コンピューティング・デバイスに、例えば、コプロセッサとして、ネットワークまたはストレージ・アダプタの一部として、別個のハードウェア・デバイスとして、あるいはこれらのハードウェア・デバイスの１つまたは複数と１つもしくは複数のプロセッサ・デバイス上で実行される１つまたは複数のソフトウェアメカニズムとの組み合わせとして、一体化することが可能である。
【００６４】
図８に示されているように、復号器／圧縮解除器がこの復号器／圧縮解除器が実装されているデータ処理システム／コンピューティング・デバイスに送信された可変長符号化データ・ストリームの一部である入力ライン・データを受け取る（ステップ８１０）ことによって、動作が開始する。復号器／圧縮解除器は、次の入力ライン・データへのその入力ライン・データのビット・スピル・オーバの量を、シンボル整列のために決定する（ステップ８２０）。復号器／圧縮解除器は、決定されたビット・スピル・オーバの量に基づいて、入力ライン・データを整列する（ステップ８３０）。復号器／圧縮解除器は、整列された入力ライン・データをトークン化して１組のトークンを生成する（ステップ８４０）。ここで、それぞれのトークンは、符号化された入力ライン・データにおけるシンボルに対応する。復号器／圧縮解除器は、この１組のトークンに基づいて、出力ワード・データを生成する（ステップ８５０）。この出力ワード・データは、オリジナルの１組のデータにおける１ワードのデータに対応する。この出力ワードは、処理のために、データ処理システム／コンピューティング・デバイスの他の要素に出力され（ステップ８６０）、動作が終了する。
【００６５】
上述したように、これらの説明のための実施形態は、すべてがハードウェアである実施形態、すべてがソフトウェアである実施形態、またはハードウェアとソフトウェアとの両方の要素を含む実施形態の形式をとりうることを、理解すべきである。ある実施形態の例では、上述した説明のための実施形態のメカニズムは、これらに限定されることはないが、ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含むソフトウェアまたはプログラム・コードとして実装される。
【００６６】
プログラム・コードを格納もしくは実行またはその両方を行うのに適したデータ処理システムは、直接的にまたはシステム・バスを介して間接的にメモリ要素に結合された少なくとも１つのプロセッサを含むことになる。このメモリ要素は、プログラム・コードが実際に実行されている間に用いられるローカル・メモリと、大容量記憶装置と、コードを実行中に大容量記憶装置から読み出されなければならない回数を減少させるために少なくとも一部のプログラム・コードの一時的保管を提供するキャッシュ・メモリとを含みうる。
【００６７】
入力／出力すなわちＩ／Ｏデバイス（これらに限定されることはないが、キーボード、ディスプレイ、ポインティング・デバイスなどを含む）は、直接に、または、Ｉ／Ｏコントローラを介在させて、システムに結合することができる。また、ネットワーク・アダプタをシステムに結合して、このデータ処理システムが、中間にある私有または公共のネットワークを通じて、他のデータ処理システムまたはリモートのプリンタもしくは記憶デバイスに結合されることを可能にすることもできる。モデム、ケーブル・モデム、およびイーサネット（Ｒ）カードは、現時点で利用可能なタイプのネットワーク・アダプタのごく一部である。
【００６８】
本発明に関する説明は、例示および説明の目的で提示してきたのであって、網羅的であることや開示された形態での発明に限定することは、意図していない。当業者には、多くの変更および改変が明らかであろう。本実施形態は、本発明の原理および実際的な応用を最もよく説明するために、また、他の当業者が、考察された特定の用途に適した様々な変更を伴う様々な実施形態として本発明を理解することができるように、選択され説明された。
【符号の説明】
【００６９】
１００  分散データ処理システム
１０２  ネットワーク
１０４  サーバ
１０６  サーバ
１０８  ストレージ・ユニット
１１０  クライアント
１１２  クライアント
１１４  クライアント
２００  データ処理システム
２０２  ＮＢ／ＭＣＨ
２０４  ＳＢ／ＩＣＨ
２０６  処理ユニット
２０８  メイン・メモリ
２１０  グラフィクス・プロセッサ
２１２  ネットワーク・アダプタ
２１６  オーディオ・アダプタ
２２０  キーボードおよびマウス・アダプタ
２２２  モデム
２２４  ＲＯＭ
２２６  ＨＤＤ
２３０  ＣＤ−ＲＯＭ
２３２  ＵＳＢポートおよびそれ以外の通信ポート
２３４  ＰＣＩ／ＰＣＩｅデバイス
２３８  バス
２４０  バス
３００  復号器／圧縮解除器
３１０  整列ロジック
３２０  トークナイザ・ロジック
３２５  トークン・テーブルのデータ構造
３３０  出力生成器ロジック
３４０  データ・ストリーム入力ライン・ストレージ
３５０  可変長符号化データ・ストリーム
４１０  シンボル１
４１２  シンボル２
４１４  シンボル３
４１６  シンボル４
４１８  シンボル５
４２０  シンボル６
４２２  シンボル７
５２０  パディング・ロジック
５７０  整列された入力ライン
７１０  トークンの組１
７１２  トークンの組２
７６０  出力ワード
【図１】
0005878644.tif 000002
【図２】
0005878644.tif 000003
【図３】
0005878644.tif 000004
【図４】
0005878644.tif 000005
【図５】
0005878644.tif 000006
【図６】
0005878644.tif 000007
【図７】
0005878644.tif 000008
【図８】
0005878644.tif 000009