1

在 C# 项目中，我必须读取 jffs2 文件系统的图像。jffs2 中使用的压缩算法之一是“rtime”。

除了 linux 交叉引用主页上的一些 C 代码行外，我没有找到任何关于这种“rtime”压缩方法的信息。

是否有描述解压缩如何工作的描述，或者更好的.Net库或压缩/解压缩项目？

谢谢

彼得

4

2 回答 2

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 回答
0

我也找不到任何真正的文档。所以我不得不求助于在http://www.codeforge.com/read/7074/compr_rtime.c__html上研究源代码

这是我想出来的。Rtime 压缩数据以字节对编码。其中第一项是数据字节，第二项是重复计数器。

Rtime 算法一次一个字节地遍历输入数据。它记住当前字节最后一次出现的位置加一。它称之为'backpos'。因此，例如，如果最后一次看到“A”是在位置 0，那么它的 backpos 将为 1。当前字节的位置与 backpos 之间的距离创建了一种 LZ77-ish 滑动窗口。Rtime 然后继续将下一个输入字节与 backpos 处的字节进行比较。如果它们相同，它会将重复计数器加一。它一直这样做，直到检测到差异或达到输入的结尾。

努夫说！这是一个例子：

压缩

给定以下输入：

  ABBBABBBA

1）第一个输入字节是一个A，所以Rtime存储一个A作为第一对压缩结果的第一项。因为在 A 的 backpos 为零之前它从未见过 A。

[A] BBBABBBA
  ^ ^
  |__|  
   =？

接下来，它比较 backpos 处的字节和输入的下一个字节（即 A 和 B）。由于它们不相同，因此 Rtime 使用零重复计数。所以第一对是（A，0）。

2）第二个输入字节是一个B。Rtime存储一个B作为第二对结果的第一项。由于它以前从未见过 B，因此 B 的 backpos 也为零。它继续将 backpos 处的字节与下一个输入字节进行比较：

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

他们显然不是平等的。所以重复计数再次为零。因此第二个结果对是 (B, 0)。

3）第三个字节又是B。Rtime存储一个B作为第三对结果的第一项。由于在上一次迭代中在位置 1 遇到了 B，所以 backpos 现在是 2。

它继续将 backpos 处的字节（索引 2）与下一个输入字节（索引 3）进行比较：

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

它们相等，因此重复计数设置为 1。

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

Rtime 比较接下来的两个字节，但它们是不同的。所以比较停止第三对结果是 (B, 1)

4）由于我们在最后一次迭代中成功重复，第四个输入字节已经被覆盖，我们现在可以继续第五个字节。即 A。所以第四个结果对的第一项是 A。由于在第一次迭代中在位置 0 处遇到了 A，所以 backpos 为 1。

在这一点上，事情变得有趣了。接下来的四次比较将成功，Rtime 必须停止，因为它已到达输入的末尾。

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

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

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

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

所以第四个也是最后一个结果对是 (A, 4)。总而言之，压缩后的结果是：(A, 0)(B, 0)(B, 1)(A, 4)。

这需要“仅”8 个字节，而原始输入是 9 个字节。

减压

减压的工作方式完全相同，但顺序相反。鉴于上述结果：

(A, 0)(B, 0)(B, 1)(A, 4)。

1) 第一对的第一个值是 A。所以马上，我们可以将 A 放在结果的第一个位置。并且由于重复计数为零，因此完成了此迭代。A的Backpos为0。

压缩：[A, 0](B, 0)(B, 1)(A, 4)

 解压：[A]

2) 第二对包含 B。我们将 B 放在结果的第二个位置。并且由于重复计数为零，因此也完成了此迭代。B的Backpos为1。

压缩：(A, 0)[B, 0](B, 1)(A, 4)

 解压：A [B]

3) 第三对包含 B。我们将 B 放在结果的第三个位置。在这种情况下，重复计数为 1。因此，我们将 backpos 处的字节（此时仍为 1）附加到结果的末尾。然后 B 的 Backpos 设置为 2。

压缩：(A, 0)(B, 0)[B, 1](A, 4)

 解压：AB [B]+B+

4) 第四对包含 A。我们将 A 放在结果的第五位。重复计数为 4。因此，我们将从 backpos（此时仍为 0）开始的四个字节附加到解压缩流的末尾。

压缩：(A, 0)(B, 0)(B, 1)[A, 4]

 解压后：ABBB [A]+A++B++B++B+

我们完成了:)

希望这有所帮助。

除非输入中有很多冗余，否则 Rtime 不会产生小于原始结果的结果。在 C 实现的评论中，我在某处读到 Rtime 仅用于进一步压缩已压缩的图像。大概 gzip 包含很少的冗余。我想知道 Rtime 多久会真正产生改进的结果。

于 2012-07-29T14:46:27.500 回答