Udaremnij kompresję LZMA2

11

Cel

Utwórz program lub parę programów, które wspólnie zakłócają i naprawiają pliki w celu uniemożliwienia efektywnego działania LZMA2. Procedury zakłócania i naprawy muszą być wzajemne, aby można było dokładnie odzyskać oryginalny plik.

Cele

Metody kompresji

  • Ubuntu / powiązane: xz -kz5 <infile>
  • Windows: 7z.exe a -txz -mx5 <outfile> <infile>
  • Inne: Użyj kompresora LZMA2 o poziomie kompresji 5, który kompresuje dzieła Szekspira do 1570550 bajtów ± 100 bajtów.

Punktacja; suma (wszystko jest w bajtach ls -llub dirto):

  • Rozmiar (-y) programu (cokolwiek zbiorowo wymaga, aby odwracalnie „złamać” / naprawić plik)
  • Różnica wielkości (absolutna) między:
    • Surowe zebrane dzieła Szekspira i zmodyfikowana (nieskompresowana) kopia.
    • Nieprzetworzone zdjęcie i zmodyfikowana (nieskompresowana) kopia.
  • Różnica wielkości lub 0, w zależności od tego, która wartość jest większa między:
    • Surowe zebrane dzieła Szekspira pomniejszone o zmodyfikowaną, skompresowaną kopię LZMA2.
    • Nieprzetworzone zdjęcie bez zmodyfikowanej, skompresowanej kopii LZMA2.

Przykład

Słabo punktowany, leniwie golfowy, ale zgodny z Python 2.x przykład:

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)

Bieganie...

$ 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

Wynik

  • = 194 + abs (5589891 - 5589891) + max (5589891 - 3014136, 0) + abs (1659874 - 1659874) + max (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2 589 267 bajtów. Źle, ale brak działania na plikach daje wynik 4635153 bajtów.

Wyjaśnienie

To jest golf, więc starasz się zminimalizować swój wynik. Nie jestem pewien, czy komentarze wskazują na uzasadnioną lukę w mojej punktacji, czy też dlatego, że uczyniłem to zbyt skomplikowanym. W każdym razie chcesz NAJMNIEJSZY :

  • kod źródłowy
  • różnica między nieskompresowanym zmodyfikowanym plikiem a plikiem oryginalnym (np. jeśli zmodyfikujesz go przez dodanie bilionów zer na końcu, twój wynik wzrósł o bilion bajtów)
  • różnica między skompresowanym zmodyfikowanym plikiem a plikiem oryginalnym (np. im bardziej pliki są nieściśliwe, tym wyższy wynik). Idealnie nieściśliwy plik, który rośnie nieznacznie lub wcale nie ma wartości 0.
code-challenge compression Nick T.
źródło
2
Trollingowa odpowiedź: Krok 1 - sprawdź, ile masz wolnego miejsca na dysku, a następnie podziel go przez rozmiar pliku, aby uzyskać N. Krok 2 - dołącz plik do siebie N razy i dołącz liczbę N. Krok 3 - uświadom sobie, że jest nie ma już miejsca na kompresowanie pliku, ale kończy się absolutną różnicą w rozmiarach kilku terrabajtów (lub więcej) .... [Aby odwrócić, przeczytaj N na końcu pliku i zmniejsz plik do 1 / N-tej wielkości. ]
MT0
@ MT0: Ach, myślę, że rozwiązaniem jest to, że różnice nie powinny być absolutne. Jeśli zmodyfikowany plik jest większy, należy odjąć punkty.
Claudiu
@ MT0, jeśli zmodyfikujesz plik tak, aby był duży w terabajcie, twój wynik wyniesie 1 terabajt ... całkiem źle, gdy próbujesz grać w golfa.
Nick T
@ MT0 Dodałem wyjaśnienie do wpisu, czy to pomaga?
Nick T
2
Jeden spór. Kompresor może utworzyć większy plik, jeśli t jest szczególnie nieściśliwy. W takim przypadku powinieneś zostać nagrodzony, a nie ukarany, nie?
Claudiu

Odpowiedzi:

8

Python, wynik = 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

Tworzy jednorazową podkładkę przy użyciu md5 w trybie licznika . xors plik z nim. Ma to tę zaletę, że oryginalne i uszkodzone pliki mają ten sam rozmiar oraz że program przerywający i naprawiający to ten sam program.

Skompresowane, uszkodzone pliki są większe niż oryginały.

Keith Randall
źródło
Skorygowałem punktację, więc jeśli spakowane pliki są większe niż ich oryginalne odpowiedniki, nie zostaniesz ukarany i po prostu zdobędziesz 0. Nie wiem, w jaki sposób różnica była dla twoich plików, ale możesz chcieć zaktualizować wynik
Nick T
@NickT: zaktualizowano.
Keith Randall
8

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

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

Pod sztuczkami golfa program ten zapętla każdy bajt na standardowym wejściu i robi wyłączność - lub z nieskończonym padem od rand (). Przetestowałem to za pomocą rand () w libc OpenBSD 5.5.

Stosowanie:

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

Aby przetestować mój program, napisałem skrypt powłoki test.sh (57 linii) w celu skompilowania programu i obliczenia wyniku.

$ 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

Uwagi na temat rand () i prawej zmiany

Każdy algorytm kompresji nie może kompresować losowych danych. Mogę ukryć pg100.txt i filament.jpg jako dane losowe, jeśli zaszyfruję je za pomocą szyfru strumieniowego .

Moim pierwszym pomysłem było wyłącznym-lub zwykłego tekstu z podkładką do wprowadzania tekstu zaszyfrowanego , a następnie przechowywać zarówno szyfrogram i pad w kodowanym pliku. Zwiększy to rozmiar pliku i zwiększy mój wynik. Oczywistym wyborem jest użycie tego samego padu dla każdego pliku i zapisanie tylko tekstu zaszyfrowanego w zaszyfrowanym pliku. Jeśli po prostu wywołam rand (), użyje domyślnego zera 1 i utworzy ten sam pad każdym razem .

OpenBSD 5.5 definiuje rand () w stdlib.h i 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));
}

Jest to liniowy generator kongruencjalny . Wielką wadą jest to, że niskie bity mają krótkie okresy. Pierwszy bit ma okres 2: jeśli rzucisz monetą rand()&1, trafi on w głowy, ogony, głowy, ogony i tak dalej. N-ty bit ma okres 2 n . Jest 31 bitów, więc cała sekwencja ma okres 2 31 .

LZMA2 może znaleźć wzorce w krótkim okresie i je skompresować. Najkrótszy kod ~c^rand()zajmuje niskie 8 bitów i nie zapobiega kompresji. Właściwa zmiana ~c^rand()>>9pomaga, ale niewystarczająco. Używam ~c^rand()>>23.

  • ~c WYNIK: 4227957 = 40 + 0 + 0 + 4019391 + 208526
  • ~c^rand() WYNIK: 2474616 = 47 + 0 + 0 + 2463735 + 10834
  • ~c^rand()>>9 WYNIK: 350717 = 50 + 0 + 0 + 350667 + 0
  • ~c^rand()>>23 WYNIK: 51 = 51 + 0 + 0 + 0 + 0
kernigh
źródło
5

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

random.bf (dodano kanały dla zwiększenia czytelności)

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

Aby stworzyć unrandom.bf , musisz zmienić ostatni + w drugiej linii.

Większość kodu oparta jest na generatorze liczb losowych Daniela B Cristofaniego według Reguły 30 dostosowanym do dodawania liczby do każdego wejścia i kończenia, gdy nie ma już żadnych danych wejściowych.

* Przetestowałem dotychczas przetworzone bajty 212992 (przetworzone po 12 godzinach) i oba pliki zmieniają się w skompresowany plik 213064. Myślę, że można to zrobić do końca tygodnia na pewno, ale nie chcę czekać z wysłaniem. Zaktualizuję wynik, jeśli jest niepoprawny, ale zachowaj rozwiązanie, ponieważ przepis 30 rządzi!

Ciekawostki: Reguła 30 została odkryta przez Stephena Wolframa w 1983 roku i według Wikipedii jest używana do tworzenia losowych liczb całkowitych w Mathematica.

Kompilacja i uruchomienie:

Wykorzystuje wykładniczy czas i przestrzeń (iteruje ponad 32 więcej komórek na przetworzony znak), więc wymaga środowiska wykonawczego BrainFuck, który ma co najmniej 178 876 517 komórek do kodowania pliku Shakespear, nie traktuj non ascii jako Unicode, ma szersze niż 8 bitów komórki i wykorzystuje -1 jako eof (różni się między 255 a -1). Zwykle używam tłumaczy innych ludzi, ale tym razem muszę być wtyczką i promować własne:

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 kompiluje BrainFuck do zoptymalizowanego C i nadużywa Perla Inline :: C, aby go uruchomić. Jest dołączony do mojego kompilatora Extended BrainFuck . Przy rozmiarze i szerokości komórki w argumencie przydzieli około 400 MB.

Sylwester
źródło
3

CJam, 22 bajty

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

Używa opóźnionego generatora Fibonacciego z relacją powtarzalności s n = (s n-5 + s n-16 )% 255 (który wybrałem przez pomyłkę, ale mimo to działa) i trywialny materiał siewny do wygenerowania pseudolosowego strumienia bajtów , który następnie XORs z wejściem.

Przetestowałem swój kod w CJam 0.6 , który został opublikowany 1 maja 2014 r.

Jak to działa

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.

Wynik

$ 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
źródło
3

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

Bo czy naprawdę powierzyłbyś zadanie zmanipulowania danych nie do poznania jakimkolwiek innym językiem?

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

Podczas gdy wszystkie inne rozwiązania są oparte na „bezpiecznych” konstrukcjach, takich jak „generatory liczb losowych” lub „kryptografia klasy wojskowej”, to jedno po prostu interpretuje ciągi znaków reprezentujące długości nieparzyste o długości modulo 2–256 ^ i oblicza ich modułową odwrotność .

Próbny:

$ 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
źródło
2

skrypt powłoki, 203

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

Uruchamianie:

% 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

Niezbyt przenośny, ale może być wykonany kosztem kilku bajtów. Wymaga PGP (możliwa byłaby również implementacja z OpenSSL). Prawdopodobnie można zapisać różnicę około 50 bajtów między zakodowanym plikiem a oryginałem.

Punktacja:

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

Kopiuj
źródło
1

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

Punktacja karze Cię za uczynienie pliku całkowicie nieściśliwym, ponieważ wtedy skompresowany plik jest większy niż narzut kompresji. Tak więc mój program czyni je nieco mniej niż całkowicie nieściśliwymi:

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:]))

Wynik:

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
źródło
Przy obecnych zasadach nie ma kary za większy rozmiar skompresowanego pliku. Czy zasady się zmieniły? Jeśli tak, taka zmiana była niesprawiedliwa dla tego programu.
kernigh
@kernigh: Tak, zmienili się po tym, jak to opublikowałem. Naprawdę powinni byli być tacy, jak teraz.
Claudiu