(57)【要約】【課題】処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための方法及び装置を提供する。【解決手段】圧縮データは、トーク・データのストリームを入力として受け入れることによって可変且つ未知の長さのトークンによって表される。本発明は、トークン・データからトークンを部分的にデコードしてトークンの境界位置を決定し、そのトークンと境界位置を表す長さマーカとを処理パイプラインに事前通知することによるものである。更に、リテラル・データが検出され、直接に出力される。コピー・ポインタがそれらのターゲットを見つけるためにチェックされ、ヒストリ・バッファから又はパイプラインの処理中のコンテンツから解決される。【選択図】　図１
2004021992.tif 000002
【特許請求の範囲】
【請求項１】
処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための方法であって、前記圧縮データは可変且つ未知の長さのトークンによって表され、
トークン・データを含む入力として前記ストリームを受け入れるステップと、
前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するステップと、
前記トークンと前記境界位置を表す長さマーカとを前記処理パイプラインに事前通知するステップと、
を含む方法。
【請求項２】
前記処置パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処置パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するステップと、
前記決定するステップに応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするステップと、
前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るステップと、
を更に含む、請求項１に記載の方法。
【請求項３】
前記トークンのうち、コピー・ポインタを表すとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するステップと、
コピー・ポインタが前記処理パイプラインにおいて前記トークンを指示することを指示トークンにおいて決定したことに応答して、前記コピー・ポインタを前記被指示トークンでもって置換するステップと、
を更に含む、請求項２に記載の方法。
【請求項４】
前記被指示トークンを、それの指示されたデータでもって置換するステップと、
前記指示されたデータを出力手段に送るステップと、
を更に含む、請求項３に記載の方法。
【請求項５】
処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための装置であって、前記圧縮データは可変且つ未知の長さのトークンによって表され、
トークン・データを含む入力として前記ストリームを受け入れるための第１ロジック手段と、
前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するための第２ロジック手段と、
前記トークンと前記境界位置を表す長さマーカを前記処理パイプラインに事前通知するための第３ロジック手段と、
を含む装置。
【請求項６】
前記処置パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処置パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するための第４ロジック手段と、
前記第４ロジック手段に応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするための第５ロジック手段と、
前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るための第６ロジック手段と、
を更に含む、請求項５に記載の装置。
【請求項７】
前記トークンのうち、コピー・ポインタを表すとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するための第７ロジック手段と、
コピー・ポインタが前記処理パイプラインにおける前記トークンを指示していることを被指示トークンにおいて決定したことに応答して、前記コピー・ポインタを前記被指示トークンでもって置換するための第８ロジック手段と、
を更に含む、請求項６に記載の装置。
【請求項８】
前記被指示トークンを、それの指示されたデータでもって置換するための第９ロジック手段と、
前記指示されたデータを出力手段に送るための第１０ロジック手段と、
を更に含む、請求項７に記載の装置。
【請求項９】
前記ロジック手段のうちのいずれかが１つ又は複数のプロセッサ・コンポーネントを含む、請求項６乃至８のいずれか１つに記載の装置。
【請求項１０】
前記１つ又は複数のプロセッサ・コンポーネントが１つ又は複数のアプリケーション特有の集積回路を含む、請求項９に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ圧縮解除に関し、特に、「ＬＺ１」データ圧縮解除に関するものである。
【０００２】
【従来の技術】
レンペル・ジフ（Ｌｅｍｐｅｌ−Ｚｉｖ）アルゴリズムは、データ圧縮の分野では周知である。詳しく云えば、ＬＺ１として知られた「ヒストリ・バッファ」バージョンは、コード化データの無損失圧縮がどこで必要とされようとも、ハードウェア・インプリメンテーションにおいて特に人気のあるものになっている。これは、それの比較的中庸なバッファ要件及び予測可能なパフォーマンスがほとんどのテクノロジに対してそれを良好に適合させるためである。
【０００３】
ＬＺ１アルゴリズムは、文字の入力ストリングを調べること及びそれが知っている文字のレコードを保持することによって作用する。そこで、その前の最近のヒストリにおいて生じたストリングが現れるとき、それは、出力ストリングにおいて、「トークン」、即ち、過去においてそのストリングが何処で及びどのくらい長く生じたかを表すコード、によって置換される。圧縮装置及び圧縮解除装置のいずれも、或る定義された長さの「ヒストリ・バッファ」を使用しなければならないが、その点を除けば、それ以上の情報がそれらの間で伝送される必要がない。
【０００４】
有益なストリングにおいて事前に見たことがない文字は、圧縮時に「リテラル（ｌｉｔｅｒａｌ）」としてコード化される。これは、必要なビットの数の拡大になるが、ほとんどのタイプのデータでは、トークンによる代用（従って、圧縮）の機会が圧縮不能なデータにまさっているので、全体的な圧縮が得られる。代表的な圧縮比は、２：１から１０：１の範囲に及ぶ。
【０００５】
基本的なＬＺ１アルゴリズムの或る変種がここ数年にわたって出現しているが、改良が増えている。
【０００６】
ＬＺ１アルゴリズムはバイト単位で作用するので、伝統的なハードウェア・インプリメンテーションは、入力ストリームを圧縮解除するとき、一時に１バイトしか考慮しない。
【０００７】
ＬＺ１圧縮データは、圧縮解除データを生じさせるためには各々が順次デコードされなければならない可変長トークンのストリームから成る。その圧縮データのストリームにおけるトークンは、１バイトのデータを含むリテラルであるか、又は複数バイトのストリングを指定するコピー・ポインタであってもよい。なお、それら複数バイトのストリングは、既に圧縮解除され且つこの目的でヒストリ・バッファに保持されている最新のバイトを参照することによって得ることができる。
【０００８】
伝統的な１バイトのハードウェア圧縮解除の場合、各サイクルにおいて１つの入力トークンしか考慮される必要がない。リテラルは、１サイクルで完全にデコードされ、一方、コピー・ポインタは、デコードのために複数サイクルを必要とする。各サイクルにおいて、厳密に１バイトの圧縮解除データが生じる。
【０００９】
ハードウェア圧縮解除のパフォーマンスを高めるためには２つの代替え方法、即ち、サイクル・タイムを小さくするためのものと、１サイクル当たり更に多くの圧縮解除バイトを生じさせるためのものとが存在する。それら２つのオプションのうちの容易な方は、サイクル・タイムを小さくするように作用するけれども、一般的には、単に、パフォーマンスのわずかな改良が得られるだけである。試行されたマルチバイト方式のものはすべてかなり複雑な設計になるが、単一バイトの場合のパフォーマンスの数倍のパフォーマンスを提供することができるという利点を持っている。以前に試みられた唯一のマルチバイト・ハードウェアＬＺ１の実施事例である、米国特許第５，７７１，０１１号及びそれの分割米国特許第５，９２９，７９１号のものは、本来、１サイクル当たり２バイトに限定されていた。
【００１０】
【発明が解決しようとする課題】
マルチバイト・ハードウェア圧縮解除と関連した問題点は、圧縮された入力データ・ストリームの次のような特性から生じる：
１．入力トークンが１から２７１までの可変数のバイトを生じる。
２．入力トークンは、可変長（９、１２、１４、１６、１８又は２２ビット）である。
【００１１】
オペレーションを幾つかの段階にパイプライン化することによってマルチバイト圧縮解除を可能にすることが望ましい。しかし、データの性質上、次のような問題が生じる：
１．例えば、１２バイトの出力を生じさせるため、如何に多くの入力トークンが必要であるかが、容易にはわからない。例えば、１２バイトは、１２個のリテラル・トークンから、又は１２個以上のバイトを含む１つの長いトークンの部分から生じ得る。１サイクルにおいて如何に多くのトークンが処理されたかを知ることなく、次のサイクルを開始することはできない。
２．トークンが可変長であるため、１サイクルで入力データから次の１２個のトークンを取り出すことは不可能である。第１インスペクションにおいて、次のサイクルが正しい位置で入力ストリームを処理できるように入力ストリームから如何に多くのデータが使用されたかを知るためには、これを行うことが必要であると思われる。
３．１２バイトのグループをデコードするとき、１つのコピー・ポインタ・トークンからデコードされるというプロセスにあって未知の値を有する１つ又は複数の前のバイトを指示するコピー・ポインタ・トークンからその後のバイトの１つを生じさせることが可能である。
【００１２】
ＬＺ１圧縮データのハードウェア圧縮解除のパフォーマンスを高めるためには、上記の問題点を克服すると共に１サイクル当たり複数のバイトを処理することが望ましい。
【００１３】
【課題を解決するための手段】
従って、本発明は、第１の局面では、処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための方法を提供する。なお、前記圧縮データは、可変且つ未知の長さのトークンによって表される。その方法は、トークン・データを含む入力として前記ストリーム受け入れるステップと、前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するステップと、前記トークンと前記境界位置を表す長さマーカとを前記処理パイプラインに事前通知するステップとを含む。
【００１４】
望ましくは、第１の局面の方法は、更に、前記処理パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処理パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するステップと、前記決定するステップに応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするステップと、前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るステップとを含む。
【００１５】
望ましくは、第１の局面の方法は、更に、前記トークンのうち、コピー・ポインタを表すものとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するステップと、コピー・ポインタが前記処理パイプラインにおける前記トークンを指示していることを被指示トークンにおいて決定したことに応答して前記コピー・ポインタを前記被指示トークンでもって置換するステップとを含む。
【００１６】
望ましくは、第１の局面の方法は、更に、前記被指示トークンをそれの指示されたデータでもって置換するステップと、前記指示されたデータを出力手段に送るステップとを含む。
【００１７】
第２の局面では、本発明は、処理パイプラインを使用して圧縮されたデータのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための装置を提供する。なお、前記圧縮データは、可変且つ未知の長さのトークンによって表される。前記装置は、トークン・データを含む入力として前記ストリームを受け入れるための第１ロジック手段と、前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するための第２ロジック手段と、前記トークンと前記境界位置を表す長さマーカとを前記処理パイプラインに事前通知するための第３ロジック手段とを含む。
【００１８】
望ましくは、第２局面の前記装置は、更に、前記処理パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処理パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するための第４ロジック手段と、前記第４ロジック手段に応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするための第５ロジック手段と、前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るための第６ロジック手段とを含む。
【００１９】
望ましくは、第２局面の前記装置は、更に、前記トークンのうち、コピー・ポインタを表すとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するための第７ロジック手段と、コピー・ポインタが前記処理パイプラインにおける前記トークンを指示していることを被指示装置において決定したことに応答して、前記コピー・ポインタを前記被指示トークンでもって置換するための第８ロジック手段とを含む。
【００２０】
望ましくは、第２の局面の装置は、更に、前記被指示トークンをそれの指示されたデータでもって置換するための第９ロジック手段と、前記指示されたデータを出力手段に送るための第１０ロジック手段とを含む。
【００２１】
望ましくは、第２の局面の装置は、前記ロジック手段のうちのいずれかが１つ又は複数のプロセッサ・コンポーネントを含む装置である。
【００２２】
望ましくは、第２の局面の装置は、前記１つ又は複数のプロセッサ・コンポーネントが１つ又は複数のアプリケーション特有の集積回路を含む装置である。
【００２３】
【発明の実施の形態】
中心部においてトークンＦＩＦＯ（１０６）を有するパイプライン（１００）を使用する本発明の望ましい実施例では、圧縮解除における改良されたパフォーマンスが得られる。その望ましい実施例では、パイプライン（１００）における各ステージにおいて行われるべきオペレーションは、設計の幅を最大にするように選択されている。本発明の望ましい実施例は、任意の選択された設計幅にスケーラブルであり、従って、本発明の範囲は、如何なる特定の設計幅にも限定されるものではない。
【００２４】
本発明の望ましい実施例では、パイプラインは、説明の便宜上、４つのステージに分割されている。しかし、それらステージの各々が、全体として望ましい結果を全パイプライン・ステージから得るに必要なサブ・オペレーションに従って複数の部分に更に細分割可能であるということは、当業者には容易に明らかであろう。
【００２５】
本発明の１つの望ましい実施例は、各サイクル毎に１２バイトを生成するが、その実施例は容易に拡張可能であり、単に、使用可能な基礎的テクノロジ及びサイクル・タイムの制約によって限定されるだけである。
【００２６】
本発明の望ましい実施例は、次のようなセクションを含むパイプライン（１００）から成る：
１．アライン及びスプリット（１０４）
２．ＦＩＦＯ（１０６）
３．デコード（１０８）
４．ヒストリ・バッファ・ルックアップ（１１０）
【００２７】
或るトークンは、多くの出力バイトを生じさせるようにデコードし得るし、一方、別のものは、単に１つの出力バイトしか生じないようにデコードする。１つのサイクルにおいて如何に多くのトークンが使用されるかが事前には判らないということに関連した問題を克服するために、ＦＩＦＯ（１０６）が使用される。１２バイト設計を使用する１つの実施例では、ＦＩＦＯ（１０６）のタスクは、１２個のトークンが、たとえそれらがすべて使用されなくても、各サイクル中の処理のために使用可能であることを保証することである。次のロジックは、各サイクル毎に正確に１２個の出力バイトを生じるようにこれらのトークンのサブセットをデコードする。それは、如何に多くのトークンが使用され、次のサイクル前にこれらがＦＩＦＯ（１０６）から廃棄され得るかを表すために、ＦＩＦＯロジックにフィードバックする。
【００２８】
ＦＩＦＯ（１０６）の入力側において、そのロジックは、それが１サイクルで最小１２個のトークン（１０２）をＦＩＦＯ（１０６）に加えることができるように構成される。１サイクルでＦＩＦＯ（１０６）から除去可能なトークンの最大数が１２であるので、これは、ＦＩＦＯ（１０６）がアンダーランしないことを保証する。一方、ＦＩＦＯ（１０６）の出力において大きなトークン（１０２）が処理されようとしている場合、入力ロジックは、それがＦＩＦＯ（１０６）の入力により多くのトークンを加える機会を持つ前に、数サイクルの間一時停止しなければならない。
【００２９】
そのようなＦＩＦＯを持つことは、デコーディング・プロセスが、独立して解決可能な２つの別個のセクションに分離されることを可能にする。本発明の望ましい実施例の第１セクションは、入力データ・ストリームを揃えてそれを個別のトークンに分離し、第２セクションがこれらのトークンをデコードする。
【００３０】
この第１セクションの仕事、即ち、アライン及びスプリット（１０４）は、個々のトークン（１０２）を、それらがＦＩＦＯ（１０６）に置かれる順序で入力ストリームから分離することである。この望ましい実施例では、このセクションは、３つの個別のパイプライン化されたステージに分離される。それは、トーク（１０２）が１サイクルで個々のトークンに完全に分けられた場合、それに取られる時間がずっと長くなるであろうし、従って、１つのサイクルで生じ得るトークンの最大数が小さくなるためである。パイプライン化されたステージの数が多数の実現可能な代替え実施例の間の設計選択事項であること、及び多くの変更が当業者にとって容易に明らかであることは当業者が認めるところであろう。
【００３１】
１２個の出力バイトを生じさせるために必要な入力ビットの最大数は、入力トークンがリテラルである（従って、各々が９ビットによって表される）ときに生じ、１０８ビット（１２＊９）になり、従って、入力データ幅は、少なくともこれでなければならない。現時点で望ましい実施例では、２ビット左を過剰にさせた場合でも精々１４個のトークンしか生じ得ない１２８ビットの入力データ幅を有することが都合よい。しかし、これが多くの代替え方法の間の設計選択事項であること、及び、同様の望ましい実施例が、基礎となるハードウェア及びシステム編成次第で更に多くの又は更に少ないビットに適応し得ることは、当業者が認めるところであろう。
【００３２】
トークン（１０２）を揃えるプロセスの第１ステージは、設計の最大幅を限定するのがこのステージであるので、重要なステージである。このステージは、入力データを調べ且つ何処にトークン境界があるかを決定しなければならない。それは、何処に最後のトークン境界があるかを憶えておかなければならず、しかも、入力データ・ストリームにおける次の１２８ビットに対してこれらのビットが準備される次のサイクルまで、次のトークンの第１部分を形成する残りのビットを保存しなければならない。このステージの出力は、最長のトークンが２２ビットであり、従って、次のサイクルに搬送するための最長の部分的トークンは２１ビットであるので、最大１４９ビット（１２８＋２１）である。前の部分的トークンのプリペンド（ｐｒｅｐｅｎｄ）のために、このステージの出力がトークン境界においてスタートすることは知られている。
【００３３】
図２及び図３は、着信データ（図２）及び最終ビットのアレー（図３の２１４）を示し、それは、トークン境界を決定しそしてマークを付すプロセスにおいて使用される。トークンｎとして図２に示された第１トークンでもってスタートすると、結合ロジックが、そのトークンにおける最初の数ビットをデコードすることによって、そのトークンの長さを決定するために使用される。最終ビットのアレー（２１４）における入力トークンの最終ビットに対応するビットが１にセットされる。このビットがセットされるということは、同様に次のトークンからの分離を可能にするであろう。その後の各トークンの分離が前のトークンの分離に依存するので、このプロセスは、それらのトークンを通して伝播する。次のサイクルのための入力を提供するためにはデータが何処で分離されるべきかを知るためにプロセスを丁度よい時に完了することが可能になるのは、単に最も少ない作業を行うことによる。
【００３４】
従って、例えば、図２におけるトークンｎが入力におけるビット位置ｐにおいてスタートする場合、最終ビット（ｐ−１）は前のデコードによってセットされているであろう。これは、トークンｎにおける最初の数ビットを、それの長さを算出するためにデコードすることを可能にするであろう。これは、最終ビットのアレーにおいて正しいビットをセットするために、この場合、トークンｎが１８ビットの長さであるので、ｐ＋１７をセットするために、使用されるであろう。そこで、これは、次のトークン、この場合、９ビットのリテラル等のデコードを可能にするであろう。次のサイクルのための残っている部分的トークンのサイズは、最終ビットのアレーの終わりから逆走査すること、及び１に遭遇する前に見つかったゼロの数をカウントすることによって見つけることが可能である。
【００３５】
見つかったトークンの数のカウントは、その後のステージにおいて使用するための出力でもある。本発明の望ましい実施例のインプリメンテーションにおいて、当業者には容易に明らかであるように、パイプライン（１００）の更に多くのステージが必要に応じて使用可能であるけれども、個々のトークンを完全に分離するためには更に２ステージのパイプライン（１００）が必要である。
【００３６】
トークンの完全なデコードは、更に２ステージのパイプライン（１００）を必要とする。
【００３７】
これらのステージの第１ステージは、生じる１２バイトの出力データの各々に対して１つの出力トークンが存在するように、トークンを部分的にデコードする。これらの部分的にデコードされたトークンは、そのトークンがリテラルであるか又はコピー・ポインタであるを表すための１つのビット、及びリテラル又はヒストリ・バッファまでの変位である第２フィールドを有する。図４は、入力トークン（３０２）と部分的にデコードされたトークン（３０８、３１２、３１６、３２０）との間の関係を示す。
【００３８】
これらのステージの第２ステージは、コピー・ポインタ・トークンの１つにおける変位が、デコードされる１２個のトークンにおける早期のトークンを指すという場合を扱う。これがその場合であるとわかると、トークンは、それが指示する初期のトークンの値でもって代用される。これはリテラルであるか、又はヒストリ・バッファに対するポインタである。それが１２バイトにおける他のどこかに対するポインタである場合、それは、既に代用されているであろう。これは、このデコード・ステージ（１０８）の出力において、すべての部分的にデコードされたトークンがリテラルであるか、又は前のサイクルからのヒストリ・バッファに対する参照であることを意味する。即ち、デコードされる１２バイト内の他のバイトに対する参照はあり得ない。
【００３９】
ヒストリ・バッファ・ルックアップ・ステージ（１１０）に対する入力には、１２個の部分的にデコードされたトークンがある。何らかのリテラルが出力（１１２）にそのまま送られ得るし（トークンがリテラルであることを表したビットなしに）、一方、コピー・ポインタ・トークンは、ヒストリ・バッファから正しいバイトを選択するマルチプレクサ（１２個の可能なトークンの各々に対して１つ）によってヒストリ・バッファにおいてルックアップされる。
【００４０】
従って、ＬＺ１圧縮解除データが、本発明の望ましい実施例のパイプラインから出力される。
【００４１】
本願において開示された望ましい実施例が、利用い得る可能な経済的及び効率的実施例の１つの例を表すということは、当業者には明らかであろう。例えば、１２バイトの設計幅が指定されている場合、その設計幅が、基礎となるハードウェア及びシステム構成の利用可能な処理能力の関数であること、及び更に大きい設計幅を処理するように設計をスケール・アップすることが現在及び将来のいずれのテクノロジによっても実現可能であることは明らかであろう。
【００４２】
並行処理及び他の最適化の更なる活用が本発明に関して容易に意図される変更の範囲内であることも当業者には明らかであろう。
【００４３】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４４】
（１）処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための方法であって、前記圧縮データは可変且つ未知の長さのトークンによって表され、
トークン・データを含む入力として前記ストリームを受け入れるステップと、
前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するステップと、
前記トークンと前記境界位置を表す長さマーカとを前記処理パイプラインに事前通知するステップと、
を含む方法。
（２）前記処置パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処置パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するステップと、
前記決定するステップに応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするステップと、
前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るステップと、
を更に含む、上記（１）に記載の方法。
（３）前記トークンのうち、コピー・ポインタを表すとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するステップと、
コピー・ポインタが前記処理パイプラインにおいて前記トークンを指示することを指示トークンにおいて決定したことに応答して、前記コピー・ポインタを前記被指示トークンでもって置換するステップと、
を更に含む、上記（２）に記載の方法。
（４）前記被指示トークンを、それの指示されたデータでもって置換するステップと、
前記指示されたデータを出力手段に送るステップと、
を更に含む、上記（３）に記載の方法。
（５）処理パイプラインを使用して圧縮データのストリームから１プロセッサ・サイクル当たり３個以上のバイトを圧縮解除するための装置であって、前記圧縮データは可変且つ未知の長さのトークンによって表され、
トークン・データを含む入力として前記ストリームを受け入れるための第１ロジック手段と、
前記トークン・データからトークンを部分的にデコードして前記トークンの境界位置を決定するための第２ロジック手段と、
前記トークンと前記境界位置を表す長さマーカを前記処理パイプラインに事前通知するための第３ロジック手段と、
を含む装置。
（６）前記処置パイプラインにおけるいずれかのトークンがリテラル・データを表すかどうか及び前記処置パイプラインにおけるいずれかのトークンがコピー・ポインタを表すかどうかを決定するための第４ロジック手段と、
前記第４ロジック手段に応答して、リテラル・データ及びコピー・ポインタのどちらが表されるかを表示するマーカでもって各トークンをマークするための第５ロジック手段と、
前記トークンのうち、リテラル・データを表すとしてマークされたトークンから出力手段にリテラル・データを直接に送るための第６ロジック手段と、
を更に含む、上記（５）に記載の装置。
（７）前記トークンのうち、コピー・ポインタを表すとしてマークされたトークンが前記処理パイプラインにおける前記トークンを指示しているコピー・ポインタを有するかどうかを被指示トークンにおいて決定するための第７ロジック手段と、
コピー・ポインタが前記処理パイプラインにおける前記トークンを指示していることを被指示トークンにおいて決定したことに応答して、前記コピー・ポインタを前記被指示トークンでもって置換するための第８ロジック手段と、
を更に含む、上記（６）に記載の装置。
（８）前記被指示トークンを、それの指示されたデータでもって置換するための第９ロジック手段と、
前記指示されたデータを出力手段に送るための第１０ロジック手段と、
を更に含む、上記（７）に記載の装置。
（９）前記ロジック手段のうちのいずれかが１つ又は複数のプロセッサ・コンポーネントを含む、上記（６乃至８のいずれか１つ）に記載の装置。
（１０）前記１つ又は複数のプロセッサ・コンポーネントが１つ又は複数のアプリケーション特有の集積回路を含む、上記（９）に記載の装置。
【図面の簡単な説明】
【図１】本発明の望ましい実施例における４ステージ・パイプラインを表すブロック図である。
【図２】本発明の望ましい実施例におけるトークンＦＩＦＯでの圧縮データ・ストリームの一部分を示す図である。
【図３】本発明の望ましい実施例における「最終ビット」のアレーを表す図である。
【図４】本発明の望ましい実施例におけるパイプラインのデコード・ステージの第２部分に供給されるべき部分的にデコードされたトークンの導出を示す図である。
【符号の説明】
１００　パイプライン
１０２　トークン
１１２　出力
【図１】
2004021992.tif 000003
【図２】
2004021992.tif 000004
【図３】
2004021992.tif 000005
【図４】
2004021992.tif 000006