Dediğiniz gibi LZ77 stili bir format, ancak eşleştiği belirli bir algoritma bulamadım. Sıkıştırılmış veriler, her biri bazı verilerden en az birini veya bazı geri referansları içeren bir dizi blok oluşturur.

Biçim

Bir araya getirdiğim koda dayanarak sıkıştırılmış verinin veri yapısının listesi.

Blok

Her bloğun biçimi aşağıdaki gibidir:

  Bölüm | Uzunluk ----------------------- | ------- Başlık | 1 ila 3 Bayt (başlık açıklamasına bakın) Veri | 0 - 0x1011D (65821) BytesBack referansları | 1 ila 4 Baytın 0 ila 8 kez tekrarlanması (referans açıklamasına bakın)  

Başlık

Başlık aşağıdaki gibidir:

  Bölüm | Uzunluk ----------------------- | ------- Referans Sayısı | 3 bit Veri Uzunluğu | 5 bitEk Veri Uzunluğu | 0 - 2 Bayt  

Geri referansların sayısı, 1'den ( 0b000 ) 8'e kadar bir sayıya izin verecek şekilde, 1 endeksli sayı olarak ilk 3 bit olarak kodlanır ( 0b111 ). 8'den fazla geri referansın gerekli olduğu durumda, 0 veri uzunluğu ayarlanabilir, böylece yalnızca geri referansları içeren birkaç ardışık bloğa sahip olabilirsiniz.

veri uzunluğu sonraki 5 bit olarak kodlanır. Veri uzunluğu 0x1E (30) 'dan azsa, doğrudan başlığın ilk 5 bitine kodlanır. 0x1E arasındaysa ve 0x11E (286) daha sonra tek bir ek bayt kullanılacaktır, bu bayt verinin uzunluğu olmalıdır - 0x11E . 0x11E ve 0x1011D (65821) daha sonra 16 bitlik bir sayı olarak iki ek bayt kullanılır ve bu veri uzunluğu olmalıdır - 0x11E .

Veri uzunluğu mümkün olan maksimumsa ( 0x1011D ), o zaman geri referansların sayısı o kadar azaltılır ne, 0 geri referansa izin verir. Bu, arka referanslar olmadan ardışık veri bölümlerine izin verir.

Geri referans

Geri referansların biçimi, başlığınkine benzer:

  Bölüm | Uzunluk ----------------------- | ------- Veri Uzunluğu | 3 bit Veri Mesafesi | 5 bitEk Veri Uzunluğu | 0 ila 1 Bayt Ek Uzaklık | 0 ila 2 Bayt  

Referansın başvurduğu veri uzunluğu (bayt cinsinden), 0 - 7 uzunluğa izin verecek şekilde ilk 3 bit olarak kodlanır. Uzunluk 7'den büyükse daha sonra bu 3 bit 0 olarak ayarlanır ve - 7 uzunluğunu içeren ek bir bayt eklenir, bu 262 bayta kadar uzunluklara izin verir.

Mesafe, geri bayt cinsinden geri referansın konumunu temsil eder. sıkıştırılmış verilerin mevcut sonundan. Mesafe ve ek mesafe baytları, başlıktaki Veri Uzunluğu ile aynı şekilde hesaplanır.

Ayarlandığında, her geri referans hesaplanan veri uzunluğunu current_position - distance - 1'den bayt olarak kopyalar. çıkış akışına.

Uzunluğun ve ek uzunluğun 0 olarak ayarlandığı özel bir geri referans durumu vardır. Bu, akışın sonunu belirtir ve sıkıştırıcı geri dönecektir.

Akıl Yürütme

Bir bloğun genel biçimi koddan makul bir şekilde anlaşılıyor, ancak sihirli sayıların arkasındaki mantığı çözene kadar gerçekten mantıklı değildi.

Buradaki ilginç şey, uzaklık = 0x1011D özel durumuydu. Bu mesafeyi kontrol eden şubeye ulaşmak için, ilk uzaklık = temp >> 3; kod> 0x1E 'den büyük olmalıdır, bu nedenle 0x1F olmalıdır, çünkü 0x1E üzerindeki hiçbir değer tem p . Bu bilgilerle, sonraki 2 baytın gerekli değerlerini hesaplayabiliriz ( a ve b):

  0x1011D = 0x1F + a + (b << 8) + 0xFF0x1001E = 0x1F + a + (b << 8)
0x0FFFF = a + (b << 8)  

a ve b 8 bit sayılar olduğundan, her ikisinin de olması gerekir 0xFF .Böylece 0x1011D o noktadaki uzaklık için olası en büyük değerdir.

uzunluğunun nedeni-- Koşullu ile ilişkili görünür hale gelir: Bu, görüntüler veya diğer yetersiz sıkıştırılabilir veriler gibi durumlarda kullanılmak üzere geri referans içermeyen ham veri bloklarına izin verir.

Bunun dışında, sayı aralığı Veri Uzunluğunun desteklediği, temp 'in 0b11111 ??? ve 0b11110 ??? olarak ayarlanmasının sonucu dikkate alınarak ve Aşağıdaki iki baytın maksimum ve minimum değerleri.

Blok başlık formatını anladıktan sonra, geri referans formatını anlamak oldukça kolaydır, ana sorun uzunluk = 0 aşağıdaki 0 baytı akışı sona erdirir.

Sayma yazma rpart sıkıştırma algoritması

Dosyaların orijinal dosyalarla aynı alana sığmasına ihtiyacınız yoksa, kendi dosyalarınızı "sıkıştırmanın" en kolay yolu, formatın gerçek sıkıştırma özelliklerini göz ardı etmektir ve Akış sinyalinin sonu olan tek bir geri referansa sahip olacak son bloğa kadar maksimum boyutta veri blokları oluşturmanın en azını yapın. Bu hızlı bir uygulama izler.

  #include <cstring> # <fstream> # (uint8_t *, uint8_t sıkıştırılmış * decompressed) <iterator>unsigned int sıkıştırmasını include <string> # <iostream> # <vector> # <deque> # include include { uint32_t uzaklık, uzunluk, i, j; uint8_t temp, * sıkıştırılmış_ptr = sıkıştırılmış, * sıkıştırılmış_ptr = sıkıştırılmış, * geriye doğru_ptr = NULL; while (1) {temp = * (sıkıştırılmış_ptr ++);
uzunluk = (temp & 7) + 1; mesafe = temp >> 3; eğer (mesafe == 0x1E) uzaklık = * (sıkıştırılmış_ptr ++) + 0x1E; else if (mesafe > 0x1E) {mesafe + = * sıkıştırılmış_ptr; mesafe + = (* (++ compressed_ptr) << 8) + 0xFF; compressed_ptr ++; eğer (mesafe == 0x1011D) uzunluk--; } if (mesafe! = 0) {std :: memcpy (sıkıştırılmış_tr, sıkıştırılmış_tr, mesafe); decompressed_ptr + = uzaklık; compressed_ptr + = mesafe; } for (i = uzunluk; i > 0; i--) {temp = * (compressed_ptr ++); uzunluk = temp & 7; mesafe = temp >> 3; eğer (uzunluk == 0) {uzunluk = * (sıkıştırılmış_ptr ++); eğer (uzunluk == 0) {return (uintptr_t) decompressed_ptr - (uintptr_t) sıkıştırılmış; } uzunluk + = 7; } if (mesafe == 0x1E) uzaklık = * (sıkıştırılmış_ptr ++) + 0x1E; else if (mesafe > 0x1E) {mesafe + = * sıkıştırılmış_ptr; mesafe + = (* (++ compressed_ptr) << 8) + 0xFF; compressed_ptr ++; } backwards_ptr = decompressed_ptr - mesafe - 1; for (j = uzunluk; j > 0; j--) * (sıkıştırılmış_ptr ++) = * (geriye doğru_ptr ++); }}} std :: vector<uint8_t> sıkıştır (const std :: vector<uint8_t>& input) {const uint32_t max_distance = 0x1011D; std :: vector<uint8_t> çıktı; auto input_it = input.begin (); // Kalan_input = std :: distance (input_it, input.end ());
while (kalan_ giriş > maks_distance) {output.push_back (0xF8); output.push_back (0xFF); output.push_back (0xFF); std :: copy (input_it, input_it + maks_distance, std :: back_inserter (çıktı)); input_it + = max_distance; kalan_input = std :: mesafe (input_it, input.end ()); } // Kalan veriyle son bir blok ekleyin if (kalan_input > 0x11D) {output.push_back (0xF8); const uint16_t başlık_bayt = kalan_ girdi - 0x11E; output.push_back (başlık_baytları & 0xFF); output.push_back (başlık_baytları >> 8); std :: copy (input_it, input.end (), std :: back_inserter (çıktı)); } else if (kalan_ girdi > 0x1D) {output.push_back (0xF0); const uint8_t başlık_baytı = kalan_ girdi - 0x1E; output.push_back (başlık_baytı); std :: copy (input_it, input.end (), std :: back_inserter (çıktı)); } else {const uint8_t header_byte = kalan_giriş << 3; output.push_back (başlık_baytı); std :: copy (input_it, input.end (), std :: back_inserter (çıktı)); } // Çıkış akışını sonlandırmak için özel bir durum 0 uzunluk geri referansı ekleyin ..push_back (0x00); output.push_back (0x00); dönüş çıkışı;} int main (int argc, char * argv []) {std :: deque<std :: string> değiştirgeler (argv, argv + argc); args.pop_front (); if (args.empty ()) {std :: cerrah << "Girdi dosyası yok!" << std :: endl; dönüş 1; } for (const auto& dosyaadı: args) {std :: ifstream in_file (dosyaadı, std :: ios :: in | std :: ios :: ikili); if (! in_file.good ()) {std :: cerr << "Hatalı girdi dosyası:" << dosya adı << std :: endl; dönüş 1; }
std :: cout << "Sıkıştırılıyor" << dosya adı << std :: endl; std :: vector<uint8_t> input ((std :: istreambuf_iterator<char> (in_file)), (std :: istreambuf_iterator<char> ())); otomatik sıkıştırılmış = sıkıştır (giriş); std :: cout << "" << input.size () << "den" << compressed.size () <<'den sıkıştırılmıştır; const std :: string new_filename = dosyaadı + ".compres"; std :: ofstream out_file (yeni_dosyaadı); out_file.write ((char *) compressed.data (), compressed.size ()); out_file.close (); std :: cout << "<< olarak kaydedildi new_filename << std :: endl; const int buffer_length = 2000000; uint8_t arabellek [arabellek_uzunluğu]; const int size = sıkıştırmayı açma (arabellek, sıkıştırılmış.data ()); std :: vector<uint8_t> yeniden oluşturuldu; regenerated.assign (arabellek, arabellek + boyut); if (reenerated == input) std :: cout << "Yeniden oluşturulan dosya orijinalle eşleşir." << std :: endl; else std :: cout << "Yeniden oluşturulmuş dosya orijinali ile eşleşmiyor!" << std :: endl; } return 0;}  

Derleme: clang ++ --std = c ++ 14 -o fake_compress fake_compress.cpp

Ve şunu çalıştırın:

  $ ./fake_compress havok.xmlSıkıştırılıyor havok.xml 137261'den 137272'ye sıkıştırıldıHavok.xml.compres olarak kaydedildi Yenilenen dosya orijinalle eşleşiyor.  

Çoğu genel amaçlı LZ77 benzeri biçimler, tek tek gerçek karakterlerin verimli bir şekilde eklenmesi ve değişmez harflerin ve geriye dönük referansların sıralanması için optimize edilmiştir - bu, doğal dil metninde ve metin benzeri ikili dosyalarda iyi sıkıştırma oranları elde etmek için yararlıdır veriler (yürütülebilir kod). Ayrıca, rastgele boyutlardaki dosyaları veya akışları işlemek için kayan bir sözlük penceresi kavramına da sahiptirler.

Sorunuzdaki rutin, özellikle bellek içi veriler için uyarlanmış bir formatı işliyor gibi görünüyor (kayan penceresi) çok sayıda (arka arkaya 8'e kadar) açılmış arabelleğe birbirini izleyen referanslarla, arada sırada kopyalanması gereken uzun dizelerle birlikte.

Sıkıştırılmış akışa karakter eklemenin yalnızca iki yolu olduğunu unutmayın: memcpy çağrısı kullanarak değişmez kopyalama ve geriye dönük işaretçiyi kullanarak bir döngü içinde kopyalama. Başka bir deyişle, bu iki işlem modu "sıkıştırılmış akıştan (oldukça uzun) bir sözlüğü kopyalamak" ve "sıkıştırılmış akıştan sözlüğe referansları okumak ve sözlükten dizeleri kopyalamaktır". Bireysel değişmez karakterler için özel bir hüküm yoktur.

LZ77 sıkıştırma algoritmasının herhangi bir basit uygulaması (bir karakter dizesinin bir simge akışına "değişmez karakter" veya "uzaklık / uzunluk" işlevi) işe yarar. . Ardından, bu simgeleri formatın sınırlamasına göre paketlemek için bir program yazabileceksiniz (0x1011D sihirli değerine dikkat edin).

Alternatif olarak, ortam boyutuyla sınırlı olma ihtimaliniz düşük olduğundan, herhangi bir gerçek sıkıştırma yapma ihtiyacını ortadan kaldırabilirsiniz (sıkıştırma düzeyi 0'ın analoğu). Amaçlarınız için, tüm verileri bir dizi uzun değişmez değerler olarak temsil etmek, değişmez dizenin uzunluğu için "uzaklık" alanını kullanmak ve aşağıdaki sözlük referanslarının olmadığını belirtmek için "uzunluk" alanını 0 olarak ayarlamak yeterli olabilir. değişmez dize. Veriler tükenene kadar tekrarlayın.