1

C＃プロジェクトでは、jffs2ファイルシステムのイメージを読み取る必要があります。jffs2で使用される圧縮アルゴリズムの1つは、「rtime」です。

Linuxの相互参照ホームページにあるCコードの行を除いて、この「rtime」圧縮方法に関する情報は見つかりませんでした。

解凍がどのように機能するか、または圧縮/解凍用の.Netライブラリまたはプロジェクトの説明はどこかにありますか？

ありがとうございました

ピーター

4

2 に答える 2

0

私も本当の文書を見つけることができませんでした。だから私はhttp://www.codeforge.com/read/7074/compr_rtime.c__htmlでソースを研究することに頼らなければなりませんでした

これが私が理解したことです。Rtime圧縮データは、バイトペアでエンコードされます。ここで、最初の項目はデータバイトで、2番目の項目はリピートカウンターです。

Rtimeアルゴリズムは、一度に1バイトずつ入力データを反復処理します。現在のバイトに1を加えた最後の出現位置を記憶しています。これを「バックポス」と呼びます。したがって、たとえば、「A」が最後に位置0で見られた場合、そのバックポスは1になります。現在のバイトの位置とバックポスの間の距離は、一種のLZ77風のスライディングウィンドウを作成します。次に、Rtimeは、次の入力バイトをバックポジションのバイトと比較します。それらが同一である場合、それはリピートカウンターを1つインクリメントします。違いが検出されるか、入力の終わりに達するまで、それを続けます。

言っ途切れる！次に例を示します。

圧縮

次の入力が与えられます：

  ABBBABBBA

1）最初の入力バイトはAであるため、RtimeはAを圧縮結果の最初のペアの最初の項目として格納します。Aのバックポスがゼロになる前にAを見たことがないので。

[A] BBBABBBA
  ^ ^
  | __ |  
   =？

次に、backposのバイトと入力の次のバイト（つまり、AとB）を比較します。それらは同じではないため、Rtimeはゼロの繰り返しカウントを使用します。したがって、最初のペアは（A、0）です。

2）2番目の入力バイトはBです。Rtimeは、結果の2番目のペアの最初の項目としてBを格納します。これまでにBを見たことがないため、Bのバックポスもゼロです。次に、backposのバイトを次の入力バイトと比較します。

  A [B] BBABBBA
  ^ ^
  | _____ |
    =？

それらは明らかに等しくありません。したがって、繰り返し回数は再びゼロになります。したがって、2番目の結果ペアは（B、0）です。

3）3番目のバイトは再びBです。Rtimeは、結果の3番目のペアの最初の項目としてBを格納します。前の反復で位置1でBに遭遇したため、backposは2になります。

次に、backposのバイト（インデックス2）を次の入力バイト（インデックス3）と比較します。

  AB [B] BABBBA
        ^ ^
        | __ |
         =？

それらは等しいので、繰り返し回数は1に設定されます。

  AB [B] BABBBA
           ^ ^
           | __ |
            =？

Rtimeは次の2バイトを比較しますが、それらは異なります。したがって、比較は停止し、結果の3番目のペアは（B、1）です。

4）最後の反復で成功したリピートがあったので、4番目の入力バイトはすでにカバーされており、5番目のバイトを続行できます。これはAです。したがって、4番目の結果ペアの最初の項目はAです。最初の反復で位置0でAに遭遇したため、backposは1です。

この時点で物事は面白くなります。次の4つの比較は成功し、Rtimeは入力の終わりに達したため、停止する必要があります。

  ABBB [A] BBBA
     ^ ^
     | ___________ |
          =？

  ABBB [A] BBBA
        ^ ^
        | ___________ |
             =？

  ABBB [A] BBBA
           ^ ^
           | ___________ |
                =？

  ABBB [A] BBBA
              ^ ^
              | ___________ |
                   =？

したがって、4番目で最後の結果ペアは（A、4）です。全体として、圧縮された結果は（A、0）（B、0）（B、1）（A、4）です。

元の入力は9バイトでしたが、これには「わずか」8バイトが必要です。

減圧

解凍はまったく同じように機能しますが、順序が逆になります。上記の結果を考えると：

（A、0）（B、0）（B、1）（A、4）。

1）最初のペアの最初の値はAです。したがって、すぐに、結果の最初の位置にAを置くことができます。また、繰り返し回数がゼロであるため、この反復が実行されます。Aのバックポスは0です。

圧縮：[A、0]（B、0）（B、1）（A、4）

 解凍：[A]

2）2番目のペアにはBが含まれています。結果の2番目の位置にBを配置します。また、繰り返し回数がゼロであるため、この反復も実行されます。Bのバックポスは1です。

圧縮：（A、0）[B、0]（B、1）（A、4）

 解凍：A [B]

3）3番目のペアにはBが含まれています。結果の3番目の位置にBを配置します。この場合、繰り返し回数は1回です。したがって、backposのバイト（この時点ではまだ1）を結果の最後に追加します。次に、Bのバックポスを2に設定します。

圧縮：（A、0）（B、0）[B、1]（A、4）

 解凍：AB [B] + B +

4）4番目のペアにはAが含まれています。結果の5番目の位置にAを配置します。繰り返し回数は4です。したがって、解凍されたストリームの最後に、backpos（この時点ではまだ0）から始まる4バイトを追加します。

圧縮：（A、0）（B、0）（B、1）[A、4]

 解凍：ABBB [A] + A ++ B ++ B ++ B +

そして、これで完了です:)

これが少し役立つことを願っています。

入力に多くの冗長性がない限り、Rtimeは元の結果よりも小さい結果を生成しません。C実装のコメントで、Rtimeはすでにgzip圧縮された画像をさらに圧縮するためにのみ使用されることをどこかで読みました。おそらくgzipにはほとんど冗長性が含まれていません。Rtimeが実際にどのくらいの頻度で改善された結果をもたらすのだろうか。

于 2012-07-29T14:46:27.500 に答える
0

これは、元のCソースからC＃への多かれ少なかれ文字通りの転写です。どちらがあなたの目的のために働くはずです。

System.IOを使用します。



名前空間RTime
{{


public class RTimeCompressor
{
    /// <summary>
    /// Compress data in the supplied stream
    /// </summary>
    /// <param name="inputData">Data to be compressed</param>
    /// <param name="compressedBytes">Number of compressed bytes. Normally value is equal to inputData.Length unless maxAcceptableCompressionSize is reached.</param>
    /// <param name="maxAcceptableCompressionSize">Upper limit of the length of the returned compressed memory stream</param>
    /// <returns>Compressed data stream</returns>
    public static MemoryStream Compress(Stream inputData, out int compressedBytes, int maxAcceptableCompressionSize = (int)short.MaxValue)
    {
        int[] positions = new int[256];
        int pos = 0;
        MemoryStream compressed = new MemoryStream();

        inputData.Seek(0, SeekOrigin.Begin);
        while (pos < inputData.Length &&
                compressed.Position <= maxAcceptableCompressionSize - 2)
        {
            int runlen = 0;
            byte value = GetByteAtPos(inputData, pos++);
            int backpos = positions[value];

            compressed.WriteByte(value);
            positions[value] = pos;

            while ((backpos < pos) &&
                    (pos < inputData.Length) &&
                    (GetByteAtPos(inputData, pos) == GetByteAtPos(inputData, backpos)) &&
                    (runlen < 255))
            {
                backpos++;
                pos++;
                runlen++;
            }

            compressed.WriteByte((byte)runlen);
        }

        // result is larger than the original input
        if (compressed.Position >= pos)
        {
            compressedBytes = 0;
            return null;
        }

        compressed.Seek(0, SeekOrigin.Begin);

        compressedBytes = pos;
        return compressed;
    }

    private static byte GetByteAtPos(Stream inputData, int pos)
    {
        long originalPos = inputData.Position;
        inputData.Seek(pos, SeekOrigin.Begin);
        byte value = (byte)inputData.ReadByte();
        inputData.Seek(originalPos, SeekOrigin.Begin);
        return value;
    }

    /// <summary>
    /// Decompress data in the supplied stream
    /// </summary>
    /// <param name="inputData">Data to be decompressed</param>
    /// <returns>Decompressed data stream</returns>
    public static MemoryStream Decompress(Stream inputData)
    {
        int[] positions = new int[256];
        int pos = 0;
        MemoryStream decompressed = new MemoryStream();
        inputData.Seek(0, SeekOrigin.Begin);

        while (pos < inputData.Length)
        {
            byte value = GetByteAtPos(inputData, pos++);
            int backoffs = positions[value];
            int repeat = GetByteAtPos(inputData, pos++);

            decompressed.WriteByte(value);
            positions[value] = (int)decompressed.Position;
            if (repeat > 0)
            {
                for (int i = 0; i < repeat; i++)
                {
                    decompressed.WriteByte(GetByteAtPos(decompressed, backoffs++));
                }
            }
        }

        decompressed.Seek(0, SeekOrigin.Begin);
        return decompressed;
    }
}

}

于 2012-07-29T15:19:32.167 に答える