Verhindern Sie die LZMA2-Komprimierung

11

Tor

Erstellen Sie ein Programm oder ein Programmpaar, das gemeinsam Dateien stört und repariert, um zu verhindern, dass LZMA2 effektiv funktioniert. Die Unterbrechungs- und Korrekturroutinen müssen wechselseitig sein, damit Sie die Originaldatei genau wiederherstellen können.

Ziele

Komprimierungsmethoden

  • Ubuntu / verwandt: xz -kz5 <infile>
  • Windows: 7z.exe a -txz -mx5 <outfile> <infile>
  • Sonstiges: Verwenden Sie einen LZMA2-Kompressor mit Komprimierungsstufe 5, der die Werke von Shakespeare auf 1570550 Byte ± 100 Byte komprimiert.

Wertung; Summe von (alles ist in Bytes ls -loder dirso):

  • Programmgröße (was auch immer zusammen benötigt wird, um die Datei reversibel zu "brechen" / zu reparieren)
  • Größenunterschied (absolut) zwischen:
    • Rohe gesammelte Werke von Shakespeare und Ihre modifizierte (unkomprimierte) Kopie.
    • Rohfoto und Ihre modifizierte (unkomprimierte) Kopie.
  • Größenunterschied oder 0, je nachdem, welcher Wert größer ist zwischen:
    • Rohe gesammelte Werke von Shakespeare abzüglich Ihrer modifizierten, LZMA2-komprimierten Kopie.
    • Rohfoto abzüglich Ihrer modifizierten, LZMA2-komprimierten Kopie.

Beispiel

Schlecht punktendes, träge Golf, aber konformes Python 2.x-Beispiel:

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)

Laufen...

$ 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

Ergebnis

  • = 194 + abs (5589891 - 5589891) + max (5589891 - 3014136, 0) + abs (1659874 - 1659874) + max (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2,589,267 Bytes. Schlecht, aber nichts mit den Dateien zu tun, ergibt eine Punktzahl von 4.635.153 Bytes.

Klärung

Dies ist Golf, also versuchen Sie, Ihre Punktzahl zu minimieren . Ich bin mir nicht sicher, ob die Kommentare auf ein legitimes Loch in meiner Wertung hinweisen oder ob sie es sind, weil ich es zu kompliziert gemacht habe. In jedem Fall möchten Sie das KLEINSTE :

  • Quellcode
  • Unterschied zwischen der unkomprimierten geänderten Datei und der Originaldatei (z. B. wenn Sie sie ändern, indem Sie am Ende eine Billion Nullen anhängen, ist Ihre Punktzahl nur um eine Billion Bytes gestiegen)
  • Unterschied zwischen der komprimierten modifizierten Datei und der Originaldatei (z. B. je inkompressibler die Dateien werden, desto höher ist Ihre Punktzahl). Eine perfekt inkompressible Datei, die leicht oder gar nicht wächst, erhält 0 Punkte.
code-challenge compression Nick T.
quelle
2
Die Trolling-Antwort: Schritt 1 - Berechnen Sie, wie viel freien Speicherplatz Sie haben, und teilen Sie diesen durch die Größe der Datei, um N zu erhalten. Schritt 2 - Hängen Sie die Datei N-mal an sich selbst an und fügen Sie die Nummer N hinzu. Schritt 3 - Stellen Sie fest, dass es Speicherplatz gibt Es bleibt kein Speicherplatz mehr zum Komprimieren der Datei übrig, es ergibt sich jedoch ein absoluter Unterschied in der Dateigröße von mehreren Terrabyte (oder mehr) .... [Um dies umzukehren, lesen Sie N vom Ende der Datei und verkleinern Sie die Datei auf 1/9 der Größe. ]
MT0
@ MT0: Ah ich denke die Lösung ist, dass die Unterschiede nicht absolut sein sollten. Wenn Ihre geänderte Datei größer ist, sollten Punkte abgezogen werden.
Claudiu
@ MT0 Wenn Sie die Datei so ändern, dass sie ein Terabyte groß ist, beträgt Ihre Punktzahl 1 Terabyte ... ziemlich schlecht, wenn Sie versuchen, Golf zu spielen.
Nick T
@ MT0 Ich habe dem Beitrag eine Klarstellung hinzugefügt, hilft das?
Nick T
2
Ein Streit. Der Kompressor erstellt möglicherweise eine größere Datei, wenn t besonders inkompressibel ist. In diesem Fall solltest du belohnt, nicht bestraft werden, oder?
Claudiu

Antworten:

8

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

Erstellt ein einmaliges Pad mit md5 im Zählermodus . xors die Datei damit. Dies hat den Vorteil, dass die ursprüngliche und die gestörte Datei dieselbe Größe haben und dass der Störer und der Fixierer dasselbe Programm haben.

Die komprimierten gestörten Dateien sind größer als die Originale.

Keith Randall
quelle
Ich habe die Bewertung so angepasst, dass wenn die komprimierten Dateien größer sind als ihre ursprünglichen Gegenstücke, Sie nicht bestraft werden und sie nur 0 Punkte erzielen. Sie sind sich nicht sicher, wie der Unterschied für Ihre Dateien war, aber Sie möchten möglicherweise die Bewertung aktualisieren
Nick T
@ NickT: aktualisiert.
Keith Randall
8

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

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

Unter den Golf-Tricks durchläuft dieses Programm jedes Byte in der Standardeingabe und wird exklusiv ausgeführt - oder mit einem unendlichen Pad von rand (). Ich habe dies mit rand () in libc von OpenBSD 5.5 getestet.

Verwendung:

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

Um mein Programm zu testen, habe ich ein Shell-Skript test.sh (57 Zeilen) geschrieben , um mein Programm zu kompilieren und meine Punktzahl zu berechnen.

$ 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

Hinweise zu rand () und der Rechtsverschiebung

Jeder Komprimierungsalgorithmus kann keine zufälligen Daten komprimieren. Ich kann pg100.txt und filament.jpg als zufällige Daten tarnen , wenn ich sie mit einer Stream-Verschlüsselung verschlüssele .

Meine erste Idee war, Exklusiv- oder Klartext mit Pad zu erstellen , um Chiffretext zu erstellen , und dann sowohl Chiffretext als auch Pad in der verschlüsselten Datei zu speichern. Dies würde die Größe der Datei erhöhen und meine Punktzahl erhöhen. Die naheliegende Wahl besteht darin, für jede Datei dasselbe Pad zu verwenden und nur Chiffretext in der verschlüsselten Datei zu speichern. Wenn ich nur rand () aufrufe, wird ein Standard-Startwert von 1 verwendet und jedes Mal das gleiche Pad erstellt .

OpenBSD 5.5 definiert rand () in stdlib.h und 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));
}

Dies ist ein linearer Kongruenzgenerator . Der große Fehler ist, dass niedrige Bits kurze Perioden haben. Das erste Bit hat eine Periode von 2: Wenn Sie eine Münze mit werfen rand()&1, geht es um Köpfe, Schwänze, Köpfe, Schwänze und so weiter. Das n-te Bit hat eine Periode von 2 n . Es gibt 31 Bits, daher hat die gesamte Sequenz eine Periode von 2 31 .

LZMA2 kann Muster in kurzen Zeiträumen finden und komprimieren. Der kürzeste Code ~c^rand()nimmt die niedrigen 8 Bits und verhindert nicht die Komprimierung. Die richtige Verschiebung ~c^rand()>>9hilft, aber nicht genug. Ich benutze ~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
quelle
5

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

random.bf (Zeilenvorschübe zur besseren Lesbarkeit hinzugefügt)

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

Zum Erstellen müssen unrandom.bfSie das letzte + in der zweiten Zeile ändern.

Der größte Teil des Codes basiert auf dem auf Regel 30 basierenden Zufallszahlengenerator von Daniel B. Cristofani, der angepasst wurde, um die Nummer zu jeder Eingabe hinzuzufügen und zu beenden, wenn keine Eingabe mehr vorhanden ist.

* Ich habe die bisher verarbeiteten Bytes 212992 (nach 12 Stunden verarbeitet) getestet und beide Dateien werden zu einer komprimierten 213064-Datei. Ich denke, es könnte sicher bis Ende der Woche fertig sein, aber ich möchte nicht mit dem Posten warten. Ich werde die Punktzahl aktualisieren, wenn es falsch ist, aber die Lösung behalten, da Regel 30 rockt!

Wissenswertes: Regel 30 wurde 1983 von Stephen Wolfram entdeckt und laut Wikipedia verwendet, um zufällige ganze Zahlen in Mathematica zu erzeugen.

Zusammenstellung und Ausführung:

Es verwendet exponentielle Zeit und Raum (iteriert über 32 weitere Zellen pro verarbeitetem Zeichen), sodass eine BrainFuck-Laufzeit erforderlich ist, die mindestens 178.876.517 Zellen zum Codieren der Shakespear-Datei enthält, Nicht-ASCII nicht als Unicode behandelt, mehr als 8-Bit-Zellen enthält und verwendet -1 als eof (zwischen 255 und -1 zu unterscheiden). Normalerweise benutze ich Dolmetscher anderer Leute, aber dieses Mal muss ich ein Plug sein und meine eigenen fördern:

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 kompiliert BrainFuck zu optimiertem C und missbraucht Perl Inline :: C, um es auszuführen. Es wird mit meinem Extended BrainFuck-Compiler gebündelt . Mit der Zellengröße und -breite im Argument werden ungefähr 400 MB zugewiesen.

Sylwester
quelle
3

CJam, 22 Bytes

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

Dies verwendet einen verzögerten Fibonacci-Generator mit der Wiederholungsrelation s n = (s n-5 + s n-16 )% 255 (den ich versehentlich ausgewählt habe, der aber trotzdem funktioniert) und einen trivialen Startwert, um einen pseudozufälligen Strom von Bytes zu erzeugen , die es dann mit der Eingabe XORs.

Ich habe meinen Code mit CJam 0.6 getestet , das am 1. Mai 2014 veröffentlicht wurde.

Wie es funktioniert

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.

Ergebnis

$ 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
quelle
3

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

Denn würden Sie wirklich die Aufgabe anvertrauen, Ihre Daten bis zur Unkenntlichkeit einer anderen Sprache zuzuordnen?

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

Während alle anderen Lösungen auf „sicheren“ Konstruktionen wie „Zufallszahlengeneratoren“ oder „Kryptographie in Militärqualität“ basieren, interpretiert diese einfach Zeichenfolgen als ungerade Zahlen mit einer Länge von Modulo 2⋅256 ^ und berechnet ihre modulare Inverse .

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
quelle
2

Shell-Skript, 203

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

Ausführen:

% 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

Nicht sehr portabel, könnte aber auf Kosten von ein paar Bytes hergestellt werden. Benötigt PGP (eine Implementierung mit OpenSSL wäre ebenfalls möglich). Der Unterschied von ~ 50 Byte zwischen codierter Datei und Original kann wahrscheinlich gespeichert werden.

Wertung:

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

Kopieren
quelle
1

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

Die Bewertung bestraft Sie dafür, dass Sie die Datei vollständig unkomprimierbar machen, da die komprimierte Datei vom Komprimierungsaufwand größer ist. Mein Programm macht sie also etwas weniger als völlig unkomprimierbar:

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

Ergebnis:

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
quelle
Mit den aktuellen Regeln gibt es keine Strafe dafür, dass eine komprimierte Datei größer ist. Haben sich die Regeln geändert? Wenn ja, war eine solche Änderung für dieses Programm unfair.
Kernigh
@kernigh: Ja, sie haben sich geändert, nachdem ich es gepostet habe. Wahrlich, sie hätten von Anfang an so sein sollen, wie sie jetzt sind.
Claudiu