Menggagalkan kompresi LZMA2

11

Tujuan

Buat program atau pasangan program yang secara kolektif mengganggu dan memperbaiki file dengan maksud mencegah LZMA2 bekerja secara efektif. Mengganggu dan memperbaiki rutinitas harus bersifat timbal balik, sehingga Anda dapat memulihkan file asli dengan tepat.

Target

Metode Kompresi

  • Ubuntu / terkait: xz -kz5 <infile>
  • Windows: 7z.exe a -txz -mx5 <outfile> <infile>
  • Lainnya: Gunakan kompresor LZMA2 dengan tingkat kompresi 5 yang mengkompres pekerjaan Shakespeare ke 1570550 byte ± 100 byte.

Mencetak; jumlah (semuanya dalam byte, ls -latau diritu):

  • Ukuran program (apa pun yang diperlukan secara kolektif untuk memulihkan "kerusakan" / memperbaiki file)
  • Perbedaan ukuran (absolut) antara:
    • Karya Shakespeare yang dikumpulkan dan salinan modifikasi Anda (tidak terkompresi).
    • Foto mentah dan salinan Anda yang dimodifikasi (tidak dikompresi).
  • Perbedaan ukuran atau 0, mana yang lebih besar antara:
    • Karya Shakespeare terkumpul mentah dikurangi salinan LZMA2 terkompresi yang dimodifikasi.
    • Foto mentah dikurangi salinan terkompresi Anda, LZMA2.

Contoh

Skor buruk, malas bermain golf, tapi Python 2.x yang patuh contoh:

import sys
x = 7919 if sys.argv[1] == 'b' else -7919
i = bytearray(open(sys.argv[2], 'rb').read())
for n in range(len(i)):
    i[n] = (i[n] + x*n) % 256
o = open(sys.argv[2]+'~', 'wb').write(i)

Berlari ...

$ python break.py b pg100.txt 
$ python break.py f pg100.txt~ 
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ python break.py b Glühwendel_brennt_durch.jpg 
$ python break.py f Glühwendel_brennt_durch.jpg~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~
$ xz -kz5 Glühwendel_brennt_durch.jpg~
$ ls -ln
-rw-rw-r-- 1 2092 2092     194 May 23 17:37 break.py
-rw-rw-r-- 1 2092 2092 1659874 May 23 16:20 Glühwendel_brennt_durch.jpg
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~
-rw-rw-r-- 1 2092 2092 1659874 May 23 17:39 Glühwendel_brennt_durch.jpg~~
-rw-rw-r-- 1 2092 2092 1646556 May 23 17:39 Glühwendel_brennt_durch.jpg~.xz
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:24 pg100.txt
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~
-rw-rw-r-- 1 2092 2092 5589891 May 23 17:39 pg100.txt~~
-rw-rw-r-- 1 2092 2092 3014136 May 23 17:39 pg100.txt~.xz

Skor

  • = 194 + abs (5589891 - 5589891) + maks (5589891 - 3014136, 0) + abs (1659874 - 1659874) + maks (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2.589.267 byte. Buruk, tetapi tidak melakukan apa pun pada file menghasilkan skor 4.635.153 byte.

Klarifikasi

Ini golf, jadi Anda mencoba meminimalkan skor Anda. Saya tidak yakin apakah komentarnya menunjukkan lubang yang sah dalam penilaian saya atau apakah itu karena saya membuatnya terlalu rumit. Bagaimanapun, Anda menginginkan yang TERKECIL :

  • Kode sumber
  • perbedaan antara file termodifikasi yang tidak terkompresi dan file asli (mis. jika Anda memodifikasinya dengan menambahkan satu triliun pada akhirnya, skor Anda hanya naik satu triliun byte)
  • perbedaan antara file termodifikasi yang dikompresi dan file asli (mis. semakin file tidak dapat dikompres, semakin tinggi skor Anda). File yang sangat tidak bisa dimampatkan yang tumbuh sedikit atau tidak sama sekali akan mendapat skor 0.
code-challenge compression Nick T
sumber
2
Jawaban trolling: Langkah 1 - cari tahu berapa banyak ruang disk kosong yang Anda miliki kemudian bagi dengan ukuran file untuk mendapatkan N. Langkah 2 - tambahkan file ke dirinya sendiri N kali dan tambahkan angka N. Langkah 3 - sadari ada tidak ada ruang yang tersisa untuk mengkompres file tetapi berakhir dengan perbedaan absolut dalam ukuran file beberapa terrabytes (atau lebih) .... [Untuk membalikkan, baca N dari ujung file dan perkecil ukuran file menjadi 1 / Nth ukurannya. ]
MT0
@ MT0: Ah saya pikir solusinya adalah perbedaannya tidak harus absolut. Jika file Anda yang dimodifikasi lebih besar yang seharusnya mengurangi poin.
Claudiu
@ MT0 jika Anda memodifikasi file untuk membuatnya menjadi terabyte besar, maka skor Anda akan menjadi 1 terabyte ... sangat buruk ketika Anda mencoba untuk bermain golf.
Nick T
@ MT0 Saya menambahkan klarifikasi ke posting, apakah itu membantu?
Nick T
2
Satu berdalih. Kompresor dapat membuat file yang lebih besar jika t terutama tidak dapat dimampatkan. Dalam hal ini Anda harus dihargai, tidak dihukum, bukan?
Claudiu

Jawaban:

8

Python, skor = 120

import sys,hashlib
i=0
for c in sys.stdin.read():sys.stdout.write(chr(ord(c)^ord(hashlib.md5(str(i)).digest()[0])));i+=1

Membuat pad sekali pakai menggunakan md5 dalam mode penghitung . mengoreksi file dengan itu. Ini memiliki keuntungan bahwa file asli dan yang rusak memiliki ukuran yang sama, dan bahwa pengganggu dan pemecah masalah adalah program yang sama.

File terganggu terkompresi lebih besar dari aslinya.

Keith Randall
sumber
Saya menyesuaikan skor sehingga jika file zip lebih besar dari rekan aslinya, Anda tidak dihukum dan mereka hanya mendapat skor 0. Tidak yakin ke mana perbedaannya untuk file Anda, tetapi Anda mungkin ingin memperbarui skor
Nick T
@NickT: diperbarui.
Keith Randall
8

C, 51 = 51 + 0 + 0 + 0 + 0

main(c){for(;c=~getchar();putchar(~c^rand()>>23));}

Di bawah trik golf , program ini loop untuk setiap byte dalam input standar, dan melakukan eksklusif-atau dengan pad tak terbatas dari rand (). Saya menguji ini dengan rand () di libc dari OpenBSD 5.5.

Pemakaian:

./scramble <orig >scrambled
./scramble <scrambled >orig.copy

Untuk menguji program saya, saya menulis script script test.sh (57 baris) untuk mengkompilasi program saya dan menghitung skor saya.

$ sh test.sh
[1/4] Compiling scramble...
/tmp//ccbcB43x.o(.text+0x6): In function `main':
: warning: rand() isn't random; consider using arc4random()
[2/4] Scrambling files...
[3/4] Compressing scrambled files...
[4/4] Checking descrambler...
SCORE: 51=51+0+0+0+0
You may wish to rm -rf tmp.9Tjw89dgCs
$ ls -l tmp.9Tjw89dgCs/
total 43032
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.cp
-rw-r--r--  1 kernigh  kernigh  1659874 May 28 17:23 filament.jpg.sc
-rw-r--r--  1 kernigh  kernigh  1660016 May 28 17:23 filament.jpg.sc.xz
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.cp
-rw-r--r--  1 kernigh  kernigh  5589891 May 28 17:23 pg100.txt.sc
-rw-r--r--  1 kernigh  kernigh  5590232 May 28 17:23 pg100.txt.sc.xz
-rwxr-xr-x  1 kernigh  kernigh     8564 May 28 17:23 scramble

Catatan tentang rand () dan pergeseran kanan

Algoritma kompresi apa pun tidak dapat mengompresi data acak. Saya dapat menyamarkan pg100.txt dan filament.jpg sebagai data acak jika saya mengacaknya dengan stream cipher .

Ide pertama saya adalah membuat-atau plaintext dengan pad untuk membuat ciphertext , kemudian menyimpan ciphertext dan pad di file yang diacak. Ini akan meningkatkan ukuran file, dan meningkatkan skor saya. Pilihan yang jelas adalah menggunakan pad yang sama untuk setiap file, dan hanya menyimpan ciphertext dalam file yang diacak. Jika saya hanya memanggil rand (), ia menggunakan seed default 1 dan membuat pad yang sama setiap waktu.

OpenBSD 5.5 mendefinisikan rand () di stdlib.h dan rand.c :

/* from stdlib.h */
#define RAND_MAX    0x7fffffff

/* from rand.c */
static u_int next = 1;

int
rand_r(u_int *seed)
{
    *seed = *seed * 1103515245 + 12345;
    return (*seed % ((u_int)RAND_MAX + 1));
}

int
rand(void)
{
    return (rand_r(&next));
}

Ini adalah generator kongruensial linier . Kelemahan besar adalah bahwa bit rendah memiliki periode pendek. Bit pertama memiliki periode 2: jika Anda melempar koin rand()&1, itu akan menjadi kepala, ekor, kepala, ekor, dan sebagainya. Bit ke-n memiliki periode 2 n . Ada 31 bit, sehingga seluruh urutan memiliki periode 2 31 .

LZMA2 dapat menemukan pola dalam waktu singkat dan mengompresnya. Kode terpendek ~c^rand()mengambil 8 bit yang rendah dan tidak mencegah kompresi. Pergeseran yang tepat dalam ~c^rand()>>9membantu, tetapi tidak cukup. Saya menggunakan ~c^rand()>>23.

  • ~c SCORE: 4227957 = 40 + 0 + 0 + 4019391 + 208526
  • ~c^rand() SCORE: 2474616 = 47 + 0 + 0 + 2463735 + 10834
  • ~c^rand()>>9 SCORE: 350717 = 50 + 0 + 0 + 350667 + 0
  • ~c^rand()>>23 SCORE: 51 = 51 + 0 + 0 + 0 + 0
kernigh
sumber
5

BrainFuck : 129 (129 + 0 + 0 + 0 + 0) *

random.bf (umpan baris ditambahkan untuk dibaca)

,+[->>>>++[<++++++++[<[<++>-]>>[>>]+>>+[-[->>+<<<[<[<<]<
+>]>[>[>>]]]<[>>[-]]>[>[-<<]>[<+<]]+<<]<[>+<-]>>-]<[-<<+
>>]<<.,+[->]>>>]]

Untuk membuat unrandom.bfAnda perlu mengubah + terakhir di baris kedua.

Sebagian besar kode didasarkan pada Rule30 generator nomor acak berbasis Daniel B Cristofani yang disesuaikan untuk menambahkan nomor ke setiap input dan untuk mengakhiri ketika tidak ada lagi input.

* Saya sudah menguji byte yang telah diproses sejauh ini 212992 (diproses setelah 12 jam) dan kedua file berubah menjadi file terkompresi 213064. Saya kira itu mungkin dilakukan pada akhir minggu untuk mengetahui dengan pasti tetapi saya tidak ingin menunggu dengan posting. Saya akan memperbarui skor jika itu salah, tetapi pertahankan solusinya karena Rule30 mendukung!

Trivia: Aturan 30 ditemukan oleh Stephen Wolfram pada tahun 1983 dan menurut Wikipedia digunakan untuk menghasilkan bilangan bulat acak di Mathematica.

Kompilasi dan berjalan:

Ini menggunakan waktu dan ruang eksponensial (lebih dari 32 lebih banyak sel per char diproses) sehingga memerlukan runtime BrainFuck yang memiliki setidaknya 178.876.517 sel untuk menyandikan file Shakespear, tidak memperlakukan non ascii sebagai unicode, memiliki sel lebih dari 8 bit dan menggunakan -1 sebagai eof (berbeda antara 255 dan -1). Saya biasanya menggunakan penerjemah orang lain, tetapi kali ini saya harus menjadi penyambung dan mempromosikan sendiri:

jitbf --eof -1 -b 16 -c 200000000 random.bf < pg100.txt > pg100.txt.ran
jitbf --eof -1 -b 16 -c 200000000 random.bf < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg.ran

jitfb mengkompilasi BrainFuck untuk mengoptimalkan C dan menyalahgunakan perl Inline :: C untuk menjalankannya. Ini bundel dengan kompiler Extended BrainFuck saya . Dengan ukuran dan lebar sel dalam argumen itu akan mengalokasikan sekitar 400MB.

Sylwester
sumber
3

CJam, 22 byte

G,~q{5$H$+255%_@^o}/];

Ini menggunakan generator Fibonacci lagged dengan relasi pengulangan s n = (s n-5 + s n-16 )% 255 (yang saya pilih secara tidak sengaja, tetapi tetap berfungsi) dan seed trivial untuk menghasilkan aliran byte pseudo-acak byte , yang kemudian XOR dengan input.

Saya telah menguji kode saya dengan CJam 0.6 , yang diterbitkan pada 1 Mei 2014.

Bagaimana itu bekerja

G,~                    e# Dump 0, 1, ... and 15 on the stack.
   q                   e# Read from STDIN.
    {             }/   e# For each character in the input.
     5$H$              e# Copy the sixth and 19th element from the stack.
         +255%         e# Push their sum modulo 255.
              _@       e# Duplicate and rotate the character on top.
                ^o     e# XOR and print.
                    ]; e# Clear the stack.

Skor

$ LANG=en_US
$ alias cjam='java -jar /usr/local/share/cjam/cjam-0.6.jar'
$ cjam thwart.cjam < pg100.txt > pg100.txt~
$ cjam thwart.cjam < pg100.txt~ > pg100.txt~~
$ diff -s pg100.txt pg100.txt~~
Files pg100.txt and pg100.txt~~ are identical
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg > Gluehwendel_brennt_durch.jpg~
$ cjam thwart.cjam < Gluehwendel_brennt_durch.jpg~ > Gluehwendel_brennt_durch.jpg~~
$ diff -s Gluehwendel_brennt_durch.jpg Gluehwendel_brennt_durch.jpg~~
Files Gluehwendel_brennt_durch.jpg and Gluehwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 pg100.txt~ Gluehwendel_brennt_durch.jpg~
$ wc -c thwart.cjam pg100.txt* Gluehwendel_brennt_durch.jpg*
      22 thwart.cjam
 5589889 pg100.txt
 5589889 pg100.txt~
 5589889 pg100.txt~~
 5590232 pg100.txt~.xz
 1659874 Gluehwendel_brennt_durch.jpg
 1659874 Gluehwendel_brennt_durch.jpg~
 1659874 Gluehwendel_brennt_durch.jpg~~
 1660016 Gluehwendel_brennt_durch.jpg~.xz
28999559 total
Dennis
sumber
3

PHP, 117 + 0 + 0 + 0 + 0 = 117

Karena apakah Anda benar-benar akan mempercayakan tugas mengatur data Anda di luar pengenalan ke bahasa lain?

<?=substr(gmp_export(gmp_invert(2*gmp_import($s=stream_get_contents(STDIN))+1,$m=2*gmp_pow(256,strlen($s)))/2+$m),1);

Sementara semua solusi lain didasarkan pada konstruksi "aman" seperti "generator nomor acak" atau "kriptografi tingkat militer", yang satu ini hanya menafsirkan string sebagai mewakili angka ganjil panjang modulo, dan menghitung invers modular mereka .

Demo:

$ php thwart.php < 100.txt.utf-8 > 100.txt.utf-8~
$ php thwart.php < 100.txt.utf-8~ > 100.txt.utf-8~~
$ diff -s 100.txt.utf-8 100.txt.utf-8~~
Files 100.txt.utf-8 and 100.txt.utf-8~~ are identical
$ php thwart.php < Glühwendel_brennt_durch.jpg > Glühwendel_brennt_durch.jpg~
$ php thwart.php < Glühwendel_brennt_durch.jpg~ > Glühwendel_brennt_durch.jpg~~
$ diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg~~
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg~~ are identical
$ xz -kz5 100.txt.utf-8~ Glühwendel_brennt_durch.jpg~
$ wc -c *
 5589889 100.txt.utf-8
 5589889 100.txt.utf-8~
 5590232 100.txt.utf-8~.xz
 5589889 100.txt.utf-8~~
 1659874 Glühwendel_brennt_durch.jpg
 1659874 Glühwendel_brennt_durch.jpg~
 1660016 Glühwendel_brennt_durch.jpg~.xz
 1659874 Glühwendel_brennt_durch.jpg~~
     117 thwart.php
28999654 total
Anders Kaseorg
sumber
2

skrip shell, 203

id|gpg --batch --passphrase-fd 0 --personal-compress-preferences Uncompressed $1 $2

Menjalankannya:

% sh break.sh -c pg100.txt                       
% sh break.sh -d pg100.txt.gpg > pg100.txt-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s pg100.txt pg100.txt-original
Files pg100.txt and pg100.txt-original are identical
% sh break.sh -c Glühwendel_brennt_durch.jpg
% sh break.sh -d Glühwendel_brennt_durch.jpg.gpg > Glühwendel_brennt_durch.jpg-original
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: WARNING: message was not integrity protected
% diff -s Glühwendel_brennt_durch.jpg Glühwendel_brennt_durch.jpg-original
Files Glühwendel_brennt_durch.jpg and Glühwendel_brennt_durch.jpg-original are identical
% xz -kz5 Glühwendel_brennt_durch.jpg.gpg 
% xz -kz5 pg100.txt.gpg 
% ls -ln
total 28340
-rw-r--r-- 1 1000 1000      84 May 24 04:33 break.sh
-rw-r--r-- 1 1000 1000 1659874 Jan 19 17:22 Glühwendel_brennt_durch.jpg
-rw-r--r-- 1 1000 1000 1659943 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg
-rw-r--r-- 1 1000 1000 1660084 May 24 04:46 Glühwendel_brennt_durch.jpg.gpg.xz
-rw-r--r-- 1 1000 1000 1659874 May 24 04:46 Glühwendel_brennt_durch.jpg-original
-rw-r--r-- 1 1000 1000 5589891 May 24 03:55 pg100.txt
-rw-r--r-- 1 1000 1000 5589941 May 24 04:43 pg100.txt.gpg
-rw-r--r-- 1 1000 1000 5590284 May 24 04:43 pg100.txt.gpg.xz
-rw-r--r-- 1 1000 1000 5589891 May 24 04:43 pg100.txt-original

Tidak terlalu portabel, tetapi dapat dibuat dengan biaya beberapa byte. Membutuhkan PGP (implementasi dengan OpenSSL juga dimungkinkan). Perbedaan ~ 50 byte antara file yang disandikan dan asli mungkin dapat disimpan.

Mencetak:

84 + abs (1659874 - 1659943) + maks (1659874 - 1660084, 0) + abs (5589891 - 5589941) + maks (5589891 - 5590284, 0) = 203

salinan
sumber
1

Python, skor = 183 + 7 + 6 + 0 + 0 = 196

Skor menghukum Anda karena membuat file benar-benar tidak dapat dikompresi, karena file terkompresi lebih besar dari overhead kompresi. Dengan demikian program saya membuat mereka sedikit kurang dari sama sekali tidak terkompresi:

import sys
from random import randint as J,seed
x=sys.stdin.read()
seed(ord(x[1]))
n=int(2362*J(1,2)**2.359)
sys.stdout.write(x[:n]+''.join(chr(ord(c)^J(0,255))for c in x[n:]))

Hasil:

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat photo.jpg | python break.py > photo.jpg~; cat photo.jpg~ | python break.py > photo.jpg~~; diff photo.jpg photo.jpg~~; xz -kz5 photo.jpg~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ cat pg100.txt | python break.py > pg100.txt~; cat pg100.txt~ | python break.py > pg100.txt~~; diff pg100.txt pg100.txt~~; xz -kz5 pg100.txt~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ ls -l
total 28337
----------+ 1 Laxori mkpasswd     183 2014-05-24 13:43 break.py
----------+ 1 Laxori mkpasswd 5589891 2014-05-23 19:19 pg100.txt
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~
-rw-r--r--+ 1 Laxori mkpasswd 5589884 2014-05-24 13:45 pg100.txt~.xz
-rw-r--r--+ 1 Laxori mkpasswd 5589891 2014-05-24 13:45 pg100.txt~~
----------+ 1 Laxori mkpasswd 1659874 2014-05-23 19:19 photo.jpg
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~
-rw-r--r--+ 1 Laxori mkpasswd 1659880 2014-05-24 13:44 photo.jpg~.xz
-rw-r--r--+ 1 Laxori mkpasswd 1659874 2014-05-24 13:44 photo.jpg~~

Laxori@Laxori-PC /cygdrive/f/Programming/lzkill
$ python
Python 2.5.2 (r252:60911, Dec  2 2008, 09:26:14)
[GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 183 + abs(5589891-5589884) + abs(1659874-1659880)
196
Claudiu
sumber
Dengan aturan saat ini, tidak ada penalti untuk file terkompresi menjadi lebih besar. Apakah aturannya berubah? Jika demikian, perubahan seperti itu tidak adil untuk program ini.
kernigh
@kernigh: Ya mereka berubah setelah saya mempostingnya. Sesungguhnya mereka seharusnya seperti sekarang dari awal.
Claudiu