jffs2中使用的rtime压缩

Question

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

我没有发现任何关于这个"rtime"压缩方法的信息，除了linux交叉引用主页上的一些C代码。

是否有关于解压缩工作原理的描述，或者更好的是用于压缩/解压缩的.Net库或项目？

谢谢

Peter

Answer 1

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

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

Rtime算法在输入数据上一次迭代一个字节。它记住当前字节最后一次出现的位置加一。它称之为"backpos"。例如，如果"A"最后一次出现在位置0，它的backpos是1。当前字节的位置和backpos创建的位置之间的距离有点像LZ77风格的滑动窗口。Rtime然后继续比较下一个输入字节后面那个。如果它们相同，它会将重复计数器增加一。它一直这样做，直到检测到差异或到达输入的末尾。

努夫说！这里有一个例子：

压缩

给定以下输入：

A B B B A B B A

1)第一个输入字节是A，因此Rtime将A存储为第一项第一对压缩结果。因为它从未见过A的前后位置为零。

[A]B B B A B B A^^|__|=

Next它比较backpos处的字节和输入的下一个字节(即A和B)。由于它们不相同，Rtime使用重复计数为零。所以第一对是(A，0)。

2) 第二个输入字节是B。Rtime将B存储为第二对结果。由于它以前从未见过BB的backpos也是零。它继续比较backpos处的字节下一个输入字节：

A[B]B B A B B A^^|_____|=3) 第三个字节也是B。Rtime将B存储为第三对结果。由于它在中的位置1遇到了B上一次迭代，backpos现在是2。
它继续将backpos处的字节(索引2)与下一个输入字节(索引3)进行比较：
A B[B]B A B B B A^^|__|=
它们相等，因此重复计数设置为1。
A B[B]B A B B B A^^|__|=
Rtime比较接下来的两个字节，但它们不同。所以比较停止了第三对结果是(B，1)
4) 由于我们在上一次迭代中成功地重复了第四个输入字节已经涵盖了，现在我们可以继续使用第五个字节。哪个是A。因此，第四个结果对的第一项是A。由于它在在第一次迭代中的位置0，backpos为1。
在这一点上，事情变得有趣起来。接下来的四个比较将会成功并且Rtime必须停止，因为它已经到达输入的末尾。
A B B B[A]B B B A^^|___________|=？A B B B[A]B B B A^^|___________|=？A B B B[A]B B B A^^|___________|=？A B B B[A]B B B A^^|___________|=这"只需要"8个字节，而原始输入是9个字节。
解压缩
解压缩的工作原理完全相同，但顺序相反。给定上述结果：
(A，0)(B，0)，(B，1)(A，4)。
1) 第一对的第一个值是A。所以我们可以马上在第一个位置放一个A结果。由于重复次数为零，因此完成了此迭代。A的背包数为0。
压缩：[A，0](B，0)(B，1)(A，4)解压缩：[A]
2)第二对包含B。我们在结果的第二个位置放一个B。由于重复次数为零，因此也完成了此迭代。B的背包是1。
压缩：(A，0)[B，0](B，1)(A，4)解压缩：A[B]
3)第三对包含B。我们在结果的第三个位置放一个B。以及重复计数在这种情况下为1。因此，我们将backpos处的字节(此时仍为1)附加到结果结束。B的背包设置为2。
压缩：(A，0)(B，0)[B，1](A，4)解压缩：A B[B]+B+
4)第四对包含A。我们把A放在结果的第五位。重复计数是4。因此，我们将从backpos开始的四个字节(此时仍为0)附加到解压缩流的末尾。
压缩：(A，0)(B，0)解压缩：A B B B[A]+A++B++B++B+
我们完成了：)
希望这能有所帮助。
除非输入中有大量冗余，否则Rtime不会产生比原始结果更小的结果。在C实现的注释中，我在某个地方读到Rtime只用于进一步压缩已经gzip化的图像。大概gzip包含很少的冗余。我想知道Rtime实际多久会产生一次改进的结果。

Answer 2

这是将原始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;
}
}

}