Frustrar la compresión LZMA2

11

Objetivo

Cree un programa o un par de programas que interrumpan y arreglen colectivamente archivos con la intención de evitar que LZMA2 funcione de manera efectiva. Las rutinas de interrupción y reparación deben ser recíprocas, para que pueda recuperar el archivo original exactamente.

Objetivos

Métodos de compresión

  • Ubuntu / relacionado: xz -kz5 <infile>
  • Ventanas: 7z.exe a -txz -mx5 <outfile> <infile>
  • Otro: Use un compresor LZMA2 con nivel de compresión 5 que comprima las obras de Shakespeare a 1570550 bytes ± 100 bytes.

Puntuación; suma de (todo está en bytes ls -lo dir):

  • Tamaño del programa (s) (lo que sea necesario colectivamente para "romper" / arreglar el archivo de forma reversible)
  • Diferencia de tamaño (absoluto) entre:
    • Obras recopiladas sin procesar de Shakespeare y su copia modificada (sin comprimir).
    • Foto sin procesar y su copia modificada (sin comprimir).
  • Diferencia de tamaño o 0, lo que sea mayor entre:
    • Trabajos recopilados sin procesar de Shakespeare menos su copia comprimida LZMA2 modificada.
    • Foto sin procesar menos su copia comprimida LZMA2 modificada.

Ejemplo

Ejemplo de Python 2.x mal puntuado, perezosamente golfizado, pero compatible:

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)

Corriendo...

$ 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

Puntuación

  • = 194 + abs (5589891 - 5589891) + max (5589891 - 3014136, 0) + abs (1659874 - 1659874) + max (1659874 - 1646556, 0)
  • = 194 + 0 + 2575755 + 0 + 13318
  • 2,589,267 bytes. Malo, pero no hacer nada a los archivos produce una puntuación de 4,635,153 bytes.

Aclaración

Esto es golf, por lo que está tratando de minimizar su puntaje. No estoy seguro de si los comentarios señalan un agujero legítimo en mi puntuación o si lo son porque lo hice demasiado complicado. En cualquier caso, quieres lo MÁS PEQUEÑO :

  • código fuente
  • diferencia entre el archivo modificado sin comprimir y el archivo original (por ejemplo, si lo modifica agregando un billón de ceros al final, su puntaje subió un billón de bytes)
  • diferencia entre el archivo modificado comprimido y el archivo original (por ejemplo, cuanto más incompresibles sean los archivos, mayor será su puntaje). Un archivo perfectamente incompresible que crezca ligeramente o no se puntuará 0.
code-challenge compression Nick T
fuente
2
La respuesta de trolling: Paso 1: calcule cuánto espacio libre tiene en el disco y luego divídalo por el tamaño del archivo para obtener N. Paso 2: agregue el archivo a sí mismo N veces y agregue el número N. Paso 3: tenga en cuenta que hay no queda espacio para comprimir el archivo, pero termina con una diferencia absoluta en los tamaños de archivo de varios terrabytes (o más) ... [Para revertir, lea N desde el final del archivo y reduzca el archivo a 1 / Nth del tamaño. ]
MT0
@ MT0: Ah, creo que la solución es que las diferencias no deberían ser absolutas. Si su archivo modificado es más grande, eso debería restar puntos.
Claudiu
@ MT0 si modifica el archivo para que sea un terabyte grande, su puntaje será de 1 terabyte ... bastante malo cuando intente jugar al golf.
Nick T
@ MT0 Agregué una aclaración a la publicación, ¿eso ayuda?
Nick T
2
Una objeción. El compresor podría hacer un archivo más grande si t es especialmente incompresible. En este caso deberías ser recompensado, no castigado, ¿no?
Claudiu

Respuestas:

8

Python, puntuación = 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

Hace un pad de una sola vez usando md5 en modo contador . Xors el archivo con él. Esto tiene la ventaja de que los archivos originales e interrumpidos son del mismo tamaño, y que el disruptor y el fijador son el mismo programa.

Los archivos interrumpidos comprimidos son más grandes que los originales.

Keith Randall
fuente
Ajusté la puntuación, por lo que si los archivos comprimidos son más grandes que sus contrapartes originales, no se lo penaliza y solo puntúan 0. No estoy seguro de cuál era la diferencia para sus archivos, pero es posible que desee actualizar la puntuación
Nick T,
@NickT: actualizado.
Keith Randall
8

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

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

Bajo los trucos de golf , este programa realiza un bucle para cada byte en la entrada estándar, y lo hace de forma exclusiva o con un pad infinito de rand (). Probé esto con rand () en libc de OpenBSD 5.5.

Uso:

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

Para probar mi programa, escribí un script de shell test.sh (57 líneas) para compilar mi programa y calcular mi puntaje.

$ 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

Notas sobre rand () y el desplazamiento a la derecha

Cualquier algoritmo de compresión no puede comprimir datos aleatorios. Puedo disfrazar pg100.txt y filament.jpg como datos aleatorios si los codifico con un cifrado de flujo .

Mi primera idea fue hacer un texto exclusivo o simple con el teclado para crear texto cifrado , luego almacenar el texto cifrado y el teclado en el archivo codificado. Esto aumentaría el tamaño del archivo y aumentaría mi puntaje. La opción obvia es usar el mismo pad para cada archivo y almacenar solo texto cifrado en el archivo codificado. Si solo llamo a rand (), usa una semilla predeterminada de 1 y hace el mismo pad cada vez.

OpenBSD 5.5 define rand () en stdlib.h y 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));
}

Este es un generador congruencial lineal . El gran defecto es que los bits bajos tienen períodos cortos. El primer bit tiene un período de 2: si lanzas una moneda rand()&1, iría cara , cruz, cara, cruz, etc. El enésimo bit tiene un período de 2 n . Hay 31 bits, por lo que toda la secuencia tiene un período de 2 31 .

LZMA2 puede encontrar patrones en períodos cortos y comprimirlos. El código más corto ~c^rand()toma los 8 bits bajos y no impide la compresión. El cambio correcto en ~c^rand()>>9ayuda, pero no lo suficiente. Yo uso ~c^rand()>>23.

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

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

random.bf (avances de línea añadidos para facilitar la lectura)

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

Para crear unrandom.bfnecesita cambiar el último + en la segunda línea.

La mayor parte del código se basa en el generador de números aleatorios basado en la Regla 30 de Daniel B Cristofani adaptado para agregar el número a cada entrada y para terminar cuando no hay más entrada.

* He probado los bytes que ha procesado hasta ahora 212992 (procesados ​​después de 12 horas) y ambos archivos se convierten en un archivo comprimido 213064. Supongo que podría hacerse antes de fin de semana para saberlo con certeza, pero no quiero esperar con la publicación. Actualizaré el puntaje si está mal, ¡pero mantén la solución ya que Rule30 es genial!

Curiosidades: Stephen Wolfram descubrió la Regla 30 en 1983 y, según Wikipedia, se usa para producir enteros aleatorios en Mathematica.

Compilación y ejecución:

Utiliza tiempo y espacio exponenciales (itera más de 32 celdas más por char procesado), por lo que requiere un tiempo de ejecución BrainFuck que tiene al menos 178,876,517 celdas para codificar el archivo Shakespear, no trate los no ascii como unicode, tiene celdas más anchas de 8 bits y usa -1 como eof (para diferir entre 255 y -1). Usualmente uso intérpretes de otras personas, pero esta vez necesito ser un complemento y promover el mío:

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 compila BrainFuck para C optimizado y abusa de Perl Inline :: C para ejecutarlo. Se incluye con mi compilador Extended BrainFuck . Con el tamaño y el ancho de la celda en el argumento, asignará aproximadamente 400 MB.

Sylwester
fuente
3

CJam, 22 bytes

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

Esto utiliza un generador de Fibonacci rezagado con relación de recurrencia s n = (s n-5 + s n-16 )% 255 (que seleccioné por error, pero funciona de todos modos) y una semilla trivial para generar un flujo de bytes pseudoaleatorio , que luego XOR con la entrada.

He probado mi código con CJam 0.6 , que se publicó el 1 de mayo de 2014.

Cómo funciona

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.

Puntuación

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

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

¿Porque realmente confiaría la tarea de manipular sus datos más allá del reconocimiento a cualquier otro idioma?

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

Si bien todas las demás soluciones se basan en construcciones "seguras" como "generadores de números aleatorios" o "criptografía de grado militar", esta simplemente interpreta las cadenas como representantes de números impares módulo 2⋅256 ^ de longitud, y calcula su inverso modular .

Manifestación:

$ 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
fuente
2

script de shell, 203

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

Ejecutándolo:

% 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

No es muy portátil, pero podría hacerse a costa de un par de bytes. Requiere PGP (también sería posible una implementación con OpenSSL). La diferencia de ~ 50 bytes entre el archivo codificado y el original probablemente se pueda guardar.

Puntuación:

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

Copiar
fuente
1

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

La puntuación lo penaliza por hacer que el archivo sea completamente incompresible, ya que el archivo comprimido es más grande que la sobrecarga de compresión. Por lo tanto, mi programa los hace un poco menos que totalmente incompresibles:

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

Resultado:

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
fuente
Con las reglas actuales, no hay penalización por que un archivo comprimido sea más grande. ¿Cambiaron las reglas? Si es así, dicho cambio fue injusto para este programa.
Kernigh
@kernigh: Sí, cambiaron después de que lo publiqué. Verdaderamente deberían haber sido como son ahora desde el principio.
Claudiu