(57)【要約】【課題】ＰａｃｋＢｉｔｓエンコード処理を、プロセッサで高速に処理することは困難であった。【解決手段】プロセッサでＰａｃｋＢｉｔｓ圧縮のエンコード命令を実行するデータ圧縮方法であって、前記エンコード命令は、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を取得し、該エンコード処理状態に基づいて制御コード（＋１，−２等）の出力を制御する第１の命令と、前記エンコード処理状態に基づいて入力データ（Ａ〜Ｆ）の出力を制御する第２の命令と、ＰａｃｋＢｉｔｓ圧縮の終了時点での制御コード出力を制御する第３の命令と、を含む。【選択図】    図２
2004274509.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサでパックビッツ（ＰａｃｋＢｉｔｓ）圧縮のエンコード命令を実行するデータ圧縮方法であって、前記エンコード命令は、
ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を取得し、該エンコード処理状態に基づいて制御コードの出力を制御する第１の命令と、
前記エンコード処理状態に基づいて入力データの出力を制御する第２の命令と、
ＰａｃｋＢｉｔｓ圧縮の終了時点での制御コード出力を制御する第３の命令と、
を含むことを特徴とするデータ圧縮方法。
【請求項２】
前記プロセッサは前記第１の命令によって、
入力データとその直前データとの比較結果、及び前記直前データにおける前記エンコード処理状態に基づいて新たなエンコード処理状態を取得し、該新たなエンコード処理状態に基づいて前記制御コードの出力の可否を制御し、
該出力を行う場合には、出力ベースアドレスに基づいて前記制御コードを出力し、該出力ベースアドレスを更新する
ことを特徴とする請求項１記載のデータ圧縮方法。
【請求項３】
前記プロセッサは前記第２の命令によって、
前記新たなエンコード処理状態に基づいて、入力データの出力の可否を制御し、該出力を行う場合には、該エンコード処理状態及び前記出力ベースアドレスに基づいて出力アドレスを算出する
ことを特徴とする請求項２記載のデータ圧縮方法。
【請求項４】
前記プロセッサは前記第３の命令によって、
前記新たなエンコード処理状態に基づいて、前記制御コードを出力する
ことを特徴とする請求項２記載のデータ圧縮方法。
【請求項５】
前記エンコード処理状態は、所定範囲の値をとり得るラベルによって識別され、該ラベル値によって初期状態、リプリケイトラン（ｒｅｐｌｉｃａｔｅ  ｒｕｎ）、リテラルラン（ｌｉｔｅｒａｌ  ｒｕｎ）に対応する
ことを特徴とする請求項１記載のデータ圧縮方法。
【請求項６】
前記ラベル値は、−１２８が初期状態に、−１〜−１２７がリプリケイトランに、０〜１２７がリテラルランに、それぞれ対応する
ことを特徴とする請求項５記載のデータ圧縮方法。
【請求項７】
前記プロセッサは前記第１の命令によって、
前記入力データとして同じ値が２回連続した場合にはリテラルランとして処理を続行し、該値が３回連続した時点でリプリケイトランとして処理する
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項８】
前記プロセッサは、
前記第１の命令による制御コード出力を行わず、前記第２の命令による入力データ出力を行うことによって、リテラルランを継続する
ことを特徴とする請求項５記載のデータ圧縮方法。
【請求項９】
前記プロセッサは、
前記第１の命令による制御コード出力を行わず、前記第２の命令による入力データ出力も行わないことによって、リプリケイトランを継続する
ことを特徴とする請求項５記載のデータ圧縮方法。
【請求項１０】
前記プロセッサは、
前記エンコード処理状態のラベル値が１２７であり、入力データが直前データと異なる場合には、前記第１の命令によって制御コード＋１２７を出力し、前記第２の命令によって該入力データを次のランに対応するアドレスに出力することによって、制御コードが１２７であるリテラルランを確定させる
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項１１】
前記プロセッサは、
前記入力データとして同じ値が３回連続した時点で、前記第１の命令により制御コードを出力し、前記第２の命令による入力データの出力を行わないことによって、リテラルランを確定し、制御コードｒが−２であるリプリケイトランを継続する
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項１２】
前記プロセッサは、
１２７バイトのリテラルラン候補データの後に２バイト同じデータが入力された場合、前記第１の命令によって制御コード１２６を出力し、前記第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、制御コードが＋１２６であるリテラルランを確定し、制御コードが−１であるリプリケイトランを継続する
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項１３】
前記プロセッサは、
１２８バイト以上同じデータが連続した場合に、前記第１の命令によって制御コード−１２７を出力し、前記第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、制御コードが−１２７であるリプリケイトランを確定する
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項１４】
前記プロセッサは、
前記第１の命令によって遷移前のラベルを制御コードとして出力し、前記第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、リプリケイトランを確定する
ことを特徴とする請求項６記載のデータ圧縮方法。
【請求項１５】
前記プロセッサは、
前記第１乃至第３の命令によって出力する前記制御コード及び前記入力データの出力アドレスを、出力ベースアドレス及び前記エンコード処理状態に基づいて算出する
ことを特徴とする請求項２記載のデータ圧縮方法。
【請求項１６】
前記プロセッサは、
前記第１の命令によって取得されたエンコード処理状態を複数保持し、
該複数のエンコード処理状態から選択されたエンコード処理状態に基づく前記第１乃至第３の命令の実行を、複数のエンコード状態について並行に行う
ことを特徴とする請求項１記載のデータ圧縮方法。
【請求項１７】
前記プロセッサは、
前記入力データが逆順に入力された場合にも、該入力データが順入力された場合と同様のデータ列を出力することを特徴とする請求項１記載のデータ圧縮方法。
【請求項１８】
前記プロセッサは、
前記入力データが逆順に入力された場合に、出力ベースアドレスに対するアドレス計算のオフセット値の加減を、該入力データが順入力された場合と逆となるように制御する
ことを特徴とする請求項１７記載のデータ圧縮方法。
【請求項１９】
前記プロセッサは、
前記入力データが順入力されたか逆入力されたかによって、前記アドレス計算方法を切換える
ことを特徴とする請求項１８記載のデータ圧縮方法。
【請求項２０】
パックビッツ圧縮のエンコード命令を実行するプロセッサであって、
パックビッツ圧縮のエンコード処理状態を保持するエンコード状態保持手段と、
パックビッツ圧縮のエンコード処理状態を計算するエンコード状態計算手段と、
出力するエンコードデータのアドレスを計算する出力アドレス計算手段と、
を有することを特徴とするプロセッサ。
【請求項２１】
前記エンコード命令は、
パックビッツ圧縮のエンコード処理状態を取得し、該エンコード処理状態に基づいて制御コードの出力を制御する第１の命令と、
前記エンコード処理状態に基づいて入力データの出力を制御する第２の命令と、
パックビッツ圧縮の終了時点での制御コード出力を制御する第３の命令と、
を含むことを特徴とする請求項２０記載のプロセッサ。
【請求項２２】
前記エンコード状態保持手段は、入力データの直前データ、エンコード処理状態を示すラベル情報、及び出力ベースアドレスを保持する
ことを特徴とする請求項２０記載のプロセッサ。
【請求項２３】
前記エンコード状態計算手段は、入力データと前記エンコード状態保持手段に保持されたエンコード処理状態に基づいて、新たなエンコード処理状態及び命令動作を決定する
ことを特徴とする請求項２０記載のプロセッサ。
【請求項２４】
前記出力アドレス計算手段は、前記エンコード状態計算手段によって計算された新たなエンコード処理状態に基づいて、エンコードデータを出力すべきアドレスを計算する
ことを特徴とする請求項２０記載のプロセッサ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像・音声等のデータをプロセッサによってランレングス圧縮するデータ圧縮技術に関するものである。
【０００２】
【従来の技術】
画像や音声等のデータを処理する場合、中間データや出力データのサイズを抑えるために、処理データをランレングス方式で圧縮することがしばしば行われる。代表的なランレングス圧縮方式として、ＴＩＦＦ仕様書に記述されたＰａｃｋＢｉｔｓ圧縮が知られている。
【０００３】
このようなＰａｃｋＢｉｔｓ圧縮、あるいはランレングス圧縮は、従来、プロセッサのソフトウェアによって処理されるか、あるいは、ハードウェアで処理（例えば、特許文献１参照。）されてきた。
【０００４】
【特許文献１】
特開平９−１５４０２１号公報
【発明が解決しようとする課題】
しかしながら、ＰａｃｋＢｉｔｓ圧縮のエンコードをソフトウェアのみで処理した場合、処理速度が遅いという問題があった。すなわち、ＰａｃｋＢｉｔｓ圧縮のエンコード処理は、複数の条件判定を伴うため、プロセッサのもつ基本的な演算命令のみで処理しようとすると、高速処理ができない。したがって、処理を高速化するために、データ処理を行うプロセッサとは別にＰａｃｋＢｉｔｓ圧縮のエンコードを行う専用ハードウェアを設けると、プロセッサが外部のハードウェアにアクセスするためのオーバヘッドがかかり、例えば、細かなデータの単位で圧縮を行う等の処理フローの変更を柔軟に行うことが難しくなる。
【０００５】
また、ＰａｃｋＢｉｔｓ圧縮のエンコードを行う直前の処理のデータが、ＰａｃｋＢｉｔｓ圧縮エンコーダに入力されるべきデータの順序と逆順に出力されるような場合には、データの並べ替えを行うために処理速度が低下するばかりでなく、並べ替え用の一時的なバッファを用意する必要があった。このような状況は、画像データの左右反転処理をＰａｃｋＢｉｔｓ圧縮の直前に行う場合や、誤差拡散法等の方向性を持った画像処理を入力データ順と逆方向にかける場合に発生する。
【０００６】
本発明は、上述した課題を解決するためになされたものであり、プロセッサでＰａｃｋＢｉｔｓ圧縮のエンコードを行う際に、プロセッサとは別に専用のハードウェアを設けることなく、高速性と処理フローの柔軟性を両立させることを目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するために、本発明は、プロセッサでＰａｃｋＢｉｔｓ圧縮のエンコード命令を実行するデータ圧縮方法であって、前記エンコード命令は、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を取得し、前記エンコード処理状態に基づいて制御コードの出力を制御する第１の命令と、前記エンコード処理状態に基づいて入力データの出力を制御する第２の命令と、ＰａｃｋＢｉｔｓ圧縮の終了時点での制御コード出力を制御する第３の命令と、を含むことを特徴とする。
【０００８】
【発明の実施の形態】
本発明は、プロセッサでＰａｃｋＢｉｔｓ圧縮のエンコード命令を実行するデータ圧縮方法であって、該エンコード命令は、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を取得し、該エンコード処理状態に基づいて制御コードの出力を制御する第１の命令と、該エンコード処理状態に基づいて入力データの出力を制御する第２の命令と、ＰａｃｋＢｉｔｓ圧縮の終了時点での制御コード出力を制御する第３の命令と、を含むものである。プロセッサは第１の命令によって、入力データとその直前データとの比較結果、及び前記直前データにおける前記エンコード処理状態に基づいて新たなエンコード処理状態を取得し、該新たなエンコード処理状態に基づいて前記制御コードの出力の可否を制御し、該出力を行う場合には、出力ベースアドレスに基づいて前記制御コードを出力し、該出力ベースアドレスを更新する。またプロセッサは第２の命令によって、新たなエンコード処理状態に基づいて、入力データの出力の可否を制御し、該出力を行う場合には、該エンコード処理状態及び前記出力ベースアドレスに基づいて出力アドレスを算出する。またプロセッサは第３の命令によって、新たなエンコード処理状態に基づいて、制御コードを出力する。
【０００９】
なお、エンコード処理状態は、所定範囲の値をとり得るラベルによって識別され、該ラベル値によって初期状態、ｒｅｐｌｉｃａｔｅ  ｒｕｎ、ｌｉｔｅｒａｌ  ｒｕｎに対応しており、ラベル値−１２８が初期状態に、−１〜−１２７がｒｅｐｌｉｃａｔｅ  ｒｕｎに、０〜１２７がｌｉｔｅｒａｌ  ｒｕｎに、それぞれ対応する。
【００１０】
プロセッサは第１の命令によって、入力データとして同じ値が２回連続した場合にはｌｉｔｅｒａｌ  ｒｕｎとして処理を続行し、該値が３回連続した時点でｒｅｐｌｉｃａｔｅ  ｒｕｎとして処理する。また、第１の命令による制御コード出力を行わず、第２の命令による入力データ出力を行うことによって、ｌｉｔｅｒａｌ  ｒｕｎを継続し、第１の命令による制御コード出力を行わず、第２の命令による入力データ出力も行わないことによって、ｒｅｐｌｉｃａｔｅ  ｒｕｎを継続する。
【００１１】
プロセッサはまた、エンコード処理状態のラベル値が１２７であり、入力データが直前データと異なる場合には、第１の命令によって制御コード＋１２７を出力し、第２の命令によって該入力データを次のランに対応するアドレスに出力することによって、制御コードが１２７であるｌｉｔｅｒａｌ  ｒｕｎを確定させる。また、入力データとして同じ値が３回連続した時点で、第１の命令により制御コードを出力し、第２の命令による入力データの出力を行わないことによって、ｌｉｔｅｒａｌ  ｒｕｎを確定し、制御コードｒが−２であるｒｅｐｌｉｃａｔｅ  ｒｕｎを継続する。
【００１２】
プロセッサはまた、１２７バイトのｌｉｔｅｒａｌ  ｒｕｎ候補データの後に２バイト同じデータが入力された場合、第１の命令によって制御コード１２６を出力し、第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、制御コードが＋１２６であるｌｉｔｅｒａｌ  ｒｕｎを確定し、制御コードが−１であるｒｅｐｌｉｃａｔｅ  ｒｕｎを継続する。また、１２８バイト以上同じデータが連続した場合に、第１の命令によって制御コード−１２７を出力し、第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、制御コードが−１２７であるｒｅｐｌｉｃａｔｅ  ｒｕｎを確定する。また、第１の命令によって遷移前のラベルを制御コードとして出力し、第２の命令によって入力データを次の制御コードアドレスの次のアドレスに出力することによって、ｒｅｐｌｉｃａｔｅ  ｒｕｎを確定する。
【００１３】
プロセッサは、第１乃至第３の命令によって出力する制御コード及び入力データの出力アドレスを、出力ベースアドレス及び前記エンコード処理状態に基づいて算出する。
【００１４】
また本発明は、ＰａｃｋＢｉｔｓ圧縮のエンコード命令を実行するプロセッサであって、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を保持し、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を計算し、出力するエンコードデータのアドレスを計算する。なお、エンコード命令として、ＰａｃｋＢｉｔｓ圧縮のエンコード処理状態を取得し、該エンコード処理状態に基づいて制御コードの出力を制御する第１の命令と、該エンコード処理状態に基づいて入力データの出力を制御する第２の命令と、ＰａｃｋＢｉｔｓ圧縮の終了時点での制御コード出力を制御する第３の命令と、を含む。
【００１５】
ここで保持されるエンコード処理状態としては、入力データの直前データ、エンコード処理状態を示すラベル情報、及び出力ベースアドレス等がある。また、エンコード状態の計算は、入力データと保持されたエンコード処理状態に基づいて、新たなエンコード処理状態及び命令動作を決定するものであり、該計算された新たなエンコード処理状態に基づいて、エンコードデータを出力すべきアドレスが計算される。
【００１６】
このような本発明は、具体的に願書に添付する図面に示す構成及び処理において、以下の実施形態と対応して実現できる。
【００１７】
以下、本発明に係る一実施形態について説明する。
【００１８】
＜第１実施形態＞
まず、本実施形態のベースとなる、代表的なランレングス圧縮方式であるＴＩＦＦ仕様書に記述されたＰａｃｋＢｉｔｓ圧縮方法について説明する。ＰａｃｋＢｉｔｓ圧縮によるデータ形式は、１バイトの制御コードＮと、この制御コードＮで決定されるバイト長のバイトデータ列、の繰り返しからなり、制御コードＮの値によって、デコーダの動作は以下の（１）〜（３）に示す３通りに分類される。
【００１９】
（１）  ０  ≦  Ｎ  ≦  １２７  の場合
制御コードの後にＮ＋１バイトのデータ列が続き、デコード時には制御コードを除いたＮ＋１バイトがそのまま出力される（ＴＩＦＦ仕様書では、ｌｉｔｅｒａｌ  ｒｕｎと呼ばれる）。
【００２０】
（２）  −１２７  ≦  Ｎ  ≦  −１  の場合
制御コードの後に１バイトのデータが続き、デコード時には、制御コードの後の１バイトのデータが−Ｎ＋１回繰り返し出力される。（ＴＩＦＦ仕様書では、ｒｅｐｌｉｃａｔｅ  ｒｕｎと呼ばれる）
（３）  Ｎ  ＝  −１２８  の場合
制御コードの後に続くバイトデータ列は無く、デコード時には、制御コードが捨てられるだけである。
【００２１】
一般にＰａｃｋＢｉｔｓ圧縮によるエンコードは、上述のデコーダで元データを復元できれば、どのようなエンコードを行っても構わないが、圧縮率の高いエンコードを行うためには、基本的な方針としては、同じバイトデータの繰り返しはなるべく多くのバイトデータをまとめて（２）のｒｅｐｌｉｃａｔｅ  ｒｕｎ形式でエンコードし、それ以外は、なるべく多くのバイトデータをまとめて（１）のｌｉｔｅｒａｌ  ｒｕｎ形式でエンコードを行う。但し、バイトデータの２回繰り返しに関しては、常にｒｅｐｌｉｃａｔｅ  ｒｕｎ形式（Ｎ＝−１）でエンコードすると却って圧縮率が悪くなる場合があるため、入力データに応じて、エンコード形式を選択する必要がある。
【００２２】
以下、本実施形態におけるＰａｃｋＢｉｔｓ圧縮のエンコードについて、詳細に説明する。
【００２３】
本実施形態におけるＰａｃｋＢｉｔｓ圧縮のエンコードは、３つのＰａｃｋＢｉｔｓエンコード命令をもつプロセッサとして実現される。まず、この３つのＰａｃｋＢｉｔｓエンコード命令について説明するが、本実施形態における命令の名称（ＰＢＥ１，  ＰＢＥ２，  ＰＢＥＦ）は、説明用に付した仮称であるため、任意の変更が可能である。
【００２４】
＊  ＰＢＥ１命令：入力バイトデータを受け取り、エンコード処理ステートマシンの状態遷移を計算して、制御コード出力が必要であれば制御コードを適切な出力番地にストアする。
【００２５】
＊  ＰＢＥ２命令：ＰＢＥ１命令で計算された状態遷移結果をもとに、入力バイトデータを適切な出力番地にストアする。
【００２６】
＊  ＰＢＥＦ命令：すべての入力バイトデータが処理された時点で未出力である制御コードを適切な出力番地にストアし、エンコード処理ステートマシンをリセットする。
【００２７】
以下、これら３つの命令を使用してＰａｃｋＢｉｔｓエンコードを行う例を、図２及び図３を用いて説明する。
【００２８】
図２において、２００は左から右に向けて順に並んだバイト単位の入力データであり、Ａ〜Ｆはそれぞれ異なった値をとる１バイトのデータを示している。入力データ２００は左から右に、プロセッサ２０１に対して順次入力され、ＰａｃｋＢｉｔｓエンコードされて出力データ２０２となる。出力データ２０２において、Ａ〜Ｆは入力のデータ値を示し、＋１，−３などの数値は制御コードＮを示す。図２に示す例では、１１バイトの入力データが１０バイトに圧縮されて出力されている。
【００２９】
図３は、１バイトのデータが入力される毎に、本実施形態の命令によってどのような出力が生成されるかを例示するものである。同図において、（１）〜（１１）は各ステップを示し、各ステップにおける右向き矢印の左辺は入力データを示し、右辺は、入力に対してＰＢＥ１命令とＰＢＥ２命令を順に実行した後の出力バッファの状態を示している。なお、出力バッファの状態図において、−で示される欄はまだ書込みの行われていないアドレスを示す。また、Ａ〜Ｆあるいは、＋１，−２などの数値は、そのアドレスに書き込まれた値を示す。特に網点のかかった欄は、そのステップにおいて実行されたＰＢＥ１あるいはＰＢＥ２命令によって書き込まれた値を示す。また上向き矢印は、後述する出力ベースアドレスを示す。
【００３０】
ステップ（１２）は、すべてのデータが入力された後に、まだ出力されていない最後の制御コードを出力するためのフラッシュ処理であり、ＰＢＥＦ命令が実行される。
【００３１】
以下、図３に示す各ステップを順に追って、本実施形態におけるＰａｃｋＢｉｔｓエンコードを具体的に説明する。
【００３２】
まずステップ（１）では、最初のデータＡが入力されるが、１バイトしかデータが無い時点では、ｌｉｔｅｒａｌ  ｒｕｎであるかｒｅｐｌｉｃａｔｅ  ｒｕｎであるかの判定がつかないため、ＰＢＥ１命令は制御コードを出力せず、ＰＢＥ２命令だけが入力データを出力する。ステップ（２），（３）の入力データは、いずれも直前のデータと異なるためｌｉｔｅｒａｌ  ｒｕｎと考えられ、ＰＢＥ１命令は制御コードを出力せず、ＰＢＥ２命令だけが入力データを出力する。
【００３３】
ステップ（４）では、Ｃが２回連続するため、ｒｅｐｌｉｃａｔｅ  ｒｕｎの可能性が出てくるが、前述したようにＰａｃｋＢｉｔｓ圧縮では、同データの２回連続をｒｅｐｌｉｃａｔｅ  ｒｕｎにエンコードしてしまうと圧縮率が悪くなる場合があるため、このステップではまだ判定を行わず、ステップ（１）から（３）と同様の処理が行われる。
【００３４】
ステップ（５）では、Ｃが３回連続し、これをｒｅｐｌｉｃａｔｅ  ｒｕｎでエンコードすることが確定するため、遡ってＡ，Ｂの２バイトがＮ＝＋１のｌｉｔｅｒａｌ  ｒｕｎとなる。従って、ステップ（５）のＰＢＥ１命令は＋１を出力する。またＰＢＥ２命令は、本来ならば入力データＣを出力するところであるが、既に前のステップでＣが書き込まれているため、このステップでは出力を行っていない。
【００３５】
ステップ（６）では、Ｃと異なるデータＤが入力されるため、Ｃが３回連続のｒｅｐｌｉｃａｔｅ  ｒｕｎ（Ｎ＝−２）であることが確定し、ＰＢＥ１命令は−２を出力する。このＰＢＥ１命令実行後の時点では、ステップ（１）の１バイトしかデータが無い状態と同じになるため、ＰＢＥ２命令は、ステップ（１）と同様に入力データＤを出力する。
【００３６】
次のステップ（７）では、Ｄが２回連続するためステップ（４）と類似の状態が発生するが、このステップでは直前データＣがｒｅｐｌｉｃａｔｅ  ｒｕｎであり、ｒｅｐｌｉｃａｔｅ  ｒｕｎと隣り合う同一データの２回繰り返しはｒｅｐｌｉｃａｔｅ  ｒｕｎにしても圧縮率は悪化しないため、ここでは、ｒｅｐｌｉｃａｔｅ  ｒｕｎであると判定して、ＰＢＥ２命令による入力データの出力は行っていない。また、この時点ではラン長がどこまで続くか不明であるため、ＰＢＥ１命令による制御コードの出力も行われない。ステップ（８），（９）についてもステップ（７）と全く同様で、ラン長が確定しないため、何の出力も行われない。
【００３７】
ステップ（１０）では、Ｄと異なるデータＥが入力されるため、Ｄのラン長が４と確定し、ＰＢＥ１命令によって制御コードＮ＝−３が出力される。ＰＢＥ２命令は、ステップ（１）等と同様に入力データを出力する。
【００３８】
ステップ（１１）は、ステップ（１），（２）等と同様にＰＢＥ１命令による制御コード出力は行われず、ＰＢＥ２命令による入力データ出力だけが行われる。
【００３９】
最後のデータが入力されたステップ（１１）の終了時点では、最後の制御コードが出力されていないため、追加のステップ（１２）でＰＢＥＦ命令を実行し、最後の制御コードを出力する。
【００４０】
このように本実施形態によれば、データ入力等に要する付随的な命令を除くと、ＰＢＥ１命令＋ＰＢＥ２命令を入力データのバイト数回実行し、最後にＰＢＥＦ命令を１回実行することで、ＰａｃｋＢｉｔｓエンコードが完了する。すなわち、ソフトウェア上の条件判定や分岐処理がないため、従来のソフトウェアのみによるエンコード処理に比べて、処理速度が大幅に向上する。
【００４１】
次に、本実施形態におけるＰＢＥ１命令、ＰＢＥ２命令、ＰＢＥＦ命令の具体的な処理内容について、図１Ａ〜図１Ｃおよび図４を用いて説明する。なお、各命令の処理内容を示す図１Ａ〜図１Ｃにおいて、同一の処理については同一番号を付してある。
【００４２】
図１Ａは、ＰＢＥ１命令による処理内容を説明する図である。
【００４３】
ＰＢＥ１命令が実行されると、入力バイトデータ１００は、以前の命令によって保存されていた直前バイトデータ１０２と比較され、その比較結果（一致又は不一致）がエンコードステートマシン１０４に入力される。エンコードステートマシン１０４では、この比較結果入力と、エンコーダ状態１０３を用いてエンコーダの状態遷移を計算して、新たなエンコーダ状態を保存し、この命令でどのような動作を行うべきかを出力する。なお、エンコードステートマシン１０４における動作の詳細については、図４を参照して後述する。
【００４４】
エンコードステートマシン１０４において、この命令で制御コード出力を行うという指示が無かった場合は、直前バイトデータ更新１０９を行って、直前バイトデータ１０２にこの命令の入力バイトデータ１００を格納する。
【００４５】
一方、エンコードステートマシン１０４において、この命令で制御コード出力を行うという指示がなされた場合には、制御コード計算１０５を行って、出力ベースアドレス１０１で示される出力アドレスに制御コードのストアを行うように、制御コードストア指示１０６を行う。制御コードストア指示１０６はバスインタフェース部１０７へ指示を送り、バスインタフェース部１０７が実際のメモリへの書込み動作を行う。ここで出力ベースアドレス１０１は、次に制御コードのストアをすべきアドレスを保持しているため、制御コードストア指示１０６の後には出力ベースアドレス更新１０８を行って、次に制御コードのストアをすべきアドレスを新たに出力ベースアドレス１０１に格納する。なお、制御コード出力を行う場合も、直前バイトデータ更新１０９は行われる。
【００４６】
図１Ｂは、ＰＢＥ２命令による処理の内容を示す図である。
【００４７】
ＰＢＥ２命令が実行されると、ＰＢＥ１命令によって更新された新たなエンコーダ状態１０３が読み込まれ、その状態によって、入力バイトの出力が必要か否かが判定される。この判定は、後述する図４のステートマシンの状態からだけでも行える（例えば、ラベル−２〜−１２７の状態であれば入力バイトを出力しない等）が、ＰＢＥ１命令の時点で入力バイトの出力が必要か否かは判定できるため、そのフラグを、エンコーダ状態の一部としてＰＢＥ２命令に渡すような実装も可能である。
【００４８】
判定の結果、入力バイトの出力が必要ない場合、ＰＢＥ２命令で行うことは無いため処理を終了する。一方、入力バイトの出力が必要な場合には、ＰＢＥ１命令により必要に応じて更新された出力ベースアドレス１０１を読み込み、エンコーダ状態１０３と合わせて出力アドレス計算１１０を行う。ここで計算されたアドレスと、ＰＢＥ１命令への入力と同じ入力バイトデータ１００（ＰＢＥ１命令により直前バイトデータ１０２にも同じ値が入っているため、こちらを使用することも可能）を用いて、バスインタフェース部１０７に対して入力データストア指示１１１を出す。
【００４９】
図１Ｃは、ＰＢＥＦ命令による処理の内容を示す図である。
【００５０】
ＰＢＥＦ命令が実行されると、エンコーダ状態１０３と出力ベースアドレス１０１が読み込まれ、出力ベースアドレスに対してエンコーダ状態から求められる制御コードをストアするよう、バスインタフェース部１０７に対して制御コードストア指示１０６が行われる。出力ベースアドレス更新１０８は、制御コードストア指示１０６後の、次の出力ベースアドレスを計算して、出力ベースアドレス１０１に格納する。このアドレスは、ＰＢＥＦ命令終了時点での最後の出力データの次のデータを指し示しているため、プロセッサで実行されているソフトウェアは、ＰＢＥＦ命令実行後の出力ベースアドレスを知ることで、一連の圧縮エンコードにより最終的に何バイトのデータが出力されたかを知ることができる。
【００５１】
エンコード状態初期化１１２は、エンコーダ状態１０３に初期値を書き込む処理であり、ＰＢＥＦ命令実行後に、引き続き新しいデータに対してＰＢＥ１命令，ＰＢＥ２命令を実行するための準備であるため、必ずしもここで行う必要は無い。
【００５２】
図４は、エンコードステートマシン１０４における状態遷移の一例を示す図である。上述したように、ＰａｃｋＢｉｔｓ圧縮のエンコードは自由度を有するが、図４は、効率の良い圧縮方式の一例を示している。同図において、各楕円はエンコードステートマシン１０４の状態を示し、楕円内の数字は状態に対するラベルを示す。また、矢印は入力があった時の状態遷移を示し、入力データと直前データが等しかった場合には実線の矢印、等しくなかった場合には点線の矢印に、それぞれ状態が遷移する。
【００５３】
初期状態はラベル−１２８で示される状態であり、ここから出発して、入力データがある毎に、エンコードステートマシン１０４の状態が遷移していく。ここで各状態のラベル値は、現在圧縮中のデータに対して想定している制御コード（Ｎ）の値を示しており、例えば、図３のステップ（２）のようにＡ，Ｂの２バイトの入力があった時点では、状態は−１２８→０→１と遷移し、この時点では、Ｎ＝＋１のｌｉｔｅｒａｌ  ｒｕｎとしてエンコードすることが想定されている。
【００５４】
図４において、ラベル−１２８の状態は初期状態、ラベル−１〜−１２７の状態はｒｅｐｌｉｃａｔｅ  ｒｕｎに、ラベル０〜１２７の状態はｌｉｔｅｒａｌ  ｒｕｎにそれぞれ対応しているが、本実施形態ではそれ以外に、２’〜１２７’という「’」付きの状態を想定している。この状態は、同じデータが２回連続した場合に、これを無条件でｒｅｐｌｉｃａｔｅ  ｒｕｎにせずに、ひとまずｌｉｔｅｒａｌ  ｒｕｎとして処理を進め、その次のデータで、同じデータが３回連続した時点で初めてｒｅｐｌｉｃａｔｅ  ｒｕｎとする特殊処理のために設けられている。従って、ラベル１の状態で直前データと同じデータが入力された場合、いきなりｒｅｐｌｉｃａｔｅ  ｒｕｎに遷移するのではなく、ラベル２’のｌｉｔｅｒａｌ  ｒｕｎに遷移し、さらにその次も同じデータが入力されて同じデータが３回繰り返しになった時点で、ラベル−２のｒｅｐｌｉｃａｔｅ  ｒｕｎに遷移する。一方、ラベル２’の状態で直前データと異なるデータが入力された場合は、同一データの２回繰り返しはｌｉｔｅｒａｌ  ｒｕｎとして処理されることが確定するため、ラベル３の通常のｌｉｔｅｒａｌ  ｒｕｎの状態に戻る。
【００５５】
図４において各矢印に付された（ａ）〜（ｇ）は、対応する状態遷移が起きたときの、ＰＢＥ１またはＰＢＥ２命令のとるべき動作を示している。以下、各動作の具体的な内容を示す。
【００５６】
（ａ）  ｌｉｔｅｒａｌ  ｒｕｎの継続：
図３に示すステップ（１）〜（４），（１１）に相当し、ＰＢＥ１命令による制御コード出力は行わず、ＰＢＥ２命令による入力データ出力のみが行われる。
【００５７】
（ｂ）  ｒｅｐｉｃａｔｅ  ｒｕｎの継続：
図３に示すステップ（７）〜（９）に相当し、ＰＢＥ１命令による制御コード出力も、ＰＢＥ２命令による入力データ出力も行われない。
【００５８】
（ｃ）  ｌｉｔｅｒａｌ  ｒｕｎ（Ｎ＝１２７）の確定：
図３には例示されないが、ｌｉｔｅｒａｌ  ｒｕｎとして処理できる最大長に１２８バイトの制限があるため、状態１２７，１２７’でさらに直前と異なるデータが来た場合は、Ｎ＝１２７のｌｉｔｅｒａｌ  ｒｕｎを確定させるため、ＰＢＥ１命令で制御コード＋１２７を出力し、状態０に遷移する。ＰＢＥ２命令では、入力データを次のランに対応するアドレスに出力する。
【００５９】
（ｄ）  ｌｉｔｅｒａｌ  ｒｕｎの確定，及び  ｒｅｐｌｉｃａｔｅ  ｒｕｎ（Ｎ＝−２）の継続：
図３に示すステップ（５）に相当し、同じデータが３回続いた時点で、その前のデータをｌｉｔｅｒａｌ  ｒｕｎとして確定させ、ＰＢＥ１命令により制御コードを出力する。このとき、入力データと同じ値が既に以前の状態で書き込まれているため、ＰＢＥ２命令は入力データを出力する必要が無い。
【００６０】
（ｅ）  ｌｉｔｅｒａｌ  ｒｕｎ（Ｎ＝＋１２６）の確定，及び  ｒｅｐｌｉｃａｔｅ  ｒｕｎ（Ｎ＝−１）の継続：
図３には例示されないが、１２７バイトのｌｉｔｅｒａｌ  ｒｕｎ候補データの後に２バイト同じデータが入力された場合、Ｎ＝１２６のｌｉｔｅｒａｌ  ｒｕｎが確定し、Ｎ＝−１のｒｅｐｌｉｃａｔｅ  ｒｕｎが継続しているものとして扱う。ＰＢＥ１命令は制御コード１２６を出力し、ＰＢＥ２命令は入力データを次の制御コードアドレスの次のアドレスに出力する。
【００６１】
（ｆ）  ｒｅｐｌｉｃａｔｅ  ｒｕｎ（Ｎ＝−１２７）の確定：
図３には例示されないが、ｒｅｐｌｉｃａｔｅ  ｒｕｎの最大長は−１２８であるため、１２８バイト以上同じデータが連続した場合は、Ｎ＝−１２７のｒｅｐｌｉｃａｔｅ  ｒｕｎを確定させ、状態０に遷移する。ＰＢＥ１命令は制御コード−１２７を出力し、ＰＢＥ２命令は入力データを次の制御コードアドレスの次のアドレスに出力する。
【００６２】
（ｇ）  ｒｅｐｌｉｃａｔｅ  ｒｕｎの確定：
図３に示すステップ（６），（１０）に相当し、継続していたｒｅｐｌｉｃａｔｅ  ｒｕｎのラン長が確定して、状態０に遷移する。ＰＢＥ１命令は制御コードとして遷移前のラベルを出力し、ＰＢＥ２命令は入力データを次の制御コードアドレスの次のアドレスに出力する。
【００６３】
ここで、出力アドレスの計算方法について詳細に説明する。
【００６４】
まず制御コードについては、次に制御コードを格納すべきアドレスが出力ベースアドレスとして保存されているため、この出力ベースアドレスをそのまま使用してストアを行う。制御コードのストアを行った場合、その次の制御コードを格納すべきアドレスは、ストアした制御コード（Ｎ）から次の式で計算できる。
【００６５】
新出力ベースアドレス  ＝  旧出力ベースアドレス＋Ｎ＋２      （Ｎ≧０の場合）
新出力ベースアドレス  ＝  旧出力ベースアドレス＋２          （Ｎ＜０の場合）
また、入力バイトデータの出力については、出力ベースアドレスと状態ラベルＬ（「’」付きのラベルであれば「’」を省いた値）を参照して、その次のアドレスに対して行われる。すなわち、
入力データストアアドレス  ＝  出力ベースアドレス＋Ｌ＋１    （Ｌ≧０の場合）
入力データストアアドレス  ＝  出力ベースアドレス＋１        （Ｌ＝−１の場合）
なお、Ｌ≦−２の場合には、入力データストアアドレスの出力は不要である。
【００６６】
なお、この入力データストアアドレス計算方式では、Ｌ＝−１の場合について、図４に示す状態０から状態−１への遷移（ｂ）と、状態１２７から状態−１への遷移（ｅ）を区別していないため、遷移（ｂ）の場合に無駄なストアを生じてしまうが、これらを区別できるような情報を、ＰＢＥ１命令からＰＢＥ２命令へエンコーダ状態１０３の一部として渡すことによってこの無駄を無くすことができる。
【００６７】
このように本実施形態によれば、１バイトのデータ入力に対して２つの命令（ＰＢＥ１，ＰＢＥ２）を呼び出すだけで、ソフトウェアのみによるＰａｃｋＢｉｔｓ圧縮のエンコードを高速に行うことが可能となる。
【００６８】
図５に、本実施形態において、ＰａｃｋＢｉｔｓエンコード命令を実現するための具体的な構成例を示す。ＰａｃｋＢｉｔｓエンコード命令実行部５００はプロセッサ内にあって、ＰａｃｋＢｉｔｓエンコード命令が実行された際の実際の処理を担当する。同図には示されていないが、プロセッサ内のデコーダによってＰａｃｋＢｉｔｓエンコード命令がデコードされた場合に、ＰａｃｋＢｉｔｓエンコード命令実行部５００の動作が有効になる。ＰａｃｋＢｉｔｓエンコード命令実行部５００は、大きく分けて、エンコード処理状態保持部５０１、エンコード処理状態計算部５０２、出力バイトアドレス計算部５０３の３つの部分からなる。
【００６９】
エンコード処理状態保持部５０１は、ＰａｃｋＢｉｔｓエンコード処理に伴って保持すべき状態情報を格納しており、格納する情報としては、例えば図１Ａ等では直前バイトデータ１０２、エンコーダ状態１０３、出力ベースアドレス１０１が対応する。但し、必ずしもこれらすべての情報をエンコード処理状態保持部５０１で格納する必要は無く、一部あるいはすべての情報をプロセッサの汎用レジスタや他のレジスタに格納し、これらの情報をＰａｃｋＢｉｔｓエンコード命令実行部５００の外から与えて利用するような実装も、プロセッサの構成によっては可能である。
【００７０】
エンコード処理状態計算部５０２は、外部からの入力データを受け取り、エンコード処理状態保持部５０１に格納された状態情報を使用して、状態遷移と、命令の行うべき出力動作を決定する部分である。エンコード処理状態計算部５０２によって、図１Ａ等に示すエンコードステートマシン１０４と、処理の流れが決定付けられる。
【００７１】
出力バイトアドレス計算部５０３は、エンコード処理状態計算部５０２の決定に従って、データを出力すべきアドレスを計算し、ＰａｃｋＢｉｔｓエンコード命令実行部５００の外にあるバスインタフェース部５０４に対してストアアドレスを与える。このときエンコード処理状態計算部５０２は、バスインタフェース部５０４に対してストアデータを与える。
【００７２】
なお、本実施形態における命令の実装は、必ずしも図１Ａ〜図１Ｃや図４、図５の通りの形式である必要は無く、同様の結果が得られる、様々な他の実装が考えられる。
【００７３】
また、図１Ａ〜図１Ｃによって３つのＰａｃｋＢｉｔｓエンコード命令について説明したが、処理内容の分担は必ずしもこの通りである必要は無く、同じ処理内容であれば、各命令の分担はどのような分割方法であっても良い。また、命令の個数も３命令に限定されるものではなく、命令の実装が許せば、２命令、あるいは１命令にまとめてもよい。
【００７４】
また、図１Ａ，図１Ｂに示すＰＢＥ１，ＰＢＥ２命令では不必要な出力を避けるために、条件判定によってストアを行うか否かを切り替える例を示したが、不必要な出力を行っても、最終的な出力結果を変えない限りアルゴリズムとしては問題ないため、このような切り替えを行わない実装もありうる。例えば、ｒｅｐｌｉｃａｔｅ  ｒｕｎの継続中（図４の状態遷移（ｂ））であっても繰り返し同じデータの出力を行うような実装も可能であるし、あるいは、ストア条件不成立の時に、圧縮処理に影響の無いダミーアドレスにストアを指示するような実装も可能である。
【００７５】
また、図１Ａ等において、命令の入出力となるデータ，入力バイトデータ１００，出力ベースアドレス１０１，直前バイトデータ１０２，エンコーダ状態１０３、のいずれが命令オペランドとして指定可能（例えば汎用レジスタ）であり、いずれが暗黙の命令オペランド（例えばＰａｃｋＢｉｔｓ命令専用のステートレジスタ）であるかについては示していないが、これらは、プロセッサとして利用可能なリソースや命令の実装コストに依存して、最適な実装形態が変わってくる。
【００７６】
以上説明したように本実施形態によれば、プロセッサに圧縮命令を追加、内蔵することによって、プロセッサとは別にＰａｃｋＢｉｔｓ圧縮用の専用ハードウェアを設けることなく、例えば圧縮のデータ単位を変更する等、処理フローの変更を柔軟に行うことができるのみならず、プロセッサにおけるＰａｃｋＢｉｔｓエンコードの処理速度を大幅に向上させることができる。
【００７７】
＜第２実施形態＞
以下、本発明に係る第２実施形態について説明する。
【００７８】
上述した第１実施形態の図５に示す構成においては、エンコード処理状態保持部５０１が、現在エンコード中であるデータ列に関する状態情報を保持しているが、第２実施形態においては、この状態情報を複数のデータ列について保持可能とする。すなわち、エンコード処理状態保持部を複数備え、その中のひとつをエンコード処理状態計算部５０２が選択的に使用することによって、複数の入力データ列に対するＰａｃｋＢｉｔｓエンコード処理を並行して行うことができる。
【００７９】
例えば、２つのバイトデータ系列｛Ａ０，Ａ１，Ａ２，．．．｝，｛Ｂ０，Ｂ１，Ｂ２，．．．｝について、これを別々にＰａｃｋＢｉｔｓエンコードする場合を考える。
【００８０】
ここで、入力データが、Ａ０，Ａ１，Ａ２，．．．，Ｂ０，Ｂ１，Ｂ２，．．．と最初のデータ系列の後に、次のデータ系列が来るという形で生成されてくるとすると、まず、Ａ０，Ａ１，Ａ２，．．．系列に対するエンコードをＰＢＥ１，ＰＢＥ２命令によって行い、この系列の最後のデータの後にＰＢＥＦ命令を実行すれば、引き続き、Ｂ０，Ｂ１，Ｂ２，．．．系列に対するエンコードを行うことができる。
【００８１】
ところが、２つのデータ系列のデータがＡ０，Ｂ０，Ａ１，Ｂ１，Ａ２，Ｂ２，．．．のように入り混じった順序で生成されてくるとすると、Ａ０，Ａ１，Ａ２，．．．系列に対するエンコード処理から先に行うために、Ｂ０，Ｂ１，Ｂ２，．．．系列の入力データを一時バッファ領域に格納しておく必要が生じる。このような場合に、第２実施形態では複数のエンコード処理状態保持部を備えているため、入力データがＡ０，Ａ１，Ａ２，．．．系列のときにはＡ系列用の状態保持部を選択し、入力データがＢ０，Ｂ１，Ｂ２，．．．系列のときにはＢ系列用の状態保持部を選択することによって、一時バッファを用意することなく、２つのデータ系列に対するエンコードを並行して進めることができる。
【００８２】
このように第２実施形態のプロセッサは、ＰＢＥ１命令によって取得されたエンコード処理状態を複数保持し、該複数のエンコード処理状態から選択されたエンコード処理状態に基づく各命令の実行を、複数のエンコード状態について並行に行うことができる。
【００８３】
以上説明したように第２実施形態によれば、ソフトウェアによる高速なＰａｃｋＢｉｔｓエンコード処理を、複数の入力データ列に対して並行に行うことができるため、さらなる処理の高速化が望める。
【００８４】
＜第３実施形態＞
以下、本発明に係る第３実施形態について説明する。
【００８５】
第３実施形態では、例えば画像データの左右反転処理をＰａｃｋＢｉｔｓ圧縮の直前に行う場合や、誤差拡散法等の方向性を持った画像処理を入力データ順と逆方向にかける場合等、入力データが本来の入力順序と逆、すなわち後ろから前に向かって入力される場合にも、ＰａｃｋＢｉｔｓエンコード命令を高速に実行可能なプロセッサについて説明する。なお、使用する命令の名称は、上述した第１実施形態と同様である。
【００８６】
以下、図６及び図７を用いて、本実施形態における逆順のＰａｃｋＢｉｔｓエンコードについて説明する。
【００８７】
図６において、入力データ６００は左から右に向けて順に並んだバイト単位のデータである。入力データ６００は、第１実施形態において図２に示した入力データ２００と同じ並びであるが、プロセッサに入力される順序が異なっている。図６に示す入力データ６００では、図中矢印で示されるように、本来の順序とは逆順、すなわち右から左へデータが入力される。
【００８８】
プロセッサ６０１は、逆順の入力データ６００をＰａｃｋＢｉｔｓエンコードし、出力データ６０２として出力するが、出力データ６０２は、図２の出力データ２０２と同じ並びである。すなわちプロセッサ６０１は、入力データが逆順に入力されたにも関わらず、本来の順序で入力された場合と等価な並びの出力データを生成する。
【００８９】
以下、図７に示す各ステップを順に追って、第３実施形態におけるＰａｃｋＢｉｔｓエンコードを具体的に説明する。図７に示す記号等は、第１実施形態で示した図３と同様であるが、上向き矢印で示される出力ベースアドレスの意味は、第１実施形態のように次に制御コードを出力するアドレスではなく、最後に制御コードを出力したアドレスを指している点が異なる。
【００９０】
図７の各ステップで実行する命令は、図３の場合と全く同様であり、ステップ（１）〜（１１）では入力データに対応して、ＰＢＥ１命令とＰＢＥ２命令を実行し、最終データ入力後のステップ（１２）では、ＰＢＥＦ命令を実行する。従って第３実施形態においては第１実施形態の場合と同様に、処理速度の向上が達成される。
【００９１】
具体的に図７のステップを追っていくと、まずステップ（１）では最初のデータＦが入力されるが、１バイトしかデータが無い時点では、ラン種別もラン長も判定がつかないため、ＰＢＥ１命令は制御コードを出力せず、ＰＢＥ２命令だけが入力データを出力する。このとき、ステップ（１）では、まだ制御コードを一度も出力していないため、最後に制御コードを出力したアドレスを指す出力ベースアドレスは、出力バッファの最後の次のアドレスを指している。これは、第１実施形態とは異なって第３実施形態では、次に制御コードを出力すべきアドレスの確定が、ラン種別・ラン長の確定の後になるためである。
【００９２】
ステップ（２），（３）の入力データは、いずれも直前のデータとは異なるため、ｌｉｔｅｒａｌ  ｒｕｎと考えられ、ステップ（１）と同様、ＰＢＥ２命令だけが入力データを出力する。ステップ（４）ではＤが２回連続しているが、第１実施形態でも説明したように、ＰａｃｋＢｉｔｓ圧縮では同データの２回連続をｒｅｐｌｉｃａｔｅ  ｒｕｎにエンコードしてしまうと圧縮率が悪くなる場合があるため、ここではまだ判定を行わない。
【００９３】
ステップ（５）では、Ｄが３回連続し、これをｒｅｐｌｉｃａｔｅ  ｒｕｎでエンコードすることが確定するため、遡ってＥ，Ｆの２バイトがＮ＝＋１のｌｉｔｅｒａｌ  ｒｕｎとなる。従って、ステップ（５）のＰＢＥ１命令は＋１を出力する。またＰＢＥ２命令は、本来ならば入力データＤを出力するところであるが、既に前のステップでＤが書き込まれているため、このステップでは出力を行っていない。
【００９４】
ステップ（６）では、さらにＤが入力されるが、ラン長が確定しないため、何の出力も行われない。次のステップ（７）では、Ｄと異なるデータＣが入力されるため、Ｄが４回連続のｒｅｐｌｉｃａｔｅ  ｒｕｎ（Ｎ＝−３）であることが確定し、ＰＢＥ１命令は−３を出力する。このＰＢＥ１命令実行後の時点では、ステップ（１）の１バイトしかデータが無い状態と同じになるため、ＰＢＥ２命令は、ステップ（１）と同様に入力データＣを出力する。
【００９５】
次のステップ（８）では、Ｃが２回連続するためステップ（４）と類似の状態が発生するが、このステップでは直前データＤがｒｅｐｌｉｃａｔｅ  ｒｕｎであり、ｒｅｐｌｉｃａｔｅ  ｒｕｎと隣り合う同一データの２回繰り返しはｒｅｐｌｉｃａｔｅ  ｒｕｎにしても圧縮率は悪化しないため、ここでは、ｒｅｐｌｉｃａｔｅ  ｒｕｎであると判定して、ＰＢＥ２命令による入力データの出力は行っていない。また、この時点ではラン長がどこまで続くか不明であるため、ＰＢＥ１命令による制御コードの出力も行われない。
【００９６】
ステップ（９）は、ステップ（６）と全く同様で、ラン長が確定しないため、何の出力も行われない。
【００９７】
ステップ（１０）では、Ｃと異なるデータＢが入力されるため、Ｃのラン長が３と確定し、ＰＢＥ１命令によって制御コードＮ＝−２が出力される。ＰＢＥ２命令は、ステップ（１）等と同様に入力データを出力する。
【００９８】
ステップ（１１）は、ステップ（１），（２）等と同様にＰＢＥ１命令による制御コード出力は行われず、ＰＢＥ２命令による入力データ出力だけが行われる。
【００９９】
最後のデータが入力されたステップ（１１）の終了時点では、最後の制御コードが出力されていないため、追加のステップ（１２）でＰＢＥＦ命令を実行し、最後の制御コード＋１を出力する。
【０１００】
以上説明した図７の例は、第１実施形態の図３の例と多くの部分が共通であるが、出力アドレスの計算方法が大きく異なっている。すなわち第３実施形態は、第１実施形態で示した図１Ａ〜図１Ｃと殆ど同じ命令処理の流れと、図４と全く同じステートマシンを使用し、出力アドレスの計算方法のみを変更することによって、実現できる。
【０１０１】
図８Ａ，図８Ｂはそれぞれ、第３実施形態におけるＰＢＥ１，ＰＢＥＦ命令処理の流れを示す図であるが、図１Ａ，図１Ｂと殆ど同様であるため、ここではその相違点のみについて説明する。なおＰＢＥ２命令については図１Ｂと全く同様であるため、ここではその説明を省略する。
【０１０２】
まずＰＢＥ１命令について、図１Ａと図８Ａで異なる点は、制御コードストア指示１０６と出力ベースアドレス更新１０８の処理順序である。第３実施形態においての出力ベースアドレスは、「最後に制御コードを出力したアドレス」を指すため、制御コードを出力する時は、次に制御コードを出力するアドレスを指すよう出力ベースアドレス更新１０８を行った後に、制御コードストア指示１０６を行うことになる。
【０１０３】
ＰＢＥＦ命令についても同様に、出力ベースアドレスの意味が異なることから、図１Ｃと図８Ｂでは、制御コードストア指示１０６と出力ベースアドレス更新１０８の順序が異なっている。
【０１０４】
以下、第３実施形態における出力アドレスの計算について説明する。
【０１０５】
まず制御コードについては、直前に制御コードを格納したアドレスが出力ベースアドレスとして保存されているため、この出力ベースアドレスを更新した後にストアを行う。制御コードの更新を行う場合、更新後の新しいアドレスは、これからストアする制御コード（Ｎ）から次の式で計算できる。
【０１０６】
新出力ベースアドレス＝旧出力ベースアドレス−（Ｎ＋２）    （Ｎ≧０の場合）
新出力ベースアドレス＝旧出力ベースアドレス−２            （Ｎ＜０の場合）
また、入力バイトデータの出力については、出力ベースアドレスと状態ラベルＬ（「’」付きのラベルであれば「’」を省いた値）を使用して、次のアドレスに対して行われる。すなわち、
入力データストアアドレス  ＝  出力ベースアドレス−（Ｌ＋１）    （Ｌ≧０の場合）
入力データストアアドレス  ＝  出力ベースアドレス−１            （Ｌ＝−１の場合）
なお、Ｌ≦−２の場合には、入力データストアアドレスの出力は不要である。
【０１０７】
これらの計算式を上述した第１実施形態におけるアドレス計算式と比較すれば、出力ベースアドレスに対するオフセット値を加算するのか、減算するのかが異なっていることが分かる。
【０１０８】
なお、第３実施形態における入力データストアアドレス計算方式においても、Ｌ＝−１の場合について、図４に示す状態０から状態−１への遷移（ｂ）と、状態１２７から状態−１への遷移（ｅ）を区別していないため、遷移（ｂ）の場合に無駄なストアを生じてしまうが、これらを区別できるような情報を、ＰＢＥ１命令からＰＢＥ２命令へエンコーダ状態１０３の一部として渡すことによってこの無駄を無くすことができる。
【０１０９】
このように第３実施形態のプロセッサは、入力データが逆順に入力された場合にも、該入力データが順入力された場合と同様のデータ列を出力する。すなわち、出力ベースアドレスに対するアドレス計算のオフセット値の加減を、該入力データが順入力された場合と逆となるように制御する。
【０１１０】
このように第３実施形態によれば、入力データが後ろから前に逆順で入力される場合においても、第１実施形態と全く同様に、すなわち本来の順序で入力された場合と同様に、１バイトのデータ入力に対して２つの命令（ＰＢＥ１，ＰＢＥ２）を呼び出すだけで、ソフトウェアのみによるＰａｃｋＢｉｔｓ圧縮のエンコードを高速に行うことが可能となる。従って、逆順の入力データを並べ替えるための処理が不要となるため、処理速度の低下が回避され、かつ、データ保存用の一時バッファも不要となる。
【０１１１】
なお、第１実施形態と第３実施形態の実装は、アドレス計算を除いて殆ど共用できるため、入力データが本来の順序で入力される場合と、逆順で入力される場合との選択部を設けることによって、第１実施形態と第３実施形態を選択的に切り替えて使用するようなＰａｃｋＢｉｔｓエンコード命令も容易に実現可能である。すなわち、入力データが順入力されたか逆入力されたかによって、アドレス計算方法を切換えることができれば良い。
【０１１２】
また、上述した従来技術として示した特許文献１に記載された圧縮方式は、ＰａｃｋＢｉｔｓ圧縮の制御コードとそれに続くバイトデータ列の順序を逆にしたものであり、この方式は、第３実施形態において入力データを逆順で圧縮する場合と同様の動作となる。但し、特許文献１の方式と第３実施形態とでは出力番地の計算方向が異なるため、特許文献１ではＰａｃｋＢｉｔｓ圧縮と非互換の出力が生成されるが、第３実施形態では、ＰａｃｋＢｉｔｓ圧縮と互換の出力が生成される。
【０１１３】
【他の実施形態】
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用しても良い。
【０１１４】
【発明の効果】
以上説明したように本発明によれば、プロセッサでＰａｃｋＢｉｔｓ圧縮のエンコードを行う際に、プロセッサとは別に専用のハードウェアを設けることなく、高速性と処理フローの柔軟性を両立させることができる。
【図面の簡単な説明】
【図１Ａ】本発明に係る一実施形態におけるＰＢＥ１命令の処理内容を説明する図である。
【図１Ｂ】本実施形態におけるＰＢＥ２命令の処理内容を説明する図である。
【図１Ｃ】本実施形態におけるＰＢＥＦ命令の処理内容を説明する図である。
【図２】本実施形態におけるＰａｃｋＢｉｔｓエンコード処理（順方向）の出力例を示す図である。
【図３】本実施形態におけるステップ毎の処理例を示す図である。
【図４】本実施形態において命令を実現するためのエンコードステートマシンの状態遷移例を示す図である。
【図５】本実施形態を実現する構成例を示す図である。
【図６】第３実施形態におけるＰａｃｋＢｉｔｓエンコード処理（逆方向）の出力例を示す図である。
【図７】第３実施形態におけるステップ毎の処理例を示す図である。
【図８Ａ】第３実施形態におけるＰＢＥ１命令の処理内容を説明する図である。
【図８Ｂ】第３実施形態におけるＰＢＥＦ命令の処理内容を説明する図である。
【符号の説明】
１００  入力バイトデータ
１０１  出力ベースアドレス
１０２  直前バイトデータ
１０３  エンコーダ状態
１０４  エンコードステートマシン
１０５  制御コード計算
１０６  制御コードストア指示
１０７  バスインタフェース部
１０８  出力ベースアドレス更新
１０９  直前バイトデータ更新
１１０  入力バイトデータに対する出力アドレス計算
１１１  入力データストア指示
１１２  エンコーダ状態初期化
２００  順方向で入力される入力データ
２０１  プロセッサ
２０２  ＰａｃｋＢｉｔｓエンコード後の出力データ
５００  ＰａｃｋＢｉｔｓエンコード命令実行部
５０１  エンコード処理状態保持部
５０２  エンコード処理状態計算部
５０３  出力バイトアドレス計算部
５０４  バスインタフェース部
６００  逆方向で入力される入力データ
６０１  プロセッサ
６０２  ＰａｃｋＢｉｔｓエンコード後の出力データ
【図１Ａ】
2004274509.tif 000003
【図１Ｂ】
2004274509.tif 000004
【図１Ｃ】
2004274509.tif 000005
【図２】
2004274509.tif 000006
【図３】
2004274509.tif 000007
【図４】
2004274509.tif 000008
【図５】
2004274509.tif 000009
【図６】
2004274509.tif 000010
【図７】
2004274509.tif 000011
【図８Ａ】
2004274509.tif 000012
【図８Ｂ】
2004274509.tif 000013