Сжатие rtime, используемое в jffs2
В проекте C# я должен прочитать образ файловой системы jffs2. Одним из алгоритмов сжатия, используемых в jffs2, является "rtime".
Я не нашел никакой информации об этом методе сжатия "rtime", за исключением некоторой строки кода C на домашней странице перекрестных ссылок linux.
Есть ли где-нибудь описание, как работает декомпрессия или, что еще лучше, библиотека.Net или проект для сжатия / декомпрессии?
Спасибо
Питер
2 ответа
Я не смог найти никакой реальной документации. Поэтому мне пришлось прибегнуть к изучению источника по адресу http://www.codeforge.com/read/7074/compr_rtime.c__html
Вот что я понял. Сжатые данные Rtime кодируются в байтовых парах. Первый элемент - это байт данных, а второй элемент - счетчик повторений.
Алгоритм Rtime перебирает входные данные по одному байту за раз. Он запоминает позицию последнего вхождения текущего байта плюс один. Это называется "backpos". Так, например, если "A" последний раз видели в позиции 0, его обратные позиции были бы равны 1. Расстояние между позициями текущего байта и обратных позиций создает вид скользящего окна LZ77-иша. Затем Rtime сравнивает следующий входной байт с байтом в backpos. Если они идентичны, счетчик повторений увеличивается на единицу. Это продолжается до тех пор, пока не будет обнаружена разница или не будет достигнут конец ввода.
Достаточно! Вот пример:
компрессия
Учитывая следующий вход:
ABBBABBBA
1) Первый входной байт - это A, поэтому Rtime сохраняет A в качестве первого элемента первой пары сжатого результата. Так как он никогда не видел A, прежде чем обратная точка A равна нулю.
[A] BBBABBBA ^ ^ | __ | знак равно
Затем он сравнивает байт в backpos и следующий байт ввода (а именно A и B). Поскольку они не совпадают, Rtime использует счетчик повторений, равный нулю. Итак, первая пара (A, 0).
2) Второй входной байт представляет собой B. Rtime сохраняет B в качестве первого элемента второй пары результата. Так как он никогда раньше не видел B, обратная сторона B также равна нулю. Далее идет сравнение байта в backpos со следующим входным байтом:
A [B] BBABBBA
^ ^
| _____ |
знак равноОни явно не равны. Таким образом, число повторов снова равно нулю. Следовательно, вторая пара результатов - (B, 0).
3) Третий байт снова равен B. Rtime сохраняет B как первый элемент третьей пары результата. Так как он встретил B в позиции 1 на предыдущей итерации, backpos теперь равен 2.
Далее выполняется сравнение байта в backpos (индекс 2) со следующим входным байтом (индекс 3):
AB [B] BABBBA
^ ^
| __ |
знак равноОни равны, поэтому число повторов установлено на 1.
AB [B] BABBBA
^ ^
| __ |
знак равноRtime сравнивает следующие два байта, но они разные. Таким образом, сравнение останавливается и третья пара результата (B, 1)
4) Поскольку у нас было успешное повторение на последней итерации, четвертый входной байт уже покрыт, и теперь мы можем продолжить с пятого байта. Который является А. Итак, первый элемент четвертой пары результатов - это А. Поскольку он встретил А в позиции 0 на первой итерации, обратное значение равно 1.
В этот момент вещи становятся интересными. Следующие четыре сравнения пройдут успешно, и Rtime должен быть остановлен, потому что он достиг конца ввода.
A B B B [A] B B B A
^ ^
|___________|
знак равно
ABBB [A] BBBA
^ ^
| ___________ |
знак равно
ABBB [A] BBBA
^ ^
| ___________ |
знак равно
ABBB [A] BBBA
^ ^
| ___________ |
знак равноТаким образом, четвертая и последняя пара результатов - (A, 4). В целом сжатый результат: (A, 0)(B, 0)(B, 1)(A, 4).
Это требует "только" 8 байтов, тогда как исходный ввод был 9 байтов.
декомпрессия
Декомпрессия работает точно так же, но в обратном порядке. Учитывая приведенный выше результат:
(А, 0) (В, 0) (В, 1) (А, 4).
1) Первым значением первой пары является А. Итак, сразу же мы можем поставить А в первую позицию результата. И поскольку количество повторений равно нулю, эта итерация завершена. Backpos of A равен 0.
сжатый: [A, 0](B, 0)(B, 1)(A, 4) распакованный: [A]
2) Вторая пара содержит B. Мы ставим B во второй позиции результата. И поскольку счетчик повторений равен нулю, эта итерация также выполнена. Backpos of B - 1.
сжатый: (A, 0)[B, 0](B, 1)(A, 4) распакованный: A [B]
3) Третья пара содержит B. Мы ставим B на третью позицию результата. И количество повторений в этом случае равно 1. Таким образом, мы добавляем байт в backpos (который все еще равен 1 на данный момент) к концу результата. Backpos из B затем установите на 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] распакованный: A B B B [A]+A++B++B++B+
И мы сделали:)
Надеюсь, это немного поможет.
Если на входе нет большого количества избыточности, Rtime не будет давать результаты, которые меньше, чем оригинал. В комментариях к реализации C я где-то читал, что Rtime используется только для дальнейшего сжатия уже сжатого изображения. Предположительно gzip содержит очень мало избыточностей. Интересно, как часто Rtime действительно дает улучшенные результаты.
Вот более или менее буквальная транскрипция исходного 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; } }
}