データ圧縮及びデータ伸張
【課題】文字圧縮の改良されたデータ圧縮及び/又は伸張技法を提供する。
【解決手段】前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリームを備える圧縮データに作用するように構成されるデータ伸張装置が開示される。該装置は、出力メモリエリア、伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び前に復号されたデータの次の参照される群又は直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするためのデータコピー器を備える。
【解決手段】前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリームを備える圧縮データに作用するように構成されるデータ伸張装置が開示される。該装置は、出力メモリエリア、伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び前に復号されたデータの次の参照される群又は直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするためのデータコピー器を備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ圧縮及びデータ伸張に関する。
【背景技術】
【0002】
レンペル(Lempel)及びジフ(Ziv)は、いわゆるLZ77アルゴリズム及びLZ78アルゴリズム等の多数の可逆データ圧縮アルゴリズムを生み出した。これらのいわゆるLZ77アルゴリズム及びLZ78アルゴリズムは、LZW、LZSS他を含む多くの変形の基礎を成している。これらのLZ77アルゴリズム及びLZ78アルゴリズムは、共に、辞書コーダ(dictionary coder)である。辞書コーダは、符号化器及び復号器の双方をすでに通過した一致データの参照子でデータの一部を置換することによって圧縮を達成する。データの一致するセクションは、距離−長さ対(distance-length pair)と呼ばれる数字の対によって符号化され、効果的には、カウンタ(いくつの文字をコピーするのか)及びポインタ(すでに符号化されたデータ又はすでに復号されたデータにおける最初のこのような文字をどこで見つけるのか)の対によって符号化される。距離−長さ対は、「次の長さ文字のそれぞれが、未圧縮ストリームにおいてその後方にある文字、正確には距離文字に等しい」という記述と等価であると見ることができる。
【0003】
符号化フェーズ中、(符号化される文字の文字列の)可能な最良の一致するものが探し出される。すなわち、システムは、利用可能な符号化データ内において最大の長さを与える一致するものを得る。このプロセスは、添付図面の図1a〜図1cに関して模式的に示される。
【0004】
既に符号化されているデータは、「検索バッファ(search buffer)」10と呼ばれるメモリのエリアに記憶される。この検索バッファは、特定のアプリケーションにおいて既に符号化されたデータのすべてを保持するのに十分大きなものとすることもできるし、一定の量の最も近時に符号化されたデータのみを保持することもできる。符号化されるデータは、「先読みバッファ(look-ahead buffer)」20と呼ばれるメモリのエリアに記憶される。先読みバッファ20の最初の文字(この場合、文字「g」)が、符号化される次の文字である。もちろん、本出願では符号化されるデータを示すのに英数文字が使用され、これらのデータは「文字」として参照されるが、この表記は、解説を明確にするだけのためのものであることが認識されよう。当然、データが英数文字を表すものであろうと、ピクセルを表すものであろうと、オーディオサンプルを表すものであろうと、その他何を表すものであろうと、技術的に重要ではない。同様に、このような各「文字」のビットのサイズも、技術的に重要ではない。
【0005】
符号化器は、検索バッファ10において「g」のインスタンスを検索する。本例では、2つが見つけられる(図1a)。
【0006】
次に、符号化器は、検索バッファにおいて「g」の各インスタンスに続く位置を調べて、先読みバッファにおける次の文字(文字「f」)が「g」のいずれかのインスタンスの後に続いているか否かを検出する。実際には、次の文字は、双方のインスタンスにおいて後に続いており(図1b)、そこで、検索は、先読みバッファにおける次の後続の文字(「s」)に進む。この文字は、「gf」の1つのインスタンスの後にしか続いておらず(図1c)、先読みバッファにおける次の後続の文字(「h」)は、検索バッファにおいてそれら3つの文字の後に続いていない。そこで、先読みバッファの最初の3つの文字に関して生成される距離−長さ対は、(13,3)である。ここで、この文字列は、符号化シーケンス(検索バッファ)において13文字戻って開始し、3文字の長さを有する。
【0007】
2つ以上の文字の一致する文字列が検索バッファにおいて見つからない場合には、その文字は、「リテラル(literal)」として符号化される。すなわち、その文字は、出力データストリーム内に単にコピーされるだけである。そこで、圧縮の利益は、距離−長さ対の使用の結果生じ、リテラルは、元の文字と同程度の大きさであるだけでなく、その文字がリテラルであることを示す或る種のフラグも必要となるので、リテラルを引用することは、データ圧縮の目的に反した振る舞いをする。したがって、これらの技法は、有益な圧縮比を達成するために、文字列が繰り返す十分な見込みがあるデータには良く適している。
【0008】
したがって、一般に、このタイプのプロセスによって生成される圧縮データは、リテラルが点在した距離−長さ対から形成されることになる。
【0009】
図2a〜図2dは、距離−長さ対(13,3)の復号を模式的に示している。
【0010】
図2aは、距離−長さ対(13,3)がまさに復号されようとしている時の利用可能な復号データを提供する検索バッファを示している。図2b、図2c、及び図2dでは、検索バッファにおいて13文字戻った位置から開始する3つの文字の文字列が、出力用にコピーされる。
【0011】
このタイプのデータ圧縮及びデータ伸張は、データの符号化及び復号の成功が、符号化又は復号された前のすべてのデータに依拠するという点で、本質的に線形プロセスである。
【発明の概要】
【発明が解決しようとする課題】
【0012】
本発明の目的は、改良されたデータ圧縮及び/又は伸張技法を提供しようとすることである。
【課題を解決するための手段】
【0013】
本発明は、前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、を備える圧縮データに作用するように構成されるデータ伸張装置であって、該装置は、出力メモリエリア、伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び前に復号されたデータの次の参照される群又は直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするためのデータコピー器を備える、装置を提供する。
【0014】
本発明のさらなる各態様及び各特徴は、添付の特許請求の範囲に規定されている。
【0015】
本発明の上記の目的、特徴、及び利点、並びに他の目的、特徴、及び利点は、添付図面に関して読まれる例示の実施形態の以下の詳細な説明から明らかであろう。
【図面の簡単な説明】
【0016】
【図1a】これまでに提案されたデータ圧縮技法を模式的に示す。
【図1b】これまでに提案されたデータ圧縮技法を模式的に示す。
【図1c】これまでに提案されたデータ圧縮技法を模式的に示す。
【図2a】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2b】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2c】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2d】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図3a】データの3つのストリームを模式的に示す。
【図3b】データの3つのストリームを模式的に示す。
【図4】図3bのデータストリームを使用する伸張技法を示す模式的なフローチャートである。
【図5a】図4のフローチャートによるデータ伸張の模式的な加工例(worked example)を示す。
【図5b】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図5c】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図5d】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図6a】並列伸張技法を模式的に示す。
【図6b】並列伸張技法を模式的に示す。
【図6c】並列伸張技法を模式的に示す。
【図7】並列圧縮技法を示す模式的なフローチャートである。
【図8】並列伸張技法を模式的に示す。
【図9a】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図9b】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図9c】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図10】並列伸張技法を示す模式的なフローチャートである。
【図11】データ圧縮及び/又は伸張装置の模式図である。
【発明を実施するための形態】
【0017】
次に図3a及び図3bを参照すると、図1及び図2に関して説明された圧縮プロセス等の圧縮プロセスによって出力されたデータ信号が、距離−長さ対(図3bで「符号」と呼ばれる)の順序付けられたストリーム50、リテラルの順序付けられたストリーム60、及びフラグの順序付けられたストリーム70の3つのデータのストリームとして(圧縮装置により又は中間プロセスとして)配列されている。フラグは、復号される次のデータアイテムが距離−長さ対であるのか、又はリテラルであるのかを示す。
【0018】
図3aは、図1の技法によって生成されたような距離−長さ対及びリテラルが点在した単一のストリームからストリーム50及び60を再分割することができた時のストリーム50及び60を示している。フラグは、「l」(リテラル)及び「cp」(符号対、すなわち距離−長さ対)として模式的に示されている。
【0019】
図3bにおいて、ストリームは、ギャップを除去するように連接されている。復号時において、フラグストリームの次のエントリーは、符号化データの次のアイテムを符号ストリームから取り出すのか、又はリテラルストリームから取り出すのかを示す。符号ストリームの次のアイテムを示すポインタ(図示せず)及びリテラルストリームの次のアイテムを示すポインタ(図示せず)が維持される。アイテムが復号用にストリームから取り出されるたびに、関連のあるポインタは更新される(1アイテム分だけ前方に移動される)。
【0020】
図4は、図3bのデータストリームを使用する伸張技法を示す模式的なフローチャートである。
【0021】
ステップ100において、フラグストリームにおける次のフラグを検査して、そのフラグがリテラルを示すのか、又は符号対を示すのかを検出する。フラグがリテラルを示す場合には、ステップ110において、現在の「リテラル」フラグの後に続く「リテラル」フラグの個数をカウントすることにより、隣り合った(連続した)リテラルの個数が確定される。このカウントは、データ処理システム内の通常の解析的技法を使用して行うことができるが、Sony Computer Entertainment(ソニーコンピュータエンターテインメント)(登録商標)、Toshiba(東芝)(登録商標)、及びIBM(登録商標)によって開発された「セル(Cell)」マイクロプロセッサを使用する本実施形態(以下の図11参照)では、このマイクロプロセッサが、同一のビットの列の長さをカウントする単一のコマンドを実際に有する。そこで、ステップ110は、このようなセルマイクロプロセッサによって高速且つ容易に実行することができる。
【0022】
現在のフラグがリテラルを示していない場合には、次の符号対をステップ120において検査して、その符号対によって表される距離及び長さの量をリトリーブする。
【0023】
ステップ130において、コピーオペレーションを実行する。このコピーオペレーションでは、16個の隣り合った文字のブロックが、データ出力バッファ(すなわち、復号データが記憶されるメモリの場所又はエリア)へコピーされる。
(a)現在のフラグがリテラルを示していた場合には、次の16個のリテラルが、リテラルストリームから出力バッファへコピーされる。
(b)現在のフラグが符号対を示していた場合には、検査バッファにおいて距離変数により示される位置の後に続く16文字が出力バッファへコピーされる。
【0024】
連続したリテラルフラグの個数によって又は長さ変数によって実際に示される文字の個数に関わらず、16文字のブロックがコピーされる理由は、セルマイクロプロセッサがこの長さのブロックの効率的なコピー用に特に設計されているからである。当然、実際のリテラルの個数又は長さ変数が正確に16に等しいことは考えにくい。そこで、さまざまな対策を適用してこれに対処しなければならない。
【0025】
まず、リテラルの個数又は長さ変数が16よりも大きい状況を考えると、ステップ140において、この状況を検出し(「それ以外にあるか?」という質問は、コピーされる文字がそれ以外に残っているか否かを検出する、すなわち、リテラルの元の個数又は元の長さ変数から、既にコピーされた文字の個数を差し引いた残りが、0よりも大きいか否かを検出する)、制御は、ステップ130に再び渡り、16の別のブロックがコピーされる。これは、ステップ130によってコピーされたリテラルの個数又は前に復号された文字が、必要とされる個数に達するか又は必要とされる個数を超えるまで続く。
【0026】
その時点で、制御はステップ150に渡る。このステップにおいて、さまざまなポインタを更新する。出力バッファにおける現在の出力位置を示すポインタを、ステップ130によって出力バッファ内に書き込まれた最後の有効な文字を示すように更新する(すなわち、このポインタは、出力バッファへ既に書き込まれた有効に伸張されたデータの範囲を示す)。ステップ130が、16(又は16の倍数)個の文字を、必要な個数に達するか又は必要な個数を超えるようにコピーしたことを思い出すと、最後に有効にコピーされた文字は、ステップ130によってコピーされた最後の16文字内のいずれかにあることになる。
【0027】
たとえば、ステップ110によって検出された連続したリテラルフラグの個数が7であったものと仮定する。ステップ130において、現在の出力ポインタの位置から開始して、16個のリテラルが出力バッファ内にコピーされている。この個数16(この例では)は、有効なリテラルの個数(7)に関わらず、一定である。しかし、これらの16個のコピーされたリテラルの最初の7つのみが有効な復号データである。したがって、出力ポインタは、出力データバッファにおいて7文字前方に移動するように更新される。これは、ステップ130による次のコピーオペレーションが、前のコピーオペレーションの終端ではなく、前にコピーされたブロックの先頭の後の7文字で開始し、それによって、前にコピーされたが無効な最後の9文字は上書きされることになる。
【0028】
コピーオペレーションがリテラルに関係していたのか、又は符号対に関係していたのかに応じて、別の2つのポインタの一方をステップ150において更新する必要がある。最後のコピーオペレーションがリテラルに関係していた場合には、使用される(リテラルストリームにおける)次のリテラルへのポインタを(この例では、7つの位置だけ)更新する。最後のコピーオペレーションが符号対に関係していた場合には、符号対ストリームにおける次の利用可能な符号対へのポインタを更新する。
【0029】
最後に、検索バッファのコンテンツを、最も近時の復号データを反映するように更新する。検索バッファの更新は、そのオペレーションサイクルで実行された復号を反映するように、出力バッファにおける新しく追加され且つ有効な文字を検索バッファへコピーすることを伴う。
【0030】
次に、制御は、次のオペレーションのサイクルのために、ステップ100に戻る。
【0031】
特にセルマイクロプロセッサと共にデータの別個のストリームを使用することによって(ただし、セルマイクロプロセッサと共に使用することに限るものではない)、効率的な復号プロセスが与えられる。ステップ110又は120は、ステップ130と同様に、1つの命令のみによって実行される。そこで、ステップ100からステップ150までのサイクル全体は、比較的少数の命令で完了することができる。
【0032】
以下に示す一例のセルプロセッサの実施態様は、5つの命令とはならないが、特定のハードウェア実施態様は、わずか5つの命令とすることできる。
【0033】
[
// 必要とされるアラインされていない16バイトストリームを含む32バイト(16バイトにアラインされる)をフェッチする
lq b0to15,base,distance
lq b16to31,base16,distance
//16バイトのアラインされたストリームを、必要に応じて繰り返し生成する
shufb aligned,b0to15,b16to31,AlignRepeat
// アラインされた16書き込みブロックは、0〜14個の前に有効なバイトを含むことができる
lq write,dest
// ストリームをアラインされた終端まで挿入する
shufb write,write,aligned,insert0
sq write,dest
// 次の16バイトのアラインされたブロック内へのオーバーフローを生成する
shufb write,aligned,aligned,overflow
sq write,dest+16
]
【0034】
図5a〜図5dは、図4のフローチャートによるデータ伸張の模式的な加工例を示している。図3bに示すデータのストリームは、この加工例への入力として使用される。検索バッファは、ブロック160として模式的に示され、ステップ130によってコピーされた16ビット群は、ブロック170として模式的に示されている。
【0035】
図3bの最初の3つのフラグはリテラルフラグである。したがって、ステップ130は、リテラル「s」から開始して16個のリテラルを出力用にコピーする(図5a)。これらのうちの最初の3つのみが有効であり、そこで、ステップ150の結果、「s」、「d」、「g」が検索バッファへ書き込まれ、「次のリテラル」ポインタが、図3bのリテラルストリームにおけるリテラル「j」を指すように更新される。
【0036】
次のフラグは符号対フラグである。図5bでは、最初の符号対(7,4)が符号対ストリームから読み出され、16文字の適切なコピーが、検索バッファから作成されて出力される。これらの文字は、検索バッファからの近時に書き込まれた文字s、d、gを含むことに留意されたい。これらの文字のうちの最初の4つは有効であり、検索バッファに再びコピーされる。検索バッファに十分な文字が存在しない場合には、一定の16文字コピーは、これらの符号の複製されたバージョンで構成される。この必要性は、距離変数が16未満である場合に検出され、単純な表として実施される。
すなわち、
距離7:16文字は{0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1}である。
距離9:16文字は{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5}である。
【0037】
次のフラグも符号対フラグである。次の符号対(12,3)が読み出され、プロセスが、上述したように図5cで実行される。
【0038】
最後に、次の2つのフラグはリテラルフラグである。「j」から開始する16個のリテラルのブロックが、図5dでコピーされる。これらのリテラルのうちの最初の2つの文字が有効なデータである。
【0039】
いくつかの実施形態では、検索バッファは、実際には、別個のストアの形態である必要はないことに留意されたい。検索バッファに保持される情報は、出力バッファにも保持され、そこで、検索バッファの機能は、出力バッファに保持された有効に復号されたデータへの更新可能なポインタによって単純に達成することができる。検索バッファを更新するステップ(上述したステップ150の一部)は、単にポインタを更新することを伴うだけである。
【0040】
図6a〜図6cは、並列伸張技法を模式的に示している。これは、セルマイクロプロセッサとの関連で特に有用なさらに別の技法を表している(ただし、セルマイクロプロセッサとの関連に限られるものではない)。
【0041】
上述したように、符号対及びリテラルを使用するこれまでに提案された技法は、本質的に線形技法である。線形処理は、セルマイクロプロセッサ他等の並列プロセッサによるオペレーションにあまり役に立たない。以下の技法は、並列処理を効率的に使用してデータ圧縮及びデータ伸張に対処することを可能にする。
【0042】
基本原理は、圧縮されるデータが、複数のデータブロックに分割されるということである。図6a〜図6cでは、4つのこのようなブロック200が示されているが、この個数は、単に図面を明確にするために選ばれたものである。実際には、使用中のプロセッサの並列処理能力に適合するようにブロックの個数を選ぶことができる。そこで、たとえば、フル仕様のセルプロセッサでは、最大8つまでのブロックが、フル仕様のセルプロセッサ内の8つの利用可能なサブプロセッサを効率的に活用するのに適している。
【0043】
ブロックは、別個に圧縮及び伸張されるが、1つのブロックの圧縮/伸張が、処理されているブロックだけでなく他のブロックに関連付けられた検索バッファ内の参照子(距離−長さ対による)を使用することを可能にすることができる。
【0044】
特に伸張時における効率性を改善するために、ブロックは、サイズが可変にされ、ブロックサイズの導出及びデータの圧縮を行うのに、反復プロセスが使用される。この構成(後述)は、たとえば、ビデオゲームの処理中に使用されるビデオ又はテクスチャデータ(等)といった高速且つ効率的に伸張する必要があるデータをハンドリングするのに特に適している。多くの場合、ゲーム記憶媒体(たとえば、Blu−Ray(ブルーレイ)(登録商標)ディスク)内にデータを適合させるために圧縮しなければならないが、ビデオフレーム期間内にうまく伸張する必要があるこのようなデータは大量に存在する。このような構成は、圧縮プロセスをプロセッサにより多く集中させることによって、改善された伸張を提供するシステムを十分に利用することができる。
【0045】
ブロックサイズは、ブロックがほぼ同じ命令サイクル数を伸張に要するように選択される。伸張時に必要とされるサイクル数は、伸張中に見つけられた一致するブロックのサイズに依存し、また、符号化する必要があるリテラルの個数及び分布にも依存する。一般に、試験的圧縮(trial compression)が、伸張時において必要とされる命令サイクル数を検出する唯一の信頼することができる方法と考えられている。
【0046】
そこで、図6a〜図6cを参照すると、図6aは、圧縮されるデータの4つの(当初)等しいサイズのブロック200を示している。各ブロックは、圧縮プロセスを受け、(プロセスの途中の或る時刻において)既に圧縮された各ブロックの網掛け部分及びまだ圧縮されていない網掛けされていない部分によって模式的に示されている。4つのブロックの圧縮プロセスは、並列に実行することができるが、実際には、これは、圧縮時には必要ではない。
【0047】
4つのブロックを圧縮する際の相対的な進行度は、各ブロックのコンテンツの性質に依存し、具体的には、圧縮がどれだけ容易であるのかに依存する。図6bでは、ブロックの境界が移動された場合に、変更されたブロック200’の進行度が、はるかに一様なものとなっており、図6cのさらなる小さな移動(ブロック200”)によって、さらにより一様な進行度が与えられることが分かる。
【0048】
しかし、一様に近づけるべきものは、圧縮時間でもなければ、圧縮データの量でもない。一様にすべきものは、伸張時間、すなわち、より正確には、データを伸張するのに必要とされる命令サイクル数である。これを行うことによって、伸張時の並列プロセスのすべてが同時に開始して終了する。もちろん、正確な一様性が必要とされるわけではなく、合理的にできるだけ可能な一様性を得ることが目的とされているにすぎない。
【0049】
このポイントを示すために、図7は、ちょうど説明したような並列圧縮技法を示す模式的なフローチャートである。
【0050】
ステップ300において、ソースマテリアル(圧縮されるデータ)を、2つ以上の隣接したデータブロックに分割する。最初に、これは、等しいブロックサイズに基づいた分割とすることができるが、ソースマテリアルの統計的解析に基づいたサイズの重み付けを導入することが可能である。
【0051】
ステップ310において、各ブロックを、上述した技法の1つを使用して圧縮符号化する。
【0052】
ステップ320において、各符号化ブロックを復号(伸張)するのに必要とされる処理ステップ(命令サイクル)の個数を検出する。これは、符号化データの統計的解析(たとえば、リテラル又は符号対のような各データアイテムが必要とする命令サイクルがどれだけあるのかの知識に基づいて、リテラルがどれだけあるのか、リテラルの連続した群の長さ、符号対がどれだけあるのか等)により導出することもできるし、実際の試験的伸張により導出することもできる。
【0053】
ステップ330において、伸張処理所要量(decompression processing requirements)がブロック間で均一に分散されているか否かについての検出を行う。ここで、当業者は、「均一」は、「正確に均一」又は場合によっては「(たとえば)2%以内までで均一」を意味することができることを認識するであろう。
【0054】
分散が(定義されように)均一である場合には、プロセスは終了し、(ステップ310において既に圧縮されたような)ブロックは、その個数の伸張プロセッサを使用する並列伸張用に適切に圧縮されている。一方、分散が(定義されたように)均一でない場合には、ブロック境界を、ステップ340において移動する。伸張するのにより多くの処理を必要としたブロックはより小さくされ、逆もまだ同様に行われる。ブロックサイズの変更は、伸張処理所要量の差に比例したものとすることができる。そこで、たとえば、4ブロックシステムでは、処理所要量(100に正規化)が以下の通りである場合には、
【0055】
【表1】
【0056】
ブロックAのサイズは、1/11だけ削減され、ブロックCのサイズは、同じ量だけ増加される。これは、ブロックBのブロックサイズを同じに保ちながら、ブロックBの先頭境界及び終端境界の双方が移動することをおそらく意味する。(この例では)境界のこの変更のみがデータコンテンツに影響を与えることができ、したがって、ブロックBを伸張するための処理所要量に影響を与えることができるので、サイズが変更されたブロックだけでなく、4つのすべてのブロックをステップ310において再び処理することが適切である。
【0057】
伸張時には、各ブロックは並列に伸張される。たとえブロックサイズ(及び各ブロックの圧縮データのサイズ)がおそらく異なっていようとも、意図するものは、ブロック伸張プロセスがすべて同時に(又はほぼ同時に)開始して終了することである。図8は、ほぼ半分過ぎた時点でのこのような並列伸張技法を模式的に示している。各ブロックの伸張の開始点は、インジケータデータ(図示せず)によって示される。各圧縮ブロック210は、伸張されて、元のブロック200に戻されており、これまでの進行度は、既に伸張されたデータを表す網掛け部分によって示されている。
【0058】
図9a〜図9cは、各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示している。詳細には、図4の伸張技法が使用される場合、ステップ130によって書き出された16文字のブロックのオーバーラップを伴った問題が存在する可能性がある。
【0059】
この問題は、ブロックが、それよりも大きなソースデータセットの隣接したセクションを表すことから生じる可能性がある。それらのブロックは、伸張されるとき、メモリの隣接したエリアに記憶される可能性がある。これは、或るブロックの伸張の終端における最後に書き込まれた16文字群が、次のブロックの先頭における既に伸張された有効なデータに上書きされる可能性があることを意味し得る。
【0060】
図9aは、2つ出力ブロック220、230のみを模式的に示している。伸張プロセスは、(描かれた)ブロックの左端から右に向かって進行する。ブロック220の終端部分及びブロック230の先頭部分のみが示されている。
【0061】
最初の16文字群が、ステップ130によってブロック230内に書き込まれる。これらの文字のいくつかは有効でない可能性があるが、少なくとも正に最初の文字が有効であることは事実である。ブロック230の伸張は、出力ポインタ(上記ステップ150の説明を参照)が前方に移動して、ブロック230の16番目の文字を超えるまで続く。その時点で、ブロック230最初の16文字の全体(網掛け群232によって図9aに示される)が有効であることは事実である。その16文字群は、出力バッファとは別個のストア234へコピーされる。
【0062】
伸張は、その後、上述したように進行する。ブロック220の伸張の終了に向かうにつれて(実際には、伸張はすべて、伸張プロセスのすべての終了に向かうにつれて、同時に終了する)、16文字の最終ブロックが、ステップ130によって書き込まれる。これは、図9bに網掛けエリア236として模式的に示されている。データ236は、2つのブロックの境界にまたがっていることが分かる。ブロック220内に含まれる群236の文字は、もちろん、有効なデータである。境界を越えて含まれる文字、すなわち、ブロック230内の文字は、無効な文字であり、ステップ130のコピーオペレーションのアーティファクトである。しかし、これらは、ブロック230の先頭部分が伸張された時に、前に書き込まれた有効なデータに上書きされる。
【0063】
解決法は、先行ブロック220の伸張が完了した後に、ブロック230の最初の16個の文字内に、記憶されたデータ232を再書き込みすることである。
【0064】
先行ブロック220の最後に書き込まれた16文字群の少なくとも1つの文字は、その先行ブロック220内に含まれなければならないので、先行ブロックの伸張によって破損したあらゆるデータを元に戻すことを確実にするには、厳密には、各ブロックの最初の15文字のみを保存することが必要であることが認識されよう。しかし、本システムは、16文字データワードを効率的にハンドリングするように設計されているので、16文字群232が保存される。
【0065】
図10は、上述した並列伸張技法を示す模式的なフローチャートである。このプロセスは、ソースデータが2つ以上の隣接したブロック内に圧縮されているものと仮定するが、図7に関して説明した並列オペレーションの効率性改善は、図10の方法が有用となるための要件ではない。
【0066】
ステップ300において、各ブロックの伸張を開始する。16個の有効な文字を伸張すると(たとえば、出力ポインタが16番目の文字を過ぎることによって示される)、ステップ310において、最初の16個の伸張文字群を保存する。すなわち、別個のメモリエリアに記憶する。
【0067】
ステップ320において、伸張は、各ブロックの終端に続く。
【0068】
最後に、ステップ330において、各ブロックの先頭からの保存された16文字を、それらの元の位置へ再書き込みする。
【0069】
明らかに、この対策は、必ずしも、特定のソースマテリアルから導出された隣接したブロックのセットの最初のブロックについて行う必要はない。しかし、各ブロックについて同じ処理を使用すること、すなわち、最初のブロックについてもこれらのステップを実行することは並列システムにおいてより簡単なものとなり得る。
【0070】
最後に、図11は、データ圧縮及び/又は伸張装置の模式図である。
【0071】
この装置は、図を明確にするために簡単化した形態で示されている。当業者は、他のルーチンコンポーネントが必要とされる場合があることを認識するであろう。
【0072】
この装置は、データメモリ400(たとえば、圧縮データ又は伸張データを保持する検索バッファ及び出力バッファを記憶する)、プログラムメモリ410、中央処理装置(CPU)420(セルマイクロプロセッサ等)、並びに入力/出力ロジック430を備える。これらはすべて、バス440を介して相互接続されている。
【0073】
この装置は、CPU420がプログラムメモリ410に記憶されているプログラムコードを実行することによって、上述したオペレーションを実行する。このようなプログラムコードは、ディスク媒体450等の記憶媒体から得ることもできるし、場合によってはインターネット若しくは別のネットワーク470を介したサーバ460へのデータ接続等の伝送媒体によって得ることもできるし、他の既知のソフトウェア配布手段若しくはコンピュータプログラム製品によって得ることもできる。
【0074】
もちろん、代替的に、図11の機能は、注文ハードウェアによって達成することもできるし、ASIC(特定用途向け集積回路)又はFPGA(フィールドプログラマブルゲートアレイ)等のセミプログラマブルハードウェアによって達成することもできることが認識されよう。
【0075】
本明細書では、添付図面に関して、本発明の例示の実施形態を詳細に説明してきたが、本発明は、それらの正確な実施形態に限定されるものではないこと、並びに添付の特許請求の範囲によって規定されるような本発明の範囲及び精神から逸脱せずに、当業者は、さまざまな変更及び修正を実施形態において行うことができることが理解されるべきである。
【図1A】
【図1B】
【図1C】
【図2A】
【図2B】
【図2C】
【図2D】
【図3A】
【図3B】
【技術分野】
【0001】
本発明は、データ圧縮及びデータ伸張に関する。
【背景技術】
【0002】
レンペル(Lempel)及びジフ(Ziv)は、いわゆるLZ77アルゴリズム及びLZ78アルゴリズム等の多数の可逆データ圧縮アルゴリズムを生み出した。これらのいわゆるLZ77アルゴリズム及びLZ78アルゴリズムは、LZW、LZSS他を含む多くの変形の基礎を成している。これらのLZ77アルゴリズム及びLZ78アルゴリズムは、共に、辞書コーダ(dictionary coder)である。辞書コーダは、符号化器及び復号器の双方をすでに通過した一致データの参照子でデータの一部を置換することによって圧縮を達成する。データの一致するセクションは、距離−長さ対(distance-length pair)と呼ばれる数字の対によって符号化され、効果的には、カウンタ(いくつの文字をコピーするのか)及びポインタ(すでに符号化されたデータ又はすでに復号されたデータにおける最初のこのような文字をどこで見つけるのか)の対によって符号化される。距離−長さ対は、「次の長さ文字のそれぞれが、未圧縮ストリームにおいてその後方にある文字、正確には距離文字に等しい」という記述と等価であると見ることができる。
【0003】
符号化フェーズ中、(符号化される文字の文字列の)可能な最良の一致するものが探し出される。すなわち、システムは、利用可能な符号化データ内において最大の長さを与える一致するものを得る。このプロセスは、添付図面の図1a〜図1cに関して模式的に示される。
【0004】
既に符号化されているデータは、「検索バッファ(search buffer)」10と呼ばれるメモリのエリアに記憶される。この検索バッファは、特定のアプリケーションにおいて既に符号化されたデータのすべてを保持するのに十分大きなものとすることもできるし、一定の量の最も近時に符号化されたデータのみを保持することもできる。符号化されるデータは、「先読みバッファ(look-ahead buffer)」20と呼ばれるメモリのエリアに記憶される。先読みバッファ20の最初の文字(この場合、文字「g」)が、符号化される次の文字である。もちろん、本出願では符号化されるデータを示すのに英数文字が使用され、これらのデータは「文字」として参照されるが、この表記は、解説を明確にするだけのためのものであることが認識されよう。当然、データが英数文字を表すものであろうと、ピクセルを表すものであろうと、オーディオサンプルを表すものであろうと、その他何を表すものであろうと、技術的に重要ではない。同様に、このような各「文字」のビットのサイズも、技術的に重要ではない。
【0005】
符号化器は、検索バッファ10において「g」のインスタンスを検索する。本例では、2つが見つけられる(図1a)。
【0006】
次に、符号化器は、検索バッファにおいて「g」の各インスタンスに続く位置を調べて、先読みバッファにおける次の文字(文字「f」)が「g」のいずれかのインスタンスの後に続いているか否かを検出する。実際には、次の文字は、双方のインスタンスにおいて後に続いており(図1b)、そこで、検索は、先読みバッファにおける次の後続の文字(「s」)に進む。この文字は、「gf」の1つのインスタンスの後にしか続いておらず(図1c)、先読みバッファにおける次の後続の文字(「h」)は、検索バッファにおいてそれら3つの文字の後に続いていない。そこで、先読みバッファの最初の3つの文字に関して生成される距離−長さ対は、(13,3)である。ここで、この文字列は、符号化シーケンス(検索バッファ)において13文字戻って開始し、3文字の長さを有する。
【0007】
2つ以上の文字の一致する文字列が検索バッファにおいて見つからない場合には、その文字は、「リテラル(literal)」として符号化される。すなわち、その文字は、出力データストリーム内に単にコピーされるだけである。そこで、圧縮の利益は、距離−長さ対の使用の結果生じ、リテラルは、元の文字と同程度の大きさであるだけでなく、その文字がリテラルであることを示す或る種のフラグも必要となるので、リテラルを引用することは、データ圧縮の目的に反した振る舞いをする。したがって、これらの技法は、有益な圧縮比を達成するために、文字列が繰り返す十分な見込みがあるデータには良く適している。
【0008】
したがって、一般に、このタイプのプロセスによって生成される圧縮データは、リテラルが点在した距離−長さ対から形成されることになる。
【0009】
図2a〜図2dは、距離−長さ対(13,3)の復号を模式的に示している。
【0010】
図2aは、距離−長さ対(13,3)がまさに復号されようとしている時の利用可能な復号データを提供する検索バッファを示している。図2b、図2c、及び図2dでは、検索バッファにおいて13文字戻った位置から開始する3つの文字の文字列が、出力用にコピーされる。
【0011】
このタイプのデータ圧縮及びデータ伸張は、データの符号化及び復号の成功が、符号化又は復号された前のすべてのデータに依拠するという点で、本質的に線形プロセスである。
【発明の概要】
【発明が解決しようとする課題】
【0012】
本発明の目的は、改良されたデータ圧縮及び/又は伸張技法を提供しようとすることである。
【課題を解決するための手段】
【0013】
本発明は、前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、を備える圧縮データに作用するように構成されるデータ伸張装置であって、該装置は、出力メモリエリア、伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び前に復号されたデータの次の参照される群又は直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするためのデータコピー器を備える、装置を提供する。
【0014】
本発明のさらなる各態様及び各特徴は、添付の特許請求の範囲に規定されている。
【0015】
本発明の上記の目的、特徴、及び利点、並びに他の目的、特徴、及び利点は、添付図面に関して読まれる例示の実施形態の以下の詳細な説明から明らかであろう。
【図面の簡単な説明】
【0016】
【図1a】これまでに提案されたデータ圧縮技法を模式的に示す。
【図1b】これまでに提案されたデータ圧縮技法を模式的に示す。
【図1c】これまでに提案されたデータ圧縮技法を模式的に示す。
【図2a】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2b】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2c】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図2d】対応するこれまでに提案されたデータ伸張技法を模式的に示す。
【図3a】データの3つのストリームを模式的に示す。
【図3b】データの3つのストリームを模式的に示す。
【図4】図3bのデータストリームを使用する伸張技法を示す模式的なフローチャートである。
【図5a】図4のフローチャートによるデータ伸張の模式的な加工例(worked example)を示す。
【図5b】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図5c】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図5d】図4のフローチャートによるデータ伸張の模式的な加工例を示す。
【図6a】並列伸張技法を模式的に示す。
【図6b】並列伸張技法を模式的に示す。
【図6c】並列伸張技法を模式的に示す。
【図7】並列圧縮技法を示す模式的なフローチャートである。
【図8】並列伸張技法を模式的に示す。
【図9a】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図9b】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図9c】各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示す。
【図10】並列伸張技法を示す模式的なフローチャートである。
【図11】データ圧縮及び/又は伸張装置の模式図である。
【発明を実施するための形態】
【0017】
次に図3a及び図3bを参照すると、図1及び図2に関して説明された圧縮プロセス等の圧縮プロセスによって出力されたデータ信号が、距離−長さ対(図3bで「符号」と呼ばれる)の順序付けられたストリーム50、リテラルの順序付けられたストリーム60、及びフラグの順序付けられたストリーム70の3つのデータのストリームとして(圧縮装置により又は中間プロセスとして)配列されている。フラグは、復号される次のデータアイテムが距離−長さ対であるのか、又はリテラルであるのかを示す。
【0018】
図3aは、図1の技法によって生成されたような距離−長さ対及びリテラルが点在した単一のストリームからストリーム50及び60を再分割することができた時のストリーム50及び60を示している。フラグは、「l」(リテラル)及び「cp」(符号対、すなわち距離−長さ対)として模式的に示されている。
【0019】
図3bにおいて、ストリームは、ギャップを除去するように連接されている。復号時において、フラグストリームの次のエントリーは、符号化データの次のアイテムを符号ストリームから取り出すのか、又はリテラルストリームから取り出すのかを示す。符号ストリームの次のアイテムを示すポインタ(図示せず)及びリテラルストリームの次のアイテムを示すポインタ(図示せず)が維持される。アイテムが復号用にストリームから取り出されるたびに、関連のあるポインタは更新される(1アイテム分だけ前方に移動される)。
【0020】
図4は、図3bのデータストリームを使用する伸張技法を示す模式的なフローチャートである。
【0021】
ステップ100において、フラグストリームにおける次のフラグを検査して、そのフラグがリテラルを示すのか、又は符号対を示すのかを検出する。フラグがリテラルを示す場合には、ステップ110において、現在の「リテラル」フラグの後に続く「リテラル」フラグの個数をカウントすることにより、隣り合った(連続した)リテラルの個数が確定される。このカウントは、データ処理システム内の通常の解析的技法を使用して行うことができるが、Sony Computer Entertainment(ソニーコンピュータエンターテインメント)(登録商標)、Toshiba(東芝)(登録商標)、及びIBM(登録商標)によって開発された「セル(Cell)」マイクロプロセッサを使用する本実施形態(以下の図11参照)では、このマイクロプロセッサが、同一のビットの列の長さをカウントする単一のコマンドを実際に有する。そこで、ステップ110は、このようなセルマイクロプロセッサによって高速且つ容易に実行することができる。
【0022】
現在のフラグがリテラルを示していない場合には、次の符号対をステップ120において検査して、その符号対によって表される距離及び長さの量をリトリーブする。
【0023】
ステップ130において、コピーオペレーションを実行する。このコピーオペレーションでは、16個の隣り合った文字のブロックが、データ出力バッファ(すなわち、復号データが記憶されるメモリの場所又はエリア)へコピーされる。
(a)現在のフラグがリテラルを示していた場合には、次の16個のリテラルが、リテラルストリームから出力バッファへコピーされる。
(b)現在のフラグが符号対を示していた場合には、検査バッファにおいて距離変数により示される位置の後に続く16文字が出力バッファへコピーされる。
【0024】
連続したリテラルフラグの個数によって又は長さ変数によって実際に示される文字の個数に関わらず、16文字のブロックがコピーされる理由は、セルマイクロプロセッサがこの長さのブロックの効率的なコピー用に特に設計されているからである。当然、実際のリテラルの個数又は長さ変数が正確に16に等しいことは考えにくい。そこで、さまざまな対策を適用してこれに対処しなければならない。
【0025】
まず、リテラルの個数又は長さ変数が16よりも大きい状況を考えると、ステップ140において、この状況を検出し(「それ以外にあるか?」という質問は、コピーされる文字がそれ以外に残っているか否かを検出する、すなわち、リテラルの元の個数又は元の長さ変数から、既にコピーされた文字の個数を差し引いた残りが、0よりも大きいか否かを検出する)、制御は、ステップ130に再び渡り、16の別のブロックがコピーされる。これは、ステップ130によってコピーされたリテラルの個数又は前に復号された文字が、必要とされる個数に達するか又は必要とされる個数を超えるまで続く。
【0026】
その時点で、制御はステップ150に渡る。このステップにおいて、さまざまなポインタを更新する。出力バッファにおける現在の出力位置を示すポインタを、ステップ130によって出力バッファ内に書き込まれた最後の有効な文字を示すように更新する(すなわち、このポインタは、出力バッファへ既に書き込まれた有効に伸張されたデータの範囲を示す)。ステップ130が、16(又は16の倍数)個の文字を、必要な個数に達するか又は必要な個数を超えるようにコピーしたことを思い出すと、最後に有効にコピーされた文字は、ステップ130によってコピーされた最後の16文字内のいずれかにあることになる。
【0027】
たとえば、ステップ110によって検出された連続したリテラルフラグの個数が7であったものと仮定する。ステップ130において、現在の出力ポインタの位置から開始して、16個のリテラルが出力バッファ内にコピーされている。この個数16(この例では)は、有効なリテラルの個数(7)に関わらず、一定である。しかし、これらの16個のコピーされたリテラルの最初の7つのみが有効な復号データである。したがって、出力ポインタは、出力データバッファにおいて7文字前方に移動するように更新される。これは、ステップ130による次のコピーオペレーションが、前のコピーオペレーションの終端ではなく、前にコピーされたブロックの先頭の後の7文字で開始し、それによって、前にコピーされたが無効な最後の9文字は上書きされることになる。
【0028】
コピーオペレーションがリテラルに関係していたのか、又は符号対に関係していたのかに応じて、別の2つのポインタの一方をステップ150において更新する必要がある。最後のコピーオペレーションがリテラルに関係していた場合には、使用される(リテラルストリームにおける)次のリテラルへのポインタを(この例では、7つの位置だけ)更新する。最後のコピーオペレーションが符号対に関係していた場合には、符号対ストリームにおける次の利用可能な符号対へのポインタを更新する。
【0029】
最後に、検索バッファのコンテンツを、最も近時の復号データを反映するように更新する。検索バッファの更新は、そのオペレーションサイクルで実行された復号を反映するように、出力バッファにおける新しく追加され且つ有効な文字を検索バッファへコピーすることを伴う。
【0030】
次に、制御は、次のオペレーションのサイクルのために、ステップ100に戻る。
【0031】
特にセルマイクロプロセッサと共にデータの別個のストリームを使用することによって(ただし、セルマイクロプロセッサと共に使用することに限るものではない)、効率的な復号プロセスが与えられる。ステップ110又は120は、ステップ130と同様に、1つの命令のみによって実行される。そこで、ステップ100からステップ150までのサイクル全体は、比較的少数の命令で完了することができる。
【0032】
以下に示す一例のセルプロセッサの実施態様は、5つの命令とはならないが、特定のハードウェア実施態様は、わずか5つの命令とすることできる。
【0033】
[
// 必要とされるアラインされていない16バイトストリームを含む32バイト(16バイトにアラインされる)をフェッチする
lq b0to15,base,distance
lq b16to31,base16,distance
//16バイトのアラインされたストリームを、必要に応じて繰り返し生成する
shufb aligned,b0to15,b16to31,AlignRepeat
// アラインされた16書き込みブロックは、0〜14個の前に有効なバイトを含むことができる
lq write,dest
// ストリームをアラインされた終端まで挿入する
shufb write,write,aligned,insert0
sq write,dest
// 次の16バイトのアラインされたブロック内へのオーバーフローを生成する
shufb write,aligned,aligned,overflow
sq write,dest+16
]
【0034】
図5a〜図5dは、図4のフローチャートによるデータ伸張の模式的な加工例を示している。図3bに示すデータのストリームは、この加工例への入力として使用される。検索バッファは、ブロック160として模式的に示され、ステップ130によってコピーされた16ビット群は、ブロック170として模式的に示されている。
【0035】
図3bの最初の3つのフラグはリテラルフラグである。したがって、ステップ130は、リテラル「s」から開始して16個のリテラルを出力用にコピーする(図5a)。これらのうちの最初の3つのみが有効であり、そこで、ステップ150の結果、「s」、「d」、「g」が検索バッファへ書き込まれ、「次のリテラル」ポインタが、図3bのリテラルストリームにおけるリテラル「j」を指すように更新される。
【0036】
次のフラグは符号対フラグである。図5bでは、最初の符号対(7,4)が符号対ストリームから読み出され、16文字の適切なコピーが、検索バッファから作成されて出力される。これらの文字は、検索バッファからの近時に書き込まれた文字s、d、gを含むことに留意されたい。これらの文字のうちの最初の4つは有効であり、検索バッファに再びコピーされる。検索バッファに十分な文字が存在しない場合には、一定の16文字コピーは、これらの符号の複製されたバージョンで構成される。この必要性は、距離変数が16未満である場合に検出され、単純な表として実施される。
すなわち、
距離7:16文字は{0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1}である。
距離9:16文字は{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5}である。
【0037】
次のフラグも符号対フラグである。次の符号対(12,3)が読み出され、プロセスが、上述したように図5cで実行される。
【0038】
最後に、次の2つのフラグはリテラルフラグである。「j」から開始する16個のリテラルのブロックが、図5dでコピーされる。これらのリテラルのうちの最初の2つの文字が有効なデータである。
【0039】
いくつかの実施形態では、検索バッファは、実際には、別個のストアの形態である必要はないことに留意されたい。検索バッファに保持される情報は、出力バッファにも保持され、そこで、検索バッファの機能は、出力バッファに保持された有効に復号されたデータへの更新可能なポインタによって単純に達成することができる。検索バッファを更新するステップ(上述したステップ150の一部)は、単にポインタを更新することを伴うだけである。
【0040】
図6a〜図6cは、並列伸張技法を模式的に示している。これは、セルマイクロプロセッサとの関連で特に有用なさらに別の技法を表している(ただし、セルマイクロプロセッサとの関連に限られるものではない)。
【0041】
上述したように、符号対及びリテラルを使用するこれまでに提案された技法は、本質的に線形技法である。線形処理は、セルマイクロプロセッサ他等の並列プロセッサによるオペレーションにあまり役に立たない。以下の技法は、並列処理を効率的に使用してデータ圧縮及びデータ伸張に対処することを可能にする。
【0042】
基本原理は、圧縮されるデータが、複数のデータブロックに分割されるということである。図6a〜図6cでは、4つのこのようなブロック200が示されているが、この個数は、単に図面を明確にするために選ばれたものである。実際には、使用中のプロセッサの並列処理能力に適合するようにブロックの個数を選ぶことができる。そこで、たとえば、フル仕様のセルプロセッサでは、最大8つまでのブロックが、フル仕様のセルプロセッサ内の8つの利用可能なサブプロセッサを効率的に活用するのに適している。
【0043】
ブロックは、別個に圧縮及び伸張されるが、1つのブロックの圧縮/伸張が、処理されているブロックだけでなく他のブロックに関連付けられた検索バッファ内の参照子(距離−長さ対による)を使用することを可能にすることができる。
【0044】
特に伸張時における効率性を改善するために、ブロックは、サイズが可変にされ、ブロックサイズの導出及びデータの圧縮を行うのに、反復プロセスが使用される。この構成(後述)は、たとえば、ビデオゲームの処理中に使用されるビデオ又はテクスチャデータ(等)といった高速且つ効率的に伸張する必要があるデータをハンドリングするのに特に適している。多くの場合、ゲーム記憶媒体(たとえば、Blu−Ray(ブルーレイ)(登録商標)ディスク)内にデータを適合させるために圧縮しなければならないが、ビデオフレーム期間内にうまく伸張する必要があるこのようなデータは大量に存在する。このような構成は、圧縮プロセスをプロセッサにより多く集中させることによって、改善された伸張を提供するシステムを十分に利用することができる。
【0045】
ブロックサイズは、ブロックがほぼ同じ命令サイクル数を伸張に要するように選択される。伸張時に必要とされるサイクル数は、伸張中に見つけられた一致するブロックのサイズに依存し、また、符号化する必要があるリテラルの個数及び分布にも依存する。一般に、試験的圧縮(trial compression)が、伸張時において必要とされる命令サイクル数を検出する唯一の信頼することができる方法と考えられている。
【0046】
そこで、図6a〜図6cを参照すると、図6aは、圧縮されるデータの4つの(当初)等しいサイズのブロック200を示している。各ブロックは、圧縮プロセスを受け、(プロセスの途中の或る時刻において)既に圧縮された各ブロックの網掛け部分及びまだ圧縮されていない網掛けされていない部分によって模式的に示されている。4つのブロックの圧縮プロセスは、並列に実行することができるが、実際には、これは、圧縮時には必要ではない。
【0047】
4つのブロックを圧縮する際の相対的な進行度は、各ブロックのコンテンツの性質に依存し、具体的には、圧縮がどれだけ容易であるのかに依存する。図6bでは、ブロックの境界が移動された場合に、変更されたブロック200’の進行度が、はるかに一様なものとなっており、図6cのさらなる小さな移動(ブロック200”)によって、さらにより一様な進行度が与えられることが分かる。
【0048】
しかし、一様に近づけるべきものは、圧縮時間でもなければ、圧縮データの量でもない。一様にすべきものは、伸張時間、すなわち、より正確には、データを伸張するのに必要とされる命令サイクル数である。これを行うことによって、伸張時の並列プロセスのすべてが同時に開始して終了する。もちろん、正確な一様性が必要とされるわけではなく、合理的にできるだけ可能な一様性を得ることが目的とされているにすぎない。
【0049】
このポイントを示すために、図7は、ちょうど説明したような並列圧縮技法を示す模式的なフローチャートである。
【0050】
ステップ300において、ソースマテリアル(圧縮されるデータ)を、2つ以上の隣接したデータブロックに分割する。最初に、これは、等しいブロックサイズに基づいた分割とすることができるが、ソースマテリアルの統計的解析に基づいたサイズの重み付けを導入することが可能である。
【0051】
ステップ310において、各ブロックを、上述した技法の1つを使用して圧縮符号化する。
【0052】
ステップ320において、各符号化ブロックを復号(伸張)するのに必要とされる処理ステップ(命令サイクル)の個数を検出する。これは、符号化データの統計的解析(たとえば、リテラル又は符号対のような各データアイテムが必要とする命令サイクルがどれだけあるのかの知識に基づいて、リテラルがどれだけあるのか、リテラルの連続した群の長さ、符号対がどれだけあるのか等)により導出することもできるし、実際の試験的伸張により導出することもできる。
【0053】
ステップ330において、伸張処理所要量(decompression processing requirements)がブロック間で均一に分散されているか否かについての検出を行う。ここで、当業者は、「均一」は、「正確に均一」又は場合によっては「(たとえば)2%以内までで均一」を意味することができることを認識するであろう。
【0054】
分散が(定義されように)均一である場合には、プロセスは終了し、(ステップ310において既に圧縮されたような)ブロックは、その個数の伸張プロセッサを使用する並列伸張用に適切に圧縮されている。一方、分散が(定義されたように)均一でない場合には、ブロック境界を、ステップ340において移動する。伸張するのにより多くの処理を必要としたブロックはより小さくされ、逆もまだ同様に行われる。ブロックサイズの変更は、伸張処理所要量の差に比例したものとすることができる。そこで、たとえば、4ブロックシステムでは、処理所要量(100に正規化)が以下の通りである場合には、
【0055】
【表1】
【0056】
ブロックAのサイズは、1/11だけ削減され、ブロックCのサイズは、同じ量だけ増加される。これは、ブロックBのブロックサイズを同じに保ちながら、ブロックBの先頭境界及び終端境界の双方が移動することをおそらく意味する。(この例では)境界のこの変更のみがデータコンテンツに影響を与えることができ、したがって、ブロックBを伸張するための処理所要量に影響を与えることができるので、サイズが変更されたブロックだけでなく、4つのすべてのブロックをステップ310において再び処理することが適切である。
【0057】
伸張時には、各ブロックは並列に伸張される。たとえブロックサイズ(及び各ブロックの圧縮データのサイズ)がおそらく異なっていようとも、意図するものは、ブロック伸張プロセスがすべて同時に(又はほぼ同時に)開始して終了することである。図8は、ほぼ半分過ぎた時点でのこのような並列伸張技法を模式的に示している。各ブロックの伸張の開始点は、インジケータデータ(図示せず)によって示される。各圧縮ブロック210は、伸張されて、元のブロック200に戻されており、これまでの進行度は、既に伸張されたデータを表す網掛け部分によって示されている。
【0058】
図9a〜図9cは、各ブロックの最初の1つ又は複数の復号文字に関する並列伸張技法の特徴を模式的に示している。詳細には、図4の伸張技法が使用される場合、ステップ130によって書き出された16文字のブロックのオーバーラップを伴った問題が存在する可能性がある。
【0059】
この問題は、ブロックが、それよりも大きなソースデータセットの隣接したセクションを表すことから生じる可能性がある。それらのブロックは、伸張されるとき、メモリの隣接したエリアに記憶される可能性がある。これは、或るブロックの伸張の終端における最後に書き込まれた16文字群が、次のブロックの先頭における既に伸張された有効なデータに上書きされる可能性があることを意味し得る。
【0060】
図9aは、2つ出力ブロック220、230のみを模式的に示している。伸張プロセスは、(描かれた)ブロックの左端から右に向かって進行する。ブロック220の終端部分及びブロック230の先頭部分のみが示されている。
【0061】
最初の16文字群が、ステップ130によってブロック230内に書き込まれる。これらの文字のいくつかは有効でない可能性があるが、少なくとも正に最初の文字が有効であることは事実である。ブロック230の伸張は、出力ポインタ(上記ステップ150の説明を参照)が前方に移動して、ブロック230の16番目の文字を超えるまで続く。その時点で、ブロック230最初の16文字の全体(網掛け群232によって図9aに示される)が有効であることは事実である。その16文字群は、出力バッファとは別個のストア234へコピーされる。
【0062】
伸張は、その後、上述したように進行する。ブロック220の伸張の終了に向かうにつれて(実際には、伸張はすべて、伸張プロセスのすべての終了に向かうにつれて、同時に終了する)、16文字の最終ブロックが、ステップ130によって書き込まれる。これは、図9bに網掛けエリア236として模式的に示されている。データ236は、2つのブロックの境界にまたがっていることが分かる。ブロック220内に含まれる群236の文字は、もちろん、有効なデータである。境界を越えて含まれる文字、すなわち、ブロック230内の文字は、無効な文字であり、ステップ130のコピーオペレーションのアーティファクトである。しかし、これらは、ブロック230の先頭部分が伸張された時に、前に書き込まれた有効なデータに上書きされる。
【0063】
解決法は、先行ブロック220の伸張が完了した後に、ブロック230の最初の16個の文字内に、記憶されたデータ232を再書き込みすることである。
【0064】
先行ブロック220の最後に書き込まれた16文字群の少なくとも1つの文字は、その先行ブロック220内に含まれなければならないので、先行ブロックの伸張によって破損したあらゆるデータを元に戻すことを確実にするには、厳密には、各ブロックの最初の15文字のみを保存することが必要であることが認識されよう。しかし、本システムは、16文字データワードを効率的にハンドリングするように設計されているので、16文字群232が保存される。
【0065】
図10は、上述した並列伸張技法を示す模式的なフローチャートである。このプロセスは、ソースデータが2つ以上の隣接したブロック内に圧縮されているものと仮定するが、図7に関して説明した並列オペレーションの効率性改善は、図10の方法が有用となるための要件ではない。
【0066】
ステップ300において、各ブロックの伸張を開始する。16個の有効な文字を伸張すると(たとえば、出力ポインタが16番目の文字を過ぎることによって示される)、ステップ310において、最初の16個の伸張文字群を保存する。すなわち、別個のメモリエリアに記憶する。
【0067】
ステップ320において、伸張は、各ブロックの終端に続く。
【0068】
最後に、ステップ330において、各ブロックの先頭からの保存された16文字を、それらの元の位置へ再書き込みする。
【0069】
明らかに、この対策は、必ずしも、特定のソースマテリアルから導出された隣接したブロックのセットの最初のブロックについて行う必要はない。しかし、各ブロックについて同じ処理を使用すること、すなわち、最初のブロックについてもこれらのステップを実行することは並列システムにおいてより簡単なものとなり得る。
【0070】
最後に、図11は、データ圧縮及び/又は伸張装置の模式図である。
【0071】
この装置は、図を明確にするために簡単化した形態で示されている。当業者は、他のルーチンコンポーネントが必要とされる場合があることを認識するであろう。
【0072】
この装置は、データメモリ400(たとえば、圧縮データ又は伸張データを保持する検索バッファ及び出力バッファを記憶する)、プログラムメモリ410、中央処理装置(CPU)420(セルマイクロプロセッサ等)、並びに入力/出力ロジック430を備える。これらはすべて、バス440を介して相互接続されている。
【0073】
この装置は、CPU420がプログラムメモリ410に記憶されているプログラムコードを実行することによって、上述したオペレーションを実行する。このようなプログラムコードは、ディスク媒体450等の記憶媒体から得ることもできるし、場合によってはインターネット若しくは別のネットワーク470を介したサーバ460へのデータ接続等の伝送媒体によって得ることもできるし、他の既知のソフトウェア配布手段若しくはコンピュータプログラム製品によって得ることもできる。
【0074】
もちろん、代替的に、図11の機能は、注文ハードウェアによって達成することもできるし、ASIC(特定用途向け集積回路)又はFPGA(フィールドプログラマブルゲートアレイ)等のセミプログラマブルハードウェアによって達成することもできることが認識されよう。
【0075】
本明細書では、添付図面に関して、本発明の例示の実施形態を詳細に説明してきたが、本発明は、それらの正確な実施形態に限定されるものではないこと、並びに添付の特許請求の範囲によって規定されるような本発明の範囲及び精神から逸脱せずに、当業者は、さまざまな変更及び修正を実施形態において行うことができることが理解されるべきである。
【図1A】
【図1B】
【図1C】
【図2A】
【図2B】
【図2C】
【図2D】
【図3A】
【図3B】
【特許請求の範囲】
【請求項1】
前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、
復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
を備える圧縮データに作用するように構成されるデータ伸張装置であって、
該装置は、
出力メモリエリア、
伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び
前に復号されたデータの次の参照される群又は前記直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを前記出力メモリエリアへコピーするためのデータコピー器、
を備える、装置。
【請求項2】
前記データコピー器は、
前記出力メモリエリアへ既に書き込まれた有効に伸張されたデータの範囲を示す、前記出力メモリエリアに関するポインタを維持し、
前記参照される群のサイズ又は前記個数nに関わらず、m個の連続したデータアイテムの群をコピーし、且つ
前記参照される群のサイズ又は前記個数nに応じて前記ポインタを設定する、
ように構成される、請求項1に記載の装置。
【請求項3】
前記伸張されるデータは、2つ以上の隣接したデータブロックのシリーズを含み、前記装置は、
前記出力メモリエリアとは別個のデータストアであって、前記シリーズにおける少なくとも最初のブロック以外のブロックに対応する最初に伸張されたデータアイテムの群を記憶するためのデータストアを備え、該データストアは、前記シリーズにおける先行ブロックの伸張が完了した後に、前記記憶されたデータアイテムの群をその元の位置へ再書き込みするように構成される、請求項1に記載の装置。
【請求項4】
前記ブロックは、各ブロックが実質的に同じ量の伸張処理を必要とするようにサイズを構成される、請求項3に記載の装置。
【請求項5】
前記ブロックは、並列に伸張される、請求項4に記載の装置。
【請求項6】
前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、
復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
を備える圧縮データに作用するように構成されるデータ伸張方法であって、
該方法は、
伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出するステップ、及び
前に復号されたデータの次の参照される群又は前記直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするステップ、
を含む、方法。
【請求項7】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化されるデータ圧縮方法であって、該方法は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして生成するステップを含む、データ圧縮方法。
【請求項8】
コンピュータによって実行されると、請求項7に記載の方法を該コンピュータに実行させるプログラムコードを含むコンピュータソフトウェアが記憶されているマシン可読媒体。
【請求項9】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化されるデータ圧縮装置であって、該装置は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして生成するように構成される、データ圧縮装置。
【請求項10】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化される、データ圧縮プロセスによって生成されるデータ信号であって、該データ信号は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして含む、データ信号。
【請求項1】
前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、
復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
を備える圧縮データに作用するように構成されるデータ伸張装置であって、
該装置は、
出力メモリエリア、
伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出する検出器、及び
前に復号されたデータの次の参照される群又は前記直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを前記出力メモリエリアへコピーするためのデータコピー器、
を備える、装置。
【請求項2】
前記データコピー器は、
前記出力メモリエリアへ既に書き込まれた有効に伸張されたデータの範囲を示す、前記出力メモリエリアに関するポインタを維持し、
前記参照される群のサイズ又は前記個数nに関わらず、m個の連続したデータアイテムの群をコピーし、且つ
前記参照される群のサイズ又は前記個数nに応じて前記ポインタを設定する、
ように構成される、請求項1に記載の装置。
【請求項3】
前記伸張されるデータは、2つ以上の隣接したデータブロックのシリーズを含み、前記装置は、
前記出力メモリエリアとは別個のデータストアであって、前記シリーズにおける少なくとも最初のブロック以外のブロックに対応する最初に伸張されたデータアイテムの群を記憶するためのデータストアを備え、該データストアは、前記シリーズにおける先行ブロックの伸張が完了した後に、前記記憶されたデータアイテムの群をその元の位置へ再書き込みするように構成される、請求項1に記載の装置。
【請求項4】
前記ブロックは、各ブロックが実質的に同じ量の伸張処理を必要とするようにサイズを構成される、請求項3に記載の装置。
【請求項5】
前記ブロックは、並列に伸張される、請求項4に記載の装置。
【請求項6】
前に復号されたデータアイテムの群の参照子の順序付けられたストリーム、
復号されるデータアイテムの直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
を備える圧縮データに作用するように構成されるデータ伸張方法であって、
該方法は、
伸張オペレーションが直接的表現に作用すべきであることを示す個数nの連続したフラグを検出するステップ、及び
前に復号されたデータの次の参照される群又は前記直接的表現の順序付けられたストリームからのn個の連続した直接的表現の群のいずれかを出力メモリエリアへコピーするステップ、
を含む、方法。
【請求項7】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化されるデータ圧縮方法であって、該方法は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして生成するステップを含む、データ圧縮方法。
【請求項8】
コンピュータによって実行されると、請求項7に記載の方法を該コンピュータに実行させるプログラムコードを含むコンピュータソフトウェアが記憶されているマシン可読媒体。
【請求項9】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化されるデータ圧縮装置であって、該装置は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして生成するように構成される、データ圧縮装置。
【請求項10】
入力データアイテムが、前に符号化されたデータアイテムの群の参照子として又は前記入力データアイテムの直接的表現としてのいずれかで符号化される、データ圧縮プロセスによって生成されるデータ信号であって、該データ信号は、
参照子の順序付けられたストリーム、
直接的表現の順序付けられたストリーム、及び
各連続的な伸張オペレーションが参照子に作用すべきであるのか、又は直接的表現に作用すべきであるのかを示すフラグの順序付けられたストリーム、
の、出力データの別個のストリームとして含む、データ信号。
【図4】
【図5A】
【図5B】
【図5C】
【図5D】
【図6A】
【図6B】
【図6C】
【図7】
【図8】
【図9A】
【図9B】
【図9C】
【図10】
【図11】
【図5A】
【図5B】
【図5C】
【図5D】
【図6A】
【図6B】
【図6C】
【図7】
【図8】
【図9A】
【図9B】
【図9C】
【図10】
【図11】
【公開番号】特開2010−68511(P2010−68511A)
【公開日】平成22年3月25日(2010.3.25)
【国際特許分類】
【外国語出願】
【出願番号】特願2009−168779(P2009−168779)
【出願日】平成21年7月17日(2009.7.17)
【出願人】(502070679)ソニー コンピュータ エンタテインメント ヨーロッパ リミテッド (40)
【Fターム(参考)】
【公開日】平成22年3月25日(2010.3.25)
【国際特許分類】
【出願番号】特願2009−168779(P2009−168779)
【出願日】平成21年7月17日(2009.7.17)
【出願人】(502070679)ソニー コンピュータ エンタテインメント ヨーロッパ リミテッド (40)
【Fターム(参考)】
[ Back to top ]