C# 프로젝트에서 jffs2 파일 시스템의 이미지를 읽어야합니다. jffs2에서 사용되는 압축 알고리즘 중 하나는 "rtime"입니다.rtime 압축이 jffs2에서 사용됨
"rtime"압축 방법에 대한 정보를 찾지 못했습니다. 단, Linux 상호 참조 홈페이지의 C 코드 일부 행은 예외입니다.
어딘가에 압축 풀기 작동 방식이나 더 나은 .Net 라이브러리 또는 압축/압축 풀기 프로젝트가 있습니까?
는피터
가 나도 실제 documetation을 찾을 수 없습니다 감사합니다. 그래서 나는 근원을 연구하는 것에 의지해야했다. http://www.codeforge.com/read/7074/compr_rtime.c__html
내가 알고있는 것은 이것이다. Rtime 압축 데이터는 바이트 쌍으로 인코딩됩니다. 첫 번째 항목은 데이터 바이트이고 두 번째 항목은 반복 카운터입니다.
Rtime 알고리즘은 입력 데이터를 한 번에 한 바이트 씩 반복합니다. 은 현재 바이트의 마지막 발생 위치에 1을 더한 위치를 기억합니다. 이 'backpos'를 호출합니다. 예를 들어, 'A'가 0 위치에서 마지막으로 보인 경우, 은 1의 역행입니다. 현재 바이트와 백 포지션 사이의 거리는 LZ77-ish 슬라이딩 윈도우를 만듭니다. 그런 다음 Rtime은 다음 입력 Y이트 과 backpos에있는 Y이트를 비교합니다. 일치하면 반복 카운터를 1 씩 증가시킵니다. 차이점이 감지되거나 입력의 끝에 도달 할 때까지 계속됩니다.
Nuff said!
압축 다음 입력이 주어
: 여기 예가
A B B B A B B B A
1) 제 1 입력 바이트,는 A이다 RTIME 저장소 상기 제 1의 첫 번째 항목 같은 쌍의 압축 결과. A의 backpos 이전에 A가 0 인 경우는 을 본 적이 없으므로.
[A] B B B A B B B A
^^
|__|
=?
다음 그것은 backpos에서 바이트 입력 (즉, A 및 B)의 다음의 바이트를 비교한다. 그들은 동일하지 않기 때문에 Rtime은 반복 카운트 을 0으로 사용합니다. 첫 번째 쌍은 (A, 0)입니다.
2) 두 번째 입력 바이트는 B입니다. Rtime은 결과의 두 번째 쌍인 의 첫 번째 항목으로 B를 저장합니다. 이전에 B를 본 적이 없기 때문에 B의 back35는 입니다. 그것은 다음 입력 바이트와 backpos 에서 바이트를 비교하기 위해 계속 :
A [B] B B A B B B A
^ ^
|_____|
=?
그들은 명확하게 동일 아니에요. 따라서 반복 횟수는 다시 0입니다. 따라서 두 번째 결과 쌍은 (B, 0)입니다.
3) 세 번째 바이트가 다시 B.Rtime은 결과의 세 번째 쌍인 의 첫 번째 항목으로 B를 저장합니다.
: 그것은 이전 반복에서 위치 1에서 B가 발생하고 있기 때문에, backpos 2.그것은 다음 입력 바이트 backpos (인덱스 2)의 바이트를 비교 간다 지금 (인덱스 3) 인 반복 횟수가 1 RTIME은 다음의 2 바이트를 비교
A B [B] B A B B B A
^^
|__|
=?
로 설정되도록
A B [B] B A B B B A
^^
|__|
=?
그들은 동일,하지만 그들은이 다르다. 따라서 비교가 중지됩니다 결과의 세 번째 페어는 (B, 1)
입니다. 4) 마지막 반복에서 성공적으로 반복했기 때문에 네 번째 입력 바이트 이 이미 적용되었으며 이제 우리는 다섯 번째 바이트. 이 첫 번째 반복에서 위치 0에서 A A가 발생했습니다 때문에 어느 A. 그래서 네 번째 결과 쌍의 첫 번째 항목입니다 A.입니다 backpos 상황이 재미가 될이 시점에서 1
입니다. 다음 4 번의 비교는 을 성공적으로 수행하며 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
^ ^
|___________|
=?
그래서 네 번째와 마지막 결과 쌍은 (A, 4)입니다. 결과는 모두 (A, 0) (B, 0) (B, 1) (A, 4)입니다.
원래 입력이 9 바이트 인 반면 "단지"8 바이트가 필요합니다.
감압
압축 해제 정확히 동일하게 작동하지만 역순으로한다. 위의 결과가 주어진다면 :
(A, 0) (B, 0) (B, 1) (A, 4).
1) 첫 번째 쌍의 첫 번째 값은 A입니다. 따라서 바로 첫 번째 위치에 A를 넣을 수 있습니다. 결과는 입니다. 반복 횟수가 0이므로이 반복이 수행됩니다. (A)의 Backpos 번째 쌍 우리는 결과의 제 위치에 넣어 B. B 포함) 0
compressed: [A, 0](B, 0)(B, 1)(A, 4) decompressed: [A]
2이다. 반복 횟수가 0이므로이 반복도 수행됩니다. B의 Backpos 세 번째 쌍 우리는 결과의 제 위치에 넣어 B. B 포함) 1.
compressed: (A, 0)[B, 0](B, 1)(A, 4) decompressed: A [B]
3이다. 이 경우 반복 횟수는 입니다. 그래서 결과의 끝에 backpos (이 시점에서 여전히 1 임)에 바이트를 추가합니다. B의 Backpos이어서 네번째 쌍 우리는 제 위치 결과에 A A 넣어 A. 포함 2.
compressed: (A, 0)(B, 0)[B, 1](A, 4) decompressed: A B [B]+B+
4)로 설정. 반복 카운트 은 4입니다. 따라서 backpos에서 시작하는 4 바이트 (이 시점에서 여전히 0입니다)를 압축 해제 된 스트림의 끝에 추가합니다.
compressed: (A, 0)(B, 0)(B, 1)[A, 4] decompressed: A B B B [A]+A++B++B++B+
그리고 우리는
희망이 조금 도움이 : 완료됩니다.
입력에 중복성이 없으면 Rtime은 원본보다 작은 결과를 생성하지 않습니다. C 구현의 주석에서 나는 Rtime이 이미 gzipped 이미지를 더 압축하는 데에만 사용된다는 것을 읽었다. 아마도 gzip에는 중복이 거의 없을 것입니다. Rtime이 실제로 얼마나 자주 개선 된 결과를 가져올 지 궁금합니다.
원본 C 소스를 C#으로 대체하여 표현한 것입니다. 어떤 목적으로 작동해야합니다.
using System.IO;namespace 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; } }
}